Contributions to exact approaches in combinatorial optimization

The focus of this thesis is to contribute to the development of new, exact solution approaches to different combinatorial optimization problems. In particular, we derive dedicated algorithms for a special class of Traveling Tournament Problems (TTPs), the Dial-A-Ride Problem (DARP), and the Vehicle Routing Problem with Time Windows and Temporal Synchronized Pickup and Delivery (VRPTWTSPD). Furthermore, we extend the concept of using dual-optimal inequalities for stabilized Column Generation (CG) and detail its application to improved CG algorithms for the cutting stock problem, the bin packing problem, the vertex coloring problem, and the bin packing problem with conflicts. In all approaches, we make use of some knowledge about the structure of the problem at hand to individualize and enhance existing algorithms. Specifically, we utilize knowledge about the input data (TTP), problem-specific constraints (DARP and VRPTWTSPD), and the dual solution space (stabilized CG). Extensive computational results proving the usefulness of the proposed methods are reported.

Rylenfarbstoffe in nanoskopischen Systemen

ZusammenfassungDurch die Funktionalisierung des Chromophors Tetraphenoxyperylendiimid mit vier Ethinylgruppen stand ein Farbstoff zur Verfügung, welcher sich als Kernmolekül für den Aufbau von Polyphenylendendrimeren eignet. Ausgehend von dem Farbstoffkern wurden drei Dendrimergenerationen synthetisiert. Durch die Dendronisierung wird die Aggregation des zentralen Farbstoffs im Festkörper verhindert, weshalb das G1-Dendrimer als aktive Schicht in LED´s eingesetzt wurde und zur Verbesserung dieser Bauelemente führte. Weiterhin wurde auch die Oberfläche der Polyphenylendendrimere mit 4, 8 bzw. 16 Perylenmonoimidfarbstoffen funktionalisiert. Durch zeitaufgelöste Absorptions- und Emissionsmessungen und Einzelmolekülspektroskopie des G2-Dendrimers wurde ein photophysikalisches Modell des multichromophoren Systems entwickelt.Neben Polyphenylendendrimeren dienten auch Emulsionspolymerisate, Miniemulsionspolymerisate und Halbleiterkristalle als nanoskopische Trägermaterialien für Rylenfarbstoffe. Für die Anknüpfung an Lartices wurden amino- und styrylfunktionalisierte Perylen- und Terrylenchromophore dargestellt, was zu einer statistischen Verteilung der Farbstoffe auf der Oberfläche bzw. im Inneren führte. Außerdem wurden Rylenfarbstoffe als stabile Fluoreszenzmarkierung von Metallocenkatalysatoren eingesetzt. Silica- und polymergeträgerte markierte Katalysatoren wurden zur Polymerisation von Ethylen verwendet und lieferten fluoreszente PE-Produkte, ohne Einfluß auf die Polymerisation zu nehmen. Zum Einen wurde mit Hilfe der Dotierung der heterogenen Polymerisationskatalysatoren der Verbleib des fragmentierten Trägermaterials in den PE-Produktpartikeln detektiert. Zum Anderen erlaubt der Einsatz unterschiedlich fluoreszierender Markierungsgruppen die Durchführung eines kombinatorischen Verfahrens zum Testen von Polymerisationskatalysatoren.

Chemische und enzymatische Synthese von orthogonal stabil geschützten Kohlenhydrat-Scaffolds für kombinatorische Anwendungen

