Hauptseminar Automaten und Formale Sprachen Algorithmen der Bioinformatik Exact String Matching Michael Opfermann

Hauptseminar Automaten und Formale Sprachen

Algorithmen der Bioinformatik

Exact String Matching

Michael Opfermann

Exact String Matching

Problemstellung- Das Auffinden aller Vertreter eines Musters P innerhalb eines

Textes T

T : TGACGTACGAATG

P : GTACG- Möglichst zeit- und speicherplatzeffizient

Definitionen

String S– Sei ein Wort, oder eine Kette, aus Buchstaben des Alphabetes X

Substring S[k..l]– Sei ein stetiger Teilausschnitt eines Strings S, beginnend an einer Position

k und endend an der Position l Prefix

– Sei ein Substring S[1..k] des Strings S Suffix

– Sei ein Substring S[k..|S|] des Strings S Muster P

– Das Muster sei der zu suchende String der Länge m Text T

– Sei der nach Vorkommen des Musters zu durchsuchende String der Länge n

Naiver Algorithmus

Buchstabenweiser Vergleich von Text und Muster Bei Fehler verschieben des Musters um 1 Position nach Rechts

relative zum Text GTAGTCCTAG

GTCCT

_GTCCT

Worst Case Laufzeit : O (m*n) Verbesserungen der Laufzeit durch Preprocessing zum Berechnen

größerer Verschiebungen als im naiven Algorithmus– Entweder am Text oder am Muster

Preprocessing

Preprocessing am Muster P– Right-most Position der Buchstaben des Musters

Bezeichnet das Vorkommen am weitesten rechts eines Buchstabens im Muster

Definition– Für jeden Buchstaben x im Alphabet, sei R(x) die right-

most Position von x in P– R(x) = 0 wenn x nicht in P existiert

GTAAGT : R(G) = 5 R(T) = 6R(C) = 0 R(A) = 4

Preprocessing

Preprocessing am Muster– Definitionen

Zi(S) (einfach Zi, falls S fest bestimmt)– Gegeben sei ein String S und eine Position 1 < i <=|S| in diesem String.

Dann sei Zi(S) die Länge des längsten Substrings in S, der in i beginnt und einen Prefix von S entspricht

Z-Box– Für jede Position 1 < i <=|S| in S, wenn Zi(s) > 0, sei die Z-Box das

Intervall [i, i+ Zi(s) -1] ri

– ri sei der right-most Endpunkt aller Z-Boxen, die links von oder an der Position i beginnen.

li– li sei der am weitesten links liegende Startpunkt einer Z-Box, die in r i endet

Preprocessing am Muster

Der Z Algorithmus (Teil 1)Zur Bestimmung der Zi(S)

– r = 0, l = 0– Für 1 < k <= |S|

Wenn k > r dann Vergleiche die Substrings S[k…m] und S[1…m-k+1] miteinander, bis ein ungleiches Paar auftritt. Zk ist gleich der Länge der Übereinstimmung. Wenn Zk > 0, dann r = k + Zk -1 und l = k


Der Z Algorithmus (Teil 2) k <= r

– k‘ = k – l +1– b = r – k + 1– 1. Fall

Zk‘(S) < b

Zk = Zk‘

– 2. Fall Zk‘(s) >= b Vergleiche Substrings von S startend an Positionen (b + 1)

und (r + 1) miteinander bis ein Fehler auftritt (an Position q) Zk = q – k, r = q – 1, l = k


Der Z Algorithmus (Teil 3)– Ziel

Berechnen von Zi(S) Werten durch benutzen der Zj(S) Werte für j < i

Beispiel k = 121, r120 = 130, l120 = 100

– Z22(S) = 3

– Dann folgt, Z121(S) ist ebenfalls 3

Boyer Moore Algorithmus

Bestandteile– Right-to-Left-Scan

Eigentliche Vergleichsoperation

– Bad Character Rule Aufruf bei Auftreten eines ungleichen Vergleichspaares

zur Berechung der Verschiebung

– Good Suffix Rule Aufruf bei Auftreten eines ungleichen Vergleichspaares,

das nicht das erste Vergleichspaar ist, oder dem Auffinden eines Vorkommens des Musters im Text


Right to Left Scan– Buchstabenweiser Vergleich wie im naiven Algorithmus– Allerdings nicht von Links nach Rechts, sondern von Rechts nach

LinksGTCGTAAATGTGAGTAATAA

– Laufzeit unverändert zu Naiven Algorithmus– Verschieben des Musters anhand der beiden Verschieberegeln

Bad Character Rule Good Suffix Rule


Bad Character Rule– Sei x ein Buchstabe aus T und y ein Buchstabe aus P– Sei k die aktuelle Vergleichsposition in T und i die Position in P– Wenn ein Vergleich von x und y ergibt x <> y, dann verschiebe P

um Max[1, i-R(T(k))] nach rechts

GTCAGT…. GTCAGT…..

GTAC GTTC

GTAC GTTC


Laufzeiten und Speicherbedarf– g sei die Größe des Alphabets, m sei die Länge von P, n sei die

Länge von T– Vorverarbeitung von P

Speicherbedarf: O(g) = O(1) Laufzeit O(g*m) = O(m)

