UNIVERSITA’ DI MILANO-BICOCCA
LAUREA MAGISTRALE IN
BIOINFORMATICA
Corso di
BIOINFORMATICA: TECNICHE DI BASE
Prof. Giancarlo Mauri
Lezione 6
Alberi di suffissi
Sommario
 Ricerca di stringhe
 Breve Storia degli Alberi dei Suffissi (ST)
 Definizioni
 Un esempio
 Algoritmo di Ukkonen
 Applicazioni degli Alberi dei Suffissi
 Bibliografia
2
Il problema: ricerca di stringhe
Ricerca delle occorrenze di una stringa P (di lunghezza m)
all’interno di un testo T (di lunghezza n)
T xyabcxabcxabcdeqfeg
P
abcxabcde
3
Il problema: ricerca di stringhe
Ricerca delle occorrenze di una stringa P (di lunghezza m)
all’interno di un testo T (di lunghezza n)
T
P
xyabcxabcxabcdeqfeg
abcxabcde
Risolvibile in tempo O(n+m) (O(m) per il preprocessing
di P e O(n) per la ricerca delle occorrenze di P in T)
tramite:
 algoritmo di Boyer-Moore
 algoritmo di Knuth-Morris-Pratt
4
La soluzione con alberi di suffissi
 Si impiega:
 un tempo O(n) per la costruzione dell’albero dei suffissi
(Suffix Tree, ST) di T
 un tempo O(m) per la ricerca delle occorrenze di P in T
 È possibile costruire il ST per il testo T una sola volta
e poi cercare più stringhe P in tempo proporzionale
alla lunghezza di ciascuna stringa
5
Breve storia degli alberi dei suffissi
 1973: Weiner inventa il primo algoritmo per la
costruzione di un albero dei suffissi (Position Tree) in
tempo lineare
 1976: McCreight inventa un algoritmo più efficiente
 1995: Ukkonen introduce un nuovo algoritmo in tempo
lineare più semplice dei precedenti
6
Definizione
 L’ Albero dei Suffissi  per una stringa T di n caratteri
è un albero radicato e orientato con n foglie numerate
da 1 a n tale che:
 Ogni nodo interno ha almeno due figli e ogni arco è
etichettato con una sottostringa non nulla di T
 Due archi uscenti dallo stesso nodo non possono avere
etichette che iniziano con lo stesso carattere
 Per ogni foglia i, la concatenazione delle etichette
relative al percorso dalla radice alla foglia i è il suffisso
di T che inizia alla posizione i e cioè T[i,m]
7
Esempio di albero dei suffissi
T: xabxac
R
b
x
a
w
b
a
a
x
c
c
u
a
c
x
c
c
1
b
x
4
a
c
3
6
5
2
Il percorso del
L’etichetta
conpercorso
etichetta<R,w,1>
xabx
u
L’arco
La
estring-depth
w sono
(R,w)
nodi
ha etichetta
di
interni
wè
xa
è xabxac
termina
in mezzo
ad
un2 arco
8
Proprietà di un ST
 L’etichetta di un percorso dalla radice a un nodo è la
concatenazione nell’ordine delle sottostringhe che etichettano
gli archi che costituiscono il percorso
 L’etichetta di percorso di un nodo è l’etichetta del percorso dalla
radice a quel nodo
 La profondità di un nodo v è il numero di caratteri nell’etichetta
di v
 Un percorso che termina nel mezzo di un arco (u,v) divide
l’etichetta di (u,v) in un punto prestabilito. L’etichetta di questo
percorso è l’etichetta di u concatenata con i caratteri sull’arco
(u,v) fino al punto di divisione.
9
Ricerca di una stringa mediante un
albero dei suffissi
Per cercare le occorrenze di P in T:
 Creare l’albero dei suffissi  di T in tempo O(n)
 Cercare in  il percorso etichettato P
 Se si raggiunge una foglia di  prima della fine di P o si
incontra sul percorso un carattere non contenuto in P
allora non vi sono occorrenze di P in T
 Altrimenti tutte le foglie del sottoalbero del percorso
