Efficient q-Gram Filters
for Finding All -Matches
over a Given Length
Kim R. Rasmussen, Jens Stoye, Eugene W. Myers
Seminario di:
Francesca Pratesi
Giacomo Righetti
Q-Gram Filters for Finding All
-Matches
Sommario
• Motivazioni biologiche del problema
• Differenze tra algoritmo esatto,
euristiche e filtri
• Definizione del problema
• Formulazione semplificata
- alcuni esempi
- condizioni di filtraggio
- algoritmo proposto
• Formulazione completa
- condizioni di filtraggio
- algoritmo completo
- complessità
• Applicazioni e risultati sperimentali
Q-Gram Filters for Finding All
-Matches
Motivazioni biologiche
Comparare sequenze biomolecolari A, B ∑*
È interessante ricercare sequenze omologhe
• L’omologia (carattere qualitativo) fa riferimento
ad una relazione evolutiva presente o assente.
• La similarità (carattere quantitativo) fa riferimento
al grado di similitudine che viene misurato tra due
sequenze precedentemente allineate.
• Allineare due o più sequenze vuol dire determinare
una relazione tra le sequenze in modo da rendere
massimo il grado di similarità
• L’allineamento può essere globale oppure locale
Q-Gram Filters for Finding All
-Matches
Motivazioni biologiche
Sequence similarity
• Si possono identificare delle regioni funzionali
(ad esempio siti, geni o proteine) in sequenze
biologiche
– Da queste regioni è possibile ricavare altre informazioni;
ad esempio, attraverso la ricerca di similarità tra siti di
restrizione è possibile localizzare potenziali enzimi di
restrizione (Rebase software di R. Roberts)
– C'è un algoritmo derivato da Smith-Waterman che serve
per trovare potenziali geni gRNA (che guida la modifica del
criptogene) da un dato criptogene (gene originale)
– Le trascriptasi inverse sono proteine omologhe, usate da
alcuni tipi di retrovirus (Moloney murine leukemia e HIV
Type I) per replicare la propria informazione genetica che è
conservata nell'RNA
Q-Gram Filters for Finding All
-Matches
Motivazioni biologiche
Sequence similarity
Methanocaldococcus Jannaschii: ha delle caratteristiche degli
eucarioti (proteine coinvolte nella trascrizione, traduzione e
regolazione) e altre dei procarioti (assenza di membrana
nucleare, proteine del metabolismo)
Ricerca degli effetti della sclerosi multipla: la sclerosi multipla è
una malattia autoimmune nella quale il sistema immunitario
attacca le cellule nervose del paziente
È stato ipotizzato che le proteine delle guaine di mielina
identificate dalle T-cellule siano simili quelle di alcuni virus o
batteri
Sono state effettuate delle ricerche che hanno portato
all’identificazione di certi epitopi (di batteri e di virus) che
potevano essere confuse con le proteine delle guaine
protettive di mielina
Q-Gram Filters for Finding All
-Matches
Motivazioni biologiche
Sequence assembly
Un programma (assemblatore) allinea i
frammenti e, sfruttando le parti che essi
hanno in comune, li mette insieme. Viene
ricostruita così la sequenza originale
I frammenti sono generati:
• tramite shotgun sequencing: il DNA viene
diviso in modo casuale in milioni di frammenti
(che possono essere letti)
• dalla trascrizione di geni (ESTs)
Q-Gram Filters for Finding All
-Matches
Motivazioni biologiche
EST clustering
Le Expressed Sequence Tag sono dei brevi
frammenti di DNA trascritti e sequenziati da
una sequenza di cDNA (mRNA risultante dopo il
processo di splicing) più lunga
Le EST sono strutture indispensabili per la
scoperta di geni e lo studio del genoma
Un singolo EST rappresenta una sequenza
parziale di un gene
L’obiettivo è raggruppare EST appartenenti allo
stesso gene; per poterli raggruppare, questi si
devono sovrapporre e la distanza tra i
frammenti non deve superare una certa soglia
Q-Gram Filters for Finding All
-Matches
Sommario
• Motivazioni biologiche del problema
• Differenze tra algoritmo esatto,
euristiche e filtri
• Definizione del problema
• Formulazione semplificata
- alcuni esempi
- condizioni di filtraggio
- algoritmo proposto
• Formulazione completa
- condizioni di filtraggio
- algoritmo completo
- complessità
• Applicazioni e risultati sperimentali
Q-Gram Filters for Finding All
-Matches
Come risolvere il problema?
Tipologie di algoritmo:
• esatto
• euristico
• filtro
Q-Gram Filters for Finding All
-Matches
Che cos’è un filtro
• Serve per ridurre l’area di ricerca
• Elimina le sottostringhe che sicuramente
non soddisfano il problema
• Può restituire dei falsi positivi
• È necessario applicare un algoritmo esatto sul
risultato restituito (la dimensione dell’input è
ridotta)
• Si basa su una condizione necessaria
Q-Gram Filters for Finding All
-Matches
Che cos’è un filtro (2)
A
B
Fase di
filtraggio
Fase di
verifica
Match potenziali
Falsi positivi
Match reali
Q-Gram Filters for Finding All
-Matches
Che cos’è un filtro (2)
Preprocessing
Indice
A
B
Fase di
filtraggio
Fase di
verifica
Match potenziali
Falsi positivi
Match reali
Q-Gram Filters for Finding All
-Matches
Lavori precedenti
• L’inefficienza di Smith-Waterman ha motivato lo
sviluppo di euristiche quali FASTA (1988) e BLAST
(1990-97)
• Il primo algoritmo di filtraggio è stato quello di
Ukkonen (1992)
• QUASAR (Burkhardt 1999) basato sul precedente
• SSAHA (Ning 2001) e BLAT (Kent 2002)
• FLASH (Califano, Rigoutos 1993)
Q-Gram Filters for Finding All
-Matches
Sommario
• Motivazioni biologiche del problema
• Differenze tra algoritmo esatto,
euristiche e filtri
• Definizione del problema
• Formulazione semplificata
- alcuni esempi
- condizioni di filtraggio
- algoritmo proposto
• Formulazione completa
- condizioni di filtraggio
- algoritmo completo
- complessità
• Applicazioni e risultati sperimentali
Q-Gram Filters for Finding All
-Matches
Definizione del problema
allineamento (L)
sequenza di operazioni (inserzione,
cancellazione, sostituzione) per far sì che B sia uguale ad A
δ(L)
numero di operazioni in L
distδ(A,B)
min{δ(L)}
distδ (A,B)
|B |
error rate ()
q-gram
sottostringa di lunghezza q
q-hit
coppia (i,j) tale che A[i, i+q-1]=B[j, j+q-1]
Q-Gram Filters for Finding All
-Matches
Alcuni esempi
0
1 2 3
4 5
6
7 8 9 10 11 12 13 14
A = ACCTTTGCAAACGTA
B = CGCAAACCGTTTGC
5-gram:
A
{ACCTT,CCTTT,CTTTG,TTTGC,TTGCA,TGCAA,
GCAAA,CAAAC,AAACG,AACGT,ACGTA}
B
{CGCAA,GCAAA,CAAAC,AAACC,AACCG,ACCGT,C
CGTT,CGTTT,GTTTG,TTTGC}
Q-Gram Filters for Finding All
-Matches
Alcuni esempi
0
1 2 3
4 5
6
7 8 9 10 11 12 13 14
A = ACCTTTGCAAACGTA
B = CGCAAACCGTTTGC
5-gram:
A
{ACCTT,CCTTT,CTTTG,TTTGC,TTGCA,TGCAA,
GCAAA,CAAAC,AAACG,AACGT,ACGTA}
B
{CGCAA,GCAAA,CAAAC,AAACC,AACCG,ACCGT,C
CGTT,CGTTT,GTTTG,TTTGC}
5-hit:
{ (CAAAC,7,2) , (TTTGC,3,9) }
Q-Gram Filters for Finding All
-Matches
Definizione del problema
Trovare gli -match (allineamento locale
con error rate al più )
Input: due stringhe A e B, una lunghezza
minima n0 ed un error rate massimo 
Output: tutti gli -match(α,β) dove α e β
sono sottostringhe di A e B e |β|n0 e
distδ(α,β) β
Q-Gram Filters for Finding All
-Matches
Idea di base
• Cercare tutti i q-hit tra le due stringhe
• Identificare le regioni contenenti
“abbastanza” q-hit
• Esaminare più attentamente queste regioni
Q-Gram Filters for Finding All
-Matches
Sommario
• Motivazioni biologiche del problema
• Differenze tra algoritmo esatto,
euristiche e filtri
• Definizione del problema
• Formulazione semplificata
- alcuni esempi
- condizioni di filtraggio
- algoritmo proposto
• Formulazione completa
- condizioni di filtraggio
- algoritmo completo
- complessità
• Applicazioni e risultati sperimentali
Q-Gram Filters for Finding All
-Matches
Formulazione iniziale
Caso più semplice: |β|=n0
La struttura di base usata per risolvere
il problema è il “parallelogramma”,
associata all’uso della matrice di edit
Q-Gram Filters for Finding All
-Matches
Trovare i parallelogrammi
Esempio: date le stringhe GATCT e
ACGTC
B
Supponiamo
di ricercare
regioni
contenenti
2 q-hit
A
Q-Gram Filters for Finding All
-Matches
Trovare i parallelogrammi
Esempio: date le stringhe GATCT e
ACGTC
B
Supponiamo
di ricercare
regioni
contenenti
2 q-hit
A
Q-Gram Filters for Finding All
-Matches
Trovare i parallelogrammi
Esempio: date le stringhe GATCT e
ACGTC
B
Supponiamo
di ricercare
regioni
contenenti
2 q-hit
A
Q-Gram Filters for Finding All
-Matches
Trovare i parallelogrammi
Esempio: date le stringhe GATCT e
ACGTC
B
Supponiamo
di ricercare
regioni
contenenti
2 q-hit
A
Q-Gram Filters for Finding All
-Matches
Trovare i parallelogrammi
Esempio: date le stringhe GATCT e
ACGTC
B
Supponiamo
di ricercare
regioni
contenenti
2 q-hit
A
...
Q-Gram Filters for Finding All
-Matches
Trovare i parallelogrammi
Parallelogramma n0· e
n0 caratteri
Supponiamo
di ricercare
regioni
contenenti
2 q-hit
e+1 diagonali
Q-Gram Filters for Finding All
-Matches
Trovare i parallelogrammi
Esempio: date le stringhe GATCT e
ACGTC
B
Supponiamo
di ricercare
regioni
contenenti
2 q-hit
ATC
A
Q-Gram Filters for Finding All
A- C
-Matches
Trovare i parallelogrammi
Esempio: date le stringhe GATCT e
ACGTC
B
Supponiamo
di ricercare
regioni
contenenti
2 q-hit
A
e+1 diagonali
Q-Gram Filters for Finding All
-Matches
Trovare i parallelogrammi
Esempio: date le stringhe GATCT e
ACGTC
B
Supponiamo
di ricercare
regioni
contenenti
2 q-hit
ATCT
A
Q-Gram Filters for Finding All
ACGT
-Matches
Trovare i parallelogrammi
Esempio: date le stringhe GATCT e
ACGTC
Supponiamo
di ricercare
regioni
contenenti
2 q-hit
A
B
PB
PA
Q-Gram Filters for Finding All
-Matches
Lemma 1
Siano α e β sottostringhe di A e B tali che |β|=n0
e distδ(α,β) e
e = n0 
τ = f(n0,q,e) = (n0+1) – q(e+1)
Esiste un parallelogramma n0 · e tale che:
• contiene almeno τ q-hit
• β è la proiezione di B
• la proiezione di A è contenuta in α
Q-Gram Filters for Finding All
-Matches
Lemma 1 - Precisazioni
τ = f(n0,q,e) = (n0+1) – q(e+1)
e = n0 
Q-Gram Filters for Finding All
-Matches
Lemma 1 - Precisazioni
τ = f(n0,q,e) = (n0+1) – q(e+1)
e = n0 
Q-Gram Filters for Finding All
-Matches
Lemma 1 - Precisazioni
τ = f(n0,q,e) = (n0+1) – q(e+1)
e = n0 
Q-Gram Filters for Finding All
-Matches
Trovare i parallelogrammi
n0=8
e=2
q=2
τ=3
Q-Gram Filters for Finding All
-Matches
Trovare i parallelogrammi
β
PB
n0=8
α
e=2
PA
Q-Gram Filters for Finding All
q=2
τ=3
-Matches
Trovare i parallelogrammi
n0=8
e=2
q=3
τ=0
Q-Gram Filters for Finding All
-Matches
Passi dell’algoritmo (1)
Preprocessing: Indicizziamo la stringa A, in modo da
sapere le occorrenze di ogni q-gram (Morris-Pratt)
Q-Gram Filters for Finding All
-Matches
Passi dell’algoritmo (2)
• Si trovano tutti i q-hit
• Per ogni possibile parallelogramma
– Si contano quante occorrenze di q-hit vi sono
– Se tale numero supera la soglia τ  α e β
potrebbero costituire un -match
Q-Gram Filters for Finding All
-Matches
Sommario
• Motivazioni biologiche del problema
• Differenze tra algoritmo esatto,
euristiche e filtri
• Definizione del problema
• Formulazione semplificata
- alcuni esempi
- condizioni di filtraggio
- algoritmo proposto
• Formulazione completa
- condizioni di filtraggio
- algoritmo completo
- complessità
• Applicazioni e risultati sperimentali
Q-Gram Filters for Finding All
-Matches
Formulazione completa
In questo caso: |β|≥n0
• È necessaria una nuova funzione per il
calcolo di τ
• Parallelogramma w x e’ (di area maggiore
rispetto al precedente)
• β può non coincidere con pB
• pB può coincidere con B
• pA può coincidere con α
Q-Gram Filters for Finding All
-Matches
Formulazione completa -
U(1,
U(2,
U(3,
U(4,
U(5,
U(6,
U(7,
U(8,
2,
2,
2,
2,
2,
2,
2,
2,
0.25)
0.25)
0.25)
0.25)
0.25)
0.25)
0.25)
0.25)
…
=
=
=
=
=
=
=
=
Deriviamo
0
0
2
1
2
3
4
3
Q-Gram Filters for Finding All
-Matches
τ
Formulazione completa -
Deriviamo
τ
1
Per q    , U(i , q,) è strettamente crescente