Auf der Suche nach potenten pharmakologischen Wirkstoffen hat die Kombinatorische Chemie in der letzten Dekade eine große Bedeutung erlangt, um innerhalb kurzer Zeit ein breites Spektrum von Verbindungen für biologische Tests zu erzeugen. Kohlenhydrate stellen als Scaffolds interessante Kandidaten für die kombinatorische Synthese dar, da sie mehrere Derivatisierungspositionen in stereochemisch definierter Art und Weise zur Verfügung stellen. So ist die räumlich eindeutige Präsentation angebundener pharmakophorer Gruppen möglich, wie es für den Einsatz als Peptidmimetika wünschenswert ist. Zur gezielten Derivatisierung einzelner Hydroxylfunktionen ist der Einsatz eines orthogonalen Schutz-gruppenmusters erforderlich, das gegenüber den im Lauf der kombinatorischen Synthese herrschenden Reaktionsbedingungen hinreichend stabil ist. Weiterhin ist ein geeignetes Ankersystem zu finden, um eine Festphasensynthese und damit eine Automatisierung zu ermöglichen.Zur Minimierung der im Fall von Hexosen wie Galactose benötigten fünf zueinander orthogonal stabilen Schutzgruppen wurde bei der vorliegenden Arbeit von Galactal ausgegangen, bei dem nur noch drei Hydroxylfunktionen zu differenzieren sind. Das Galactose-Gerüst kann anschließend wiederhergestellt werden. Die Differenzierung wurde über den Einsatz von Hydrolasen durch regioselektive Acylierungs- und Deacylierungs-reaktionen erreicht, wobei auch immobilisierte Enzyme Verwendung fanden. Dabei konnte ein orthogonales Schutzgruppenmuster sequentiell aufgebaut werden, das auch die nötigen Stabilitäten gegenüber sonstigen, teilweise geeignet modifizierten Reaktionsbedingungen aufweist. Für die Anbindung an eine Festphase wurde ein metathetisch spaltbarer Anker entwickelt, der über die anomere Position unter Wiederherstellung des Galactose-Gerüsts angebunden wurde. Auch ein oxidativ spaltbares und ein photolabiles Ankersystem wurden erprobt.

Gleichmäßig dünne Basen zweiter Ordnung

Eine Menge B nicht negativer ganzer Zahlen heißt Basis h-ter Ordnung, wenn jede nicht negative ganze Zahl Summe von höchstens h Elementen von B ist. Eine der großen Fragen der additiven Zahlentheorie ist die nach der effektivsten Basis h-ter Ordnung für ein gegebenes h>=2. Im Fokus des Interesses steht dabei der immer noch offene Fall h=2. Bezeichnet B(x) die Anzahl der Elemente b aus B mit 0= af(x), wobei f die Wurzelfunktion bezeichne. Andererseits gibt es Basen B zweiter Ordnung mit B(x) <= cf(x). Daher kann man den Limes superior S(B), den Limes inferior s(B) sowie im Falle der Existenz den Limes d(B) des Quotienten B(x) / f(x) als Dichtefunktionen von Basen zweiter Ordnung betrachten. J. W. S. Cassels konstruierte 1957 eine Basis C zweiter Ordnung mit d(C)=5,196…. G. Hofmeister gab 2001 eine Basis H zweiter Ordnung mit asymptotischer Wurzeldichte d(H)=4,638… an. In der vorliegenden Arbeit wird eine Basis S zweiter Ordnung mit asymptotischer Wurzeldichte d(S)=3,464… konstruiert. Darüber hinaus wird für die von J. W. S. Cassels, für die von G. Hofmeister und für die in dieser Arbeit verwendete Klasse von Basen zweiter Ordnung gezeigt, dass die asymptotische Wurzeldichte innerhalb der jeweiligen Klasse nicht mehr zu verbessern ist. Bisher war die Frage nach möglichen Verbesserungen innerhalb der jeweiligen Konstruktionsprinzipien offen geblieben.

Selektiv deblockierbare 2,6-Diamino-2,6-didesoxy-D-glucose-Scaffolds für die kombinatorische Synthese potentieller RNA-Liganden

Aminoglydosid-Antibiotika wie Neomycin B oder Cyclopeptid-Antibiotike wie Viaomycin sind dafür bekannt, daß sie selektiv an RNA binden können. Diese Interaktionen beruhen sowohl auf elektrostatischen Wechselwirkungen als auch auf H-Brücken-Bindungen. Des weiteren ist die definierte räumliche Anordnung von Donor- und Akzeptor-Resten in den Strukturen der RNA-Liganden wichtig für die Affinität. Eine Möglichkeit natürliche RNA-Liganden zu imitieren ist der Einsatz polyfunktioneller Template wie zum Beispiel das 2,6-Diamino-2,6-didesoxy-D-glucose-Scaffold. Mit Hilfe dieser Scaffolds können dann verschiedene positv geladene Reste und Donatoren sowie Akzeptoren für H-Brücken-Bindungen oder auch Interkalatoren räumlich definiert präsentiert werden. Für die unabhängige Funktionalisierung einer jeden Position ist ein Satz orthogonal stabiler Schutzgruppen nötig, wobei eine Hydroxylguppe durch einen Anker ersetzt wird, der eine Anbindung des Scaffolds an einen polymeren Träger ermöglicht. Das neu entwickelte 2,6-Diamino-2,6-didesoxy-D-glucose-Scaffold ist das erste Monosaccharid-Templat, das in allen fünf Positionen mit orthogonal stabilen Schutzgruppen blockiert ist. Alle Positionen könne in beliebiger Reihenfolge selektiv deblockiert und anschließend derivatisiert werden. Das Scaffold kann mit Aminosäuren, Guanidinen oder Interkalatoren umgesetzt werden, um so natürlich vorkommende RNA-bindende Aminoglycoside oder Peptide zu imitieren. Aufbauend auf diesem Monosaccharid-Templat wurde eine Bibliothek von über 100 potentiellen RNA-Liganden synthetisiert, die im Rahmen des Sonderforschungsbereichs 579 (RNA-Liganden-Wechselwirkungen) in Zellassays auf ihre Fähigkeit zur Hemmung der Tat/TAR-Wechselwirkung untersucht wurden, wobei bis jetzt 9 Verbindungen mit einer hemmenden Wirkung im micromolaren Bereich gefunden wurden.

