1 Introduzione

Chiunque abbia mai usato programmi di elaborazione testi ha dovuto affrontare il problema di ricercare una stringa all’interno del testo. Forse senza saperlo, ci si è imbattuti nel problema del pattern matching.

Contrariamente a quanto si può pensare l’applicazione dei metodi di pattern matching non è limitata all’elaborazione dei testi, ma è ampiamente utilizzata nella biologia computazionale, il cui tema centrale è la ricerca di sequenze molecolari all’interno di sequenze più lunghe, un’operazione fondamentale per problemi quali:

· ricostruire una sequenza di DNA dai singoli pezzi ottenuti da esperimenti;

· ricercare delle specifiche caratteristiche nelle sequenze di DNA;

· determinare quanto sono differenti due sequenze di codice genetico

L’obbiettivo di questo documento è definire il problema del pattern matching e proporre soluzioni adeguate. Tutto ciò dopo una breve infarinatura sul significato biologico di alcuni termini utilizzati nel documento stesso.

Al fine di seguire un percorso strutturato, il documento è suddiviso nelle seguenti cinque sezioni:

· Nozioni biologiche: in questa parte del documento sono accennati termini strettamente legati alla biologia, che aiuteranno il lettore alla comprensione dell’argomento trattato;

· Definizione del problema: in questa sezione definiamo una formalizzazione del problema del pattern matching e di alcune sue varianti (pattern matching multiplo e approssimato), introducendo una serie di definizioni utili;

· Soluzioni al pattern matching (esatto): è la sezione dove sono presentate alcune possibili soluzioni al problema del pattern matching, analizzandone il grado di efficienza. Le soluzioni sono inoltre confrontate tra loro, al fine di definire vantaggi e svantaggi;

· Soluzioni al pattern matching multiplo: in questa parte è mostrata una variante del problema trattato, presentando, anche in questo caso, alcune possibili soluzioni. La prima con approccio naive, ed altre due realizzate rispettivamente su Keyword Tree e Suffix Tree.

· Soluzioni al pattern matching approssimato: in questa seziona vengono proposte due diverse soluzioni, la prima con approccio naive, la seconda basata sull’utilizzo delle matrici di punti. Continuando, viene presentato il Query Matching Problem, una generalizzazione del problema Pattern Matching e una sua possibile soluzione basata sull'idea di filtraggio.

· Appendice: sono sviluppati due argomenti di interesse del lettore non strettamente legati a quello che è lo scopo di questo documento: Hashing, un argomento che interessa il sistema del filtraggio citato al punto precedente, e l’algoritmo di Aho-Corasick., utilizzato per la generazione dei Suffix Tree adottati, a loro volta, per la risoluzione del problema del pattern matching multiplo.

2 Nozioni biologiche

Prima di addentrarci nel problema concreto del pattern matching è bene definire alcune utili nozioni di biologia.

Come accennato nell’introduzione il pattern matching trova la sua maggiore applicazione nella ricerca e nella ricostruzione del genoma umano, cioè il DNA. Una sequenza di DNA è un lungo polimero di unità più piccole unite tra loro attraverso legami fosfo-diesterici: i nucleotidi.

I nucleotidi sono molecole organiche semplici costituite da uno zucchero, un gruppo fosfato, ed una base azotata, che è una tra le seguenti quattro:

· adenina(A);

· citosina (C);

· guanina (G) ;

· timina (T).

I nucleotidi si associano fra loro formando grandi polimeri; la ripetizione di queste associazioni genera polimeri lineari.

In una molecola di DNA si trovano accoppiate due stringhe anti-parallele le cui sequenze di nucleotidi sono complementari (C-G, A-T).

Le due stringhe generano una doppia elica di (approssimativamente) 10 coppie di nucleotidi per

ogni volta dell’elica.

L’informazione biologica contenuta nel gene deve essere copiata esattamente e trasmessa da ogni

cellula a tutte le sue cellule figlie. La struttura a doppia elica del DNA suggerisce come il trasferimento dell’informazione viene effettuato. Poiché ogni sequenza (stringa, fibra, filo) di DNA contiene una successione di nucleotidi esattamente complementare alla successione dell’altra sequenza, entrambe le sequenze di DNA contengo la medesima informazione genetica. Quindi, dopo la separazione delle due sequenze, ciascuna può costituire un modello per produrre una nuova sequenza di DNA. Nella figura a sinistra è riportato un esempio di ripetizione di nucleotidi.

3 Definizione del problema

Il pattern matching consiste nell’individuare l’occorrenza di una certa sequenza, detta pattern, all’interno di una sequenza più lunga, denominata testo.

Si assuma di avere un testo, visto come array di caratteri T[1..n] e un pattern, visto come array di caratteri P[1..m], con m £ n, dove m è la lunghezza del pattern P e n la lunghezza del testo T.

I caratteri di P e T appartengono ad un certo alfabeto S, cioè un insieme finito di elementi detti caratteri.

Il nostro obiettivo è quello di trovare tutte le occorrenze (espresse in posizioni) di P nel testo T.

Si osservi che una posizione in cui il pattern P occorre nel testo T corrisponde al numero di spostamenti validi necessari affiche P coincida con una sottosequenza di T.

Esempio:

Il pattern appare solo una volta nel testo, con spostamento valido s = 4.

3.1 Il problema specifico

Dopo aver dato una definizione generale del problema, possiamo ora estenderlo al campo della biologia computazionale.

Una fondamentale assunzione in biologia molecolare è che il DNA può essere visto come una sequenza mono-dimensionale costruita su un alfabeto di 4 simboli {A,C,G,T}, astraendo dalla reale natura del DNA quale molecola tridimensionale.

Notazioni utili

Come notazione per la rappresentazione di sequenze di DNA sono usati i doppi apici per la delimitazione della sequenza stessa mentre i caratteri che la compongono non sono separati in alcun modo. Esempio: “ACTAGCT”.

Inoltre, per indicare un determinato carattere di una sequenza vengono utilizzate le parentesi quadre che racchiudono il numero, o la variabile numerica, che rappresenta la posizione del carattere a partire da sinistra, come nel seguente esempio:

Dato il testo T = “ACTAGCT”, per indicare la prima “G” che compare in T si utilizza: T[5], oppure T[i] con i = 5.

Le parentesi quadre sono quindi utilizzate sia nel modo appena descritto, sia nel modo utilizzato in precedenza, ovvero per l’identificazione di una determinata sottosequenza di una data sequenza, come ad esempio:

Dato il testo T = “ACTAGCT”, per indicare la sottosequenza “TAGC” che compare in T si utilizza: T[3 .. 6], oppure T[i .. j] con i = 3 e j = 6.

Esempio:

Il pattern appare solo una volta nel testo, con spostamento valido s = 3.

Ad ogni nuovo spostamento devono essere confrontati i caratteri del pattern P con i caratteri del testo T[s+1.. s+m], se un carattere di P, P[q] è diverso da T[s+1+q],con q compreso tra 1 ed m, allora si è verificato un mismatch. Questo implica che dovrà essere effettuato un nuovo spostamento.

Il termine “mismatch” è utilizzato nel modo seguente: si dice che si è verificato un mismatch tra testo T e il pattern P per un determinato spostamento di P, se uno o più caratteri di P sono diversi dai corrispondenti caratteri di T.

3.2 Pattern matching multiplo

Il pattern matching può essere esteso alla ricerca simultanea di tutte le occorrenze di un dato insieme di pattern S = {P₁, ..., P_r} , con r il numero di pattern contenuti nell’insieme S, in un testo T , dove P_i è una sequenza di caratteri lunga m_i; con m_i £ n . Denotiamo con |S| la somma delle lunghezze di tutti i pattern.

Esempio:

L’insieme S è composto da due pattern: P₁ e P₂ rispettivamente di dimensione m₁ e m₂

