All-Against-All All-Against-All Sequence Matching Sequence Matching

All-Against-All All-Against-All

Sequence Matching Sequence Matching

Implementazione Mediante Suffix Array Implementazione Mediante Suffix Array

e Analisi Prestazionale Comparata e Analisi Prestazionale Comparata

Corelatori:

Corelatori:

Dott. Federica Mandreoli Dott. Federica Mandreoli Ing. Riccardo Martoglia Ing. Riccardo Martoglia Relatore:

Relatore:

Prof. Paolo Tiberio Prof. Paolo Tiberio Tesi di:

Tesi di:

Dario Gelmini Dario Gelmini

Dati due insiemi di Dati due insiemi di

sequenze A e B sequenze A e B

Confrontare tutte le sotto- Confrontare tutte le sotto-

sequenze di A sequenze di A

con tutte le sotto-sequenze con tutte le sotto-sequenze

di B di B

indicandone il grado di indicandone il grado di

Similitudine Similitudine

Proble Proble

ma ma

… … A A A C T G T T A … A A A C T G T T A … … … C T A G T A T A G… C T A G T A T A G…

Sequenza A

Sequenza A Sequenza B Sequenza B

CT CT GT GT

TA TA

Sottosequenze Comuni

Sottosequenze Comuni

Come Come

Procedere Procedere

• Scansione delle sequenze Scansione delle sequenze

• Valutazione delle Coppie Valutazione delle Coppie

Coppie di Coppie di

Sottoseque Sottoseque

nze nze

Distanz Distanz

a a

e e

Lunghez Lunghez

za za

Minima

Minima

Edit Edit

Distance Distance

A C T G T

A C T G T A C T T T G T A A C T T T G T A

A C T T T G T A 0 1 2 3 4 5 6 7 8 A 1 0 1 2 3 4 5 6 7 C 2 1 0 1 2 3 4 5 6 T 3 2 1 0 1 2 3 4 5 G 4 3 2 1 1 2 2 3 4 T 5 4 3 2 1 1 2 2 3

C C

se se lettera uguale

lettera uguale

C C _{i,j i,j} = =

1 + Max(C 1 + Max(C

, C , C

, ,

C C

) ) altrimenti altrimenti

D B D B Sequenze Sequenze

A C T

0 1 2 3

A 1 0 1 2 C 2 1 0 1

A C T T G

A C T T G :: G C T T A G C T T A A C T T G

A C T T G :: T T A T T A A C T T G

A C T T G :: T A T A A C T T G A C T T G :: A A C T T G

C T T G :: C T T A C T T A C T T G

C T T G :: T T A T T A C T T G

C T T G :: T A T A C T T G C T T G :: A A

2 2 22 33 4 4 55 22 1 1 22

Creazione Indice Creazione Indice

sul DB delle Sequenze sul DB delle Sequenze Esplorazione Ricorsiva Esplorazione Ricorsiva

dei due Indici dei due Indici

Calcolo della distanza Calcolo della distanza

per ogni Coppia per ogni Coppia

Filtro sulle Distanze Filtro sulle Distanze

[Baeza-Yates, Gonnet, 1999]

[Baeza-Yates, Gonnet, 1999]

(Sequenze Genetiche) (Sequenze Genetiche)

Suffix Tree Suffix Tree

A C T T T A C T T T

G T A G T A

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

1 1 8 8 2 2

6 6

3 3 4 4 5 5

7 7

AA

AA GG TT

TT TT

CC

GG

GG CC

$$ 11

22

33 //

A A C C

$ $

T T T T T T

Algoritmo

Algoritmo [Baeza-Yates, [Baeza-Yates, Gonnet, 1999]

Gonnet, 1999]

1 1 2 2

5 5

3 3 4 4

AA

TT TT

CC

GG

GG 11 //

1 1 2 2

5 5

3 3

4 4

GG

TT TT

CC

AA

AA 11 //

A C T T G

A C T T G G C T T AG C T T A

1 2 3 4 51 2 3 4 5 1 2 3 4 51 2 3 4 5

A C T T G

A C T T G : G C T T A: G C T T A A C T T G

A C T T G : C T T A: C T T A A C T T G

A C T T G : T T A: T T A A C T T G

A C T T G : T A: T A A C T T G

A C T T G : A: A C T T G

C T T G : G C T T A: G C T T A C T T G

C T T G : C T T A: C T T A C T T G

C T T G : T T A: T T A C T T G

C T T G : T A: T A C T T G

C T T G : A: A

22 22 33 44 55 22 11 22 33 44

A C T T T G T A A C T T T G T A C T T T G T A C T T T G T A T T T G T A T T T G T A T T G T A T T G T A T G T A T G T A G T A G T A T AT A AA AA

A C T T T G T A A C T T T G T A C T T T G T A C T T T G T A G T A

G T A T AT A

T G T A T G T A T T G T A T T G T A T T T G T A T T T G T A

88 11 22 66 77 55 44 33

Implementaz Implementaz ione ione

(Suffix Tree con (Suffix Tree con Suffix Array) Suffix Array)

1 1 8 8 2 2

6 6

3 3 4 4 5 5 7 7

AA

AA GG TT

TT TT

CC

GG

GG CC

$$ 11

22

33 //

A C T T T G T A A C T T T G T A

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

C T T T G T A C T T T G T A T T T G T A T T T G T A T T G T A T T G T A T G T A T G T A G T A G T A T AT A

AA

Suffix Tree

Suffix Tree Suffix Array Suffix Array

[Baeza-Yates, Gonnet]

