UNIVERSITA DI MILANO-BICOCCA LAUREA MAGISTRALE IN BIOINFORMATICA Corso di BIOINFORMATICA: TECNICHE...

UNIVERSITA’ DI MILANO-BICOCCAUNIVERSITA’ DI MILANO-BICOCCALAUREA MAGISTRALE IN LAUREA MAGISTRALE IN

BIOINFORMATICABIOINFORMATICA

Corso di

BIOINFORMATICA: TECNICHE DI BASE

Prof. Giancarlo Mauri

Lezione 5

Algoritmi di string matching esatto

2

Exact matching: il problema

DATEDATE:

una stringa T di lunghezza n (detta testo) e

una stringa P di lunghezza m<n (detta pattern)

definite su un alfabeto

TROVARETROVARE:

l’ insieme di tutte le posizioni nel testo T a partire da cui occorre il pattern P

3

Exact matching: il problema

Algoritmo diAlgoritmo diexact matchingexact matching

P=aba

T=bbabaxababay

Esempio

{3,7,9}NB: le occorrenze di P in T possonoanche sovrapporsi (es. 7 e 9)

NB: le occorrenze di P in T possonoanche sovrapporsi (es. 7 e 9)

4

Exact matching: prime idee

Algoritmo “forza bruta”

Allinea il primo carattere di P con il primo carattere di T

Confronta, da sinistra a destra, i caratteri corrispondenti di P e T fino a quando trovi un mismatch o raggiungi la fine di P

Se hai raggiunto la fine di P, restituisci la posizione del carattere di T che corrisponde al primo carattere di P

Sposta P di un posto a destra

Se l’ultimo carattere di P va oltre la fine di T, termina l’esecuzione; altrimenti ripeti da 2

5


Esempio

T = xabxyabxyabxz

P = abxyabxz

x a zxbayb x y a b xT

zxba b x y aP

Allinea il primo carattere di P con il primo carattere di T

a b x y a b x z



a zb x y a b x



zxa b x y a b


Sposta P di un posto a destra...

zxba b x y a zxbaa b x y zxbaya b x


Se hai raggiunto la fine di P, restituisci la posizione del carattere di T che corrisponde al primo carattere di P => 6


xbayxa b z

L’ultimo carattere di P va oltre la fine di T. Termina l’esecuzione

6


Caratteristiche dell’algoritmo “forza bruta”

Non è necessaria una fase di pre-processing

Il pattern P viene sempre spostato di una posizione a destra

La complessità in tempo è O(nm)

NB: non sempre è necessario spostare P diuna sola posizione. Come aumentare lospostamento senza rischiare di perdere occorrenze?

NB: non sempre è necessario spostare P diuna sola posizione. Come aumentare lospostamento senza rischiare di perdere occorrenze?

7

Exact matching: preprocessing

Fase di pre-processing per

imparare la struttura “interna” del pattern P o del testo T

e

RIDURRE IL TEMPO DI ESECUZIONE

8


S = A A T G C A T T C G C T

S = A A T G C A T T C G C T

Def.: un suffisso S[i…|S|] di una stringa S è una sottostringa che inizia alla posizione i e termina alla posizione finale di S

Esempio

Def.: un prefisso S[1…i] di una stringa S è una sottostringa che inizia alla posizione 1 di S e termina alla posizione i

Esempio

9


q

T g a c g a g a g a a g c g a t

P sa g a g a c a

Si supponga di essere nella seguente situazione con P in s+1

NB: all’interno del matching lungo q=5 esiste la sottostringaP[3..5] = aga che coincide con il prefisso P[1..3]

NB: all’interno del matching lungo q=5 esiste la sottostringaP[3..5] = aga che coincide con il prefisso P[1..3]

k

10


k


a g a g a c a

Si supponga di essere nella seguente situazione con P in sE’ evidente che conviene spostare P in

s’+1 = s+(q-k)+1

NB: all’interno del matching lungo 5 esiste la sottostringaP[3..5]=“aga” che coincide con il prefisso P[1..3]

NB: all’interno del matching lungo 5 esiste la sottostringaP[3..5]=“aga” che coincide con il prefisso P[1..3]NB: si è così sicuri che esiste un matching iniziale dilunghezza k=3 per il prefisso P[1..3]

NB: si è così sicuri che esiste un matching iniziale dilunghezza k=3 per il prefisso P[1..3]

Ps’

s q-k

11


Intuitivamente...

Dato che il prefisso P[1...q] coincide con la sottostringa T[s+1…s+q], ci si chiede quale sia il minimo spostamento s’>s tale che:

P[1...k] = T[s'+1…s'+k]

Ovviamente

s’ = s+q-k

NB: il confronto dei primi k caratteri di P è superfluoNB: il confronto dei primi k caratteri di P è superfluo

12