Il pattern P₁ appare una volta sola dopo s₁ = 3 spostamenti validi, mentre il pattern P₂ appare anch’esso un’unica volta dopo s₂ = 4 spostamenti validi;

Da notare che, in questo caso, ogni occorrenza del primo pattern implica un’occorrenza del secondo, quindi l'algoritmo utilizzato dovrebbe in qualche modo rendere efficiente la ricerca riconoscendo la situazione di similarità verificatasi.

3.3 Pattern matching approssimato

Il pattern matching approssimato entra in gioco quando si vuole far corrispondere ad un pattern, in un testo, una corrispondenza approssimata. In tale operazione sono permesse al massimo k non corrispondenze.

La ricerca approssimata, nella sua forma più generale, consiste nell’identificare le posizioni del testo T in cui si trovano occorrenze del pattern P permettendo un numero limitato di “errori” nei confronti.

Richiamiamo le definizioni già viste per il problema del pattern matching esatto:

· S è l’alfabeto dei simboli su cui sono costruiti testo e pattern;

· T[1 . .n] è il testo (un array di simboli di S) su cui effettuiamo la ricerca;

· P[1 . .m] è il pattern (un array di simboli di S) ricercato nel testo.

Formalmente, oltre alle definizioni introdotte per la ricerca esatta, è necessario introdurre la seguente notazione:

• k ÎÀ è il numero massimo di errori permessi;
• s1 e s2 sono due parole costruite su S;
• d(s1, s2) è la funzione di distanza che prende valore in Â.

Quindi il problema della ricerca approssimata consiste nel determinare l’insieme delle posizioni j del testo T tali che, per qualche:

i ≤ j, d(T[i]…T[j], P) ≤ k

(insieme delle posizioni in cui si trova un’occorrenza di P con al più k errori)

Definizione della funzione distanza

Esistono vari modi per definire la funzione; in questo lavoro definiamo la distanza d(x, y) fra due stringhe x ed y come il costo minimo di una sequenza di operazioni atte a trasformare la stringa x nella stringa y.

Il costo di una sequenza di operazioni è dato dalla somma dei costi delle singole operazioni.

Le operazioni sono un insieme finito di regole esprimibili nella forma d(z, w) = t, ove

• z e w sono due diverse stringhe;
• t un numero reale non negativo;

Una volta che la stringa z è stata convertita nella stringa w nessun altra operazione può essere eseguita su z.

Si noti come quest’ultima condizione impedisca di agire più volte sulla stessa stringa. Eliminare tale restrizione dalla definizione di distanza significherebbe permettere un livello di elaborazione della stringa tale da renderne impossibile il calcolo della distanza. Si noti inoltre come la distanza in tal modo descritta definisca a sua volta una metrica, infatti, se per ogni operazione d(z, w) esiste la rispettiva operazione d (w, z) di ugual costo, allora la distanza è simmetrica (es: d(x, y) = d(y, x)), inoltre date le stringhe x, y, z con d(x, y) ³ 0

• d(x, x) = 0
• d(x, z) £ d(x, y) + d(y, z)

Generalmente, nel maggior numero delle applicazioni, le possibili operazioni utilizzate al fine di valutare la distanza fra stringhe risultano essere:

• Inserimento
• Cancellazione
• Sostituzione
• Trasposizione

4 Soluzioni al pattern matching esatto

In questa parte del documento introdurremo le soluzioni al pattern matching singolo che ricercano con esattezza un pattern P all’interno di un testo T.

Come per ogni problema computazionale esiste sempre una soluzione naive, che trova prima o poi la soluzione corretta. Naturalmente tale soluzione risulta estremamente inefficiente, e questa inefficienza cresce con la lunghezza del testo T considerato.

Proprio per questo motivo vengono descritte due soluzioni molto più efficienti della soluzione naive poiché entrambe si basano sulla ricerca di alcune informazioni ottenute durante i confronti eseguiti, con la possibilità di eseguire spostamenti validi maggiori di una posizione.

4.1 Algoritmo naive

La prima soluzione al problema si basa sull’utilizzo di un algoritmo banale, di cui non sono note le origini. Questo algoritmo prova tutti i possibili spostamenti finché non trova quello valido.

In input prende un testo T di dimensione n e un pattern P di dimensione m. Restituisce in output lo spostamento valido, ovvero la posizione della prima occorrenza di P in T se P è compreso in T, nulla se P non è compreso in T.

L’algoritmo restituisce I, l’insieme degli spostamenti validi del pattern P nel testo T.

L’algoritmo naive per prima cosa allinea il primo carattere di P con il primo carattere di T.

Successivamente confronta, da sinistra verso destra, i caratteri corrispondenti di P e T fino a quando non trova un mismatch o raggiunge la fine di P.

Se viene raggiunta la fine di P, l’algoritmo aggiunge la posizione del carattere di T che corrisponde al primo carattere di P all’insieme I.

Invece se trova un mismatch sposta P di un posto a destra, però se l’ultimo carattere di P va oltre la fine di T, l’algoritmo termina l’esecuzione.

L’ algoritmo naive risulta inefficiente poiché nelle sequenze di DNA, i valori tipici di m sono dell’ ordine delle centinaia di caratteri, per cui il costo di questo algoritmo risulta essere molto eccessivo. Infatti nel caso pessimo l’ algoritmo richiede O(m*n) .

4.2 Algoritmo di Knuth-Morris-Pratt (KMP)

Introduzione

Nel 1976 Knuth, Morris e Pratt pubblicarono il loro algoritmo differente da quello basato su approccio naive. L’algoritmo studia i legami di somiglianza tra il pattern P e il testo T tenendo traccia dell’informazione ricevuta dai precedenti confronti.

Questi tre studiosi hanno pensato bene che per avere un algoritmo di ricerca più veloce occorre separare il procedimento di ricerca in due fasi:

· Preprocessing: elaborazione preliminare del pattern con la quale si ricavano informazioni che verranno usate nella seconda fase;

· Scanning: scansione veloce del testo.

Preprocessing

Il preprocessing in KMP è la funzione prefisso che dà informazioni di come il pattern compare all’interno di se stesso. Questa informazione è molto importante in quanto permette di evitare di controllare spostamenti sicuramente non validi.

Infatti come si può notare dall’esempio dato che i caratteri P[1 .. q] combaciano con i caratteri del testo T[s+1 .. s+q], dove q rappresenta quindi il numero di caratteri del pattern coincidenti nel testo a partire da s. Possiamo evitare di controllare gli spostamenti s+1, s+2 in quanto sono sicuramente spostamenti non validi.

T

Con k tale che P[1 .. k] e suffisso di P[1 .. q].

Il preprocessing richiesto si formalizza nel seguente modo: Dato un pattern P[1.. m], la funzione prefisso per il pattern P è la funzione

P:{1,..,m}è {0,..,m-1} t.c. P [q]= max{k:k<q e P[1 .. k] è suffisso di P[1.. q] }.

Cioè, P [q] è la lunghezza del prefisso più lungo di P che è anche un suffisso di P[1 .. q]

L’algoritmo in pseudocodice seguente computa la funzione prefisso sopra descritta.

L’algoritmo per prima cosa pone a zero il primo elemento dell’array P, per definizione, anche se la sequenza P[1.. q] (cioè P[1..1]) è costituita da un solo carattere e di conseguenza l’unico prefisso coincide con l’unico suffisso. Successivamente si considerano la sequenza di caratteri P[1..i] e per ognuna di queste si considera se c’è un prefisso che corrisponde ad un suffisso in P[1..i].

Nel caso in cui si trovi tale corrispondenza, l’elemento dell’array P nella posizione i viene impostato con la lunghezza del prefisso trovato.

Il tempo di esecuzione della funzione prefisso nel caso pessimo è O(m).

Esempio di funzione prefisso P per il pattern P = “GACGAGAGAAGCGAT”, j indica la posizione del carattere nell’array P e P.

Ad esempio nella sequenza P[1.. 5] = “GACGA” il prefisso P[1.. 2] coincide con il suffisso P[4 .. 5].

