Segment-based multiple sequence alignment

Abstract

In this PhD thesis the segment-based approach for multiple sequence alignment, initially introduced by the DIALIGN program, is thorougly investigated and substiantially improved. The segment-based approach belongs to the class of local alignment methods and thus is very strong in finding locally conserved motifs, whereas global methods align the input sequences globally from the beginning to end without specifically looking at locally occuring conserved motifs. Local alignments and especially segment-based methods therefore play an important role in molecular biology research, which is underscored by the fact that the results of this PhD thesis have already been extensively used in various biological research areas.

Initially we present a complete re-implementation of the DIALIGN approach -- DIALIGN-T -- which also embraces several improvements, such as the exclusion of low-scoring sub-fragments and weight score factors yielding a statistical superior method on local and global benchmark databases. However DIALIGN-T still uses a greedy and, therefore, very naive strategy to build the final alignment so that we re-formulate the assembling phase as an optimization problem that is NP-complete, but for which we can proove it to be a fixed parameter tractable (FPT) in the number of input sequences, under reasonable assumptions. Since we are interested in approaches that are useful in practice, we develop a plane-sweep algorithm that optimally solves the assembling problem whereby its computational time basically grows with the number of simultaneously occuring conflicting situations. By exploiting the ideas of the plane-sweep algorithm, we extend it to a full algorithmic framework which acts as a basis for developing further optimal or near-optimal heuristics for assembling an alignment from a given set of input similarities. Inspired by this framework, we improve DIALIGN-T to its most recent version DIALIGN-TX, which incorporates substiantial improvements by combining greedy and progressive strategies for assembling the alignment. In order to measure the quality of our improvements, we used the standard benchmark databases BAliBASE and BRaliBASE~II on global alignments and the artifically generated databases IRMBASE and DIRMBASE on local alignments. The results show that DIALIGN-TX is currently outperforming all other methods on the local benchmark databases while still providing very good results on global alignments, i.e. it even outperforms the very popular global alignment program CLUSTAL~W on the global benchmark database BAliBASE~3.

Altogether we conclude that DIALIGN-TX is one of the strongest methods on the important class of local alignments while still providing very good results on global alignments and consuming in practice only a reasonable amount of computational time. In combination with the algorithmic framework we obtain a rich basis or future improvements to the segment-based approach for computing general and (biological) domain-specific multiple sequence alignments.

In dieser Dissertation wird der Segment-basierte Ansatz zur Lösung des Multiplen Sequenz Alignment Problems, der initial mit dem DIALIGN Program eingeführt wurde, untersucht und substantiell weiterentwickelt. Der Segment-basierte Ansatz zählt zu den lokalen Alignment Methoden, die insbesondere bei der Suche nach lokal konservierten Motiven den globalen Methoden, die die Eingabesequenzen ohne spezifische Berücksichtigung von lokal konservierten Motiven global von Anfang bis Ende alignieren, überlegen sind. Lokalen Alignment Methoden und insbesondere der Segment-basierte Ansatz spielen aus diesem Grund eine wichtige Rolle in der molekularbiologischen Forschung. Dies zeigt sich unter anderem auch darin, dass die Ergebnisse dieser Arbeit bereits mehrfach für verschiedene biologische Fragestellungen erfolgreich eingesetzt wurden.

Mit DIALIGN-T wird eine signifikant verbesserte Re-Implementation des Segment-basierten Ansatzes vorgestellt. Im Rahmen dieser Verbesserungen werden insbesondere niedrig bewertete und damit störende Sub-Fragmente ausgeschlossen sowie zusätzlich über Gewichtungsfaktoren die Priorität der einzelnen Fragmente in der Assemblierungsphase optimaler vergeben. Jedoch wird innerhalb DIALIGN-T nach wie vor ein naives 'greedy' Verfahren eingesetzt, um das finale Alignment aus der Menge der errechneten Fragmente zusammenzufügen, so dass wir diese Assemblierungsphase daher als mathematisches Optimierungsproblem formulieren, welches NP-vollständig ist. Wir zeigen jedoch, dass dieses Problem, unter angemessenen Rahmenbedingungen, 'Fixed Parameter Tractable' (FPT) in der Anzahl der Eingabesequenzen ist. Da wir uns für in der Praxis gut anwendbare Ansätze interessieren, entwickeln wir den sogenannten Plane-Sweep Algorithmus, der das Assemblierungsproblem exakt löst und dessen Komplexität im Wesentlichen nur mit der Anzahl der parallel auftretenden Konfliktsituationen steigt. Basierend auf der Grundidee des Plane-Sweep Algorithmus, leiten wir anschließ{}end ein ganzes algorithmisches Frameworks ab, welches als Grundlage zur systematischen Entwicklung weiterer optimaler und fast-optimaler Algorithmen/Heuristiken dient. Insbesondere wurde durch dieses Framework die Entwicklung von DIALIGN-TX inspiriert. DIALIGN-TX stellt momentan die neueste Version des DIALIGN Ansatzes dar und setzt eine kombinierte Methode aus progressiven und greedy Strategien ein. Um die Alignment-Qualität zu messen, wurden für globale Alignments die Datenbanken BAliBASE~3 und BRAliBase~II als Referenz verwendet; für lokale Alignments wurden die künstlichen Datenbanken IRMBASE und DIRMBASE erzeugt, die aus in Zufallssequenzen implantierte konservierten Motive bestehen. Anhand unserer Benchmark-Ergebnisse zeigen wir, dass DIALIGN-TX allen anderen aktuell populären Methoden auf lokalen Alignments qualitativ überlegen ist, aber auch zu sehr guten Resultaten auf globalen Alignments führt. Insbesondere sind die Ergebnisse von DIALIGN-TX auf der globalen Benchmarkdatenbank BAliBASE~3 signifikant besser als die des sehr populären globalen Alignment-Programs CLUSTAL~W.

Zusammenfassend schließ{}en wir, dass DIALIGN-TX eine der stärksten Methoden auf der wichtigen Klasse der lokalen Alignments darstellt, dabei ebenfalls auf globalen Alignments sehr gute Ergebnisse liefert und im praktischen Einsatz innerhalb vernünftiger Zeitschranken läuft. In Kombination mit dem algorithmischen Framework erhalten wir eine reichhaltige Basis für zukünftige Verbesserungen des Segment-basierten Ansatzes zur Berechnung von allgemeinen und (biologisch) Domänen spezifischen Multiplen Sequenz Alignments.