avente P come etichetta sono i punti di T in cui vi è
un’occorrenza di P in T
10
Esempio (1)
T: xabxac
P: xa
R
b
x
a
w
b
a
a
x
c
c
u
a
c
x
c
c
b
1
x
4
a
c
3
6
5
2
Occorrenze alle posizioni 1 e 4
11
Esempio (2)
T: xabxac
P: ad
R
b
x
a
w
b
a
a
x
c
c
u
a
c
x
c
c
d?
b
1
x
4
a
c
3
6
5
2
Non vi sono occorrenze di P in T
12
Esempio (3)
T: xabxac
P: xacd
R
b
x
a
b
x
a
a
x
c
c
u
a
c
w
c
c
b
1
x
4
a
c
3
6
d?
5
2
Non vi sono occorrenze di P in T
13
Carattere di fine stringa ($)
La definizione di albero dei suffissi non garantisce l’esistenza di
un ST per ogni stringa T
Se un suffisso di T è uguale al prefisso di un altro suffisso di T,
tale suffisso non potrà terminare in una foglia
Soluzione
Basta aggiungere alla fine di T un carattere che non
compare mai in T ($ ad esempio)
14
Algoritmo di Ukkonen
Costruisce l’albero dei suffissi implicito per la stringa T
L’albero implicito dei suffissi è ottenuto rimuovendo tutte
le occorrenze del carattere di terminazione $ e di
conseguenza tutti gli archi che rimangono senza etichetta e
tutti i nodi con un solo figlio

Esempio per T=xabxa
b
x
a
x
R
a
b x
a $
$
a
$
$
$
b
1
b
x
4
a
x
a
3
6
5
$
3
2
R
x
a
b
a
x
a
1
b
x
a
2
15
Algoritmo di Ukkonen
Algoritmo di Ukkonen naive
Per i che va 1 a m-1
Per j che va da 1 a i+1
Estensione j
Fase i+1
Costruisci l’albero I1
Trova il punto in cui termina il
percorso (dalla radice) etichettato
con T[j..i] nell’albero corrente Ii.
Se necessario, estendi questo
percorso aggiungendo il carattere
T(i+1), assicurandoti così che la
stringa T[j..i+1] stia nell’albero Ii+1
NB: Ii è il ST implicito per il prefisso T[1,i]
16
Algoritmo di Ukkonen
Esempio di estensione
R
R
b
a
x
a
4
a
b
axabxb
x
a
b
x
b
a
x
x
x
3
2
1
Albero per la stringa axabx
b
bxb
x
b
x
4
a
b
x
b
abxb
b
b
x
b
x
b
x
b
5
3
xb
b
xabxb
2
1
Albero per la stringa axabxb
17
Algoritmo di Ukkonen
L’algoritmo naïve di Ukkonen genera in tempo O(n3) un
ST per un testo T lungo n
È possibile utilizzare alcuni accorgimenti:

Utilizzo di Suffix Links

Per ogni nodo interno v con etichetta di percorso x (dove  è
una stringa e x un singolo carattere) esiste un nodo s(v) con
etichetta di percorso . Un Suffix Link collega v a s(v)). I Suffix
Link, semplificando la ricerca dei suffissi durante le fasi
dell’algoritmo, consentono di raggiungere un tempo O(n2)
Le etichette di ciascun arco vengono rappresentate come una
coppia di indici (u,s) che indicano una sottostringa P[u,s] di P.
Questo consente di rappresentare l’albero dei suffissi con
un’occupazione di memoria pari a O(n)

18
Algoritmo di Ukkonen
Altri accorgimenti consentono di evitare di considerare più
volte gli stessi caratteri della stringa T e di raggiungere
quindi il limite O(n).
L’aggiunta del carattere $ di fine stringa e la trasformazione
dell’albero dei suffissi implicito in un albero dei suffissi reale
può essere effettuata in tempo O(n)
L’algoritmo di Ukkonen costruisce un albero dei
suffissi in tempo O(n)
19
Applicazioni degli alberi dei
suffissi
Ricerca esatta di stringhe
 Ricerca di stringhe
 Dato un testo T e un pattern P si vogliono ricercare
