Albero dei sussi per le relazioni identità e non transitive

Come abbiamo visto nella prima parte di questo capitolo, un albero dei su- issi è usato nell'indicizzazione di un testo, ogni susso possiede una foglia etichettata con l'indice del susso stesso nel testo e i sussi che condividono un presso, hanno in comune anche la parte del percorso che dalla radice ar- riva al nodo di ramicazione per quel presso. Trovare le ripetizioni identiche di lunghezza L in un testo s con l'albero dei sussi è un operazione sem- plice, in quanto, è necessario solo visitare tutti i percorsi relativi ai pressi di lunghezza L e calcolare i sussi che hanno in comune quei percorsi. La complessità di questo algoritmo naive è lineare.

L'algoritmo appena visto calcola gli stessi indici delle ripetizioni identiche calcolati dal'algoritmo KMR per la relazione identità.

L'albero dei sussi non è solo usato per la ricerca di ripetizioni identiche. L'algoritmo proposto in [SW], usa l'albero dei sussi per la generazione dei modelli di una relazione non transitiva con errori.

Il problema che i modelli cercano di rivolvere è il seguente:

Problema 4 (Problema della ricerca delle ripetizioni con la distanza di Hamming e di Edit). Data una stringa s ∈ Σ+_{, un intero k ≥ 0 e un quorum}

q, trovare tutti i modelli m tale che m è valido, cioè, è presente almeno q volte in s, ogni volta con al più k errori.

Per generare i modelli di s, l'algoritmo visita l'albero dei sussi ST di s. Ad ogni passo, si estende un modello di una unità e l'insieme delle occorrenze del nuovo modello m viene creato dall'insieme delle occorrenze

del modello m0 _{di lunghezza | m | −1 che è suo presso, aggiornando tale}

insieme in base a ciò che segue nell'albero dei sussi. Quindi per ogni modello m considerato bisogna tenere gli insiemi delle occorrenze di tutti i modelli presso del modello m. Le occorrenze di un modello sono nodi dell'albero (nodi occorrenza) rappresentati con una coppia (i,d) dove i è una posizione in s e d è la misura della distanza dal modello in esame.

L'algoritmo applica ricorsivamente il Lemma 3, dove x denota un nodo dell'albero, padre(x) il suo più stretto antenato e d il numero di errori tra il presso x e il modello m.

Lemma 3. (x,d) è un nodo-occorrenza di m0 _{= mαcon m ∈ Σ}L _{e α ∈ Σ se}

e solo se d ≤ k e una delle condizioni seguenti è vericata:

(uguaglianza) (padre(x),d) è un nodo-occorrenza di m e l'etichetta dell'ar- co che va da padre(x) a x è proprio α;

(sostituzione) (padre(x),d-1) è un nodo-occorrenza di m e l'etichetta del- l'arco che va da padre(x) a x è β 6= α;

2.5. LA RELAZIONE DI EQUIVALENZA CON DIFFERENZE HL

L 49

(cancellazione) (x,d-1) è un nodo-occorrenza di m;

(inserzione) (padre(x),d-1) è un nodo-occorrenza di mα;

Per riuscire a vericare la validità di un modello è necessario aggiungere per ogni nodo x di ST, il numero di foglie del sottoalbero Tx. Se il numero

è superiore al quorum q allora il modello è valido, altrimenti non lo è. Prima di dare la complessità al caso pessimo è necessario introdurre la nozione di parole vicine o word neighbourhood.

Denitione 24. Data una parola di lunghezza L denita su ΣL_{, V(k, L), è}

il numero di parole a distanza (Hamming o Edit) al più k da essa.

La vicinanza misura il numero di modelli m ∈ ΣL _{di cui una posizione i}

in s può essere un'occorrenza.

Il numero di modelli validi nel caso pessimo è allora O(nV(k, L)). V(k, L) è limitato dal valore Lk_|Σ|k _[Sag98].

Per completezza, in [Sto00], il concetto di modello è stato esteso all'in- ferenza di motivi strutturati che rappresentano motivi per cui è possibile denire formalmente una struttura fatta di motivi singoli distanziati oppor- tunamente l'uno dall'altro. La loro applicazione è stata indirizzata verso lo studio dei binding site.

2.5 La relazione di equivalenza con dierenze H

l L La relazione RL non transitiva con errori basata sui modelli, se si considera

la denizione che usa la distanza di Hamming, è anche una relazione con dierenze. La non transitività che la caratterizza è, però, cruciale per questa relazione. Il problema della ricerca delle ripetizioni con errore o con dif- ferenza che si basa sulle nozioni di distanza di Hamming o di Edit, conduce

