Segment-based multiple sequence alignment [Elektronische Ressource] / vorgelegt von Amarendran Ramaswami Subramanian

Sujets

• Informatik
• Biologie

Informations

• Publié par: eberhard_karls_universitat_tubingen
• Publié le: 01 janvier 2009
• Nombre de lectures: 19
• Langue: English

Extrait

Segment-based Multiple Sequence Alignment
Dissertation
der Fakult at fur Informations- und Kognitionswissenschaften
der Eberhard-Karls-Universit at Tubingen
zur Erlangung des Grades eines
Doktors der Naturwissenschaften
(Dr. rer. nat.)
vorgelegt von
Dipl.-Inform. Dipl.-Math. Amarendran Ramaswami Subramanian
aus Stuttgart
Tubingen
2009Tag der mundlic hen Quali kation: 11.02.2009
Dekan: Prof. Dr. Oliver Kohlbacher
1. Berichterstatter: Prof. Dr. Michael Kaufmann
2. Berich Prof. Dr. Burkhard Morgenstern, Univ. G ottingenThis work is dedicated to my family.
3ABSTRACT
In this PhD thesis the segment-based approach for multiple sequence align-
ment, 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 nding locally conserved
motifs, whereas global methods align the input sequences globally from the be-
ginning to end without speci cally looking at locally occuring conserved motifs.
Local alignments and especially segment-based methods therefore play an im-
portant 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
in chapter 3 { 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. How-
ever DIALIGN-T still uses a greedy and, therefore, very naive strategy to build
the nal alignment so that in chapter 4 we re-formulate the assembling phase
as an optimization problem that is NP-complete, but for which we can proove
it to be a xed 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 con icting situations. By exploiting the
ideas of the plane-sweep algorithm, we extend it, in chapter 5, to a full al-
gorithmic 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, in chapter 6, DIALIGN-T
to its most recent version DIALIGN-TX, which incorporates substiantial im-
provements 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 align-
ments and the arti cally generated databases IRMBASE and DIRMBASE on
local alignments. The results show that DIALIGN-TX is currently outperform-
ing all other methods on the local benchmark databases while still providing
very good results on global alignments, i.e. it even outperforms the very popu-
lar 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 ofcomputational 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-speci c multiple sequence alignments.
5ZUSAMMENFASSUNG
In dieser Dissertation wird der Segment-basierte Ansatz zur L osung des Mul-
tiplen Sequenz Alignment Problems, der initial mit dem DIALIGN Program
eingefuhrt wurde, untersucht und substantiell weiterentwickelt. Der Segment-
basierte Ansatz ahltz zu den lokalen Alignment Methoden, die insbesondere
bei der Suche nach lokal konservierten Motiven den globalen Methoden, die
die Eingabesequenzen ohne spezi sche Beruc ksichtigung von lokal konservierten
Motiven global von Anfang bis Ende alignieren, ub erlegen sind. Lokalen Align-
ment 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
fur verschiedene biologische Fragestellungen erfolgreich eingesetzt wurden.
In Kapitel 3 wird mit DIALIGN-T eine signi kant verbesserte Re-Implementation
des Segment-basierten Ansatzes vorgestellt. Im Rahmen dieser Verbesserungen
werden insbesondere niedrig bewertete und damit st orende Sub-Fragmente aus-
geschlossen sowie zus atzlich ub er Gewichtungsfaktoren die Priorit at der einzel-
nen Fragmente in der Assemblierungsphase optimaler vergeben. Jedoch wird
innerhalb DIALIGN-T nach wie vor ein naives ’greedy’ Verfahren eingesetzt,
um das nale Alignment aus der Menge der errechneten Fragmente zusammen-
zufugen, so dass wir diese Assemblierungsphase daher in Kapitel 4 als mathe-
matisches Optimierungsproblem formulieren, welches NP-vollst andig ist. Wir
zeigen jedoch, dass dieses Problem, unter angemessenen Rahmenbedingungen,
’Fixed Parameter Tractable’ (FPT) in der Anzahl der Eingabesequenzen ist.
Da wir uns fur in der Praxis gut anwendbare Ans atze interessieren, entwickeln
wir den sogenannten Plane-Sweep Algorithmus, der das Assemblierungsprob-
lem exaktostl und dessen Komplexit at im Wesentlichen nur mit der Anzahl der
parallel auftretenden Kon iktsituationen steigt. Basierend auf der Grundidee
des Plane-Sweep Algorithmus, leiten wir anschlie end ein ganzes algorithmis-
ches Frameworks in Kapitel 5 ab, welches als Grundlage zur systematischen En-
twicklung weiterer optimaler und fast-optimaler Algorithmen/Heuristiken dient.
Insbesondere wurde durch dieses Framework die Entwicklung von DIALIGN-TX
in Kapitel 6 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 at zu messen, wurden fur
globale Alignments die Datenbanken BAliBASE 3 und BRAliBase II als Ref-
erenz verwendet; fur lokale Alignments wurden die kunstlic hen 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 aren Methoden auf lokalen
Alignments qualitativ ub erlegen ist, aber auch zu sehr guten Resultaten aufglobalen Alignments fuhrt. Insbesondere sind die Ergebnisse von DIALIGN-TX
auf der globalen Benchmarkdatenbank BAliBASE 3 signi kant besser als die
des sehr popul aren globalen Alignment-Programs CLUSTAL W.
Zusammenfassend schlie en wir, dass DIALIGN-TX eine der st arksten Metho-
den auf der wichtigen Klasse der lokalen Alignments darstellt, dabei ebenfalls auf
globalen Alignments sehr gute Ergebnisse liefert und im praktischen Einsatz in-
nerhalb vernunftiger Zeitschrankenauft.l In Kombination mit dem algorithmis-
chen Framework erhalten wir eine reichhaltige Basis fur zukunftige Verbesserun-
gen des Segment-basierten Ansatzes zur Berechnung von allgemeinen und (bi-
ologisch) Dom anen spezi schen Multiplen Sequenz Alignments.
7CONTENTS
1. Introduction: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 10
2. Background : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 13
2.1 Biological background . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Problem description . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.1 Computing pairwise alignments . . . . . . . . . . . . . . . 16
2.2.2 The general multiple sequence alignment problem . . . . . 25
2.2.3 The segment-based approach . . . . . . . . . . . . . . . . 30
2.3 Common multiple sequence alignment approaches . . . . . . . . . 31
2.3.1 Global alignment strategies . . . . . . . . . . . . . . . . . 31
2.3.2 Local alignment . . . . . . . . . . . . . . . . . . 34
3. The DIALIGN-T program : : : : : : : : : : : : : : : : : : : : : : : : : 37
3.1 Pairwise computation of the fragments . . . . . . . . . . . . . . . 37
3.1.1 The objective function in DIALIGN-T . . . . . . . . . . . 38
3.1.2 Approximation of the objective function . . . . . . . . . . 39
3.1.3 Dynamic programming . . . . . . . . . . . . . . . . . . . . 41
3.1.4 Excluding low-scoring sub-fragments . . . . . . . . . . . . 42
3.2 Assembling the multiple sequence alignment . . . . . . . . . . . . 45
3.2.1 Consistency data structure . . . . . . . . . . . . . . . . . 45
3.2.2 Weight score factors . . . . . . . . . . . . . . . . . . . . . 46
3.2.3 Dealing with inconsistent fragments . . . . . . . . . . . . 48
3.3 Benchmark results . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4. Constructing multiple sequence alignments from pairwise local similari-
ties : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 58
4.1 The maximum fMSA-subgraph problem . . . . . . . . . . . . . . 59Contents
4.2 NP-Completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.3 E cient dynamic programming .