Determination of the gluon polarisation from open charm production at COMPASS

One of the main goals of the COMPASS experiment at CERN is the determination of the gluon polarisation in the nucleon. It is determined from spin asymmetries in the scattering of 160 GeV/c polarised muons on a polarised LiD target. The gluon polarisation is accessed by the selection of photon-gluon fusion (PGF) events. The PGF-process can be tagged through hadrons with high transverse momenta or through charmed hadrons in the final state. The advantage of the open charm channel is that, in leading order, the PGF-process is the only process for charm production, thus no physical background contributes to the selected data sample. This thesis presents a measurement of the gluon polarisation from the COMPASS data taken in the years 2002-2004. In the analysis, charm production is tagged through a reconstructed D0-meson decaying in $D^{0}-> K^{-}pi^{+}$ (and charge conjugates). The reconstruction is done on a combinatorial basis. The background of wrong track pairs is reduced using kinematic cuts to the reconstructed D0-candidate and the information on particle identification from the Ring Imaging Cerenkov counter. In addition, the event sample is separated into D0-candidates, where a soft pion from the decay of the D*-meson to a D0-meson, is found, and the D0-candidates without this tag. Due to the small mass difference between D*-meson and D0-meson the signal purity of the D*-tagged sample is about 7 times higher than in the untagged sample. The gluon polarisation is measured from the event asymmetries for the for the different spin configurations of the COMPASS target. To improve the statistical precision of the final results, the events in the final sample are weighted. This method results in an average value of the gluon polarisation in the x-range covered by the data. For the COMPASS data from 2002-2004, the resulting value of the gluon polarisation is $=-0.47+-0.44 (stat)+-0.15(syst.)$. The result is statistically compatible with the existing measurements of $$ in the high-pT channel. Compared to these, the open charm measurement has the advantage of a considerably smaller model dependence.

Mathematical aspects of Feynman integrals

In the present dissertation we consider Feynman integrals in the framework of dimensional regularization. As all such integrals can be expressed in terms of scalar integrals, we focus on this latter kind of integrals in their Feynman parametric representation and study their mathematical properties, partially applying graph theory, algebraic geometry and number theory. The three main topics are the graph theoretic properties of the Symanzik polynomials, the termination of the sector decomposition algorithm of Binoth and Heinrich and the arithmetic nature of the Laurent coefficients of Feynman integrals.rnrnThe integrand of an arbitrary dimensionally regularised, scalar Feynman integral can be expressed in terms of the two well-known Symanzik polynomials. We give a detailed review on the graph theoretic properties of these polynomials. Due to the matrix-tree-theorem the first of these polynomials can be constructed from the determinant of a minor of the generic Laplacian matrix of a graph. By use of a generalization of this theorem, the all-minors-matrix-tree theorem, we derive a new relation which furthermore relates the second Symanzik polynomial to the Laplacian matrix of a graph.rnrnStarting from the Feynman parametric parameterization, the sector decomposition algorithm of Binoth and Heinrich serves for the numerical evaluation of the Laurent coefficients of an arbitrary Feynman integral in the Euclidean momentum region. This widely used algorithm contains an iterated step, consisting of an appropriate decomposition of the domain of integration and the deformation of the resulting pieces. This procedure leads to a disentanglement of the overlapping singularities of the integral. By giving a counter-example we exhibit the problem, that this iterative step of the algorithm does not terminate for every possible case. We solve this problem by presenting an appropriate extension of the algorithm, which is guaranteed to terminate. This is achieved by mapping the iterative step to an abstract combinatorial problem, known as Hironaka's polyhedra game. We present a publicly available implementation of the improved algorithm. Furthermore we explain the relationship of the sector decomposition method with the resolution of singularities of a variety, given by a sequence of blow-ups, in algebraic geometry.rnrnMotivated by the connection between Feynman integrals and topics of algebraic geometry we consider the set of periods as defined by Kontsevich and Zagier. This special set of numbers contains the set of multiple zeta values and certain values of polylogarithms, which in turn are known to be present in results for Laurent coefficients of certain dimensionally regularized Feynman integrals. By use of the extended sector decomposition algorithm we prove a theorem which implies, that the Laurent coefficients of an arbitrary Feynman integral are periods if the masses and kinematical invariants take values in the Euclidean momentum region. The statement is formulated for an even more general class of integrals, allowing for an arbitrary number of polynomials in the integrand.