– Anwenden der Bad Character Rule Right to Left Scan : O(m) Bestimmung der Verschiebeposition : O(g)

– Worst Case Laufzeit : O(n*(g+m)) + O(m) = O(n*m)– Laufzeit bei großem Alphabet und kurzem P geht gegen O(n/m)


Good Suffix Rule– Arbeitsweise

Fall 1 Ein Substring t von T stimmt mit einem Suffix von P überein

– Dann finde die right-most Kopie t‘ von t in P, so dass t‘ ist kein Suffix von P und das Zeichen links von t‘ ist ungleich dem Zeichen links von t

– Verschiebe P nach rechts, so dass t‘ unter t liegt– Gibt es kein solches t‘ dann suche einen Suffix von t, der mit

einem Prefix von P übereinstimmt und verschiebe P, so das dieser Suffix über diesem Prefix liegt

– Gibt es keinen solchen Suffix, dann verschiebe P um m Positionen nach rechts


Good Suffix Rule– Arbeitsweise

Fall 2 eine Kopie K von P wurde in T gefunden– Melde Position der Kopie– Suche einen echten Prefix t von P, so dass t = Suffix t‘

von K– Verschiebe P nach rechts, so dass t genau über t‘ liegt– Gibt es kein solches t dann verschiebe P um m Positionen

nach rechts


Good Suffix Rule– Vorverarbeitung von P

Definitionen– Für jede Position i in P sei L‘(i) die am weitesten rechts

liegende Position für die gilt P[i..n] entspricht einem Suffix von P[1..L‘(i)] und der Buchstabe vor diesem Suffix is ungleich P(i-1). L‘(i) = 0 wenn keine solche Position existiert

– Für P sei Nj(P) die Länge des längsten Suffix des Substrings P[1..j], der zudem ein Suffix von P ist

– Pr sei Umkehrung von P

Good Suffix RulePreprocessing

Zi(s) ist die Länge des längsten Substrings von S, der in i beginnt und einen Prefix von S ist

Offensichtlich ist N die Umkehrung von Z– D.h.

Nj(P) = Zn-j+1(Pr)

Da Z O(m) ist auch N O(m)

L‘(i) = max(j | Nj(P) = |P[i..n]| = (n-i+1))


Z-Based Boyer Moore

for i := 1to n do L‘(i) = 0

for j := 1 to n-1 do

begin

i := n – Nj(P) + 1

L‘(i) := j

end;


Definition– l‘(i) sei gleich dem größten j <= |P[i..n]|, so das Nj(P) = j

Die Good Suffix Rule– Tritt beim Vergleich ein Fehler an Position i -1 auf und L‘(i)

>0 dann verschiebe P um m - L‘(i) Positionen nach rechts– Ist L‘(i) = 0, dann verschiebe P um m – l‘(i) Positionen nach

rechts– Wurde ein Vorkommen von P in T gefunden, dann

verschiebe P um m – l‘(2) Positionen nach rechts


Berechne L‘(i), l‘(i) und R(x) k:=n Solange k <=n

– i:= n– h:= k– Solange i > 0 und P(i) = T(h)

i:= i -1; h:= h-1– If i = 0

Berichte gefundenes Vorkommen von P k:= k + n – l‘(2)

– Else Verschiebe P um das Maximum der durch die Good Suffix bzw. Bad

Character Rule berechnete Verschiebung

Knuth Morris Pratt Algorithmus

Definitionen– spi‘(P) sei die Länge des Längsten echten Suffix von P[1..i]

der mit einem Prefix von P übereinstimmt und außerdem gilt P(i+1) <> P(spi‘+1)

Verschieberegel– Verglichen wird von links nach rechts wie im naiven

Algorithmus– Tritt ein Fehler an der Position i+1 von P auf, so verschiebe

P um i- spi‘ Positionen nach rechts– Wird ein Vorkommen von P in T gefunden, so verschiebe P

um n – spn‘ Positionen nach rechts


Vorteile der Verschieberegel– 1. oft Verschiebungen größer 1– 2. nach einer Verschiebung stimmt der Prefix

P[1..spi‘] mit T überein und der Vergleich braucht erst ab der Position P[spi‘+1] fortgeführt zu werden


Preprocessing– Z Based Knuth Morris Pratt

Für i:= 1 bis n– spi‘ = 0

Für j:= n abwärts bis 2– i:= j + Zj -1

– spi‘ := Zj

Fehlerfunktion F‘(i) = spi-1‘ +1 – (wobei sp0‘=0)


Preprocessing F‘(k) c:= 1; p:= 1 Solang c+(m-p) <= n

– Solange P(p) = T(c) und p<=m p++, c++

– Wenn p=n+1 dann Berichte Vorkommen von P in T startend an Position c-m

– Wenn p=1 dann c++– p:= F‘(p)


Realtime Erweiterung– Z based real time matching

Für i:= 1 bis n– Spi,x‘ = 0 für jedes x aus dem Alphabet

Für j:= n abwärts bis 2– i:= j + Zj -1

– x:= P(Zj+1)

– Spi,x‘ := Zj

Documents

Hauptseminar Automaten und Formale Sprachen Algorithmen der Bioinformatik Exact String Matching Michael Opfermann