[Baeza-Yates, Gonnet]

Suffix Array Suffix Array

T T C CT T C C

1 2 3 4 1 2 3 4

CC C CC C

T T C C C C

T T C C T T C C 44

33 22 11

C C : G: G C C :: G G G G C C :: T G G T G G C C : T T G G: T T G G C C

C C :: G G C C

C C :: G G G G C C

C C :: T G G T G G C C

C C :: T T G G T T G G T C C

T C C :: G G T C C

T C C :: G G G G T C C

T C C :: T G G T G G T C C

T C C :: T T G G T T G G T T C C

T T C C :: G G T T C C

T T C C :: G G G G T T C C

T T C C :: T G G T G G

T T G GT T G G

1 2 3 4 1 2 3 4

GG G GG G

T T G G G G

T T G G T T G G 44

33 22 11

T T C 2 2 22 2 2 CC T T C C C T 2 2T 2 2 12 2 12 2 12 2 22 2 22 2 12 22 22 2

Applicazione Applicazione

dei Filtri dei Filtri

A A A C A A A C C C C A C C C A

1 2 3 4 1 2 3 4

AA

A C A C

A A C A A C

A A A C A A A C 44

33 22 11

T T T C T T T C C C C C T C C T

1 2 3 4 1 2 3 4

CC

C T C T

C C C T C T

C C C T C C C T 44

33 22 11 CC

C A C A

C C A C C A

C C C A C C C A 44

33 22 11

TT

T T C C

T T T C T C

T T T C T T T C 44

33 22 11

Massima Distanza = 1 Massima Distanza = 1

11 22 22 22 22 11 11 11

11 22

11 22

AA

0 10 1 C C 1 11 1

AA

0 10 1 T T 1 11 1 C C 2 22 2

A CA C

0 1 20 1 2 C C 1 1 11 1 1

T 2 2T 2 2 T T 3 3 23 3 2 C C 3 3 23 3 2

A CA C

0 1 20 1 2 T

T 1 1 1 1 2 2

Minima Lunghezza = 2 Minima Lunghezza = 2

Lunghezza Minima Lunghezza Minima

[Mandreoli, Martoglia, [Mandreoli, Martoglia,

Tiberio, 2002]

Tiberio, 2002]

(Sequenze Testuali) (Sequenze Testuali)

D B D B Sequenze Sequenze

A C T

0 1 2 3

A 1 0 1 2 C 2 1 0 1

A C T T G

A C T T G :: G C T T A G C T T A A C T T G

A C T T G :: T T A T T A A C T T G

A C T T G :: T A T A A C T T G A C T T G :: A A C T T G

C T T G :: C T T A C T T A C T T G

C T T G :: T T A T T A C T T G

C T T G :: T A T A C T T G C T T G :: A A

2 2 22 33 4 4 55 22 1 1 22

Impostazione Parametri Impostazione Parametri di minima Lunghezza e di minima Lunghezza e di massima Distanza di massima Distanza dei filtri

dei filtri

Filtraggio delle sequenze Filtraggio delle sequenze ed estrapolazione coppie ed estrapolazione coppie potenzialmente simili

potenzialmente simili Calcolo della distanza Calcolo della distanza per ogni coppia

per ogni coppia

Filtro sulle Distanze Filtro sulle Distanze SubSub²²Position Position

SubSub²²CountCount

Filtri Filtri

Prestazioni

Prestazioni (Analisi (Analisi dei Risultati)

dei Risultati) Filtro sulla Massima Distanza Filtro sulla Massima Distanza

Aumento Sopralineare dei tempi Aumento Sopralineare dei tempi all’aumentare della massima all’aumentare della massima distanza consentita

distanza consentita

Conseguenza dell’applicazione della Conseguenza dell’applicazione della funzione di Edit Distance a tutte le funzione di Edit Distance a tutte le coppie

coppie

Filtro sulla Minima Lunghezza Filtro sulla Minima Lunghezza

Diminuzione lineare dei tempi al Diminuzione lineare dei tempi al Aumentare della lunghezza minima Aumentare della lunghezza minima richiesta

richiesta

Conseguenza dell’operazione di filtro Conseguenza dell’operazione di filtro eseguita senza il calcolo della

eseguita senza il calcolo della distanza

distanza

Confronto

Confronto [Baeza-Yates, Gonnet] - [Baeza-Yates, Gonnet] - [Mandreoli, Martoglia, Tiberio]

[Mandreoli, Martoglia, Tiberio]

Scarse Prestazioni su Scarse Prestazioni su

sequenze Testuali sequenze Testuali

Prestazioni Interessanti Prestazioni Interessanti su sequenze Genetiche su sequenze Genetiche

Conclus Conclus ioni ioni

Implementazione Implementazione

• Suffix Tree con Suffix Array Suffix Tree con Suffix Array (Modificato) (Modificato)

• Edit Distance con Corner Edit Distance con Corner (Modificato) (Modificato)

• Algoritmo di [Baeza-Yates, Gonnet] con Suffix Array Algoritmo di [Baeza-Yates, Gonnet] con Suffix Array Analisi delle Prestazioni

Analisi delle Prestazioni

• Discrete Prestazioni su Insiemi di Sequenze Genetiche Discrete Prestazioni su Insiemi di Sequenze Genetiche

• Pessime Prestazioni su Insiemi di Sequenze Testuali Pessime Prestazioni su Insiemi di Sequenze Testuali

• Verifica di validita delle tecniche di Pre-Filtering Verifica di validita delle tecniche di Pre-Filtering