Algorithmen auf Sequenzen - ls11- · einer Sequenz. Entdecken von wiederholten Teilsequenzen (n utzlich f ur Genomanalyse, Kompression). Entwicklung von Codes zur fehlertoleranten

Algorithmen auf Sequenzen

Dipl.-Inform. Tobias MarschallProf. Dr. Sven Rahmann

LS 11, Fakultat fur Informatik, TU Dortmund

Wintersemester 2009/10Entwurf vom 5. Februar 2010

Inhaltsverzeichnis

1 Motivation 11.1 Probleme in der Sequenzanalyse . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Nutzliche Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.3 Grundlegende Definitionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3.1 Beispiele fur Alphabete . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Pattern-Matching 52.1 Das Pattern-Matching-Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Der Knuth-Morris-Pratt-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . 6

2.2.1 Laufzeitanalyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.3 DFA-Basiertes Pattern Matching . . . . . . . . . . . . . . . . . . . . . . . . . 82.4 Boyer-Moore-Horspool / Sunday . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.4.1 Horspool-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.4.2 Sunday-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.5 Patterns aus mehreren Strings - Aho-Corasick . . . . . . . . . . . . . . . . . . 142.6 Nichtdeterministische Automaten . . . . . . . . . . . . . . . . . . . . . . . . . 172.7 Bit-parallele Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.8 Zahlweisen von Matches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.9 Teilstring-basierte Ansatze: BDM, BNDM, BOM . . . . . . . . . . . . . . . . 21

2.9.1 Backward Dawg Matching (BDM) . . . . . . . . . . . . . . . . . . . . 222.9.2 Backward Nondeterministic Dawg Matching (BNDM) . . . . . . . . . 232.9.3 Suffix-Orakel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.10 Auswahl eines geeigneten Algorithmus in der Praxis . . . . . . . . . . . . . . 26

3 Bit-parallele Algorithmen 273.1 Approximative Matching mit NFAs . . . . . . . . . . . . . . . . . . . . . . . . 28

3.1.1 Bit-parallele Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . 283.1.2 Verallgemeinerung: ”Gaps“ beschrankter Lange . . . . . . . . . . . . . 29

3.2 Alternative: BNDM verallgemeinern . . . . . . . . . . . . . . . . . . . . . . . 31

i

Inhaltsverzeichnis

3.3 Alternative Implementierung des k-Fehler-NFA . . . . . . . . . . . . . . . . . 323.4 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4 DP-Algorithmen zum approximativen String-Matching und Sequenzalignment 354.1 Globales Alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.2 Visualisierung des Alignments . . . . . . . . . . . . . . . . . . . . . . . . . . . 364.3 Anzahl globaler Alignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374.4 Alignment-Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.4.1 Ein universeller Alignment-Algorithmus . . . . . . . . . . . . . . . . . 394.5 Suche eines Musters P in einem Text t . . . . . . . . . . . . . . . . . . . . . . 394.6 ”Free End Gaps“-Alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.6.1 Lokales Alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424.7 Allgemeine Gapkosten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.7.1 Algorithmus zum globalen Alignment mit affinen Gapkosten . . . . . . 434.8 Alignments mit Einschrankungen / suboptimale Alignments . . . . . . . . . . 444.9 Globales Alignment mit linearem Platzbedarf . . . . . . . . . . . . . . . . . . 44

4.9.1 Lokales Alignment mit linearem Platzbedarf . . . . . . . . . . . . . . . 454.10 Probleme des lokalen Alignments . . . . . . . . . . . . . . . . . . . . . . . . . 464.11 Four-Russians-Trick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5 Hidden-Markov-Modelle (HMMs) 495.1 Viterbi-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505.2 Verweildauer in Zustanden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

6 Indexstrukturen 556.1 Suffixbaume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

6.1.1 Konstruktion in Linearzeit: Ukkonens Algorithmus . . . . . . . . . . . 566.2 Suffixarrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

7 Statistik der Mustersuche in Sequenzen 617.1 Textmodelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 617.2 Parameterschatzung fur Textmodelle . . . . . . . . . . . . . . . . . . . . . . . 647.3 Momente der Anzahl der Treffer . . . . . . . . . . . . . . . . . . . . . . . . . 66

7.3.1 Erwartete Anzahl Treffer . . . . . . . . . . . . . . . . . . . . . . . . . 667.4 Die Verteilung der Anzahl der Treffer . . . . . . . . . . . . . . . . . . . . . . . 667.5 Analyse des Horspool-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . 70

8 Exkurse 738.1 Erzeugende Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 738.2 Anwendung von erzeugenden Funktionen auf PAAs . . . . . . . . . . . . . . . 768.3 Compound-Poisson-Approximation . . . . . . . . . . . . . . . . . . . . . . . . 78

8.3.1 Der Poisson-Prozess der Clumps . . . . . . . . . . . . . . . . . . . . . 788.3.2 Berechnung der Verteilung der Clumpgroße Ψ . . . . . . . . . . . . . . 798.3.3 Eine untere Schranke fur den p-Wert . . . . . . . . . . . . . . . . . . . 80

9 Weitere Planungen 83

A Molekularbiologische Grundlagen 85A.1 Desoxyribonukleinsaure (DNA) . . . . . . . . . . . . . . . . . . . . . . . . . . 85

ii

Inhaltsverzeichnis