Scanning

La fase di scanning, la scansione veloce del testo è schematizzata nel seguente algoritmo. Da notare l’utilizzo della funzione prefisso precalcolata.

L’algoritmo restituisce I, l’insieme degli spostamenti validi del pattern P nel testo T.

Esaminiamo ora l’algoritmo di KMP che rappresenta una evoluzione in quanto a differenza del naive non ignora le informazioni relative al pattern P.

- per prima cosa l’algoritmo calcola la funzione prefisso sul pattern P ed otteniamo P

- il ciclo for itera fin quando non trova un carattere del testo T, T[j] che coincide con il primo carattere di P, P[0]. A questo punto controlla i successivi caratteri del pattern P che coincidono con i successivi caratteri del testo T fin quando non trova un non corrispondenza tra T[j] e P[q+1]. Se per il carattere del pattern P[q+1],

§ l’array P restituisce un valore q = 0, la ricerca del pattern P inizia dal primo carattere di P

§ l’array P restituisce un valore q > 0, la ricerca del pattern P inizia da P[q+1] questo significa che q caratteri precedenti nel testo T a partire dal T[j] trovano corrispondenza con i primi q caratteri di P.

Non considerando la funzione prefisso l’algoritmo KMP impiega tempo O(n). Quindi il tempo di esecuzione dell’algoritmo di Knuth-Morris-Pratt è O(n+m) .

Esempio completo

Vogliamo trovare il pattern P = “AGACAC” nel testo T = “AGACAACATCAGACACAA”.

Prima vengono computati gli elementi dell’array P:

Poi dopo aver inizializzato q a zero, inizia il ciclo for (riga 5):

a) Ciclo n°1: q = 0 e j = 1;

- il ciclo while non viene eseguito;

- il carattere P[q+1] è uguale al carattere T[j], quindi si passa alla seconda iterazione.

…

Ciclo n°6: q = 5 e j = 6;

- il ciclo while viene eseguito, ciò significa che si è verificato un mismatch, quindi q = P[q] cioè q = 1

b) Ciclo n°6: q = 1 e j = 6;

- il ciclo while viene seguito nuovamente ma P[q+1] = P[2] = “G” <> “A”= T[6], quindi q = P[q] = P[1] = 0, ciò significa saltare il ciclo while.

c) Ciclo n°6: q = 0 e j = 6;

- dopo aver saltato il ciclo while viene controllato P[q+1] = T[j], il controllo è positivo quindi q = 1;

- viene incrementato j = 7, e viene controllato P[2] = P[q+1]= ”G” <> “C” = T[7], si verifica un mismatch si entra nel ciclo while e q = P[q] = P[1] = 0, poiché q = 0 il ciclo while non sarà più eseguito;

d) Ciclo n°7: q = 0 e j = 7;

- dopo aver saltato il ciclo while viene controllato P[q+1] = T[j], il controllo è negativo, si passa al prossimo ciclo for, quindi j = 8.

e) Ciclo n°8: q = 0 e j = 8;

- viene controllato se P[q+1] = T[j], il controllo è positivo, quindi q = 1 e j = 9;

- quindi si passa al prossimo ciclo for e viene controllato P[q+1] = P[2] =”G” <> ”T”= T[9] = T[j], il controllo è negativo e q > 0 quindi il ciclo while viene eseguito e q = P[q] = P[1] = 0;

- di conseguenza il successivo ciclo while non viene eseguito.

f) Ciclo n°9: q = 0 e j = 9;

- dopo aver saltato il ciclo while viene controllato P[q+1] = T[j], il controllo è negativo quindi si passa al successivo ciclo for.

g) Ciclo n°10: q = 0 e j = 10;

- viene controllato se P[q+1]=P[1] <> T[10] = T[j], il controllo è positivo ma q = 0 quindi il ciclo while non viene nemmeno una volta;

- si controlla successivamente se P[q+1]=P[1] = T[10] = T[j], ma anche questo controllo è negativo, quindi si passa al successivo ciclo for.

f) Ciclo n°11: q = 0 e j = 11;

- il ciclo while viene saltato, mentre il controllo P[q+1]=P[1] = T[11] = T[j] ha successo, quindi q = 1 e si passa al successivo ciclo for;

- in effetti ora tutti i controlli saranno positivi, fino ad arrivare al 16° ciclo in cui avremo che q = m = 6 è il pattern P è stato trovato nel testo T;

- viene restituito j – m = “da dove inizia il pattern P in T”;

- l’algoritmo continuerà la sua esecuzione alla ricerca di P in T, senza successo.

4.3 Algoritmo di Boyer-Moore

Introduzione

Gli algoritmi presentati finora hanno tutti la caratteristica comune di esaminare, come minimo, tutti i caratteri del testo nel caso pessimo. A tal proposito, un risultato di Rivest afferma che gli algoritmi di pattern matching che usano confronti devono esaminare almeno n-m+1 caratteri nel caso pessimo!

Nulla vieta però che si possa migliorare la situazione nel caso medio. Infatti in contemporanea a KMP, Boyer e Moore nel 1997 idearono il loro algoritmo che per ogni porzione di m caratteri del testo T ne confronta solo O(log n) in media, dove n è la lunghezza del testo T ed m è la lunghezza del pattern P.

Il dr. Robert Boyer ha ricevuto l’Herbrand Award per “Distinguished Contributions to Automated Reasoning”; attualmente professore di Informatica alla “University of Texas” di Austin.

Il dr. J. Strother Moore III ha ricevuto l’Herbrand Award per “Distinguished Contributions to Automated Reasoning” alla “International Conference on Automated Deduction”; attualmente professore alla “University of Texas” di Austin.

Tutt’oggi tale algoritmo è chiamato Boyer-Moore, sebbene anche R. W. Gosper, indipendentemente dagli altri due, giunse a sviluppare lo stesso algoritmo.

Le idee principali su cui si basa l’algoritmo sono:

· metodo di confronto a ritroso: i confronti vengono effettuati da destra a sinistra, partendo dalla fine del pattern. Il vantaggio di questa scelta è che in caso di mismatch, come nell’esempio, possiamo spostare il pattern P di m posizioni, ovvero di un numero di posizioni pari alla lunghezza del pattern;

· spostamento deciso tramite l’euristica: il cardine della computazione è dato dal calcolo veloce dello spostamento del pattern P, che avviene prendendo il massimo degli spostamenti suggeriti da due funzioni:

o L’euristica del carattere discordante;

o L’euristica del buon suffisso.

Come è ben evidente nell’immagine, il carattere T[4] = “T” non è presente nel pattern P, di conseguenza il pattern P può essere spostato di m, cioè 5, posizioni in avanti, senza saltare spostamenti validi.

Euristica del carattere discordante

L’euristica del carattere discordante funziona nel seguente modo:

Supponiamo che siamo in presenza di un mismatch, per cui T[s+j] <> P[j], con T[s .. s+j–1] = P[1 .. j–1], dove s è lo spostamento corrente del pattern P in T e j è, appunto, la posizione rispetto a P del carattere discordante.

L’euristica del carattere discordante ci dice di trovare la prima occorrenza del carattere discordante del testo T in P.

Formalmente: sia k l’indice più grande in P tale che T[s .. s+k] = P[1 .. k], abbiamo le seguenti possibilità:

• k = 0 è il carattere discordante di T non appare in P per cui possiamo spostarci di j posizioni senza saltare spostamenti validi;

• k < j è il carattere discordante di T è presente in P e si trova a sinistra della posizione j, per cui j – k > 0 (spostamento valido positivo,verso destra), quindi possiamo incrementare s di j-k posizioni senza saltare spostamenti validi;

• k > j è il carattere discordante di T è presente in P e si trova a destra della posizione j, per cui j – k < 0 (spostamento negativo,verso sinistra), quindi viene ignorato poiché sicuramente l’euristica del buon suffisso suggerirà uno spostamento valido positivo.