Funktionelle Analyse der Gliazellwanderung im Drosophila-Embryo

Gliazellen kommen in allen höheren Organismen vor und sind sowohl für die korrekte Entwicklung, als auch für die Funktionalität des adulten Nervensystems unerlässlich. Eine der mannigfachen Funktionen dieses Zelltyps ist die Umhüllung von Axonen im zentralen und peripheren Nervensystem (ZNS und PNS). Um eine vollständige Umhüllung zu gewährleisten, wandern Gliazellen während der Neurogenese zum Teil über enorme Distanzen von ihrem Entstehungsort aus. Dies trifft insbesondere auf die Gliazellen zu, durch deren Membranausläufer die distalen Axonbereiche der peripheren Nerven isoliert werden.rnIn dieser Arbeit wurde die Migration von Gliazellen anhand des Modelorganismus Drosophila untersucht. Ein besonderes Interesse galt dabei der Wanderung einer distinkten Population von Gliazellen, den sogenannten embryonalen Peripheren Gliazellen (ePG). Die ePGs werden überwiegend im sich entwickelnden ventralen Bauchmark geboren und wandern anschließend entlang der peripheren Nerventrakte nach dorsal aus, um diese bis zum Ende der Embryogenese zu umhüllen und dadurch die gliale Blut-Nerv-Schranke zu etablieren. Das Hauptziel dieser Arbeit bestand darin, neue Faktoren bzw. Mechanismen aufzudecken, durch welche die Migration der ePGs reguliert wird. Dazu wurde zunächst der wildtypische Verlauf ihrer Wanderung detailliert analysiert. Es stellte sich heraus, dass in jedem abdominalen Hemisegment eine invariante Anzahl von 12 ePGs von distinkten neuralen Vorläuferzellen generiert wird, die individuelle Identitäten besitzen und mittels molekularer Marker auf Einzelzellebene identifiziert werden können. Basierend auf der charakteristischen Lage der Zellen erfolgte die Etablierung einer neuen, konsistenten Nomenklatur für sämtliche ePGs. Darüber hinaus offenbarten in vivo Migrationsanalysen, dass die Wanderung individueller ePGs stereotyp verläuft und demzufolge weitestgehend prädeterminiert ist. Die genaue Kenntnis der wildtypischen ePG Migration auf Einzelzellebene diente anschließend als Grundlage für detaillierte Mutantenanalysen. Anhand derer konnte für den ebenfalls als molekularen Marker verwendeten Transkriptionsfaktor Castor eine Funktion als zellspezifische Determinante für die korrekte Spezifizierung der ePG6 und ePG8 nachgewiesen werden, dessen Verlust in einem signifikanten Migrationsdefekt dieser beiden ePGs resultiert. Des Weiteren konnte mit Netrin (NetB) der erste diffusible und richtungsweisende Faktor für die Migration von ePGs enthüllt werden, der in Interaktion mit dem Rezeptor Uncoordinated5 speziell die Wanderung der ePG6 und ePG8 leitet. Die von den übrigen Gliazellen unabhängige Navigation der ePG6 und ePG8 belegt, dass zumindest die Migration von Gruppen der ePGs durch unterschiedliche Mechanismen kontrolliert wird, was durch die Resultate der durchgeführten Ablationsexperimente bestätigt wird. rnFerner konnte gezeigt werden, dass während der frühen Gliogenese eine zuvor unbekannte, von Neuroblasten bereitgestellte Netrinquelle an der initialen Wegfindung der Longitudinalen Gliazellen (eine Population Neuropil-assoziierter Gliazellen im ZNS) beteiligt ist. In diesem Kontext erfolgt die Signaldetektion bereits in deren Vorläuferzelle, dem Longitudinalen Glioblasten, zellautonom über den Rezeptor Frazzled. rnFür künftige Mutantenscreens zur Identifizierung weiterer an der Migration der ePGs beteiligter Faktoren stellt die in dieser Arbeit präsentierte detaillierte Beschreibung eine wichtige Grundlage dar. Speziell in Kombination mit den vorgestellten molekularen Markern liefert sie die Voraussetzung dafür, individuelle ePGs auch im mutanten Hintergrund zu erfassen, wodurch selbst subtile Phänotypen überhaupt erst detektiert und auf Einzelzellebene analysiert werden können. Aufgrund der aufgezeigten voneinander unabhängigen Wegfindung, erscheinen Mutantenanalysen ohne derartige Möglichkeiten wenig erfolgversprechend, da Mutationen vermutlich mehrheitlich die Migration einzelner oder weniger ePGs beeinträchtigen. Letzten Endes wird somit die Aussicht verbessert, weitere neuartige Migrationsfaktoren im Modellorganismus Drosophila zu entschlüsseln, die gegebenenfalls bis hin zu höheren Organismen konserviert sind und folglich zum Verständnis der Gliazellwanderung in Vertebraten beitragen.

