Uni Bonn / CS Department / Chair V / (deutsch)

For the moment we have this document only in German. Soon it will be also in English.

Diskrete Algorithmen und ihre Anwendung in der Naturwissenschaft und Technik (Th. Lengauer)

Schwerpunkte in Forschung und Lehre

Die Bearbeitung der Forschungsvorhaben erfolgt in Arbeitsgruppen, die sowohl an der GMD (Gesellschaft für Mathematik und Datenverarbeitung mbH) als auch an der Universität Bonn plaziert sind.

Molekulare Bioinformatik

Die dreidimensionale Struktur von Proteinen bildet die Grundlage für ihre chemishe Funktion. Daher ist die Vorhersage drei dimensionaler Proteinstrukturen auf der Basis der Aminosäuresequenz des Proteins eine wesentliche Komponente eines effektiven rechnergestützten Entwurfs biochemischer Wirkstoffe. Wesentliche Beiträge zur Lösung von Strukturvorhersageproblemen können diskrete Modellierungen liefern. In dem Forscungsbereich werden auf diskreter Modellierung basierende Untersuchungen von topologischen Strukturen von Proteinen durchgeführt. Weitere Arbeiten betreffen den Einsatz Rechnern bei der Beantwortung von Fragen, die im Rahmen der Strukturaufklärung von der mit MHC-II Molekülen assoziierten invarianten Ketten auftreten.Diese Arbeiten finden im Rahmen einer Kooperation mit Prof. Dr. Norbert Koch aus dem Forschungsbereich Immunbiologie statt.
Heute benötigt eine erfolgreiche Strukturvorhersage bei Proteinen hochwertige Alignments von Proteinsequenzen, die sowohl evolutionäre Eigenschaften als auch strukturelle Verwandtschaften zwischen unterschiedlichen Proteinen aufdecken. Die Verbesserung von Algorithmen für Alignments zweier Proteinsequenzen basiert auf der Neudefinition entsprechender Parametersätze und ihrer systematischen Erschließung. Dabei muß auch die Verteilung nicht-optimaler Alignments untersucht werden.
In dieses Forschungsgebiet gehört weiterhin die Entwicklung von Algorithmen zum Alignmen von mehr als zwei Proteinsequenzen, zur Einbettung einer Sequenz in eine bekannte Struktur und zum 3D-Strukturvergleich.
Der Bindungsprozeß von Rezeptoren und Liganden, der die Grundlage sämtlicher biochemischer Wechselwirkungen darstellt, wird allgemein als Docking bezeichnet. Ziel der Forschungsarbeiten ist es, anhand von neuen Algorithmen und Datenbankkonzepten ein System zu entwickeln, daß es ermoglicht, aus unterschiedlichen Sequenz- und Strukturdaten und weiteren Informationen 3D-Modelle von Rezeptor-Ligand-Komplexen zu generieren. Diese dienen als Ausgangspunkt für die Entwicklung von biochemischen Wirkstoffen. In diesem Bereich wird mit Industrieunternehmen kooperiert.

Molekulare Modellierung anorganischer amorpher Festkörper

Ziel dieser Forschung, die in Zusammenarbeit mit chemischen und physikalischen Instituten der Universität Bonn sowie der DLR Porz durchgefürt wird, ist die Analyse der räumlichen Struktur von anorganischen amorphen Clustern mithilfe von z.T. diskreten, z.T. nimmerischen rechengestützten Verfahren. Eingabedaten sind a priori Kenntnisse über die amorhen Systeme sowie Informationen, die aus Spektren verschiedenster Art gewonnen werden.

Entwurfs- und Packungsprobleme