Dato un pattern P, si trova la funzione carattere discordante λ:

λ: {σ₁, σ₂, .., σ_|Σ|} è {0, 1, .., m}

λ[σ_i] = max{k: 1 ≤ k < m e P[k] = σ_i} se σ_i è presente nel pattern P,

λ[σ_i] = 0 altrimenti.

Nota: σ_i è l’i-esimo simbolo dell’alfabeto Σ.

In pratica questa funzione assegna ad ogni lettera dell’alfabeto un valore intero compreso tra 0 ed m, ora se l’i-esimo carattere dell’alfabeto è presente nel pattern P, la funzione restituisce la posizione dell’ultima occorrenza del carattere i-esimo in P, altrimenti restituisce 0.

CASO1: il carattere discordante non appare nel pattern P.

Lo spostamento è tale da allineare il primo carattere di P con il carattere di T successivo al carattere discordante, in pratica si ha uno spostamento pari alla lunghezza del pattern.

CASO2: il massimo indice k, tale per cui P[k] è uguale al carattere discordante, è minore dell’indice j che corrisponde al carattere di P allineato con il carattere discordante.

Lo spostamento é tale da allineare P[k] con il carattere discordante

CASO3: il massimo indice k, tale per cui P[k] è uguale al carattere discordante, è maggiore dell’indice j che corrisponde al carattere di P allineato con il carattere discordante.

Si può solo effettuare lo spostamento di un carattere a destra.

Euristica del buon suffisso

Se ci troviamo in caso di mismatch, l’euristica del buon suffisso dice che possiamo, con successo, incrementare s di:

g[j] = m – max{k: 0 ≤ k < m e P[j+1 .. m] ~ P[1 .. k] con P[k] <> P[j]}

La funzione restituisce un valore che rappresenta la quantità minima di cui s può avanzare senza far si che alcun carattere nel “buon suffisso” T[s+j+1 .. s+m] sia discorde dal nuovo allineamento del pattern, dove j, come indicato in precedenza, è la posizione rispetto a P del carattere discordante.

Nota: il simbolo ~ si legge “simile” e significa che:

P[j+1 .. m] P[1 .. k] oppure P[1 .. k] P[j+1 .. m]

Significa che P[j+1 .. m] o è un suffisso di P[1 .. k] oppure P[1 .. k] è un suffisso di P[j+1 .. m].

Dato che il suffisso P[j+1 .. m] coincide con la sottosequenza T[s+j+1 .. s+m], la funzione del buon suffisso trova il minimo spostamento s’ – s tale che:

P[k+1 .. k+m–j] = T[s+j+1 .. s+m] con s’+k = s+j e P[k] <> P[ j ]

Si noti che il confronto dei caratteri di P da k a k+m–j è superfluo.

Qui di seguito viene riportato lo pseudocodice relativo alla funzione del buon suffisso.

L’algoritmo restituisce l’array γ che contiene i valori calcolati dalla funzione g.

Per prima cosa l’algoritmo utilizza al suo interno la funzione prefisso (descritta in KMP), sul pattern P e sull’inverso del pattern P, cioè P’. Il primo ciclo inizializza l’array γ con la differenza tra la lunghezza del pattern P e il valore restituito dalla funzione prefisso per P[1…m].

• Ora se P ’[m] = q = 0 è per j=1...m si ipotizza l’inesistenza di un prefisso di P, che coincida con P[j+1…m], cioè supponiamo che non ci siano sottosequenze che si ripetano nel pattern P, ciò comporterebbe che ogni qual volta si verifichi un mismatch, avremo uno spostamento valido s pari a m, quindi γ[j] = m.
• Invece se P ’[m] = q <> 0 (dove 0 < q < m) è indica che esiste il suffisso di lunghezza q che coincide col prefisso di lunghezza q, quindi per j=1...m γ[j]= m – q.

Poi successivamente per ogni j = 1 .. m , si considera la sottosequenza P[j+1 .. m] e si controlla se tale sottosequenza compare nuovamente in P[0 .. j], se il controllo ha esito positivo sarà memorizzato in γ[j] la posizione da dove inizia la ripetizione di P[j+1 .. m], altrimenti γ[j] = m – q.

CASO1: k non esisteè si sposta P fino a far coincidere un suo prefisso v 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]

CASO2: k esiste è si sposta P 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. Questo significa che è presente un altro segmento T[s+j+1 .. s+m] in P, ovvero P[k+1 .. k+m-j], ma con P[k] diverso da P[j].

Come è ben evidente nell’esempio, è stata trovata una sottostringa P[k+1…k+m-j] uguale a T[s+j+1…s+m] con P[k] cioè “A” diverso da P[j] cioè “G”.

Qui di seguito è riportato l’algoritmo completo di Boyer-Moore.

Come KMP anche questo algoritmo precalcola le due funzioni cioè quella del carattere discordante e quella del buon suffisso. Poi l’algoritmo prosegue effettuando i confronti tra il pattern P ed il testo T. Nel caso in cui si verifichi un mismacth, lo spostamento del pattern è dato dal valore restituito da una delle due funzioni, ovviamente sarà preso quello più grande.

L’algoritmo restituisce I, l’insieme degli spostamenti validi del pattern P nel testo T.

La complessità in tempo di Boyer-Moore è O(n*m) in quanto, la complessità della fase di ricerca è O(n–m+1), COMPUTE-LAST-OCCURRENCE-FUNCTION richiede tempo O(m+|S|), mentre COPUTE-GOOD-SUFFIX-FUNCTION richiede tempo O(m).

L’algoritmo di Boyer-Moore funziona “bene” se il pattern P è relativamente lungo e se l’alfabeto |Σ| è ragionevolmente grande

Esempio completo

Vogliamo trovare il pattern P = “AGACAC” nel testo T = “AGACAACATCAGACACAA”.

Prima vengono precalcolati i due array:

Ecco un esempio dove possiamo vedere come opera l’algoritmo di Boyer-Moore.

Nel punto

a) abbiamo subito un mismatch per cui vediamo se il carattere del testo T che ha provocato il mismatch è presente nel pattern, se si prendiamo il carattere più a destra.

b) abbiamo un match “AC” ed un mismatch nel 4° confronto (“A” <> “C”) a questo punto entra in gioco l’euristica del buon suffisso, poiché l’euristica del carattere discordante mi indicherebbe di tornare indietro. L’euristica del buon suffisso invece mi indica che all’interno del pattern c’è un ‘altra occorrenza della sottostringa “AC” preceduta da un carattere diverso “C” (“C” <> “G”).

c) invece riutilizziamo l’euristica del carattere discordante e siccome “T” non compare nel pattern posso fare avanzare il pattern di m posizioni come mostrato nella figura.

d) abbiamo di nuovo un mismatch “A” <> “C”, il carattere discordate nel testo è presente nel pattern (“A”), prendo quella più a destra come mostrato nella figura.

e) in cui abbiamo finalmente uno spostamento valido!

4.4 Conclusioni

L’algoritmo naive risulta il meno efficiente degli altri algoritmi nella maggior parte dei casi. In particolare KMP risulta alquanto veloce con pattern corti, in quanto aumenta la probabilità che un prefisso del pattern abbia un match. In tutti gli altri casi (in pratica i più frequenti) Boyer-Moore risulta l’algoritmo più efficiente ,in particolare con testi grandi e pattern grandi.

Però va notato che il naive è una soluzione competitiva quando si vuole trovare la prima occorrenza di un pattern e questa occorrenza ha una buona probabilità di trovarsi all’inizio del testo, oppure si cercano pattern al più di 3-4 caratteri. (caso improbabile per i pattern del DNA!). In tal caso, il costo addizionale di KMP e di Boyer-Moore potrebbe non ripagare il vantaggio della conseguente scansione veloce del testo in quanto quest’ultima si ferma nelle posizioni iniziali.