Bioinformatische Identifizierung und Charakterisierung von Zyklin-abhängigen Kinasen und Zyklinen des Parasiten Eimeria tenella und deren Nutzung im rationalen Wirkstoffdesign

Parasiten der Apicomplexa umfassen sowohl humanpathogene, als auch tierpathogene Protozoen. Beispiele für wichtige Vertreter human- und tierpathogener Parasiten sind Plasmodium falciparum und Eimeria tenella. E. tenella verursacht die Kokzidiose des Hühnchens, eine Darmerkrankung die weltweit für Verluste in einer geschätzten Höhe von bis zu 3 Milliarden US$ verantwortlich zeichnet. Eine prophylaktische Vakzinierung gegen diese Krankheit ist ökonomisch meist ineffizient, und eine Behandlung mit Kokzidiostatika wird durch häufige Resistenzbildung gegen bekannte Wirkstoffe erschwert. Diese Situation erfordert die Entwicklung neuer kostengünstiger Alternativen. Geeignete Zielproteine für die Entwicklung neuartiger Arzneistoffe zur Behandlung der Kokzidiose sind die Zyklin-abhängigen Kinasen (CDKs), zu denen auch die CDK-related Kinase 2 (EtCRK2) aus E. tenella gehört. Diese Proteine sind maßgeblich an der Regulation des Zellzyklus beteiligt. Durch chemische Validierung mit dem CDK Inhibitor Flavopiridol konnte nachgewiesen werden, dass ein Funktionsverlust von CDKs in E. tenella die Vermehrung des Parasiten in Zellkultur inhibiert. E. tenella CDKs sind daher als Zielproteine für die Entwicklung einer Chemotherapie der Kokzidiose geeignet. Mittels bioinformatischer Tiefenanalysen sollten CDK Proteine im Parasiten E. tenella identifiziert werden. Das Genom von E. tenella liegt in Rohfassung vor [ftp://ftp.sanger.ac.uk]. Jedoch waren zum Zeitpunkt dieser Arbeiten viele Sequenzen des Genoms noch nicht annotiert. Homologe CDK Proteine von E. tenella konnten durch den Vergleich von Sequenzinformationen mit anderen Organismen der Apicomplexa identifiziert und analysiert werden. Durch diese Analysen konnten neben der bereits bekannten EtCRK2, drei weitere, bislang nicht annotierte CDKs in E. tenella identifiziert werden (EtCRK1, EtCRK3 sowie EtMRK). Darüber hinaus wurde eine Analyse der entsprechenden Zykline – der Aktivatoren der CDKs – bezüglich Funktion und Struktur, sowie eine Datenbanksuche nach bisher nicht beschriebenen Zyklinen in E. tenella durchgeführt. Diese Suchen ergaben vier neue potentielle Zykline für E. tenella, wovon EtCYC3a als Aktivator der EtCRK2 von María L. Suárez Fernández (Intervet Innovation GmbH, Schwabenheim) bestätigt werden konnte. Sequenzvergleiche lassen vermuten, dass auch EtCYC1 und EtCYC3b in der Lage sind, EtCRK2 zu aktivieren. Außerdem ist anzunehmen, dass EtCYC4 als Aktivator der EtCRK1 fungiert. Ein weiterer Schwerpunkt der vorliegenden Arbeit war die Suche und Optimierung nach neuen Inhibitoren von CDKs aus E. tenella. In vorangegangenen Arbeiten konnten bereits Inhibitoren der EtCRK2 gefunden werden [BEYER, 2007]. Mittels Substruktur- und Ähnlichkeitssuchen konnten im Rahmen dieser Arbeit weitere Inhibitoren der EtCRK2 identifiziert werden. Vier dieser Strukturklassen erfüllen die Kriterien einer Leitstruktur. Eine dieser Leitstrukturen gehört zur Strukturklasse der Benzimidazol-Carbonitrile und ist bislang nicht als Inhibitor anderer Kinasen beschrieben. Diese neu identifizierte Leitstruktur konnte in silico weiter optimiert werden. Im Rahmen dieser Arbeit wurden Bindungsenergien von Vertretern dieser Strukturklasse berechnet, um einen wahrscheinlichen Bindemodus vorherzusagen. Für die weiterführende in silico Optimierung wurde eine virtuelle kombinatorische Substanzbibliothek dieser Klasse erstellt. Die Auswahl geeigneter Verbindungen für eine chemische Synthese erfolgte durch molekulares Docking unter Nutzung von Homologiemodellen der EtCRK2. Darüber hinaus wurde ein in silico Screening nach potentiellen Inhibitoren der PfMRK und EtMRK durchgeführt. Dabei konnten weitere interessante virtuelle Hit-Strukturen aus einer Substanzdatenbank kommerziell erhältlicher Verbindungen gefunden werden. Durch dieses virtuelle Screening konnten jeweils sieben Verbindungen als virtuelle Hits der PfMRK sowie der EtMRK identifiziert werden. Die Häufung von Strukturklassen mit bekannter CDK Aktivität deutet darauf hin, dass während des virtuellen Screenings eine Anreicherung von CDK Inhibitoren stattgefunden hat. Diese Ergebnisse lassen auf eine Weiterentwicklung neuer Wirkstoffe gegen Kokzidiose und Malaria hoffen.

On the car sequencing problem: analysis and solution methods

This work deals with the car sequencing (CS) problem, a combinatorial optimization problem for sequencing mixed-model assembly lines. The aim is to find a production sequence for different variants of a common base product, such that work overload of the respective line operators is avoided or minimized. The variants are distinguished by certain options (e.g., sun roof yes/no) and, therefore, require different processing times at the stations of the line. CS introduces a so-called sequencing rule H:N for each option, which restricts the occurrence of this option to at most H in any N consecutive variants. It seeks for a sequence that leads to no or a minimum number of sequencing rule violations. In this work, CS’ suitability for workload-oriented sequencing is analyzed. Therefore, its solution quality is compared in experiments to the related mixed-model sequencing problem. A new sequencing rule generation approach as well as a new lower bound for the problem are presented. Different exact and heuristic solution methods for CS are developed and their efficiency is shown in experiments. Furthermore, CS is adjusted and applied to a resequencing problem with pull-off tables.

Problem-specific design of metaheuristics for constrained spanning tree problems

When designing metaheuristic optimization methods, there is a trade-off between application range and effectiveness. For large real-world instances of combinatorial optimization problems out-of-the-box metaheuristics often fail, and optimization methods need to be adapted to the problem at hand. Knowledge about the structure of high-quality solutions can be exploited by introducing a so called bias into one of the components of the metaheuristic used. These problem-specific adaptations allow to increase search performance. This thesis analyzes the characteristics of high-quality solutions for three constrained spanning tree problems: the optimal communication spanning tree problem, the quadratic minimum spanning tree problem and the bounded diameter minimum spanning tree problem. Several relevant tree properties, that should be explored when analyzing a constrained spanning tree problem, are identified. Based on the gained insights on the structure of high-quality solutions, efficient and robust solution approaches are designed for each of the three problems. Experimental studies analyze the performance of the developed approaches compared to the current state-of-the-art.

Segmentale Musterbildung in der terminalen Abdominalregion des zentralen Nervensystems von Drosophila melanogaster

In dieser Arbeit wurden Mechanismen der Musterbildung in der terminalen Abdominalregion des Zentralnervensystems von Drosophila melanogaster untersucht. Dazu wurden zunächst die Anzahl der angelegten Neuromere und das Muster der dort lokalisierten neuralen Stammzellen (Neuroblasten) analysiert. Dabei zeigte sich, dass sowohl die Größe der Neuromere, als auch die Anzahl an Neuroblasten von anterior nach posterior sukzessiv abnimmt, wobei keine geschlechtsspezifischen Unterschiede in der Anzahl der vorhandenen Neuroblasten festgestellt werden konnten. Durch die Kombination einer Vielzahl von molekularen Markern war es anschließend möglich, die Identität aller Neuroblasten in diesem Bereich aufzuklären und in einer Karte zusammenzutragen. Sie weisen alle eine serielle Homologie zu Neuroblasten in weiter anterior gelegenen Segmenten auf. Des Weiteren wurde die embryonale Identität der geschlechtsspezifischen Neuroblasten untersucht und deren postembryonalen mänchenspezifischen Zellstammbäume charakterisiert. Diese detaillierten Beschreibungen bildeten die Grundlage für die funktionelle Analyse von geschlechts- und segmentspezifischen Faktoren, die zur Musterbildung in dieser Region des Zentralnervensystems beitragen. So konnte gezeigt werden, dass die weibliche Isoform von doublesex den programmierten Zelltod der geschlechtsspezifischen Neuroblasten induziert, während die männliche Isoform diesen verhindert. Das Hox-Gen Abdominal-B zeigt relativ milde Effekte auf das Überleben dieser Neuroblasten, was darauf hindeutet, dass weitere Faktoren benötigt werden, um diesen Prozess in segmentspezifischer Weise zu kontrollieren. Die Funktion von Hox-Genen wurde ferner im Hinblick auf die abgeleitete Morphologie der terminalen Neuromere untersucht. Es konnte herausgefunden werden, dass die regulatorische Isoform von Abdominal-B auf mehreren Ebenen wirkt: Sie beeinflusst die Zusammensetzung bestimmter Zellstammbäume durch Modifikation von Zelldeterminationsprozessen und durch die Kontrolle des programmierten Zelltods. Außerdem unterdrückt sie die Bildung einer spezifischen Subpopulation von Neuroblasten. Allerdings benötigt Abdominal-B.r die Co-Expression des ParaHox-Gens caudal, um sein gesamtes Potenzial bezüglich der Suppression dieser Neuroblasten zu entfalten. Die vorliegende Arbeit hat somit erste Einblicke in die geschlechtsspezifische und segmentspezifische Spezifizierung der terminalen Abdominalregion des Zentralnervensystems von Drosophila auf Ebene des Neuroektoderms, der daraus hervorgehenden Neuroblasten und deren Tochterzellen gewährt. Die vollständige und detailgetreue Beschreibung des Neuroblasten-Musters und der postembryonalen männchenspezifischen Zellstammbäume hat zudem attraktive Modellsysteme für zukünftige Untersuchungen etabliert, an denen sich weitere Mechanismen der Musterbildung im Zentralnervensystem analysieren lassen.

Hydrogels for DNA isolation from blood

This dissertation describes the synthesis of surface attached hydrogel biomaterials, characterization of their properties, evaluation of structuring concepts and the investigation of these materials in the isolation of DNA from human whole blood. Photosensitive hydrogel precursor materials on the basis of hydroxyethylmethacrylate (HEMA) were synthesized by free radical polymerization. In order to obtain surface bound hydrogel films, the precursors were deposited on a suitable substrate and subsequently irradatiated with UV - light to accomplish the formation of crosslinks in the film and create surface attachment. The composition of the polymerization precursor materials was determined by comprehensive NMR and GPC studies, revealing the copolymerizationrnbehaviour of the used monomers - HEMA derivatives and the photocrosslinkerrnMABP - and their respective distribution in the hydrogel precursors. The degree of crosslinking of the hydrogels was characterized with UV/vis spectroscopy. Stress-strain measurements were conducted in order to investigate the mechanical properties of the biomaterials. Moreover, the swelling process and biomolecule adsorption properties of the hydrogels were investigated with SPR/OW spectroscopy. For this, the deposition and binding of the hydrogels on gold or SiO2 surfaces was facilitated with photocrosslinkable adhesion promotors. The produced hydrogels were mechanically rigid and stablernunder the conditions of PCR and blood lysis. Furthermore, strategies towards the increase of hydrogel surface structure and porosity with porosigens, 2D laser interference lithography and photocleavable blockcopolymers were investigated. At last, a combinatorial strategy was used for the determination of the usefulness of hydrogels for the isolation from DNA from blood. A series of functionalized hydrogel precursors were synthesized, transferred to the surface inside a PCR tube and subsequently screened in regard to DNA adsorption properties with Taqman quantitative PCR. This approach yielded a promising candidate for a functional PCR tube coating that would allow the entire DNA isolation procedure being carried out in a single reaction container.rnThereforce, the practical application of such macromolecular architectures can be envisioned to improve industrial DNA diagnostic processes.

Detrimental effects of exuberant and restrained immune responses against the central nervous system in the context of multiple sclerosis and glioblastoma multiforme

Glioblastoma multiforme (GBM) is the most common and most aggressive astrocytic tumor of the central nervous system (CNS) in adults. The standard treatment consisting of surgery, followed by a combinatorial radio- and chemotherapy, is only palliative and prolongs patient median survival to 12 to 15 months. The tumor subpopulation of stem cell-like glioma-initiating cells (GICs) shows resistance against radiation as well as chemotherapy, and has been suggested to be responsible for relapses of more aggressive tumors after therapy. The efficacy of immunotherapies, which exploit the immune system to specifically recognize and eliminate malignant cells, is limited due to strong immunosuppressive activities of the GICs and the generation of a specialized protective microenvironment. The molecular mechanisms underlying the therapy resistance of GICs are largely unknown. rnThe first aim of this study was to identify immune evasion mechanisms in GICs triggered by radiation. A model was used in which patient-derived GICs were treated in vitro with fractionated ionizing radiation (2.5 Gy in 7 consecutive passages) to select for a more radio-resistant phenotype. In the model cell line 1080, this selection process resulted in increased proliferative but diminished migratory capacities in comparison to untreated control GICs. Furthermore, radio-selected GICs downregulated various proteins involved in antigen processing and presentation, resulting in decreased expression of MHC class I molecules on the cellular surface and diminished recognition potential by cytotoxic CD8+ T cells. Thus, sub-lethal fractionated radiation can promote immune evasion and hamper the success of adjuvant immunotherapy. Among several immune-associated proteins, interferon-induced transmembrane protein 3 (IFITM3) was found to be upregulated in radio-selected GICs. While high expression of IFITM3 was associated with a worse overall survival of GBM patients (TCGA database) and increased proliferation and migration of differentiated glioma cell lines, a strong contribution of IFITM3 to proliferation in vitro as well as tumor growth and invasiveness in a xenograft model could not be observed. rnMultiple sclerosis (MS) is the most common autoimmune disease of the CNS in young adults of the Western World, which leads to progressive disability in genetically susceptible individuals, possibly triggered by environmental factors. It is assumed that self-reactive, myelin-specific T helper cell 1 (Th1) and Th17 cells, which have escaped the control mechanisms of the immune system, are critical in the pathogenesis of the human disease and its animal model experimental autoimmune encephalomyelitis (EAE). It was observed that in vitro differentiated interleukin 17 (IL-17) producing Th17 cells co-expressed the Th1-phenotypic cytokine Interferon-gamma (IFN-γ) in combination with the two respective lineage-associated transcription factors RORγt and T-bet after re-isolation from the CNS of diseased mice. Pathogenic molecular mechanisms that render a CD4+ T cell encephalitogenic have scarcely been investigated up to date. rnIn the second part of the thesis, whole transcriptional changes occurring in in vitro differentiated Th17 cells in the course of EAE were analyzed. Evaluation of signaling networks revealed an overrepresentation of genes involved in communication between the innate and adaptive immune system and metabolic alterations including cholesterol biosynthesis. The transcription factors Cebpa, Fos, Klf4, Nfatc1 and Spi1, associated with thymocyte development and naïve T cells were upregulated in encephalitogenic CNS-isolated CD4+ T cells, proposing a contribution to T cell plasticity. Correlation of the murine T-cell gene expression dataset to putative MS risk genes, which were selected based on their proximity (± 500 kb; ensembl database, release 75) to the MS risk single nucleotide polymorphisms (SNPs) proposed by the most recent multiple sclerosis GWAS in 2011, revealed that 67.3% of the MS risk genes were differentially expressed in EAE. Expression patterns of Bach2, Il2ra, Irf8, Mertk, Odf3b, Plek, Rgs1, Slc30a7, and Thada were confirmed in independent experiments, suggesting a contribution to T cell pathogenicity. Functional analysis of Nfatc1 revealed that Nfatc1-deficient CD4+ T cells were restrained in their ability to induce clinical signs of EAE. Nfatc1-deficiency allowed proper T cell activation, but diminished their potential to fully differentiate into Th17 cells and to express high amounts of lineage cytokines. As the inducible Nfatc1/αA transcript is distinct from the other family members, it could represent an interesting target for therapeutic intervention in MS.rn