All-Against-All Sequence Matching
Implementazione Mediante Suffix Array
e Analisi Prestazionale Comparata
Tesi di:
Dario Gelmini
Relatore:
Prof. Paolo Tiberio
Corelatori:
Dott. Federica Mandreoli
Ing. Riccardo Martoglia
Problema
Dati due insiemi di sequenze A e B
Confrontare
tutte le sotto-sequenze
Sequenza
A
Sequenza Bdi A
con tutte le sotto-sequenze di B
…Aindicandone
A A C T G T ilT grado
A … di Similitudine
…C T A G T A T A G…
CT
GT
TA
Sottosequenze Comuni
Come Procedere
• Scansione delle sequenze
Coppie di
Sottosequenze
Distanza
• Valutazione delle Coppie
e
Lunghezza
Minima
Edit Distance
A C T G T
A C T T T G T A
A C T
1
C0i-1,j-1
Ci,j =
T
T
G T
A
2
3
4
5
6 se 7lettera
8 uguale
A 1
0
1
2
3
4
5
6
7
C 2
1
0
1
2
3
4
5
6
T
2 1 0 ,1C 2 , C
3 4)
13 + Max(C
i-1,j-1
i-1,j
i,j-1
G 4
3
2
1
1
2
2
3
5altrimenti
4
T
4
3
2
1
1
2
2
3
5
[Baeza-Yates, Gonnet, 1999]
(Sequenze Genetiche)
Creazione Indice
sul DB delle Sequenze
A
C
T
0
1
2
3
A
1
0
1
2
C
2
1
0
1
Esplorazione Ricorsiva
dei due Indici
Calcolo della distanza
per ogni Coppia
DB
Sequenze
A
A
A
A
C
C
C
C
C
C
C
C
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
G
G
G
G
G :
G :
G :
G :
: C
: T
: T
: A
G C T T A
T T A
T A
A
T T A
T A
A
2
2
3
4
5
2
1
2
Filtro sulle Distanze
Suffix Tree
1 2 3 4 5 6 7 8
A C T T T G T A
C
1
$
A
C
1
8
2
T
/
T
T
G
3
2
G
A
5
7
6
G
3
4
T
A
C
T
$
T
Algoritmo [Baeza-Yates, Gonnet, 1999]
1
2 3
4
5
1
1
G
/
T
T
1 G
G
5
5
A
A
A
A
A
1
C 2
C 2
/
4
G C T T A
A C T T G
A
2 3
3
4
T
T
1 A
A
5
3
4
C
C
C
C
C
C
C
C
C
C
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
G
G
G
G
G
G
G
G
G
G
:
:
:
:
:
:
:
:
:
:
G C T T A
C T T A
T T A
T A
A
G C T T A
C T T A
T T A
T A
A
2
2
3
4
5
2
1
2
3
4
Implementazione
(Suffix Tree con Suffix Array)
1 2 3 4 5 6 7 8
Suffix Tree
C
1
$
A
C
C T T T G T A
1
T T T G T A
8
T T G T A
T G T A
2
T
/
T
T
G
3
2
G
A
5
7
6
Suffix Array
A C T T T G T A
G
3
4
G T A
T A
A
8
1
2
6
7
5
4
3
A C T T
C C
T T T
A
T T T G
C
T
T TT G
G
AT
G T A
T A
GG
T A
T
T A
T A
T G T
AT T G
T
T G T A
G
T AT A
T G
T AT A
G
A
A
T A
[Baeza-Yates, Gonnet] con Suffix Array
1
2
3
4
1
T T C C
4
3
2
1
C
C C
T C C
T T C C
2
3
4
T T G G
4
3
2
1
G
G G
T G G
T T G G
C
C
C
C
:
:
:
:
G
G G
T G G
T T G G
C
C
C
C
C
C
C
C
:
:
:
:
G
G G
T G G
T T G G
T
T
T
T
C
C
C
C
C
C
C
C
:
:
:
:
G
G G
T G G
T T G G
T
T
T
T
T
T
T
T
C
C
C
C
C
C
C
C
:
:
:
:
G
G G
T G G
T T G G
Applicazione dei Filtri
Massima Distanza = 1
1
1
2
2
3
4
1
A A A C
C C C A
1
2
2
3
4
T T T C
C C C T
Minima Lunghezza = 2
Lunghezza Minima
2
1
1
1
4
3
2
1
A
A C
A A C
A A A C
1
2
2
2
4
3
2
1
C
C T
C C T
C C C T
1
2
2
2
4
3
2
1
C
C A
C C A
C C C A
2
1
1
1
4
3
2
1
T
T C
T T C
T T T C
TT
C
CTCT
CT
0
11
22
3
A
1
11
222
3
C
2
21
12
2
[Mandreoli, Martoglia, Tiberio, 2002]
(Sequenze Testuali)
Filtri
Sub2Position
Sub2Count
DB
Sequenze
A
A
A
A
C
C
C
C
A
C
T
0
1
2
3
A
1
0
1
2
C
2
1
0
1
C
C
C
C
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
G
G
G
G
G :
G :
G :
G :
: C
: T
: T
: A
G C T T A
T T A
T A
A
T T A
T A
A
Impostazione Parametri
di minima Lunghezza e
di massima Distanza
dei filtri
Filtraggio delle sequenze
ed estrapolazione coppie
potenzialmente simili
2
2
3
4
5
2
1
2
Calcolo della distanza
per ogni coppia
Filtro sulle Distanze
Prestazioni (Analisi dei Risultati)
Filtro sulla Massima Distanza
Aumento Sopralineare dei tempi
all’aumentare della massima
distanza consentita
Conseguenza dell’applicazione della
funzione di Edit Distance a tutte le
coppie
Filtro sulla Minima Lunghezza
Diminuzione lineare dei tempi al
Aumentare della lunghezza minima
richiesta
Conseguenza dell’operazione di filtro
eseguita senza il calcolo della
distanza
Confronto [Baeza-Yates, Gonnet] - [Mandreoli, Martoglia, Tiberio]
Scarse Prestazioni su
sequenze Testuali
Prestazioni Interessanti
su sequenze Genetiche
Conclusioni
Implementazione
• Suffix Tree con Suffix Array (Modificato)
• Edit Distance con Corner (Modificato)
• Algoritmo di [Baeza-Yates, Gonnet] con Suffix Array
Analisi delle Prestazioni
• Discrete Prestazioni su Insiemi di Sequenze Genetiche
• Pessime Prestazioni su Insiemi di Sequenze Testuali
• Verifica di validita delle tecniche di Pre-Filtering