Costruzione efficiente di indici per ripetizioni con caratteri "wild card".

1

Università degli studi di Pisa

FACOLTÀ DI SCIENZE MATEMATICHE, FISICHE E NATURALI

Corso di Laurea Specialistica in Informatica

Costruzione eciente di indici per ripetizioni con

caratteri wild card

Relatore:

Dott. Nadia Pisanti

...

Correlatore: Prof. Roberto Grossi

...

Tesi di laurea di:

Davide Cangelosi

Matr. 224348

Anno Accademico 2006 - 2007

Indice

1 Introduzione 5

1.1 Inferenza di motivi . . . 5

1.1.1 Inferenza di motivi con wild card . . . 7

1.2 La Biologia e l'Informatica . . . 9

1.3 Alcune nozioni di biologia molecolare . . . 10

1.4 L'inferenza di motivi con wildcard in biologia molecolare . . . 12

1.4.1 Binding site e promotori . . . 12

1.4.2 Microsatelliti . . . 14

1.5 L'approssimazione nell'inferenza dei motivi . . . 15

1.6 Approcci per la ricerca dei motivi in sequenze biologiche . . . 17

1.6.1 Approccio pattern driven . . . 18

1.6.2 Approccio sample driven . . . 18

1.7 Obbiettivi della tesi e risultati raggiunti . . . 19

2 Relazioni di somiglianza e algoritmi 21 2.1 Denizioni preliminari . . . 22

2.2 Costruzione degli alberi dei sussi . . . 28

2.2.1 L'algoritmo di costruzione di Ukkonen . . . 29

2.2.2 L'algoritmo di costruzione di McCreight . . . 30

2.3 Distanza e Somiglianza . . . 31 2

INDICE 3

2.3.1 Il modello di distanza di Edit . . . 32

2.3.2 Il modello di distanza di Hamming . . . 34

2.3.3 Nozioni di somiglianza . . . 36

2.4 Algoritmi per le relazioni . . . 42

2.4.1 KMR per la relazione identità . . . 43

2.4.2 KMRC per la relazione non transitiva senza errori . . 45

2.4.3 Albero dei sussi per le relazioni identità e non transitive 47 2.5 La relazione di equivalenza con dierenze Hl L . . . 49

3 La generazione di tutte le combinazioni 55 3.1 Denizione e rappresentazione delle combinazioni . . . 55

3.2 L'albero Binomiale e l'organizzazione delle combinazioni . . . 58

4 La gerarchia tra indici 62 4.1 Un esempio di ordinamento tra indici . . . 62

4.2 Base di alberi e le combinazioni . . . 68

4.3 La gerarchia e il ranamento . . . 75

5 Algoritmi proposti per l'inferenza di motivi con wildcard 78 5.1 Algoritmo naive . . . 79

5.2 Soluzione con generazione mirata delle combinazioni . . . 82

5.3 Soluzione per ranamento . . . 85

5.3.1 Metodo alternativo per la generazione mirata . . . 86

5.4 Analisi degli algoritmi proposti e confronto . . . 91

6 Conclusioni e lavoro futuro 93

A 94

Capitolo 1

Introduzione

In questo capitolo si inquadra il problema algoritmico arontato in questa tesi. A cominciare da una breve introduzione al problema dell'inferenza di motivi in informatica, aronteremo le principali problematiche dell'inferen-za con wildcard e le applicazioni biologiche che la motivano. Esaminere-mo, inoltre, la necessità dell'approssimazione in applicazioni biologiche, in-trodurremo la formulazione combinatoria della soluzione proposta. Inne, riassumeremo i risultati raggiunti.

1.1 Inferenza di motivi

L'inferenza di pattern ripetuti è un'area di ricerca volta a sviluppare stru-menti e metodi per trovare pattern non conosciuti a priori. Tali pattern sono spesso chiamati anche motivi. Quest'area di ricerca, nota anche come pattern discovery o motif inference, ha molti campi di applicazione. Nella compres-sione di testi, ad esempio, una delle attività dell'algoritmo di comprescompres-sione mediante sostituzione di testi, è proprio la ricerca di stringhe che si ripetono nel le da comprimere. Tali ripetizioni vengono rimpiazzate da puntatori a copie contenute in una struttura dati, chiamata dizionario, costruita a

tire dal le. Da ciò risulta che, più sono le ripetizioni di sequenze nel le di input, maggiore è il grado di compressione raggiunta, in quanto i puntatori occupano in genere meno spazio delle stringhe rimpiazzate [ZL77]. Nei siste-mi di data siste-mining, pattern o item che occorrono insieme abbastanza spesso, detti itemset frequenti, sono alla base del problema della ricerca delle regole associative. In musica, l'identicazione di ripetizioni di segmenti o frasi nei pezzi musicali è una tecnica che rivela una struttura nelle registrazioni audio, che è molto utile per l'automatizzazione dei processi di analisi, ricerca e clas-sicazione di musica a partire da una qualsiasi rappresentazione dell'audio [DH02]. Tra i nuovi campi di applicazione vi è quella della biologia mole-colare, a cui ci interessiamo in questa tesi, e nell'ambito della quale pattern ripetuti, in proteine e sequenze di DNA, possono corrispondere ad elementi biologicamente rilevanti dal punto di vista funzionale o strutturale. La ricer-ca di motivi in quest'area si basa sull'assunzione che, siccome queste regioni occorrono più spesso di quanto ci si aspetti, esse sono state più conservate durante l'evoluzione e quindi potrebbero avere una particolare e rilevante funzione biologica. La ricerca dei motivi è uno dei problemi fondamentali della bioinformatica e trova applicazione in molti dei suoi campi, di cui sono esempi l'allineamento multiplo di sequenze, la caratterizzazione delle famiglie di proteine, l'identicazione di segnali promotori, e altre aree di ricerca.

L'inferenza di motivi, in qualsiasi campo essa sia applicata, ha a che fare, sia con ripetizioni identiche che con ripetizioni che non occorrono perfetta-mente uguali. In biologia, le ripetizioni identiche sono importanti perchè rappresentano oggetti estremamente conservati. Le ripetizioni con qualche dierenza sono altrettanto ricorrenti e non meno importanti. Il motivo per cui sequenze che si somigliano possono rappresentare lo stesso oggetto bio-logico è che il DNA, e in generale le sequenze biologiche, sono suscettibili

1.1. INFERENZA DI MOTIVI 7

ad alterazioni. Una mutazione, come viene generalmente chiamata un'al-terazione del codice genetico, non modica necessariamente la funzione del-l'oggetto rappresentato dalla sequenza mutata (mutazioni silenti), quindi, sequenze non perfettamente identiche rappresentano lo stesso oggetto bi-ologico. Algoritmicamente l'inferenza di motivi esatti è una sda chiusa perchè oggigiorno esistono molte soluzioni ecienti, vedi [Ukk95], mentre l'inferenza di motivi approssimati rimane ancora un problema aperto. Per questo motivo, la ricerca delle ripetizioni con dierenze, o inferenza di motivi approssimati, è l'argomento trattato in questa tesi.

1.1.1 Inferenza di motivi con wild card

