Dissecting multiple sequence alignment methods: The analysis, design and development of generic multiple sequence alignment components in SeqAn

Abstract

Multiple sequence alignments are an indispensable tool in bioinformatics. Many applications rely on accurate multiple alignments, including protein structure prediction, phylogeny and the modeling of binding sites. In this thesis we dissected and analyzed the crucial algorithms and data structures required to construct such a multiple alignment. Based upon that dissection, we present a novel graph-based multiple sequence alignment program and a new method for multi-read alignments occurring in assembly projects. The advantage of the graph-based alignment is that a single vertex can represent a single character, a large segment or even an abstract entity such as a gene. This gives rise to the opportunity to apply the consistency-based progressive alignment paradigm to alignments of genomic sequences. The proposed multi-read alignment method outperforms similar methods in terms of alignment quality and it is apparently one of the first methods that can readily be used for insert sequencing. An important aspect of this thesis was the design, the development and the integration of the essential multiple sequence alignment components in the SeqAn library. SeqAn is a software library for sequence analysis that provides the core algorithmic components required to analyze large-scale sequence data. SeqAn aims at bridging the current gap between algorithm theory and available practical implementations in bioinformatics. Hence, we always describe in conjunction to the theoretical development of the methods, the actual implementation of the data structures and algorithms in order to strengthen the use of SeqAn as an experimental platform for rapidly developing and testing applications. All presented methods are part of the open source SeqAn library that can be downloaded from our website, www.seqan.de.

Multiple Sequenzvergleiche sind ein entscheidendes Hilfsmittel in der Bioinformatik. Zahlreiche Anwendungen, wie zum Beispiel Proteinstrukturvorhersagen, Phylogenie oder die Modellierung von Bindungsstellen beruhen auf der effizienten und biologisch korrekten Berechnung von multiplen Sequenzvergleichen. Aufgrund dieser enormen Bedeutung wurden in der vorliegenden Doktorarbeit Methoden zum multiplen Sequenzvergleich detailiert untersucht, analysiert und in elementare Algorithmen und Datenstrukturen zergliedert. Diese strukturelle Zerlegung bildet die Grundlage für unsere eigenen Weiterentwicklungen. Insbesondere diskutieren und beschreiben wir hier zwei erweiterte Ansätze zum graphbasierten, multiplen Sequenzvergleich und zum Konsensusalignment. Für beide Methoden zeigen wir die Vorteile unserer Algorithmen gegenüber bisherigen Ansätzen. Ein weiterer zentraler Bestandteil der Arbeit ist der Entwurf, die Implementierung und die Integration dieser grundlegenden Algorithmen und Datenstrukturen zum multiplen Sequenzvergleich in der SeqAn Bibliothek. SeqAn ist eine Softwarebibliothek zur Sequenzanalyse. SeqAn hat das Ziel die neuesten Erkenntnisse aus der Algorithmentheorie für praktische Anwendungen verfügbar zu machen und im Rahmen einer experimentellen Plattform anzubieten, in der Algorithmen einfach entworfen, entwickelt und verglichen werden können. Daher beschreiben wir in der gesamten Arbeit neben der theoretischen Entwicklung der Algorithmen ebenso deren softwaretechnische Umsetzung in SeqAn und zeigen zum Beispiel anhand von paarweisen Alignmentalgorithmen deren Überlegenheit in Zeit- und Platzbedarf verglichen mit bisherigen Implementierungen. Am Ende der Arbeit werden Einschränkungen und mögliche Erweiterungen der vorgestellten Methoden diskutiert. Alle Algorithmen und Datenstrukturen sind im Rahmen der SeqAn Bibliothek frei verfügbar: www.seqan.de.