inevitabilmente, per quanto abbiamo visto, ad una relazione non transitiva. Uno dei nostri obbiettivi è di proporre una denizione di relazione con dif- ferenze che sia una relazione di equivalenza. L'idea è venuta partendo proprio dalla ricerca di una relazione transitiva che riuscisse a fondere insieme, nella stessa denizione, la distanza di Hamming e la transitività. Comprendere la sottigliezza su cui si basa la nostra idea signica comprendere perchè, così come sono denite, la transitività e la distanza di Hamming coesistono di- cilmente. La distanza di Hamming, sappiamo che, conta le dierenze tra le sequenze a confronto. Questa denizione esclude in partenza la transitività tra le sequenze perchè, se una sequenza s1 ha k dierenze con un altra se- quenza s2 e se quest'ultima ha k dierenze con una terza sequenza s3, allora, non è detto che il numero di dierenze tra s1 e s3 sia lo stesso k. I casi che possono capitare sono due; se l'insieme delle posizioni di dierenza tra s1 e

s2, e tra s2 e s3 è diverso, allora l'insieme delle posizioni di dierenza tra s1 e s3 è diverso e il numero di dierenze è almeno k +1 e al più 2∗k, se invece,

s1, s2 e s3 hanno dierenze nello stesso insieme di posizioni allora la transi- tività è sempre vericata. La denizione proposta di relazione con dierenza è una relazione di equivalenza che costruisce la nozione di somiglianza tra stringhe sulle posizioni di dierenza tra le stringhe stesse. In sostanza due stringhe sono simili se, ssando un insieme di posizioni l, sono identiche nelle posizioni non scritte in l e dieriscono al più nelle posizioni di l.

Formalmente, dato una lunghezza L ssiamo un insieme di posizioni l ⊆

{0, · · · , L − 1}, l'idea è di mettere insieme in una classe di equivalenza, tutte le parole identiche di s che dieriscono al più nelle posizioni non scritte in l.

Partiamo dalla denizione di HL con le posizioni ssate.

Denitione 25 (Relazione HL con le posizioni ssate). Date due stringhe

2.5. LA RELAZIONE DI EQUIVALENZA CON DIFFERENZE HL

L 51

u H_L v _{se e solo se ∃l ⊆ {0, · · · , L − 1} tale che}

• |l| ≤ k,

• ui E vi per ogni i ∈ {0, · · · , L − 1}\l,

• dist_H(u_i, v_i) ≤ 1 _{per ogni i ∈ l.}

La relazione HL così denita, non è transitiva. Vediamo un controesem-

pio che dimostri questa osservazione.

Esempio 13. Dati un errore k=1 e tre stringhe u=abc, v=dbc e w=dgc. Le posizioni di una stringa sono in ordine decrescente (2, 1, 0). La proprietà transitiva di una relazione H3 si scrive u H3 v, v H3 w ; u H3 w.

abc H3 dbc per l = {2}

dbc H3 dgc per l = {1}

abc H3 dgc per l = {2, 1}

Visto che |l| = 2 > k = 1 la relazione H3 non è transitiva.

Generalizzando, se la relazione HL non è transitiva, allora non è una

relazione di equivalenza. Cerchiamo una denizione di HL per cui sia una

relazione di equivalenza. La denizione che segue è la denizione corretta, che ssa veramente l'insieme delle posizioni di dierenza.

Denitione 26 (Relazione Hl

L). Date due stringhe u, v ∈ ΣL, un numero k

e un insieme l ⊆ {0, · · · , L − 1} e |l| ≤ L − k.

u Hl

L v se e solo se

• ui = vi per ogni i ∈ l

Dimostriamo adesso che, la relazione Hl

L è una relazione di equivalenza. Lemma 4. Fissato L e un l,Hl

Dimostrazione. Una relazione di equivalenza è una relazione tale che: 1. u Hl L u(riessiva) 2. u Hl L v ⇒ v HLl u(simmetrica) 3. u Hl L v e v HLl w ⇒ u HLl w(transitiva)

La riessività è immediata con l={}. La simmetria è vericata immediata- mente per qualsiasi insieme l e la transitività è vericata per qualsiasi insieme

l. Visto che l è ssato, se u e v sono identici tranne al più nelle posizioni di

l e v e w sono identici tranne al più nelle posizioni di l, allora u e w sono identici tranne al più nelle posizioni di l.

La denizione di Hl

L è immediata se consideriamo anche coppie di po-

sizioni piuttosto che parole in s.