Ad oggi l’ algoritmo di Boyer-Moore ha subito modifiche che lo hanno portato ad essere più efficiente, tale algoritmo è quello che viene attualmente utilizzato per la ricerca di sequenze di DNA, tuttavia questo ambito di ricerca si sta dirigendo verso la ricerca approssimava di sequenze di DNA, l’ ambito dell’ approximative string matching è stato studiato ed è tuttora portato avanti dai Prof. Navarro e Raffinot che hanno dedicato all’ argomento alcune pubblicazioni.

Di seguito sono riportati quattro grafici che indicano il comportamento dei tre algoritmi:

- Naive

- KMP

- Boyer-Moore

Nei primi due consideriamo il numero dei confronti eseguiti. Mentre nei restanti due consideriamo il numero di spostamenti validi (attempts).

Nota: i dati ricavati sono da ritenersi puramente indicativi, essendo dipendenti dal tipo di calcolatore sul quale viene eseguito il programma.

Per ricavarli si è implementato ogni singolo algoritmo in Java.

I valori ottenuti degli algoritmi sono il risultato della media di una serie di test, effettuati utilizzando pattern e testi casuali. La dimensione del pattern è indicata nella parte superiore dei grafici.

5 Soluzioni al pattern matching multiplo

Esistono diversi approcci alla ricerca simultanea di più pattern in una sequenza, ognuno con relativi pro e contro ed in questa sezione del documento ne sono presentati i più significativi.

Posto un problema, come accaduto per il pattern matching esatto, la prima soluzione ad essere proposta è sempre quella più semplice, la soluzione naive: semplicemente l’algoritmo naive riportato nel capitolo precedente viene ripetuto singolarmente per il tutti i pattern P da trovare nel testo T.

Il secondo metodo trattato presenta la possibilità di utilizzare la similarità tra i pattern da ricercare al fine di incrementare le prestazioni ed offrire una alternativa migliore alla soluzione naive.

5.1 Algoritmo naive

La più semplice soluzione è ripetere un algoritmo per il pattern matching singolo, come, ad esempio, l'algoritmo "forza bruta", r volte, ovvero per ogni pattern. Non essendoci alcun tipo di ottimizzazione basata su eventuali affinità tra i pattern in questione, la complessità risulta essere uguale a quella dell'algoritmo utilizzato moltiplicata per il numero dei pattern r.

Questo approccio è molto semplice da implementare ma ha una complessità proibitiva (pari a O(|S|*m*n) con l’algoritmo naive), ed è quindi non considerabile in presenza di sequenze molto lunghe.

5.2 Approccio con Tree Data-Structure

Questo tipo di approccio permette l’ottimizzazione della ricerca dei pattern sfruttando la similarità di sottosequenze tra i pattern stessi. Sono due le tecniche più utilizzate e si basano sulla strutturazione delle informazioni in alberi: Prefix tree e Suffix tree.

5.2.1 Prefix Tree (keyword tree, trie)

Una efficiente soluzione al problema del pattern matching multiplo è l’utilizzo dei prefix-tree, detti anche keyword tree oppure trie.

Un keyword tree è un albero che deve seguire le seguenti caratteristiche:

· ogni arco è etichettato con un carattere;

· due archi uscenti da un nodo hanno differenti etichette.

L’utilizzo dei trie è strutturato in due parti:

· Generazione del trie: è la fase di precomputazione del metodo: i pattern appartenenti al’insieme S da ricercare nel testo vanno a formare il keyword tree; l’idea alla base è che i pattern condividano un prefisso comune, più la diramazione tra questi è lontana dalla radice, più questo prefisso in comune è lungo; La costruzione dell’albero è strutturata nel modo seguente:

Si inizia creando il nodo radice, non etichettato in alcuna maniera particolare; si prosegue aggiungendo all’albero ogni pattern P_i, come segue:

Partendo dal nodo radice, si segue il cammino etichettato con i caratteri di P_i e se il cammino finisce prima di P_i, si aggiunge un nuovo arco e un nuovo nodo per ogni carattere rimanente di P_i etichettando il nuovo arco con il carattere aggiunto di P_i.

Alla fine si salva l'identificatore i di P_i nell'ultimo nodo del cammino

· Ricerca: scorrendo il testo lungo il trie è possibile sapere se uno o più pattern appartengano a quest’ultimo. Lungo l’albero abbiamo alcuni nodi che rappresentano la terminazione di un determinato pattern, etichettati con l’identificatore del pattern stesso (spesso questi nodi corrispondono alle foglie); giungere nella fase di scorrimento ad uno dei nodi appena descritti implica un’occorrenza nel testo del pattern a cui appartiene quel nodo terminale.

Complessità del trie

L’operazione di generazione dell’albero richiede generalmente una complessità pari ad O(|S|). La ricerca nel trie può essere effettuata con un’applicazione di un’algoritmo semplice con una complessità pari a O(|S|*m); tramite l’algoritmo di Aho-Corasik (basato su un’automa a stati finiti) è possibile trovare la soluzione in tempo O(|S| + m).

Nota: L’algoritmo di Aho-Corasik non è trattato in questa sezione. Nel caso il lettore sia interessato ad approfondire l’argomento lo si rimanda all’appendice.

Esempio di utilizzo di un trie

Generazione di un trie

In questo esempio abbiamo il keyword tree generato dal set di pattern S:

S = {P₁, P₂, P₃, P₄, P₅} = {“ACTC”, “TGAT”, “ATGAGT”, “TGAG”, “ATGA”}

I nodi in grigio indicano la fine di un pattern e sono etichettati col rispettivo identificatore; da notare che P₃ (“ATCAGT”) include P₅ (“ATGA”), ciò significa che il matching del primo implica il matching anche del secondo; questa situazione è rappresentata nel trie come un nodo di fine pattern lungo il percorso del pattern più lungo.

Ogni nodo può avere al massimo 4 figli, tanti quanti sono gli elementi dell’alfabeto in questione: “A”, “C”, “T”, “G”.

Ricerca pattern nel testo mediante un trie

Supponiamo che il testo sia:

T = “ATGAGCATGA”

Il testo scorre il trie fino al penultimo elemento di P₃, dopodichè termina lo scorrimento perché non c’è corrispondenza tra il successivo carattere del testo e l’etichetta dell’arco che collega al prossimo nodo dell’albero.

Lungo il percorso il testo ha però trovato una corrispondenza con P₅ (“ATGA”); nessun altro pattern è contenuto nel testo (il nodo terminale del pattern P₅ è colorato in nero).

I nodi in grigio chiaro sono quelli visitati durante la fase di ricerca del testo.

5.2.2 Suffix tree

Un’altra soluzione al pattern matching multiplo alternativa ai trie altrettanto efficiente sono i suffix tree. Questi alberi, a differenza della tecnica precedente, vengono generati non a partire dal set di pattern S, bensì dal testo T; per la precisione l’albero viene generato sulla base di tutti i suffissi di T. Una soluzione, questa, che ha un ambito leggermente più ampio rispetto ai keyword tree, in quanto i suffix tree sono utilizzati non solo per la ricerca di più pattern in un testo T, bensì consentono di trovare tutte le occorrenze del singolo pattern P in T. Nell’esempio mostrato in seguito questo punto non è trascurato: sono mostrate per ogni pattern tutte le posizioni nelle quali si trova una loro corrispondenza nel testo.

Passiamo ora alla descrizione specifica dei suffix tree.

Un suffix tree ha le foglie numerate da 1 a n, con n la dimensione del testo T. Questo valore associato ad una foglia corrisponde alla posizione nel testo da cui parte il suffisso indicato dalla foglia stessa; questo suffisso si ricava concatenando tutte le etichette dalla radice alla foglia in questione; in seguito un esempio chiarirà il concetto.

Come i keyword tree anche l’utilizzo dei suffix tree richiedono una fase di precomputazione, nella quale viene generato l’albero a partire dai dati:

· Costruzione del suffix tree: come accennato, la generazione dell’albero avviene a partire dal testo T, in particolare da tutti i suoi suffissi. Algoritmi specializzati come quello di Ukkonen (qui solo menzionato non trattato nello specifico) si occupano di questo problema.

Nota: L’algoritmo di Ukkonen non è trattato in questo documento. Nel caso il lettore sia interessato ad approfondire l’argomento è invitato a consultare i riferimenti bibliografici.

· Ricerca: una volta generato l’albero è possibile effettuare la ricerca dei pattern al suo interno; per ogni pattern p si scorre l’albero e 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.

Complessità del suffix tree

L’algoritmo di Ukkonen per la generazione dell’albero richiede un tempo O(n), dove n è lunghezza di T. La ricerca di un pattern di lunghezza m richiede una complessità pari a O(m).

Esempio di utilizzo del suffix tree

Generazione del suffix tree

Con un testo T = “ATGAGCATGAT”

Otteniamo i seguenti suffissi:

1. “ATGAGCATGAT”

2. “TGAGCATGAT”

3. “GAGCATGAT”

4. “AGCATGAT”

5. “GCATGAT”

6. “CATGAT”

7. “ATGAT”

8. “TGAT”

9. “GAT”

10. “AT”

11. “T”

Suffix tree ottenuto:

Ricerca di un pattern nel suffix tree

Supponiamo di voler cercare il set di pattern

S = {“ATG”, “AGCATA”, “TGA”, “GAGCATGAT”, “TGATA”}

T = “ATGAGCATGAT”

Nella figura sono evidenziati con i colori di ogni pattern i percorsi effettuanti durante la ricerca.

La ricerca ottiene i seguenti risultati:

“ATG”: presente a partire dalla posizione 1 e 7;

“AGCATA”: Non presente: incontrato carattere differente;

“TGA”: presente a partire dalla posizione 2 e 8;

“GAGCATGAT”: presente a partire dalla posizione 3;

“TGATA”: Non presente: raggiunta foglia prima del termine dello scorrimento

Da notare che per non creare confusione tra i valori numerici relativi all’identificazione dei pattern e alle posizioni di occorrenza nel testo, i pattern sono non sono indicati con un valore numerico, bensì con un colore.

6 Soluzioni al pattern matching approssimato

Negli ultimi anni le soluzioni che trovano un approssimazione del pattern in un testo sono le più ricercate per motivi strettamente legati alla struttura complessa del DNA.

Come abbiamo già detto nell'introduzione di questo documento la ricerca di sottosequenze specifiche all'interno della sequenza del DNA è un’operazione fondamentale per problemi quali ricostruire una sequenza di DNA dai singoli pezzi ottenuti da esperimenti, ricercare delle specifiche caratteristiche nelle sequenze di DNA, oppure determinare quanto siano differenti

due sequenze di codice genetico.

La ricerca esatta è però poco utile per queste applicazioni, poiché i pattern raramente combaciano in modo esatto con il testo: le misure sperimentali sono affette da errori di vario tipo e perfino delle sequenze corrette possono avere delle piccole differenze, dovute ad esempio all’evoluzione della specie oppure a processi di mutazione.

Nel Pattern Matching approssimato il problema è quello di ricercare quanto una sottosequenza del testo è simile al pattern cercato e, se la somiglianza rientra entro una certa soglia, di proporla nel risultato della ricerca.

In questo capitolo vedremo un primo approccio naive che tenta di trovare il pattern P all’interno del testo T a meno di k errori, dove k è il numero massimo di mismatch tollerati. Successivamente introdurremo un secondo approccio basato sulle matrici di punti, in grado di misurare il livello di somiglianza tra due stringhe e quindi di trovare un’approssimazione di P in T.

Dopo aver introdotto i primi due approcci viene definita una generalizzazione del problema del Pattern Matching cioè Query Matching: si vuole far corrispondere le sottosequenze di una query con le sottosequenze di un testo, con al massimo k errori. Una query è una "richiesta" ed indica l'azione attraverso la quale vengono estratte una serie di informazioni da un database. La query si ottiene effettuando una serie di comandi standard, specifici per ogni database; nel nostro caso le informazioni estratte sono delle sequenze di nucleotidi.

Tale problema potrebbe corrispondere alla seguente situazione: si vogliono vedere le similitudini tra alcuni geni ma si potrebbe non conoscere quali parti del gene cercare.

Una soluzione valida al problema Query Matching sarà una soluzione valida anche per il problema Pattern Matching.

In ultima analisi sarà descritta una soluzione al problema Query Matching basata sull'idea di filtraggio, cioè si trovano brevi ripetizioni esatte e le si usano come base per trovare ripetizioni più grandi, filtrando, cioè escludendo le posizioni in cui iniziano ripetizioni non estensibili.

6.1 Algoritmo naive

Obiettivo dell’algoritmo è trovare tutte le corrispondenze di un pattern in un testo, accettando un certo numero di non corrispondenze. In input richiede un pattern P[1 .. m], un testo T[1 .. n] e il massimo numero di non corrispondenze k. L’output dell’algoritmo è dato da tutte le posizioni

1 < i < (m – n + 1) tali che T[i .. i+n] e P[1..n] hanno al più k non corrispondenze.

L’algoritmo restituisce I, l’insieme degli spostamenti validi del pattern P nel testo T.

Spiegazione dell’algoritmo: innanzitutto definiamo n ed m rispettivamente come la lunghezza del testo T e del pattern P. Il primo ciclo fa spostare di un carattere alla volta il pattern sul testo. Per ogni spostamento calcoliamo la differenza tra il T[s .. s+m] e P[1 .. m], cioè il secondo for scorre tutte le lettere di P e se P[s+j-1] è diverso da P[j] per 1≤ j < m allora il contatore dist viene incrementato.

Il contatore dist indica la differenza calcolata tra il T[s .. s+m] e P[1 .. m].

Al termine del secondo ciclo for se dist è inferiore alla soglia k lo aggiunge all’insieme I.

Dovrebbe essere chiaro che l’unica differenza tra l’algoritmo appena visto è l’algoritmo di pattern matching con approccio naive è solamente nel calcolo della differenza dist. Possiamo anche dire che l’algoritmo esatto naive è un caso particolare di questo algoritmo con k = 0.

Questo è un algoritmo di forza bruta che ha un tempo di esecuzione pari a O(n*m) , dove n è la lunghezza del pattern P ed m la lunghezza del testo T. Tale tempo è inefficiente.

6.2 Matrice di punti

Una matrice di punti (Dot Matrix) mostra il grado di somiglianza tra due sequenze. Si dispongono le due sequenze da confrontare in alto e a lato della matrice, e si evidenziano le posizioni in cui le due sequenze sono uguali.

Successivamente si cercano le diagonali più lunghe (che superino una certa soglia prestabilita); ogni diagonale rappresenta una corrispondenza perfetta tra sottostringhe delle sequenze originali.

Si estendono le diagonali massime e si uniscono tra di loro nei punti in cui la distanza è minima. Questa operazione ha come risultato una corrispondenza approssimata tra due sottostringhe più lunghe.

Di seguito viene riportato un esempio dell’applicazione della matrice di punti. Cerchiamo il pattern P = “GATTCGTTAGT” all’interno del testo T = “CTGATTCCTTAGTCAG”. L’algoritmo naive visto prima cercherebbe di allineare il pattern sul testo fino a trovare un certo numero di corrispondenze limitando il numero di mismatch. La disposizione a matrice permette di trovare subito le corrispondenze utili.

Nella prima figura ogni asterisco denota una corrispondenza tra il pattern e il testo. Evidenziamo le diagonali con lunghezza minima di 5 (ovviamente le diagonali vanno prese sempre nel verso indicato in figura).

Uniamo le due diagonali trovate nel punto in cui la loro distanza è minima (in questo caso un solo carattere).

Abbiamo trovato una corrispondenza del pattern nel testo con un solo mismatch.

