Contributions to computing and modeling multiple whole-genome alignments

Abstract

Recent advances in sequencing technologies have opened up the opportunity to study whole genomes at the nucleotide level. Similarities in the nucleotide sequences of genomes provide new insights in the relationships of organisms and species. Multiple whole-genome alignments represent these similarities, however their computation is challenging. In contrast to approaches for other sequence alignment problems, genome alignment methods have to deal with very long sequences and with non-colinearity of similarities. This thesis makes three contributions to the development of multiple whole-genome alignment methods. The prevailing strategy of such methods is to combine a set of local alignments to a global genome alignment. This thesis suggests an efficient and fully sensitive local alignment approach, compares graph data structures for representing genome alignments, and describes hidden rearrangement breakpoints that become visible only in the comparison of more than two genomes. All three contributions provide potential for significant improvements to the computation or modeling of genome alignments. In a comparison to other local alignment approaches, the new local aligner is the fastest of three fully sensitive ones and competitive with seed-and-extend approaches despite having full sensitivity. The assessment of graph data structures describes for the first time all graphs using the same terminology, and demonstrates how the graph structures differ in their information content. Finally, an analysis of breakpoints in simulated genome alignments suggests that hidden breakpoints are abundant and relevant for measuring the accuracy of genome alignments. In summary, the three contributions provide a promising basis for future genome alignment methods.

In den letzten Jahren wurden enorme Fortschritte mit Sequenziertechnologien gemacht, die es ermöglichen, ganze Genome auf Nukleotidebene zu untersuchen. Genomische Nukleotidsequenzen weisen erstaunliche Ähnlichkeiten auf, die neue Einblicke in Verwandschaftsbeziehungen von Organismen und Arten gewähren können. Multiple Genomalignments stellen diese Ähnlichkeiten zwischen verschiedenen Genomen dar, ihre Berechnung ist allerdings sehr anspruchsvoll. Im Gegensatz zu Methoden für andere Squenzalignmentprobleme muss bei der Berechnung von Genomalignments zum einen die gewaltige Länge von genomischen Sequenzen bewältigt werden und zum anderen beachtet werden, dass ähnliche Abschnitte in verschiedenen Genomen in unterschiedlicher Anordnung vorliegen können (Nichtkolinearität). Methoden zur Berechnung von Genomalignments suchen meist zunächst lokale Alignments und fügen diese anschließend zu einem globalen Genomalignment zusammen. Die vorliegende Arbeit leistet drei Beiträge zu solchen Methoden: Es wird ein effizienter Ansatz für lokales Alignment vorgeschlagen, Graphdatenstrukturen für Genomalignments verglichen und genomische Bruchstellen beschrieben, die erst im Vergleich von mehr als zwei Genomen sichtbar werden und auf zusätzliche nichtkolineare Veränderungen hinweisen.