Denitione 27 (Relazione Hl

L per le posizioni). Sia s ∈ Σn, un numero k,

date due posizioni i, j ∈ s e un insieme l ⊆ {0, · · · , L − 1} tale che |l| ≤ k.

i Hl

L j se e solo se

• s_i+indice E s_j+indice per ogni indice ∈ {0, · · · , L − 1}\l, • dist_H(si2, sj2) ≤ 1 per ogni i2, j2 ∈ l.

Data una posizione i in s, una lunghezza L e un insieme l, per identicare la classe di appartenenza di i leggendo semplicemente i suoi componenti

si· · · si+L−1, basta trovare la classe con etichetta si· · · si+L−1 con wildcard

nelle posizioni di non espresse in l. La relazione Hl

L è una relazione di equivalenza. Una relazione HLl sulle

parole di una stringa s crea una famiglia di classi di occorrenze di s. Un indice i, all'interno di una famiglia, appartiene al più ad una e una sola classe. Se osserviamo ogni famiglia di classi di occorrenza, un indice i di

2.5. LA RELAZIONE DI EQUIVALENZA CON DIFFERENZE HL

L 53

s_{, compare in ogni famiglia creata a partire da una relazione H}l

L. Questa

proprietà deriva dal fatto che ogni relazione esamina le stesse stringhe delle altre relazioni selezionadone la sottosequenza specicata nell'insieme l, per questo motivo l'indice i di una parola compare in ogni Hl

L.

Questa forma di degenerazione è diversa da quella vista nora, in quanto ogni relazione Hl

L con il trucco delle posizioni ssate non ha localmente (in

ogni famiglia) degenerazione degli indici delle parole, ma solo a livello di tutte le relazioni. Vedremo nel Capitolo 4 come questa diversità o mascheramento ci permette di costruire gli indici delle parole in maniera eciente.

Fissare l'insieme l con |l| ≤ k rende necessario comunque calcolare la relazione Hl

L per ogni possibile combinazione di posizioni l. La complessità

esponenziale è intrinseca al problema della ricerca di ripetizioni con errore o dierenze, di conseguenza avere le relazioni di equivalenza ci riduce lo spazio delle combinazioni da vericare, come vedremo nel Capitolo 4, ma non ci risolve il problema. Infatti, le posizioni delle dierenze tra le occor- renze, essendo imprevedibili, sono calcolabili solo provando tutte le possibili combinazioni di posizione di errore.

Adesso si puntualizza il legame tra la relazione Hl

Le gli alberi AT W (s, L, l).

Gli indici dei sussi associati alle foglie di un AT W (s, L, l) o di un ctw(s, L, l) sono in relazione Hl

L tra loro.

Lemma 5. Dati una lunghezza 1 ≤ L ≤ n, un insieme di posizioni l ⊆

{0, · · · , L − 1} _{e un AT W (s, L, l), per ogni foglia f ∈ foglie(AT W (s, L, l))}

tale che |f|=L vale i Hl

L j, per ogni coppia i, j ∈ If, con If = {i ∈

{1, ··, n}|i è associato alla foglia di f}.

Dimostrazione. Si sonsiderino due indici i, j ∈ If, per una generica foglia f

presso in AT W (s, L, l) con al più distH(si2, sj2) ≤ 1 per ogni i2, j2 ∈ {0, · · · , L − 1}_{. Di conseguenza i H}l

Lj.

Il lemma 5 assicura che nelle foglie di un albero AT W (s, L, l) siano raggruppate eettivamente le occorrenze delle classi della famiglia di una relazione Hl

L.

Nel Capitolo 3 si analizza la generazione delle combinazioni di posizioni e la struttura di indicizzazione delle combinazioni, nel Capitolo 4 si dimostra- no le dipendenze tra gli indici e i problemi della formalizzazione di una gerarchia tra gli indici, inne, nel Capitolo 5 si mostrano tre algoritmi di risoluzione del problema dell'inferenza di motivi con wildcard e si analizza la loro complessità.

Capitolo 3

La generazione di tutte le

combinazioni

La scelta degli elementi dell'insieme l per una relazione Hl

L non è deter-

minabile a priori, non si può prevedere dove una mutazione avviene o è avvenuta e per questo motivo le selezioni vanno compiute considerando tutte le possibili scelte. In questo capitolo introduciamo la nozione di combinazione di posizioni e discutiamo alcune modi per rappresentarle. Inoltre, discuti- amo la generazione delle combinazioni secondo un opportuno ordinamento e introduciamo la struttura di indicizzazione per le combinazioni.