6.3 Query Matching Problem

Una soluzione al problema Query Matching ha come obiettivo principale quello di trovare tutte le sottosequenze del risultato Q della query che corrispondono approssimativamente in un testo T.

Un algoritmo che risolverà tale problema dovrà accettare come input:

- Q[1 .. w] è il risultato di una query;

- T[1 .. n] un testo;

- d la lunghezza delle sottosequenze che corrispondono tra Q e T; indichiamo con t la sottosequenza del testo T e q la sottosequenza del risultato Q della query, tali che t e q coincidono.

- k il numero massimo di non corrispondenze.

Come output restituirà tutte le coppie di posizioni (i, j) dove 1 < i < (w–d+1) e 1 < j < (n–d+1) dove i indica da dove inizia la sottosequenza q in Q, che corrisponde approssimativamente alla sottosequenza t in T che inizia da j, con al massimo k non corrispondenze.

L’idea base del Query Matching è quella di non cercare sequenze con corrispondenza approssimata, ma di cercare sottosequenze con corrispondenza esatta. Con il Pattern Matching approssimato, infatti, a partire dalla prima lettera di T consideravamo le sequenze T[s+1 .. s+m] con 0<s<n-m (s è lo spostamento di P all’interno di T) da confrontare con il pattern P. Con il Query Matching cerchiamo, invece, una sottosequenza t di lunghezza d ≤ m in T (m lunghezza di P) che coincide esattamente con una sottosequenza di P e poi si cerca di estendere t prima a destra e poi a sinistra per trovarne una che approssimi il pattern P nel testo T.

L’immagine qui sotto riportata evidenzia la differenza che c’è tra il Pattern Matching approssimato ed il Query Matching.

6.4 Filtration nel Query Matching

Dopo aver introdotto il problema Query Matching, proponiamo una sua soluzione basata sull’idea di filtraggio per trovare tutte le corrispondenze tra un testo T e il risultato Q di una query e con al massimo k non corrispondenze. In pratica si “filtrano” le posizioni che si conoscono e che non corrispondono tra il testo T e il risultato Q dell query. Essenzialmente la soluzione si compone di due parti:

• Scoperta della corrispondenza potenziale: si trovano tutte le corrispondenze esatte di dimensione d tra il testo T ed il risultato Q della query, attraverso l’hashing o i suffix tree.
• Verifica della corrispondenza potenziale: ciascuna corrispondenza esatta viene estesa a destra e poi anche a sinistra, finché non troviamo una corrispondenza di dimensione m (lunghezza del pattern P) con k non corrispondenze.

Nota: L’hashing non è trattato in questa sezione. Nel caso il lettore sia interessato ad approfondire l’argomento lo si rimanda all’appendice. I suffix tree sono, invece, trattati nel capitolo 5: Soluzioni al pattern matching multiplo.

Scoperta della corrispondenza

Data una sottosequenza di T di lunghezza h e una sottosequenza di Q di pari lunghezza, se le due sottosequenze corrispondono con al massimo k non corrispondenze, possono essere divise in k+1 parti chiamate l-tuple, ciascuna di lunghezza d = ëh/(k + 1)û .

Le k non corrispondenze possono colpire al massimo k di queste k+1 parti, quindi almeno una di queste k+1 parti è perfettamente in corrispondenza, quindi abbiamo una corrispondenza esatta di lunghezza d.

Qui di seguito mostriamo un esempio per chiarire la fase di scoperta della corrispondenza.

Nell’esempio abbiamo il risultato di una query che genera la seguente sequenza di nucleotidi:

Ora si vogliono trovare sottosequenze di lunghezza h = 4, con al più k = 1 non corrispondenze.

Come è ben evidente viene trovata una corrispondenza, evidenziata in azzurro. Col blu denotiamo, invece, una non corrispondenza. Ora si scompone la sequenza in k+1 parti, cioè nelle due seguenti parti:

Parte 1

Parte 2

A

T

G

A

È possibile notare che le k non corrispondenze possono colpire al più k parti, essendo k+1 il numero totale di parti e solo una di queste non presenterà una non corrispondenza, cioè la parte 2.

Quindi abbiamo trovato una potenziale sottosequenza con corrispondenza esatta di dimensione h/(k+1) = 4/2 = 2, utili per trovare il nostro pattern P.

Denotiamo con l-corrispondenza una l-tupla con corrispondenza esatta.

Verifica della corrispondenza potenziale

Per ogni l-corrispondenza esatta, ovvero una l-tupla con corrispondenza esatta, di lunghezza d trovata, la si estende finché non si trova una corrispondenza approssimata di lunghezza m con k non corrispondenze, cioè un approssimazione del pattern P.

Qui di seguito viene riportata una rappresentazione grafica di come si estende una

l-corrispondenza esatta. Infatti viene usato un sistema di riferimento cartesiano in cui si evidenziano i tratti continui che sono le corrispondenze tra il testo T e il risultato Q della query, mentre i punti le non corrispondenze. A partire dal punto evidenziato si estende l’esatta corrispondenza.

7 Conclusioni

Abbiamo visto che le sequenze di proteine e di DNA possono essere viste come lunghi testi costruiti su specifici alfabeti (per esempio, “ACGT” per il DNA).

Queste sequenze rappresentano il codice genetico degli esseri viventi. Ricercare sequenze specifiche di simboli lungo questi testi è un’operazione fondamentale per problemi quali ricostruire una sequenza di DNA dai singoli pezzi ottenuti da esperimenti, ricercare delle specifiche caratteristiche nelle sequenze di DNA, oppure determinare quanto sono differenti due sequenze di codice genetico. Tali problemi possono essere modellati come ricerche di una o più stringhe all’interno di un testo e sono tante le soluzioni algoritmiche.

In questo documento sono stati trattati i principali algoritmi per la risoluzione del pattern matching esatto.

Come abbiamo visto la ricerca esatta è poco utile, poiché non idonea ai problemi reali di pattern matching nell’ambito della biologia, in quanto la struttura del DNA risulta essere molto complessa.

Basti pensare che in ogni molecola di DNA vi sono milioni di sequenze del tipo:

“....ATCGCGATGATGCGATGATCATGCTCGAGATAACATAGTCGATA....”

il cui significato, eccezion fatta per organismi estremamente semplici come i batteri, è pressoché ignoto.

Più precisamente il 95% del DNA nell’uomo ancora oggi è sconosciuto ai biologi.

L’attenzione degli studiosi si è dunque rivolta alla ricerca approssimata, che ha prodotto soluzioni algoritmiche più efficienti ed affidabili. Tuttora il pattern matching approssimato risulta essere un campo in pieno sviluppo.

8 Appendici

8.1 Hashing

Una hash table è una struttura dati che viene usata per l'implementazione di strutture dati astratte associative. Può usare qualsiasi tipo di dato come indice e tutte le operazioni si possono fare in tempo costante O(1). L'hash table è molto utilizzata nei metodi di ricerca nominati hashing.

L'hashing è un'estensione della ricerca indicizzata da chiavi che gestisce problemi di ricerca.

Una ricerca basata su hashing è completamente diversa da una basata su confronti: invece che spostarci nella struttura data in funzione dell'esito dei confronti tra chiavi, cerchiamo di accedere agli elementi nella tabella in modo diretto tramite operazioni aritmetiche che trasformano le chiavi in indirizzi della tabella.

Il primo passo per realizzare algoritmi di ricerca tramite hashing è quello di determinare la funzione di hash: il dato da indicizzare viene trasformato da un'apposita funzione di hash in un intero compreso tra 0 ed n-1 che viene utilizzato come indice in un array di lunghezza n. Idealmente, chiavi diverse dovrebbero essere trasformate in indirizzi differenti, ma poiché non esiste la funzione di hash perfetta, è possibile che due o più chiavi diverse siano convertite nello stesso indirizzo. Il caso in cui due dati diversi hanno lo stesso valore di hash viene chiamato collisione e può essere gestito in vari modi, ovvero ci sono diverse soluzione al problema delle collisioni in hashing.