A.2 Ribonukleinsaure (RNA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87A.3 Proteine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88A.4 Das zentrale Dogma der Molekularbiologie . . . . . . . . . . . . . . . . . . . . 90A.5 Genregulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91A.6 Experimentelle Techniken zur DNA-Bearbeitung . . . . . . . . . . . . . . . . 91

A.6.1 Kopieren mit PCR (polymerase chain reaction, Polymerasekettenre-aktion) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

A.6.2 Kopieren durch Klonierung in Vektoren . . . . . . . . . . . . . . . . . 91A.6.3 Cut+Paste mit Restriktionsenzymen . . . . . . . . . . . . . . . . . . . 91A.6.4 Langenbestimmung mit Gel-Elektrophorese . . . . . . . . . . . . . . . 92A.6.5 Test auf Prasenz eines DNA-Abschnitts . . . . . . . . . . . . . . . . . 92

Literaturverzeichnis 93

iii

Inhaltsverzeichnis

iv

KAPITEL 1

Motivation

In der Sequenzanalyse beschaftigen wir uns mit der Analyse von sequenziellen Daten, alsoFolgen von Symbolen. Sequenzen sind ”eindimensional“ und daher einfach darzustellen undzu analysieren. Schwieriger sind z.B. Probleme auf Graphen. Viele Informationen lassen sichjedoch in Form von Sequenzen darstellen (serialisieren). Einige Beispiele:

• Biosequenzen (DNA, RNA, Proteine). Aber: Genome sind komplexer als nur eine DNA-Sequenz; d.h. die Darstellung eines Genoms als Zeichenkette stellt eine vereinfachendeModellannahme dar.

• Texte (Literatur, wissenschaftliche Texte). Die Kunst hinter guter Literatur und hinterguten wissenschaftlichen Arbeiten besteht darin, schwierige, komplex zusammenhangendeSachverhalte in eine logische Abfolge von einzelnen Satzen zu bringen.

• Quelltexte von Programme

• Dateien, Datenstrome. Komplexe Datenstrukturen werden serialisiert, um sie persi-stent zu machen.

• Zeitreihen, Spektren. (Audiosignale, Massenspektren, ...)

1.1 Probleme in der Sequenzanalyse

Die Sequenzanalyse umfasst (unter anderem) folgende Probleme:

• Mustersuche: Wir suchen in einer vorgegebenen Sequenz ein bestimmtes Muster, z.B.einen regularen Ausdruck. Beispiel: ”suchen“-Funktion in Textverarbeitungsprogram-men. Mustersuche kann exakt oder approximativ erfolgen. Bei der approximativen Su-che sollen nicht nur exakt passende sondern auch ahnliche Muster gefunden werden(z.B. Meier statt Mayer).

1

1 Motivation

• Sequenzvergleich: Ermitteln und Quantifizieren von Gemeinsamkeiten und Unterschie-den verschiedener gegebener Texte. Dies ist eine wichtige Anwendung im Kontext bio-logischer Sequenzen, aber auch im Bereich der Revisionskontrolle (CVS, Subversion).

• Kompression: Wie kann eine gegebene Symbolfolge moglichst platzsparend gespeichertwerden? Je mehr Struktur bzw. Wiederholungen in einer Sequenz vorkommen, destobesser kann man sie komprimieren. Dies liefert implizit ein Maß fuer die Komplexitateiner Sequenz.

• Entdecken von wiederholten Teilsequenzen (nutzlich fur Genomanalyse, Kompression).

• Entwicklung von Codes zur fehlertoleranten Ubertragung von sequenzieller Informati-on.

1.2 Nutzliche Literatur

Folgende Bucher konnen beim Erarbeiten des in diesem Skript enthaltenen Stoff nutzlichsein:

• Navarro and Raffinot, Flexible Pattern Matching in Strings

• Gusfield, Algorithms on Strings, Trees and Sequences: Computer Science and Compu-tational Biology

• Sankoff and Kruskal, Time Warps, String Edits, and Macromolecules: The Theory andPractice of Sequence Comparison

• Durbin, Eddy, Krogh, and Mitchison, Biological Sequence Analysis: Probabilistic Mo-dels of Proteins and Nucleic Acids

Die genauen Quellenangaben finde sich im Literaturverzeichnis.

1.3 Grundlegende Definitionen

Wir wollen notige Grundbegriffe nun etwas formaler einfuhren.

Definition 1.1 (Alphabet). Ein Alphabet ist eine (endliche oder unendliche) Menge.

Wir befassen uns in der Regel mit endlichen Alphabeten, die wir normalerweise mit Σ oderA bezeichnen.

Definition 1.2 (Indexmenge). Eine Indexmenge ist eine endliche oder abzahlbar unendlichelinear geordnete Menge.

Wir bezeichnen Indexmengen mit I. Beispiele fur Indexmengen sind N, Z und 1, . . . , N.Nun konnen wir eine Sequenz als mathematische Funktion s : I → A oder als Tupel s ∈ AIauffassen.

Je nach Kontext findet man verschiedene Bezeichnungen fur Elemente der Menge An =A1,...,n, zum Beispiel Worter, Tupel, Strings, Sequenzen der Lange n oder n-Gramme uberA. Wir definieren A+ :=

⋃n≥1A

n und A∗ :=⋃n≥0A

n, wobei A0 = ε und ε den leeren

2

1.3 Grundlegende Definitionen

String bezeichnet. ε ist der einzige String der Lange 0. Sei nun s ∈ A∗ ein String. Wir be-zeichnen mit s[i] den Buchstaben, der in s an der Stelle i steht. Dabei muss i ∈ I sein. Wirschreiben s[i . . . j] um den Teilstring von i bis j (einschließlich) zu benennen. Falls i > j,ist per Definition s[i . . . j] = ε. Eine Teilsequenz von s ist definieren wir als (si)i∈I mitI ⊂ I. Eine Teilsequenz ist im Gegensatz zum Teilstring also nicht notwendigerweise zusam-menhangend. Die Begriffe Teilstring und Teilsequenze sind daher also auseinanderzuhalten.

Beispiel 1.1 (Sequenz). s = AGGTC ist eine Sequenz mit A = A, C, G, T (DNA-Alphabet),I = 1, 2, 3, 4, 5 in der ublichen Ordnung. Z.B. bildet s die 3 auf G ab, s[3] = G. ♥

Beispiel 1.2 (Darstellung einer Sequenz in JAVA). In der Programmiersprache JAVAkonnen Sequenzen auf unterschiedliche Arten reprasentiert werden, zum Beispiel als String(wenn A ⊂ Unicode) oder A[] oder ArrayList<A> oder Map<I,A>. ♥

Normalerweise befassen wir uns mit endlichen Sequenzen; dann ist I = 0, . . . , N furN ∈ N.Das heißt insbesondere, dass wir in diesem Skript bei 0 (und nicht bei 1) anfangen die Buch-staben zu indizieren. Weiter definieren wir s[. . . i] := s[0 . . . i] und s[i . . .] := s[i . . . |s| − 1]und bezeichnen solche Teilstrings als Prafix beziehungsweise Suffix von s. Wenn t ein Prafix(Suffix) von s ist und t 6= ε und t 6= s, dann bezeichnen wir t als echtes Prafix (Suffix) von s.Ferner definieren wir die Menge aller Prafix/Suffixe von s durch

Prefixes(s) := s[. . . i] fur − 1 ≤ i < |s|

undSuffixes(s) := s[i . . .] fur 0 ≤ i ≤ |s| .

Fur eine Menge von Wortern S ⊂ Σ∗ definieren wir

Prefixes(S) :=⋃s∈S

Prefixes(s)

bzw.Suffixes(S) :=

⋃s∈S

Suffixes(s) .

1.3.1 Beispiele fur Alphabete

Sequenztyp Alphabet ADNA-Sequenz A,C,G, TProtein-Sequenz 20 Standard-AminosaurenC-Programme ASCII-Zeichen (7-bit)Java-Programme Unicode-ZeichenAudiosignal (16-bit samples) 0, . . . , 216 − 1Massenspektrum Intervall [0, 1] (unendlich) oder Double

3

1 Motivation

4

KAPITEL 2

Pattern-Matching

2.1 Das Pattern-Matching-Problem

Gegeben: Alphabet A, Text T ∈ An, Pattern/Muster P ∈ Am. Das Muster ist also eineinfacher String (Spater: andere Muster!). Ublicherweise ist m n.

Gesucht (3 Varianten):

1. Entscheidung: Ist P ein Teilstring von T?

2. Anzahl: Wie oft kommt P als Teilstring von T vor?

3. Aufzahlung: An welchen Positionen (Start- oder Endposition) kommt P in T vor?

Algorithmen, die eine dieser Fragen beantworten, lassen sich oft auf einfache Weise so mo-difizieren, dass sie auch die anderen beiden Fragen beantworten. Zunachst behandeln wireinen sehr einfachen (naiven) Algorithmus, zur Losung von Variante 2 des Pattern-Matching-Problems:

1 def simplePatternCountNaive(P,T):2 m = len(P)3 n = len(T)4 count = 05 for i in range(n-m+1):6 if T[i:i+m]==P:7 count += 18 return count

Diese Algorithmus benotigt O(n ·m) Zeit (worst-case). Im Durchschnitt (average-case) istdieser Algorithmus evtl. (je nach Alphabetgroße) garnicht so schlecht, weil in Zeile 6 imSchnitt sehr schnell ein nicht passendes Zeichen (Mismatch) gefunden wird.

5

2 Pattern-Matching

Iteration 0:Iteration 1:Iteration 2:Iteration 3:...

Abbildung 2.1: Naiver Algorithmus zum Pattern-Matching: Das Pattern (rot) wird in jederIteration mit einem Substring des Textes (blau) verglichen und nach jedemVergleich um eine Position nach rechts verschoben.

Offensichtlich hat der (theoretisch) bestmogliche Algorithmus eine Laufzeit von Ω(n + m),denn jeder Algorithmus muss mindestens den Text (in Ω(n)) und das Pattern (in Ω(m))einmal lesen. Wir wollen uns nun einem in diesem Sinne optimalen Algorithmus mit einerLaufzeit von Θ(n+m) zuwenden.

2.2 Der Knuth-Morris-Pratt-Algorithmus

Wir werden nun einen Algorithmus mit Laufzeit Θ(n + m) behandeln (Knuth, Morris, andPratt, 1977).

Der naive Algoritmus vergleicht viele Textzeichen mehrfach, viele sogar m-mal. Es werdenalso Informationen, die aus dem jeweils ersten Vergleich gewonnen wurden nicht optimalgenutzt. Wir konnen den Algorithmus verbessern, indem wir uns Informationen uber bereitsgelesene Zeichen geschickt ”merken“. Dadurch wird eine langere Verschiebungen des Patternsmoglich.

Beispiel 2.1 (Mogliche Verschiebung). Die ersten 5 Zeichen von P passen; daher sind dieentsprechenden 5 Textzeichen bekannt. Fur das Pattern P ist eine Verschiebung um einZeichen ware nutzlos, denn wir wissen schon, dass z.B. an Position 5 im Text ein b steht,was nicht zu P [0] = a passt. Ein neuer Match kann also fruhestens bei einer Verschiebungum 2 Zeichen entstehen.

012345678901234 012345678901234T bacbababaabcbab bacbababaabcbab

|||||x |||?P ababaca ababaca

0123456 0123456

Entscheidende Frage: Welches ist das langste Prafix von P , das ein echtes Suffix des mat-chenden Teils von P (ababa) ist? Hier: aba. ♥

Angenommen P kommt an Position i vor; d.h. ein Match von P in T endet an der Position i,oder mit anderen Worten T [i− |P |+ 1 . . . i] = P . Wir wollen nun eine Verschiebung 0 <k ≤ |P | betrachten. An der Position i + k kann das Pattern nur dann vorkommen, wenn

6

2.2 Der Knuth-Morris-Pratt-Algorithmus

T [i− k + 1 . . . i] = P [. . . k − 1]. Deshalb brauche wir Verschiebungen, bei denen das nicht derFall ist garnicht zu betrachten. Die Idee des KMP-Algorithmus ist nun, immer das kleinstek mit dieser Eigenschaft zu betrachten. Auf diese Weise konnen wir uns sicher sein, keineMatches zu ubersehen. Daher definieren wir:

Definition 2.1 (LPS). Wir definieren die Funktion lps folgendermaßen:

lps(q) := max|p| : p ist Prafix von P, p ist Suffix von P [. . . q] und |p| < q + 1

Mit anderen Worten ist lps(q) die Lange des langsten Prafix von P , das ein echtes Suffix vonP0 . . . Pq ist. Diese Definition ist die zentrale Definition des KMP-Algorithmus. Wir wollensie uns an einem Beispiel vergegenwartigen.

Beispiel 2.2 (LPS). 0 1 2 3 4 5 6P a b a b a c alps 0 0 1 2 3 0 1

In der obersten Zeile steht der Index der Position, darunter das Pattern P und darunter derWert von lps an dieser Stelle. ♥

Damit ergibt sich der folgende Algorithmus: Jedes Textzeichen wird genau einmal gelesen.Wir merken uns in der Variablen q die Lange des langsten Prafix von P , das mit einemSuffix des bisher gelesenen Textes ubereinstimmt; am Anfang ist das 0. Stimmt das nachstegelesene Zeichen in T nicht mit dem nachsten in P benotigten Zeichen P [q] uberein, dannverkurzen wir (wenn q nicht sowieso null ist) q auf lps(q − 1) und wiederholen den Test.Stimmt das nachste gelesene Zeichen jetzt mit P [q] uberein, erhohen wir q um 1. Haben wirdas komplette Muster gefunden (q = |P |), notieren wir die Endposition des Matches und furden nachsten Schritt q.

1 def KMP(P,T,lps):2 q = 03 for i in range(len(T)):4 while q==len(P) or (q>0 and P[q] != T[i]):5 q = lps[q-1]6 if P[q] == T[i]: q += 17 # Invariante (I) trifft an dieser Stelle zu.8 if q == len(P): yield i

Bemerkung 2.1 (yield in Python). Der Befehl yield kann in Python dazu verwendetwerden um aus einer Funktion eine Folge von Werten zuruckzugeben. Ein Aufruf von yieldliefert einen Wert zuruck ohne die Funktion zu beenden. Eine Funktion, die von yieldGebrauch macht, nennt man Generator. Man kann einen Generator in einer for -Schleifeverwenden und so uber alle zuruckgelieferten Werte iterieren:

1 for s in KMP(P,T,lps):2 print s

Das obige Code-Fragment gibt zum Beispiel alle Positionen aus, die vom KMP-Algorithmuszuruckgeliefert werden.

7

2 Pattern-Matching

Um die Korrektheit zu zeigen, mussen wir prufen, dass q tatsachlich nach jedem Schlei-fendurchlauf die Lange des langsten Suffixes des bisher gelesenen Textes ist, das ein Prafixunseres Patterns P ist. Formal ausgedruckt mussen wir folgende Invariante in Zeile 7 zeigen:

(I) : q = maxk : Ti−k+1...Ti = P0...Pk−1 .

Solange ein Match nicht mehr verlangert werden kann, entweder weil q = |P | oder weil dernachste zu lesende Buchstabe des Textes nicht zu dem Pattern passt (T [i] 6= P [q]), dannverringert der Algorithmus q soviel wie notig, aber so wenig wie moglich. Dies geschiet inden Zeilen 4 und 5 mit Hilfe der lps-Tabelle; und zwar solange, bis ein Suffix des Textesgefunden ist, welches mit einem Prafix des Patterns kompatibel ist oder q = 0 wird.

Wir verzichten hier auf einen formalen Korrektheitsbeweis.

Noch offen ist die Berechnung der lps-Tabelle, die als Vorverarbeitung durchgefuhrt werdenmuss. Interessanterweise konnen wir die lps-Tabelle mit einer Variante des KMP-Algorithmusberechnen. Fur die Berechnung eines Wertes in der Tabelle wird immer nur der schon be-rechnete Teil der Tabelle benotigt:

1 def KMPComputeLPS(P):2 lps = [0]* len(P)3 q = 04 for i in range(1,len(P)):5 while q>0 and P[q] != P[i]:6 q = lps[q-1]7 if P[q] == P[i]: q += 18 # Invariante (J) trifft an dieser Stelle zu.9 lps[i] = q

10 return lps

2.2.1 Laufzeitanalyse

Wir fuhren eine amortisierte Laufzeitanalyse durch. Jede Iteration der while-Schleife inZeile 4 verkleinert das Matching, das heisst, q verkleinert sich. Die Lange des Matchingswird aber in jeder Iteration der for-Schleife in Zeile 3 hochstens um 1 erhoht. Daherkann der Rumpf der while-Schleife (also Zeile 4) maximal n-mal ausgefuhrt werden. Da-mit ist die Laufzeit von KMP O(n). Eine analoge Analyse liefert eine Laufzeit von O(m) furKMPComputeLPS. Inklusive Vorverarbeitung benotigt der KMP-Algorithmus also O(m + n)Zeit. Diese Laufzeit ist theoretisch optimal.

2.3 DFA-Basiertes Pattern Matching

KMP-Algorithmus liest jedes Textzeichen genau einmal (von links nach rechts). Wie wir indiesem Abschnitt sehen werden, konnen wir den KMP-Algorithmus auch als Anwendungeines endlichen Automaten auffassen. Die Idee hierbei ist, dass der Algorithmus sich je nachdem Wert von q in |P |+1 verschiedenen Zustanden befinden kann. Beim Lesen einesZeichenswird der Zustand gewechselt (wobei u.U. der neue Zustand gleich dem alten sein kann).

8

2.3 DFA-Basiertes Pattern Matching

0 1 2 3 4 5a b b a b

a a

a

a

bb

b

Abbildung 2.2: Deterministischer endlicher Automat (DFA), der die Suche nach dem Patternabbab mit dem KMP-Algorithmus simuliert. Dabei ist der Startzustand inblau und der einzige akzeptierende Zustand in rot eingezeichnet.

Dies lasst sich explizit als deterministischer endlicher Automat (engl. deterministic finiteautomaton, DFA) formulieren:

Definition 2.2 (DFA). Ein DFA ist ein Tupel (Q, q0,Σ, δ) mit

• endliche Zustandsmenge Q

• Startzustand q0 ∈ Q• endliches Alphabet Σ (Elemente: ”Buchstaben“)

• akzeptierende Zustande F ⊂ Q• Ubergangsfunktion δ : Q× Σ→ Q

Mit dieser Definition verbinden wir folgende Semantik: Der Automat startet im Zustand q0

und liest nacheinander Zeichen aus Σ. Dabei ordnet die Ubergangsfunktion δ einem demPaar (q′, a) einen neuen Zustand zu; dabei ist q′ der alte Zustand und a das gelesene Zeichen.Ist der neue Zustand in F , gibt der Automat das Signal ”akzeptiert“.

Hier suchen wir einen Automaten, der immer dann akzeptiert, wenn die zuletzt gelesenen |P |Zeichen mit P ubereinstimmen, und daher alle Strings der Form Σ∗P akzeptiert.

Die Grundidee ist, dass in jeder KMP-Iteration der Wert der Variable q den Zustand desAutomaten bildet. Die Ubergangsfunktion ergibt sich, indem wir mit Hilfe der lps-Funktionexplizit ausrechnen, welchen Wert q nach dem Lesen jedes Zeichens bekommt.

Wir definieren also den Automaten wie folgt:

• Q = 0, . . . , |P |, also |P |+ 1 Zustande

• q0 = 0

• Σ ist das Alphabet des Textes und Patterns

• F = |P |• Ubergangsfunktion δ : Q× Σ→ Q wie unten beschrieben.

Der folgende Code ist aquivalent zu KMP, sofern die Funktion delta die korrekte Ubergangsfunktion δimplementiert.

9

2 Pattern-Matching

1 def simpleDFA(P,T,delta):2 q = 03 for i in range(len(T)):4 q = delta(q,T[i])5 if q == len(P):6 yield i

Die Funktion delta kann man, wenn lps bereits berechnet wurde, wie folgt implementieren,um Aquivalenz zu KMP zu erhalten:

1 def deltaFromLPS(q,a, lps):2 while q==len(lps) or (q>0 and P[q] != a):3 q = lps[q-1]4 if P[q] == a: q += 15 return q6

7 delta = partial(deltaFromLPS , lps=KMPComputeLPS(P))

Das Ergebnis der delta-Funktion kann man fur alle Paare (q, a) ∈ Q×Σ vorberechnen undin einer Tabelle speichern. Dies gelingt in O(m · |Σ|) Zeit, wenn man bei der Berechnungvon δ(q, ·) ausnutzt, dass δ(q′, ·) fur alle q′ < q bereits berechnet ist.

Der Folgezustand von q = 0 ist 1, wenn das richtige Zeichen P0 gelesen wird, sonst 0. DerFolgezustand von 0 < q < m ist q+ 1, wenn das richtige Zeichen Pq gelesen wird; sonst, alsofur a 6= Pq, der entsprechende Folgezustand des Zustands lps[q − 1], der schon berechnetworden ist. Der Folgezustand von q = m ist immer der entsprechende Folgezustand vonlps[m− 1].

1 def deltaTable(P, alphabet ):2 delta = dict()3 lps = KMPComputeLPS(P)4 for a in alphabet:5 delta [(0,a)] = 1 if a==P[0] else 06 for q in range(1,len(P)+1):7 for a in alphabet:8 delta [(q,a)] = delta [(lps[q-1],a)]9 if q<len(P):

10 delta [(q,P[q])] = q+111 return lambda *args: delta[args]12

13 delta = DeltaTable(P, alphabet)

(Die return-Zeile verpackt die delta-Tabelle in eine Funktion, da simpleDFA eine Funktionerwartet.)

Korrektheit. simpleDFA in Verbindung mit deltaFromLPS ist korrekt, da es nur eine Refak-torisierung von KMP ist. Zu zeigen ist also, dass deltaTable dasselbe liefert wie deltaFromLPS.Das ist einfach mit Induktion; fur q = 0 ist das sowieso klar; ...

Wir konnen Korrektheit auch mit der erweiterten Ubergangsfunktion δ : Q × Σ∗ → Q,induktiv definiert durch (q, ε) 7→ q und (q, xa) 7→ δ(δ(q, x), a) formulieren. Sei stateP (x) :=

10

2.4 Boyer-Moore-Horspool / Sunday

A A A AText:

Pattern: B B B B

Abbildung 2.3: Einfaches Beispiel, das belegt, dass es im besten Fall reichen kann, jedes m-teZeichen anzuschauen um festzustellen, dass ein Pattern der Lange m nichtvorkommt.

δ(q0, x) der Zustand nach Lesen des Textes x im durch P definierten DFA. Sei lpsP (x) dieLange des langsten Prafix von P , das auch Suffix von x ist. Dann ist stateP (x) = lpsP (x)fur alle x ∈ Σ∗.

Zeit- und Platzbedarf. Die Tabelle δ benotigt PlatzO(|Σ|·m), und die Funktion deltaTableberechnet diese in optimaler Zeit O(|Σ| ·m).

Verschlechterung gegenuber KMP: lps benotigt nur O(m) Platz und Zeit zur Berechnung.simpleDFA benotigt zum Matchen dann wie KMP O(n) Zeit.

Interpretation: lps ist kompakte Darstellung von δ.

Warum dann also DFA-Variante? Schritt bei KMP kann im Einzelfall O(m) dauern; amor-tisierte Analyse notwendig, um insgesamt O(m + n) zu zeigen. Mit DFA ist jeder SchrittO(1). Wichtig fur Realzeitanwendungen. Garantierte kurze Laufzeit in jedem Schritt, nurein Table-Lookup. (Implementierung als dict unter diesem Gesichtspunkt nicht schlau.)


Im KMP-Algorithmus wird in jeder Iteration ein Zeichen des Textes verarbeitet. Wir wollennun die Frage stellen, ob dies wirklich notig ist. Wieviele Zeichen eines Textes der Lange nmussen mindestens angeschaut werden um kein Vorkommen des gesuchten Patterns derLange m zu ubersehen? Wenn wir weniger als n/m betrachten, gibt es im Text irgendwoeinen Block der Lange m, in dem wir kein Zeichen angeschaut haben. Damit konnen wirnicht festgestellt haben ob sich dort ein Vorkommen befindet. Es ist jedoch unter Umstandenmoglich mit O(n/m) Schritten auszukommen. Wenn z.B. unser Text ausschließlich aus demBuchstaben A besteht und das Pattern nur aus dem Buchstaben B. Dann kann man durchanschauen jedes m-ten Zeichens feststellen, dass nirgendwo ein Match vorhanden sein kann(vgl. Abbildung 2.3).

In diesem Kapitel behandeln wir Algorithmen, die nach Moglichkeit Zeichen im Text uberspringen:

• Boyer-Moore-Algorithmus (Boyer and Moore, 1977, klassisch, aber meist langsamer alsdie folgenden Algorithmen, deshalb uberspringen wir ihn hier, siehe Gusfield (1997),Abschnitt 2.2),

• Horspool-Algorithmus (Horspool, 1980, Variante des Boyer-Moore Algorithmus),

• Sunday-Algorithmus (Sunday, 1990).

11

2 Pattern-Matching

AText:Pattern (Fall 1): BAA

AAAPattern (Fall 2):rechtestes "A"weiteres "A"

AText:Pattern (Fall 1): BAA

AAAPattern (Fall 2):

Nach der SHIFT-Phase:

Abbildung 2.4: Illustration des Horspool-Algorithmus. Zunachst wird das Zeichen ganzrechts im aktuellen Fenster mit dem rechtesten Zeichen des Patterns ver-glichen. Das Fenster wird in der SHIFT-Phase soweit verschoben, dass dasrechtestes Vorkommen dieses Buchstabens im Pattern (außer dem letztenZeichen) auf dieser Stelle zu liegen kommt. Dabei ist es unerheblich, ob wirvorher einen Match (Fall 1) oder einen Mismatch (Fall 2) beobachtet haben.

Typischerweise haben diese Algorithmen eine best-case-Laufzeit von O(n/m) und eine worst-case-Laufzeit von O(m·n). Insbesondere bei großen Alphabeten lohnt sich der Einsatz solcherAlgorithmen, da bei großen Alphabeten die Chance groß ist, einen Mismatch zu finden, deruns erlaubt viele Zeichen zu uberspringen.

Bemerkung 2.2. Durch Kombination mitO(n+m) Algorithmen, z.B. dem KMP-Algorithmus,lasst sich eine worst-case-Laufzeit von O(n + m) erreichen. Das ist jedoch nur theoretischinteressant.

2.4.1 Horspool-Algorithmus

Wir betrachten hier den Algorithmus von Horspool (1980), der eine Variante des Boyer-Moore-Algorithmus ist.

Idee. Zu jedem Zeitpunkt gibt es ein aktuelles Suchfenster der Lange m, dies entsprichtdem Teilstring des Textes, der gerade mit dem Muster verglichen wird.

Wir betrachten das letzte (rechteste) Zeichen des Suchfensters im Text, sagen wir a ∈ Σ.

TEST-PHASE: Wir prufen zuerst, ob a mit dem letzten Zeichen von P ubereinstimmt.Wenn nicht, geht es weiter mit der SHIFT-PHASE. Wenn ja, prufen wir das ganze Fensterauf Ubereinstimmung mit P , bis wir entweder ein nicht passendes Zeichen finden oder eineexakte Ubereinstimmung verifiziert haben. Dieser Text kann von rechts nach links oderlinks nach rechts erfolgen; haufig kann auf Maschinenebene eine memcmp-Instruktion genutztwerden.

12


SHIFT-PHASE: Unabhangig vom Ausgang der TEST-PHASE verschieben wir das Fenster.Sei `[a] die Position des rechtesten a in P ohne das letzte Zeichen, sofern eine solche Positionexistiert. Andernfalls sei `[a] := −1. Also `[a] := max0 ≤ j < m − 1 : Pj = a, wobei hierdas Maximum uber die leere Menge −1 gesetzt wird. Dann verschieben wir das Fenster umshift[a] := m− 1− `[a] Positionen (siehe Abbildung 2.4).

Damit konnen wir keinen Match verpassen, denn kurzere Shifts fuhren nach Konstruktionimmer dazu, dass das bereits gelesene a in P nicht passt.

Die Werte shift[a] werden fur jedes Zeichen a, das in P vorkommt, vorberechnet; fur alleanderen Zeichen ist shift[a] = m.

Im folgenden ist der Horspool-Algorithmus implementiert; dabei wird in der Testphase dasFenster von rechts nach links verglichen.

1 def horspool_search(s,p):2 # preprocessing: compute shifts3 shift = dict()4 for i,c in enumerate(p[: -1]):5 shift[c]=len(p)-1-i6 # main phase: search text7 count = 08 n = len(p)-19 while n<len(s):

10 # phase 1: comparison11 i = 012 while i<len(p):13 if s[n-i]!=p[-i-1]: break14 i+=115 if i==len(p): count +=116 # phase 2: shift17 try:18 k = shift[s[n]]19 except KeyError:20 k = len(p)21 n+=k22 return count

Laufzeit-Analyse Best case ist O(n/m): Klar, im besten Fall vergleicht man immer einZeichen a, das im Pattern nicht vorkommt und kann um m verschieben.

Worst case ist O(mn), lasst sich aber einfach auf O(n) modifizieren.

Interessant ist Average Case. Untersuchen in jedem Fenster: Erwartungswert der AnzahlZeichenvergleiche, Erwartungswert der Shiftlange.

Anzahl Zeichenverlgeiche hatten wir bereits als Ubungsaufgabe: in jedem Fall O(1), sogar< 2

Shiftlange: Die genauen Wahrscheinlichkeiten fur Shiftlangen hangen von P ab. Wir konnenden Erwartungswert aber abschatzen, wenn wir annehmen, dass es jeweils ein Zeichen furShiftlange 1, 2, 3, . . . gibt, bis minm, |Σ|. Im Fall |Σ| ≥ m fuhrt das auf mehr als m/2, alsoO(m). Im Fall eines kleinen Alphabets fuhrt das auf O(Σ).

13

2 Pattern-Matching

Erweiterung auf mehrere Muster (Mengen) Wahle Minimum der shifts uber alle Muster(sonst kann ein Match ubersehen werden).

idR nicht sinnvoll, da die shifts schnell sehr kurz werden.

2.4.2 Sunday-Algorithmus

Variante von Sunday Sunday (1990): Berechne Shifts nicht anhand des letzten Zeichens desSuchfensters, sondern des Zeichens dahinter.

2.5 Patterns aus mehreren Strings - Aho-Corasick

In diesem Abschnitt behandeln wir den Algorithmus von Aho and Corasick (1975).

Wir betrachten jetzt eine Menge von Patterns P = P 1, . . . , P k mit ggf. unterschiedlichenLangen; sei mi := |P i| fur 1 ≤ i ≤ k und ferner m :=

∑i mi.

Offensichtlich kann man den KMP-Algorithmus (bzw. seine Variante mit DFAs) fur jedesPattern einzeln laufen lassen. Das fuhrt zu einer Laufzeit von O(kn+m). In diesem Abschnittwollen wir der Frage nachgehen, ob das auch in O(n + m) Zeit moglich ist. Die Grundideeist die selbe wie beim KMP-Algorithmus: wir fuhren im Verlauf des Algorithmus daruberBuch, was das langste Suffix des bisher gelesenen Textes ist, das ein Prafix eines Patternsin unserer Menge P ist. Wir benotigen also eine Datenstruktur, die uns in konstanter Zeitermoglicht, ein weiteres Zeichen zu lesen und dabei diese Invariante erhalt. Das ist mit einemTrie (Kunstwort aus tree und retrieval) zu bewerkstelligen.

Definition 2.3 (Trie). Ein Trie uber eine endliche Menge von Wortern S ⊂ Σ+ ist einkantenbeschrifteter Baum uber der Knotenmenge Prefixes(S) mit folgender Eigenschaft: derKnoten s ist genau dann ein Kind von t, wenn t = sa fur ein a ∈ Σ; die Kante t → s istdann mit a beschriftet.

Um nach einer Menge von Wortern P gleichzeitig zu suchen, konstruieren wir also den Trieuber P . Nach dem Lesen eines jeden Zeichens befinden wir uns in dem Knoten, der demlangsten Suffix des Textes entspricht, das ein Prafix eines Wortes aus P ist. Wenn wir nunein neues Zeichen a lesen und eine ausgehende Kante exisiert, die mit a beschriftet ist, dannfolgen wir dieser Kante. Wir konnen den Trie dann als nicht-determinischen Automatenverstehen, indem wir einen Selbstubergang fur alle Zeichen a ∈ Σ im Startzustand anfugen.Um einen deterministischen Automaten zu erhalten, konnt wir die aus der Automatentheoriebekannte Teilmengen-Konstruktion anwenden.

Eine hier effizientere(!) Moglichkeit, einen deterministischen Automaten zu erhalten, bestehtdarin, wieder eine lps-Funktion einzufuhren. Diese hilft uns, den richtigen Zielknoten zufinden, falls keine entsprechend beschriftete Kante existiert. Wir definieren analog zum KMP-Algorithmus:

lps(q) := argmaxp∈p′∈Prefixes(P ):|p|<|q|,q[|q|−|p|...]=p|p| .

langstes Prafix von einem Muster in P , das echtes Suffix von q ist.

Berechnung der lps-Funktion:

14

2.5 Patterns aus mehreren Strings - Aho-Corasick

a

r

c

t

c a

r

tr

i

ca

0

1 5

4 8

9

62

3

7

11 12

10

a

a,rica

at,cat

a at

arc

car

Abbildung 2.5: Trie uber Patternmenge P = cat, car, arc, rica, at, a. Zusatzlich ist dielps-Funktion durch gestrichelte Pfeile dargestellt (Pfeile in die Wurzel sindder Ubersichtlichkeit halber weggelassen). Der Startzustand ist blau hinter-legt; die Zustande, die explizit zu Worten aus P korrespondieren sind rotdargestellt. Jeder Knoten ist mit der Menge der auszugebenden Worter anno-tiert (in blau). All diese Komponenten zusammen bilden den Aho-Corasick-Automaten.

1. Nummeriere Knoten durch Breitensuche

2. Initialisiere lps[0] = 0

3. Tiefe 1: lps[0] = 0 fur alle i der Tiefe 1

4. Tiefe j ≥ 2: In Knoten xa mit x 6= ε, i := 1 prufe ob lpsi[xa] := lpsi[x]a. Wenn neini := i+ 1. (Dabei ist mit lpsi die i-fache Anwendung der lps-Funktion gemeint.

Um die Konstruktion des Aho-Corasick-Automaten zu vervollstandigen, benotigen wir furjeden Knoten noch die Menge der Worter, die im gelesenen Text enden, wenn wir diesen Zu-stand erreichen. Wir nennen das Ausgabefunktion Prefixes(P )→ 2P . Die Ausgabe-Funktionkann in O(m) Zeit durch Ruckverfolgen der lps-Links gewonnen werden.

Den Aho-Corasick-Algorithmus kann man wie KMP-Alogrithmus auf Basis der lps-Funktionlaufenlassen, dann dauert die Verarbeitung jedes Zeichens amortisiert O(1). Um die Lauf-zeit jedes einzelnen Schritts auf O(1) zu beschranken, mussen wir den Automaten explizitkonstruieren, d.h. fur jede Kombination aus Knoten und Buchstaben den Zielknoten vorbe-rechnen.

Zusammenfassend konnen wir einen Aho-Corasick-Automaten, d.h. einen Trie mit lps- undAusgabe-Funktion, folgendermaßen konstruieren:

15

2 Pattern-Matching

1 def ACwithLPS(P):2 """build AC autmaton for list of patterns P,3 return its root node."""4 # Build a root for the trie5 root = ACNode ()6 # Build the trie , pattern by pattern7 for (i,p) in enumerate(P):8 node = root9 for a in p:

10 if a in node.targets:11 node = node.targets[a]12 else:13 newnode = ACNode(parent=node , letter=a)14 node.targets[a] = newnode15 node = newnode16 node.out.append(i)17 # Walk through trie in BFS -order to build lps18 for node in root.bfs():19 if node.parent == None: continue20 if node.depth >1:21 node.lps = node.parent.lps.delta(node.letter)22 else:23 node.lps = root24 node.out.extend(node.lps.out)25 return root

Dabei sind wir davon ausgegangen, dass wir eine Klasse ACNode implementiert haben, dieeinen Zustand reprasentiert und folgende Attribute besitzt: die Kinder dieses Zustand wer-den in targets gespeichert, der Buchstabe an der Kante, die zu diesem Zustand fuhrt wirdin letter gespeichert und lps- und Ausgabe-Funktion werden in lps bzw. out abgelegt.Zusatzlich stellt die Klasse noch eine Funktion bfs zur Verfugung, die alle Knoten desentsprechenden Teilbaums in der Reihenfolge einer Breitensuche zuruckliefert (als Genera-tor). Zusatzlich kann jeder Knoten uber die Funktion delta unter Berucksichtigung derlps-Funktion daruber Auskunft geben, ein welchen Zustand der Automat beim Lesen einesbestimmten Zeichens ubergeht.

Damit reduziert sich Pattern-Matching mit Aho-Corasick-Automaten auf die folgenden we-nigen Zeilen:

1 def ACMatches(P, T, root):2 q = root3 for (i,a) in enumerate(T):4 q = q.delta(a)5 for x in q.out:6 yield (i-len(P[x])+1, i+1, x)7

8 def setPatternMatchesAC(P,T):9 acroot = ACwithLPS(P)

10 return ACMatches(P, T, acroot)

16

2.6 Nichtdeterministische Automaten

0 1 2 3 4a b b a b

Abbildung 2.6: NFA zum finden des Wortes abbab. Der Startzustand ist blau hinterlegt; derakzeptierende Zustand ist rot dargestellt.

2.6 Nichtdeterministische Automaten

Einen DFA haben wir in Abschnitt 2.3 als Tupel (Q, q0, F,Σ, δ) definiert. Ein DFA zeichnetsich dardurch aus, dass er sich immer in genau einem Zustand befindet. Wir bezeichnen ihndeshalb als deterministisch. Wir wollen nun kurz nichtdeterministische endliche Automaten(engl. non-deterministic finite automaton, NFA) wiederholen. NFAs konnen sich in mehrerenZustanden gleichzeitig befinden.

Definition 2.4 (NFA). Ein NFA ist ein Tupel (Q,Q0, F,Σ,∆), wobei

• Q eine endliche Menge von Zustanden,

• Q0 ⊂ Q eine Menge von Startzustanden,

• F ⊂ Q eine Menge von akzeptierenden Zustanden,

• Σ das Eingabealphabet und

• ∆ : Q× Σ→ 2Q eine nichtdeterministische Ubergangsfunktion ist.

Wir verbinden mit dieser Definition folgende Semantik: Es gibt stets eine Menge aktiverZustande A. Am Anfang ist A = Q0. Nach dem Lesen eines Textzeichens a ∈ Σ sind alleZustande aktiv, die von A durch Lesen von a gemaßder Ubergangsfunktion ∆ erreicht werdenkonnen. Der bisher eingelesene String wird akzeptiert wann immer A ∩ F 6= ∅.

Die Ubergangsfunktion ∆ : Q×Σ→ 2Q gibt zu jedem (q, a) eine Menge an Folgezustandenan. Dies kann auch die leere Menge sein. Es ist oft hilfreich, die Ubergangsfunktion sozu erweitern, dass wir Mengen von Zustanden ubergeben konnen; d.h. wir erweitern denDefinitionsbereich der ersten Komponente von Q auf 2Q durch

∆′(A, a) :=⋃q∈A

∆(q, a) .

Daruber hinaus ist es nutzlich, wenn wir in der zweiten Komponente nicht nur einzelneZeichen, sondern ganze Strings ubergeben konnen. Wir erweitern den Definitionsbereich alsoin der zweiten Komponente auf Σ∗ durch

∆′′(A, ε) := A

und∆′′(A, xa) := ∆′′(∆′(A, x), a)

fur x ∈ Σ∗ und a ∈ Σ. Wir haben nun also eine Funktion ∆′′ : 2Q × Σ∗ → 2Q definiert. ImFolgenden unterscheiden wir nicht mehr zwischen ∆, ∆′ und ∆′′, denn es ist stets aus demKontext klar, welche Funktion gemeint ist.

17

2 Pattern-Matching

i t0 1

b i t2 3 4

i t s5 6 7

Abbildung 2.7: NFA zum parallelen finden der Worter aus der Menge it, bit, its. DieStartzustande sind blau hinterlegt; die akzeptierenden Zustande sind rot dar-gestellt. Hinweis: Auch wenn es mehrere Zusammenhangskomponenten gibt,handelt es sich um einen Automaten.

Der DFA zum KMP-Algorithmus (vgl. Abbildung 2.2) erkennt alle Strings, die auf dengesuchten String p enden, also die Sprache Σ∗p. Ein NFA, der dasselbe leistet, ist sehreinfach zu konstruieren. Ein Beispiel findet sich in Abbildung 2.6.

Auch der DFA zum Aho-Corasick-Algorithmus erkennt alle Strings, die auf einen Stringaus P enden (hier ist P nun eine Menge von Strings). Wir mussten einigen Aufwand trei-ben um diesen Automaten zu konstruieren. Der aquivalente NFA ist jedoch sehr einfach:Wir mussen noch nicht einmal einen Trie erstellen, sondern konnen einfach mehrere NFAs

”parallel schalten“. Genauer: Wir verwenden als Zustandsmenge Q := 0, . . . , |P |. JederZustand reprasentiert ein Prafix eines Strings p ∈ P . Wir bauen den Automaten so auf,dass immer alle Zustande aktiv sind, die zu einem Prafix gehoren, das mit dem Suffix (glei-cher Lange) des bisher gelesenen Textes ubereinstimmt. Entsprechend ist Q0 die Menge derZustande, die jeweils das leere Prafix representieren und F die Menge der Zustande, diejeweils den ganzen String reprasentieren. Ein Ubergang vom Zustand q nach q + 1 ist beimLesen des ”richtigen“ Zeichens moglich. Die Startzustande bleiben immer aktiv, was wirdurch Selbstubergange (die fur alle Zeichen des Alphabets gelten) erreichen. Abbildung 2.7illustriert diese Konstruktion an einem Beispiel.

Um zu beweisen, dass diese Konstruktion korrekt die Sprache Σ∗P erkennt, mussten wirfolgende Invarianten prufen:

• Zu jedem Zustand q gibt es genau einen String, der den Pfad von einem Startzustandnach q labelt: string(q).

• Jeder Startzustand ist stets aktiv.

• Zustand q ist genau dann aktiv, wenn die |string(q)| zuletzt gelesenen Zeichen gleichstring(q) sind.

Uberspringen jedoch einen formalen Beweis.

18

2.7 Bit-parallele Simulation

2.7 Bit-parallele Simulation

Um Pattern-Matching mit einem NFA zu implementieren, mussen wir die aktive Menge Averwalten. Diese Menge hat die Große O(m). Der resultierende Algorithmus hat folglich eineLaufzeit von O(m · n). In der Praxis kann sich das Simulieren eines NFAs jedoch auszahlen,wenn wir die Menge der aktiven Zustande als Bit-Vektor codieren.

Wir betrachten zunachst den einfacheren Fall eines Patterns p und gehen spater darauf ein,wie wir das auf eine endliche Menge von Patterns P verallgemeinern konnen. Wir mussenalso einen linearen NFA (vgl. Abbildung 2.6) simulieren. Die aktiven Zustande verschiebensich immer nur um eine Position nach rechts (aber nur dann, wenn das eingelesene Zeichenzur Kantenbeschriftung passt).

Dieses Verhalten konnen wir mit den Bit-Operationen shift und and simulieren; diese arbei-ten auf Registern mit vielen Bits (32, 64, oder auch 256, 1024 bei manchen Grafikkarten).Der resultierende Algorithmus heisst deshalb auch shift-and-Algorithmus. Wir nehmen an,das unser Pattern weniger Zeichen als ein Register Bits hat (trifft in der Praxis oft zu). Furlange Patterns ist diese Methode nicht empfehlenswert, weil man sich manuell um Carry-Bitskummern muss.

Der Startzustand ist immer aktiv, leitet also immer ein 1-bit weiter; wir mussen ihn also nichtexplizit simulieren. Daher vereinbaren wir folgende Zustandsbenennung: Zustand 0 ≤ q < |p|ist aktiv, wenn p[0 . . . q] gelesen wurde. Der Startzustand bekommt keine Nummer. DerInteger A mit |p| Bits reprasentiert die Zustandsmenge. Da die Startzustande darin nichtenthalten sind und alle anderen Zustande zu Beginn nicht aktiv sind, initialisieren wir A mitdem Wert 0 = (0, . . . , 0).

Zum Lesen eines Zeichen a fuhren wir einen Bit-Shift nach links durch, wobei wir ein neues 1-bit von rechts aus Startzustand hinzufugen mussen. Dann streichen wir alle geshifteten Bits,die nicht dem Lesen von a entsprechen durch Ver-und-en mit einer Maske maska fur a; dabeiist Maske maska folgendermaßen definiert: es ist maskai = 1 wenn p[i] = a und maskai = 0sonst.

Um zu entscheiden, ob unser Pattern an der aktuellen Position matcht, prufen wir, ob derZustand |P | − 1 aktiv ist.

1 def maskTable(P):2 masks = dict()3 starts = 14 alph = alphabet(P)5 for a in alph: masks[a]=06 bit = 17 for a in P:8 masks[a] |= bit9 bit *= 2

10 accepts = (bit //2)11 return (masks , starts , accepts)12

13 def ShiftAnd(T, masks , starts , accepts ):14 A = 015 for i in range(len(T)):16 A = ((A << 1) | starts) & masks.get(T[i], 0)

19

2 Pattern-Matching

17 if A & accepts !=0: yield (None , i+1)18

19 def simplePatternMatchesShiftAnd(P,T):20 masks , starts , accepts = maskTable(P)21 return ShiftAnd(T, masks , starts , accepts)

Wir wenden uns nun dem Fall einer Menge von Strings P zu. Idee: Wir hangen alle Stringsnebeneinander in ein Register. Nun mussen wir jedoch genau buchhalten, welche Bits akzep-tierender bzw. “Start”-Zustande reprasentieren.

Problem: Ermitteln welche Strings gefunden wurden. Welche Bits sind genau gesetzt? Daskann schnell die Einfachheit von Shift-And zu Nichte machen. Daher beschrankt man sich aufdas Identifizieren der Endpositionen. Man muss nur die Funktion, die die Masken berechnetumschreiben; P ist jetzt eine Liste von Strings.

1 def maskTable(P):2 masks = dict()3 starts = 04 accepts = 05 alph = alphabet(P) # Menge aller Buchstaben6 for a in alph: masks[a]=07 bit = 18 for p in P:9 starts |= bit

10 for a in p:11 masks[a] |= bit12 bit *= 213 accepts |= (bit //2)14 return (masks , starts , accepts)

Im Falle eines einzelnen Strings kann man sich die Veroderung mit 1 in jedem Schritt sparen,wenn man die Bitlogik umkehrt (0 statt 1). Beim shift-left kommt sowieso eine Null vonrechts. Entsprechend muss man auch die Logik der Masken und des Tests auf Akzeptanzumkehren. Dies liefert den Shift-Or-Algorithmus. Bei mehreren Strings nicht sinnvoll, damehrerere “Start”-Punkte.

Bemerkung 2.3. An dieser Stelle ist eine Python-Implementierung im Grunde nicht sehrsinnvoll, da ganze Zahlen als Objekte verwaltet werden und Anwendung der bit-Operationennicht wirklich low-level ist. Shift-And und Shift-Or sollte man eigentlich in Assembler/Cprogrammieren, damit man die Vorteile voll ausnutzen kann.

Laufzeit: O(m ·n/w), dabei ist w die Registerlange (word size). Wenn P nicht in ein Registerpasst, muss man das Ubertragsbit beim shift-left beachten. Wenn wir annehmen, dass m ≤ wbzw m/w = O(1) erhalten wir eine Laufzeit von O(n) Laufzeit. Wenn diese Annahme erfulltist, erhalten wir einen Algorithmus, der in der Praxis sehr schnell ist.

2.8 Zahlweisen von Matches

Die eben behandelten Algorithmen shift-and und shift-or liefern die Positionen im Text, andenen mindestens ein Pattern in der gegebenen Menge endet. Die Anzahl dieser Positionen

20

2.9 Teilstring-basierte Ansatze: BDM, BNDM, BOM

Pattern:

Text: A u

A u

B u

Abbildung 2.8: Illustration des Teilstring-basierten Pattern-Matchings. Das Pattern enthaltden Teilstring u. Links von u wurde im Text der Buchstabe A gelesen; da Auist aber kein Teilstring des Patterns. Daher konnen wir das Fenster (rot ge-strichelt) soweit verschieben, dass der Beginn des Fensters auf das gefundeneVorkommen von u fallt. (Wenn das Fenster weniger weit verschoben wurde,enthielte es Au, was aber kein Teilstring des Patterns ist.)

unterscheidet sich im Allgemeinen von der Anzahl der Vorkommen der Patterns, weil auchmehrere Patterns an einer Stelle enden konnen (wenn ein Pattern ein Suffix eines anderesPatterns ist).

Allgemein konnen wir die Anzahl der Vorkommen eines Musters (o.b.d.A. eine Menge vonStrings) in einem Text T auf (mindestens) drei verschiedene Arten zahlen:

• uberlappende Matches; entspricht Anzahl Paare (i, j) so dass T [i . . . j] ∈ P , entsprichtStandard-Definition; wird mit AC-Automat mit output-Funktion gelost

• Endpositionen von Matches; entspricht Anzahl j, fur die es mindestens ein i gibt sodass T [i . . . j] ∈ P ; kann ebenfalls mit AC-Automat gelost werden (man braucht keineDetails zu gefundenen Strings, kann jeden Zustand mit einem Bit markieren).

• nichtuberlappende Matches; gesucht ist eine maximale Menge von Paaren (i, j), dieMatches sind, so dass die Intervalle [i, j] fur je zwei verschiedene Paare disjunkt sind.Bisher hier nicht behandelt.


Wir behandeln jetzt Teilstring-basierte Ansatze zum Pattern-Matching. Dabei wird das ak-tuell betrachtete Fenster (wie auch schon beim Horspool-Algorithmus) von rechts nach linksgelesen. Die Idee besteht nun darin, nicht nur solange von rechts nach links zu lesen, bis esein Mismatch mit dem Pattern gibt, sondern solange, bis der gelesene Teil kein Teilstring desPatterns ist. Daraus ergibt sich dann sofort, wie weit wir das Fenster verschieben konnen,ohne ein Vorkommen zu verpassen (siehe Abbildung 2.8).

Eventuell konnen wir das Fenster noch weiter verschieben, wenn wir nachhalten, was daslangste Suffix des aktuellen Fensters ist, dass auch ein Prafix unseres Patterns ist (sieheAbbildung 2.9). Wir benotigen also eine Datenstruktur, die es uns erlaubt:

1. dem gelesenen Text von rechts nach links Zeichen anzufugen,

2. festzustellen, ob der bisher gelesene Teil ein Teilstring des Patterns ist,

21

2 Pattern-Matching

pu

p

Pattern:

Text: A u

Bp

pA u

Abbildung 2.9: Die Verschiebung kann unter Umstanden noch großer als in Abbildung 2.8ausfallen, wenn das langste Suffix p der bisher gelesenen Zeichen bekannt ist,dass ein Prafix des Patterns ist.

3. festzustellen, ob der bisher gelesene Teil ein Prafix des Patterns ist.

Diese Anforderungen werden erfullt durch den Suffixautoment des reversen Patterns. DerSuffixautomat fur den String x ist ein DFA mit folgende Eigenschaften:

• Es muss nicht zu jedem Zustand und jedem Buchstaben eine ausgehende Kante geben.Fehlende Kanten fuhren in einen besonderen Zustand “FAIL”.

• Es existiert ein Pfad mit Label y von der Wurzel genau dann, wenn x ein Teilstringvon y ist.

• Der Pfad mit Label y endet genau dann in einem akzeptierenden Zustand, wenn y einSuffix von x ist.

• Der Automat kann in Platz O(|x|) in Zeit O(|x|) konstruiert werden.

Wird der Suffixautomat fur ein Pattern P konstruiert, so erlaubt die dritte Eigenschaft dasErkennen von Suffixen von P rev, also Prafixen von P .

2.9.1 Backward Dawg Matching (BDM)

Wir stellen nur das Konzept vor, BDM ist in der Praxis nie optimal.

Vorverarbeitung. Zu Pattern P erzeugen wir den Suffixautomaten von P rev.

Suche. Wie bei Horspool gibt es ein aktuelles Suchfenster der Lange |P | = m. Wir lesendas Fenster von rechts nach links mit dem Suffixautomaten, solange nicht der Zustand FAILeintritt.

Initial setzen wir die Variable next auf das erste Zeichen hinter dem aktuellen Fenster. Errei-chen wir beim Lesen einen akzeptierenden Zustand, haben aber noch nicht das ganze Wortgelesen, haben wir ein Prafix des Patterns erkannt und setzen next auf dessen Startposition.Haben wir das ganze Pattern gelesen, so haben wir ein Match identifiziert, setzen aber nichtnext.

22


M O O A M

Abbildung 2.10: Nichtdeterministischer Suffixautomat fur das Wort MOOAM (blau: Startzu-stand, rot: akzeptierender Zustand)

Ob wir nun mit FAIL abbrechen oder ein Match finden, wir verschieben das Fenster so, dasses nun bei Position next beginnt; dies ist die nachste Position, bei ein der Prafix des Fenstersmit einem Prafix von P ubereinstimmt (vgl. Abbildung 2.9).

Dieser Algorithmus braucht im schlimsten Fall (worst-case) O(mn) Zeit. Durch Kombinationmit KMP lasst sich wieder O(n) erreichen. Im besten Fall braucht der Algorithmus, wie auchder Horspool-Algorithmus, O(n/m) Zeit. Die average-case-Analyse fuhrt auf O(n log|Σ|m/n)(ohne Beweis).

Das Problem ist jedoch die Konstruktion des verhaltnismaßig komplizierten Suffixautomaten,die sich in der Praxis unter Umstanden nicht auszahlt. Deshalb kommt statt dessen oft derim nachsten Abschnitt beschriebene BNDM-Algorithmus zum Einsatz.

2.9.2 Backward Nondeterministic Dawg Matching (BNDM)

Statt eines determinischen Suffixautomaten betrachten wir nun den entsprechenden nichtde-terministischen Automaten. Dieser lasst sich leicht erstellen und bitparallel simulieren (vgl.Abschnitte 2.6 und 2.7). Wir konnen den nichtdeterministichen Automaten auch nutzen, umdaraus den deterministischen Suffixautomaten zu konstruieren.

Der Automat besteht lediglich aus einer Kette von |P |+1 Zustanden plus einem Startzustand.Vom Startzustand gehen zu jedem Zustand ε-Ubergange aus (siehe Abbildung 2.10). ImPrinzip kann man diesen Automaten nun bitparallel simulieren. Details hierzu finden sichim Buch von Navarro and Raffinot (2002, Abschnitt 2.42). Die Idee hierbei ist, solangeZeichen im aktuellen Fenster (von rechts nach links) einzulesen, wie noch Zustande aktivsind. Wenn nach k gelesenen Zeichen der akzeptierende Zustand aktiv ist, wissen wir, dasswir ein passendes Suffix (des reversen Patterns) der Lange k gelesen haben.

2.9.3 Suffix-Orakel

Wir betrachten nun eine Vereinfachung. Eigentlich brauchen wir nur einen Automaton, dererkennt wann ein String kein Teilstring von P ist. Das bedeutet, wir suchen einen Auto-maten, der Teilstrings von P und evtl. einige Strings mehr akzeptiert. Dadurch wird etwasLaufzeit verloren; wenn die Datenstruktur jedoch einfacher aufzubauen ist, kann sich dasunter Umstanden lohnen.

23

2 Pattern-Matching

n a n n a n n0 1 2 3 4 5 6 7

nichtdef.

0 0 1 1 2 3 4

a

n

8

4

n q9

n

0

q

q

q

Abbildung 2.11: Suffix-Orakel fur den String nannannnq (blau: Startzustand, rot: Suffix-Funktion suff)

Gewunschte Eigenschaft:

• u ist Teilstring von P ⇒ Es gibt einen Pfad vom Startzustand aus, der u buchstabiert.

Die Ruckrichtung fordern wir nicht streng sondern begnugen uns mit der Forderung, dass

”nicht zuviele zusatzlichen Strings“ erkannt werden. Praziser formuliert: Es wird nur eineinziger String der Langem und auch keine langeren erkannt. Um diese Forderung zu erfullen,werden mindestens m + 1 Zustande benotigt. Zusatzlich verlangen wir, dass der Automatauch nicht mehr als m+ 1 Zustande und nicht mehr als 2m− 1 Ubergange hat.

Das algorithmische Prinzip beim String-Matching bleibt wie vorher: Man liest ein Textfensterruckwarts und wendet darauf das Orakel von x := P rev an. Sobald festgestellt wird, dass dergelesene String kein Teilstring von P rev ist, kann man das Fenster hinter das letzte geleseneZeichen verschieben (vgl. Abbildung 2.8).

Konstruktion

Wir beschreiben jetzt die Konstruktion des Orakels; danach weisen wir die gewunschtenEigenschaften nach.

Wir beginnen mit dem Startzustand 0 und fugen dann in m := |x| Iterationen jeweils einenZustand und mindestens eine Kante hinzu. In Iteration 1 ≤ i ≤ m wird das Wort um denBuchstabe xi−1 verlangert, indem Zustand i und mindestens die Kante i−1

xi−1→ i hinzugefugtwerden. Kanten von i− 1 nach i nennen wir innere Kanten.

Nun ist fur i ≥ 2 weiter zu beachten, dass alle schon existierenden Teilstrings, die mitxi−2 enden, um xi−1 verlangert werden konnen. Enden diese ohnehin in Zustand i − 1,so geschieht dies automatisch durch die neue Kante. Enden diese aber in einem fruherenZustand j, von dem es noch keine ausgehende Kante mit Label xi−1 gibt, so muss die Kantejxi−1→ i zusatzlich eingefugt werden. Solche Kanten nennen wir außere Kanten. Woher wissen

wir, ob es solche Teilstrings (Suffixe von x[0 . . . i− 2]) gibt, die die Einfugung von außerenKanten notig machen?

Wir definieren eine Hilfsgroße: Sei suff [i] der Zustand, in dem das langste Suffix vonx[0 . . . i− 1] (also des Prafix der Lange i von x) endet, das nicht in i endet. Wir setzensuff [0] := −1 (oder undefiniert). Offensichtlich ist dann suff [1] = 0 (entsprechend dem

24


leeren Suffix) und stets suff [i] < i. Hat man von jedem Zustand Zugriff auf das langste Suf-fix, erhalt man alle Suffixe durch Iteration, bis man eine existierende passende ausgehendeKante findet oder im Zustand 0 angekommen ist. Der Zielzustand einer solchen existierendenKante (bzw. 0) ist dann offenbar das gesuchte neue suff [i].

Es ergibt sich folgender Algorithmus zur Berechnung der Ubergangsfunktion δ des Orakels.

1 def deltaTableBOM(x):2 m = len(x)3 delta = dict()4 suff = [None ]*(m+1)5 for i in range(1,m+1):6 a = x[i-1]7 delta[(i-1,a)]=i8 k = suff[i-1]9 while k!=None and (k,a) not in delta:

10 delta[(k,a)]=i11 k = suff[k]12 suff[i] = delta[(k,a)] if k!=None else 013 return lambda *args: delta.get(args , None)

In Zeile 7 werden die “inneren” Kanten erzeugt, in Zeile 10 die außeren Kanten. In Zei-le 12 wird suff [i] gesetzt, entweder auf das Ziel einer existierenden Kante mit richtigemBuchstaben (dann gibt es das entsprechende Suffix und alle kurzeren Suffixe schon), oderauf den Startzustand 0, wenn sich dort bereits befindet und es keine ausgehende Kante mitdem korrekten Buchstaben gab (k==None). Abbilung 2.11 zeigt ein Suffix-Orakel und diezugehorige Funktion suff .

Anwendung des Orakels. Die delta-Funktion wird zum reversen Muster konstruiert; daraufwird dann die oben erwahnte Grundidee angewendet, das Fenster hinter das zuletzt geleseneZeichen zu verschieben.

1 def matchesBOM(P,T):2 delta = deltaTableBOM(P[:: -1])3 return BOMwithDelta(T,delta ,len(P)) # return generator

1 def BOMwithDelta(T,delta ,m):2 n = len(T)3 window = m # current window is T[window - m : window]4 while window <= n:5 q, j = 0, 1 # start state of oracle , character to read6 while j <= m and q!=None:7 q = delta(q,T[window -j])8 j += 19 if q!=None: yield (window -m, window)

10 window += m-j+2

25

2 Pattern-Matching

2.10 Auswahl eines geeigneten Algorithmus in der Praxis

Einen schonen Uberblick wann (in Abhangigkeit von Alphabetgroße und Patternlange) wel-che Algorithmus in der Praxis vorteilhaft ist, findet sich bei Navarro and Raffinot (2002,Figure 2.22).

Zusammenfassend lasst sich folgendes sagen: Ab einer hinreichend grossen Alphabetgroßeist immer der Horspool-Algorithmus der schnellste. Bei sehr kleinen Alphabeten und kurzenPatterns ist Shift-Or gut. BNDM ist gut, solange der Automat bit-parallel in einem Registerverarbeitet werden kann.

26

KAPITEL 3

Bit-parallele Algorithmen

In der Praxis kommt es haufig vor, dass man nicht nur nach exakten sondern auch nachungefahren Vorkommen eines Musters suchen mochte (z.B. bei einer vom Benutzer einge-gebenen Suchanfrage, die moglicherweise Rechtschreibfehler enthalt). Ziel ist es also, alleSubstrings in einem Text zu finden, die ahnlich zu dem vorgegebenen Pattern sind; dazumussen wir zunachst einen Distanzbegriff zwischen Strings definieren.

Beispiele fur Distanzmaße:

• Pancake-Flip-Distanz: Anzahl der Flips (=umdrehen eines Prafixes), die notig sind umeinen String in einen anderen zu uberfuhren.

• Hamming-Distanz

• Edit-Distanz

Wir betrachten zunachst die Edit-Distanz. Die Edit-Distanz zwischen zwei Strings ist defi-niert als die minimale Anzahl an Operationen, die benotigt werden um den einen String inden anderen zu uberfuhren. Als Operationen sind dabei zugelassen:

• Ersetzen eines Zeichens,

• Ein Zeichen loschen (engl. deletion),

• Ein Zeichen einfugen (engl. insertion).

27

3 Bit-parallele Algorithmen

a b b a b

a b b a b

a b b a b

b a a b a

b a a b a

k=0

k≤1

k≤2

-1 0 1 2 3 4

Abbildung 3.1: NFA zum finden von approximativen Vorkommen des Patterns abbab ausdem Alphabet Σ = a, b. Der Automat findet alle Vorkommen, die maximaleine Edit-Distanz von k = 2 haben. Blaue Zustande: Startzustande; roteZustande: Endzustande; grune Kanten: insertions, durfen beim Lesen allerBuchstaben des Alphabets passiert werden; rote Kanten (ε-Kanten): deletion.

3.1 Approximative Matching mit NFAs

Eine Idee zur approximativen Suche besteht wieder in der Konstruktion eines NFAs. Dabeiverwenden wir wir einen ”linearen“ NFA; allerdings betreiben wir k solche Automaten par-allel wenn k die Anzahl der maximal erlaubten Fehler ist. Formaler Ausgedruckt verwendenwir den Zustandsraum Q = −1, 0, . . . , |p|−1×0, . . . , k fur die Suche nach dem Pattern pmit maximal k Fehlern. Ein solcher Automat ist in Abbildung 3.1 illustriert.

Invarianten:

1. Ist in einer Spalte i ein Zustand aktiv, dann auch alle darunter,

2. Ist der Zustand in Zeil j und Spalte i aktiv, dann wurde zuletzt p[0 . . . i] mit ≤ jFehlern gelesen.

Wir fuhren keinen formalen Korrektheitsbeweis, sondern skizzieren ihn nur. Die Idee be-steht darin, die obigen Invarianten durch Induktion zu beweisen. Offensichtlich sind beideInvarianten zu Beginn, wenn noch kein Zeichen gelesen wurde, korrekt.

3.1.1 Bit-parallele Simulation

Diesen Automaten bit-parallel zu simulieren ist etwas komplizierter als beim einfachen linea-ren Automaten, aber durchfuhrbar. Wir verwenden wieder einen Shift-And-Ansatz. Fur jedeZeile j definieren wir einen Bitvektor Aj , die Bitvektoren aus dem jeweils verhergegangenenSchritt bezeichenen wir mit A(alt)

j , das aktuell gelesene Zeichenen mit c. Es ergeben sichfolgende Operationen zum lesen eines Zeichens:

• A0 ← (A(alt)0 1|1) & mask[c]

• A1 ←((A(alt)

1 1) & mask[c])|

(A

(alt)0

)︸︷︷︸Einfugungen

|(A

(alt)0 1

)︸︷︷︸Ersetzungen

|(A0 1

)︸︷︷︸Loschungen

28

3.1 Approximative Matching mit NFAs

b a Σ Σ ΣΣ

b

εε

Abbildung 3.2: NFA zur Suche nach dem Pattern a-b-x(1,3)-b.

Implementierung:

1. von unten nach oben: Update mit alten Werten

2. von oben nach unten: Update mit neuen Werten

3.1.2 Verallgemeinerung:”

Gaps“ beschrankter Lange

Wir verwenden nun folgende Notation um ein Pattern zu beschreiben: b-a-x(1,3)-b; dabeisteht x fur ein beliebiges Zeichen und x(1,3) fur ein bis drei beliebige Zeichen.

Einsschraankungen:

1. Wir erlauben x(,) nicht ganz vorne und nicht ganz hinten.

2. Wir erlauben nicht zweimal hintereinander x(,), denn:

. . . -x(a,b)-x(a’,b’)- . . . ⇔ . . . -x(a+a’,b+b’)- . . .

3. Wir erlauben keine Gaps mit Lange 0, d.h. x(a,b) ist nur fur a > 0 erlaubt.

Implementierung:

1. Shift-And-Schritt

2. ε-Ubergang. Dafur verwenden wir zwei Bitmasken: in der Mask F sind alle Zustande,die zum Ende eines x(,)-Blocks auf eins gesetzt sind; in der Maske I setzen wir alleBits auf eins, die zu den Anfangen der x(,)-Blocke gehoren. Dann ergibt sich dieUpdate-Formel:

A← A |[(F − (A & I)

)& ∼ F

]Bemerkung: Die oben genannte Technik kann man immer dann einsetzen, wenn in einemBitvektor ein ganzer Bereich mit Einsen gefullt werden soll, moglicherweise in Abhangigkeitvom Wert eines bestimmten Bits.

Insgesamt ergibt sich fur die Suche nach einem Pattern der Langemmit Gaps variabler Langemit maximal k Fehlern eine Laufzeit von O(n·m/w ·(k+1)). Dabei ist n die Textlange und wdie Wortgroße unserer Rechnerarchitektur. In der Regel wenden wir bitparallele Algorithmennur an, wenn m/w = O(1) ist.

29


εε ε

a b c d eΣ -1 0 1 2 3 4

f g h5 7 8

I: 1 10 0 0 0 0 0F: 1 100000 0O: 1 1 10 0 0 0 0

Abbildung 3.3: NFA fur das Pattern abc?d?efg?h mit den dazugehorigen Bitmasken.

Noch eine Pattern-Klasse. Wir betrachten Patterns der Art ab?c*e+, dabei wirken dieZeichen ?, * und + immer auf das verhergegangene Zeichen. Es steht

• b? fur ε oder b

• c* fur ε, c, cc, ccc, . . .

• e+ fur ee*

Wir fangen mit Strings an, die nur ? und nicht * und + vorkommen. Wieder suchen wir nacheiner Moglichkeit, den NFA bitparallel zu simulieren.

• Fall 1: Zeichen mit ? haben mindestens ein normales Ziechen dazwischen. Dieser Fallist relativ einfach:

A = A | (A& I) 1,

dabei ist A Menge der aktiven Zustande und I eine Bitmaske, in der alle Bits auf Nullgesetzt sind, bis auf die Bits, die zu Zeichen vor Fragezeichen gehoren.

• Fall 2: Fragezeichen durfen beliebig verteilt sein:

AF ← A |F (3.1)

A← A∣∣ [O&

((∼ (AF − I))⊕AF

)](3.2)

dabei steht das Symbol ⊕ fur exklusives Oder (xor). Die Bitmasken A, I und O habendabei folgende Bedeutung:

– I ist je Block der Start der ersten ε-Kante,– F ist je Block das Ende der letzten ε-Kante,– O: alles in ]I, F ] (Endzustande von ε-Kanten).

Abbildung 3.3 zeigt den NFA zur Suche nach dem Pattern abc?d?efg?h und die dazu-gehorigen Bitmasken I, F und O. Zu beachten ist, dass das niederwertigste Bit jeweils ganzlinks steht (unter dem Zustand 0). Als Binarzahl geschrieben ergeben sich also die Bimasken:

I = 00100010

F = 01001000

O = 01001100

30

3.2 Alternative: BNDM verallgemeinern

Als Beispiel nehmen wir an, dass nach der Shift-And-Phase die Zustande -1 und 1 aktiv sind;das entspricht A = 00000010. Wir werten nun (3.1) und (3.2) Schritt fur Schritt aus:

AF = A |F = 01001010

I = 00100010

(AF − I) = 00101000

∼ (AF − I) = 11010111

AF = 01001010(∼ (AF − I)

)⊕AF = 10011101

O = 01001100

O&(∼ (AF − I)

)⊕AF = 00001100

Das Ergebnis sagt uns, dass die Zustande 2 und 3 zusatzlich aktiviert werden mussen. Dasstimmt mit Abbildung 3.3 uberein, denn die Zustande 2 und 3 sind vom Zustand 1 aus uberε-Kanten erreichbar.

Nun erweitern wir den Algorithmus so, dass auch Wiederholungen (* und +). Dabei steht +fur ein oder mehr Vorkommen und * fur null oder mehr Vorkommen des jeweils vorherge-gangenen Buchstabens.

Beispiel: abc+def*g*h

Verwendete Bitmasken:

• A : Ai = 1⇐⇒ Zustand i aktiv

• mask[c] : mask[c]i = 1⇐⇒ pi = c

• rep[c] : rep[c]i = 1⇐⇒ pi wiederholbar (+ oder *)

• I, F,O : fur optionale Blocke (? und *), wie oben.

Schritte des Algorithmus:

1. Shift-And: A←[(

(A 1) | 1)

&mask[c]] ∣∣∣ [A& rep[c]

]2.

AF ← A |F

A← A∣∣ [O&

((∼ (AF − I))⊕AF

)]

3.2 Alternative: BNDM verallgemeinern

In den vorhergegangenen Abschnitten haben wir stets den Shift-And Algorithmus verall-gemeinert. Das heisst, wir haben Automaten bitparallel simuliert, die einen Text Zeichenfur Zeichen von links nach rechts lesen. Eine Alternative ist wieder das Lesen eines Text-fensters von rechts nach links, was im besten Fall zu langeren Shifts und damit wenigerVergleichen fuhrt; genauer erhalten wir eine bestcase-Laufzeit von O(n/`min), wobei `min

31


a b b a b

a b b a b

a b b a b

b a a b a

b a a b a

k=0

k≤1

k≤2

-1 0 1 2 3 4

D0 D1 D2 D3

Abbildung 3.4: Verdeutlichung der Reprasentation eines k-Fehler-NFAs durch Diagonalen.

die Mindestlange eines Matches ist. Im schlimmsten Fall werden jedoch O(n`max) Vergleichebenotigt.

Wir fuhren die Konstruktion des entsprechenden Automaton hier nicht im Detail durch,sondern listen lediglich seine Eigenschaften auf. Der Automat

• erkennt das reverse pattern prev,

• besitzt keinen Selbstubergang des Startzustands,

• hat aktive Zustande, solange ein Teilstring von p gelesen wurde,

• erreicht Endzustand, wenn ein Prafix von p gelesen wurde.

Algorithmus:

1. Initial werden alle Zustande des Automaton aktiviert.

2. Lese `min Zeichen im aktuellen Fenster von rechts nach links.

3. Im Erfolgsfall: Vorwartsverifikation des Patternvorkommens.

4. Verschiebung des Fensters wie beim BNDM-Algorithmus.

3.3 Alternative Implementierung des k-Fehler-NFA

Bisher hatten wir den k-Fehler-Automaten zeilenweise implementiert. Jede Zeile war dabeidurch k + 1 Register/Speicherplatze reprasentiert. Ein Update erfolgte durch iterieren uberalle k + 1 Zeilen.

Die Beobachtung, dass sich auf den Diagonalen ε-Kanten befinden, fuhrt zu der Idee, denAutomaten nicht zeilen, sondern diagonalenweise durch (vgl. Abbildung 3.4). Wir speicherndie Bitvektoren fur alle Diagonalen (getrennt durch jeweils eine Null) hintereinander in einemlangen Bitvektor. Die 0-te Diagonale D0 muss nicht gespeichert werden, da alle Zustandeauf dieser Diagonalen ohnehin immer aktiv sind. Insgesamt ergibt sich also ein Speicherbe-darf von (m− k)(k + 2) Bits. Die Update-Schritte konnen mit den besprochenen Technikendurchgefuhrt werden. Der Vorteil besteht darin, dass die Schleife mit k+1 Schritten entfallt;

32

3.4 Zusammenfassung

dies ist insbesondere ein Vorteil, wenn alle Bits in ein Prozessorregister passen. Der Nach-teil besteht darin, dass sich diese Technik nicht ohne weiteres mit den obigen Methoden furoptinale Zeichen bzw. wiederholte Zeichen kombinieren lasst.

3.4 Zusammenfassung

Bitparallele Techniken (Shift-And, BNDM) erlauben sehr flexibel, unterschiedliche Pattern-Klassen zu handhaben (z.B. -x(,)-, optionale Zeichen ?* und Wiederholungen +*) unddabei Fehler zuzulassen. Fur kurze Patterns sind bitparallele Algorithmen sehr schnell.

33


34

KAPITEL 4

DP-Algorithmen zum approximativenString-Matching und Sequenzalignment

In diesem Kapitel behandeln wir Dynamic-Programming-Algorithmen. Dynamic Program-ming (DP) ist eine algorithmische Technik, deren Anwendung sich immer dann anbietet,wenn Probleme im Prinzip rekursiv gelost werden konnen, dabei aber (bei naiver Implem-tierung) dieselben Instanzen des Problems oft gelost werden musste.

4.1 Globales Alignment

Wir betrachten das Problem der Berechnung der Edit-Distanz d(s, t) von s, t ∈ Σ∗ unda, b ∈ Σ. Dabei ist die Edit-Distanz die Anzahl der Operationen, die man mindestensbraucht, um einen String in einen anderen zu uberfuhren; zulassige Operationen sind dasLoschen/Einfugen eines Zeichens und das Verandern eines Zeichens.

d(s, ε) = |s| (4.1)d(ε, t) = |t| (4.2)

d(a, b) =

1 falls a 6= b

0 falls a = b(4.3)

d(sa, tb)(i)= min

d(s, t) + d(a, b),d(s, tb) + 1,d(sa, t) + 1

(Ersetzung)(Einfugung von a)(Einfugung von b)

(4.4)

Dabei ist (i) zunachstmal eine Behauptung, die wir beweisen mussen.

35

4 DP-Algorithmen zum approximativen String-Matching und Sequenzalignment

s a

t b

s a

tb -

sa -

t b

Abbildung 4.1: Mogliche Fortsetzungen, wenn ein Alignment der Strings s und t schon be-kannt ist. Dabei sind a, b ∈ Σ.

Idee zum Beweis von (4.4). Die Richtung ”≤“ gilt, da alle drei Moglichkeiten zulassige Edit-Operationen fur sa und tb darstellen. Eine Illustration findet sich in Abbildung 4.1. Um dieUngleichung ”≥“ zu zeigen, fuhren wir einen Widerspruchsbeweis mit Induktion. Annahme:d(sa, tb) < min. . .. Ein Alignment von sa, tb muss jedoch auf eine der o.g. Arten enden:

”a steht uber b“, ”a steht uber –“ oder ”– steht uber b“. (Widerspruch).

Die Edit-Distanz kann mit dem Algorithmus von Needleman and Wunsch (1970) wie folgtberechnet werden. Seien m := |s| und n := |t|. Wir verwenden eine DP-Tabelle D[i, j] mit

D[i, j] := Edit-Distanz der Prafixe s[. . . i] und t[. . . j]

Wir initialisieren die nullte Spalte und die nullte Zeile durch D[i, 0] = i fur 0 ≤ i ≤ mund D[0, j] = j fur 0 ≤ j ≤ n. Alle weiteren Werte konnen berechnet werden, sobald dieNachbarzellen ”daruber“, ”links daneben“ und ”links daruber“ bekannt sind:

D[i, j] = min

D[i− 1, j − 1] + d(s[i], s[j]),D[i− 1, j] + 1,D[i, j − 1] + 1

Die Auswertung kann in verschiedenen Reihenfolgen erfolgen, z.B. von links nach rechts undvon oben nach unten. In jedem Fall konnen wir nach Ausfullen der Tabelle die Edit-Distanzvon s und t im Feld D[m,n] ablesen. Code fur diesen Algorithmus findet sich im nachstenAbschnitt.

4.2 Visualisierung des Alignments

Wir definieren ein Alignment von s, t ∈ Σ∗ als String uber (Σ∪−)2\(−,−)mit π1(A) = sund π2(A) = t, wobei π1 ein String-Homomorphismus mit π1

((a, b)

)= a fur a ∈ Σ und

π1

((−, b)

)= ε ist. Analog ist π2

((a, b)

)= b fur b ∈ Σ und π2

((a,−)

)= ε

Die Kosten eines Alignments berechnen sich als die Summe der Kosten der Spalten:

d(a, b) =

0 a = b,

1 a 6= b,

wobei d(−, b) = d(a,−) = 1 fur alle a, b ∈ Σ. Gesucht ist nun das optimale Alignment (bisherkonnen wir nur die Edit-Distanz berechnen); wir wollen also das Alignment berechnen, dessenKosten gleich der Edit-Distanz sind. Dies konnen wir durch Backtracing in der DP-Tabelleerreichen. Dabei starten wir von der letzten Zelle D[m,n] und schließen in jeder Zelle aufdie Vorgangerzelle.

36

4.3 Anzahl globaler Alignments

1 def global_alignment(s,t):2 # initialisiere zunaechst nur die erste Zeile der DP-Tabelle3 D = [range(len(t)+1)]4 # schleife ueber alle zeilen der DP-Tabelle5 for row in xrange(1,len(s)+1):6 # lege zunaechst neue zeile an7 D.append ([row]+len(t)*[0])8 # iteriere ueber alle spalten9 for col in xrange(1,len(t)+1):

10 D[row][col] = min(11 [D[row -1][ col]+1,12 D[row][col -1]+1 ,13 D[row -1][col -1]+1*(s[row -1]!=t[col -1])14 ])15 # traceback durch die Matrix um das Alignment zu gewinnen16 row ,col = len(s),len(t)17 alignment = []18 while (row >0) or (col >0):19 if (row >0) and (col >0)20 and (D[row][col] == D[row -1][col -1]+1*(s[row -1]!=t[col -1])):21 alignment = [(s[row -1],t[col -1])]+ alignment22 row ,col = row -1,col -123 elif (col >0) and D[row][col] == D[row][col -1]+1:24 alignment = [(’-’,t[col -1])]+ alignment25 row ,col = row ,col -126 else:27 alignment = [(s[row -1],’-’)]+ alignment28 row ,col = row -1,col29 # Liefere Paar zurueck: Edit -Distanz und Alignment30 return D[len(s)][ len(t)], alignment

Etwas Zeit kann man noch einsparen, wenn die jeweilige Vorgangerzelle beim Ausfullen derDP-Tabelle gespeichert wird.

Die Berechnung einer Zelle der DP-Tabelle ist in konstanter Zeit moglich. Damit ist derZeitbedarf O(nm). Falls nach dem Erstellen der Tabelle das Alignment rekonstruiert werdensoll, mussen wir die gesamte Tabelle speichern und benotigen daher O(nm) Platz. Sind wirnur an der Edit-Distanz, aber nicht am Alignment interessiert, brauchen wir nur jeweils diezuletzt berechnete Spalte/Zeile zu speichern (je nachdem, ob wir zeilen- oder spaltenweisedie Tabelle fullen). Damit kommen wir auf einen Platzbedarf von O(minm,n).

4.3 Anzahl globaler Alignments

Wie viele Alignments zweier Sequenzen der Langen m und n gibt es? Offensichtlich hangtdie Anzahl N(n,m) nur von der Lange der Sequenzen (und nicht von den Sequenzen selbst)

37


Abbildung 4.2: Beispiel fur einen Alignmentgraphen fur ein globales Sequenzalignment.

ab. Wie stellen folgende Rekurrenz auf:

N(0, 0) = 1 (4.5)N(n, 0) = 1 (4.6)N(0,m) = 1 (4.7)N(n,m) = N(m− 1, n− 1) +N(m,n− 1) +N(m− 1, n) (4.8)

Diese Rekurrenz kann man sich anhand der Abbildung 4.1 verdeutlichen. Es ergeben sichfur N(m,n) folgende Werte:

1 1 1 1 1 . . .

1 3 5 7 9 . . .

1 5 13 25 41 . . .

1 7 25 63 129 . . .

1 9 41 129 321 . . .

1...

......

.... . .

In welche Großenordung liegt N(n, n)? Offensichtlich gilt N(n, n) > 3N(n−1, n−1) und da-mit N(n, n) > 3n. Asymptotisch ergibt sich N(n, n) =

√n ·(1+

√2)2n+1, d.h. das Wachstum

ist exponentiell mit Basis (1 +√

2)2 ≈ 5.8.

4.4 Alignment-Graph

Wir drucken das Problem, ein Sequenzalignment zu berechenen nun graphentheoretisch aus.Dazu definieren wir den Alignment-Graph:

• Knotenmenge V := (i, j) : 0 ≤ i ≤ m, 0 ≤ j ≤ n ∪ v, v•

38

4.5 Suche eines Musters P in einem Text t

• Kanten:Kante Label Kosten

horizontal: (i, j)→ (i, j + 1)[−tj

]1

vertikal: (i, j)→ (i+ 1, j)[si−

]1

diagonal: (i, j)→ (i+ 1, j + 1)[sitj

] 0 wennsi = tj

1 sonstInitialisierung: v → (0, 0) ε 0Finalisierung: (m,n)→ v• ε 0

In Abbildung 4.2 wird ein Alignmentgraph dargestellt. Mit der Definition des Alignment-graphent haben wir das Problem des Sequenzalignments reduziert auf das Problem in einemGraphen den Pfad mit minimalen Kosten zu finden. Diese Problem betrachten wir kurz imnachsten Abschnitt.

4.4.1 Ein universeller Alignment-Algorithmus

Das Problem, einen optimalen Pfad zu finden, konnen wir ebenfalls mit dynamic program-ming losen.

Wir definieren C(v) als die minimalen Kosten aller Pfade von v nach v. Offensichtlich istC(v) = 0. Dann, fur alle v 6= v in topologisch sortierter Reihenfolge:

C(v) = minw:w→v∈E

C(w) + cost(w → v)

W (v) = argminw:w→v∈EC(w) + cost(w → v)

Losung (opt. Kosten): C(v•) Losung (opt. Pfad): v• → w(v•)→ w(w(v•)) . . . wk(v•)→ v

Wir konnen alternativ auch einen Score maximieren, anstatt Kosten zu minimieren.

4.5 Suche eines Musters P in einem Text t

Wenn wir nach einem gegebenen Patten in einem Text suchen wollen, ist es nicht zielfuhrend,die Edit-Distanz bzw. ein globales Alignment des Textes und des Musters zu berechnen, dawir ja wollen, dass das Muster an jeder beliebigen Stelle im Text beginnen darf. Wir mussendie Definition unserer Tabelle D auf die veranderte Situation anpassen. Wir definieren D[i, j]nun als die minimale Edit-Distanz des Prafixes P [. . . i] mit einem Teilstring T [j′ . . . j] mitj′ ≤ j + 1. Daraus ergibt sich D[0, j] = 0 fur 0 ≤ j ≤ n. Sinnvollerweise erfolgt die Berech-nung der Tabelle spaltenweise. Eine andere Moglichkeit besteht darin, den in Abschnitt 4.4.1beschriebenen Algorithmus auf den in Abbildung 4.3 gezeigten Alignmentgraphen anzuwen-den.

Wir behandeln jetzt eine Verbesserung von Ukkonen (1985). Wenn eine Fehlerschranke kvorgegeben ist, so mussen wir nicht die komplette DP-Tabelle berechnen, da wir nur an denSpalten interessiert sind, in denen ein Wert kleiner gleich k in der untersten Zeile steht.Formal definieren wir:

lastk(j) := maxi : Dij ≤ k,Di′,j > k fur alle i′ > i.

39


Abbildung 4.3: Beispiel fur einen Alignmentgraphen fur ein semi-globales Sequenzalignment,d.h. zur Suche nach approximativen Vorkommen eines Patterns in einemText.

Werte D[i, j] mit i > lastk(j) mussen nicht berechnet werden. Dieser Sachverhalt ist inAbbildung 4.4 illustriert. Die Frage ist naturlich, wie man die Funktion lastk berechnen kann(ohne die komplette Spalte der Tabelle zu kennen). Fur die erste Spalte ist die Berechnungvon lastk einfach, denn D[i, 0] = i fur alle i und damit lastk(0) = k. Fur die weiteren Spaltennutzen wir aus, dass sich benachbarte Zellen (bei der Verwendung von Einheitskosten) immermaximal um eins unterscheiden konnen (was man mit einem Widerspruchsbeweis zeigenkann). Das bedeutet, dass lastk von einer Spalte zur nachsten um maximal eins ansteigenkann: lastk(j + 1) ≤ lastk(j) + 1.

Der gesamte Algorithmus (ohne Verwendung von lastk) benotigt O(mn) Zeit und O(m)Platz wenn nur die Endpositionen der Matches berechnet werden sollen. Die Verwendungvon lastk bringt bei (relativ) kleinen k und (relativ) großen m in der Praxis tatsachlicheinen Vorteil. Man kann beweisen, dass der erweiterte Algorithmus auf zufalligen Texteneine erwartetet Laufzeit von O(kn) hat.

1 def semiglobal_alignment(pattern ,text ,allowed_errors ):2 # initialisiere erste Zeile mit Nullen3 D = [ (len(text )+1)*[0] ]4 # initialisiere den Rest der DP-Tabelle mit ’inf’5 for k in xrange(len(pattern )):6 D.append ((len(text )+1)*[ float(’infinity ’)])7 # fuelle erste Spalte aus8 last_k = allowed_errors9 for i in xrange(last_k +1):

10 D[i][0] = i11 # schleife ueber alle zeilen der DP-Tabelle12 match_positions = []13 # iteriere ueber alle spalten (bis auf 0.)14 for col in xrange(1,len(text )+1):15 new_last_k = 016 # iteriere ueber alle zeilen (bis auf 0.)17 for row in xrange(1,min(last_k+1,len(pattern ))+1):18 D[row][col] = min([

40

4.6”Free End Gaps“-Alignment

0 0 0 0 0 0 0 0 0 0 0

1 1 0 1 1 0 1 0 1 1 0

2 1 1 1 1 1 0 1 0 1 1

3 2 2 1 2 2 1 1 1 0 1

4 3 3 2 1 2 2 2 1 1 1

5 4 3 3 2 1 2 2 2 2 1

M

A

O

A

M

A M O A M A M A O M

Abbildung 4.4: DP-Tabelle fur ein semi-globales Sequenzalignment des Patterns MAOAM mitdem Text AMOAMAMAOM. Die blaue Linie entspricht der lastk-Funktion fureinen maximal erlaubten Fehler von k = 1, d.h. fur alle Zellen D[i, j] unterder Linie gilt: i > lastk(j). In rot gekennzeichnet sind die durch Backtracinggewonnenen Alignments der beiden gefundenen Treffer.

19 D[row -1][ col]+1,20 D[row][col -1]+1 ,21 D[row -1][col -1]+1*( pattern[row -1]!= text[col -1])22 ])23 if D[row][col]<= allowed_errors:24 new_last_k = row25 last_k = new_last_k26 if D[len(pattern )][ col]<= allowed_errors:27 match_positions.append(col -1)28 return match_positions

Obiger Quelltext gibt die Positionen im Text zuruck, an denen Matches mit weniger alsallowed errors enden. Bei Bedarf konnte man Code hinzufugen, um fur jede dieser Posi-tionen durch Traceback ein Alignment zu ermitteln.

4.6”

Free End Gaps“-Alignment

Um die Frage zu beantworten, ob sich 2 Stucke DNA (mit Fehlern) uberlappen, benotigenwir eine weitere Variante unseres Alignment-Algorithmus. Wir wollen also Gaps am Endebzw. am Anfang nicht bestrafen (daher der Name free end gaps). Wir benutzen folgendesPunkteschema: End Gaps: 0; innere Gaps: -3; Mismatch: -2; Match: +1. Wichtig ist, dass einMatch einen positiven Score bekommt, da sonst immer das leere Alignment zuruckgeliefertwurde.

Auch das ”Free End Gaps“-Alignment ist ein Spezialfall des Algorithmus in Abschnitt 4.4.1.Der zugehorige Alignment-Graph findet sich in Abbildung 4.5.

41


Abbildung 4.5: Beispiel fur einen Alignmentgraphen fur ein free-end-gap-Sequenzalignment.

4.6.1 Lokales Alignment

Beim lokalen Alignment von s, t ∈ Σ∗ suchen wir Teilstrings s′ (Teilstring von s) und t′

(Teilstring von t), die sich optimal global alignieren lassen. Dieses Problem wurde von Smithand Waterman (1981) formuliert und mittels DP gelost. Ein naiver Ansatz ware es, fur allePaare von Teilstrings von s und t ein globales Alignment zu berechnen. Um den universel-len Algorithmus aus Abschnitt 4.4.1 nutzen zu konnen, stellen wir wieder einen AlignmentGraphen auf. Die einzige notige Anderung ist das Hinzufugen von Initialisierungs- und Fi-nalisierungskanten:

• Initialisierungskanten: v → (i, j) fur 0 ≤ i ≤ m und 0 ≤ j ≤ n• Finalisierungskanten: (i, j)→ v• fur 0 ≤ i ≤ m und 0 ≤ j ≤ n

Explizite Formulierung Der Ubersichtlichkeit halber schreiben wir den Algorithmus nocheinmal explizit auf (auch wenn dies ein Spezialfall des universellen Algorithmus ist). Wirnehmen an, dass der Score fur ein Gap negativ ist (Gaps werden also bestraft). In folgendemCode wird ein Match mit +1 und ein Mismatch oder Gap mit -1 bewertet.

1 def local_alignment(s,t):2 # initialisiere zunaechst nur die erste Zeile der DP-Tabelle3 D = [ (len(t)+1)*[0] ]4 # schleife ueber alle zeilen der DP-Tabelle5 best , best_row , best_col = 0,0,06 for row in xrange(1,len(s)+1):7 # lege zunaechst neue zeile an8 D.append( (len(t)+1)*[0] )9 # iteriere ueber alle spalten

10 for col in xrange(1,len(t)+1):11 D[row][col] = max([12 0,13 D[row -1][ col]-1,14 D[row][col -1]-1,15 D[row -1][col -1] -1+2*(s[row -1]==t[col -1])

42

4.7 Allgemeine Gapkosten

16 ])17 if D[row][col] > best:18 best , best_row , best_col = D[row][col], row , col19 # traceback durch die Matrix um das Alignment zu gewinnen20 row ,col = best_row , best_col21 alignment = []22 while ((row >0) or (col >0)) and (D[row][col]>0):23 if (row >0) and (col >0)24 and (D[row][col] == D[row -1][col -1] -1+2*(s[row -1]==t[col -1])):25 alignment = [(s[row -1],t[col -1])]+ alignment26 row ,col = row -1,col -127 elif (col >0) and D[row][col] == D[row][col -1] -1:28 alignment = [(’-’,t[col -1])]+ alignment29 row ,col = row ,col -130 else:31 alignment = [(s[row -1],’-’)]+ alignment32 row ,col = row -1,col33 return best , alignment

4.7 Allgemeine Gapkosten

Bisher hat ein Gap der Lange ` einen Score von g(l) = −γ · `, wobei γ ≥ 0 die Gapkostensind. Diese Annahme ist bei biologischen Sequenzen nicht sonderlich realistisch. Besser istes, die Kosten fur das Eroffnen eines Gaps hoher anzunehmen als die fur das Verlangerneines Gaps. Eine relativ einfache aber schon bedeutend realistischere Modellierung erreichenwir mit affinen Gapkosten:

g(`) =

−c− γ(`− 1) fur l > 0.0 fur l = 0,

dabei gibt die Konstante c den gap open penalty und γ den gap extend penalty an.

Eine weitere Moglichkeit sind die konvexen Gapkosten, dabei ist g(`) konkav, z.B. g(`) =− log(1 + γ`). Konvexe Gapkosten fuhren zu einer Laufzeit von O(mn log(mn)); den Algo-rithmus uberspringen wir jedoch.

Im Falle allgemeiner Gapkosten, d.h. wir machen keine Einschrankungen die Funktion gbetreffend, ergibt sich einen Laufzeit von O

(mn(n+m)

), denn wir mussen in jeder der mn

Zellen unserer DP-Tabelle O(n+m) mogliche Vorganger untersuchen.

4.7.1 Algorithmus zum globalen Alignment mit affinen Gapkosten

Wir entwickeln nun einen Algorithmus fur eine Alignment mit affinen Gapkosten mit einerLaufzeit von O(mn). Wir wahlen d ≥ e ≥ 0, wobei d der gap open penalty und e der gapextend penalty sind. Die Idee ist, jeden Knoten des Alignmentgraphen (und damit die DP-Tabelle) zu verdreifachen. Wir bezeichnen den optimalen Score eines Alignments der Prafixes[. . . i] und t[. . . j] wieder mit S

((i, j)

). Zusatzlich definieren wird:

43


V((i, j)

):= max

score(A)

∣∣∣∣ A ist ein Alignment von s[. . . i] und t[. . . j]das mit einem Gapzeichen (–) in t endet

,

H((i, j)

):= max

score(A)

∣∣∣∣ A ist ein Alignment von s[. . . i] und t[. . . j]das mit einem Gapzeichen (–) in s endet

.

Dann ergibt sich

S((i, j)

)= max

S((i− 1, j − 1)

)+ score(s[i], t[j]), V

((i, j)

), H((i, j)

).

4.8 Alignments mit Einschrankungen / suboptimale Alignments

Wir behandeln nun die Frage, wie Alignments gefunden werden konnen, wenn ein (odermehrere) Punkte auf dem Alignmentpfad vorgegeben sind. Wir stellen also die Frage nachdem optimalen Pfad, der durch einen Punkt (i, j) verlauft. Die Losung erhalten wir, indemwir zwei globale Alignements berechnen:

(0, 0)→ (i, j) und (i, j)→ (m,n)

Etwas schwieriger wird das ganze, wenn wir dies fur alle Paare (i, j) berechnen wollen. Dernaive Ansatz, einfach fur jeden Punkt (i, j) die beiden Alignments zu berechnen, brauchteO(m2n2)Zeit. Der Schlussel zu einer besseren Laufzeit ist die Beobachtung, dass der Score des opti-malen Pfades von (0, 0) nach (i, j) fur alle (i, j) in der DP-Tabelle gespeichert sind, d.h. dieLosung ”der ersten Halfte“ des Problems konnen wir einfach ablesen. Um auch den optima-len Score von (i, j) nach (m,n) einfach ablesen zu konnen, brauchen wir nur die DP-Tabellefur das Alignment der reversen Strings zu berechnen.

4.9 Globales Alignment mit linearem Platzbedarf

Sei j(i) der kleinste Spaltenindex j, so dass das optimale Alignment durch (i, j) geht. Findej(m/2), indem die obere Halfte der Matrix vorwarts, die untere ruckwarts berechnet wird.Addiere Vorwarts- und Ruckwarts-Scores fur Zeile m/2. Dabei ist

j(m

2

)= min argmax

Sm

2,j : 0 ≤ j ≤ n

Dadurch haben wir das Problem in zwei Teilprobleme zerlegt, die wir rekursiv losen konnen:

1. Alignment von (0, 0)→ (m/2, j(m/2))

2. Alignment von (m/2, j(m/2))→ (m,n)

Platzbedarf: O(n) +O(n) = O(n)

Zeitbedarf: O(mn+mn/2 +mn/4 + · · · ) = O(2mn)

44

4.9 Globales Alignment mit linearem Platzbedarf

0 j(i) j(m/2) n0

i

m/2

m

Abbildung 4.6: Zerlegung des Problems des globalen Sequenzalignments in zwei Teilproble-me. Die grauen Bereiche brauchen nicht weiter betrachtet zu werden.

4.9.1 Lokales Alignment mit linearem Platzbedarf

Sobald bekannt ist, dass das optimale Alignment von (istart, jstart) → (iend, jend) lauft, sobrauchen wir nur ein globales Alignment auf diesem Ausschnitt zu berechnen. Die Schwie-rigkeit besteht aber darin, dieses Fenster zu bestimmen.

1. Idee

• Vorwarts: argmaxi,j Sij liefert Endpunkt,

• Ruckwarts: argmaxi,j Sij liefert Startpunkt,

• Problem: evtl. gibt es mehrere gleich gute Alignments.

2. Idee Definiere start(i, j) als die Koordinaten (i′, j′) des Startpunktes des optimalenAlignments, das in (i, j) endet. Die Idee besteht nun darin, fur jede Zelle den Wert vonstart(i, j) parallel zum Scorewert S(i, j) zu verwalten.

S(i, j) = max

0 → start(i, j) = (i, j)

S(i− 1, j − 1) + score

(si

tj

)→ start(i, j) = start(i− 1, j − 1)

S(i− 1, j)− γ → start(i, j) = start(i− 1, j)S(i, j − 1)− γ → start(i, j) = start(i, j − 1)

45


4.10 Probleme des lokalen Alignments

1. Wann ist ein Score ”hoch genug“? Auch zufallige Sequenzen haben Score großer gleich0.

2. Schatten-Effekt: Es kann dazu kommen, dass ein langeres Alignment mit relativ vielenMismatches und InDels einen besseren Score hat als als ein kurzeres Alignments dasaber fast ausschließlich aus Matches besteht. Moglicherweise ist das kurzere Alignmentbiologisch interessanter.

3. Mosaik-Effekt: wenn sich einzelne Bereiche sehr gut alignieren lassen, dazwischen aberBereiche liegen, die sich nicht/schlecht alignieren lassen kann es dazu kommen, dassein langes Alignment, bestehend aus den guten und den schlechten Bereichen, einenbesseren Score hat als die guten Bereiche jeweils alleine.

Der Grund fur Schatten- und Mosaik-Effekt liegt darin, dass die Zielfunktion (also der Ali-gnmentscore) additiv ist:

Score(Alignment) =∑

Score(Spalten)

Eine Alternative liegt z.B. im langennormalisiertem Alignment: d.h. wir maximieren denQuotienten score

Laenge+L dabei ist L eine konstante, z.B. L = 200. Problem: nun konnen wir denbesprochenen DP-Algorithmus nicht mehr anwenden. Losung: Umformulieren in die FormScore−λ(Laenge+L) fur ein λ ∈ R, λ > 0. Das Problem ist aquivalent zu einem ”normalen“Alignment, wobei der Score abhangig von λ ist. Es gibt aber immer ein λ > 0, so dass diesaquivalent zum langennormalisierten Alignment-Problem ist.

Zu 1: Eine wichtige Frage ist in diesem Zusammenhang, wie die Verteilung der Scores vonAlignements zufalliger Sequenzen aussieht. Annahmen:

• Score(Match) > 0,

• Score(Gap) < 0,

• Erwarteter Score fur zwei zufallige Zeichen < 0.

Dann gilt fur große t und m,n→∞:

P(Score ≥ t) ≈ K ·m · n · e−λt,

dabei sind K > 0 und λ > 0 Konstanten abhangig vom Score-System und dem Textmodell.Eine wesentliche Beobachtung ist hier, dass sich die Wahrscheinlichkeit einen Score ≥ t zuerreichen, ungefahr verdoppelt, wenn wir die Lange einer der Sequenzen verdoppeln.

4.11 Four-Russians-Trick

Annahmen:

• Alphabetgroße σ ist klein: O(1),

• Wertebereich der Score-Funktion ist klein, z.B. c = |−1, 0,+1| = 3,

• Der Einfachheit halber: m = Θ(n).

46

4.11 Four-Russians-Trick

0 n0

m

t

t

Abbildung 4.7: Four-Russians-Trick: Zerlegung der Alignmentmatrix in uberlappende Blockeder Große t × t. Der Uberlappungsbereich ist jeweils grau hinterlegt. Zurbesseren Unterscheidung sind die Blocke verschieden eingefarbt.

Die Idee besteht darin, die DP-Tabelle in uberlappende t × t-Blocke zu zerlegen und dieseBlocke vorzuberechnen (siehe Abbildung 4.7). Insgesamt existieren (nach Abzug des Start-werts oben links in jedem Block) nur (cσ)2t verschiedene Blocke. Das resultiert in einemAlgorithmus mit Laufzeit von O(n2/t2). Die Frage ist nun, wie t zu wahlen ist, damit dasVorberechnen noch durchfuhrbar ist. Oder asymptotisch ausgedruckt: die Große der Tabellesoll nicht exponentiell in n wachsen, aber trotzdem großer als O(1) sein, so dass die Laufzeitdes Gesamtalgorithmus sich verbessert. Wir wahlen t = log(cσ)2 n. Wir gehen von einemRAM-Modell aus, d.h. die Blocke konnen von 0..n durchnummeriert werden und ein Zugriffauf einen Block benotigt O(1) Zeit.

47


48

KAPITEL 5

Hidden-Markov-Modelle (HMMs)

Beispiel: zwei Wurfel 1x je 1/6, einmal Wk fur 1-5: 1/5 Wk. fur Wechsel des 1/10.

Markov-Kette:

• Zustande Z = s, t, k, . . .• Ubergangswahrscheinlichket (ast)

• Startzustand bzw. Startwahrscheinlichkeiten a0s

• Emissionen V

• Emissionswahrscheinlichkeiten je Zustand ek(b) fur k ∈ Z und b ∈ V

Ein HMM liefert zwei stochastische Prozesse:

• Zustandsprozess/Pfad: π = π1π2π3 . . . = (πi) (versteckt, engl. hidden)

• Emissionsprozess: X = X1X2X3 . . . = (Xi) (beobachtet)

Wahrscheinlichkeit fur (π, x), feste Lange L:

P(π, x) =2∏i=1

aπi−1πi · eπi(xi)

Drei Probleme:

1. Welches π maximiert P(π, x)? π∗ argmaxπ P(x, π)

2. Berechne P(x) =∑

Alle Pfade π P(π, x)

3. Berechne die bedingte Wahrscheinlichkeit P(πi = k |x). Achtung: Haufig ist P(πi =k |x) maximal fur ein k 6= π∗i .

49

5 Hidden-Markov-Modelle (HMMs)

1: 1/6

4: 1/6

2: 1/63: 1/6

5: 1/66: 1/6

1: 1/5

4: 1/5

2: 1/53: 1/5

5: 1/56: 0

1-p

1-q

p q

Abbildung 5.1: Hidden-Markov-Modell (HMM), das eine Folge von Wurfen mit zwei ver-schiedenen Wurfeln modelliert. Jeder Wurfel wird durch einen Zustand re-prasentiert. Dabei ist der eine Wurfel fair, der andere unfair. Die Wahrschein-lichkeit, den Wurfel zu wechseln betragt 1− p bzw. 1− q.

Um Problem 2 zu losen, konnten wir, wie es die Formel suggeriert, die Summe uber dieWahrscheinlichkeiten aller Pfade berechnen. Dann ware die Laufzeit allerdings exponentiell.Die Losung bietet der Viterbi-Algorithmus.

5.1 Viterbi-Algorithmus

δt(i) := maxπ1...πt−1

P(π1 . . . πt−1, πt = i,X1, . . . , Xt),

dabei ist i ein Zustand und t ein Index in der Sequenz. Fur δ stellen wir eine Rekurrenz auf:

δ1(i) = a0i · ei(X1)δt(i) = max

j

(δt−1(j)aji

)· ei(Xt) fur t > 0

Beweis der Rekurrenz:≥: trivial.≤: Zu zeigen: Es gibt keine bessere Moglichkeit als einen optimalen Pfad zu verlangern.Annahme: es gibt einen Pfad π∗ = π∗1 . . . π

∗t−1i. Sei nun j = π∗t−1. π∗1..t−1 musste besser sein

als δt−1(j). Das ist ein Widerspruch.

Wie bei den Sequenzalignments erhalten wir den optimalen Pfad durch ein Traceback: injedem Schritt t < L speichern wir Φt(i) = argmaxj(δt−1(j) · aji), ΦL = argmaxj δL(i) Pfadruckwarts: ΦL,ΦL−1(ΦL),ΦL−2(ΦL−1), . . .

Viterbi zur Berechnung des optimalen Pfads:

vk(i) = maxπ1...πi−1

P(x1, . . . , xi, π1 . . . πi−1k)

vk(i+ 1) =(vk′(i) · ak′k · ek(xi+1)

TODO: Das ist doppelt. Aufraumen! Welche Notation nehmen wir jetzt? Analogzu PAAs?

50

5.2 Verweildauer in Zustanden

Forward-Algorithmus:

fk(i) =∑

π1...πi−1

P(x1, . . . , xi, π1 . . . πi−1k)

fk(i+ 1) =

(∑k′

fk′(i) · ak′k

)· ek(xi+1)

Vergleiche P(x, π∗) und P(x):

P(x) =∑π

P(x, π) = P(x, π∗) +∑π 6=π∗

P(x, π)(i)≥ P(x, π∗)

Dabei gilt fur (i) ungefahr Gleichheit, wenn P(x, π)/P(x, π∗) ≈ 0 fur alle π 6= π∗, d.h. dann,wenn es nur einen sinnvollen Pfad gibt (dies kommt aber in der Praxis selten vor).

Backward-Algorithmus:

bk(i) =P(xi+1 . . . xL, πi+1 . . . πL |πi = k)bk(L) =1

kk(i) =∑k′

akk′ · ek′(xi+1) · bk′(i+ 1)

Forward-Backward-Algorithmus zur Berchnung der bedingten Wahrscheinlichkeit P(πi =k |x). Der Satz von Bayes liefert uns:

Prob(πi = k |x) =Prob(πi = k, x)

P(x)=fk(i) · bk(i)

P(x)

πi = argmaxk fk(i) · bk(i)

Die Folge der πi gibt fur jeden Zeitpunkt den wahrscheinlichsten Zustand an, ist aber nichtnotwendiger Weise ein gultiger Pfad.

Falle;

• π∗i = πi: hohe Konfidenz,

• π∗i 6= πi: Vorhersage zweifelhaft.

Anwendung: CpG-Inseln. Im menschlichen Genom ist das Dinukleotid CG unterreprasentiert(d.h. es kommt selten vor) im Vergleich zu dem, was aufgrund der Haufigkeiten von C und Gzu erwarten ist. CpG-Inseln sind Bereiche in einem Genom, in denen CG sehr haufig ist. DasFinden von CpG-Inseln kann mit Hilfe von HMMs erfolgen. Dazu definiert man zwei Textmo-delle, eins fur CpG-Inseln und eins fur den Rest des Genoms. Diese beiden Modelle verbindetman zu einem HMM, das zwischen beiden Modellen wechseln kann. In Abbildung 5.2 ist einsolches Modell fur zwei Textmodelle erster Ordnung dargestellt. Angewendet auf ein konkre-tes Genom, ergibt sich mit Hilfe des Forward-Backward-Algorithmus fur jede Position dieWahrscheinlichkeit, dass diese Position Teil einer CpG-Insel ist.

51


A+ C+ G+ T+

A- C- G- T-

Modell für CpG-Inseln

Modell für Rest

hoheWahrscheinlichkeit

niedrigeWahscheinlichkeit

Abbildung 5.2: HMM zum Finden von CpG-Inseln in einem Genom. Nur zwei Kanten diesesvollstandig verbundenen Graphen sind dargestellt. Aber auch alle anderenUbergange haben eine Warhscheinlichkeit großer Null. Diese Parameter sinn-voll zu schatzen ist jedoch (besonders fur die Kanten vom oberen zum unterenTeil und umgekehrt) nicht einfach.

1.0 0.6 5/6 0.4 1.01234

0.40.10.30.2

T Wk.

0.4

1/60.6

Abbildung 5.3: Beispiel fur einen Teil eines HMMs, das mit Hilfe mehrere Zustande einebeliebige vorgegebene Verteilung der Verweildauer T realisiert. Dabei wer-den spezielle Zustande (rund) verwendet, die nichts emittieren (analog zuε-Transitionen bei NFAs).


Wir betrachten nochmal das Beispiel eines HMMs mit zwei Zustanden. Dabei modelliert dereine Zustand (F ) einen fairen, der andere Zustand (U) einen unfairen Wurfel (siehe Abbil-dung 5.1). Wir stellen die Frage, wie lange das Modell in einem der Zustande verweilt. ImFolgenden bezeichnen wir die Verweildauer im Zustand F mit TFair und das Wahrschein-lichkeitsmaß, dass sich auf eine Zustandsfolge bezieht, die im Zustand F beginnt, mit PFair.Dann gilt:

PFair(TFair ≥ 1) =1PFair(TFair ≥ 1 + t) =pt mit (t ≥ 0)PFair(TFair = 1 + t) =pt · (1− p) mit (t ≥ 0)

52


1.0 1-p 1-p 1-p 1-p

n-mal

pp p0.03

0.025

0.02

0.015

0.01

0.005

0

Wahrscheinlichkeit

0 20 40 60 80 100 120

Verweildauer

p=0.8n=10

Abbildung 5.4: Teil eines HMMs mit einer unimodalen Verteilung der Verweildauer. Dabeiwerden spezielle Zustande (rund) verwendet, die nichts emittieren (analog zuε-Transitionen bei NFAs). Je großer n, desto mehr nahert sich die Verteilungeiner Normalverteilung (zentraler Grenzwertsatz).

Fur die Verweildauer in einem Zustand ergibt sich also eine geometrische Verteilung. Es gibtjedoch Anwendungen, in denen dies unvorteilhaft ist. Wie also ist es moglich, ein Modell mitbeliebigen Verteilungen von Verweildauern zu realisieren? Ansatze:

• Speichere zu jedem Zustand die bisherige Verweildauer. Nachteil: Erhoht die Komple-xitat aller Algorithmen um den Faktor Tmax. Dabei ist Tmax die maximal moglicheVerweildauer. Interpretation: Jeder Zustand wird Tmax-mal dupliziert (siehe Abbil-dung 5.3).

• Durch Hintereinanderschalten von n Zustanden mit Selbstubergangen (deren Verweil-dauer daher jeweils geometrisch verteilt ist) lasst sich fur große n eine Verteilung rea-lisieren, die einer Normalverteilung nahe kommt. Allerdings ist die Verteilung linksabgeschnitten, d.h. die minimale Verweildauer betragt mindestens n. Eine solche Ver-teilung nennt man negative Binomialverteilung oder diskrete Gammaverteilung. DerErwartungswert betragt n/(1− p) (siehe Abbilung 5.4).

• Durch Parallelschalten der vorherigen Konstruktion lasst sich eine Mischung von uni-modalen Veteilungen (und daher eine multimodale Verteilung) realisieren.

53


54

KAPITEL 6

Indexstrukturen

Wenn wir in einem feststehenden Text (der Lange n) oft nach verschiedenen Mustern (derLange m) suchen wollen, dann kann es sinnvoll sein, den Text vorzuverarbeiten und eineIndexstrukur aufzubauen. Das kann einen Vorteil in der Gesamtlaufzeit bringen:

Online Index-basiertesPattern Matching Pattern MatchingO(m) O(n) VorverarbeitungO(n) O(m) Matching (ein Pattern)O(k(m+ n)

)O(n+ km) Matching (k Patterns)

Um naturlichsprachliche Texte zu indizieren (z.B. fur Suchmaschinen), bieten sich Wort-basierte Verfahren an. Beim Indizieren von biologischen Texten ohne Wortstruktur, bei-spielsweise DNA, benotigen wir Indexstrukturen, die die Suche nach beliebigen Teilstrings(ohne Rucksicht auf Wortgrenzen) erlauben. In diesem Kapitel geht es um Datenstrukturen,die das ermoglichen. Dafur gibt es zwei populare Indexstrukturen, namlich Suffixbaume undSuffixarrays.

6.1 Suffixbaume

Eigenschaften eines Suffixbaums des Strings s$ (dabei ist $ ein spezielles Zeichen, das dasEnde eines Strings markiert und an keiner anderen Stelle in s vorkommt):

• Bijektion Blatter ↔ Suffixe von s$.

• Ausgehende Kanten sind mit nicht-leeren Teilstrings von s$ annotiert.

55

6 Indexstrukturen

a b c a

b c a

c a b c a

032145

$

$

b c a $

b c a $

$

b c a $

c a

a

Abbildung 6.1: Suffixbaume fur die Strings cabca und cabca$. Es zeigt sich, dass das String-Ende-Zeichen dafur sorgt, dass fur jedes Suffix genau ein Blatt existiert.Die Zahlenfolge unter dem rechten Bild gibt die Positionen im Text an undentspricht dem Suffixarray (da in jedem Knoten die ausgehenden Kantensortiert sind).

• Ausgehende Kanten eines Knotens beginnen mit verschiedenen Buchstaben.

• Jeder innere Knoten hat ≥ 2 Kinder.

• Jeder Teilstring von s$ kann auf einem Pfad von der Wurzel ausgehend ”abgelesen“werden.

Abbildung 6.1 illustiert einen Suffixbaum und motiviert die Verwendung eines String-Ende-Zeichens. Die Kantenbeschriftungen konnen durch Indexpaare (i, j) reprasentiert werden(das Paar (i, j) entspricht dem Label s[i . . . j]) und benotigen daher nur konstanten Platz.Der Baum hat n Blatter; der Verwzeigungsgrad ist ≥ 2 in jedem inneren Knoten, d.h. esexistieren ≤ n−1 innere Knoten und ≤ 2(n−1) Kanten. Insgesamt benotigt ein Suffixbaumalso (nur) O(n) Platz, obwohl O(n2) Teilstrings indiziert werden.

Fur die Konstruktion eines Suffixbaums gibt es mehrere Moglichkeiten:

• Naiv: O(n2) durch Einfugen aller Suffixes in einen Trie.

• Ukkonen (1995): O(n), implementierbar, online (String kann verlangert werden).

6.1.1 Konstruktion in Linearzeit: Ukkonens Algorithmus

Ein Lauf des Algorithmus von Ukkonen (1995) ist in Abbildung 6.2 illustriert. Der Al-gorithmus arbeitet online, das bedeutet, nach jedem Schritt haben wir den Suffixbaum desjeweiligen Prafixes konstruiert. Die Kantenbeschriftungen werden durch ein Paar von Indizes

56

6.2 Suffixarrays

reprasentiert. Dabei steht das Ende-Zeichen E fur ”bis zum Ende des bis jetzt verarbeite-ten Strings“. Das gute daran ist, dass alle Kanten, die zu Blattern des Baumes fuhren, sichin jedem Schritt automatisch (in Zeit 0) um Eins verlangern. Dies ist einer der Tricks, dieeine lineare Laufzeit ermoglichen. Der Algorithmus verwaltet immer die sogenannte aktivePosition. Die aktive Position nach Phase i entspricht dem langsten Suffix von s[. . . i] dasauch Teilstring von s[. . . i− 1] ist. Ausgehend von der aktiven Position wird gepruft, ob dasanzuhangede Zeichen von dort aus gelesen werden kann.

Wir betrachten nun die Konstruktion des Suffixbaumes von s = babacacb$ genauer (sieheAbbildung 6.2). Der Algorithmus startet zunachst nur mit der Wurzel. In den ersten beidenSchritten werden jeweils zwei neue Blatter eingefugt, weil von der Wurzel aus weder a noch bgelesen werden konnen. Beim Anfugen der Buchstaben 2 und 3 verschiebt sich die aktivePosition jeweils um Eins, da die Buchstaben im Baum gelesen werden konnen. Beim Einfugenvon Position 4 (c) kann kein c unterhalb der aktiven Position gefunden werden. Daher mussein neuer Knoten eingefugt werden. Der zur aktiven Position gehorende String (also dieKantenbeschriftungen von der Wurzel bis zu dieser Position) verkurzt sich um Eins: aus bawird a die Verbindung von ba nach a heißt Suffixlink. Suffixlinks werden fur alle innerenKnoten gespeichert. Auch von der Position a im Baum kann kein c gelesen werden: Es wirdnoch ein neues Blatt eingefugt und die aktive Position verschiebt sich zur Wurzel. Auchdort wird ein Blatt eingefugt und Phase 4 ist damit abgeschlossen. Die restlichen Phasenverlaufen analog.

Die Operation ”Gehe zum nachsten Suffix“ benotigt amortisiert O(1) Zeit pro Phase. Beim

”Hinuntergehen“ von Knoten zu Knoten springen, richtige Kanten auswahlen bis gewunschteTiefe erreicht.

Anwendung. Finde langsten gemeinsamen Substring zweier Strings. Baue den Suffixbaum(mit Suffix-Links) eines Strings und suche ihn nach dem anderen String ab. Immer wennkein zusatzliches Zeichen gelesen werden kann, entferne vorne ein Zeichen durch Folgen vonSuffix-Links.

6.2 Suffixarrays

Wie eben gesehen, hat eine Suffixbaum einen Platzbedarf vonO(n). Allerdings ist die inO(n)versteckte Konstante verhaltnismaßig groß. Eine Moglichkeit, die Konstante zu verkleinern,bieten Suffixarrays. Ein Suffixarray eines Strings s$ ist definiert als die Permutation pos von0, . . . , n − 1, die die Startpositionen der Suffixe in lexikographischer Reihenfolge angibt.Zum Beispiel ist (5, 4, 1, 2, 3, 0) das Suffixarray des Strings cabca$.

Das Suffixarray enthalt also dieselben Informationen wie die unterste Ebene eines Suffix-baums (siehe Abbildung 6.1). Um die restliche Struktur des Baumes zu speichern, benotigenwir ein zweites Array, das sogenannte lcp-Array, das die gemeinsame Prafixlange von zweiim Suffixarray benachbarten Suffixen angibt. Formal:

lcp[r] := max|x| : x ist Prafix von S[pos[r − 1] . . .] und von S[pos[r] . . .]lcp[0] =lcp[n] := −1

57

6 Indexstrukturen

r pos[r] lcp[r] Suffix0 5 -1 $1 4 0 a$2 1 1 abca$3 2 0 bca$4 3 0 ca$5 0 2 cabca$6 – -1 –

Pattern-Matching-Probleme und ihre Laufzeit:

1. Finde P ∈ Σm im Suffixbaum.

a) Kommt P uberhaupt vor? → O(m)b) Wie oft? → O(m+ z) bzw. mit Zusatzinformationen O(m)c) Wo uberall? → O(m+ z)

2. Finde P ∈ Σm im Suffixarray.→ Beobachtung: Pattern P entspricht einem r-Intervall [L,R] im Suffixarray.

a) Kommt P uberhaupt vor? → O(m log n) mittels binarer Suche von L und R.b) Wie oft? → +O(1) denn z = R− L+ 1c) Wo uberall? → +O(z) : pos[L], . . . , pos[R]

Dabei ist z die Anzahl der Vorkommen des Patterns im Text.

58

6.2 Suffixarrays

Phase 1 ("ba"):

Phase 7 ("babacacb"):

Initialisierung: Phase 0 ("b"):

b

(0:E)

ba

(1:E) (0:E)

a

Phase 2 ("bab"):

ba

(1:E) (0

:E)

ab

b

Phase 3 ("baba"):

ba

(1:E) (0

:E)

ab

b

aa

Phase 4 ("babac"):

c(4:E)

b

a(0:2)

b

(2:E)

c

(4:E)

a

(1:2)

c

(4:E)

b

(2:E)

a

c

a

c

Phase 5 ("babaca"):

c

(4:E)

b

a

(0:2)

b

(2:E)

c

(4:E)

a

(1:2)

c(4:E)

b(2:E)a

c

a

c

a

a

aa

a

Phase 6 ("babacac"):

c

(4:E)

b

a

(0:2)

b

(2:E)

c

(4:E)

a

(1:2)

c

(4:E)

b

(2:E)

a

c

a

c

a

a

a

a

a

c cc c

c

Phase 6 ("babacac"):

c

(4:E)

b

a

(0:2)

b

(2:E)

c

(4:E)

a

(1:2)

c

(4:E)

b

(2:E)

a

c

a

c

a

a

a

a

a

c cc c

c

c

(7:E)

b

a(0:2)

b(2:E)

c

(4:E)

a

(1:2)

c

(5:E)

b

(2:E)

(4:5)

b

(7:E)

a

c

b

(4:5)

b

(5:E)

a

c

b

a

c

b

a

c

a

c

b

a

c

a

c

b

Phase 8 ("babacacb$"):

c

(7:E)

b

a

(0:1)

b

(2:E)

c

(4:E)

a(1:

2)

c

(5:E)

b

(2:E)

(4:5)

b

(7:E)

a

c

b

(4:5)

b

(5:E)

a

c

b

a

c

b

a

c

a

c

b

a

c

a

c

b

$

$ $$

$

$ $ $

$

(8:E)

(8:E)

(1:2)

Abbildung 6.2: Schrittweise Konstruktion des Suffixbaumes von s = babacacb$ mittels Uk-konens Algorithmus. Die jeweils aktive Position ist mit einem roten Kreisgekennzeichnet. Suffixlinks sind grun dargestellt. Die schwarzen Kantenbe-schriftungen dienen lediglich der besseren Ubersicht, gespeichert werden dieblau eingezeichneten Indexpaare, dabei steht E fur das Ende des Strings.

59

6 Indexstrukturen

60

KAPITEL 7

Statistik der Mustersuche in Sequenzen

Unter einem Sequenzmotiv verstehen wir allgemein eine endliche (meist kleine) Menge vonStrings, die wir auch bei der Mustersuche als Muster verwenden. Diese Menge muss nichtexplizit (aufzahlend) gegeben sein, sondern kann auch zunachst implizit beschrieben sein,etwa als die Menge aller Strings mit Hamming-Distanz hochstens 2 zu einem gegebenenString.

Wie wir ein Motiv oder Muster in einem Text finden, haben wir bereits gesehen. In diesemKapitel geht es um die Berechnung von entsprechenden Wahrscheinlichkeiten in zufalligenTexten. Dazu fuhren wir zunachst verschiedene Textmodelle ein (auch Nullmodelle oderHintergrundmodelle genannt). Dann betrachten wir ein Beispiel, das in die Fragestellungeinfuhrt (“Wie wahrscheinlich ist es, dass ein gegebenes Motiv genau (mindestens) k-mal ineinem Zufallstext der Lange n vorkommt?”). Wir beschreiben eine systematische Methode(probabilistische arithmetische Automaten), die die Berechnung solcher Wahrscheinlichkeitenauf einfache Weise moglich macht.

7.1 Textmodelle

Es sei wie immer Σ ein endliches Alphabet.

Ein Textmodell P bzw. Pn ist ein Wahrscheinlichkeitsmaß, das jedem endlichen String sbzw. jedem String fester Lange uber Σ eine Wahrscheinlichkeit P(s) bzw. Pn(s) zuweist. Wirunterscheiden zwischen Modellen (eigentlich Modellfamilien), die dies fur jede Stringlangen getrennt tun (die Lange also nicht mitmodellieren, sondern als anzugebenden Parameterbetrachten), und Modellen, die die Lange modellieren. Im ersteren Fall gilt

∑s∈Σn Pn(s) = 1

fur alle n ≥ 0; im letzteren Fall gilt dagegen∑

s∈Σ∗ P(s) = 1. Wir betrachten in diesem

61

7 Statistik der Mustersuche in Sequenzen

Abschnitt nur Modelle, bei denen die Lange n ein Parameter ist. Zur Vereinfachung schreibenwir P statt Pn, wenn n fest gewahlt ist.

Das i.i.d.-Modell oder M0-Modell. In diesem Modell wird jedes Zeichen in s = s1 . . . snunabhangig von den anderen und identisch verteilt erzeugt (i.i.d.: independently and iden-tically distributed). Dazu mussen wir angeben, mit welcher Wahrscheinlichkeit pa jeweilsZeichen a ∈ Σ gewahlt wird. Die Modellparameter sind also ein Wahrscheinlichkeitsvektorp = (pa)a∈Σ, und es ist

P(s) =n∏i=1

psi =∏a∈Σ

pnaa ,

wobei na := |i : si = a|. Setzt man zusatzlich voraus, dass auf Σ die Gleichverteilungvorliegt, also pa ≡ 1/|Σ| gilt, dann ist P(s) = 1/|Σ|n fur alle s der Lange n. Dies wird auchals i.i.d.-Modell mit Gleichverteilung oder als M00-Modell bezeichnet.

Beispiel 7.1 (M0-Modell). Wir betrachten das Alphabet Σ = a, b, c und die Vertei-lung p = (0.5, 0.3, 0.2). Das Auftreten des String s = abacab hat somit die Wahrscheinlich-keit

Pn(s) = pa · pb · pa · pc · pa · pb = p3a · p2

b · p1c = 0.00225 .

Bei der praktischen Anwendung werden solche Wahrscheinlichkeit schnell sehr klein; mogli-cherweise so klein, dass sie im Rechner nicht mehr mit double-Genauigkeit darstellbar sind.Deshalb rechnet mit in der Praxis oft mit logarithmierten Wahrscheinlichkeiten

log Pn(s) = log pa + log pb + log pa + log pc + log pa + log pb= 3 · log pa + 2 · log pb + 1 · log pc .

Auf diese Weise konnen auch sehr kleine Wahrscheinlichkeiten numerisch stabil berechnetwerden. ♥

Das Markov-Modell oder M1-Modell. Hierbei bilden die Zeichen in s eine homogene Mar-kovkette erster Ordnung, d.h. die Wahrscheinlichkeiten fur die Wahl des (i+ 1)-ten Zeichenshangen vom i-ten Zeichen ab (aber nicht von der Position i). Anzugeben ist also eine Wahr-scheinlichkeitsmatrix P = (pab)a,b∈Σ mit Zeilensummen

∑b∈Σ pab = 1 fur alle a ∈ Σ. Das

erste Zeichen wird nach gesondert anzugebender Verteilung p0 ausgewahlt. Damit ergibt sichals Wahrscheinlichkeit, dass genau s = s1 . . . sn erzeugt wird,

P(s) = p0s1 ·

n∏i=2

psi−1,si .

Unter der Voraussetzung pab > 0 fur alle a, b gibt es eine eindeutige stationare Verteilungπ = (πa)a∈Σ, die invariant gegenuber der Ubergangsmatrix ist, fur die also (als Zeilenvektor)π · P = π gilt. Sie berechnet sich als Losung des Gleichungssystems

π · (P − Id|Σ| | e) = (0 . . . 0 | 1);

dabei ist e der Vektor aus Einsen. Eine der ersten |Σ| Spalten ist uberflussig, da die ersten |Σ|Spalten linear abhangig sind.

62

7.1 Textmodelle

Beispiel 7.2 (M1-Modell). Sei wieder Σ = a, b, c und s = abacab. Sei ferner ein M1-Modell gegeben durch die Startverteilung p0 = (0.5, 0.3, 0.2) und die Ubergangsmatrix

P =

0.1 0.8 0.10.7 0.1 0.20.7 0.2 0.1

Die Wahrscheinlichkeit fur Auftreten von s berechnet sich nun durch

P(s) = p0a · Pa,b · Pb,a · Pa,c · Pc,a · Pa,b

= 0.5 · 0.8 · 0.7 · 0.1 · 0.7 · 0.8= 0.01568

♥

Das Mk-Modell. Statt nur einem Zeichen kann man auch allgemeiner k ≥ 1 Zeichen zuruckschauen, um die Wahrscheinlichkeiten fur das aktuelle Zeichen festzulegen. Die letzten kZeichen bezeichnet man dann auch als den aktuellen Sequenzkontext. Man erhalt das Mar-kovmodell k-ter Ordnung oder Mk-Modell. Man muss fur die Sequenzanfange ebenfalls Se-quenzkontexte von weniger als k Zeichen berucksichtigen. Zweckmaßigerweise schreibt mandie Ubergangswahrscheinlichkeiten py,b mit y ∈

⋃kk′=0 Σk′ und b ∈ Σ in eine |Σ|

k+1−1|Σ|−1 × |Σ|-

Matrix, aus der man fur jeden gegebenen Sequenzkontext der Lange k (und fur Anfangsstuckekurzerer Lange) die Wahrscheinlichkeiten fur das nachste Zeichen ablesen kann. Die Anzahlder hierfur festzulegenden Parameter erhoht sich exponentiell mit k. Da man diese Parame-ter im Normalfall aus vorhandenen Daten schatzen muss, verbieten sich zu hohe Werte vonk.

Wenn man wieder voraussetzt, dass das Modell stationar ist, kommt man mit einer |Σ|k×|Σ|-Matrix aus, da sich die entsprechenden Wahrscheinlichkeiten fur kurzere Kontexte berechnenlassen.

Markov-Modelle variabler Ordnung. Ein Kompromiss, um weniger Parameter zur Mo-dellbeschreibung zu benotigen, aber dennoch flexibel zu sein, ist, die Kontextlange abhangigvom Kontext variabel zu halten.

Beispiel: Wir betrachten das Alphabet a, b, c. Ist das letzte Zeichen a oder b, hangen dieWahrscheinlichkeiten fur das aktuelle Zeichen nur davon ab. Ist es aber c, betrachten wir dieKontexte ac, bc, cc, εc differenziert. Die entsprechenden Wahrscheinlichkeiten lassen sich ineinem Trie speichern, so dass man sie effizient findet, wenn man den aktuellen Kontext vonrechts nach links liest.

Beispiel 7.3 (Anwendung eines Markovmodells variabler Ordnung, aus Schulz et al. (2008)).Sei s = gattaca. Wir mochten nun die Produktionswahrscheinlichkeit von s unter dem durchAbbildung 7.1 gegebenen Modell bestimmen. Dabei verwenden wir immer den maximalmoglichen Kontext. Dabei bezeichnet ε den leeren Kontext.

P(s) = pε,g · pg,a · pa,t · pgat,t · ptt,a · pa,c · pε,a= 0.17 · 0.88 · 0.91 · 0.46 · 0.04 · 0.03 · 0.33

≈ 2.48 · 10−5

♥

63


a

g

t

tt

atgat

(0.46,0.04,0.04,0.46)

(0.32,0.03,0.03,0.62)

(0.04,0.46,0.46,0.04)

(0.2,0.2,0.2,0.4)

(0.88,0.04,0.04,0.04)

(0.03,0.03,0.03,0.91)

(0.33,0.09,0.17,0.41)

ε

Abbildung 7.1: Schematische Darstellung eines Markovmodells variabler Ordnung. In jedemKnoten steht der Kontext, der durch diesen Knoten reprasentiert wird. Dabeisteht ε fur den leeren Kontext. Die Knoten sind in rot mit der dazugehorigenWahrscheinlichkeitsverteilung (uber dem Alphabet Σ = a, c, g, t) anno-tiert. Quelle: Schulz et al. (2008).

7.2 Parameterschatzung fur Textmodelle

Die Berechnung der Wahrscheinlichkeit, dass ein String s ∈ Σn von einem Textmodell ge-neriert wird, ist unkompliziert. Haufig steht man jedoch vor dem umgekehrten Problem:Zu einem oder mehreren gegebenen Strings aus Σn soll z.B. das beste M0-Modell geschatztwerden.

Schatzung im M0-Modell Angenommen, es sind m Strings sj ∈ Σn gegeben, j = 1 . . .m.Gesucht sind die Parameter pa, a ∈ Σ unter der Bedingung pa ≥ 0 und

∑a pa = 1. Zur

Berechnung verwenden wir das Maximum-Likelihood-Kriterium, d.h. wir wahlen die pa, sodass die Gesamtwahrscheinlichkeit

∏Mj=1 P(sj) maximal wird. Es ist

∏mj=1 P(sj) =

∏a∈Σ pna

a

mit na :=∑m

j=1 |i : sji = a|. Logarithmieren fuhrt auf das Optimierungsproblem

Maximiere∑a∈Σ

na log pa

so dass∑a∈Σ

pa = 1.

Es hat die eindeutige Losung p∗a = na/∑

b nb. Sie stimmt mit der intuitiven Vorstellunguberein: p∗a ist die relative Haufigkeit des Symbols a in den gegebenen Texten.

Aufgabe 7.1. Rechne nach, dass p∗a = na/∑

b nb tatsachlich die Maximum-Likelihood-Schatzung fur pa ist.

64

7.2 Parameterschatzung fur Textmodelle

Schatzung im M1- und Mk-Modell. Analog schatzt man die Parameter im Markov-Modelloder allgemein im Mk-Modell: Bezeichnet ny mit y ∈ Σ∗ die Gesamtzahl der Teilstrings y inallen Texten, dann ist die ML-Schatzung fur px,a gerade

p∗x,a = nxa/nx (x ∈ Σk, a ∈ Σ).

Beispiel 7.4 (Schatzung eines M1-Modells). Auch wenn es nicht sinnvoll ist, ein Textmodellaus einem sehr kurzen Text zu schatzen, wollen wir dennoch tun um zu verdeutlichen wasdabei passiert. Sei unser Text s = abacab. Zunachstmal ergibt sich als M0-Modell (durchabzahlen der Buschstabenhafigkeiten) die Verteilung p = (3/6, 2/6, 1/6). Durch zahlen der2-mere erhalten wir die Matrix

P =

0 2/3 1/31 0 01 0 0

.

Dieses Beispiel verdeutlicht, dass fur das robuste Schatzen eines Textmodells genugend Be-obachtungen zur Verfugung stehen mussen. In unserem Fall ist das nicht der Fall: 5 Eintragein der Matrix sind 0, weil keine Beobachtungen vorliegen. ♥

Zur Schatzung der pz,a am Anfang der Sequenz (|z| < k) gibt es prinzipiell drei Moglichkeiten.

1. Sind sehr viele verschiedene Sequenzen gegeben, ist die ML-Schatzung als relativeHaufigkeit von a an der entsprechenden Position im entsprechenden Kontext moglich.

2. Eine Alternative ist, dass man die nxa mit |x| = k uber die ersten Zeichen summiert:

pz,a =∑

y∈Σk−|z|

nyza/∑

y∈Σk−|z|

nyz.

3. Eine andere Alternative, die numerisch zu ahnlichen, aber nicht identischen Ergebnis-sen wie die vorige Alternative fuhrt, ist die pz,a so zu bestimmen, dass die Markovkettestationar wird.

Schatzung von Markov-Modellen variabler Ordnung. Wenn man die Ordnung fur jedenKontext (also die Trie-Topologie) fest vorgibt, ist die Schatzung mit relativen Haufigkeiteneinfach moglich. Interessanter wird es, wenn man die (in einem zu definierenden Sinn) opti-male Kontextlange erkennen will. Dabei muss man sich nach zwei Kriterien richten:

1. Es mussen genug Beobachtungen fur den entsprechenden Kontext vorhanden sein (sa-gen wir als Faustregel, mindestens 100|Σ|), so dass die Verteilung des nachsten Zeichenssinnvoll bestimmt werden kann.

2. Fur festes x sollten sich mindestens zwei Verteilungen der Kontexte ax (a ∈ Σ) hinrei-chend unterscheiden, sonst ist die Einbeziehung von a sinnlos.

Wir behandeln die Details an dieser Stelle nicht und verweisen auf die Arbeiten von Schulzet al. (2008).

65


7.3 Momente der Anzahl der Treffer

In diesem Abschnitt wollen wir uns nun die Frage stellen, wie oft ein gegebenes Pattern ineinem Zufallstext vorkommt. Naturlich konnen wir daruber nur statistische Aussagen treffen.Wir berechnen zunachst den Erwartungswert und die Varianz der Anzahl der Treffer einesMotivs in einem Zufallstext der Lange n. Fur die Zufallstexte legen wir die in Abschnitt 7.1eingefuhrten Textmodelle zu Grunde.

7.3.1 Erwartete Anzahl Treffer

Als erste Aufgabe berechnen wir die erwartete Anzahl an Treffern (engl. matches) einesMotivs in einem Zufallstext der Lange n. Das Motiv bestehe zunachst aus einem einzelnenString M der Lange m.

Wir definieren Zufallsvariablen Xi := 1, wenn ein Treffer an Position i beginnt, und Xi := 0sonst. Dann ist X :=

∑n−m+1i=1 Xi die Zufallsvariable, die die beobachtete Anzahl an Treffern

zahlt. Es ist E[X] = E[∑n−m+1

i=1 Xi] =∑n−m+1

i=1 E[Xi] = (n − m + 1) · E[X1], und es istE[X1] = Pn(X1 = 1) = Pm(M), die Wahrscheinlichkeit, dass die ersten m Zeichen das Motivbuchstabieren.. Die Berechnung ist deswegen einfach, weil der Erwartungswert ein linearerOperator ist und mit Summen vertauscht werden kann.

Wenn das Motiv M = M1, . . . ,Mp aus p verschiedenen Strings gleicher Lange m be-steht, verwenden wir denselben Ansatz; nur berechnet sich E[X1] als die Summe der Ein-zelwahrscheinlichkeiten (was man wiederum mit Indikatorvariablen zeigen kann): E[X1] =∑p

j=1 Pm(Mj).

Besteht das Motiv aus Strings verschiedener Lange, funktioniert die Methode im Prinzipimmer noch, nur muss man die verschiedenen Langen beachten: Es sei M = M1, . . . ,Mpmit |Mj | = mj . Dann ist E[X] =

∑pj=1 (n−mj + 1) · Pmj (Mj).

Aufgabe 7.2. Beweise die Aussage E[X] =∑p

j=1 (n−mj + 1) ·Pmj (Mj) im Detail. (Verur-sacht der Fall, dass ein String ein Prafix oder Suffix eines anderen sein kann, wirklich keineProbleme?)

7.4 Die Verteilung der Anzahl der Treffer

Wir wenden uns jetzt der Berechnung der Verteilung der Anzahl der Treffer zu. Als Spezialfallbetrachten wir die Frage nach der Wahrscheinlichkeit, dass uberhaupt kein Treffer im Textvorkommt.

Beispiel 7.5 (Verteilung der Treffer eines Musters). Sei Σ = O,M,A; betrachte die MotiveM1 = OMAMA und M2 = MAOAM und z.B. die Textlange n = 9. Viele finden es verbluffend, dassdie Wahrscheinlichkeit, dass M1 nicht vorkommt, verschieden ist von der Wahrscheinlichkeit,dass M2 nicht vorkommt. Tatsachlich verteilen sich 0, 1 und 2 Vorkommen auf die 39 = 19683Strings wie folgt.

66


Anzahl AnteilMotiv 0 Treffer 1 Treffer 2 Treffer 0 Treffer 1 Treffer 2 TrefferOMAMA 19278 405 0 0.97942 0.02058 0.00000MAOAM 19279 403 1 0.97947 0.02047 0.00005

Die 405 Strings fur das nichtuberlappende OMAMA ergeben sich aus den 5 verschiedenen Start-positionen, an denen das Wort beginnen kann und die freie Wahl der verbleibenden 4 Zeichenim Wort; dabei wird kein String doppelt gezalt, da ein Vorkommen von OMAMA im String einweiteres ausschließt. Es ist in der Tat 5 · 43 = 405. ♥

Aufgabe 7.3. Man hatte moglicherweise damit rechnen konnen, dass die Verteilung beiMAOAM, wenn es schon einen einzelnen String mit 2 Treffern gibt, so aussieht: (19278, 404, 1),d.h., dass zumindest die Anzahl der Strings mit keinem Treffer gegenuber OMAMA unverandertist. Benutze ein einfaches Argument, um zu erklaren, warum das nicht sein kann.

Aufgabe 7.4. Konstruiere ein Minimalbeispiel (binares Alphabet, moglichst kurze Worter,kurzer Text) fur dasselbe Phanomen.

Wir beschreiben jetzt, ausgehend von einem deterministischen endlichen Automaten, eineKonstruktion, mit der sich nicht nur die Anzahlen (bzw. Anteile im M00-Modell), sondernallgemein die Trefferverteilung im M0, M1, bzw. Mk-Modell berechnen lasst: probabilistischearithmetische Automaten.

Die Idee ist, salopp formuliert, nicht in einem festen String nach einem Muster zu suchen,sondern in einem Zufallsstring. Wir verwenden also einen Automaten, der nicht in einemkonkreten Zustand ist, sondern in jedem Zustand mit einer bestimmten Wahrscheinlichkeit.Wir werden dann diese Wahrscheinlichkeitsverteilung Schritt fur Schritt aktualisieren. Wirwissen also zu jedem Zeitpunkt, mit welcher Wahrscheinlichkeit wir in welchem Zustandsind.

Wir fuhren jetzt das Konzept des probabilistischen endlichen Automaten formal einfuhren.

Definition 7.1 (PAA). Ein probabilistischer arithmetischer Automat (PAA) ist ein Tupel(Q, q0, T, E, (eq)q∈Q, N, n0, (θq)q∈Q

), dabei ist

• (Q, q0, T ) eine Markovkette, d.h.

– Q eine endliche Menge von Zustanden,– q0 ∈ Q ein Startzustand (wobei wir dies auch auf eine Startverteilung uber allen

Zustanden, q0 : Q→ [0, 1] mit∑

q∈Q q0(q) = 1, verallgemeinern konnen),– T = (Tq,q′)q,q′∈Q eine stochastische Matrix der Große Q×Q, d.h.

∑q′∈Q Tq,q′ = 1

fur alle q ∈ Q,

• (Q, q0, T, E, (eq)q∈Q) ein Hidden Markov Model (HMM), d.h.

– E eine endliche Menge von moglichen Emissionen,– eq : E → [0, 1] fur jedes q ∈ Q eine Wahrscheinlichkeitsverteilung, die fur jeden

Zustand angibt, wie wahrscheinlich jede Emission ist,

• N eine Menge von Werten,

• n0 ∈ N ein Startwert und

• θq : N × E → N fur jedes q ∈ Q eine Operation.

67


Ein PAA befindet sich zunachst im Startzustand q0 und der aktuelle Wert ist der Start-wert n0. In jedem Schritt findet gemaß der Matrix T ein Zustandsubergang statt; d.h. wennsich der Automat im Zustand q befindet, gibt Tq,q′ die Wahrscheinlichkeit an, dass sich derAutomat im nachsten Schritt im Zustand q′ befindet. Nach dem Zustandsubergang wirdeine Emission e gemaß der Verteilung eq′ gezogen und der neue Wert n = θq′(n′, e) ermittelt,dabei war n′ der vorige Wert.

Beispiel 7.6 (Einfacher PAA). Wir betrachten einen sehr einfachen Automaten, der unsAuskunft geben kann, wie groß die Summe der Augen nach einer bestimmten Anzahl anWurfelwurfen ist.

1: 1/62: 1/63: 1/64: 1/65: 1/66: 1/6

q0

1.0

Formal definieren wir unseren PAA durch. Q = q0, T = (1), E = 1, 2, 3, 4, 5, 6, eq0 ≡ 1/6,N = N, n0 = 0, θq0 : (v, e) 7→ v + e. ♥

Eine Moglichkeit die gemeinsame Verteilung von Zustanden und Werten (approximativ)zu bestimmen, ist das wiederholte Simulieren des Automaten. Wir konnten zum Beispiel1.000.000 mal eine Folge von Zustanden und Werten (gemaß T und eq usw.) ziehen und soeine empirische Verteilung erhalten. Im Folgenden werden wir einen anderen Weg beschreitenund die Zustands-Wert-Verteilung exakt berechnen.

Wir fuhren folgende Zufallsvariablen ein:

• Vt: Wert nach t Schritten

• Yt: Zustand nach t Schritten

• Zt: Emission in Schritt t

Der Wert nach t Schritten ist also gegeben durch Vt = θYt(Vt−1, Zt). Gesucht ist die Wahr-scheinlichkeit P(Yt=q, Vt=v). Fur t = 0 konnen wir die Wahrscheinlichkeit direkt angeben:

P(Y0 =q, V0 =v) =

1 wenn q = q0, v = n0,

0 sonst

Wir uberlegen nun, wie sich die gemeinsame Wahrscheinlichkeit von Zustand und Wert,P(Yt, Vt) in einem Schritt entwickelt:

P(Yt=q, Vt=v) =∑q′∈Q

∑(v′,z)∈θ−1

q (v)

P(Yt−1 =q′, Vt−1 =v′) · Tq′,q · eq(z) . (7.1)

Mit Hilfe dieser Rekurrenzgleichung konnen wir nun die Zustands-Wert-Verteilung schritt-weise aktualisieren. Wir verwalten dazu eine Tabelle der Dimension Q ×N . Die Verteilung

68


nach n Schritten zu berechnen dauert O(n · |Q|2 · |N | · |E|); dabei ist |N | oft durch O(n)oder eine Konstante beschrankt. Im Folgenden werden wir sehen, dass wir einen PAA leichtaus einem Aho-Corasick-Automaten konstruieren konnen. in dem Fall ist die Transitions-matrix T dunn besetzt; es gibt nur |Σ| ausgehende Kanten von jedem Zustand aus. Darausergibt sich fur diesen Spezialfall eine Laufzeit von O(n · |Q| · |Σ| · |N | · |E|)

Um die Verteilung der Anzahl der Matches auszurechnen, summieren wir uber alle Zustande

P(Vt = v) =∑q∈Q

P(Yt = q, Vt = v) .

Beispiel 7.7 (Spezialfall: Wie ist das im Fall 0 Matches, einzelner String?). TODO ♥

Wir haben gesehen, dass die Laufzeit linear von n abhangt. Wir mussen also in der Praxis nmal die Rekurrenz (7.1) auswerten. Das ist fur große n zeitintensiv. Wir behandeln jetzt einealternative Rekurrenz, die im Fall sehr großer n vorteilhaft ist. Diesmal verwalten wir einevierdimensionale Tabelle, die definiert ist durch

U (t)(q1, v1; q2, v2) = P(Yt=q2, Vt=v2|Y0 =q1, V0 =v1) .

Wenn wir U (t) kennen, konnen wir wieder unsere Ausgangsfrage nach der Zustands-Wert-Verteilung beantworten, denn nach Definition von U (t) ist

P(Yt = q, Vt = v) = U (t)(q0, n0; q, v) .

Die Funktion U (1) gibt die Wahrscheinlichkeit an, in einem Schritt von einem Zustands-Wert-Paar zu einem anderen zu kommen; d.h. U (1) konnen wir direkt aus den Komponentenunseres PAAs angeben:

U (1)(q1, n1; q2, v2) = Tq1,q2 ·∑

z∈E:θq2 (v1,z)=v2

eq2(z)

Die Idee ist nun, U (2·t) aus U (t) zu berechnen. Damit reduzieren wir die lineare Abhangigkeitvon n auf eine logarithmische Abhangigkeit. Die Verdopplung funktioniert folgendermaßen:

U (2·t)(q1, v1; q2, v2) =∑q′∈Q

∑v′∈N

U (t)(q1, v1; q′, v′) · U (t)(q′, v′, q2, v2) . (7.2)

Dabei berechnen wir also die Warscheinlichkeit in 2 · t Schritten von (q1, v1) nach (q1, v1) zugelangen, indem wir uber alle moglichen Zwischenzustande (q′, v′), die wir nach t Schrittenerreicht haben konnten, summieren. Auf diese Weise bekommen wir alle U (t) fur t = 2k,also fur alle Zweierpotenzen. Im Allgemeinen wollen wir jedoch U t fur beliebige t berech-nen. Das gelingt jedoch einfach, indem wir die Binardarstellung fur t betrachten und dieEntsprechenden U (2k) kombinieren.

Welche Laufzeit hat der resultierende Algorithmus? Offensichtlich hat sich die Anzahl dernotigen Schritte auf O(log2 n) verringert. Allerdings sind die einzelnen Schritte ”teurer“geworden. Eine Auswertung von (7.2) braucht O(|Q| · |N |) Zeit, denn wir haben zwei ver-schachtelte Summen, die uber alle Elemente von Q bzw. N summieren. Da wir (7.2) fur allemoglichen Kombinationen von Belegungen von q1, v1, q2 und v2 auswerten mussen, kommtnochmal ein Faktor von O(|Q|2 · |N |2) hinzu. Insgesamt ergibt sich also eine Laufzeit vonO(log2 n · |Q|3 · |N |3).

69


Bemerkung 7.1. Die vorgestellte Technik hilft bringt nur dann eine Verbesserung, wenn |N |nicht (oder nur schwach) von n abhangt. Im Fall von Pattern-Matching-Statistik, ist dasleider nicht immer gegeben. Wenn wir z.B. die Signifikanz eines Beobachteten Patterns be-rechnen wollen, dann hangt |N | indirekt von n ab, da in einem langeren Text moglicherweiseauch mehr Vorkommen eines Musters zu finden sind als in einem kurzen Text. In den meistenFallen ist es eine vernunftige Annahme, dass die Anzahl der Matches linear von n abhangt.Damit ist |N | in O(n) und wir haben nichts gewonnen. Ist |N | jedoch eine Konstante, zahltsich die vorgestellte Verdopplungstechnik fur hinreichend große n aus.

7.5 Analyse des Horspool-Algorithmus

Wir haben den Horspool-Algorithmus in Abschnitt 2.4.1 behandelt. Wir wollen nun einesehr detailierte Laufzeitanalyse vornehmen. Und zwar mochten wir fur ein gegebenens Pat-tern p und eine Textlange ` die Verteilung der Anzahl der gemachten Operationen berechnen.Das heißt, wir mochten zum Beispiel wissen, wie groß die Wahrscheinlichkeit ist, dass derAlgorithmus mehr als c Operationen benotigt. Auch hier mussen wir wieder ein Textmo-dell zugrunde legen. Im Fall des Horspool-Algorithmus sind die Operationen, die wir zahlenmochten, die Anzahl der Zugriffe auf den Text. Wir bezeichnen die Anzahl der Textzugriffebeim Durchsuchen des Textes s ∈ Σ∗ nach dem Pattern p mit ξp(s). Um das zu erreichendefinieren wir einen PAA, der den Horspool-Algorithmus simuliert. Komponenten:

• Q = Σm ∪ q0, dabei ist q0 der Startzustand,

• N = N × N, wir haben es also mit einer zweidimensionalen Wertemenge zu tun. EinWert v = (t, c) ∈ N bedeutet, dass sich die rechte Fenstergrenze an der Position tbefindet und bisher c Vergleiche benotigt wurden.

• E = 1, . . . ,m × 1, . . . ,m die Emissionen sind in unserem Fall deterministisch:jeder Zustand emittiert immer die Anderung, die wir am gerade gultigen Wert vorneh-men mussen, namlich εq =

(shift[qm−1], ξp(q)

), dabei ist ξp(q) die Zahl der notigen

Vergleiche im Fenster q.

Des Weiteren mussen wir noch eine Ubergangsfunktion δ und Operationen θq definieren. Dastun wir folgendermaßen:

θq((t, c), (t′, c′)

)=

(t+ t′, c+ c′) wenn t 6= • und t+ t′ ≤ `− 1(•, c+ c′) t 6= • und t+ t′ ≥ `(•, c) t = •

Wir definieren jetzt die Ubergangsfunktion δ(q, b) = q′. Dabei ist q = q0 . . . qm−2σ ist b ausΣshift(σ) und q′ := qshift(σ)...m−1b.

Behauptung: Auf einen gegebenen Text s berechnet dieser DAA genau ξp(s). Ist s “abge-arbeitet” (also q′ nicht definiert), hat der Wert die Form (•, c) und c = ξp(s).

Als nachstes betten wir ein Textmodell ein, d.h. wir ersetzen δ durch eine stochastischeMatrix auf Q×Q mit Tq,q′ = P(b) fur q′ = qshift(σ)...m−1b mit σ = qm−1; dabei erhalten wirdie Wahrscheinlichkeiten aus dem Textmodell.

70

7.5 Analyse des Horspool-Algorithmus

Wir haben also nun einen PAA konstruiert, der das Verhalten des Horspool-Algorithmusnachvollzieht und damit in der Lage ist, die Verteilung der Anzahl der Operationen exakt zuberechnen. Dafur konnen wir einfach die Algorithmen nutzen, die wir zur Berechnung derZustands-Wert-Verteilung von PAAs behandelt haben. Dabei ergibt sich eine Laufzeit vonO(Σ2m · `2 ·m).

71


72

KAPITEL 8

Exkurse

In diesem Kapitel kommen wir zu einigen durchaus interessanten Themen, die aber nichtzum zentralen Stoff der Vorlesung gehoren.

8.1 Erzeugende Funktionen

Erzeugende Funktionen konnen in einigen Fallen dazu verwendet werden, Rekurrenzen ge-schlossen zu losen, oder zumindest, um asymptotische Aussagen uber das Wachstum vonFunktionen zu machen. Gute Literatur hierzu ist “Generatingfunctionology” von Wilf ?oder die entsprechenden Kapitel in “‘Concrete Mathematics”’ von Knuth, Graham und Pa-tashnik ?. Wir beschreiben hier nur wenige einfache Eigenschaften und Moglichkeiten vonerzeugenden Funktionen.

Definition 8.1 (erzeugende Funktion). Wir ordnen einem Vektor (a0, . . . , an) das Poly-nom A(z) =

∑ni=0 aiz

i zu. Wir ordnen einer Folge (a0, a1, . . .) die (formale) PotenzreiheA(z) =

∑i≥0 aiz

i zuordnen. Wenn wir von formalen Potenzreihen sprechen, lassen wir Kon-vergenzbetrachtungen zunachst außer Acht. Die Funktion A(z) heißt erzeugende Funktionder Folge (ai).

Beispiel 8.1 (konstante Folge). Wir setzen ai ≡ 1 und erhalten A(z) =∑

i≥0 zi = 1

1−z(formal). Fur |z| < 1 konvergiert A(z) sogar und ist als die geometrische Reihe bekannt. ♥

Bemerkung 8.1. Wahrscheinlichkeitsverteilung Fur eine Wahrscheinlichkeitsverteilung (∑ai =

1, ai ≥ 0) istA(1) =

∑i≥0

ai · 1 = 1 .

73

8 Exkurse

Beispiel 8.2 (Gleichverteilung). Wir betrachten die Gleichverteilung auf 0, . . . , N − 1

A(z) =N−1∑i=0

1Nzi =

1N· 1− zN

1− z

ai =

1/N fur i = 0, . . . , N − 10 sonst

♥Beispiel 8.3 (Poissonverteilung). Die Poissonverteilung ist ein Grenzfall der Binomialver-teilung und gut geeignet, um Situationen zu beschreiben in denen man sehr viele Versuchemacht, die alle eine sehr geringe Erfolgswahrscheinlichkeit haben. Der einzige Parameter derPoissonverteilung ist λ. Dieser Paramter wird sich spater als Erwartungswert herausstellen.Die Wahrscheinlichkeit ai fur genau i ≥ 0 Erfolge ist definiert als

ai = e−λλi

i!fur i = 0, 1, 2, . . . .

Daraus ergibt sich folgende erzeugende Funktion:

A(z) =∑i≥0

e−λλi

i!· zi

= e−z ·∑i≥0

λ · zi

i!

= e−λ · eλ·z

= eλ(z−1) .

♥

Wir haben nun gesehen, dass wir aus einer Folge von Koeffizienten oft einfach einen geschlos-senen Term fur eine erzeugende Funktion A ableiten konnen. Nun stellt sich die Frage, wiewir aus der Funktion die Koeffizienten zuruckgewinnen konnen. Offensichtlich ist A(0) = a0.Die weiteren Terme konnen wir uns durch Ableitung verschaffen:

A′(z) = a1 + 2a2 · z + 3a3 · z2 + 4a4 · z3 + . . .

=⇒ A′(0) = a1 .

Den nachsten Koeffizienten gewinnen wir durch nochmaliges Ableiten:

A′′(z) = 2a2 + 6a3 · z + 12a4 · z2 + . . .

=⇒ A′′(0) = 2a2 .

Wir erhalten allgemeinA(i)(0)i!

= ai .

Sofern die Folge der ai eine Wahrscheinlichkeitsverteilung auf 0, 1, 2, . . . ist, konnen wirderen Erwartungswert berechnen, indem wir 1 in die Ableitung A′ einsetzen, denn

A′(1) =∑i≥0

i · ai;

das ist genau die Definition des Erwarungswerts.

74

8.1 Erzeugende Funktionen

Beispiel 8.4 (Erwartungswert der Poisson-Verteilung). Im Falle der Poissonverteilung konnenwir z.B. auf diese Weise uberprufen, dass der Parameter λ tatsachlich dem Erwartungswertder Verteilung entspricht:

A(z) = eλ(z−1)

=⇒ A′(z) = eλ(z−1) · λ=⇒ A′(1) = λ.

Dieses Beispiel zeigt, dass erzeugende Funktionen sehr nutzlich sein konnen. ♥

Losung der Fibonacci-Gleichung mit erzeugenden Funktionen. Wir zeigen jetzt, dass maneine Rekurrenz in eine Gleichung in der erzeugenden Funktion uberfuhren und gelegentlichexplizit losen kann. Wir betrachten dazu das bekannte Beispiel der Fibonacci-Zahlen. Diesesind definiert durch

f0 := 0, f1 := 1 und fn := fn−1 + fn−2fur n ≥ 2.

Es sei F (z) :=∑n ≥ 0 fnzn die erzeugende Funktion.

Multipliziert man F (z) mit z bzw. z2, erhalt man die Folgen (0, f0, f1, . . . ) bzw. (0, 0, f0, f1, . . . ),Addiert man diese, erhalt man zumindest ab Index 2 die Fibonacci-Folge. Bildlich:

(0, 0, f0, f1, f2, . . . ) z2F (z)(0, f0, f1, f2, f3, . . . ) zF (z)(f0, f1, f2, f3, f4, . . . ) F (z)

Die Addition stimmt in jedem Fall ab f2 in der untersten Zeile. Da f0 = 0, aber f1 = 1,stimmt die Rechnung nicht fur den Index 1 (es fehlt z in F (z) unten), aber fur den Index 0stimmt sie zufallig wieder. Also ist

F (z)− zF (z)− z2F (z) = z.

Auflosen nach F (z) ergibt

F (z) =z

1− z − z2.

Dies ist die erzeugende Funktion der Fibonacci-Zahlen. Hieraus konnen wir im Prinzip eineexplizite Formel fur fn durch Ableiten gewinnen.

Da F (z) in der dargestellten Form schwer abzuleiten ist, berechnen wir eine Partialbruch-zerlegung. Das Ziel dabei ist, die Funktion in der Form

F (z) =A

1− αz+

B

1− βz

mit Konstanten A,α,B, β zu schreiben, denn in dieser Form ist klar, dass es sich um geo-metrische Reihen handelt, und damit fn = Aαn +Bβn ist.

Zur Faktorisierung des Nenners lasst sich ein Trick anwenden (aus “Concrete Mathematics”?, Abschnitt 6.6): Wir fuhren eine neue Variable w ein und berechnen die Nullstellen statt

75

8 Exkurse

von 1 − z − z2 von w2 − wz − z2 in w (fur festes z). Dies fuhrt auf die Faktorisierungw2 − wz − z2 =

(w − 1+

√5

2 z)·(w − 1−

√5

2 z)

, also fur w = 1 auf

1− z − z2 =

(1− 1 +

√5

2z

)·

(1− 1−

√5

2z

).

Die gesuchte Konstante α = (1 +√

5)/2 ≈ 1.618 wird auch mit φ bezeichnet und goldenerSchnitt genannt. Die andere Konstante β = (1−

√5)/2 ≈ −0.618 wird mit φ bezeichnet.

Jetzt fehlen noch die richtigen Konstanten A und B: Aus z1−z−z2 = A

1−αz + B1−βz folgt nach

Durchmultiplizieren mit dem Nenner

z = A(1− βz) +B(1− αz) = (A+B) + z(−Aβ −Bα),

also A + B = 0 (konstanter Term) und Aβ + Bα = −1 (Faktor von z). Auflosen fuhrt zuA = 1/

√5 und damit ist

F (z) =1√5

(1

1− φz− 1

1− φz

)(nachrechnen!) und es ist

fn =1√5

(φn − φn).

Da |φ| < 1, ist der zweite Term fur große n irrelevant. In der Tat ist schon |φn/√

5| < 1/2fur alle n ≥ 0, so dass man das korrekte Ergebnis erhalt, wenn man den ersten Term einfachrundet: Es ist

fn = round(φn/√

5).

Dieses einfache Beispiel der Fibonacci-Zahlen zeigt, wie man erzeugende Funktionen gewinn-bringend einsetzen kann.

8.2 Anwendung von erzeugenden Funktionen auf PAAs

Wir wenden erzeugende Funktionen nun auf PAAs an (Definition 7.1 aus Abschnitt 7.4),insbesondere auf die Rekurrenz (7.1)

Der Einfachheit halber definieren wir

pt(q, v) := P(Yt=q, Vt = v) .

Wenn t und q fest gewahlt sind und v ∈ 0, 1, . . ., konnen wir pt(q, v) als Funktion von vauffassen und als erzeungende Funktion ausdrucken. Wir erhalten also fur jedes t und qeine solche Funktion. Diese Funktionen verwenden wir als Koeffizienten fur eine weitereerzeugende Funktion fur t und erhalten so fur jedes q eine sogenannte bivariate erzeugendeFunktion:

Pq(x, y) :=∑t≥0

(∑v≥0

pt(q, v) · xv)yt

Wir betrachten als Beispiel den PAA, der die Auskunft uber die Verteilung der Verkommendes Patterns ab, ba gibt (dabei ist Σ = a, b). Der zugrundeliegende DFA hat folgendeGestalt:

76

8.2 Anwendung von erzeugenden Funktionen auf PAAs

0

b

b

b

b

b

aa

a

a

1

2 3

4(+1)

(+1)

a

Die Zustande q0, . . . , q4 sind mit 0, . . . , 4 beschriftet. Die roten Markierungen kennzeichnenZustande in denen ein Match gezahlt werden muss. Der Startzustand ist blau. Nun werdenwir bivariate erzeugende Funktionen fur jeden Zustand q angeben. Fur den Zustand q0 istdas einfach, da er nur ausgehende Kanten hat; denn daraus folgt

pt(q0, v) =

1 falls t = 0, v = 0 ,0 sonst ,

und wir erhalten P0(x, y) ≡ 1.

Fur die anderen Zustande ist das etwas komplizierter. Wir konnen die erzeugenden Funktio-nen nicht direkt angeben sondern erstmal nur in Abhangigkeit voneinander:

P1(x, y) = y · πa ·(P0(x, y) + P1(x, y) + P3(x, y)

),

P2(x, y) = y · πb ·(P0(x, y) + P2(x, y) + P4(x, y)

),

P3(x, y) = x · y · πa ·(P2(x, y) + P4(x, y)

),

P4(x, y) = x · y · πb ·(P1(x, y) + P3(x, y)

),

dabei sind wir von einem M0-Modell ausgegangen und πa bzw. πb sind jeweils die Wahr-scheinlichkeit den Buchstaben a bzw. b zu beobachten.

Elementare Umformungen liefer uns

(yπa − 1) · P1 + yπa · P3 = −yπa(yπb − 1) · P2 + yπb · P4 = −yπb

xyπa · P2 − P3 + xyπa · P4 = 0xyπb · P1 + xyπb · P3− P4 = 0

oder in Matrixschreibweise:yπa − 1 0 yπa 0

0 yπb − 1 0 yπb0 xyπa −1 xyπa

xyπb 0 xyπb −1

·

P1

P2

P3

P4

=

−yπa−yπb

00

Der nachste Schritt ist das symbolische Invertieren der Matrix. So konnen wir die FunktionenP1, . . . , P4 explizit ausrechnen; dies sind rationale Funtionen in x und y. Hierbei mussen wirauf mogliche Singularitaten der Matrix achten.

77

8 Exkurse

8.3 Compound-Poisson-Approximation

Wir haben gesehen, dass wir die Wahrscheinlichkeitsverteilung der Trefferzahl mit Hilfe vonPAAs berechnen konnen. In diesem Abschnitt versuchen wir eine approximative, aber in derPraxis sehr genaue, formelhafte Charakterisierung der Trefferverteilung.

Beispiel 8.5 (Einzelsymbole). Betrachten wir zur Motivation den Fall eines einzelnen Stringsder Lange 1 (also eines einzelnen Symbols) mit der Wahrscheinlichkeit p im M0-Modell. Furdie Anzahl der Treffer X gilt wegen der Unabhagigkeit der einzelnen Zeichen die Binomial-verteilung

P(X = k) =(n

k

)· pk · (1− p)n−k

mit Erwartungswert E[X] = np und Varianz Var[X] = np(1− p).

Aus der elementaren Stochastik ist bekannt, dass fur große n und kleine p die Poisson-Verteilung mit Erwartungswert λ = np und Varianz λ eine gute Naherung liefert:

P(X = k) ≈ e−λ · λk/k!

♥

Aufgabe 8.1. Zeige, dass die Binomialverteilung unter der Annahme n→∞, p→ 0, np→λ > 0 in die Poissonverteilung ubergeht. Schlage in einem Stochastik-Buch eine expliziteFehlerabschatzung nach.

Das Problem besteht darin, dass die Motive normalerweise Langer als ein einzelnes Symbolsind und daher weder die Binomialverteilung noch die Poisson-Approximation gilt. Motive,die aus Strings bestehen, die sich selbst uberlappen, tendieren dazu, gehauft vorzukommen.Diese gehauften Vorkommen werden wir Clumps nennen, ihre Große abschatzen und fur ihreAnzahl eine Poisson-Verteilung annehmen. Dies liefert eine hinreichend gute Approximation.

8.3.1 Der Poisson-Prozess der Clumps

Definition 8.2. Ein Clump ist eine maximale uberlappende Mengen von Treffern in ei-nem Text. (Zwei Treffer uberlappen, wenn die Positionsmengen ihrer Teilstrings im Textwenigstens ein Element gemeinsam haben.)

Statt einzelner Treffer untersuchen wir jetzt Clumps von Treffern und stellen die Frage nachder Große und Anzahl der Clumps. Der Verteilung der Clumpgroße bezeichnen wir mit Ψ.Da ein Clump mindestens einen Treffer enthalt, gilt Ψ(≥ 1) = 1; ihren Erwartungswertbezeichenen wir mit E[Ψ] = ψ ≥ 1.

Definition 8.3. Clumpgroßenverteilung Eine Verteilung Ψ auf Z heißt Clumpgroßenverteilung,wenn Ψ(≥ 1) = 1.

78


Der Beginn eines Clumps ist (bei hinreichend spezifischen und seltenen Motiven) ein seltenesEreignis. Daher approximieren wir die Anzahl der Clumps C mit einer Poissonverteilung mit(zunachst unbekanntem) Erwartungswert λ:

P(C = c) = Pλ(c) = e−λ · λk/k!

Ist die Zahl der Clumps, auf die sich k Treffer verteilen, bekannt und gleich c, dann ist unterdieser Bedingung die Wahrscheinlichkeit fur k Treffer genau

P(XM = k | C = c) = P(Y1 + · · ·+ Yc = k) = Ψ∗c(k);

dabei sind die Yj unabhangige Kopien einer Ψ-verteilten Zufallsvariable, und Ψ∗c = Ψ∗· · ·∗Ψdie c-fache Faltung von Ψ.

Definition 8.4. Compound-Poisson-Verteilung Die Verteilung einer Zufallsvariablen X =∑Cj=1 Yj mit C ∼ Pλ und Yj ∼ Ψ unabhangig voneinander und von C fur alle j ≥ 0 heißt

Compound-Poisson-Verteilung mit Parametern λ > 0 und (Clumpgroßenverteilung) Ψ; wirbezeichnen die Verteilung mit CPλ,Ψ.

Wir werden also den p-Wert Pn(XM ≥ xm) durch CPλ,Ψ(≥ xM ) fur noch zu berechnendeλ > 0 und Ψ approximieren.

Lemma 8.1. Fur X ∼ CPλ,Ψ gilt

E[X] = E[Pλ] · E[Ψ] = λ · ψ.

Aufgabe 8.2. Beweise Lemma 8.1.

Da wir den Erwartungswert E[XM ] = (n −m + 1) · Pm(M) bereits berechnet haben, folgtnun

λ = (n−m+ 1) · Pm(M)/ψ,

wobei die erwartete Clumpgroße ψ noch unbekannt ist.

Definition 8.5. Die Compound-Poisson-Approximation des p-Werts Pn(XM ≥ xM ), kurzCPp-Wert, wird definiert als CPλ,Ψ(≥ xM ) mit λ = (n − |M | + 1) · P|M |(M)/E[Ψ], wobeiΨ = ΨM die Clumpgroßenverteilung von M ist.

In der Praxis kann man, solange ψλ/n ≤ 0.01 ist, mit vernachlassigbarem Fehler den CPp-Wert statt des wahren p-Werts verwenden.

TODO: Approximationsgute, Fehlerschranken.

8.3.2 Berechnung der Verteilung der Clumpgroße Ψ

Wir stellen ein auf PAAs basierendes exaktes Verfahren zur Berechnung der ClumpgroßenverteilungΨ vor.

Wir betrachten zu einem Motiv M im Prinzip denselben PAA wie zur exakten Berechnungder Trefferverteilung. Allerdings lassen wir den Automaten nun nicht vom ursprunglichen

79

8 Exkurse

Startzustand n Schritte (Textlange) laufen, sondern von einer (noch festzulegenden) Start-verteilung in den Treffer-Zustanden (erster Treffer im Clump) nur solange, bis ein Clump zuEnde ist, d.h. wir fur mindestens m− 1 Schritte keinen neuen Treffer gesehen haben. Dazumuss der PAA die Zeit seit dem letzten Treffer in der Wertemenge N zusatzlich tabellieren.

Wir modifizieren also den PAA (TODO) zur Trefferverteilungsmenge wie folgt: Statt einesfesten Startzustands q0 (bzw. der Dirac-Startveteilung δq0 geben wir eine Startverteilungπ an, die wir noch festlegen werden. Die Zustandsmenge Q bleibt unverander, es konnenoptional ggf. von der neuen Startverteilung aus unerreichbare Zustande entfernt werden.Die Ubergangswahrscheinlichkeiten bleiben unverandert. Die Emissionsmenge E und dieEmissionsverteilungen bleiben ebenfalls unverandert. Die Wertemenge N wird von N zuN × 0, 1, . . . ,m − 2, •; die erste Dimension zahlt nach wie vor die Anzahl der Treffer (imClump), die zweite Dimension die Anzahl der Zeichen seit dem letzten Treffer. Hat manspatestens nach m − 1 Schritten keinen weiteren Treffer gefunden, ist der Clump zu Endeund die Trefferzahl kann nicht weiter wachsen; dies wird durch das Symbol • angezeigt. Diearithmetische Operation in einem Zustand q muss nun wie folgt definiert werden:

θq : N × E → N ; ((v, t), e) 7→

(v + e, 0) wenn e > 0 und t 6= •,(v, t+ 1) wenn e = 0 und t /∈ n− 2, •,(v, •) wenn t ∈ • oder (t = n− 2 und e = 0).

Eine positive Emission bedeutet einen (oder mehrere) Treffer; deren Zahl e wird zu denbereits vorhandenen v hinzugefugt, der Zahler der Schritte seit dem letzten Treffer wird auf0 zuruckgesetzt. Dies kann aber nur geschehen, wenn der Clump noch nicht beendet war.Im Fall keiner Emission (e = 0) zahlen wir den Schrittzahler hoch; allerdings haben sowohlm− 2 als auch • den Nachfolger •.

Auf den so modifizierten PAA werden nun wieder die Algorithmen aus Abschnitt ?? zurBerechnung der gemeinsamen Zustands-Werte-Verteilung angewendet; dies liefert TODO.

Fur n→∞ approximiert die Zustands-Werte-Verteilung TODO

Es stellt sich noch die Frage nach der richtigen Startverteilung π des PAA.

8.3.3 Eine untere Schranke fur den p-Wert

Der CPp-Wert approximiert den wahren p-Wert im Normallfall sehr gut und ist etwas ein-facher zu berechnen, allerdings nicht viel einfacher. Das liegt daran, dass man dazu dieClumpgroßenverteilung Ψ ebenfalls mit einem PAA berechnen muss (allerdings kann dieseBerechnung kurzer ausfallen) und daruberhinaus die c-fachen Faltungen von Ψ benotigt.

In machen Fallen reicht bereits eine (grobe) untere Schranke fur den CPp-Wert aus: Istdiese schon groß, sind der CPp-Wert und der wahre p-Wert noch großer und das Motivdaher uninteressant. Eine solche sehr einfach zu berechnende Schranke geben wir jetzt an.

Nach (??) ist

CPλ,Ψ(≥ k) =∞∑c=0

Pλ(c) ·∞∑k′=k

Ψ∗c(k′),

ein wegen der c-fachen Faltungen aufwandig zu berechnender Ausdruck. Wir schatzen ihndurch einen einfacheren ab.

80


Lemma 8.2. Sei 0 ≤ λ′ ≤ λ, und sei Ψ eine Clumpgroßenverteilung. Dann ist

0 ≤ Pλ≥ k ≤ Pλ≥ k ≤ CPλ,Ψ(≥ k).

Beweis. Es ist Ψ∗c(≥ k) = 1, sofern c ≥ k. Daher

CPλ,Ψ(≥ k) =∑c≥0

Pλ(c) ·Ψ∗c(≥ k)

≥∑c≥kPλ(c) ·Ψ∗c(≥ k)

= Pλ≥ k.

Dies bedeutet, die Wahrscheinlichkeit fur mindestens k Clumps ist kleiner als die Wahr-scheinlichkeit fur mindestens k Matches. Die Aussage fur λ′ folgt aus der Monotonie derkumulativen Verteilungsfunktion der Poisson-Verteilung in λ.

Aufgabe 8.3. Rechne die Monotonie der (rechtsseitigen) kumulativen Verteilungsfunktionder Poisson-Verteilung im Parameter λ nach.

81

8 Exkurse

82

KAPITEL 9

Weitere Planungen

Weitere Algorithmen zum Patternmatching (Suffix-, Factor-based). Analyse von Sunday. –geht nicht mit PAA?!

Exkurs: Abelian Pattern Matching, Analyse.

Regulare Ausdrucke, Matching, mit Fehlern.

Approximative Suche: Alignment (Varianten inkl. Best Match), NFA-Ansatz mit epsilon-Uebergaengen Alignment mit Scores: NW / SW. Dotplots als Visualisierung. affine Gapko-sten. Konvexe Gapkosten? linearer Speicherbedarf: Hirshberg.

Datenbanksuche. Statistik.

Indexdatenstrukturen fur Teilstrings: Suffixbaume, Arrays, Konstruktion (Ukkonen, Skew,BwtWalk) Exaktes Pattern Matching auf Index-Datenstrukturen. BWT, auch: BackwardSearch (statt Affix Trees). Q-gram-Index, gapped q-Grams, seeded Alignment, filter, sensi-tivity.

Next generation sequencing. Technologien. Color space. Read mapping.

Kompression, bzip2. Compression Boosting.

Multiples Alignment. Heuristiken, exakte Algorithmen, Praxis. SP-Score, Komplexitat, Carillo-Lipman-Schranke. Star Alignment. Progressives Alignment (CLUSTAL/MUSCLE).

HMMs: Definition, Algorithmen, Spracherkennung, Modellierung von Proteinfamilien, GeneFinding. Anwendung aus Fachprojekt? Massenspektren fur Proteinfamilien. Viterbi, For-ward, Baum-Welch.

DNA-Design, Oligo-Stabilitat,

RNA: RNA-Faltung (Nussinov, Energiemodell bei Zuker). Erkennen von miRNAs?

83

9 Weitere Planungen

Subsequenz-Kombinatorik?

Gesten als Sequenzen?

Weitere Iterationen der Vorlesung

Sequenzstatistik: Compound-Poission Approximation. Fehlerschranken?

84

ANHANG A

Molekularbiologische Grundlagen

Das Ziel der Bioinformatik ist das Losen von biologischen Problemen mit Hilfe von Informa-tik, Mathematik und Statistik. Um die zu Grunde liegenden Fragestellungen verstandlich zumachen, geben wir in diesem Kapitel eine kurze Einfuhrung in einige wichtige Beriffe undTechniken der molekularen Genetik. Fur eine weitergehende Beschaftigung mit dem Themasei das Buch von Alberts et al. (2007) empfohlen. Dieses Buch hat uns auch beim Schreibendieses Kapitels als Quelle gedient.

A.1 Desoxyribonukleinsaure (DNA)

Die Entdeckung der molekularen Struktur der Desoxyribonukleinsaure (DNA) zahlt zu denwichtigen wissenschaftlichen Durchbruchen des 20. Jahrhunderts (Franklin and Gosling,1953; Watson and Crick, 1953; Wilkins et al., 1953)1. DNA ist ein Doppelhelix-formiges Mo-lekul, dessen Bestandteile zwei antiparallele Strange aus einem Zucker-Phosphat-Ruckgratund Nukleotid-Seitenketten sind. Die ”Sprossen“ der Leiter werden aus zwei komplementarenBasen gebildet; Adenin (A) ist immer mit Thymin (T) gepaart und Cytosin (C) immer mitGuanin (G). Chemisch gesehen bilden sich Wasserstoffbrucken zwischen den jeweiligen Part-nern; das Ausbilden dieser Bindungen bezeichnet man auch als Hybridisierung. Abstraktkonnen wir ein DNA-Molekul einfach als eine Sequenz (String) uber dem 4-Buchstaben-Alphabet A, C, G, T auffassen; die Sequenz des zweiten Strangs erhalten wir durch Bildungdes reversen Komplements. Da DNA fast immer doppelstrangig auftritt, ist die DNA-SequenzAAGCCT aquivalent zu ihrem reversen Komplement AGGCTT.

1Zur Rolle Rosalind Franklins bei der Bestimmung der DNA-Struktur sei auf die Artikel von Klug (1968)und Maddox (2003) hingewiesen.

85

A Molekularbiologische Grundlagen

Zelle

Zellkern

Chromosom

DNA-Doppelstrang

Basenpaar

Abbildung A.1: Dieses Bild zeigt schematisch die Organisation einer eukaryotischen Zelle.Man sieht, dass sich mit Zellkern verschiedene Chromosomen befinden. JedesChromosom besteht aus einem langen DNA-Doppelstrang, der in verschie-denen Organisationsebenen immer weiter aufgerollt ist. Ein DNA-Strangbesteht aus einem Zucker-Phosphat-Ruckgrat und einer Folge verschiede-ner Nukleobasen (farbig). Diese bilden Paare mit den Basen des reversenStrangs. (Dieses Bild ist gemeinfrei. Quelle: http://de.wikipedia.org/w/index.php?title=Datei:Chromosom.svg)

DNA kodiert also Informationen. In jeder bekannten Spezies (von Bakterien uber Pflanzenbis hin zu Tieren und Menschen) wird DNA als Trager der Erbinformationen verwendet.Das bedeutet, dass die kodierte Buchstabenfolge vererbt werden kann und den ”Bauplan“fur das jeweilige Individuum enthalt. Die gesamte DNA-Sequenz eines lebenden Organismusbezeichnet man als Genom. In (fast) allen Zellen eines Organismus befindet sich eine Kopiedes Genoms. Man unterscheidet Lebewesen, bei denen die Zellen einen Zellkern besitzen,die Eukaryoten, und solche bei denen das nicht der Fall ist, die Prokaryoten. Bakterien sindzum Beispiel Prokaryoten, wahrend alle Tiere und Pflanzen Eukaryoten sind. Im folgendenbehandeln wir nur eukaryotische Zellen.

Das Genom besteht in der Regel aus mehreren DNA-Molekulen. Diese Teilstucke sind mitHilfe spezieller Proteine sehr eng ”aufgerollt“. Den gesamten Komplex aus einem langenDNA-Faden und Strukturproteinen bezeichnet man als Chromosom. In (fast) jeder Zelle einesOrganismus befindet sich im Zellkern ein kompletter Satz an Chromosomen und somit eineKopie des Genoms des jeweiligen Individuums. Abbildung A.1 illustriert diese Sachverhalte.

86

http://de.wikipedia.org/w/index.php?title=Datei:Chromosom.svg

http://de.wikipedia.org/w/index.php?title=Datei:Chromosom.svg

A.2 Ribonukleinsaure (RNA)

Rueckwärtsstrang RNA-Polymerase

Vorwärtsstrang

GAC GG ATCAGCC CG A

RNA-TranskriptAG CUG CC UAGUCGG GC UU

AT

T T T TT TT T T TTA A AA A

AAAAAA TT TC G GG GG G

GGGGGGGG

C C C

CCCCCCCCCCC G

DNA-Doppelstrang

Chromosom

Abbildung A.2: RNA-Polymerase erstellt eine Kopie des Vorwartsstrangs, indem RNA er-zeugt wird, die revers-komplementar zum Ruckwartsstrang ist. (Dieses Bildist gemeinfrei. Quelle: http://de.wikipedia.org/w/index.php?title=Datei:DNA_transcription.svg)

A.2 Ribonukleinsaure (RNA)

Die Ribonukleinsaure (RNA) ist ein der DNA sehr ahnliches Kettenmolekul. Neben chemi-schen Unterschieden im Ruckgrat des Molekuls besteht der wichtigste Unterschied darin, dasRNA (fast) immer als Einzelstrang auftritt. Ein weiterer Unterschied ist, dass RNA stattder Base Thymin (T) die Base Uracil (U) enthalt. Wir konnen einen RNA-Strang somit alsString uber dem Alphabet A, C, G, U auffassen.

Ein Vorgang von zentraler Bedeutung ist die Abschrift von DNA in RNA. Diesen Pro-zess bezeichnet man als Transkription. Dabei lagert sich ein spezielles Protein, die RNA-Polymerase, an den DNA-Doppelstrang an und trennt die Bindungen zwischen den ge-genuberliegenden Strangen temporar und ortlich begrenzt auf. An dem nun freiliegendenTeil des Ruckwartsstrangs wird ein zum diesem komplementarer RNA-Strang hergestellt. DieReaktion schreitet in Ruckwartsrichtung fort; die RNA-Polymerase ”rutscht“ dabei an derDNA entlang. Die Bindung zwischen RNA und DNA-Strang wird durch die RNA-Polymerasesofort wieder getrennt. Die beiden DNA-Strange binden wieder aneinander. Zuruck bleibtein Kopie der DNA in Form eines RNA-Molekuls und der unveranderte DNA-Strang. Eineschematische Darstellung findet sich in Abbildung A.2.

Wichtig ist, dass immer nur ganz bestimmte Regionen der DNA abgeschrieben werden.Ublicherweise bezeichnet man einen solchen Abschnitt als Gen. Eine prazise, allgemein ak-

87

http://de.wikipedia.org/w/index.php?title=Datei:DNA_transcription.svg

http://de.wikipedia.org/w/index.php?title=Datei:DNA_transcription.svg


Name Abkurzung (3 Buchstaben) Abkurzung (1 Buchstabe)Alanin Ala AArginin Arg RAsparagin Asn NAsparaginsaure Asp DCystein Cys CGlutamin Gln QGlutaminsaure Glu EGlycin Gly GHistidin His HIsoleucin Ile ILeucin Leu LLysin Lys KMethionin Met MPhenylalanin Phe FProlin Pro PSerin Ser SThreonin Thr TTryptophan Trp WTyrosin Tyr YValin Val V

Tabelle A.1: Ubersicht uber die in Proteinen verwendeten Aminosauren und ihre ein- bzw.dreibuchstabigen Abkurzungen.

zeptierte Definition des Begriffs Gen gibt es allerdings nicht. Die Diskussion um diesen Begriffist in vollem Gange (Gerstein et al., 2007; Prohaska and Stadler, 2008).

A.3 Proteine

Neben den Nukleinsauren (also DNA und RNA) sind die Proteine eine weitere Klasse vonbiologisch wichtigen Kettenmolekulen. Proteine machen in der Regel ungefahr die Halfteder Trockenmasse (also des Teils, der nicht Wasser ist) einer Zelle aus. Sie ubernehmensehr unterschiedliche Funktionen: sie fungieren als Enzyme, Antikorper, Membranproteine,Transkriptionsfaktoren, etc. Die Liste ließe sich noch weit fortsetzen. Kurz gesagt: Proteinesind extrem wichtig fur das funktionieren von Zellen und ganzen Organismen.

Die Bestandteile von Proteinen sind Aminosauren. Jede Aminosaure enthalt eine Carboxyl-und eine Aminogruppe. Zwei Aminosauren konnen mit Hilfe einer sogenannten Peptidbin-dung miteinander verbunden werden. Dabei verbindet sich die Carboxylgruppe der erstenAminosaure mit der Aminogruppe der zweiten Aminosaure. Das resultierende Molekul (einsogenanntes Dipeptid) hat also auf der einen Seite eine freie Aminogruppe und auf der ande-ren Seite eine freie Carboxylgruppe. Das Ende mit der freien Aminogruppe bezeichnet manals N-Terminus und das Ende mit der freien Carboxylgruppe als C-Terminus. Dort konnennun weitere Aminosauren uber Peptidbindungen angekoppelt werden um eine lange Ketten– ein Protein – zu bilden. Die meisten Proteine sind 50 bis 2000 Aminosauren lang.

88

A.3 Proteine

Aminosaure CodonsAlanin GCA, GCC, GCG, GCUArginin AGA, AGG, CGA, CGC, CGG, CGUAsparagin AAC, AAUAsparaginsaure GAC, GAUCystein UGC, UGUGlutamin CAA, CAGGlutaminsaure GAA, GAGGlycin GGA, GGC, GGG, GGUHistidin CAC, CAUIsoleucin AUA, AUC, AUULeucin CUA, CUC, CUG, CUU, UUA, UUGLysin AAA, AAGMethionin AUGPhenylalanin UUC, UUUProlin CCA, CCC, CCG, CCUSerin AGC, AGU, UCA, UCC, UCG, UCUThreonin ACA, ACC, ACG, ACUTryptophan UGGTyrosin UAC, UAUValin GUA, GUC, GUG, GUUStopp-Signal UAA, UAG, UGA

Tabelle A.2: Genetischer Code: Zuordnung von Aminosauren zu Codons. Wird bei der Trans-lation ein Stopp-Codon erreicht, endet der Prozess.

Die Vielfalt unter den Proteinen entsteht durch die Kombination von 20 verschiedenen Ami-nosauren (siehe Tabelle A.1). Die Aminosauren unterscheiden sich durch die sogenanntenSeitenketten. Das sind chemische Komponenten, die neben der Amino- und Carboxylgrup-pe an dem zentralen Kohlenstoffatom der Aminosaure befestigt sind. Warum im Laufe derEvolution genau diese 20 Aminosauren als Komponenten aller Proteine ausgewahlt wurdenist bisher ungeklart, denn chemisch lassen sich noch viel mehr Aminosauren herstellen. Feststeht, dass diese Auswahl sehr fruh im Laufe der Evolution stattgefunden haben muss, dennsie ist allen bekannten Spezies gemein.

Die Herstellung von Proteinen erfolgt durch die Translation von mRNAs. Die AbkurzungmRNA steht fur ”messenger RNA“ (Boten-RNA). Sie ruhrt daher, dass die mRNA als Zwi-schenprodukt bei der Herstellung von Proteinen dient. Nachdem ein Gen in eine mRNAtranskribiert wurden (vgl. Abschnitt A.2), wird diese mRNA aus dem Zellkern exportiertund danach in ein Protein ubersetzt. Dabei kodieren immer drei Basenpaare der RNA eineAminosaure. Ein solches Tripel nennt man Codon. In Tabelle A.2 ist zu sehen, welche Codonsjeweils welche Aminosaure kodieren. Diese Zuordnung bezeichnet mal als genetischen Code.Da es 20 Aminosauren gibt, aber 43 = 64 mogliche Codons, gibt es Aminosauren, die durchmehrere Codons dargestellt werden.

Die Reihenfolge der Aminosauren bestimmt die Struktur eines Proteins; deshalb nenntman sie auch Primarstruktur. Nach der Herstellung eines Proteins verbleibt es allerdings

89


Abbildung A.3: Schematische Darstellung eines Proteins. Jede α-Helix ist als Spirale, jedesβ-Faltblatt als Pfeil dargestellt. (Dieses Bild ist gemeinfrei. Quelle: http://en.wikipedia.org/wiki/File:PBB_Protein_AP2A2_image.jpg)

nicht in seiner Form als langer Strang, sondern faltet sich. Man kann sich das Vorstellenwie ein Faden, der sich ”verknault“. Dies geschiet jedoch nicht zufallig, sondern ist be-stimmt von den Eigenschaften der Aminosauren-Seitenketten. So gibt es zum Beispiel Ami-nosauren, die hydrophob sind; andere sind hydrophil; wieder andere sind positiv/negativgeladen. So wirken verschiedene Krafte zwischen den einzelnen Aminosauren und der um-gebenden (wassrigen) Zellflussigkeit sowie zwischen den Aminosauren untereinander. DieseKrafte zwingen das Protein in eine ganz bestimmte dreidimensionale Struktur. Das Anneh-men dieser Struktur heißt Proteinfaltung. Dabei gibt es bestimmte ”Bausteine“, die in vielenProteinen vorkommen, namlich die α-Helix und das β-Faltblatt. Diese Elemente nennt manSekundarstruktur, wahrend die vollstandige 3D-Struktur als Tertiarstruktur bezeichnet wird(siehe Abbildung A.3). Es kommt vor, dass mehrere Proteine sich zu einem Proteinkomplexzusammenschliessen. Ein solcher Komplex heißt dann Quatarstruktur.

A.4 Das zentrale Dogma der Molekularbiologie

Wir wollen die wichtigsten Prozesse noch einmal zusammenfassen: Abschnitte der DNA (dieGene) werden transkribiert; das Resultat ist mRNA. Aus jeder mRNA wird bei der Trans-lation ein Protein hergestellt. Somit kann man ein Gen als ”Bauanleitung fur ein Protein“bezeichnen. Anders ausgedruckt werden in der DNA kodierte Informationen in RNA und vondort in Proteine ubersetzt. Dieses Prinzip ist so wichtig, dass man es als zentrales Dogmader Molekularbiologie bezeichnet.

Man muss jedoch anmerken, dass es auch Ausnahmen von dieser Regel gibt. So weiss manheute, dass zum Beispiel auch RNA in DNA ubersetzt werden kann. Ein Prinzip, dass sichRetroviren zu Nutze machen. Dennoch hat das zentrale Dogma nichts an seiner Wichigkeiteingebußt, denn es beschreibt nach wie vor einen sehr wichtigen, wenn nicht den wichtigsten,Prozess in Zellen.

90

http://en.wikipedia.org/wiki/File:PBB_Protein_AP2A2_image.jpg

http://en.wikipedia.org/wiki/File:PBB_Protein_AP2A2_image.jpg

A.5 Genregulation

A.5 Genregulation

Jede Zelle eine Organismus enthalt eine exakte Kopie des Genoms. Wie ist es dann moglich,dass es so verschiedene Zellen wie Haut-, Leber, Nerven- oder Muskelzellen gibt? Die Antwortliegt in der Regulation der Gene. Die meisten Gene werden in unterschiedlichen Gewebenunterschiedlich stark verwendet; d. h. es kann zum Beispiel sein, dass ein bestimmtes Proteinin Nervenzellen in sehr großer Zahl hergestellt wird, wahrend man es in Hautzellen garnichtantrifft. Man sagt dann, das dazugehorige Gen ist unterschiedlich stark exprimiert.

Es gibt viele verschiedene Mechanismen, mit denen eine Zelle die Genexpression steuert.Ein wichtiger Mechanismus, auf den wir uns zunachst beschranken wollen, ist die Regu-lation der Transkription durch Transkriptionsfaktoren. Das sind spezielle Proteine, die anDNA binden konnen. Diese Bindung erfolgt sequenzspezifisch, das bedeutet ein bestimmterTranskriptionsfaktor bindet nur an eine bestimmte DNA-Sequenz. Solche Sequenzen befin-den sich ublicherweise vor Genen auf der DNA in den sogenannten Promoter-Regionen. EinDNA-Abschnitt an den ein Transkriptionsfaktor binden kann bezeichnet man als Transkrip-tionsfaktorbindestelle. Sobald sich ein Transkriptionsfaktor an eine Bindestelle angelagerthat, beeinflusst er die Transkription des nachfolgenden Gens. Es gibt sowohl Transkriptions-faktoren, die das Ablesen eines Gens hemmen, als auch solche, die es fordern.

A.6 Experimentelle Techniken zur DNA-Bearbeitung

TODO: Ausfuhrlicher beschreiben

A.6.1 Kopieren mit PCR (polymerase chain reaction,Polymerasekettenreaktion)

Zyklen von (Denaturierung, Priming, Erweiterung) und Zugabe von dNTP fuhrt zu expo-nentieller Vermehrung der DNA.

A.6.2 Kopieren durch Klonierung in Vektoren

Einfugen von DNA-Abschnitten in Vektoren (DNA sich vermehrender Organismen, z.B.Viren, Bakterien)

A.6.3 Cut+Paste mit Restriktionsenzymen

Restriktionsenzyme sind Proteine, die einen DNA-Doppelstrang an charakteristischen Sequenz-Motiven zerschneiden Beispiele: PvuII (CAG—CTG) oder BamHI (G—GATCC); der Strich(—) kennzeichnet die Schnittstelle. Zusammenkleben durch Hybridisierung und Ligation.

91


A.6.4 Langenbestimmung mit Gel-Elektrophorese

DNA ist negativ geladen, DNA-Fragmente wandern zu einem positiv geladenen Pol eineselektrischen Feldes durch ein Gel. Gel als Bremse; langere Fragmente sind langsamer. DNAmit fluoreszierenden Farbstoffen sichtbar gemacht. Position der sichtbaren Banden im Gelerlaubt relativ genaue Langenermittlung der DNA-Fragmente

A.6.5 Test auf Prasenz eines DNA-Abschnitts

mittels DNA-Sonden und Hybridisierung (z.B. Microarrays)

92

Literaturverzeichnis

A. V. Aho and M. J. Corasick. Efficient string matching: an aid to bibliographic search.Commun. ACM, 18(6):333–340, 1975. doi: 10.1145/360825.360855. URL http://portal.acm.org/citation.cfm?id=360855.

B. Alberts, A. Johnson, J. Lewis, M. Raff, K. Roberts, and P. Walter. Molecular Biology ofthe Cell. Garland Science, 2007. ISBN 0815341059.

R. S. Boyer and J. S. Moore. A fast string searching algorithm. Communications of theACM, 20(10):762–772, 1977. URL http://portal.acm.org/citation.cfm?id=359842.359859.

R. Durbin, S. R. Eddy, A. Krogh, and G. Mitchison. Biological Sequence Analysis: Proba-bilistic Models of Proteins and Nucleic Acids. Cambridge University Press, 1999. ISBN0521629713.

R. Franklin and R. Gosling. Molecular configuration in sodium thymonucleate. Nature, 171:740–741, 1953.

M. B. Gerstein, C. Bruce, J. S. Rozowsky, D. Zheng, J. Du, J. O. Korbel, O. Emanuelsson,Z. D. Zhang, S. Weissman, and M. Snyder. What is a gene, post-ENCODE? Historyand updated definition. Genome Research, 17(6):669–681, 2007. ISSN 1088-9051. doi:10.1101/gr.6339607.

D. Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computa-tional Biology. Cambridge University Press, 1997. ISBN 0521585198.

R. N. Horspool. Practical fast searching in strings. Software-Practice and Experience, 10:501–506, 1980.

A. Klug. Rosalind Franklin and the discovery of the structure of DNA. Nature, 219:808–844,1968.

93

http://portal.acm.org/citation.cfm?id=360855


http://portal.acm.org/citation.cfm?id=359842.359859

http://portal.acm.org/citation.cfm?id=359842.359859

Literaturverzeichnis

D. E. Knuth, J. Morris, and V. R. Pratt. Fast pattern matching in strings. SIAM Journalon Computing, 6(2):323–350, June 1977. doi: 10.1137/0206024. URL http://link.aip.org/link/?SMJ/6/323/1.

B. Maddox. The double helix and the ’wronged heroine’. Nature, 421:407–408, 2003.

G. Navarro and M. Raffinot. Flexible Pattern Matching in Strings. Cambridge UniversityPress, 2002. ISBN 0521813077.

S. B. Needleman and C. D. Wunsch. A general method applicable to the searchfor similarities in the amino acid sequence of two proteins. Journal of Molecu-lar Biology, 48(3):443–453, Mar. 1970. ISSN 0022-2836. doi: 10.1016/0022-2836(70)90057-4. URL http://www.sciencedirect.com/science/article/B6WK7-4DN8W3K-7X/2/0d99b8007b44cca2d08a031a445276e1.

S. Prohaska and P. Stadler. “Genes”. Theory in Biosciences, 127(3):215–221, 2008.

D. Sankoff and J. Kruskal. Time Warps, String Edits, and Macromolecules: The Theory andPractice of Sequence Comparison. Center for the Study of Language and Inf, 1999. ISBN1575862174.

M. Schulz, D. Weese, T. Rausch, A. Doring, K. Reinert, and M. Vingron. Fast and adaptivevariable order markov chain construction. In K. A. Crandall and J. Lagergren, editors,Proceedings of the 8th International Workshop on Algorithms in Bioinformatics (WABI),Karlsruhe, Germany, volume 5251 of LNCS, pages 306–317, 2008. URL http://dx.doi.org/10.1007/978-3-540-87361-7_26.

T. F. Smith and M. S. Waterman. Identification of common molecular subsequences.Journal of Molecular Biology, 147(1):195–197, Mar. 1981. ISSN 0022-2836. doi: 10.1016/0022-2836(81)90087-5. URL http://www.sciencedirect.com/science/article/B6WK7-4DN3Y5S-24/2/b00036bf942b543981e4b5b7943b3f9a.

D. M. Sunday. A very fast substring search algorithm. Communications of the ACM, 33(8):132–142, 1990. doi: 10.1145/79173.79184. URL http://portal.acm.org/citation.cfm?id=79184.

E. Ukkonen. Finding approximate patterns in strings. Journal of Algorithms, 6(1):132–137,1985.

E. Ukkonen. On-line construction of suffix trees. Algorithmica, 14(3):249–260, 1995. doi:10.1007/BF01206331. URL http://dx.doi.org/10.1007/BF01206331.

J. Watson and F. Crick. A structure for deoxyribose nucleic acid. Nature, 171:737–738, 1953.

M. Wilkins, A. Stokes, and H. Wilson. Molecular structure of deoxypentose nucleic acids.Nature, 171:738–740, 1953.

94

http://link.aip.org/link/?SMJ/6/323/1

http://link.aip.org/link/?SMJ/6/323/1

http://www.sciencedirect.com/science/article/B6WK7-4DN8W3K-7X/2/0d99b8007b44cca2d08a031a445276e1

http://www.sciencedirect.com/science/article/B6WK7-4DN8W3K-7X/2/0d99b8007b44cca2d08a031a445276e1

http://dx.doi.org/10.1007/978-3-540-87361-7_26

http://dx.doi.org/10.1007/978-3-540-87361-7_26

http://www.sciencedirect.com/science/article/B6WK7-4DN3Y5S-24/2/b00036bf942b543981e4b5b7943b3f9a

http://www.sciencedirect.com/science/article/B6WK7-4DN3Y5S-24/2/b00036bf942b543981e4b5b7943b3f9a



http://dx.doi.org/10.1007/BF01206331

Documents

Algorithmen auf Sequenzen - ls11- · einer Sequenz. Entdecken von wiederholten Teilsequenzen (n utzlich f ur Genomanalyse, Kompression). Entwicklung von Codes zur fehlertoleranten