UNIVERSITA’ DI MILANO-BICOCCA
LAUREA MAGISTRALE IN
BIOINFORMATICA
Corso di
BIOINFORMATICA: TECNICHE DI BASE
Prof. Giancarlo Mauri
Lezione 5
Algoritmi di string matching esatto
Exact matching: il problema
DATE:
una stringa T di lunghezza n (detta testo) e
una stringa P di lunghezza m<n (detta pattern)
definite su un alfabeto S
TROVARE:
l’ insieme di tutte le posizioni nel testo T a partire da
cui occorre il pattern P
2
Exact matching: il problema
Esempio
P=aba
T=bbabaxababay
NB: le occorrenze di P in T possono
anche sovrapporsi (es. 7 e 9)
Algoritmo di
exact matching
{3,7,9}
3
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
4
Exact matching: prime idee

 Se



Allinea
Confronta,
Sposta
L’ultimo
hai raggiunto
ilPcarattere
primo
di da
un sinistra
posto
carattere
la di
fine
a
P ava
destra...
destra
didestra,
di
oltre
P, P con
lai il
Esempio
restituisci
primodicarattere
caratteri
fine
T. corrispondenti
la
Termina
posizione
di T
l’esecuzione
deldicarattere
P e T
di
fino
T che
a quando
corrisponde
trovi unal mismatch
primo
o
T = xabxyabxyabxz
carattere
raggiungi la
di fine
P =>di6 P
P = abxyabxz
T
x a b x y a b x y a b x z
P
a b
a
xy b
a
xy b
a
a
yxz b
a
xyz b
a
a
xz b
xz xz z
a b
x b
a
xy b
yx b
a
xyz b
5
Exact matching: prime idee
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 di
una sola posizione. Come aumentare lo
spostamento senza rischiare di perdere occorrenze?
6
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
7
Exact matching: preprocessing
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
S=AATGCATTCGCT
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
S=AATGCATTCGCT
8
Exact matching: preprocessing
Si supponga di essere nella seguente situazione con P
in s+1
T
P
g
a
s
c
g
a
g
a
g
a
a
g
a
g
a
g
a
c
a
c
g
a
t
q
k
NB: all’interno del matching lungo q=5 esiste la sottostringa
P[3..5] = aga che coincide con il prefisso P[1..3]
9
Exact matching: preprocessing
E’ evidente che conviene spostare P in
Si supponga di essere nella seguente situazione con P
s’+1 = s+(q-k)+1
in s
T
P
g
a
c
g
a
s’
s
q-k
g
a
g
a
a
g
c
g
a
g
a
g
a
c
a
a
t
k
NB: si
è così sicuri
che esiste
un matching
iniziale
di
all’interno
del matching
lungo
5 esiste la
sottostringa
lunghezza
k=3che
percoincide
il prefisso
P[1..3]
P[3..5]=“aga”
con
il prefisso P[1..3]
10
Exact matching: preprocessing
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 è superfluo
11
Exact matching: preprocessing
Formalmente...
Dato un pattern P[1, …, m], si calcola la sua funzione prefisso
p: {1,2,...,m} {0,1,...,m-1}
p[q] = max{k: k<q e P[1..k] è suffisso di P[1..q]}
NB: p[q] è la lunghezza del più lungo prefisso di P che
è anche suffisso di P[1..q]
1
k
q
m
12
Exact matching: preprocessing
Algoritmo per il calcolo della funzione prefisso p
begin
m:=length(P);
p(1):=1; k:=0;
for q:=2 to m do
begin
while P[k+1]P[q] do
k:=p[k];
if P[k+1]=P[q] then
k:=k+1;
p[q]:=k;
end
return p;
end
13
Exact matching: preprocessing
Esempio di funzione prefisso p per un pattern P
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15
P[q]
g
a
c
g
a
g
a
g
a
a
g
c
g
a
t
p[q]
0
0
0
1
2
1
2
1
2
a
1
0
1
2
0
q
14
Algoritmo di Knuth-Morris-Pratt
Algoritmo di Knuth-Morris-Pratt
begin
n:= length(T); m:=length(P);
p:= precomputed prefix function of P;
q:=0;
Numero di matches
for i:=1 to n do
Scansione da sx a dx
begin
while q>0 and P[q+1]T[i] then Il prossimo carattere è diverso
q:=p[q];
if P[q+1]=T[i] then
Il prossimo carattere è uguale
q:=q+1;
Trovata occorrenza di P
if q=m then
print “pattern in i-m+1”;
Cerca nuova occorrenza
q:=p[q];
end
end
15
Algoritmo di Knuth-Morris-Pratt
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)
16
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 il
massimo tra gli spostamenti proposti dalle due euristiche
17
Algoritmo di Boyer-Moore
Si evidente
E’
supponga che
di essere
conviene
nella
spostare
seguente
P insituazione con P
in s
s’+1 = s+1+j-k
T
P
g
a
s
c
g
a
g
a
g
a
a
g
a
g
a
g
a
c
a
k
c
g
a
t
j
NB: il carattere P[4] coincide con il carattere
T[s+7]
18
Algoritmo di Boyer-Moore
E’ evidente che conviene spostare P in s’+1 = s+1+jk
T
P
g
a
c
s’
g
a
g
a
g
a
a
g
c
g
a
a
g
a
g
a
c
a
t
k
NB: il carattere P[4] coincide con il carattere
T[s+7]
19
Algoritmo di Boyer-Moore
Intuitivamente...
Dato che esiste un j (1jm) per cui P[j]  T[s+j],
trovare il massimo k (1km), se esiste, tale che:
P[k] = T[s+j]
e spostare P in s’+1 tale che
s'+k = s+j
20
Algoritmo di Boyer-Moore
Formalmente...
Dato un pattern P, si trova la funzione carattere
discordante l:
l:{s1, s2,..., s|S|}  {1,2,...,m}
l[si] = max{k: 1km e P[k] = si}
NB: s(i) è l’i-esimo simbolo dell’alfabeto S
21
Algoritmo di Boyer-Moore
Algoritmo per il calcolo della funzione carattere
discordante l
begin
m:=length(P);
foreach s in S do
l[s]:=0;
for j:=1 to m do
l[P[j]]:=j;
return l;
end
Si verificano 3 casi...
22
Algoritmo di Boyer-Moore
Euristica del carattere discordante
CASO 1: il carattere discordante non appare nel pattern P
T
P
g
a
s
c
g
a
g
a
g
a
a
t
a
t
a
c
a
a
g
c
g
a
t
23
Algoritmo di Boyer-Moore
Euristica del carattere discordante
CASO 1: il carattere discordante non appare nel pattern P
T
P
g
a
c
g
s+6
a
g
a
g
a
a
g
c
g
a
t
a
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
24
Algoritmo di Boyer-Moore
Euristica del carattere discordante
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
P
g
a
s
c
g
a
g
a
g
a
a
t
g
t
a
c
a
a
g
c
g
a
t
25
Algoritmo di Boyer-Moore
Euristica del carattere discordante
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
P
g
a
c
s+3
g
a
g
a
g
a
a
g
c
a
t
g
t
a
c
a
g
a
t
lo spostamento è tale da allineare P[k] con il carattere
discordante in T
26
Algoritmo di Boyer-Moore
Euristica del carattere discordante
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
P
g
a
s
c
g
a
g
g
c
g
a
t
g
t
a
c
g
a
g
c
g
a
t
27
Algoritmo di Boyer-Moore
Euristica del carattere discordante
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
P
g
a
s+1
c
g
a
g
g
c
g
a
a
t
g
t
a
c
g
g
c
g
a
si può solo effettuare lo spostamento di un posto a
destra
t
28
Algoritmo di Boyer-Moore
Si
E’ supponga
evidente che
di essere
conviene
nella
spostare
seguente
P in
situazione
s’
con P
in s
T
P
g
a
s
c
g
a
g
a
c
a
c
g
a
a
c
g
a
c
g
c
g
a
t
k
j
NB: la sottostringa P[2..5] coincide il suffisso
P[5..7] e quindi con la sottostringa T[s+5..s+7]
29
Algoritmo di Boyer-Moore
Si evidente
E’
supponga che
di essere
conviene
nella
spostare
seguente
P insituazione
s’
con P
in s
T
P
g
a
c
s’
g
a
g
a
c
a
c
g
c
g
a
a
a
c
g
a
c
g
t
k
NB: si
la èsottostringa
così sicuri P[2..5]
che esiste
coincide
un matching
il suffisso
per la
P[5..7] e quindi
sottostringa
P[2..5]
con la sottostringa T[s+5..s+7]
30
Algoritmo di Boyer-Moore
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]
e spostare P in s’+1 tale che
s'+k = s+j
NB: il confronto dei caratteri di P da k a k+m-j è superfluo
31
Algoritmo di Boyer-Moore
Formalmente...
Dato un pattern P, si trova la funzione suffisso g:
g: {0,1,...,m-1}  {0,1,...,m-1}
g[j] = max{k: k<j+1, P[j+1,...,m] suffisso di P[1..g[j]+m-j]
e P[k]  P[j]}
32
Algoritmo di Boyer-Moore
Algoritmo per il calcolo della funzione suffisso g
begin
m:=length(P); P’:=inverso(P);
p:=funzione prefisso di P; //come KMP
p’:=funzione prefisso di P’; //come KMP
for j:=0 to m do
g[j]:=m-p[m];
for l:=1 to m do
begin
j:=m-p’[l];
if g[j] > l - p’[l] then
g[j]:=l-p’[l];
end
return g
end
33
Algoritmo di Boyer-Moore
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
34
Algoritmo di Boyer-Moore
Euristica del buon suffisso + Euristica del carattere
discordante (esempio)
T
P
g
a
s
c
g
a
g
a
c
a
c
g
a
a
c
g
a
c
g
c
g
a
t
l’euristica del carattere discordante genererebbe uno
spostamento in s+1
35
Algoritmo di Boyer-Moore
Euristica del buon suffisso + Euristica del carattere
discordante (esempio)
T
P
g
a
c
s+1
g
a
g
a
c
a
c
g
c
a
a
c
g
a
c
g
g
a
t
l’euristica del carattere discordante genererebbe uno
spostamento in s+1
36
Algoritmo di Boyer-Moore
Euristica del buon suffisso + Euristica del carattere
discordante (esempio)
T
P
g
a
s
c
g
a
g
a
c
a
c
g
a
a
c
g
a
c
g
c
g
a
t
l’euristica del buon suffissso genererebbe uno
spostamento in s+4
37
Algoritmo di Boyer-Moore
Euristica del buon suffisso + Euristica del carattere
discordante (esempio)
T
P
g
a
c
g
s+4
a
g
a
c
a
c
g
c
g
a
a
a
c
g
a
c
g
t
l’euristica del buon suffissso genererebbe uno
l’euristica
delinbuon
uno
spostamento
s+4 suffissso
che risultagenererebbe
essere lo spostamento
da
spostamento
effettuare in s+4
38
Algoritmo di Boyer-Moore
n:=length(T);
m:=length(P);
l:=BadCharacterRule(P);
/*Pre-processing*/
g:=GoodSuffixRule(P);
s:=0;
while s ≤ n-m do
begin
j:=m;
while j > 0 and P[j] = T[s+j] do
/*Scansione
j:=j-1;
da destra*/
if j = 0 then
stampa(“pattern in posizione s+1”);
s:=s+g[0];
else
/*Proposta
s:=s+max(g[j], j-l[T[s+j]]);
euristiche*/
end
39
Exact Matching: algoritmo di BoyerMoore
Car. discordante
...
Buon suffisso
f a i s s c n r n t s i l c r s hb s
s
a cm i n i u l c n l c
s+4
s+3
a cm i n i u l c n l c
a cm i n i u l c n l c
...
s non valido
proposta del car.
discordante
proposta del buon
suffisso
Proposta vincente: carattere discordante
40
Algoritmo di Boyer-Moore
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 |S| è ragionevolmente grande
41
Algoritmo di Boyer-Moore
Caratteristiche dell’algoritmo BM
 La complessità in tempo della fase di pre-processing
è O(|S|+m)+O(m)=O(|S|+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ù efficiente
42