Das Ziel dieser Arbeit sind mathematische Modelle für den Genomvergleich, um die evolutionäre Distanz zwischen zwei gegebenen Genomen zu schätzen. Wir präsentieren ein neues Modell für den Genomvergleich und wenden die Double-Cut-and-Join Operation auf dieses Genom-Modell an.
Im Unterschied zum traditionellen sequenzbasierten Ansatz lässt sich Evolution auf Genomebene durch Rearrangements beschreiben, die die Reihenfolge und die Richtung von Chromosomenabschnitten umordnen. Mit steigender Anzahl von entschlüsselten Genomen ist es jetzt möglich, ganze Genome statt kurzer Chromosomenabschnitte zu vergleichen. Unterschiedliche Arten haben häufig ähnliche Gene, die von gemeinsamen Vorfahren geerbt wurden, und große Veränderungen in der Reihenfolge dieser Gene lassen sich in entfernter verwandten Genomen beobachten. Daher wird angenommen, dass die Anzahl von Rearrangements der Genreihenfolge in einem Genom ein Maß für die evolutionäre Distanz zwischen zwei Arten ist.
Ein häufig verwendeter Ansatz für die evolutionäre Rekonstruktion ist die Berechnung einer Folge von Rearrangements der Genreihenfolge. Dies motiviert das folgende kombinatorische Problem: Man berechne für zwei gegebene Genome, die dieselbe Menge an Genen enthalten, eine kürzeste Folge von Rearrangements, die erforderlich sind, um ein Genom in das andere umzugestalten. Die Länge dieser Folge ist die evolutionäre Distanz zwischen den zwei Genomen. Die gebräuchlichen Rearrangments für multichromosomale Genome sind Translokationen, Fusionen, Spaltungen, Inversionen und Block-Austausche. Bemerkenswerterweise können alle diese Rearrangements durch die Double-Cut-and-Join (DCJ) Operation modelliert werden.
Neben Rearrangements ist die Verdopplung des gesamten Genoms eine andere wichtige Quelle für die Evolution von Genomen. Im Vergleich zur Verdopplung von Chromosomenabschnitten ist die Verdopplung eines Genoms ein seltenes Ereignis. Daraus ergibt sich das folgende kombinatorische Problem, genannt Genom-Halbierungs-Problem: Man finde für ein gegebenes, dupliziertes und durch Rearrangements umgeordnetes Genom ein prädupliziertes Genom, so dass die Entfernung zwischen diesen Genomen in Bezug auf die evolutionäre Distanz minimal ist. Die Lösung zu diesem Problem hängt vom zu Grunde liegenden Genommodell und auch von den erlaubten Rearrangements ab.
Die Hauptbeiträge dieser Arbeit lassen sich wie folgt zusammenfassen:
1. Ein graphenbasiertes Genommodell: Die grundlegenden Werkzeuge für unsere Darstellung von Genomen sind Graphen, die Vereinigungen von Pfaden und Zyklen sind. Auf diesem Typ von Graphen, genannt Genom-Graphen, ist es möglich, alle Rearrangements auf Genomen zu modellieren, die sowohl zirkuläre als auch lineare Chromosomen haben. Mit Hilfe von Graphen werden Genome sowie Rearrangements dargestellt.
2. DCJ-Distanzformel und Sortier-Algorithmus: Die DCJ-Operation wird auf Genome mit zirkulären und linearen Chromosomen angewandt. Eine sehr einfache Datenstruktur, der Adjazenz-Graph, ist symmetrisch in Bezug auf die beiden Genome, deren evolutionäre Distanz berechnet wird. Außerdem vereinfacht dieser Graph die Theorie und Distanzberechnung beträchtlich und ermöglicht einen effizienten Sortier-Algorithmus, der modifiziert werden kann, um den Gebrauch von bestimmten Rearrangements zu optimieren.
3. Einheitliche Behandlung der traditionellen HP-Distanzen: Unser Hauptergebnis ist eine Analyse der Beziehung zwischen dem allgemeinen DCJ-Modell und den drei Rearrangementmodellen, die in der traditionellen Hannenhalli-Pevzner-(HP-)Theorie betrachtet werden: das Inversions-Modell, das Translokations-Modell und das kombinierte Modell mit Inversionen, Translokationen, Fusionen und Spaltungen. Das letzte Modell motiviert die allgemeine HP-Distanz, die mit Konzepten aus dem Inversions-Modell gelöst werden kann. Mit Hilfe einer Baumstruktur können alle diffizilen Eigenschaften des allgemeinen HP-Problems dargestellt werden. Außerdem zeigen wir, dass alle drei in der HP-Theorie betrachteten Rearrangementmodelle in das allgemeine DCJ-Modell integriert werden können.
4. Rekonstruktionsalgorithmus für duplizierte Genome: Das Genom-Halbierungs-Problem unter Betrachtung von DCJ-Operationen wird neu betrachtet, wobei das präduplizierte Genom lineare und zirkuläre Chromosome enthalten kann. Dieses Genommodell berücksichtigt Einschränkungen, die für Genome mit nur linearen Chromosomen, sowie solche für Genome mit nur zirkulären Chromosomen erforderlich sind. Ein neuer Beweis und ein einfacher Algorithmus zur Rekonstruktion des Ursprungsgenoms werden gegeben. Außerdem korrigieren wir einen Fehler in einer Analyse von Warren und Sankoff.