Textdokument
Genome Rearrangement Algorithmen
Lade...
Volltext URI
Dokumententyp
Dateien
Zusatzinformation
Datum
Autor:innen
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Verlag
Gesellschaft für Informatik
Zusammenfassung
Durch die steigende Anzahl von vollständig sequenzierten Genomen gewinnt der Vergleich von Spezies auf Basis der sequenzierten Genome immer mehr an Bedeutung. Im Gegensatz zum klassischen Ansatz, welcher ein Distanzmaß basierend auf Punktmutationen verwendet, lassen Genome Rearrangement Algorithmen kleinere Mutationen ausser acht und berücksichtigen nur größere Umstrukturierungen, welche die Reihenfolge der Gene auf den Chromosomen verändern. Dadurch sind diese Algorithmen ein wertvolles Hilfsmittel zum Vergleich von Spezies, welche seit Millionen von Jahren divergieren, sowie von sich schnell verändernden Genomen, wie sie zum Beispiel in Krebszellen vorkommen.
Die Untersuchung dieser Genomumstrukturierungen führt zu einer Vielzahl von algorithmischen Fragestellungen, wie die Berechnung von evolutionären Distanzen, die Rekonstruktion evolutionärer Ereignisse und der Genreihenfolge in hypothetischen Vorfahren, bis hin zur Berechnung ganzer phylogenetischer Bäume. In der hier vorgestellten Dissertation [Bad11] werden einige dieser Problemstellungen sowohl von der theoretischen als auch von der praktischen Seite untersucht. So wird gezeigt, dass das Median-Problem, bei welchem ein möglichst plausibler Vorfahr für drei gegebene Genome gesucht wird, sowohl für die Transpositionsdistanz als auch für die gewichtete Reversal- und Transpositionsdistanz zu den NP-vollständigen Problemen gehört. Dazu wird ein Algorithmus vorgestellt, welcher in der Praxis vorkommende Instanzen dieser Probleme dennoch lösen kann. Desweiteren werden ein neuer Algorithmus zur phylogenetischen Rekonstruktion basierend auf diesen Distanzen sowie erstmals Algorithmen zum paarweisen Genomvergleich, welche Duplikationen und Deletionen beliebiger Länge zulassen, vorgestellt. Ein weiteres Ergebnis der Dissertation, auf welches in dieser Zusammenfassung jedoch nicht näher eingegangen werden soll, ist eine effiziente Implementierung eines Vor- und Nachverarbeitungsschritt, welcher für viele Genome Rearrangement Algorithmen benötigt wird.