Boyer-Moore Algorithmus

Transcrição

Bioinformatik
= 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!
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!
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)
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
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
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
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
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‘, | β |)
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
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
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)
13
Inhalt dieser Vorlesung
•
•
•
•
•
Bad Character und Good Suffix Rule
Preprocessing
Komplexität
Beispiel
14
• 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
15
• 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
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
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 ?
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)
• 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
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)
• 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
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
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
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
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
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)
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!
26
Fall 2
liegende Vorkommen von t in P mit k<n und
S(k-|t|-1) ≠ ‚y‘, sonst 0
• Dann
– 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
liegende Vorkommen von t in P mit k<n und
S(k-|t|-1) ≠ ‚y‘, sonst 0
• Dann
– 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 ...
28
Beispiel
• Bad character worst-case läuft jetzt in linearer Zeit
T
P
aggggggggggg
T
P
T
P
aggggggggggg
aggggggggggg
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)
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
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)
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
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
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)
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
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
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
38
t
Beispiel
b bcggbcba aggbbaacabaabgb a a c g c a b a a b c a b
c abaabgba a
BCR wins
cab aabgbaa
Mit einfacher BCR auch Schieben um 1
GSR wins
cabaabgbaa
cabaabgb a a
GSR wins
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/
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
40

Boyer-Moore Algorithmus

Transcrição

Documentos relacionados

März 11 Kinder

Bioinformatik MSc

Duales Studium bei Fendt Theorie oder Praxis? Beides!

¨Ubungen zu Computergraphik I

Umrüstung Motorola V50 auf Bluetooth SA644 (Limo) - BMW E39

Modul 2: Allgemeine und anorganische Chemie

Physik für Biologen, Chemiker, Biomed. Chemiker und

Expectations vs. Reality Ein kleiner avant

Unser Angebot für Sie... - Schloss Apotheke Ettlingen

7 Normandie, Juli 1944 In der Ferne war das Brummen schwerer