Upload
gervas-hemker
View
106
Download
0
Embed Size (px)
Citation preview
Finding Optimal Pairs of Patterns
nach Hideo Bannai, Heikki Hyyrö, Ayumi Shinohara, Masayuki Takeda, Kenta Nakai, and Satoru Miyano
von Jan Beisenkamp
2
Inhalt
I. Einleitung
II. Notationen
III. Problemdefinition
IV. Datenstrukturen- (Generalized) Suffix Tree- Suffix Array
V. 2 Algorithmen
VI. Umsetzung mit Suffix Arrays
VII. Beispiele
3
Einleitung
• Suche nach optimalen Paaren von Stringmustern• Substrings zur Einteilung von Strings anhand
– von zwei disjunkten Sets (positiv/negativ Beispiele)– eines numerischen Attributs
Maximierung eines entsprechenden Scores• hier: Zwei Substrings mit einer beliebigen
bool‘schen Kombination
4
Einleitung
• Mustererkennung in der Bioinformatik wichtig
• Viele Arbeiten zu dem Thema, Highlights hier:– Effizienter O(N²) Algorithmus bei O(N²) möglichen
Ergebnissen– Beliebige Bool‘sche Funktionen zeigen komplexes
Zusammenspiel der Muster
5
Notationen
• Σ Alphabet, Σ* String• x, y, z sind jeweils Präfix, Substring und Suffix des
Strings w = xyz• length(w) ist die Länge des Strings w• w[i] i-tes Zeichen von w; w[i:j] Substring von i bis j• |S| Kardinalität der Menge S
6
Notationen
• Ψ(p,s) bool‘sche Funktion die genau dann true ist, wenn p Substring von s ist
• ‹p,F,q› (bool‘sches) Musterpaar, gebildet aus Substrings p, q und einer bool‘schen Funktion FBedeutung: Ψ(‹p,F,q›,s) = F(Ψ(p,s),Ψ(q,s))
7
Notationen
• Wir sagen ein Muster oder Musterpaar π passt zu s genau dann wenn Ψ(π,s) = true
• Für Stringmenge S={s1,…,sm}, ist M(π,S) die Teil-Menge aller String zu denen π passt
• Wir gehen davon aus, dass jedem String si ein numerisches Attribut ri zugeordnet ist. Dann gilt
}),(|{),( truesSsSM ii
)),(|(),(
truesrr iiSM i
8
Problemdefinition
• Gegeben sein eine Menge S={s1,…,sm} von Strings mit jeweils zu si assoziierten numerischen Werten ri, sowie eine score FunktionGesucht wird ein Bool‘sches Musterpaar
das score(|M(π)|,ΣM(π) ri) maximiert.
150* ,...,,,|,, FFFqpqFp
9
Positiv/Negativ Beispiele
• Gegeben sind zwei Mengen S1 und S2, mit Positiv- bzw. Negativ-Beispielen und wir suchen ein Muster das besser zu S1 als zu S2 passt
• Wir wählen S=S1 υ S2 und ri = 1 für si aus S1 und 0 sonst
• score erhält nun |M(π,S)| und = |M(π,S1)|
• Mögliche score-Funktionen sind der Informationsgewinn, der Gini Index oder der Chi-Quadrat Test
),( SM ir
10
Muster mit Korrelation
• Gegeben sind eine Sequenzmenge S und die Attribute ri
• Gesucht wird ein Musterpaar, dessen Auftreten in den Sequenzen sich mit ri korrelieren lassen.
• Eine Beispielfunktion ist die Inter-Klassen-Varianz
• Auch möglich ist z.B. ein Wilcoxon Rang Summen Test
)(
2||
12
,)(,)(
),(
M i
m
i i ryMxxm
ry
x
yyxscore
11
Datenstukturen
• Algorithmus konzeptuell entwickelt auf (generalized) suffix trees
• zur effizienteren Implementierung ersetzt durch Suffix Arrays
12
Suffixtree
• Ein Suffixtree zu einem String s ist ein gewurzelter Baum, dessen Kanten mit Substrings von s beschriftet sind und der folgende Kriterien erfüllt:– Sei l(v) der String der durch Konkatenation der
Substrings an den Kanten von der Wurzel zu v steht– Für jedes Blatt stellt l(v) einen Suffix von s dar– Für jeden Suffix existiert genau ein solches Blatt– Jeder innere Knoten hat mindestens zwei ausgehende
Kanten die mit unterschiedlichen Buchstaben beginnen
13
Suffixtree
• Banana$
• a$• ana$• anana$• Banana$• na$• nana$
a
$
nana$
$
na
$
na$
Banana$
14
Generalized Suffix Tree
• Erweiterung für m Strings S={s1,…,sm}
• Erzeugung eines Suffixtrees für s1$1…sm$m wobei $1…,$m eindeutige, unterschiedliche Endmarkierungen sind.
• Pfade werden beim ersten Auftretenden $i beendet und das entstandene Blatt mit idi markiert
15
Generalized Suffix Tree
• Banana$Banane#
• a$• ana$• anana$• anane#• ane#• Banana$• Banane#• e#• na$• nana$• nane#• ne#
a
$
n
$
n
$
n
e#
Banan
a$
e#aa$
e#
n
a$
e#e#a
e#
16
Suffix Array
• Ein Suffix-Array zu einem String s der Länge n ist eine Permutation der Zahlen 1…n die die lexikographische Sortierung der Suffixe anzeigt
• AS[i]=j zeigt, dass s[j:n] der i-te Suffix in lexikographischer Ordnung ist.
• Meist begleitet von einem lcp-Array, dass die Länge der längsten gemeinsamen Präfixe zweier benachbarten Suffixe enthält
lcps[i]=max{k|s[As[i-1]:As[i-1]+k-1]=s[As[i]:As[i]+k-1]}
17
Suffix Array
sortiert
6. a
4. ana
2. anana
1. Banana
5. na
3. nana
Suffixe:
1. Banana
2. anana
3. nana
4. ana
5. na
6. a
a (1)
ana(3)
-(0)
-(0)
na(2)
String S=„Banana“
Suffixarray As=[6,4,2,1,5,3]
LCPs=[0,1,3,0,0,2]
18
Datenstukturen
• Der lca (lowest common ancestor) zweier Knoten ist der nächste gemeinsame Vorfahr beider
• Das (fast) Äquivalent im Suffixarray ist die rmq (range minimum query), die zu zwei Einträgen i,j das minimale Element von lcp[i:j] liefert
• Beide Abfragen lassen sich nach linearen preprocessing in konstanter Zeit beantworten
19
O(N³) Algorithmus
• Es gibt O(N) viele Möglichkeiten für ein einzelnes Muster, da:– GST hat maximal O(N) Knoten– es kommen nur Muster der Form l(v) in Frage
• Es gibt O(N²) Kandidatenpaare für π=‹p,F,q› • Für festes π kann M(π) und damit auch |M(π)| und
in O(N) mit Hilfe eines Linearzeit Substring Algorithmus berechnet werden.
• Da score-Funktion konstante Zeit braucht, ergibt sich insgesamt O(N³)
),( SM ir
20
O(N) Algorithmus
• Basiert auf Lösung für das color set size problem• Preprocessing erspart nach der Auswahl der
Kandidaten die O(N) für Substring-Test• Erweiterung dieses Algorithmus für .
– Berechnet, |M(l(v))| wenn alle ri=1
• Hilfsvariablen:– LF(v): Menge aller Blätter im Teilbaum mit v als Wurzel
– ci(v): Zahl der Blätter in LF(v) die mit idi markiert sind
– I(idi): Liste aller mit mit idi markierten Blätter (depth first)
))(( vlM ir
21
O(N) Algorithmus
• Für diese Knoten gilt:
• Gesuchte Ergebnis lässt sich umschreiben als:
• Diesen Subtrahend nennen wir Korrekturfaktor:
))),((())(( truesvlrr iivlM i
))),(()1(()( truesvlrcr iiivLF i
))),(()(()( truesvlrvcr iiivLF i
))),(()1(()),(( truesvlrcSvlcorr iii
22
O(N) Algorithmus
• Erzeugung von trivial bei bottom-up Durchlauf da rekursiv
• Ein paar nützliche Eigenschaften:– In I(idi) bilden Blätter aus LF(v) ein Intervall der Länge ci
– Ein Intervall der Länge ci in I(idi) enthält ci-1 benachbarte Knotenpaare
– Für enthält der Teilbaum mit Wurzel v auch lca(x,y)
– genau dann wenn ein mit idi markiert ist
)(vLF ir
)(, vLFyx
truesvl i )),(( )(vLFx
23
O(N) Algorithmus
• Ablauf erster Algorithmus– Für alle v: Initialisierung einen Korrekturwert auf 0
– Durchlaufe alle benachbarten x,y aus I(idi) und addiere jeweils ri in den Korrekturwert von lca(x,y)
– Nun gilt für alle v: Die Summe der Korrekturwerte-Werte des an v hängenden Teilbaums ist (ci(v)-1)ri
– Wiederholt man dies für alle I(idi) ergibt sich als Teilbaumsumme:
)),(())),(()1(( Svlcorrtruesvlrc iii
24
O(N) Algorithmus
• Errechnung von ist nun möglich• Linearzeit Algorithmus:
– Konstante Anzahl von Linearzeit-Durchläufen des Baumes
– Lineare Anzahl von lca-Anfragen in Konstanter Zeit
• ermöglicht Suche nach bestem Muster
))(( vlM ir
))(( vlM ir
25
O(N) Algorithmus
ABC$ 1BCAC# 1CAB* 0
I($)={3,5,7}I(#)={1,6,8,9}I(*)={2,4,10}
4
1
2
1 4
5 6
7 8
9
3
10
A
B
C
C#
C$* $ AC#
B*
B* #
C#
A$C
26
O(N²) Algorithmus
• So gesammelte Information reicht so nicht für 2 Muster, da komplizierte Mengenrelation nötig ist
• Leichte Abwandlung zur Findung von ‹p,F,q› :– wir wählen fixes l(v1) und markiere alle Strings und
korrespondierenden Blätter mit ψ(l(v1,si))
– Wir wenden den Algorithmus von vorher an aber sammeln getrennt für Wert von ψ(l(v1,si))
– Nun haben wir:
))),(()),((( 1)),((bsvltruesvlrr iiibvlM i
27
O(N²) Algorithmus
• Für die Negation gilt:
• Dies ermöglicht die Bestimmung von:
und damit auch:
bvlM iii
iii
rbsvlr
bsvlfalsesvlr
)),((1
1
))),(((
))),(()),(((
},{,;))),(()),((( 21211 falsetruebbbsvlbsvlr iii
)))),((),),(((( 21))(,,(( 21truesvlsvlFrr iiivlFvlM i
28
O(N²) Algorithmus
• Bei fixem l(v1) können wir nun den O(N) Algorithmus nutzen
• Es gibt insgesamt O(N) Kandidaten für diesen Wert
Algorithmus braucht insgesamt O(N²) für die Auswertung von O(N²) möglichen Kandidaten
29
Umsetzung mit Suffix Arrays
• Suffix- + LCP-Array simulieren Baum
30
Umsetzung mit Suffix Arrays
• Suffixarray hat keine internen Knoten• Extraarray C der Länge N als Ersatz
• C[i] entspricht lca von AS[i-1] und AS[i]
• Der Korrekturfaktor für AS[i] und AS[j] wird in C[rmq(i+1,j)] gespeichert
• Bei mehr als zwei Kindern pro internem Knoten entsprechen mehrere C[i] dem selben Knoten, wird beim Auslesen korrigiert
31
Beispiele
• Anwendung zur Auswertung der Degeneration von mRNA in Hefe und Mensch– Zeitunterschiede um bis zu Faktor 100– u.A. beeinflusst durch Proteinbindung in der 3‘UTR
• Algorithmus in C mit POSIX Threads• Sun Fire 15 mit 96 UltraSPARC III Cu 1.2 GHz• Nur Ergebnisse der Form qpqp )()(,)()(
32
Positiv-/Negativ-Mengen, Hefe
• Menge Sf mit 393 schnell degenerierenden Sequenzen (Halbwehrzeit < 10 min)
• Menge Ss mit 379 langsam degenerierenden Sequenzen (Halbwehrzeit > 50 min)
• Alle Sequenzen Länge 100 nt• 46.554 Einzelmuster2.167.274.916
Musterpaare• Berechnungsdauer 3~4 Minuten• Auswertung mit Chi-Quadrat Test
33
Positiv-/Negativ-Mengen, Hefe
fnStnSMfn
tpSfpSMtp
fntnfptnfptpfntp
fnfptntpSSscore
Ss
ff
sf
;),(
;),(
))()()((
)**( 2
34
Positiv-/Negativ-Mengen, Hefe
• Oft UGUA – bekannter Verfall-Promoter
• enthält ⌐AUCC und ⌐ GUUG– vermutete Stabilisatoren
35
Rangbasiert, Mensch
• 2306 mRNA Sequenzen und assoziierte Verfallsraten (hepatozelluläres Karzinom)
• Durchschnittslänge 925,54 nt mit Gesamtlänge 2.134.294 nt
• Unausgeglichene Verteilung daher:Wilcoxon Rang Summen Test– Aufsteigend sortiert und Rang entsprechend Position in
Sortierung
36
Rangbasiert, Mensch
)(;)(
12/)1)((
2/)1((),(
M iryMx
SxS
Sxyyxz
37
Rangbasiert, Mensch
• Enthält auch UGUAUA, wie die Hefe
• A und U reiche Elemente– Bekannt für Deadenylierung Verfall
ENDE
Fragen?
Irgendwas unklar?
39
Quellen
• Hideo Bannai, Heikki Hyyrö , Ayumi Shinohara, Masayuki Takeda, Kenta Nakai, and Satoru Miyano, "Finding Optimal Pairs of Patterns", In Proceedings of the 4th International Workshop on Algorithms in Bioinformatics (WABI 2004), LNBI 3240:450-462, (2004).– http://bonsai.ims.u-tokyo.ac.jp/~bannai/papers/wabi2004.pdf
• [Algorithm Engineering, Uni-Dortmund, WS 05/06– http://ls11-www.cs.uni-dortmund.de/lehre/WiSe0506/ae.jsp ]