1 mq


Formalmente...

Dato un pattern P[1, …, m], si calcola la sua funzione prefisso

NB: [q] è la lunghezza del più lungo prefisso di P cheè anche suffisso di P[1..q]

NB: [q] è la lunghezza del più lungo prefisso di P cheè anche suffisso di P[1..q]

: {1,2,...,m} {0,1,...,m-1}

[q] = max{k: k<q e P[1..k] è suffisso di P[1..q]}

k

13


Algoritmo per il calcolo della funzione prefisso

begin

m:=length(P);

(1):=1; k:=0;for q:=2 to m do

begin

while P[k+1]P[q] dok:=[k];

if P[k+1]=P[q] then

k:=k+1;

[q]:=k; end

return ;end

14


Esempio di funzione prefisso per un pattern P

P[q] g a c g a g a g a a g c g a t

[q] 0 0 0 1 2 1 2 1 2 a 1 0 1 2 0

q 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

15

begin

n:= length(T); m:=length(P);

:= precomputed prefix function of P; q:=0;

for i:=1 to n do

begin

while q>0 and P[q+1]T[i] thenq:=[q];

if P[q+1]=T[i] then

q:=q+1;

if q=m then

print “pattern in i-m+1”;

q:=[q]; end

end

Algoritmo di Knuth-Morris-Pratt


Numero di matchesScansione da sx a dx

Il prossimo carattere è diversoIl prossimo carattere è uguale

Trovata occorrenza di P

Cerca nuova occorrenza

16

Caratteristiche dell’algoritmo KMP

E’ suddiviso in due fasi: pre-processing + ricerca effettiva

Sposta in genere il pattern P di più posizioni a destra

La complessità in tempo della fase di pre-processing è O(m)

La complessità in tempo della fase di ricerca è O(n)


Complessità algoritmo K-M-P: O(m+n)

17

Algoritmo di Boyer-Moore

Idee generali

Il confronto tra il pattern e il testo avviene da destra a sinistra

Il numero dei confronti viene ridotto usando due euristiche

euristica del carattere discordante (bad character rule)

euristica del buon suffisso (good suffix rule)

NB: quando pattern e testo non coincidono si sceglie ilmassimo tra gli spostamenti proposti dalle due euristiche

NB: quando pattern e testo non coincidono si sceglie ilmassimo tra gli spostamenti proposti dalle due euristiche

18


P sa g a g a c a

Si supponga di essere nella seguente situazione con P in s

NB: il carattere P[4] coincide con il carattereT[s+7]


E’ evidente che conviene spostare P in

s’+1 = s+1+j-k

kj


19


P s’a g a g a c a

E’ evidente che conviene spostare P in s’+1 = s+1+j-k

k




20

Intuitivamente...

Dato che esiste un j (1jm) per cui P[j] T[s+j], trovare il massimo k (1km), se esiste, tale che:

P[k] = T[s+j]

e spostare P in s’+1 tale che


s'+k = s+j

21

Formalmente...

Dato un pattern P, si trova la funzione carattere discordante :

NB: (i) è l’i-esimo simbolo dell’alfabeto NB: (i) è l’i-esimo simbolo dell’alfabeto

:{1, 2,..., ||} {1,2,...,m}

[i] = max{k: 1km e P[k] = i}


22


Algoritmo per il calcolo della funzione carattere discordante

begin

m:=length(P);

foreach in do[]:=0;

for j:=1 to m do

[P[j]]:=j;return ;

end

Si verificano 3 casi...

23


Euristica del carattere discordante

CASO 1: il carattere discordante non appare nel pattern P


P sa t a t a c a

g

24



CASO 1: il carattere discordante non appare nel pattern P


P s+6a t a t a c a

lo spostamento è tale da allineare il primo carattere di P con il carattere di T successivo al carattere discordante

25



CASO 2: l’occorrenza più a destra in P del carattere discordante è in una posizione k minore dell’indice j che corrisponde al carattere di P allineato con il carattere discordante


P sa t g t a c a

g

g

26



CASO 2: l’occorrenza più a destra in P del carattere discordante è in una posizione k minore dell’indice j che corrisponde al carattere di P allineato con il carattere discordante

T g a c g a g a g a a g c g a tg

P s+3a t g t a c ag

lo spostamento è tale da allineare P[k] con il carattere discordante in T

27



CASO 3: l’occorrenza più a destra in P del carattere discordante è in una posizione k maggiore dell’indice j che corrisponde al carattere di P allineato con il carattere discordante

T g a c g a g g c g a g c g a t

P sa t g t a c g

g

g

28



CASO 3: l’occorrenza più a destra in P del carattere discordante è in una posizione k maggiore dell’indice j che corrisponde al carattere di P allineato con il carattere discordante

T g a c g a g g c g a g c g a t

