2011

2010

2009

• Rümpler, Christian; Berger, Frank (Betreuer); Lindmayer, Manfred (Betreuer); Stammberger, Hartwig (Betreuer): Lichtbogensimulation für Niederspannungsschaltgeräte. Stuttgart : Fraunhofer Verlag, 2009 Zugl.: Ilmenau, Techn. Univ., Diss., 2009 Schlagwörter: Niederspannungsschaltlichtbogen; Magnetohydrodynamik; Simulation; Strahlungstransport; Metalldampf; Dissertation Institutsveröffentlichung: SCAI: Abteilung: SIAN
  Abstract: Inhalt der vorliegenden Arbeit ist die Simulation des Schaltlichtbogens für die Anwendung in Niederspannungsschaltgeräten. Die zu Grunde liegenden magnetohydrodynamischen Gleichungen werden in einem gekoppelten Ansatz gelöst. Für die verbesserte Abbildung des wichtigen Energietransportmechanismus Strahlung wird ein nicht-graues P1-Modell implementiert und an einfachen Anordnungen verifiziert. Die Berechnungsergebnisse für einzelne Frequenzbänder liefern weitergehende Informationen über das optische Verhalten. Unter Lichtbogenbelastung wird Elektrodenmaterial freigesetzt, welches die Eigenschaften des Plasmas beeinflusst. Daher wird der Transport von Metalldampf ebenfalls im Modell berücksichtigt. Das Einlaufen des Lichtbogens in Löschbleche wird insbesondere durch die Fallspannungen an Anode und Kathode bestimmt. Hierfür wird ein einfach anzuwendendes Element für die Finite-Elemente-Berechnung entwickelt, welches die Fallspannungen als nichtlineare Widerstände abbildet. Verifikationsrechnungen an einer messtechnisch untersuchten rotationssymmetrischen Elektrodenanordnung zeigen, dass nur bei Berücksichtigung von Metalldampf die Bogenspannung richtig wiedergegeben werden kann. Berechnungen an einer Laufschienenanordnung mit einem Löschblech zeigen die Anwendbarkeit der Modelle für eine schalterähnliche Geometrie.

2001

• Baehr, Hanno C.: Stability of continuous cyclic cohomology and operator ideals on Hilbert spaces. Münster, 2001 Münster, Univ., Diss., 2001 Schlagwörter: Dissertation Institutsveröffentlichung: SCAI

• Claußen, Holger: Effizientes Protein-Ligand-Docking mit flexiblen Proteinstrukturen. Sankt Augustin : GMD - Forschungszentrum Informationstechnik, 2001 (GMD research series; 2001, 11). Zugl.: Bonn, Univ., Diss., 2001 Schlagwörter: strukturbasierter Wirkstoffentwurf; computerbasierter Wirkstoffentwurf; Protein-Ligand-Wechselwirkungen; flexibles molekulares Docking; Proteinflexibilität; Dissertation Institutsveröffentlichung: SCAI
  Abstract: Medikamente greifen in das komplexe Netzwerk von Regel- und Stoffwechselprozessen eines Organismus ein, meist indem sie an bestimmte Zielmoleküle binden und ihre Funktion beeinflussen. Die Suche nach geeigneten Wirkstoffen bedient sich heute ausgefeilter experimenteller und computergestützter Verfahren, um neue Verbindurigen von therapeutischer Relevanz zu finden. Eine solche computerbasierte Methode ist das molekulare Docking. Diese Methode versucht auf Grundlage der dreidimensionalen Struktur eines Zielproteins zu entscheiden, ob gegebene Verbindungen (Liganden) eine hohe Bindungsaffinität zum Zielprotein besitzen, und zwar bevor die Substanzen synthetisiert werden. Die meisten Ansätze für das Docking-Problem berücksichtigen die Flexibilität der Liganden. Dagegen wird das Protein vor allem aus Effizienzgründen in der Regel als starres Objekt behandelt. Aus experimentellen Beobachtungen weiß man jedoch, daß es auch bei den Proteinen Konformationsänderungen aufgrund der Bindung verschiedener Liganden gibt (in dt£ced fit), die kritisch für das Docking sein können. Die hier vorgestellte Arbeit präsentiert einen neuen, effizienten Ansatz für das Docking-Problem, der in der Lage ist, Variationen der Proteinkonformation beim Docking zu berücksichtigen. Die Proteinfiexibilität wird dabei durch eine Menge (Ensemble) möglicher Proteinstrukturen repräsentiert, die während des Dockingprozesses zu neuen gültigen Proteinstrukturen rekombiniert werden können. Die Abhängigkeiten zwischen den Konformationen der einzelnen Strukturen verwaltet ein sog. Kompatibilitätsgraph, auf den Graphsuchalgorithmen angewendet werden. Die Methode wurde anhand von zehn Ensembles experimentell bestimmter Protein-Ligand-Komplexe evaluiert, bei denen die Lage der Liganden im Protein, sowie Konformationen der Bindungspartner bekannt sind.
  Abstract: Drugs interfere with the complex network of regulatoric and metabolic processes of an organism, mostly by binding to certain target molecules and affecting their function. Today, the search for appropriate agents uses sophisticated experimental and computer-aided procedures in order to find novel compounds of therapeutical relevance. One such computer based method is called molecular docking. This method tries to decide whether given compounds possess a high binding afiinity to the given target protein using its known three-dimensional structure, before the substance is synthezied actually. Most approaches for the docking problem take into account the flexibility of ligands. In contrast, the protein is usually treated as a rigid object largely for efficiency reasons. However, it is known from experimental data that conformational changes due to the binding to different ligands (induced fit) do also appear in proteins, which may be critical for docking. The work presented here, describes a novel and efflcient approach for the docking problem, which is able to take into account the protein fiexibility. The fiexibility of a protein is represented by a set (ensemble) of protein structures, which may be recombined to new valid protein structures during the docking process. The dependencies between the conformations of the particular structures are described by a so-called compatibility graph, to which graph search algorithms are applied. The method has been evaluated on the basis of ten ensembles of experimentally determined protein-ligand complexes, for which the position of the ligands within the protein and the conformations of the binding partners are known. Volltext