Q-Gram Filters for Finding All
-Matches
Formulazione completa -
Deriviamo
È sufficiente calcolare la funzione in n0 e in n1
Per non perdere soluzioni, la scelta di τ deve essere
meno vincolante possibile (quella in cui sono richiesti
meno q-hit)
Q-Gram Filters for Finding All
-Matches
τ
Formulazione completa -
Deriviamo
  min U(n0 , q,),U(n1, q,)
Q-Gram Filters for Finding All
-Matches
τ
Dimensionamento del
parallelogramma - Calcolo di e
Un parallelogramma, per essere considerato
valido, deve contenere almeno τ q-hit
(distribuiti lungo più diagonali)
Q-Gram Filters for Finding All
-Matches
Dimensionamento del
parallelogramma - Calcolo di e
e deve essere sufficientemente grande, ma non
troppo (per non aumentare i falsi positivi)
Conoscendo il numero di q-hit richiesti (dato da U)
e il numero massimo di q-hit contenuti in una
diagonale (τ -1), si trova il numero di diagonali su
cui si distribuiscono i q-hit  U 


  -1 
Q-Gram Filters for Finding All
-Matches
Dimensionamento del
parallelogramma - Calcolo di e
Si stabilisce una relazione tra questo valore e il
numero di errori ammessi nel caso dello specifico
parallelogramma (di dimensioni n    n ),
ottenendo:


 2( -1)  (q -1) 