8.2 Algoritmo di Aho-Corasick

Automa di Aho-Corasick

Gli automi a stati finiti possono essere considerati sia come modelli semplificati di macchine che come meccanismi usati per specificare linguaggi, entrambi gli aspetti sono utili al fine del problema del pattern matching. Diamo quindi una definizione di automa a stati finiti deterministico.

Un automa a stati finiti deterministico è una quintupla A = {∑; Q; g; q; F}, dove ∑ = {a₀…a_n} è l'alfabeto di input, Q = {q₀…q_n} è un insieme finito e non vuoto di stati, è l'insieme e gli stati finali, q₀ è lo stato iniziale e è la funzione di transizione che ad ogni coppia (carattere,

stato) associa uno stato successivo.

Assumiamo che la funzione di transizione non sia totale, ovvero il valore g(q, a) è lo stato raggiunto dallo stato q mediante la transizione etichettata dal carattere a, se presente. L'automa che a noi interessa è un automa di pattern matching. Si parla di automa di pattern matching quando dato un pattern P, tale automa A_P accetta l'insieme di tutte le parole contenenti P come suffisso.

Detto questo siamo diamo allora la definizione dell'automa di Aho-Corasick.

L'automa viene definito mediante tre funzioni:

1. Sia e si definisce la funzione goto g(q, a) da lo stato successivo partendo dallo stato q facendo il matching del carattere a (funzione di transizione). Se un arco (q, v) è etichettato da a, allora g(q, a) = v, inoltre g(0, a) = 0 per ogni a che non etichetta un arco fuori dalla radice. Inoltre l'automa rimane nello stato iniziale se esamina caratteri non presenti nel pattern, cioè g(q, a) = 0.
2. la funzione fail . Il valore f(q), per q <> 0 dà lo stato in cui mi trovo quando si verifica un mismatch. Diremo che f(q) è il nodo etichettato dal più lungo suffisso proprio w di L(q) (vedere la nota dopo la figura) tale che w sia prefisso di qualche pattern, per questo motivo una transizione della funzione failure (fail transition) non manca nessuna potenziale occorrenza. Notiamo che f(q) è sempre definita, poiché L(0) è un prefisso di ogni pattern.
3. La funzione output out(q) ci dà l'insieme dei pattern riconosciuti quando entriamo in uno stato q. Gli stati dell'automa sono tipicamente rappresentati mediante un trie (keyword tree), vediamo all'opera un esempio seguente, dove le linee tratteggiate sono le fail transition.

Transizioni di Failure:

Nota: Si definisce l'etichetta di un nodo v come la concatenazione delle etichette sugli archi che compongono il percorso dal nodo radice a v, e si indica con L(v).

Ricerca

Vediamo ora come funziona la ricerca di un insieme di pattern all'interno di un testo T[1…m], supponendo di aver gia inizializzato l'automa di Aho-Corasick. La funzione di transizione può essere implementata mediante una tabella, che viene espressa con una matrice. I passi da seguire nella fase di ricerca sono:

• Partire dalla radice del trie ed eseguire fail transition finchè l'insieme restituito dalla funzione g non è vuoto per il carattere in esame.
• Effettuare una goto transition arrivando ad uno stato.
• Se tale stato ha una funzione di output non vuota, allora ho trovato una occorrenza.

Vediamo lo pseudocodice, dove g è la funzione di goto, f è la funzione fail, out è la funzione di output:

Complessità della ricerca

La ricerca nel testo T[1…m] con un automa di Aho-Corasick si effettua in O(m + z), dove z è il numero di occorrenze del pattern cercato.

Costruzione dell'automa di Aho-Corasick

Prima fase: funzione goto

Affinché sia possibile eseguire la ricerca con l'algoritmo di AC è necessario che l'automa di AC sia stato costruito, inizializzando correttamente le funzioni goto, fail e output (rispettivamente g, f e out).

La costruzione dell'automa, per un insieme di pattern fissato avviene in due fasi:

• nella prima fase si determinano gli stati dell'automa e il grafo della funzione goto
• nella seconda fase si definisce la funzione fail;

la costruzione della funzione output ha inizio nelle prima fase e si conclude nella seconda fase.

La funzione goto e il suo grafo non sono altro che un keyword tree, o trie, come già detto: basterà quindi eseguire l'algoritmo per la costruzione del keyword tree sull'insieme di pattern (algoritmo indicato nella sezione del documento 5.2.1).

Per completare la funzione goto, vengono creati dei cicli sullo stato iniziale settando g(0, a) = 0 per ogni simbolo a appartenente all'alfabeto, diverso dai caratteri iniziali delle keyword nell'insieme.

Esempio

Vediamo come si comporta la prima fase della costruzione dell'automa di Aho-Corasick con l'insieme di pattern P = {he, she, his, hers}: viene creato il keyword tree aggiungendo i pattern come cammini orientati da 0 a v, e settato out(v) = L(v) per i nodi destinazione dei cammini orientati. Infine si creano dei cicli sulla radice per ogni carattere dell'alfabeto diverso da ogni carattere iniziale di un pattern dell'insieme: in questo caso per ogni carattere diverso da 'h' e 's'. Il risultato di questa prima fase è mostrato nella seguente figura.

Esempio di costruzione dell'automa di AC: risultato della prima fase

Seconda fase: costruzione della funzione fail La funzione fail è calcolata per i nodi del trie attraverso una visita in ampiezza (BFS) in cui ci si occupa di completare anche la funzione output. Si definisce la profondità di uno stato s nel trie, come la lunghezza del più breve cammino dalla radice allo stato s. La funzione fail è calcolata nel seguente modo:

• vengono messi in coda i nodi a profondità 1 (ovvero i nodi della stella uscente della radice) e vi si associa un valore di fail uguale a 0;
• il valore della funzione fail associato al generico nodo a profondità d è calcolato sulla base dei valori della funzione di goto e di output dei nodi a profondità minore

Per calcolare la fail di un nodo s a profondità d, si considera state = r, con r il nodo di profondità (d - 1) predecessore di s; se g(f(state), a) <> null, dove a è l'etichetta dell'arco che congiunge i nodi r ed s, allora f(s) = g(f(state), a), altrimenti si ripete questo controllo con state = f(state) finché non si riesce a inizializzare f(s). Si noti che g(0, c) <> null per ogni c appartenente all'alfabeto, quindi il ciclo terminerà sempre. Intuitivamente il ciclo serve a trovare il nodo più profondo state tale che L(state) sia un suffisso proprio di L(s) e g(state, a) sia definita.

Una volta calcolata la funzione fail del generico nodo s l'algoritmo aggiornerà la funzione output unendo l'insieme di output di s con quello di f(s). Questo viene fatto perché f (s), se esiste, è un suffisso proprio (= non nullo) di L(s) e dovrà quindi essere riconosciuto anche allo stato s.

Dato che la prima fase della costruzione dell'automa di AC è banale mostreremo solo lo pseudocodice della seconda fase:

Q.add(e) aggiunge e in coda a Q;

Q.remove() legge e rimuove l’elemento in testa.

Riassumendo: la costruzione del keyword tree è banalmente lineare, la seconda fase dell'algoritmo è una visita in ampiezza (lineare nel numero di nodi del keyword tree) che contiene un ciclo che, sebbene possa sembrare anch'esso lineare in n, per come viene usato nell'algoritmo il suo peso è ammortizzato ad O(1). L'aggiornamento delle funzioni di output, anch'esso eseguito una volta per

ogni nodo, può essere implementato in tempo costante rappresentando l'insieme out(u) con una lista dato che gli insiemi da unire sono sempre disgiunti e quindi l'unione è il semplice concatenamento delle due liste. Quindi, complessivamente, la costruzione dell'automa è lineare in n.

Esempio di costruzione dell'automa di AC: primi passi della seconda fase: