Humboldt-Universität zu Berlin, Institut für Informatik,Seminar “Fortgeschrittene algorithmische Bioinformatik”, SS 2005

DIALIGN

Seminarvortrag von

Germar Brauer

Humboldt-Universität zu Berlin, Institut für Informatik, Seminar “Fortgeschrittene algorithmische Bioinformatik”, SS 2005 2

Übersicht

DIALIGN = DIagonal ALIGNment

Versionen: DIALIGN, DIALIGN 2, DIALIGN-T

neue und spezielle Methode für multiples Sequenzalignment (MSA)

Idee: Finden von Proteinfamilien mit gleicher Funktion (hochkonservierte Stücke in verschiedenen Organismen)

Einsatzgebiet: Nukleinsäuresequenzen, Proteinsequenzen

Humboldt-Universität zu Berlin, Institut für Informatik, Seminar “Fortgeschrittene algorithmische Bioinformatik”, SS 2005 3

Voraussetzungen

Algorithmus von Needleman-Wunsch mit gegebener Matrix (PAM, BLOSUM)

„lokale“ Version von Smith-Waterman

Regionen mit hoher Ähnlichkeit werden von Regionen mit geringer Ähnlichkeit unterbrochen (Introns bei DNA, Loops bei Proteinen)

es werden Blöcke statt einzelner Zeichen miteinander verglichen

Humboldt-Universität zu Berlin, Institut für Informatik, Seminar “Fortgeschrittene algorithmische Bioinformatik”, SS 2005 4

Was wird untersucht?

untersucht werden nur die Diagonalen

Humboldt-Universität zu Berlin, Institut für Informatik, Seminar “Fortgeschrittene algorithmische Bioinformatik”, SS 2005 5

Konsistente und nicht-konsistente Paare

konsistente Zuordnung

Humboldt-Universität zu Berlin, Institut für Informatik, Seminar “Fortgeschrittene algorithmische Bioinformatik”, SS 2005 6

Konsistente und nicht-konsistente Paare

nicht-konsistente Zuordnung a) doppelte Belegung

b) cross-over Zuordnung

Humboldt-Universität zu Berlin, Institut für Informatik, Seminar “Fortgeschrittene algorithmische Bioinformatik”, SS 2005 7

Algorithmus

Bilden aller optimalen paarweisen Alignments

Humboldt-Universität zu Berlin, Institut für Informatik, Seminar “Fortgeschrittene algorithmische Bioinformatik”, SS 2005 8

Algorithmus

gegeben : Diagonale D mit Länge l und Anzahl m von Matchen

P ist die Wahrscheinlichkeit eine Diagonale der Länge l mit mindestens m Matches zu bekommen

p Wahrscheinlichkeit in Matrix ein Match zu repräsentieren

p=0,25 bei DNA, p=0,05 bei Proteinen

ilil

miil ppmlP

)1(),(

Humboldt-Universität zu Berlin, Institut für Informatik, Seminar “Fortgeschrittene algorithmische Bioinformatik”, SS 2005 9

Algorithmus

T ist frei wählbarer Schwellenwert (verringert Rauschen)

die Länge Diagonale ist mindestens 7 Werte

sonst

TmlfallsEmlEDw

,0

),(),,(:)(

)),(log(:),( mlPmlE

Humboldt-Universität zu Berlin, Institut für Informatik, Seminar “Fortgeschrittene algorithmische Bioinformatik”, SS 2005 10

Algorithmus

Problem: - Dialign bevorzugt viele kurze Diagonalen vor wenigen langen - signifikante lokale

Gemeinsamkeiten gehen im „Rauschen“ der kleinen zufälligen Diagonalen unter

keine allgemeine Regel für T (Schwellenwert)

benötigte Mindestlänge der Diagonalen ist sehr willkürlich

Humboldt-Universität zu Berlin, Institut für Informatik, Seminar “Fortgeschrittene algorithmische Bioinformatik”, SS 2005 11

Algorithmus

Lösung: neue Wahrscheinlichkeit in Dialign 2

finde eine Diagonale der Länge l mit mindestens m gemeinsamen Paaren, in einer Vergleichsmatrix von 2 zufälligen Sequenzen mit derselben Länge, wie die Originalsequenzen

die Wahrscheinlichkeit hängt nun von l, m und der Länge der Sequenzen ab

),(* mlP

)),(log()( *2 mlPDw

Humboldt-Universität zu Berlin, Institut für Informatik, Seminar “Fortgeschrittene algorithmische Bioinformatik”, SS 2005 12

Algorithmus

basieren auf experimentell ermittelten Werten

für kleinere Werte gilt folgende Approximation

definiere:

5* 10),( mlP

),(),( 21* mlPllmlP

21 loglog: llK

KDwllmlP

mlPllmlPDw

)(loglog),(log

)],(log[),(log)(

21

21*

2

Humboldt-Universität zu Berlin, Institut für Informatik, Seminar “Fortgeschrittene algorithmische Bioinformatik”, SS 2005 13

Algorithmus (Overlap)

Sj gehört zu Dl und Dm

)(:),(~ nml DwDDw

Humboldt-Universität zu Berlin, Institut für Informatik, Seminar “Fortgeschrittene algorithmische Bioinformatik”, SS 2005 14

Algorithmus (Overlap)

sind Dl und Dm identisch oder haben keinen Overlap

für eine beliebige Diagonale D wird Overlap-Gewicht folgendermaßen definiert

DE

EDwDwDw ),(~)(:)(*

0:),(~ ml DDw

Humboldt-Universität zu Berlin, Institut für Informatik, Seminar “Fortgeschrittene algorithmische Bioinformatik”, SS 2005 15

Algorithmus

Gewichtsscore für Diagonalen berechnen

je größer das Gewicht, desto signifikanter die Diagonale

Humboldt-Universität zu Berlin, Institut für Informatik, Seminar “Fortgeschrittene algorithmische Bioinformatik”, SS 2005 16

Algorithmus

Überführen der Diagonalen in MSA mit Greedy-Strategie

Diagonale mit höchsten Score wird die erste Diagonale

Überprüfen der weiteren Diagonalen auf Konsistenz und MSA hinzufügen

Humboldt-Universität zu Berlin, Institut für Informatik, Seminar “Fortgeschrittene algorithmische Bioinformatik”, SS 2005 17

Algorithmus

Wiederholen des Algorithmus – weitere Diagonale

D5 mit Gewicht 4,6 zum MSA hinzufügen

im weiteren Schritt keine neuen Diagonalen

Humboldt-Universität zu Berlin, Institut für Informatik, Seminar “Fortgeschrittene algorithmische Bioinformatik”, SS 2005 18

Algorithmus

einmal hinzugefügte Diagonale kann nicht mehr entfernt werden

Ergebnis: alle Diagonalen werden in Spalten angeordnet unbenutzte Zeichen werden klein

geschrieben

Humboldt-Universität zu Berlin, Institut für Informatik, Seminar “Fortgeschrittene algorithmische Bioinformatik”, SS 2005 19

Überblick

Humboldt-Universität zu Berlin, Institut für Informatik, Seminar “Fortgeschrittene algorithmische Bioinformatik”, SS 2005 20

Zeitkomplexität

„consistency bounds“ und

für x und Sequenz S1

für x und Sequenz S2

benötigt für jede Diagonale, die zu M2 kommt

),( ixb ),( ixb

5)1,( xb 9)1,( xb

4)2,( xb 7)2,( xb

)( 2 LNO

Humboldt-Universität zu Berlin, Institut für Informatik, Seminar “Fortgeschrittene algorithmische Bioinformatik”, SS 2005 21

Zeitkomplexität

(a)

(b)

(c)

(d)

Gesamtkomplexität:

)( 24anNO

)( 2anNO

)( 22 LNO

)( 22 LNnNO a

)( 24 LNO

Humboldt-Universität zu Berlin, Institut für Informatik, Seminar “Fortgeschrittene algorithmische Bioinformatik”, SS 2005 22

Ergebnisse Vergleich mit anderen MSA Algorithmen

(HTH = Helix-Turn-Helix, bHLH = basic Helix-Loop-Helix)

HTH Transferase bHLHSequenzanzahl 30 16 9DIALIGN 1, T=10 19,2,2 16 9DIALIGN 2, T=0 24,2 16 9TWOALIGN 10,6,3,3 13,2 9ITERALIGN 16 15 9CLUSTAL W 5,3,2,2,2 13 3,2

Humboldt-Universität zu Berlin, Institut für Informatik, Seminar “Fortgeschrittene algorithmische Bioinformatik”, SS 2005 23

Vorteile

beim globalen Alignment vergleichbare Ergebnisse mit anderen Standardmethoden (Clustal W)

bessere Ergebnisse im Vergleich mit anderen Methoden beim lokalen Alignment

kleine hochkonservierte Regionen werden erkannt

keine Strafpunkte für Gaps

Nachteil: Dialign kann leicht im lokalen Maximum laufen

Humboldt-Universität zu Berlin, Institut für Informatik, Seminar “Fortgeschrittene algorithmische Bioinformatik”, SS 2005 24

Screenshot http://bibiserv.techfak.uni-bielefeld.de/dialign/

Humboldt-Universität zu Berlin, Institut für Informatik, Seminar “Fortgeschrittene algorithmische Bioinformatik”, SS 2005 25

Beispiel

Humboldt-Universität zu Berlin, Institut für Informatik, Seminar “Fortgeschrittene algorithmische Bioinformatik”, SS 2005 26

Literatur

B. Morgenstern (1999) DIALIGN 2: improvement of the segment-to-segment approach to multiple sequence alignment. Bioinformatics 15, 211-218

B. Morgenstern, W.R. Atchley, K. Hahn, A. Dress (1998) Segment-based scores for pairwise and multiple sequence alignments. Proceedings ISMB'98, pp. 115-121

B. Morgenstern, A. Dress, T. Werner (1996) Multiple DNA and protein sequence alignment based on segment-to-segment comparison.Proc. Natl. Acad. Sci. USA 93, 12098-12103

B. Morgenstern, K. Frech, A. Dress, T. Werner (1998) DIALIGN: Finding local similarities by multiple sequence alignment.Bioinformatics 14, 290-294