3.1 Denizione e rappresentazione delle combinazioni

Una scelta di k posizioni di errore in una parola con L posizioni per una re- lazione Hl

Lrappresenta un modo per selezionare un sottoinsieme di k oggetti

da un insieme di cardinalità L. Notoriamente questo sottoinsieme è conosciu- to con il nome di k-combinazione di L elementi. Il numero di k-combinazioni

di un insieme di cardinalità L è denotato con¡L k

¢

, per denizione risulta: µ L k ¶ = L! k!(L − k)! (3.1)

La formula (3.1) è simmetrica per k e L-k: (x + y)L= L X k=0 µ L k ¶ xkyL−k. (3.2)

Ciò signica che il numero di combinazioni di k oggetti selezionati tra L è uguale al numero di L − k oggetti non selezionati t. Enfatizziamo questa simmetria dicendo che

L = k + t _(3.3)

Nel corso della nostra discussione ci riferiremo ad una k-combinazione di L oggetti come ad una (k,t)-combinazione. Una (k,t)-combinazione è un modo per suddividere una collezione di k + t oggetti in due insiemi di cardinalità k e t.

Esistono due modi principali di rappresentare le (k,t)-combinazioni: pos- siamo scrivere la lista ck· · · c1 degli elementi selezionati, o possiamo lavorare con le stringhe binarie ak+t−1· · · a0 per cui vale la seguente equazione

ak+t−1+ aL−2+ . . . + a0 = k (3.4) La stringa binaria si può denire anche così:

ai =      1 se selezionato 0 se non selezionato (3.5)

3.1. DEFINIZIONE E RAPPRESENTAZIONE DELLE COMBINAZIONI57

lezionati). Nella rappresentazione con la lista ck· · · c1, gli elementi apparten-

gono all'insieme {0, . . . , L−1} e i valori degli elementi sono ordinati in ordine decrescente:

L > ck> ck−1> . . . > c0 ≥ 0 (3.6) La notazione binaria permette di collegare entrambe le rappresentazioni in maniera semplice, mostrando che le due rappresentazioni sono equivalen- ti. Possiamo, per esempio, trasformare una nell'altra. Infatti, la rappresen- tazione ck· · · c1 può essere scritta come:

2ck _{+ 2}ck−1_{+ · · · + 2}c0 ₌

k+t−1_X i=0

ai2i = (ak+t−1. . . a0)2 (3.7) Con la notazione (ak+t−1. . . a0)2 intendiamo la rappresentazione binaria di una sequenza. Lo stesso tipo di riduzione può essere applicato anche alla lista delle posizioni non selezionate bt· · · b1 in un insieme. La rappresen- tazione bt· · · b1 ha valori in {0, . . . , L − 1} e i componenti sono ordinati in ordine decrescente. Ciò signica che:

L > bt> . . . > b1≥ 0 (3.8) Un insieme di posizioni bt· · · b1 soddisfa la condizione (3.8) se e solo se

ck· · · c1 soddisfa la (3.6). Le rappresentazioni viste sopra sono tutte equiv- alenti fra loro. In [Knu98], esistono anche altre forme per modellare le com- binazioni. La Tabella 3.1 mostra ¡4

2 ¢

= 6 combinazioni alla luce delle tre forme di rappresentazione viste prima, in cui k=t=2.

L'ordinamento delle combinazioni nella Tabella 3.1 è di tipo lessicogra- co: i valori delle rappresentazioni ck· · · c1 e ak+t−1· · · a0 sono elencati in ordine decrescente. L'ordinamento di solito suggerisce il modo con cui gener-

a3a2a1a0 b2b1 c2c1 0011 32 10 0101 31 20 0110 30 21 1001 21 30 1010 20 31 1100 10 32

Tabella 3.1: Tabella per le tre principali rappresentazioni delle combinazioni

are le combinazioni. Generalmente, ordinamenti diversi hanno applicazioni diverse, costi algoritmici diversi e proprietà diverse [Knu98].

Come vedremo nel prossimo capitolo, la scelta di un ordinamento è im- portante nello studio delle dipendenze tra le combinazioni e gli indici generati a partire da essi. Tra tutte le forme di ordinamento e rappresentazione delle combinazioni scegliamo l'ordinamento lessicograco e la lista delle posizioni selezionate ck· · · c1. Esse sono tra le più usate e godono di un gran numero

di studi teorici e risultati accertati.

3.2 L'albero Binomiale e l'organizzazione delle com-

Nel documento Costruzione efficiente di indici per ripetizioni con caratteri "wild card". (pagine 47-58)