• Gastreich, Marcus: Werkzeuge zur Modellierung von Siliciumbornitrid-Keramiken : Entwicklung von Mehrkörperpotenzialen und Berechnungen zur NMR-chemischen Verschiebung. Sankt Augustin : GMD, 2001 (GMD research series; 2001, 23). Zugl.. Bonn, Univ., Diss., 2001 Schlagwörter: Theoretische Chemie; Festkörpermodellierung; Interatomare Kräfte; NMR; Keramiker; Dissertation Institutsveröffentlichung: SCAI

• Lang, Monika: Distributed relaxation multigrid applied to incompressible equations in computational fluid dynamics. Sankt Augustin : GMD - Forschungszentrum Informationstechnik, 2001 (GMD research series; 2001, 4). Zugl.: Essen, Univ., Diss. 2000 Schlagwörter: Navier-Stokes Equations; Multigrid; Distributive Gauss-Seidel Relaxation; Local Fourier Anlysis; Stability; Dissertation Institutsveröffentlichung: SCAI
  Abstract: Die numerische Simulation von Strömungen erfordert hocheffiziente Algorithmen, um den heutigen praktischen Anforderungen von Ingenieuren zu genügen. Im Rahmen dieser Dissertation der numerischen Strömungsmechanik wurde für die inkompressiblen Navier-Stokes Gleichungen ein schneller numerischer Algorithmus entwickelt und implementiert. Mit dem entwickelten Mehrgitter Verfahren wird hohe numerische Effizienz erreicht, wobei die verteilte Gauss-Seidel Relaxation als Glättung verwendet wird in Zyklen des "Full Approximation" Schemas (FAS-Zyklen) für nichtlineare Gleichungen. Eine detaillierte Stabilitätsanalyse (lokale Fourier Analyse) der diskreten Gleichungen ermittelt kritische Strömungsrichtungen in denen numerische Instabilitäten auftreten können. Die Effizienz des "Full Multigrid" Algorithmus (FMG) ist für mehrere physikalische Probleme dargestellt, wobei ein FAS-Zyklus für die hohe Genauigkeit der Ergebnisse ausreichend ist. Wichtig ist dabei die spezielle Behandlung von Gebieten nahe Strömungsrändern. Der numerische Algorithmus ist portabel implementiert für aktuell eingesetzte Betriebssysteme.
  Abstract: The numerical simulation of fluid flows requires highly efficient algorithms to satisfy current practical demands of engineers. The overall idea of this dissertation on computational fluid dynamics is to develop and implement a fast numerical algorithm for the incompressible Navier-Stokes equations. Numerical acceleration is achieved by the developed multigrid algorithm, where the distributive Gauss-Seidel relaxation serves as the smoothing scheme in the "Full Approximation Scheme"-cycles (FAS-cycles) for nonlinear equations. A detailed stability analysis (Local Fourier analysis) of the discrete equations determines critical flow directions where numerical instabilities can occur. The efficiency of the "Full Multigrid Algorithm" (FMG) is illustrated for several physical problems, where one FAS-cycle is sufficient for a high accuracy of the results. The specific treatment of areas near boundaries in relaxation and in grid transfer is essential for this. The numerical algorithm is portably implemented for the operating systems currently in use. Volltext