Viele Entwurfsprobleme in den verschiedensten technischen und wissenschaftlichen Disziplinen lassen sich als Graphenprobleme formulieren. Hierarchische Entwürfe, wie sie häufig vorgenommen werden, führen dabei Graphen mit erheblichen Regelmäßigkeiten. Solchen Graphen können mit speziellen Methoden besonders schnell analysiert werden. Bei der Größe heutiger Entwürfe, besonders im Software- und Hardware-Entwurfsbereich, spielen solche Effizienzgewinne eine entscheidende Rolle, da die Entwürfe die Speichermöglichkeiten selbst zukünftiger Rechner überfordern.
Der gegenwärtige Schwerpunkt der Forschungsarbeiten liegt hier im Bereich der Analyse solcher Graphen, die Ablaufdiagramme regelmäßiger Programmstücke (Schleifenprogramme oder rekursive Programme) darstellen. Die theoretische Grundlage dazu bildet die Analyse der Zusammenhangskomponenten und Weglängen in gitter-strukturierten regelmäßigen Graphen.
Das Layaout integrierter Schaltkreise wird üblicherweise in verschiedene Phasen eingeteilt. Die Bewertungskriterien der generierten Strukturen sind in einigen dieser Phasen i.allg. konkurrierend. Selbst die sequentielle optimale Bearbeitung jeder einzelnen Phase führt nicht zu einer optimaler Gesamtlösung. In diesem Forschungsvorhaben wird versucht, mit Methoden dar ganzzahligen Programmierung die Phase der globalen Verdratung und die Phase der Plazieruing zu integrieren, um konkurrierende Kriterien beider Phasen gleichzeitig zu optimieren und die Taxonomie des Gesamtproblems zu analysieren.
Die High-level-Synthese ist der Abschnitt des Entwurfs integrierter Scaltkreise, bei dem aus einer algorithmischen Verhaltensbeschreibung des Schaltkreises eine Blockstruktur des Schaltkreises auf der Register-Tranfer Ebene erstellt wird. Diese Struktur wird in einer anschließenden Phase, dem Layout-Entwurf, auf dem Chip ausgelegt. In diesem Forschungsvorhaben werden Methoden entwickelt, die die High-level-Synthese mit ausreichend Layout-Information ausgestatten sollen, um für das erzeugte Blockschaltbild ein Layout hoher Qualität generieren zu können.
Bei der Schnittbilderstellung in der lederverarbeitenden Industrie werden beliebig geformte Schablonen disjunkt auf beliebig geformten Unterlagen (Tierhäuten) plaziert, wobei die Verschnittfläche minimiert werden soll. Hinzu kommen Nebenbedingungen, wie etwa Rechenzetanforderungen im Minutenbereich und die Einhaltung von Qualitätsanforderungen auf Unterlagen mit nichthomogener Lederqualität. Im Rahmen einer Industriekooperation ist ein Software-Paket zur automatischen Schnittbilderstellung implementiert worden, das laufend an realen Daten getestet und verbessert wird.
In der Textilindustrie sind zusätzlich zahlreiche Randbedingungen zu beachten. Zum Beispiel ist die Lage einiger Teile zueinander vorgeschrieben, müssen die Musterungen auf der Unterlage oder den Teilen beachtet werden können die Drehwinkel der Teile beschränkt sein. Die Unterlage hat eine feste Breite und eine potentiell unendliche Länge. Zur Lösung des Nesting-Problems in der textilverarbeitenden Industrie wird ein Algorithmus basierend auf einem Simulatedannealing-Ansatz entwickelt.
In der Automobilindustrie treten komplexe dreidimensionale Packungsprobleme auf. Gesamtziel ist, die Aggregate innerhalb eines Fahrzeugs so zu plazieren, daß bei kompakten Außenmaßen großtmöglicher Komfort für den Fahrgast und hohe Wartungsfreundlichkeit erziehlt wird. Die Lösung solcher Probleme mit rechnergestützten Optiemierungsverfahren steckt heute noch in den Anfängen. Im Dialog mit einem Führenden Automobilhersteller entwickeln wir Modelle und Methodiken für diese Probleme.

Modellierung nebenläufiger Prozesse mit Hilfe von Petrienetzen

Petrinetze, ein wesentliches Modellierungswerkzeug für asynchrone nebenläufige Prozesse, sind von einem früheren Institutsleiter von SCAI, Prof. Petri, erfunden und von seiner Forschungsgruppe an der GMD wesentlich weiterentwickelt worden. Nach zwei Jahrzehnten erfolgreicher theoretischer Forschungsarbeit konzentriert sich die Forschungsarbeit in diesem Bereich auf die Einbringung der hierbei gewonnenen Erkenntnisse in Anwendungen aus den Bereich Schaltkreisenentwurf, Verfahrenstechnik, Regelungs- und Automatisierungstechnik, Betriebswirtschaft etc..

Computer-Algebra

In diesem Bereich konzentriert sich die Forschungsarbeit auf die symbolische Lösung von gewöhnlichen Differentialgleichungen. Dabei werden Algorithmen entwickelt und implementiert, die Lösungsmengen vollständig bestimmen oder auch die Nicht-Existenz bestimmter Klassen von Lösungen nachweisen. Unter den Anwendungen konzentriert sich die Gruppe auf Gebiete wie nichtlineare Dynamik, Astronomie und Robotik.

Weitere Informationen

Über die hier kurz beschribenen Forschungsaktivitäten geben gesonderte Publikationen von SCAI detaillierte Auskunft, die bei Weßkopf (Tel: 02241/14 2776, Fax:02241/14 2656) angefordert werden können.

Weitere aktivitäten des Instituts finden Sie im Institutsbericht (Postscript)

By problems with our WWW server please tell us by electronic mail:

webmaster@theory.cs.uni-bonn.de

Uni Bonn / CS Department / Chair V / (deutsch)