I motivi approssimati eventualmente scoperti con la ricerca, rappresentano pattern diversi che in teoria sono lo stesso oggetto biologico. Le attuali forme di rappresentazione dei motivi approssimati catturano aspetti come la fre-quenza delle lettere per ogni posizione del motivo, quali sono le posizioni di dierenza tra le occorrenze, ecc. Non esiste attualmente una rappresen-tazione di motivo che cattura pienamente, sia in termini formali che in ter-mini biologici, tutti gli aspetti che caratterizzano le ripetizioni nelle sequenze biologiche. I principali tipi di rappresentazione dei motivi approssimati sono classicabili in base al modo con cui raggruppano le occorrenze. Questa clas-sicazione distingue due grandi famiglie: le matrici (i cui componenti sono pesi determinati dalla frequenza delle lettere in ogni posizione del motivo, come le sequenze LOGO, Consensus e PSSW) e i pattern con wildcard (intesi come sequenze fatte sia da caratteri dell'alfabeto sia da caratteri wildcard). Un carattere wild card, denotato con il simbolo ◦, è un carattere speciale che non appartiene all'alfabeto della sequenza di input, ma che corrisponde a qualsiasi carattere in essa contenuta. In altre parole, ogni confronto tra

un carattere dell'alfabeto e il carattere wildcard restituisce lo stesso risultato del confronto tra due caratteri uguali dell'alfabeto. In questa tesi, scegliamo la rappresentazione di motivi come pattern con wildcard. L'insieme delle occorrenze rappresentate da un pattern con wildcard è composto da tutte le ripetizioni identiche con al più dierenze nelle posizioni relative ai caratteri wildcard. Un esempio di pattern con wild card è il seguente.

Esempio 1. Data una lunghezza L = 8, un numero k = 4 e una sequenza

s = ABCABCABABBCBACABC ∈ {A, B, C}_{, alcuni dei motivi con}

wildcard per s sono:

m = AB ◦ ◦AB ◦ ◦

m occorre nelle posizioni {2,4} di s.

m1 = ◦ ◦ ◦ ◦ ◦ ◦ BC

m1occorre nelle posizioni {5,10} di s.

m2 = BC ◦ ◦C ◦ B◦

m2occorre nelle posizioni {2,11} di s.

Non esaminiamo tutte le possibili combinazioni di wildcard perchè li ve-dremo più in dettaglio nei prossimi capitoli.

Sulla base di quanto detto, deniamo il problema dell'inferenza di motivi con wildcard.

Problema 1 (Problema dell'inferenza dei Motivi con wildcard). Dati in input una sequenza di caratteri s ∈ Σn_{, una lunghezza L, un numero k e un}

quorum q, trovare tutti i motivi che occorrono in s con al più k wildcard e che occorrono almeno q volte.

Nel problema appena denito, si intuisce che le posizioni dei wildcard, non sono prevedibili a priori. Non si può discriminare tra le posizioni, tranne nel caso in cui non si conosca già la struttura del motivo, quindi, la ricerca

1.2. LA BIOLOGIA E L'INFORMATICA 9

dei motivi deve esaminare tutte le possibili combinazioni di k posizioni wild-card. Questo approccio è noto come approccio combinatorio e il numero di combinazioni da analizzare è esponenziale. Il motivo di questa complessità è che ogni parola di lunghezza L del testo ha 2L−k _{possibili sottosequenze}

dis-tinte, o combinazioni di k posizioni wildcard. In s si distinguono al più n−L parole diverse. Quindi, potenzialmente, il numero di parole da esaminare è dell'ordine di O(n ∗ 2n_).

Uno degli obbiettivi di questa tesi, come vedremo, è risolvere il problema dell'inferenza dei motivi con wildcard riducendo sensibilmente lo spazio delle combinazioni da esaminare.

1.2 La Biologia e l'Informatica

La biologia e l'informatica, negli ultimi decenni, hanno stretto un impor-tante legame di cooperazione per raccogliere la sda che la scienza ha lan-ciato riguardo la comprensione dei complessi meccanismi che governano la vita. La bioinformatica è la disciplina che si occupa dello sviluppo e dell'in-tegrazione delle applicazioni della scienza dell'informazione al servizio della ricerca scientica in campo biotecnologico [Pro]. In particolare, l'impiego di modelli statistici validi per l'interpretazione dei dati che gli esperimenti di biochimica e biologia molecolare producono, lo sviluppo di nuovi modelli e strumenti matematici adatti all'analisi di sequenze di DNA, RNA e proteine e l'organizzazione e la gestione di basi di dati delle conoscenze acquisite sul genoma, sono solo alcuni dei compiti svolti dall'informatica. Il campo in cui si inquadra la nostra ricerca è lo sviluppo di nuovi modelli e strumenti matematici per l'analisi di sequenze di ogni tipo, ad esempio, di DNA, RNA e proteine.

Sul piano dell'informatica il DNA, gli RNA e le proteine sono delle se-quenze di caratteri denite su un alfabeto, che per il DNA, l'RNA e le proteine sono rispettivamente:

• ΣDN A= {A, C, T, G}

• ΣRN A= {A, C, U, G}

• ΣP roteina = {A, R, D, N, C, E, Q, G, H, I, L, K, M, F, P, S, T, W, Y, V }

1.3 Alcune nozioni di biologia molecolare

Il patrimonio genetico o genoma e tutto ciò che fa funzionare una cellu-la è codicato nel DNA. Il DNA è una lunga catena di piccole molecole, chiamati nucleotidi o basi, che possono assumere uno tra quattro possibili valori. Nella sua forma naturale, il DNA ha una struttura attorcigliata che, se estesa, da origine alla nota doppia elica. I due lamenti distinti che for-mano il DNA sono uno complementare all'altro: ciò signica che ogni coppia di molecole accoppiate nei due lamenti ha precise caratteristiche chimico-siche. Il funzionamento del DNA dipende dalla particolare anità tra le basi; se prendiamo due sequenze complementari e li mettiamo vicine, esse tenderanno ad unirsi come una cerniera, compiendo quello che in biologia molecolare è chiamato ibridizzazione. L'espressione del DNA, cioè l'attività che permette al DNA di tradursi in istruzioni, si verica per ibridizzazione di alcune zone del DNA con altre molecole come proteine e RNA. Notori-amente, si suddivide il DNA in zone codicanti e non codicanti: le zone codicanti sono zone speciche del DNA adibite alla sintesi delle proteine, le zone non codicanti sono, invece, zone la cui implicazione nel processo di regolazione è stata accertata, ma che per la maggior parte, è composta dal cosiddetto DNA spazzatura, di cui non se ne è ancora capita la funzione.

1.3. ALCUNE NOZIONI DI BIOLOGIA MOLECOLARE 11

All'interno della parte codicante del DNA, si individua il genoma composto interamente dai cosiddetti geni, cioè sequenze di DNA trascritte e tradotte nel processo di sintesi delle proteine, come vedremo più avanti. Ogni gene può contribuire alla sintesi di diverse proteine. L'individuazione dei geni coinvolti nella sintesi di una determinata proteina è una delle sde che la bi-ologia stà arontando oggigiorno. La dinamica di una cellula, cioè l'attività che viene compiuta dentro una cellula, è un usso continuo di interazioni tra piccole molecole e macromolecole come DNA, RNA e proteine [AC01]. Le proteine sono molecole fatte di amminoacidi unite da legami. Esse portano in sè il programma codicato dai geni è generalmente svolgono la loro fun-zione all'interno della cellula, interagendo con le altre molecole. Ad esempio, delle proteine chiamate enzimi, accelerano molte reazioni chimiche, altre si occupano dell'architettura della cellula (membrane), altre ancore regolano la trascrizione dei geni, ecc. [AC01]

L'attività principale del DNA è la sintesi delle proteine che è il processo con cui esse si creano a partire dal DNA. La sintesi proteica passa attraverso due tappe fondamentali: la trascrizione e la traduzione. La trascrizione sin-tetizza una molecola fatta da una catena di triplette di nucleotidi, chiamata mRNA, ottenuta con un complesso meccanismo, come si dice in termini tec-nici, di co-espressione e co-regolazione dei geni coinvolti nel processo. In altre parole, il DNA funge da stampo per la trascrizione di alcune sue sequenze nella catena complementare che forma il mRNA. Una volta sintetizzato il mRNA, esso compie un piccolo viaggio verso una zona specica della cel-lula, in cui sono presenti dei corpuscoli chiamati ribosomi. I ribosomi sono i responsabili della cosiddetta traduzione. Con la traduzione le triplette di nucleotidi sul mRNA vengono decifrate e tradotte nei corrispondenti ammi-noacidi che formano la proteina in costruzione. Nella formazione, man mano

che il mRNA scorre sul ribosoma, altre molecole chiamate transfer RNA (tR-NA), che portano legate in modo specico un amminoacido, si mettono in posizione e si attaccano tra loro con legami peptidici, formando alla ne la proteina codicata dal quel particolare mRNA.

1.4 L'inferenza di motivi con wildcard in biologia

molecolare

L'inferenza di motivi con wildcard è applicabile ad esempio a pattern rela-tivamente corti, a motivi con una struttura più o meno nota, a motivi per la cui conservazione della funzione biologica è possibile escludere a priori particolari posizioni, ecc. In questa sezione, arontiamo in particolare, due applicazioni reali che sono di grande interesse per la bioinformatica, e che rientrano nelle categorie prima menzionate: i binding site e i microsatelliti.

1.4.1 Binding site e promotori

Durante la trascrizione di un gene, una o più molecole, chiamati fattori di trascrizione (TF), devono legarsi a regioni di DNA chiamate binding site. Un binding site si trova nella regione promotore di un gene, cioè la zona di DNA, vicina alla sequenza genica, contenente l'informazione necessaria (e suciente) per localizzare la sequenza da cui iniziare la trascrizione genica. Questa informazione è fondamentale, in biologia, non solo per trovare il gene corrispondente al gene regolato da quel particolare binding site, ma anche per studiare i meccanismi che controllano l'espressione e la regolazione del gene stesso. Un fattore di trascrizione può legarsi a più binding site, presenti nelle regioni promotrici dei diversi geni corrispondenti, e da questo si deduce che uno stesso TF regola la trascrizione di molti geni, che in tal caso sono detti

1.4. L'INFERENZA DI MOTIVI CON WILDCARD IN BIOLOGIA MOLECOLARE13

co-regolati. Le sequenze nucleotidiche dei binding site sono modellabili con pattern abbastanza corti (spesso non vanno oltre le decine di basi). Inoltre, i binding site possono occorrere con dierenze che spesso sono localizzabili, e questo giustica anche la loro possibile inferenza mediante i motivi con wildcard.

Come per i pattern delle proteine, i motivi nelle sequenze non codicanti del DNA possono essere usati per determinare la funzione delle sequenze nu-cleotidiche, ad esempio, per trovare tutti i promotori in un genoma, o per de-terminare siti funzionali specici, come le regioni coinvolte nella regolazione dell'espressione genica. Le sequenze non-codicanti generalmente non sono ben conservate, quindi, la presenza di sequenze conservate nelle regioni pro-motrici spesso implica che queste regioni sono funzionalmente importanti. Per trovare tutti i promotori in sequenze genomiche vaste, occorre identi-care caratteristiche che sono comuni a tutti i promotori, ma che non sono presenti in sequenze non promotrici. Spesso l'obbiettivo non è solo identi-care i promotori, ma anche capire come sono regolati i geni sotto il controllo dei promotori. Ciò comporta l'identicazione di sequenze regolatrici speci-che nelle regioni promotrici che si legano a specici fattori di trascrizioni in risposta ai segnali biologici. Motivi che sono agganciati da TF conosciu-ti possono essere modellaconosciu-ti per trovare nuovi binding site in un genoma e per identicare geni che sono regolati nello stesso modo. Quando i TF che si legano ai motivi sono sconosciuti, questi possono essere trovati cercando elementi comuni nelle regioni promotrici che è noto che siano co-regolati.

Inoltre, la presenza di patologie degenerative spesso è associata alla co-regolazione di gruppi di geni specici, la cui contemporanea attivazione è alla base delle condizioni patologiche. Quindi, l'identicazione dei motivi è il punto di partenza per ogni attività sperimentale volta a studiare la co-espressione

e la co-regolazione dei geni associate a speciche patologie.

I binding site si presentano anche in forma strutturata, in [MS00], sono modellati come motivi composti da uno o più sottosequenze, chiamate boxes, che si trovano ad una certa distanza tra loro (distanza intesa come numero di nucleotidi che separano i boxes nella sequenza). Dal nostro punto vista ogni motivo con wild card è di fatto un motivo strutturato in cui i caratteri wildcard sono elementi separatori tra i boxes.

1.4.2 Microsatelliti

Non tutto il DNA codica geni, il 98% del genoma umano è costituito da sequenze non codicanti che hanno altre funzioni, tra le quali attivare e dis-attivare i geni. Tuttavia, gran parte del DNA spazzatura non sembra avere alcuna utilità. Nel DNA spazzatura si identicano regioni note come DNA satellite [JDW05]. Si tratta di sequenze ripetute più volte in varie combi-nazioni. Negli ultimi anni, si è cominciato a scoprire che i cosiddetti mi-crosatelliti, regioni contenenti sequenze ripetitive brevi (simple sequence re-peats), costituiscono il 3% del genoma, eseguono numerose funzioni, e hanno un signicato biologico molto importante.

Si è constatato che queste regioni del genoma sono caratterizzate da una forte variabilità in lunghezza, che può avere eetti sia positivi che negativi. In alcuni batteri patogeni, le sequenze ripetitive promuovono la comparsa di nuove caratteristiche che possono consentire loro di sopravvivere a mod-icazioni ambientali potenzialmente letali (si parla a tal proposito di (zone ipervariabili). Inoltre, si è ipotizzato che queste sequenze ripetute proteggano le zone codicanti vicine da mutazioni dannose.

È probabile che alcuni microsatelliti abbiano eetti notevoli anche sul-l'uomo dal momento che nel nostro genoma c'è ne sono almeno 100.000

1.5. L'APPROSSIMAZIONE NELL'INFERENZA DEI MOTIVI 15

[JDW05]. Finora, però, ai microsatelliti umani è stata assegnata solo una funzione negativa, e cioè essere la causa di malattie di natura neurologica. Per questo motivo, i microsatelliti sono usati per diagnosticare malattie neu-rologiche e per identicare soggetti a rischio. Inoltre, poichè la lunghezza dei microsatelliti può variare da un individuo ad un altro, si è iniziato ad usarli per l'identicazione dei criminali, o per determinare la paternità. I microsatelliti sono noti anche come ripetizioni in tandem semplici (STR), in quanto consistono sempre in sequenze ripetute in tandem (per esempio: nella sequenza ATGCCATGCCATGCC, la stringa ATGCC è ripetuta in tandem tre volte). Per sequenze ripetute in tandem si intende sequenze in cui una porzione è ripetuta più volte una di seguito all'altra. Anche per questo problema sono stati sviluppati molti algoritmi come quelli in [RKK03, WYKG04, GLM02, SM98].

1.5 L'approssimazione nell'inferenza dei motivi

Le principali motivazioni per l'approssimazione nell'inferenza dei motivi in sequenze biologiche sono: la presenza di errori nei dati rilevati da esperimen-ti condotesperimen-ti in laboratorio e le alterazioni subite dalla sequenza di DNA. Noi ci soermiamo sulla seconda categoria. Se le mutazioni coinvolgono singole basi, allora si parla di alterazioni o mutazioni puntiformi, se riguardano par-ti di cromosomi sono dette cromosomiche, altrimenpar-ti sono dette genomiche [Bet]. In genere, si può pensare che le mutazioni abbiano eetti fatali o comunque dannosi e spesso questa credenza è vera: le mutazioni possono provocare malattie, ma in realtà è molto importante tenere in mente che le mutazioni del DNA sono anche alla base dell'evoluzione di tutti gli esseri viventi e quindi anche dell'uomo. Le mutazioni hanno come eetto sulla se-quenza inserzioni, cancellazioni e sostituzioni di singoli nucleotidi. Noi siamo

interessati alle mutazioni che provocano soltanto sostituzioni. Le mutazioni con sostituzioni possono essere classicate in : senso, non senso, neutre e silenti. Una mutazioni di senso sostituisce un singolo amminoacido nella sequenza della proteina codicata; una mutazione non senso sostituisce un nucleotide che causa la sintesi di una proteina incompleta; la mutazione neu-tra forma una nuova tripletta che specica un aminoacido diverso, ma la sostituzione non altera la funzione della proteina; la mutazione silente, in-vece, forma una nuova tripletta che specica lo stesso aminoacido. Dunque, le mutazioni con sostituzione non hanno sempre eetti sull'attività cellulare, nè sulla codica espressa dalle sequenze stesse. Ad esempio, se un binding site per una proteina subisce una mutazione silente, comunque la proteina continua la sua attività nella stessa maniera. Le ripetizioni che rappresentano lo stesso oggetto con la stessa funzione, come nel caso della co-regolazione o la co-espressione, che come abbiamo già accennato, possono subire, o aver subito, mutazioni. Di conseguenza, la ricerca di tali oggetti funzionali ha bisogno dell'approssimazione nell'inferenza di motivi. Inne, sul piano del-l'informatica, gli errori sono stati modellati con una funzione di distanza tra stringhe introdotta da Levenshtein in [Lev66] nota anche come distanza di edit. Date due stringhe in ingresso, la distanza calcola il numero minimo di operazioni di cancellazioni, inserzioni e sostituzioni che trasformano una sequenza nell'altra. Esistono anche altre funzioni di distanza che vedremo nel prossimo capitolo.

1.6. APPROCCI PER LA RICERCA DEI MOTIVI IN SEQUENZE BIOLOGICHE17

1.6 Approcci per la ricerca dei motivi in sequenze

biologiche

Il problema dell'inferenza dei motivi con dierenze è molto dicile da risol-vere a causa della vastità dello spazio delle soluzioni da esplorare. Esistono due approcci fondamentali alla risoluzione di questo problema.

L'approccio combinatorio di cui fanno parte gli algoritmi esatti, tra cui quello proposto in questa tesi, che si basano sulla ricerca esaustiva dei mo-tivi e che quindi garantiscono di trovare la soluzione ottima. Gli algoritmi euristici, che riducono lo spazio di ricerca basandosi su euristiche e cer-cando i motivi nei sottoinsiemi di tutti i possibili pattern, con conseguente possibile perdita di una parte non sempre denibile della soluzione, e che quindi garantiscono solo il raggiungimento di ottimi locali [ABG98]. Inne, e l'approccio statistico al problema, di cui sono esempi Gibbs sampler[LW93] e MEME[BE94], in cui l'alta complessità del problema è contrastata sem-plicemente non eettuando la ricerca tra tutti i possibili motivi esistenti, ma riducendo lo spazio di ricerca facendo delle assunzioni probabilistiche.

Sebbene il tempo di esecuzione di questi algoritmi potrebbe essere espo-nenziale, i programmi esistenti usano tecniche di pruning per restringere lo spazio di ricerca e velocizzare la ricerca stessa, facendo uso di strutture dati quali gra e alberi dei sussi. Anche in questa tesi si utilizza una tecnica che usa una struttura di indicizzazione, restringendo in pratica lo spazio di ricerca.

Mostriamo adesso, due degli approcci che rientrano nella famiglia di soluzioni combinatorie al problema dell'inferenza dei motivi con dierenze.

1.6.1 Approccio pattern driven

Una delle tecniche più semplici per risolvere il problema dell'inferenza dei motivi, è conosciuta come Pattern Driven Approach (PD) [PS00]. Gli algo-ritmi pattern driven enumerano ogni possibile pattern che soddisfa i vincoli, tipicamente la lunghezza, stabiliti dall'utente. Se la lunghezza dei pattern da cercare è ad esempio l, ci sono 4l _{possibili pattern, utilizzando}

l'alfa-beto del DNA. Gli approcci pattern driven confrontano ogni pattern con tutte le sottostringhe lunghe l presenti nella sequenza di input, incremen-tando il contatore associato ad ogni pattern nello spazio delle soluzioni che è presente, esattamente o con dierenze per una o più basi, anche nella se-quenza di input. Il vantaggio di questo metodo è che garantisce di trovare il pattern migliore. D'altro canto questo approccio è esponenziale nel tem-po rispetto a l ed il problema diventa irrisolubile anche per moderati valori di l [Tom99]. Questo semplice metodo è infatti limitato a motivi corti che raramente superano una decina di basi.

1.6.2 Approccio sample driven

Per superare il problema dell'eccessivo tempo necessario per l'approccio PD, Waterman[MWG84] e Galas[DGW85] suggeriscono un algoritmo che riduce signicativamente il tempo richiesto dall'approccio PD. La maggior parte dei 4l _{pattern esaminati nell'approccio PD potrebbero anche non essere}

con-siderati visto che nè questi pattern nè loro simili compaiono nella sequenza di input. Da ciò segue che, essendo il tempo speso per esaminare tali pat-tern molto grande nell'approccio PD, si potrebbe velocizzare signicativa-mente il processo eliminandoli dallo spazio di ricerca. Basandosi su questa osservazione venne sviluppato un algoritmo, detto [Esk02] Sample Driven Approach, che esplora solo le sottostringhe di lunghezza ssa l presenti

ef-1.7. OBBIETTIVI DELLA TESI E RISULTATI RAGGIUNTI 19

fettivamente nella sequenza di input e quelle ad esse simili. L'approccio adottato in questa tesi è di questo tipo.

1.7 Obbiettivi della tesi e risultati raggiunti

L'obbiettivo di questa tesi è quello di concepire un nuovo metodo per indi-cizzare un testo, o un insieme di testi, al ne di individuarvi ecientemente pattern frequenti (o comuni ai vari testi) approssimati. Ci siamo focalizzati sull'approssimazione realizzata utilizzando il simbolo wild card per la de-scrizione del motivo ricorrente, e abbiamo analizzato la natura combinatoria dell'insieme di pattern di lunghezza ssa con tutti i possibili numeri e po-sizioni dei simboli wild card. Il nostro primo risultato è stato la denizione di una nuova relazione di equivalenza all'interno di questo insieme, che mascheri la degenerazione dei motivi; come mostriamo nel Capitolo 2, tale degener-azione è in generale motivo di grave inecienza. Abbiamo successivamente strutturato le varie relazioni di equivalenza introducendo una relazione di or-dine parziale tra motivi della stessa lunghezza aventi wild card in posizioni annidate, e l'abbiamo caratterizzata utilizzando il concetto di albero binomi-ale descritto nel Capitolo 3, associando un nodo di tbinomi-ale albero ad un insieme di posizioni dei simboli wild card. Abbiamo inoltre mostrato (Capitolo 4) come un indice di un tipo di pattern relativo ad un certo nodo possa essere ecientemente ricavato dall'indice del pattern corrispondente al nodo padre nell'albero binomiale. Tra questi indici, ovvero tra i nodi dell'albero, abbi-amo eettuato una classicazione e denito un concetto di base generatrice di alberi o indici corrispondente ad un sottoinsieme dei nodi dell'albero bino-miale, che porta alla riduzione dello spazio delle combinazioni del problema di indicizzare il testo per trovare tutti i pattern aventi un certo numero di wild card. Questo ci ha permesso di concepire un algoritmo eciente per

la generazione gerarchica degli alberi per i motivi con k errori, e dunque ad un nuovo approccio combinatorio per la risoluzione eciente del problema dell'inferenza di motivi con wildcard.

Il problema dell'inferenza di motivi di lunghezza ssa con wild card trova applicazione nella ricerca, in sequenze biologiche, dei binding site dei fattori di trascrizione dei geni. Date le dimensioni dei dati di ingresso in problemi di questo tipo, appare molto promettente un approccio basato sulla costruzione eciente di un indice.

Capitolo 2

Relazioni di somiglianza e

algoritmi

Gli alberi dei sussi rappresentano un'eciente struttura di indicizzazione per la ricerca di motivi esatti e per la ricerca di pattern con wildcard [Gus97]. Il loro impiego si estende anche a problemi come l'inferenza dei motivi con i modelli in [Sag98] e, per quanto ci riguarda, all'inferenza di motivi con wildcard nell'albero dei sussi stesso. In questo capitolo si discutono le principali nozioni sugli alberi dei sussi, gli algoritmi di costruzione più conosciuti ed ecienti e la dualità tra il concetto di distanza e la somiglianza tra sequenze. Ci soermeremo, in particolare, sul modello di distanza di Edit e sulla distanza di Hamming. Si metterà in evidenza la somiglianza espressa come relazione tra parole o posizioni e dopo aver introdotto gli algoritmi combinatori per le principali relazioni, discuteremo la nostra idea di relazione e il suo rapporto con gli alberi.

2.1 Denizioni preliminari

Sia Σ un alfabeto nito di caratteri. Sia ε la stringa vuota, Σ∗ _{l'insieme delle}

stringhe su Σ e Σ+ _{quelle non nulle di Σ}∗_{\{ε}. Se s = uwv con u, w, v ∈ Σ}∗

allora u è il presso di s, w è una parola di s e v è il susso di s. Una parola

w_{di s è ramicata a sinistra (o a destra) se esistono in s due caratteri distinti} a, b ∈ Σtali che wa e wb (oppure aw e bw se ramicata a destra) sono parole di s. Un presso o un susso sono annidati in s se esiste un altro presso o susso in s che lo contiene.

Lungo il corso della tesi scriveremo i termini sequenza o stringa riferendoci allo stesso oggetto.

Adesso si riportano alcune denizioni di alberi su stringhe.

Denitione 1 (Σ+_{-albero). Un Σ}+_{-albero T in [GK97] è un albero radicato} con le etichette degli archi in Σ+ _{e per ogni carattere a ∈ Σ ogni nodo f di}

T ha al più un arco etichettato f → faw 0_.

Denotiamo con path(f) la stringa ottenuta con la concatenazione delle etichette degli archi del percorso che va dalla radice di T no al nodo f. Se path(f) = w allora w è unica e scriviamo il nodo f come f. Inne, indichiamo con Tw il sottoalbero di T che ha w come radice.

Denitione 2 (Occorrenza di una parola in un Σ+_{-albero). In [GK97], dato}

un Σ+_{-albero T , si dice che una stringa w occorre in T se e solo se esiste un} nodo wv per qualche stringa v ∈ Σ∗_.

Le parole in un Σ+_{-albero sono rappresentate come coppie.}

Denitione 3 (Rappresentazione delle parole in un Σ+_{-albero). In [GK97],}

dato un Σ+_{-albero T , l'insieme word(T) è l'insieme di tutte le stringhe in}

2.1. DEFINIZIONI PRELIMINARI 23

referenza per s rispetto a T , se b è un nodo in T e s = bu. La coppia di referenza è detta canonica se b è il più lungo presso di s in T . La coppia di referenza canonica per una parola s ∈ word(T ) è unica.

Una coppia canonica di referenza (b,ε) è detta esplicita perchè fa rifer-imento al nodo b in T , mentre se espressa (b,aw) è detta implicita perchè non fa riferimento ad un nodo ma ad una stringa che nisce all'interno di un arco bawv→ bawv_.

Deniamo un Σ+_{-albero atomico o compatto nel modo seguente.}

Denitione 4 (Σ+_{-albero atomico e compatto). In [GK97], un Σ}+_{-albero T} è detto atomico se ogni arco è marcato con un singolo carattere. T è, invece, compatto se le etichette degli archi possono essere anche stringhe.

Un Σ+_{-albero atomico è chiamato anche Trie. Vediamo un esempio di}

albero atomico e compatto dei sussi.

Esempio 2. Consideriamo la stringa s = AAAAT T . La Figura 2.1 mostra gli alberi atw e ctw per s.

T A A T T T T T A A T T 5 T T 4 3 6 2 1 (a) ast TT 4 A 3 2 ATT TT TT 1 A T A 6 5 T (b) cst

Figura 2.1: Albero atomico e albero compatto dei sussi per la stringa AAAATT.

Un Σ+_{-albero compatto dei sussi di un testo s è anche chiamato albero} dei sussi di s.

Denitione 5 (Albero dei sussi). Un Albero dei sussi per una stringa

s ∈ Σ+ _{è un Σ}+_{-albero compatto T , tale che word(T)={v | v è un susso di} s}

Mostriamo un esempio più dettagliato di un albero dei sussi per una stringa s.

Esempio 3. Consideriamo la stringa s = AAAAT T , la Figura 2.2 tutti i sussi di s e l'albero dei sussi di s.

Posizione dei sussi in s word(T)

1 AAAATT 2 AAATT 3 _AATT 4 ATT 5 TT 6 _T

(a) Sussi della stringa AAAATT

TT 4 A 3 2 ATT TT TT 1 A T A 6 5 T

(b) Albero dei sussi per la stringa AAAATT

Figura 2.2: Insieme dei sussi e l'albero per i sussi di s .

Un albero dei sussi è profondo al più n, ma se si è interessati a pa-role lunghe L, allora ha senso troncare l'albero alla profondità L, poichè è suciente. Lo stesso vale per un Σ+_{-albero atomico dei sussi di s.}

Denitione 6 (Σ+_{-albero atomico dei sussi troncato). Dati una sequenza}

di caratteri s ∈ Σn_{, una lunghezza 1 ≤ L ≤ n, un Σ}+_{-albero atomico dei}

sussi AT è detto troncato all'altezza L se AT è tale che word(AT)={v | vu è un susso di s e |v| ≤ L}.

La denizione appena vista riguarda l'albero atomico con soli caratteri solidi; noi siamo interessati a un albero atomico che abbia anche caratteri wildcard.

2.1. DEFINIZIONI PRELIMINARI 25 Denitione 7 (Σ+_{-albero atomico dei sussi troncato con wildcard). Dati}

una sequenza di caratteri s ∈ Σn_{, una lunghezza 1 ≤ L ≤ n, un insieme}

di posizioni l ⊆ {0, · · · , L − 1}, un Σ+_{-albero ATW(s, L, l) è un Σ}+_-albero atomico dei sussi troncato all'altezza L con wildcard in l se ATW(s, L, l) è un Σ+_{-albero atomico dei sussi troncato all'altezza L e v}

j = ◦ per ogni j ∈ {0, · · · , L − 1} \ l.

In sostanza ogni parola di ATW(s, L, l) ha il simbolo wildcard nelle po-sizioni non contenute in l.

Esempio 4. Consideriamo ancora la stringa s = AAAAT T , l'altezza L = 3 e l'insieme delle posizioni l = {2, 0} in questo esempio mostriamo l'albero troncato all'altezza L e l'albero troncato all'altezza L con wildcard in l.

A A T T T A 5 T T 4 6 1,2 3

(a) Albero troncato all'altezza 3

A 5 T 6 ° T A 3,4 _1,2 °

(b) Albero troncato all'altezza 3 con wildcard

Le due denizioni valgono anche se il Σ+_{-albero è compatto; in questo} caso, però, non è detto che un presso di lunghezza L sia esplicito nell'albero dei sussi, quindi il troncamento è un pò più laborioso, occorre creare infatti, un nodo nell'albero troncato che esprima i pressi impliciti di lunghezza L.

Scriviamo ast(s) per indicare l'albero atomico dei sussi di una stringa

s_{, cst(s) per riferirci all'albero compatto dei sussi di s, ATW(s, L, l) e}

dei sussi troncato all'altezza L con wildcard nelle posizioni di L che non compaiono in l.

Nel corso della tesi useremo per semplicita solo gli alberi AT W .

Raniamo la nostra notazione indicando con foglie(ATW(s,L,l)) l'in-sieme delle foglie dell'albero ATW(s,L,l).

Vediamo adesso alcuni concetti specici che caratterizzano la costruzione degli alberi dei sussi.

Gli Open edges, o archi aperti, sono stati introdotti in [Ukk95] e sono una particolare rappresentazione delle etichette degli archi che conducono da un nodo ad una foglia di un albero dei sussi. La rappresentazione delle etichette degli archi delle foglie è una coppia, della forma (i,|s|), dove

i rappresenta l'indice di un susso della stringa s di lunghezza n e |s| il numero di caratteri della stringa s di lunghezza n. Questo signica che se il susso attuale si estende verso destra nella costruzione, l'etichetta della foglia cresce di conseguenza in forma implicita e la foglia rappresenta ancora una volta un susso esteso di s.

Le nozioni di susso e presso attivo rappresentano un altro concetto di fondamentale importanza per l'ecienza degli algoritmi di costruzione che vedremo nella prossima sezione.

Denitione 8 (Sussi e Pressi Attivi). In [GK97], un susso di s è un susso attivo , denotato con α(s), se esso è il più lungo susso annidato in

s. Un presso di s è un presso attivo , denotato con α−1_{(s), se esso è il}

più lungo presso annidato in s.

Se la coppia (u,v) rappresenta il susso attivo dell'albero cst(s), allora un eventuale estensione verso destra di s nella costruzione e il conseguente aggiornamento della struttura dell'albero parte proprio da (u,v). In maniera

2.1. DEFINIZIONI PRELIMINARI 27

analoga, si può dire che un presso attivo è il punto di partenza per un eventuale estensione verso sinistra della stringa s.

Esempio 5. Consideriamo la stringa s = AAAAT T e creiamo una tabella che mostra la sequenza dei sussi di s in ordine crescente e decrescente rispettivamente, evidenziando in grassetto i pressi e i sussi attivi per s.

Sussi di lunghezza crescente Sussi di lunghezza decrescente

A AATTAA AA ATTAA TAA TTAA TTAA TAA ATTAA AA AATTAA A

In [E.M76], McCreight usa le funzioni Head e Tail per distinguere il presso attivo dal resto.

Denitione 9 (Head e Tail). Sia s = ut per qualche stringa u, t ∈ Σ∗_,

head(t) è il più grande presso x di t tale che x è un susso annidato di

ux_{. Tail(t) è denito da t = Head(t)T ail(t).}

Se un susso t di s è annidato non ha una foglia t nell'albero dei sussi di s. Se si vuole che ad ogni susso dell'albero dei sussi T di s corrisponda una foglia non devono esserci sussi annidati. Per questo si aggiunge alla stringa s il carattere speciale $ che non occorre in t, chiamato sentinella.

Spesso, assumere la non esistenza della sentinella semplica molto le dimostrazioni e le costruzioni, quindi da questo momento in poi escludi-amo la sentinella dalla nostra trattazione salvo dei casi in cui lo diremo esplicitamente.

L'inserzione in tempo costante di un susso in un albero dei sussi di una stringa s è una delle operazioni chiave dei principali algoritmi di costruzione

degli alberi dei sussi. I link dei sussi, introdotti in [Ukk95], sono archi aggiuntivi di un generico Σ-albero, deniti come segue.

Denitione 10 (Link dei sussi). Consideriamo un Σ-albero T , sia a ∈ Σ,

w, v ∈ Σ∗_{, aw un nodo in T e v il più lungo susso di w tale che v sia}

anch'esso un nodo in T . Un arco non etichettato aw → v è un Link di susso. Un link di susso aw → w è detto atomico.

In questo esempio mostriamo i link dei sussi per l'albero cst(AAAAT T ).

Esempio 6. I link dei sussi dell'albero sono rappresentati con le frecce di colore rosso, le altre sono i link dei sussi presenti lungo la costruzione.

TT 4 A 3 2 ATT TT TT 1 A T A 6 5 T

In [GK97] gli autori dimostrano che i link dei sussi in un ast(s) e in un

cst(s$)per una stringa s ∈ Σ+ _{sono tutti atomici. La verica per un ast(s)} è semplice perchè tutti i nodi sono espliciti, in un cst(s$) i nodi non sono tutti espliciti ma se aw è un susso di s$, allora poichè ogni susso ha un nodo esplicito nell'albero dei sussi, essendo w un susso w sarà un nodo dell'albero dei sussi di s$.

2.2 Costruzione degli alberi dei sussi

In questa sezione parliamo dei due principali algoritmi di costruzione di un

2.2. COSTRUZIONE DEGLI ALBERI DEI SUFFISSI 29

[Ukk95] e quello di McCreight [E.M76], cercando di evidenziare i loro aspet-ti comuni, le dierenze e le novità introdotte. Nel corso della discussione chiameremo gli algoritmi di Ukkonen e di McCreight rispettivamente Ukk e Mcc.

2.2.1 L'algoritmo di costruzione di Ukkonen

Ukk esamina il testo s da sinistra verso destra, carattere dopo carattere, e in-crementalmente costruisce un albero che ad ogni iterazione è l'albero dei su-issi per la stringa presso di s letta no a quel momento. Durante la proce-dura di lettura dei caratteri di s, alcuni open edges crescono implicitamente, altri archi vengono divisi e altri ancora vengono aggiunti esplicitamente.

Analizziamo un caso reale, il passaggio dall'albero cst(p) a cst(pa), dove

pè uno dei pressi di s e a è il prossimo carattere di s a essere letto. Sia ta un susso di pa; i casi che possono capitare sono tre:

1. t non è un susso annidato di p, allora il nodo t è già una foglia per l'albero cst(p). Quindi |ta| > |α(p)a|. In tal caso il susso ta mantiene in cst(pa) la stessa foglia per l'albero cst(p), il corrispondente arco aperto è esteso implicitamente.

2. ta_{forma un nuovo susso. Cioè |α(p)a| ≥ |ta| > α(pa) e, in tal caso,}

si introduce la nuova foglia ta e si aggiorna l'insieme dei link dei sussi per la nuova foglia.

3. |α(pa)| ≥ |ta|_{. In questa ipotesi ta occorre già in cst(p) quindi ta è}

implicito.

Ogni susso in Ukk è rappresentato da una coppia di referenza canonica calcolata attraverso il link dei sussi.

La procedura di costruzione si articola in n chiamate successive di una funzione che riceve in input quattro parametri:

• cst(p) = T.

• _{l'insieme L dei link dei sussi per T .}

• la coppia di referenza canonica (b, u) di α(p).

• _{la posizione i tale che p = s1}· · · s_{i−1 dove si è il prossimo carattere di} s_{da leggere.}

è restituisce cst(psi).

2.2.2 L'algoritmo di costruzione di McCreight

Sul piano tecnico, ciò che distingue Ukk da Mcc è il modo con cui avviene, la lettura dei caratteri e l'attraversamento dei link dei sussi. Mcc inserisce interi sussi di s$ in un albero che inizialmente è vuoto; partendo dal susso più lungo di s$ no al più corto. Il metodo non è On-Line come per Ukk, gli alberi intermedi non sono alberi dei sussi. Per ogni susso t di s$, T (t) denota il Σ-albero dei sussi costruito per sussi di lunghezza maggiore di t. La sequenza prodotta è, dunque, cst(ε), T (s1· · · sn), T (s2· · · sn), · · · , T (sn−1sn), T (n) = cst(s)_{. Solo il primo e l'ultimo albero sono alberi dei sussi, mentre}

gli alberi intermedi sono Σ-alberi.

Il primo passo dell'algoritmo è banale T (s) = T (s1· · · sn$)è costruito a

partire da cst(ε) inserendo il più lungo susso di s$. T (s$) è il Σ-albero con un solo arco root→ ss$ . Consideriamo adesso un susso di s at, supponiamo che x = Head(at). Il passaggio da T (at) a T (t) si articola in tre fasi: nella prima, si calcola la coppia di referenza per y = Head(t) e T ail(t) a partire dalla coppia per x = Head(at) e T ail(at) seguendo il link dei sussi

2.3. DISTANZA E SOMIGLIANZA 31 x → y_{, nella seconda, si esamina il sottoalbero discendente da y per estendere}

eventualmente il presso attivo, nella terza, si procede con la ramicazione, se necessaria, o con l'inserzione di una foglia etichettata con T ail(t).

Entrambi gli algoritmi di costruzione di un albero dei sussi per una stringa s hanno complessità lineare in tempo e spazio. Per questo motivo sono gli algoritmi di riferimento nel calcolo degli alberi dei sussi.

2.3 Distanza e Somiglianza

L'approssimazione, la distanza e la somiglianza tra sequenze sono stretta-mente legate tra loro. Il grado di somiglianza tra due stringhe si quantica con la misura di una distanza. La distanza più opportuna da utilizzare dipende dalla specica applicazione. Il modello di distanza più diuso, nel confronto tra stringhe, è il modello di distanza di Edit. Essa misura la distan-za tra stringhe in termini di operazioni di Edit, cioè, cancellazioni, inserzioni e sostituzioni di singoli caratteri. La distanza tra due stringhe si calcola determinando la sequenza di operazioni di edit che trasformano una stringa nell'altra che, una volta stabilito il costo di ogni operazione, minimizza la somma dei costi delle operazioni coinvolte. Tale sequenza può essere calco-lata in tempo proporzionale al prodotto delle lunghezze delle due stringhe, usando la tecnica nota come programmazione dinamica. La distanza di edit, che vedremo in dettaglio nella Sezione 2.3.1, è una misura di somiglianza lo-cale, in quanto il costo del confronto è altamente dipendente dalla posizioni che le singole lettere occupano nelle rispettive stringhe. Esistono anche al-tri modelli, tra i quali, il modello maximal matches e il modello a q-gram. L'idea del modello maximal matches è di contare il numero minimo di occor-renze di caratteri in una stringa tale che se questi caratteri sono cancellati, le sottostringhe rimanenti sono tutte sottostringhe dell'altra stringa. In questo

modo, stringhe con lunghe sottostringhe comuni hanno una distanza piccola. L'idea del modello q-gram è di contare il numero di occorrenze di comuni q-grams nelle due stringhe: stringhe con molti q-gram comuni hanno una distanza piccola. Un aspetto molto interessante di questi due modelli, come vedremo nella Sezione 2.3.2 anche per la distanza di Hamming, è che la dis-tanza tra due stringhe è calcolata in tempo proporzionale alla somma delle lunghezze delle due stringhe [Gie02]. Quando si confrontano sequenze bio-logiche, il costo computazionale della distanza di edit è spesso troppo alto, e l'ordine dei caratteri della sequenza è importante.

In generale, una misura di somiglianza è una funzione che associa un val-ore numerico ad una coppia di sequenze. Un valval-ore più grande non implica necessariamente una maggiore somiglianza tra due sequenze. La nozione di distanza è in qualche modo duale a quella di somiglianza. Essa tratta le sequenze come punti in uno spazio metrico. Una distanza è una funzione che associa, come per la somiglianza, un valore numerico a una coppia di sequenze, ma con la dierenza che a un valore più grande di distanza cor-risponde un valore più piccolo di somiglianza, e viceversa. La nozione di distanza soddisfa gli assiomi matematici sulle metriche. Una distanza è una metrica per delle sequenze se e solo se sono soddisfatte le proprietà:

1. d(u, v) ≥ 0.

2. d(u, v) = 0se u=v.

3. d(u, v) = d(v, u).

4. d(u, v) ≤ d(u, w) + d(w, v)_{Disuguaglianza triangolare.}

2.3.1 Il modello di distanza di Edit

2.3. DISTANZA E SOMIGLIANZA 33 Denitione 11. Un operazione di edit è una coppia (α, β) ∈ (Σ ∪ {²}) × (Σ ∪ {²})\{(², ²)}_.

Un operazione di edit (α, β) è di solito scritta come α → β. Questo riette la vista operazionale che considera le operazioni di edit come regole di riscrittura che trasformano una stringa di partenza in una stringa obiettivo, passo per passo. In particolare, ci sono quattro tipi di operazioni di edit:

• α → α che denota la corrispondenza di un carattere α, • α → ²che denota la cancellazione di un carattere α, • ² → β _{che denota l'inserzione di un carattere β,}

• α → β che denota la sostituzione di un carattere α con un carattere β. Nel confronto tra stringhe la misura di quanto le stringhe sono distanti è importante, ma spesso l'interesse è analizzare quali dierenze distinguono le due stringhe. Il modo più diretto per stabilire le dierenze tra due stringhe è l'allineamento.

Denitione 12. Un allineamento A di u, v ∈ Σ∗ _{è una sequenza}

(α1→ β1, α2 → β2, · · · , αh→ βh)

di operazioni di edit tali che u = α1· · · α_{h e v = β1}· · · β_h.

La nozione di allineamento ottimo richiede una certa funzione di score, ovvero una funzione di costo come segue:

Denitione 13. Un funzione di costo δ assegna ad ogni operazione di edit

α → β_{, α 6= β un costo reale positivo δ(α → β). Il costo δ(α → α) di}

una operazione di edit α → α è 0. Se δ(α → β) = δ(β → α) per tutte le operazioni α → β e β → α, allora δ è simmetrica. Il costo δ(A) di un

allineamento A = (α1 → β₁, α₂ → β₂, · · · , α_h → β_h) _{è la somma dei costi} delle operazioni di edit in A. Più precisamente,

δ(A) = h X i=1 δ(αi→ βi) .

Mostriamo un esempio di allineamento tra due stringhe.

Esempio 7. Date due stringhe u = AAAAT T e v = AT AT AT . l'allinea-mento A = {A → A, T → A, A → A, A → ε, T → T, ε → A, T → T }. Se prendiamo per semplicità la funzione di costo:

δ =      0 se α, β ∈ Σ e α = β 1 _altrimenti Il costo dell'allineamento è: δ(A) =Ph_i=1δ(αi → βi) = 3

L'allineamento, come si può facilmente vericare, trasforma eettiva-mente la stringa u nella stringa v.

Denitione 14. La distanza di edit tra due stringhe u e v, denotata con

distL(u, v), è il minimo costo per un allineamento di u e v. Cioè, distL(u, v) =

min{δ(A)|A è un allineamento di u e v}.

Un allineamento A è ottimo se δ(A) = distL(u, v). 2.3.2 Il modello di distanza di Hamming

La distanza di Hamming è la più semplice delle nozioni di distanza tra se-quenze. Introdotta in [Ham50], date due sequenze della stessa lunghezza, essa conta il numero minimo di sostituzioni per trasformare una stringa nel-l'altra. In molti casi la misura di Hamming è molto utile, ma in generale

2.3. DISTANZA E SOMIGLIANZA 35

non è abbastanza essibile. Prima di tutto, le sequenze potrebbero avere dierente lunghezza. Secondo, non c'è generalmente corrispondenza ssata tra le posizioni dei loro caratteri.

La natura del modello non presuppone un allineamento. L'allineamento si forma con lo slittamento di una sequenza rispetto all'altra, la distanza di Hamming conta solo le dierenze tra i singoli caratteri delle sequenze. Ques-ta caratteristica rappresenQues-ta sia la forza che il limite di questo modello. Un caso di inecienza è quando la semplice cancellazione di un carattere in una delle due sequenze a confronto renderebbe le due sequenze identiche. Lo slittamento di una sola posizione porta ad un valore esagerato di distanza di Hamming quando in realtà le sequenze sono identiche senza lo slittamen-to. L'Esempio 8 mostra un caso reale in cui la distanza di Hamming non è abbastanza essibile.

Esempio 8. Date due sequenze di lunghezza sei u = AAT T AA e v =

AT T AAt, la cancellazione del carattere A nella seconda posizione renderebbe le due sequenze uguali, ma il valore di distanza di Hamming è tre.

Come per il modello di edit, la funzione di costo per la distanza di Hamming, denotata con γ(a, b) per a, b ∈ Σ, è: γ(a, b) =

     0 _{se a = b} 1 _{se a 6= b}

Consideriamo adesso, la denizione e un esempio di misura della distanza tra due sequenze.

Denitione 15. Date due sequenze u, v ∈ Σ∗_{, con |u| = |v|, la}

distan-za di Hamming tra u e v , denotata con distH(u, v), è il minimo numero

di sostituzioni per trasformare u in v. Alternativamente, distH(u, v) =

P_|u|

i=1γ(ui, vi).

In altre parole, calcolare la distanza di Hamming tra due sequenze della stessa lunghezza è come contare, per ogni posizione, se il carattere in quella

posizione per entrambe le sequenze è lo stesso. Se così fosse si passa alla posizione successiva e si rifà il confronto, altrimenti, è diverso, quindi la distanza si incrementa di uno e solo dopo aver incrementato il valore della distanza si passa alla posizione successiva. Il costo del calcolo della distanza di Hamming tra due sequenze è la somma delle lunghezze delle sequenze stesse. L'Esempio 9 mostra il calcolo della distanza di Hamming tra due sequenze della stessa lunghezza.

Esempio 9. Date due sequenze di lunghezza sei u = AAT T AA e v =

ACGCAA, il valore distH(u, v) =

P_|u|

i=1γ(ui, vi) = 3 nelle posizioni 2,3,4.

Il modello di distanza di Hamming rappresenta la metrica di base su cui si basa la relazione di somiglianza che proporremo nella prossima sezione.

2.3.3 Nozioni di somiglianza

La somiglianza tra due oggetti rappresenta una relazione tra gli oggetti in questione. Ogni relazione permette di raggruppare gruppi di oggetti. La somiglianza permette di creare, quindi, dei gruppi di oggetti simili. Gli oggetti della somiglianza, che intendiamo approfondire, sono le sequenze di caratteri. In [SW], si indagano diverse relazioni di somiglianza, come ve-dremo in dettaglio in questa sezione; ad esempio, la relazione identità, adot-tata da Karp, Miller e Rosenberg in [KMR72], raggruppa classi di ripetizioni identiche sparse in una stringa, in [SVC95], gli autori usano una relazione non transitiva tra le lettere dell'alfabeto per creare gruppi di ripetizioni, chia-mati cricca, in [Sag98], Sagot usa invece, una relazione con errore basata sul concetto di modello per gruppi di ripetizioni con errori. La nostra idea è, invece, la denizione di una nuova relazione con dierenze. In particolare, la relazione proposta è una relazione di equivalenza che raggruppa classi di

2.3. DISTANZA E SOMIGLIANZA 37

oggetti con dierenze. Dimostreremo che una nozione di somiglianza costru-ita su una relazione non transitiva, crea il fenomeno della degenerazione (una singola parola appartiene a più insiemi) e una maggiore dicoltà nella ver-ica e nella riscrittura di un generico indice di susso appartenente ad un insieme.

Identità

L'identità è una relazione di equivalenza tra oggetti deniti su un alfabeto Σ_{. Si denisce una relazione di identità EL tra parole, in funzione di una} relazione di identità tra singole lettere di Σ.

Denitione 16 (Relazione EL). Data una stringa s ∈ Σn e due posizioni

in s tali che 0 ≤ i, j ≤ n − L + 1, allora i EL j se e solo se si+l E sj+l

Per ogni l tale che 0 ≤ l ≤ L − 1.

Due posizioni i e j sono in relazione di equivalenza EL se e solo se le

parole di lunghezza L in s che iniziano alle posizioni i e j sono

perfetta-mente identiche. Ogni classe di EL di cardinalità almeno due rappresenta

un insieme di parole ripetute esattamente in s.

Se tutte le parole di una classe per la relazione ELsono identiche, quindi,

la classe contiene tutte e sole le parole uguali, l'identicazione della classe a cui una posizione o una parola appartiene è immediata leggendo i caratteri che compongono la parola stessa.

Relazioni Non-Transitive

Trattando, per esempio, sequenze biologiche si deve sempre tenere in mente che dietro ogni simbolo, nucleotidi per il DNA e aminoacidi per le proteine, vi sono oggetti complessi con proprietà sico-chimiche speciche, ad esem-pio, polarità, dimensione, livello di acidità, ecc. Alcune di queste proprietà

possono essere condivise da due o più di questi oggetti. In [SVC95], hanno pensato di denire una relazione tra i simboli dell'alfabeto, che non sia nec-essariamente una relazione di equivalenza in quanto riessiva e simmetrica, ma non transitiva.

La relazione viene rappresentata con un grafo in cui i nodi sono tutti i simboli dell'alfabeto Σ e dove l'arco tra due nodi evidenzia la condivisione di sucienti caratteristiche sico-chimiche tra gli elementi biologici.

Come nella precedente sottosezione, è stata denita la relazione RL tra

parole lunghe L di s come funzione della relazione R tra i singoli componenti dell'alfabeto.

Denitione 17 (Relazione RL). Data una stringa s ∈ Σn e due posizioni

in s tali che 0 ≤ i, j ≤ n − L + 1, allora i RL j se e solo se si+l R sj+l

per ogni l tale che 0 ≤ l ≤ L − 1.

Per la relazione RLgli insiemi di oggetti possono non essere più classi di

equivalenza, per via della non transitività della relazione. Tali insiemi sono conosciuti come insiemi cricca della relazione non transitiva. Una cricca è denita nel modo seguente.

Denitione 18 (Cricca su parole di una relazione R). Dato un alfabeto Σ e una relazione non transitiva R su Σ, un insieme C di elementi di Σ è una cricca della relazione R se α R β per ogni α, β ∈ C. Se C è una cricca e C ∪ {γ} non è una cricca per ogni γ ∈ Σ\C, allora C è detto cricca massimale.

La nozione di cricca può essere denita sulle parole, ma anche sulle posizioni.

Denitione 19 (Cricca di posizioni di una relazione R). Data una stringa

s ∈ Σn_{, un insieme C}

2.3. DISTANZA E SOMIGLIANZA 39 i R_L j _{per ogni i, j ∈ CL. Se CL è una cricca e CL}∪ {l} _{non è una cricca}

per ogni l ∈ [1 · · · n]\CL, allora CL è detto cricca massimale di RL.

La cricca massimale di RL ci ore un secondo modo per stabilire una

relazione di somiglianza tra parole di lunghezza L in una stringa.

A dierenza di quanto visto per la relazione identità, una posizione, ovvero una parola, può appartenere a più di un insieme cricca di s. Se una parola si trova in relazione con due parole diverse che tra loro non sono in relazione allora la parola in esame farà parte di due insiemi cricca distinti. Il numero di cricca di s a cui una parola appartiene è chiamato grado di degenerazione di una posizione o di una parola.

Nella prossima sezione si approfondirà la degenerazione e si mostrerà come la non transitività di una relazione aggiunge complessità algoritmica alla ricerca di oggetti simili in una sequenza.

Relazioni con dierenze

Le relazioni, identità e non transitiva, rientrano nella categoria delle relazioni esatte. Le relazioni esatte sono quelle che non considerano errori o dieren-ze tra gli oggetti. In questa sezione, si introduce una categoria di relazioni che considerano la somiglianza con dierenze o errori. Le relazioni con dif-ferenze si basano, generalmente, sulla distanza di Hamming, le relazioni con errori usano, invece generalmente, la distanza di Edit. In questa sezione si assumono solo relazioni che usano la distanza di Hamming.

In concordanza con le denizioni di relazione date in precedenza, si tenta di denire la relazione con dierenze indotta dalla distanza di Hamming, tra due parole di lunghezza L in una stringa s, o tra due posizioni i e j in s, nel modo seguente:

Denitione 20 (Primo tentativo di denizione della relazione HL). Data

una stringa s ∈ Σn_{, una lunghezza k e due posizioni in s tali che 0 ≤ i, j ≤} n − L + 1, allora i HL j se e solo se distH(si· · · si+L−1, sj· · · sj+L−1) ≤ k.

Calcolare HLnon è semplice come calcolare ELo RL: sebbene le denizioni

16 e 17 coinvolgano coppie di posizioni nella stringa s, è possibile riscrivere le denizioni in modo che, data una posizione i in s e una lunghezza k, risulta immediato identicare la classe o le cricche di s a cui i appartiene, leggendo semplicemente i suoi componenti si· · · si+L−1.

Nel caso dell'identità la posizione i appartiene alla classe con etichet-ta si· · · si+L−1. Mentre per la relazione non transitiva tra i simboli di Σ,

chiamiamo C l'insieme delle cricche di R e denotiamo con criccaR(α) le

cricche di R a cui il carattere α appartiene. La posizione i appartiene alle cricche massimali di RL con etichetta calcolabile dall'espressione regolare criccaR(si) · · · criccaR(si+L−1). La dierenza sostanziale tra le due relazioni

stà nella verica della massimalità dell'insieme a cui l'indice o la parola i appartiene, che, per la relazione non transitiva, deve essere vericata, men-tre per la relazione identità ciò non è necessario in quanto ogni classe è massimale.

La riscrittura e la verica di una parola o di una posizione non sono così semplici nel caso della Denizione 20 di HL. Se volessimo costruire la nozione

di somiglianza su quella di cricca di HLdovremmo confrontare i componenti si· · · si+L−1 con i componenti delle parole di tutte le cricche di HL. Per

questo motivo in [SW] si riscrive la denizione di HL come relazione non

transitiva con errori o con dierenze basata sul concetto di modello. In tal modo, si propone un modo per avere una riscrittura e una verica immediata di una parola. La riscrittura e la verica è fatta confrontando le lettere che compongono la parola considerata con tutti i modelli per s. La denizione

2.3. DISTANZA E SOMIGLIANZA 41

di modello non ha, però, eliminato la degenerazione delle parole.

In [SW] viene proposta la seguente denizione di relazione basata sul concetto di modello sulle parole di una sequenza s.

Denitione 21 (Relazione HLcon la nozione di modello per le parole).

Da-ta una stringa s ∈ Σn_{, una lunghezza k e due posizioni in s tali che 0 ≤ i, j ≤} n−L+1, allora i HLj se e solo se ∃m ∈ ΣL tale che distH(m, si· · · si+L−1) ≤ k e distH(m, sj· · · sj+L−1) ≤ k.

In [SW], dimostrano con un controesempio che gli insiemi di parole

costruiti con la relazione HL basata sui modelli non sono nè classi e nè

cricche, rappresentano degli insiemi di parole in relazione HLcon il modello

che etichetta l'insieme. Tali insiemi sono denotati come group di s.

La denizione di relazione HLcon la nozione di modello è analoga per le

posizioni in s.

Denitione 22 (Relazione HL con la nozione di modello per le posizioni).

Un insieme SL di posizioni in s rappresenta un insieme di parole in s di

lunghezza L tutte tra loro simili se e solo se esiste almeno una stringa m ∈ ΣL _{tale che, per ogni i ∈ S}

L, distH(m, si· · · si+L−1) ≤ k e, per ogni j ∈

[1 · ·n]\SL, distH(m, sj· · · sj+L−1) > k

Data una posizione i di s e una lunghezza L, la denizione della

re-lazione HL permette di ottenere le etichette dei group di s a cui i

ap-partiene confrontando la parola corrispondente a i in s con tutti i modelli

m ∈ ΣL tali che distH(m, si· · · si+L−1) ≤ k .

In [SW], si deniscono modelli le etichette di questi gruppi. L'etichetta di una cricca massimale, di una classe o di un modello, serve a dare un nome e una facile identicazione a tutti gli oggetti simili tra loro. Chiamiamo motivo o pattern questa etichetta.

Denire una relazione tra parole o posizioni di una stringa s serve proprio per raggruppare insieme sotto un'unica (o poche) etichetta (etichette), tutte le parole tra loro simili secondo una relazione.

La novità apportata dalla relazione appena introdotta e dal concetto di modello, sta nella conciliazione, tra una relazione non transitiva su un alfabeto e la possibilità di errori in un'unica denizione che ammette una facile verica e riscrittura di una qualsiasi parola o posizione in s. Un modello non è necessariamente una parola inclusa in s. Come mostrato nel prossimo esempio.

Esempio 10. Consideriamo la stringa s = AT AT ACAA, un errore k = 1, il modello m = ACAT è un modello per la relazione H4, è etichetta di un group di s che ha le sottostringhe AT AT e ACAA in s, ma non appartiene a s.

2.4 Algoritmi per le relazioni

In questa sezione trattiamo alcune classi di algoritmi combinatori che ri-solvono problemi inerenti l'individuazione delle ripetizioni. Ogni classe di algoritmi crea gli insiemi di occorrenze, basandosi su una delle relazioni di somiglianza introdotte nella sezione precedente. Partendo dalla relazione identità, trattiamo le caratteristiche principali di ogni classe, i pregi e i difetti delle soluzioni proposte.

Inne, ci soermeremo sulla nostra relazione di equivalenza e introdur-remo i concetti che saranno parte integrante della nostra risoluzione del problema dell'inferenza dei motivi con dierenze.

2.4. ALGORITMI PER LE RELAZIONI 43 2.4.1 KMR per la relazione identità

Il primo algoritmo per la ricerca esatta delle ripetizioni in una stringa, chiamato KMR, è stato elaborato da Karp, Miller e Rosemberg nel 1972 in [KMR72]. Data una sequenza s, KMR risolve i seguenti problemi:

Problema 2 (Problema della ricerca di ripetizioni esatte di lunghezza s-sa). Identicare le posizioni di tutte le parole di una ssata lunghezza L che appaiono ripetute in s.

Problema 3 (Problema della ricerca di ripetizioni esatte di lunghezza mas-sima). Trovare la lunghezza Lmax della più lunga parola ripetuta in s, e

risolvere il problema 2 per L = Lmax.

In KMR si usa la denizione EL data nella sezione 2.3.3. Sulla base di

questa relazione il problema 2 si riformula come il problema di trovare le classi di equivalenza della relazione ELche si possono costruire a partire da s, il problema 3, invece, propone di trovare il massimo valore di L tale che

EL non denisce più classi di equivalenze in s.

Per risolvere i due problemi, l'algoritmo KMR costruisce iterativamente delle classi o partizioni di El, con l < L e l potenza di due. Quindi ogni

iterazione costruisce un insieme di classi di equivalenza che si riferiscono a parole di s lunghe il doppio rispetto all'iterazione precedente. Formalmente l'idea di base di KMR è espressa dal Lemma 1 nel modo seguente:

Lemma 1. Dati due interi a, b con 1 ≤ b ≤ a, due posizioni i, j in una stringa s di lunghezza n, tale che i, j ≤ n − (a + b) + 1, allora i Ea+b j

se e solo se i Ea j e (i + b) Ea (j + b).

In particolare l'algoritmo KMR applica il lemma 1 con b = a per il mag-gior numero possibile di volte. Quindi costruisce ripetizioni di lunghezza 2a

usando gli indici delle parole nelle classi per le ripetizioni di lunghezza a. La composizione di due indici di lunghezza a fa in modo che un indice sia il presso ed l'altro il susso di una parola di lunghezza 2a. Se L non è una potenza di 2, si usa il Lemma 1 con b < a così che si possano costruire eettivamente le classi per EL anche se L non è potenza di due. Per quanto

riguarda la ricerca di Lmax, l'algoritmo applica il Lemma 1 con b < a,

avan-zando di una posizione ogni passo a partire dal valore di L potenza di 2, che chiamiamo 2p_{, per cui E2p−1 è identità e E2p non è più identità.}

Un altro modo di vedere la costruzione delle partizioni o classi di Ea è

quello di un'operazione di intersezione iterativa di insiemi.

Per risolvere il Problema 2 l'algoritmo KMR impiega tempo O(n log L) e spazio O(n) perchè, costruisce ad ogni passo pattern lunghi il doppio del passo precedente, quindi, compie log L passi e ogni passo costa n perchè n possono essere i caratteri da leggere nella sequenza s di lunghezza n. Per il Problema 3 arriva no a O(n log n) in quanto cercare il valore kmaxpotrebbe

signicare provare qualsiasi lunghezza nella sequenza s, anche, kmax= n.

Mostriamo un esempio di esecuzione dell'algoritmo KMR su una sequenza

s.

Esempio 11. Dato un alfabeto Σ = {A, B, C, D}, una lunghezza L = 4 e una sequenza s = ABCDABCD. Le posizioni di s vanno da uno a otto. Cerchiamo tutte le parole di s di lunghezza L che si ripetono almeno due volte.

Il primo passo è per L = 1 e le classi generate sono:

A = {1, 5} B = {2, 6} C = {3, 7} D = {4, 8}

Il secondo passo è per L = 2 e le classi generate sono:

AB = {1, 5} BC = {2, 6} CD = {3, 7}