e

1


-q



Q-Gram Filters for Finding All
-Matches
Dimensionamento del
parallelogramma - Calcolo di w
Effettuando vari calcoli, si ottiene una formula
per trovare il valore dell’altra dimensione del
parallelogramma:
w  ( -1)  q(e  1)
Q-Gram Filters for Finding All
-Matches
Lemma 2
Sia β una sottostringa di B tale che |β|≥n0 che ha un -match
con una sottostringa α di A
1 
q

Siano U(n, q,)  (n  1) - q( n  1) ,
 ,
  min U(n0 , q,),U(n1, q,)
e
Esiste un parallelogramma w · e:
• contenente almeno τ q-hit
• le cui proiezioni intersecano α e β
• w  ( -1)  q(e  1)


 2( -1)  (q -1) 

• e
1


-q



Se |β|≤w allora PB contiene β; altrimenti è una sottostringa di β
Q-Gram Filters for Finding All
-Matches
Alcuni valori d’esempio
Parametri ottenuti con =0,05:
Aumentando τ aumentano anche n0, w ed e
Q-Gram Filters for Finding All
-Matches
Algoritmo completo
Preprocessing
Indicizziamo la stringa A, in modo da sapere tutte
le occorrenze di ogni possibile q-Gram
Iterazione
Troviamo tutti i possibili parallelogrammi w·e
Sfruttiamo il concetto di bin (insieme di (e+1)
diagonali adiacenti) e di sliding window
Un bin conta il numero di q-hit contenuti nel
parallelogramma definito dalle diagonali del bin
e dalle colonne della sliding window
Q-Gram Filters for Finding All
-Matches
Algoritmo completo (2)
B
A
Q-Gram Filters for Finding All
-Matches
Algoritmo completo (2)
B
A
e+Δ
Q-Gram Filters for Finding All
-Matches
Algoritmo completo (2)
B
A
τ q-hit non possono
essere dispersi in più
di e+1 diagonali
e+Δ
Q-Gram Filters for Finding All
-Matches
Algoritmo completo (2)
B
A
e+Δ
Q-Gram Filters for Finding All
-Matches
Algoritmo completo (2)
B
A
e+Δ
Q-Gram Filters for Finding All
-Matches
Algoritmo completo (2)
B
A
e+Δ
Q-Gram Filters for Finding All
-Matches
Algoritmo completo (2)
B
A
e+Δ
Q-Gram Filters for Finding All
-Matches
Algoritmo completo (2)
B
A
Q-Gram Filters for Finding All
-Matches
Algoritmo completo (3)
Ottimizzazioni in tempo:
• non si possono avere τ q-hit in una stringa più
corta di q+τ-1
– si rilassa il problema, considerando i parallelogrammi w’· e, con
w’≥ q+τ-1
• due q-hit distanti più di w-q posizioni (in B) non
possono stare nello stesso parallelogramma
– per ogni bin, si usano gli indici min e max per indicare
rispettivamente il minimo e il massimo indice j (riferito a B) dei
q-hit trovati
– si termina nel momento in cui si trova un q-hit tale per cui jw+q >max
Q-Gram Filters for Finding All
-Matches
Algoritmo completo -
Precisazioni
In seguito a queste ottimizzazioni,
l’algoritmo può perdere accuratezza (si
creano un maggior numero di falsi
positivi). Questo non comporta
conseguenze solamente negative perché
anche questi casi possono essere
interessanti da un punto di vista
biologico
(Può capitare in casi particolari, in cui i q-hit si
trovano esattamente ogni w-q+1 posizioni in B)
Q-Gram Filters for Finding All
-Matches
Complessità in tempo
Preprocessing:
Lunghezza liste (pessimo): |A|
Lunghezza liste (medio):
Q-Gram Filters for Finding All
-Matches
Complessità in tempo
Preprocessing:
Lunghezza liste (pessimo): |A|
Lunghezza liste (medio):
Complessità (pessimo): O(|A|·|B|)
Complessità (medio): O(|B|  | A ||B||  |-q)
Q-Gram Filters for Finding All
-Matches
Complessità in spazio
Totale occorrenze: |A|
Numero massimo di entrate:
Dimensione tabella occorrenze:
Q-Gram Filters for Finding All
-Matches
Complessità in spazio
Totale occorrenze: |A|
Numero massimo di entrate:
Dimensione tabella occorrenze:
Parallelogrammi: w·(e+Δ)
Δ>0
Ogni bin è associato a: e+Δ diagonali
I bin si sovrappongono su e diagonali
Q-Gram Filters for Finding All
-Matches
Complessità in spazio
Totale occorrenze: |A|
Numero massimo di entrate:
Dimensione tabella occorrenze:
Parallelogrammi: w·(e+Δ)
Δ>0
Ogni bin è associato a: e+Δ diagonali
I bin si sovrappongono su e diagonali
Bin richiesti:
Di solito: Δ = 2z, 2z>e, z 
Q-Gram Filters for Finding All
-Matches
Complessità in spazio
Totale occorrenze: |A|
Numero massimo di entrate:
Dimensione tabella occorrenze:
Parallelogrammi: w·(e+Δ)
Δ>0
Ogni bin è associato a: e+Δ diagonali
I bin si sovrappongono su e diagonali
Bin richiesti:
Di solito: Δ = 2z, 2z>e, z 
Q-Gram Filters for Finding All
-Matches
Complessità in spazio
Bin e parallelogrammi: 3 interi
Totale bin:
Totale parallelogrammi: 3p
Q-Gram Filters for Finding All
-Matches
Complessità in spazio
Bin e parallelogrammi: 3 interi
Totale bin:
Totale parallelogrammi: 3p
Complessità:
Tabella occorrenze + bin + parallelogrammi
3p
Q-Gram Filters for Finding All
-Matches
Complessità in spazio
Bin e parallelogrammi: 3 interi
Totale bin:
Totale parallelogrammi: 3p
Complessità:
Tabella occorrenze + bin + parallelogrammi
3p
Q-Gram Filters for Finding All
-Matches
Sommario
• Motivazioni biologiche del problema
• Differenze tra algoritmo esatto,
euristiche e filtri
• Definizione del problema
• Formulazione semplificata
- alcuni esempi
- condizioni di filtraggio
- algoritmo proposto
• Formulazione completa
- condizioni di filtraggio
- algoritmo completo
- complessità
• Applicazioni e risultati sperimentali
Q-Gram Filters for Finding All
-Matches
Applicazioni
I filtri trovano maggior utilizzo negli
allineamenti di sequenze di DNA che
non in quelle di aminoacidi
Alcuni esempi:
• Sequence assembly
• EST clustering
Q-Gram Filters for Finding All
-Matches
Applicazioni – Sequence assembly
Nel contesto biologico del sequence assembly, il filtro
è usato per costruire l'overlapper dei frammenti
Si costruisce una stringa A concatenando i frammenti
Il filtro viene applicato ad A su se stessa, ignorando
gli hit sulla diagonale della matrice di edit e sotto di
essa
Q-Gram Filters for Finding All
-Matches
Risultati sperimentali - Sequence assembly
Si possono allineare sequenze di 60 Mbp (n0=50,
=5%) in 90 secondi (Apple PowerBook G4, 1Gb di
memoria)
Problemi di 1,8 Gbp (D. melanogaster) sono risolti in
18 ore
Utilizzando un Intel Itanium II con 16 Gb di memoria
il problema può essere risolto in meno di 2 ore
Q-Gram Filters for Finding All
-Matches
Applicazioni – EST clustering
Si utilizza il filtro adottando l’idea di BLAST
Si trovano i seed
Q-Gram Filters for Finding All
-Matches
Applicazioni – EST clustering
Si utilizza il filtro adottando l’idea di BLAST
Si trovano i seed
I seed vengono estesi
Q-Gram Filters for Finding All
-Matches
Risultati sperimentali
– EST Clustering
Si confrontano i risultati ottenuti con:
• SSEARCH (implementazione di Smith-Waterman)
• BLAST
• SWIFT (un algoritmo basato sul filtro)
Q-Gram Filters for Finding All
-Matches
Risultati sperimentali – EST Clustering (2)
Sono selezionate casualmente 40.000 sequenze dal
DNA dell’H. sapiens (25Mbp) e 5.600 sequenze dal
DNA del M. musculus (2Mbp)
La lunghezza dei q-gram è 11
Lo score minimo richiesto è 16
SSEARCH è stato eseguito su un cluster di 50 UltraSparcIIe a 500 MHz
BLAST e SWIFT sono stati eseguiti su un AMD Athlon-XP a 2 Ghz
Q-Gram Filters for Finding All
-Matches
Risultati sperimentali – EST Clustering (3)
Confrontiamo i risultati ottenuti variando  ed
n0 in SWIFT
Q-Gram Filters for Finding All
-Matches
Risultati sperimentali – EST Clustering (3)
Filtration Ratio: rapporto tra area totale dei
parallelogrammi restituiti e dimensione totale
della matrice di edit
Q-Gram Filters for Finding All
-Matches
Bibliografia
•
•
•
•
•
•
•
•
•
•
Comincioli, V. Biomatematica: interazioni tra le scienze della vita e la matematica. APOGEO
(2005), par. 2.2.
Setubal, J., Meidanis, J. Introduction To Computational Molecular Biology. PSW (1997), cap 3
Clote, P., Backofen, R. Computational Molecular Biology An Introduction. WILEY (2000), par
3.1, 3.6
Lesk, Introduzione alla bioinformatica. McGraw-Hill
Myers, E., Rasmussen, K.R., Stoye, J., Efficient q-Gram Filters for Finding All Eps-Matches over
a Given Length. J. Comp. Biol. (2006) 13(2). Pp 296-308 e relative slides
Wikipedia
Pop, M., Salzberg, S.L., Shumway, M., Genome Sequence Assembly: Algorithms and Issues.
IEEE (2002). Pp 47-54
Genome sequence assembly primer
http://www.cbcb.umd.edu/research/assembly_primer.shtml
Cerutti, L., EST clustering (2003)
www.ch.embnet.org/CoursEMBnet/Pages02/slides/est_clustering.pdf
Combinatorial Pattern Matching
http://www.dia.unisa.it/~ads/BIOINFORMATICA/CombinatorialPatternMatching/index.htm
Q-Gram Filters for Finding All
-Matches