Boyer-Moore Algorithmus
Transcrição
Boyer-Moore Algorithmus
Bioinformatik Boyer-Moore Algorithmus = String Matching in der Praxis Ulf Leser Wissensmanagement in der Bioinformatik Zusammenfassung letzte Vorlesung • Stringalgorithmen in der Bioinformatik – Sequenzieren – Assembly • Verschärftes Superstring-Problem • Shotgun Sequenzierung - >107 einzelne Reads – EST Clustering • Zusammenfassung von cDNAs zu Clustern – und damit Genen • Humanes Genom - >5*106 cDNAs – Funktionale Annotation • Von Sequenzähnlichkeit zur Funktionsgleichheit • Comparative Genomics • Suche in Genbank - >109 Basenpaare Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 2 Problemdimension: Whole Genome Shotgun • Zerbrechen von kompletten Genomen in Stücke 1KB-100KB • Alle Stücke (an-) sequenzieren • Celera: – Homo sap.: Genom: 3 GB, 28.000.000 Reads – Drosophila: Genom: 120 MB, 3.200.000 Reads ¾ Schnelle Algorithmen notwendig! Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 3 Problemdimension: UniGene • Heuristisches, mehrphasiges Verfahren • Clustern aller cDNA und EST in Genbank – Größenordnung n >1.000.000 Sequenzen, Länge 3004.000 Bp – Vergleiche: O(n2) (All-against-all) • Wöchentliche Aktualisierung • Ergebnis 4/2003 – 110.000 Cluster – Sequenzen pro Cluster: Von 1 (40.000) bis 30.000 (wenige) ¾ Schnelle Stringvergleichalgorithmen notwendig! Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 4 Standardvorgehen • Gegeben: Eine neue Sequenz (Genom) • Annotationspipeline basierend auf bereits annotiertem Genom – – – – Suche nach ähnlichen Gensequenzen Suche nach ähnlichen Promotersequenzen Suche nach ähnlichen Proteinen (Übersetzung- Rückübersetzung) Suche nach neuen Genen durch Programme (trainiert auf bekannten Gensequenzen) – Suche nach ähnlichen Proteindomänen durch Programme (trainiert auf bekannten Proteindomänen) – ... • Alternative: Experimentelle Überprüfung – Teuer, auch nicht fehlerfrei – Ethische / technische Machbarkeit (Knock-Out, Yeast2Hybrid) Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 5 Naiver Algorithmus • Exaktes Matching: P in T • Naiver Algorithmus – Beginnt Vergleich von P an jedem Zeichen von T – Komplexität O(m*n) T P ctgagatcgcgta gagatc gagatc gagatc gagatc gagatc gatatc gatatc gatatc Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 6 Z-Algorithmus: Preprocessing • Im Folgenden: S statt P (Gusfield) • Definition – Sei i>1. Dann ist Zi(S) die Länge des größten Substrings x von S mit • x=S[i..i+|x|] • S[i..i+|x|] = S[1..|x|] (x startet an Position i in S) (x ist auch Präfix von S) – x heißt Z-Box von S an Position i mit Länge Zi(S) Zi S x x Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 7 Vorarbeiten • Definition – Sei i > 1. Dann ist: • ri der maximale Endpunkt aller Z-Boxen, die bei oder vor i beginnen • li ist die Startposition der Z-Box, die bei ri endet • Sprich: S[li..ri] ist die Z-Box, die Position i von S enthält und am weitesten nach rechts reicht Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 8 Lineare Berechnung der Zi Werte • Trick – Verwenden von bereits berechneten Zi zur Berechnung von Zk (k > i) – Lineares Durchlaufen des Strings – Kontinuierliches Vorhalten der Werte l=li-1 und r=ri-1 – Größe der Z-Box an Position i ergibt sich mit konstantem Aufwand • Induktive Erklärung – Beginne mit i=2. Berechne Z2. Wenn Z2> 0, setze r=r2 und l=l2, sonst r=l=0 – Nun stehen wir an Position k>2 und wissen r, l und alle Zj, j<k Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 9 Z-Algorithmus 1 • Annahme 1: k > r – D.h., dass es keine Z-Box gibt, die k enthält – Dann tappen wir weiter im Dunkeln • Berechne Zk durch Matching • Wenn Zk>0, setze r=rk und l=lk Zk‘ • Annahme 2: k <= r – Die Situation: – Also • • • • Z-Box Zl ist Präfix von S Substring β=S[k..r] kommt auch an Pos k‘=k-l+1 von S vor Was wissen wir über diesen Substring? Natürlich: Zk‘ D.h., dass S[k.. ] ist Präfix von S mit mindestens Länge min(Zk‘, | β |) Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 10 Z-Algorithmus 2 • Fallunterscheidung – Zk‘ < |β|: Dann ist das Zeichen an k‘+Zk‘ ein Mismatch bei der Präfixverlängerung. Dann ist das Zeichen S(k+Zk‘) der gleiche Mismatch. Also Zk=Zk‘; r und l unverändert Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 11 Z-Algorithmus 3 – Zk‘ ≥ |β|: Dann ist β ein Präfix von S • ... dass sich vielleicht sogar verlängern lässt • ... denn i.A. ist S(k‘+Zk‘+1) ≠ S(r+1) = S(k+|β|+1) • ... und S(|β|+1) ist noch nicht mit S(r+1) gematched worden Matche Substring S[r+1.. ?] mit S[|β|+1.. ?] Sei der erste Mismatch an Position q Dann: Zk=q-k; l=k; r=q-1 q Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 12 Linearer Stringmatching Algorithmus • Z-Boxen lassen sich in O(|S|) berechnen • Verwendung der Z-Boxen für String Matching S := P||‘$‘||T; // ($ ∉ Σ) Berechne Z-Boxen von S; for i = |P|+2 to |S| if (Zi(S)=|P|) then print Zi(S); // P in T at position i end if; end if; • Komplexität – Schleife wird m-Mal durchlaufen => O(m) Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 13 Inhalt dieser Vorlesung • • • • • Boyer-Moore Algorithmus Bad Character und Good Suffix Rule Preprocessing Komplexität Beispiel Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 14 Boyer-Moore Algorithmus • R.S. Boyer /J.S. Moore. „A Fast String Searching Algorithm“, Communications of the ACM, 1977 • Darstellung hier nach Gusfield, Kap. 2 • Grundidee – Alignierung der Strings wie in naivem Algorithmus – Matching von rechts nach links – Überspringen von Zeichen in T, wo immer möglich Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 15 Boyer-Moore Algorithmus • Vorweg – Worst-Case des Originalalgorithmus ist O(n*m) – Verbesserungen zu O(m) bekannt • Aber: Average-Case sublinear durch Sprünge – „Normaler“ Text (grosses Alphabet, keine zufällige Verteilung) erlaubt große Sprünge – Vergleich Z-Alg: Ist nie sublinear, da m-n Zeichen von T angefasst wird – Boyer-Moore Methode der Wahl für normalen Text • Viele Texteditoren implementieren Boyer-Moore Varianten – Boyer-Moore gut für Proteine, nicht gut für DNA Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 16 Algorithmus Gerüst 1. 2. Anordnung der Strings P und T Matchen von rechts nach links 3. 4. 3. Bei Mismatch oder Match für ganz P 6. 7. 8. Erster Vergleich ist T(n):P(n) Dann T(n-1):P(n-1), T(n-2):P(n-2), ... T(1):P(1) P um X Zeichen nach rechts verschieben Gehe zu 2 Bei Match 9. Weiter matchen nach links 10. Gehe zu 2 • • Das ist noch langweilig Wann kann man P um mehr als 1 Schritt nach rechts schieben? ¾ ¾ Bad Character Rule Good Suffix Rule Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 17 Bad Character Rule • Beobachtung – Wir befinden uns im Algorithmus und haben P(n) mit T(k) aligniert; k≥n – Sei der erste Mismatch an Position n-i von P – Sei x das Zeichen an Position k-i in T – Welches sind Kandidaten für einen Match mit x in P? • Fall1: x kommt in P nicht vor – verschiebe P um n-i Zeichen T P xabxkabzzabxzzbzzb abzxyabzz T P xabxkabzzabxzzbzzb abzxyabzz Wie weit können wir jetzt schieben ? Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 18 Bad Character Rule 2 • Beobachtung – – – – Wir befinden uns im Algorithmus und haben P(n) mit T(k) aligniert Sei der erste Mismatch an Position n-i von P Sei x das Zeichen an Position k-i in T Sei l das letzte Vorkommen von x in P (also das am weitesten rechts liegende) – Welches sind Kandidaten für einen Match mit x in P? • Fall1: x kommt in P nicht vor – verschiebe P um n Zeichen • Fall2: l<i. Also kommt x in P nur vor i vor – verschiebe P um i-l Zeichen T P xabxkabzzabxzzbzzb abzxyabzz T P xabxkabzzabxzzbzzb abzxyabzz Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 19 Bad Character Rule 3 • Beobachtung – – – – Wir befinden uns im Algorithmus und haben P(n) mit T(k) aligniert Sei der erste Mismatch an Position n-i von P Sei x das Zeichen an Position k-i in T Sei l das letzte Vorkommen von x in P (also das am weitesten rechts liegende) – Welches sind Kandidaten für einen Match mit x in P? • Fall1: x kommt in P nicht vor – verschiebe P um n Zeichen • Fall2: l<i. Also kommt x in P nur vor i vor – verschiebe P um i-l Zeichen • Fall3: l>i. Das nützt uns (erst mal) nichts T P xabxkabzzabxzzbzzb abzxyabzz z gibt es rechts von i kann man mix machen Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 20 Zusammengenommen • Definition: Gegeben ein Pattern P. Dann sei R(x), x∈Σ : – 0, wenn x∉P – Sonst: Position des am weitesten rechts liegenden Auftreten von x in P • Berechnung leicht in O(n) möglich • Dann – Sei i die Position des ersten Mismatch; sei x das Zeichen in T an der entsprechenden Position – Verschiebe P um max(1, i - R(x)) • Problem: Bei kleinem Alphabet (DNA!) wird es i.d.R. immer Auftreten rechts von i geben Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 21 Extended Bad Character Rule • Beobachtung – Die „x“ rechts von i sind uninteressant – hier wurde schon geprüft – Also: Verschiebe zum nächsten, links von i liegenden x T P xabxkabzzabxzzbzzb abzxyabzz T P Xabxkabzzabxzzbzzb... abzxyabzz • Benötigt Berechnung der relativen Positionen • Array [n,|Σ|] => linearer Lookup, aber Platzverbrauch O(n*|Σ|) • Listen für jedes Zeichen mit Positionen; linearer Platz O(n), aber nicht-linearer Lookup (Binsearch in Liste) • Teuer als Berechnung bei einfacher Bad Character Rule – anwendungsabhängige Entscheidung Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 22 Bad Character Rule Zusammenfassung • Macht keine Fehler • Billig und sehr wirksam bei größeren Alphabeten (natürliche Sprache) • Keine Reduktion der Komplexität T P ggggggggggggggggggggggggggggggggggggggggg aggggggggggg aggggggggggg aggggggggggg aggggggggggg Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 23 Good-Suffix Rule • Zweite Regel zum Verschieben • Unabhängig von / Komplementär zur Bad Character Rule • Grundidee – Bad Character Rule sucht nach dem ersten Mismatch – Bis dahin haben wir aber schon einen (evt. längeren) Match gefunden – Wo ist dieser Match noch in P enthalten ? ¾ Preprocessing von P erforderlich Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 24 Good-Suffix Rule 2 T P x t y t • Substring t war ein Match, Zeichen x/y ein Mismatch • Dann können wir wie folgt verschieben – Wenn t noch mal in P vorkommt, dann verschiebe bis zum am weitesten rechts liegenden t in P – Wenn t nicht mehr in P vorkommt, dann aligniere Präfix von P mit Suffix von t (in T) – Wenn t=P, dann aligniere echtes Präfix von P mit Suffix von t (in T) Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 25 Fall 1 • Sei k das rechte Ende des weitesten rechts liegenden Vorkommen von t in P mit k<n und S(k-|t|-1) ≠ ‚y‘, sonst 0 • Dann – k≠0: Verschiebe P um n-k T P t‘ x t x t y t ≠y t‘ y t • Warum fordern wir nicht S(k-|t|-1)=‚x‘ ? • Zum Zeitpunkt des Preprocessing von P ist x nicht bekannt! Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 26 Fall 2 • Sei k das rechte Ende des weitesten rechts liegende Vorkommen von t in P mit k<n und S(k-|t|-1) ≠ ‚y‘, sonst 0 • Dann – k≠0: Verschiebe P um n-k – k=0 und P≠t: Verschiebe P um n-|t|+1 T x t P y t x t t y • Man kann geringfügig weiter verschieben • ... soweit, bis Präfix von P mit Suffix von t macht • Ist im voraus berechenbar: Präfix und Suffix von P • UlfSpäter mehr Vorlesung, Wintersemester 2003/2004 Leser: Bioinformatik, 27 Fall 3 • Sei k das rechte Ende des weitesten rechts liegende Vorkommen von t in P mit k<n und S(k-|t|-1) ≠ ‚y‘, sonst 0 • Dann – k≠0: Verschiebe P um n-k – k=0 und P ≠t: Verschiebe P um n-|t|+1 – k=0 und P =t: Verschiebe P um 1 T P x t t x t t • Bzw. geringfügig weiter ... Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 28 Beispiel • Bad character worst-case läuft jetzt in linearer Zeit T P ggggggggggggggggggggggggggggggggggggggggg aggggggggggg T P ggggggggggggggggggggggggggggggggggggggggg T P ggggggggggggggggggggggggggggggggggggggggg aggggggggggg aggggggggggg Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 29 Preprocessing • Woher wissen wir, wo und ob t in P noch vorkommt? • Gesucht: Zu jedem Suffix (t=S[i..n]) von P den am weitesten rechts liegenden Endpunkt (L‘(i)) eines identischen Teilstrings von P • Definition: L‘(i) zu einem Index i von P ist der Wert mit: – – – – Bedingung 1: P[L‘(i)-|t| .. L‘(i)] = P[i..n] Bedingung 2: L‘(i) < i Bedingung 3: P[L‘(i)-|t|-1) ≠ P(i-1) (Strong good suffix) L‘(i) = 0, falls kein solcher Teilstring existiert P t‘‘ t‘ L‘(i) Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 t i n 30 Anders gesagt • Gesucht: Zu jedem Suffix von P suchen wir den nächsten (von rechts nach links) identischen Substring von P • Erinnerung Z-Boxen: ...zu jedem Präfix von P den nächsten (von links nach rechts) identischen Substring von P ¾ Das Boxer-Moore Preprocessing ist also (fast) ein „invertiertes“ Z-Box Preprocessing Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 31 Zwischenschritt • Definition N(j) für Index j von P ist die Länge des längsten Suffix von P[1..j], das auch Suffix von P ist • Beispiel dcabcabdabdab N(j)=0002002005000 • Berechnung der N(j) Werte – N(j) symmetrisch zu Zi Werten des Z-Box Algorithmus – Berechnung durch Z-Box Algorithmus auf umgedrehtem P (=Pr) Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 32 Ableitung von L‘(i) aus N(j) • N(j) Werten geben die Länge von längsten Suffixen an, die links von j in P vorkommen • L‘(i) sucht das am weitesten rechts liegende Auftreten von Suffixen der Länge n-i+1 – i gibt die Länge des Suffixes vor – Suffix darf sich nicht verlängern lassen • Damit ist L‘(i) der größte Wert j mit N(j)=n-i+1 – Alle Positionen mit N(j)=n-i+1 stehen für (längste) Suffix der gewünschten Länge – Davon interessiert uns das am weitesten rechts liegende, also für das größte j Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 33 Beispiel 1234567890123 dcabcabdabdab N(j)=0002002005000 • Suchen wir den Wert L‘(12) – Also längste Suffixe „ab“, Länge 2 – Zeichen vor diesem „ab“ darf nicht „d“ sein – Das sind alle Positionen j mit N(j)=2 • Denn dort liegt ein längstes Suffix der Länge 2 – Davon das „rechteste“ ist unser Treffer – Also: L‘(12) = 7 Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 34 Zusammen: Preprocessing • Gegeben: P • Berechne N-Werte durch Z-Box auf Pr • Bereche L‘-Werte durch for i=1 to n L‘(i):= 0; for j=1 to n-1 i := n-N(j)+1; L‘(i) := j; end for; • Komplexität: O(n) – Z-Box ist O(n) – L‘-Werte ist O(n) Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 35 Boyer-Moore compute L‘(i); compute R(x) for each x∈Σ; k := n; while (k<m) do align P with T with right end k; match P and T from right to left until mismatch: Compute shift x using BCR and R(x); Compute shift y using GSR and L‘(i); k := k+ max(x,y); P matched: print k; k := k + 1; end while; • Algorithmus hat Worst-Case O(m*n) • Erweiterungen zu O(m) bekannt • Praxis: Sublinear Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 36 Ist die Richtung wichtig? • Warum vergleicht Boyer-Moore immer von rechts nach links? – Heuristik zu Beschleunigung – Frühe Mismatches können große Sprünge hervorrufen x ab xxxxxx y ab x ab xxxxxx y ab – Preis: Späte Mismatches machen nur kurze Sprünge – Umgedrehte Situation zu links-rechts Vergleichen Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 37 Letzter Hinweis • Was hieß „...geringfügig besser möglich ...“ ? • Wenn t in P nicht mehr vorkommt – Verschiebe P um n-|t|+1 x t y t x t y • Man kann geringfügig weiter verschieben • ... soweit, bis Präfix von P mit Suffix t von P matched • Ist im voraus berechenbar: Präfix und Suffix von P • Siehe Gusfield, l‘(i)-Werte Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 38 t Beispiel b bcggbcba aggbbaacabaabgb a a c g c a b a a b c a b c abaabgba a b bcggbcba aggbbaacabaabgb a a c g c a b a a b c a b BCR wins cab aabgbaa Mit einfacher BCR auch Schieben um 1 b bcggbcba aggbbaacabaabgb a a c g c a b a a b c a b GSR wins cabaabgbaa b bcggbcba aggbbaacabaabgb a a c g c a b a a b c a b cabaabgb a a GSR wins b bcggbcba aggbbaacabaabgb a a c g c a b a a b c a b Match Mismatch Good suffix Mit /ohne l‘ c a b a a b g b a a cabaabg b a a Ext. Bad character Good suffix/ Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 Bad character 39 Zusammenfassung • Mit einigen Änderungen garantiert lineare (und meist sublineare) Laufzeit – Komplizierter Beweis – Literatur • Praxistauglichster Exakt-String-Matching Algorithmus für viele Arten von Text • Baut auf Z-Box Preprocessing auf • Als nächstes: Knuth-Morris-Pratt – Lineares String Matching – Erweiterbar auf mehrere Pattern Ulf Leser: Bioinformatik, Vorlesung, Wintersemester 2003/2004 40