• Reschke, H.-G.: Analysis und Numerik von singilären Lösungen der Minimalflächengleichung. Köln, 2001 Köln, Univ., Diss., 2001 Schlagwörter: Dissertation Institutsveröffentlichung: SCAI

2000

• Lügering, Martin: Ganzzahlige Lineare Programmierung bei der Globalen Verdratung integrierter Schaltkreise. Universität Bonn, 2000 Bonn, Univ., Diss., 2001 Schlagwörter: Dissertation Institutsveröffentlichung: SCAI

1999

• Hess, Reinhold: Dynamically adaptive multigrid on parallel computers for a semi-implicit discretization of the shallow water equations. Sankt Augustin : GMD -Forschungszentrum Informationstechnik, 1999 (GMD research series; 99, 9). Zugl.: Köln, Univ., Diss., 1999 Schlagwörter: Multigrid; Adaptivity; Helmholtz equation; Parallel Solver; Shallow Water Equations; Dissertation Institutsveröffentlichung: SCAI
  Abstract: Numerische Wettervorhersagen und Klimasimulationen erfordern enorme Rechenleistungen; hohe Auflösung und Genauigkeit sind notwendig, um zuverlässige Ergebnisse zu erzielen. Im Rahmen dieser Dissertation des wissenschaftlichen Rechnens wurde ein numerisch hoch-effizientes meteorologisches Modell für Parallelrechner entwickelt. Numerische Effizienz wird dabei mit einem auf zweierlei Weise adaptiven Mehrgitterverfahren erreicht: Zum einen wird die räumliche Auflösung der finiten-Differenzen Diskretisierung an die tatsächlichen Erfordernisse der vorliegenden Wetterverhältnisse angepaßt. Hohe Auflösung wird nur in Gebieten angewandt, wo sie wirklich notwendig ist (z. B. in starken Tiefdruckgebieten). Da sich die Wetterverhältnisse während der Simulation ändern, müssen die Verfeinerungsgebiete angepaßt werden. Diese dynamische Anpassung wird vollautomatisch von einem Verfeinerungskriterium gesteuert, das auf einer Schätzung des lokalen Diskretisierungsfehlers beruht. Zum anderen wird Mehrgitter verwendet, um die Größe stabiler Zeitschritte zu erhöhen. Die semi-implizite Zeitdiskretisierung resultiert in einer skalaren helmholtz-ähnlichen Gleichung, die in jedem Zeitschritt mit adaptivem Mehrgitter (MLAT) gelöst wird. Der Mehrgitterzyklus ist an den Stabilitätsanforderungen des vorliegenden Modellfalls angepaßt. Das numerische Verfahren wurde mittels Gebietszerlegung und explizitem Datenaustausch (MPI) portabel auf Parallelrechnern mit verteiltem Speicher implementiert. Ein dynamischer Lastausgleichsalgorithmus berücksichtigt Nachbarschaftsbeziehungen, um den erforderlichen Datenaustausch zu reduzieren.
  Abstract: Numerical weather forecasting and climate predictions require enormous computing power since high resolution and accuracy are necessary to achieve reliable results. The overall idea of this dissertation on scientific computing is to develop and implement a numerically highly efficient basic meteorological model for parallel environments. Numerical acceleration is achieved by adaptive multigrid in two ways: Firstly, the resolution of the finite difference discretization is locally adapted to the actual requirements of the weather situation. High resolution is provided only where it is necessary (e. g. strong low pressure areas). Since the weather situation changes in a time dependent simulation the refinement areas have to be adapted. This dynamic adaptation is controlled by a refinement criterion based on the estimation of the local spatial discretization error and performed fully automatically. Secondly, multigrid is used to increase the sizes of stable time steps. The applied semi{implicit time scheme results in a Helmholtz equation, which is solved by MLAT. The cycling is adapted to the stability requirements of the actual model problem. In general, one very cheap multigrid cycle suffices. The numerical algorithm is portably implemented on parallel environments by the grid partitioning approach with explicit message passing. A dynamic load balance algorithm considers neighborhood relationships in order to reduce data transfer. Volltext

• Lemmen, Christian: Computational methods for the structural alignment of molecules. Sankt Augustin : GMD, 1999 (GMD research series; 99, 1). Zugl.: Bonn, Univ., Diss., 1999 Schlagwörter: Computer-aided drug design; Molecular superposition; Molecular similarity; Virtual database screening; Dissertation Institutsveröffentlichung: SCAI: Abteilung: ALG
  Abstract: Ähnlichkeit ist ein zentrales Konzept für den Vergleich molekularer Strukturen. Es gibt eine Fülle unterschiedlicher Definitionen molekularer Ähnlichkeit. Im Bereich molekularer Erkennung, welche ein zentrales Prinzip des Lebens auf subzellularem Level darstellt, ist die 3DStrukturähnlichkeit sicher die Wichtigste. Die Relativorientierung nimmt bei dem Vergleich von Molekülen als Objekte mit Volumen, Oberfläche und einer spezifischen Verteilung physikochemischer Eigenschaften eine Schlüsselfunktion ein. Da Moleküle flexibel sind, ist außerdem die Konformation von zentraler Bedeutung. In der vorliegenden Arbeit präsentieren wir Algorithmen, die es erlauben, plausible Relativorientierungen und Konformationen zu bestimmen und auf der Basis dieser sog. strukturellen Überlagerungen die molekulare Ähnlichkeit zu berechnen.
  Die Berechnung struktureller Überlagerungen ist unglücklicherweise außerordentlich schwierig. Erstens existiert kein handhabbares Modell zur vollständigen Beschreibung des Prozesses der molekularen Erkennung. Darüber hinaus beruht die molekulare Erkennung auf der Interaktion von (mindestens zwei) komplementären Strukturen, wogegen für die Strukturüberlagerung die Daten nur zur Hälfte zur Verfügung stehen. Zweitens hat das zugrundeliegende Optimierungsproblem eine hohe Anzahl von Freiheitsgraden.
  Wir präsentieren einen neuartigen Ansatz zur Modellierung des überlagerungsproblems in verschiedenen Varianten und bemühen sowohl kombinatorische als auch numerische Verfahren zu deren Lösung. Außerdem haben wir Algorithmen entwickelt, die es uns erlauben, die Gewichtungsparameter einer Bewertungsfunktion auf Trainingsdaten zu optimieren. Damit ist es uns möglich, die Ähnlichkeit auf der Basis der berechneten Überlagerung zu quantifizieren.
  Abstract: Similarity is an important concept for the comparison of molecular structures. There are a number of different definitions of molecular similarity. In the context of molecular recognition, which is one of the basic principles of life on a subcellular level, structural similarity in 3D space may be considered the most important. The relative orientation of the molecules plays a key role in comparing molecular structures being objects with volume, shape and a specific distribution of physicochemical properties. Since molecules are flexible objects, the conformation of the molecules is also crucial. In this study we present algorithms that allow meaningful relative orientations and conformations (i.e. structural alignments) to be determined and used as the basis for calculating molecular similarity.
  Unfortunately, the task of determining the structural alignment of molecules is extremely difficult. Firstly, no manageable model exists that describes the process of molecular recognition in its entirety. Furthermore, while molecular recognition is based on the interaction of (at least) two complementary molecules, in structural alignment only half of the data is available. Secondly, it is necessary to consider a high number of degrees of freedom for the underlying optimization problem.
  We present a novel approach to modeling the structural alignment problem, employing both combinatorial and numerical techniques for tackling various variants of this problem. In addition, we have developed algorithms that enable us to best possibly balance the weight of different parameters of a scoring function on the basis of a training set of examples. This then allows us to quantify similarity on the basis of the determined alignment.

1998

• Eulenstein, Oliver: Vorhersage von Genduplikationen und deren Entwicklung in der Evolution. Sankt Augustin : GMD, 1998 (GMD research series; 98, 20). Zugl.: Bonn, Univ., Diss., 1998 Schlagwörter: Phylogenetic tree; Gene.tree; Species-tree; Reconciled-tree; Measures for trees; Gene duplication; Dissertation Institutsveröffentlichung: SCAI: Abteilung: MOLBIO
  Abstract: Evolution vollzieht sich durch Genduplikation und Modifikation, durch deren wiederholte Anwendung die Natur die Vielzahl der heutigen unterschiedlichen Gene geschaffen hat. Wird ein Gen das eine wesentliche Funktion kodiert, dupliziert, so bewahrt eine Kopie diese Funktion für dessen Organismus. Die andere Kopie jedoch kann ungehindert modifiziert werden, wobei das UrsprungsGen dazu als Ausgangsbasis dient. Eine genaue Kenntnis vorausgegangener Genduplikationen ist für die zuverlässige Rekonstruktion phylogenetischer Beziehungen unerläßlich, welche uns dann erlaubt, die Funktionsvorhersage von Genen zu verbessern. Für einige Genfamilien, wie z.B. Globine oder Rhodopsine, sind Genduplikationen glaubhaft vorhergesagt worden, aber im allgemeinen sind diese noch unbekannt. Die Erforschung dieses unbekannten Gebietes stellt ein bedeutendes, noch ungelöstes Problem der heutigen Molekularbiologie dar. Um dieses Problem zu lösen, konstruierten wir einen Algorithmus, der ein erfolgreiches aber nicht formal beschriebenes Modell erweitert, welches ursprünglich von Biologen entwickelt wurde. Dieser Algorithmus sagt Genduplikationen durch die Auswertung der Inkonsistenzen zwischen zwei phylogenetischen Bäumen voraus, einem Genbaum und einem Speziesbaum. Der Genbaum stellt die Phylogenie für eine Menge aktueller Gene dar, während der Speziesbaum die Phylogenie der Wirts-Spezies dieser aktuellen Gene darstellt. Als Ausgabe berechnet der Algorithmus einen auf dessen vorhergesagte Genduplikationen abgestimmten Genbaum, welchen wir als Reconciled Tree bezeichnen. Für alle in der Praxis möglichen Anwendungen hat dieser Algorithmus ein lineares Laufzeitverhalten, in der Größe des gegebenen Genbaumes. Diese Zeitkomplexität ermöglicht es uns, die heutigen, schnell wachsenden Gendatenbanken nach Genduplikationen zu durchsuchen. Zuerst partitionieren wir dazu eine Gendatenbank in Genfamilien und rekonstruieren einen Genbaum für jede dieser Genfamilien durch einen etablierten und schnellen Rekonstruktions-Algorithmus. Dann suchen wir für jeden Genbaum seinen Speziesbaum in einer morphologischen Datenbank. Abschließend sagen wir die Genduplikationen für jedes Paar von Gen- und Speziesbaum voraus. Somit können wir in der Gendatenbank verborgene Genduplikationen vorhersagen. Während unser Algorithmus Genduplikationen vorhersagt, ordnet er gleichzeitig der Menge seiner ausgegebenen Vorhersagen einen Zuverlässigkeits-Index zu. Da der Reconciled Tree quadratisch in der Größe des Genbaumes ist, entwickelten wir eine neue graphische Darstellung, um die Analyse durch den Biologen zu vereinfachen. Im Wesentlichen ist diese graphische Darstellung der Genbaum, welcher nur auf die für den Biologen interessanten Genduplikationen abgestimmt ist. Durch diese natürliche Reduktion der Darstellung können wir im allgemeinen die quadratische Explosion vermeiden. Bis jetzt ist diese Arbeit theoretischer Natur, die Umwandlung in die Anwendung hat jedoch begonnen.
  Abstract: Evolution proceeds via gene duplication and modification; it is through their successive application that nature has created the vast diversity of current genes. When a gene encoding an essential function is duplicated, one copy must preserve the function for its organism. The other, however, is free to be modified, using its ancestral gene as its starting point. Knowing precisely when ancestral gene duplications occurred is indispensable for reconstructing reliable phylogenetic relationships which in turn allows us to refine the prediction of a genetic function. For some gene families, such as globines or rhodopsines, ancestral gene duplications are well predicted, but in general they are unknown. Mapping out this unknown territory is an important open issue in molecular biology today. Recognizing this, we designed an algorithm that extends a successful but in- formal model built by biologists. This algorithm predicts gene duplications by exploiting inconsistencies in two phylogenetic trees, a gene tree and a species tree. The gene tree represents the phylogeny of a set of current genes, while the species tree represents the phylogeny of the current genes organized by their host-species. As output the algorithm calculates the gene tree reconciled with its predicted gene duplications, which is called a reconciled tree. For all applications that are possible in practice, this algorithm runs in linear time in the size of the given gene tree. This time complexity allows us to screen the today's fast growing molecular databases for gene duplications. First, we partition a genetic database into gene-families and reconstruct a gene tree for each family by one of the well established and fast reconstruction algorithms. For each gene tree, we then find its species tree in a morphologic database. Finally we predict the gene duplications for every gene and species tree pair. Thus, we are able to predict hidden gene duplications throughout the genetic database. While our algorithm predicts gene duplications, it simultaneously associates a reliability index with the set of predictions it has output. Since the reconciled tree is quadratic in the size of the gene tree, we developed a new graphical representation to ease its analysis by biologists. In essence, this graphical representation is the gene tree reconciled only at those gene duplications that are of interest for the biologist. Through this logical compression in presentation, we can, in general, avoid the quadratic explosion. Up to now, this work is of theoretical nature, but its transformation into applications for biologists has begun.
  
  
  Volltext

• Heckmann, Ralf: Nesting - Berechnung oberer und unterer Schranken. Sankt Augustin : GMD, 1998 (GMD research series; 98, 6). Zugl.: Bonn, Univ., Diss., 1998 Schlagwörter: Dissertation Institutsveröffentlichung: SCAI
  Abstract: Wir präsentieren Algorithmen zur Berechnung oberer und unterer Schranken für zweidimensionale Anordnungsprobleme (bezeichnet als Nesting-Probleme). Beim Nesting-Problem ist eine Menge irregulär geformter planarer Objekte (bezeichnet als Schablonen) auf einer Unterlage zu plazieren, die als begrenzte oder unbegrenzte planare Region gegeben sein kann. Eine Plazierung der Schablonen auf der Unterlage wird als Schnittbild bezeichnet. Ziel ist die Minimierung des Verschnitts in dem zu erstellenden Schnittbild. Je nach industrieller Anwendung sind unterschiedliche Nebenbedingungen zu berücksichtigen. In dieser Arbeit untersuchen wir Nesting-Probleme unter den speziellen Randbedingungen, die in der textilverarbeitenden Industrie auftreten. In der gegenwärtigen industriellen Praxis werden Schnittbilder manuell durch hochqualifiziertes Personal erstellt. Wir entwickeln Verfahren, die vollautomatisch ohne jegliche Unterstützung von Experten Schnittbilder erstellen und die enge Garantien für die Qualität dieser Schnittbilder geben. Für die Berechnung oberer Schranken benutzen wir randomisierte, heuristische Greedy-Verfahren, die auf dem Konzept von Hodographen beruhen, datenbankgestützte Verfahren, die geometrische Mustererkennungsmethoden einsetzen, und globale Optimierung basierend auf Varianten von Simulated Annealing. Die Berechnung unterer Schranken erfolgt durch ein Branch-And-Bound Verfahren. Dieses Verfahren benutzt eine diskrete Beschreibung des Anordnungsraums, der die Menge legaler Plazierungspositionen der Schablonen relativ zueinander beschreibt, für eine hierarchische Suche basierend auf einer fortlaufenden Verfeinerung von Hodographen. Wir berechnen die unteren Schranken für Teilprobleme, die einen Schluß auf untere Schranken für das Gesamtproblem zulassen. Wir testen unsere Methoden auf einer großen Menge von Datensätzen, die wir aus der textilverarbeitenden Industrie erhalten haben. Gute obere Schranken für diese Datensätze können wir auf einem heute üblichen Arbeitsplatzrechner in weniger als einer Stunde berechnen. Die Auslastungen sind zu den von einem Experten erzielten Auslastungen konkurrenzfähig. Untere Schranken werden innerhalb weniger Stunden berechnet und sind nur wenige Prozentpunkte von den besten bekannten oberen Schranken entfernt (z.B. 0.4% bei Hosen).
  Abstract: We present lower and upper bound algorithms for two-dimensional arrangement problems (called nesting problems). In a nesting problem, a set of irregularly shaped planar objects called stencils has to be placed onto a surface which can be a bounded or unbounded planar region. A placement of the stencils on the surface is called cutting image or marker. The goal is to minimize the waste of a marker. Diverse constraints coming from the different fields of industrial application have to be considered. In this study, we examine nesting problems under the special constraints given in the textile manufacturing industry. Today's industrial practice is characterized by interactive placement systems which are used by highly skilled personnel. We develop algorithms which solve the task of generating cutting images fully automatically and which can give tight performance guarantees on the quality of these markers. For the calculation of upper bounds we use greedy strategies based on hodographs which apply randomized heuristic rules for generating legal arrangements of the stencils, a database approach which uses geometric pattern matching methods, and global optimization based on variants of simulated annealing. For the lower bounds we use branch-and-bound methods which work on discrete representations of the configuration space describing the set of legal placement positions of the stencils relative to each other. We calculate our lower bounds on placement subproblems that determine the performance of the overall problem. We validate our methods on a large amount of data sets taken from the textile manufacturing industry. The upper bounds are computed in less than an hour on a common-day workstation and are competitive in quality with results obtained by human nesters. The lower bounds take a few hours to compute and are within a few percentage points of the best known upper bounds (e.g., 0.4% for pants).

• Schwikowski, Benno: A new algorithmic approach to the construction of multiple alignments and evolutionary trees. Sankt Augustin : GMD, 1998 (GMD research series; 98, 14). Zugl.: Bonn, Univ.,Diss., 1998 Schlagwörter: Computational Molecular Biology; algorithms; multiple alignment; evolutionary tree; ohylogenetic tree; Generalized tree alignment problem; Dissertation Institutsveröffentlichung: SCAI
  Abstract: Betrachtet man die Evolution biologischer Sequenzen, konzentriert man sich häufig auf einen von zwei Aspekten: deren multiples Alignment, das die Buchstaben verschiedener Sequenzen miteinander in Beziehung setzt, oder den evolutionären Baum, der die Abstammungsgeschichte der vollständigen Sequenzen beschreibt. In der Praxis müssen Alignment und Baum meist beide aus den Sequenzen selbst rekonstruiert werden, und beide Aspekte sind eng miteinander korreliert. Deshalb bietet sich die gleichzeitige Berechnung von Alignment und Baum an. Das entsprechende Optimierungsproblem stellt allerdings in theoretischer und in praktischer Hinsicht ein schwieriges Problem dar. Mit dieser Arbeit wird der erste Ansatz vorgestellt, multiple Alignments und evolutionäre Bäume gleichzeitig und für reale Probleminstanzen zu lösen. Er ist motiviert durch eine Analogie zum Steiner-Problem aus der Informatik einerseits, und den in der praktischen Bioinformatik erfolgreichen iterativen Alignmentverfahren andererseits. Dabei vermeidet die neue Datenstruktur des gewichteten Sequenzgraphen typische Nachteile iterativer Alignmentverfahren. Neben dem Verfahren selbst werden auch die im Zuge dieser Arbeit entstandene Implementierung, sowie Experimente auf simulierten und realen Daten besprochen.
  Abstract: In understanding the evolution of biological sequences, it is common practice to focus at one of two aspects: either the multiple alignment of the characters that relates the individual characters of the sequences, or the evolutionary tree that describes the evolutionary history of the complete sequences. Usually, alignment and tree must both be reconstructed from the sequences alone, and both aspects are closely interrelated. It is therefore desirable to simultaneously reconstruct alignment and tree from the given sequences. However, this represents a difficult task in theory and in practice. This study presents the first approach to the simultaneous reconstruction of multiple alignments and evolutionary trees for real data. It is motivated by an analogy to the Steiner problem from computer science and to iterative alignment algorithms, which are successful in practical bioinformatics. The data structure of the weighed sequence graph avoids typical disadvantages of previous iterative algorithms. Besides the new algorithm, we describe implementation and experimental results on simulated and real biological data. Volltext

• Umlauf, Guenther: Numerische Simulation der dreidimensionalen thermodiffusiven-sedimentaeren Konvektion mit einem parallelen Mehrgitteralgorithmus. 1998 Bonn, Universität, Diss., 1998 Schlagwörter: Dissertation Institutsveröffentlichung: SCAI: Abteilung: WR