tutte le occorrenze di P nel testo T
 Ricerca di un set di pattern
 Dato un testo T e un insieme di pattern P={P1,…,Ps} si
vogliono ricercare tutte le occorrenze di uno qualsiasi
dei pattern Pi nel testo T
Una volta costruito l’albero dei suffissi di T, la ricerca di una
qualsiasi stringa P di lunghezza n richiede un tempo O(n)
21
Ricerca di un set di pattern
Ricerca da librerie di pattern di sequenze di DNA
 Sequence-Tagged Sites (STSs) e Expressed Sequence Tags
(ESTs)
 STS: è intuitivamente una sequenza di 200-300 nucleotidi le
cui code a dx e sx compaiono una sola volta nell’intero genoma.
Pertanto un STS compare una sola volta. Obiettivo originale
del HGP (Human Genome Project) era quello di identificare un
insieme di STS tale che ogni sottostringa del genoma di
lunghezza maggiore o uguale a 100.000 contenesse almeno
uno di questi STS
 EST: STS che compaiono in geni
 Una sequenza di DNA anonima può essere mappata sul genoma
ricercando gli STS contenuti in essa
22
Alberi di Suffissi generalizzati (1)
 Ricerca di una stringa in un database di stringhe (ad
es. ricerca di una sequenza di DNA in un database di
sequenze genomiche)
 Ricerca della sottostringa di lunghezza massima
comune a due stringhe
 Ricerca di DNA contaminato
 Si costruisce una stringa concatenando le sequenze di
DNA che possono aver contaminato la sequenza di DNA
sotto analisi
[…]
23
Alberi di Suffissi generalizzati (2)
 Ricerca di DNA contaminato (continua)
 Si estende l’approccio basato su ST generalizzati per la
ricerca di sottostringhe comuni alle due stringhe di
partenza
 Si registrano le occorrenze di sottostringhe comuni di
lunghezza superiore ad una soglia L. La presenza di
queste stringhe nella sequenza in esame può derivare da
una contaminazione avvenuta durante la procedura di
estrazione e sequenziazione del DNA.
24
Ricerca di sequenze ripetitive
 Estremamente comuni nell’analisi di DNA, RNA e
proteine
“Families of reiterated sequences account for about one third
of the human genome” [E. McConkey, 1993]

Complemented palindromes

Nested complemented palindromes

Geni che codificano molecole di RNA che devono
essere prodotte in grandi quantità

Restriction enzyme cutting sites

Tandem arrays
25
Ricerca di Maximal Pair
Un Maximal Repeat in una stringa T è una coppia di
sottostringhe identiche  e  tali che estendendo  e
 in qualsiasi direzione si distruggerebbe la loro
uguaglianza
Sia l’albero dei suffissi per la stringa S. Se
una stringa è un Maximal Repeat in S allora
è l’etichetta del percorso di uno dei nodi di .
26
Alberi di Suffissi nella ricerca
 Arabidopsis Thaliana (Michigan State Univ., Univ. of Minnesota)
Creazione della mappa degli EST del genoma dell’Arabidopsis. ST
utilizzati per la ricerca di contaminazioni e per la ricerca di
pattern biologicamente significativi
 Saccharomyces Cerevisiae (Max-Plank Institute)
ST utilizzati per la ricerca di sottostringhe nei database di
sequenze
 Borrelia Burgdorferi (Brookhaven National Laboratory) Sviluppo
di metodi, basati su ST, per il riassemblamento dei frammenti di
DNA sequenziati
27
Bibliografia
 D. Gusfield. Algorithms on strings, trees, and sequences.
Cambridge University Press, 1997
 P. Weiner. Linear pattern matching algorithms. Proc. Of the 14th
IEEE Symp. On Switching and Automata Theory, 1-11, 1973
 E. M. McCreight. A space-economical suffix tree contruction
algorithm. J. ACM, 23:262-72, 1976
 E. Ukkonen. On-line construction of suffix-trees. Algorithmica,
14:249-60, 1995
28