P s+1a t g t a c g

g

g

si può solo effettuare lo spostamento di un posto a destra

29

T g a c g a g a c a c g c g a t

P sa a c g a c g


NB: la sottostringa P[2..5] coincide il suffissoP[5..7] e quindi con la sottostringa T[s+5..s+7]


E’ evidente che conviene spostare P in s’

j


k

30


P s’a a c g a c g


E’ evidente che conviene spostare P in s’


k


NB: la sottostringa P[2..5] coincide il suffissoP[5..7] e quindi con la sottostringa T[s+5..s+7]NB: si è così sicuri che esiste un matching per lasottostringa P[2..5]

NB: si è così sicuri che esiste un matching per lasottostringa P[2..5]

31


Intuitivamente...

Dato che il suffisso P[j+1, m] coincide con la sottostringa T[s+j+1, s+m], occorre trovare, se esiste,la posizione k<j più a destra tale che:

P[k] P[j]

P[k+1, k+m-j] = T[s+j+1, s+m]

NB: il confronto dei caratteri di P da k a k+m-j è superfluoNB: il confronto dei caratteri di P da k a k+m-j è superfluo

s'+k = s+j

e spostare P in s’+1 tale che

32


Formalmente...

Dato un pattern P, si trova la funzione suffisso :

: {0,1,...,m-1} {0,1,...,m-1}

[j] = max{k: k<j+1, P[j+1,...,m] suffisso di P[1..[j]+m-j] e P[k] P[j]}

33


Algoritmo per il calcolo della funzione suffisso

begin

m:=length(P); P’:=inverso(P);

:=funzione prefisso di P; //come KMP’:=funzione prefisso di P’; //come KMPfor j:=0 to m do

[j]:=m-[m];for l:=1 to m do

begin

j:=m-’[l]; if [j] > l - ’[l] then

[j]:=l-’[l];end

return end

34


Euristica del buon suffisso

CASO 1: k non esiste

si sposta P fino a far coincidere un suo prefisso con un suffisso di T[s+j+1..s+m], o di m passi se nessun prefisso di P è suffisso di T[s+j+1..s+m]

CASO 2: k esiste

si sposta P fino del numero minimo di passi per far coincidere un suo prefisso proprio con un suffisso dell’occorrenza di P in T, o di m passi se questo non esiste

35


Euristica del buon suffisso + Euristica del carattere discordante (esempio)


P sa a c g a c g

l’euristica del carattere discordante genererebbe uno spostamento in s+1

c

c

36




l’euristica del carattere discordante genererebbe uno spostamento in s+1

P s+1a a c g a c gc

c

37




P sa a c g a c g

l’euristica del buon suffissso genererebbe uno spostamento in s+4

38




l’euristica del buon suffissso genererebbe uno spostamento in s+4

P s+4a a c g a c g

l’euristica del buon suffissso genererebbe uno spostamento in s+4 che risulta essere lo spostamento da effettuare

39


n:=length(T);m:=length(P);:=BadCharacterRule(P);:=GoodSuffixRule(P);s:=0;while s ≤ n-m do

begin j:=m; while j > 0 and P[j] = T[s+j] do

j:=j-1; if j = 0 then

stampa(“pattern in posizione s+1”);s:=s+[0];

else s:=s+max([j], j-[T[s+j]]);

end

/*Pre-processing*/

/*Scansioneda destra*/

/*Propostaeuristiche*/

40

Exact Matching: algoritmo di Boyer-Moore

f a i s s c n r n t s i l c r s h b s

a c m i n i u l c n l c

a c m i n i u lc n l c

s

s + 4

Buon suffissoCar. discordante

......

s non valido

proposta del car. discordante

clncluinimcas + 3 proposta del buon

suffisso

Proposta vincente: carattere discordante

41

Caratteristiche dell’algoritmo BM

E’ suddiviso in due parti: pre-processing + ricerca effettiva

Sposta in genere il pattern P di più posizioni a destra

La fase di pre-processing è basata su due euristiche

Funziona “bene” se il pattern P è relativamente lungo e se l’alfabeto || è ragionevolmente grande


42

Caratteristiche dell’algoritmo BM

La complessità in tempo della fase di pre-processing è O(||+m)+O(m)=O(||+m)

La complessità in tempo della fase di ricerca è O(n-m+1)m=O(nm)

La complessità in tempo di BM è O(nm)


NB: nella pratica è più efficienteNB: nella pratica è più efficiente

UNIVERSITA DI MILANO-BICOCCA LAUREA MAGISTRALE IN BIOINFORMATICA Corso di BIOINFORMATICA: TECNICHE...

Documents

Transcript of UNIVERSITA DI MILANO-BICOCCA LAUREA MAGISTRALE IN BIOINFORMATICA Corso di BIOINFORMATICA: TECNICHE...