Introduzione
Presentiamo qui un piccolo elaborato sulle potenzialità dell’albero dei suffissi in applicazioni biologiche.
In appendice A è riportata un’introduzione sulle fondamenta algoritmiche, come può venir costruito a partire dai dati, e le tecniche di ottimizzazione che sono state implementate per ridurne ad un tempo lineare la creazione e la successiva lettura.
Verranno indicate le problematiche generiche più classiche a cui è conveniente applicarlo – secondo alberi generalizzati, alberi intrinseci, profondità dei nodi o array informativi integrativi associati ai nodi.
Di seguito si porteranno degli esempi del possibile uso nel trattamento di dati di sequenze genomiche e proteomiche. Ed in particolare si focalizzerà l’attenzione su di un software realizzato nel 1999 e successivamente ottimizzato nel 2002, in grado di confrontare interi genomi, il MUMmer. Si tratta di due vecchi software, ma che si prestano molto bene per chiarire le potenzialità di questa struttura dati.
La letteratura consultata comprende i capitoli 5 e 6 del libro di D. Gusfield “algorithms on strings, trees and sequences” per le informazioni di base. Ed il capitolo 7 per quanto riguarda le prime applicazioni. Gli articoli “Alignment of whole genomes” e “Fast algorithms for large-scale menome aligment and comparison” entrambi di Arthur L. Delcher et all. pubblicati su Nucleic acids research. Un altro lavoro correlato è l’articolo “Efficient multiple genome alignment” di Michael Hohl and all, che compara gli approcci MUMs e MEMs. Inoltre una ricerca in rete ha fornito alcuni spunti per altre riflessioni sulle applicazioni possibili. Infine si sono consultati due corsi in rete riguardanti Algoritmi per biologia molecolare, da cui sono stati tratte le immagini riportate, i cui autori sono: La coppia R.C.T. Lee e Chin Lung Lu; ed Harry Hochheiser.
Applicazioni dell’albero dei suffissi
La forma molto strutturata dell’albero dei suffissi permette di implementare in modo semplice e computazionalmente veloce, molte applicazioni specifiche sulla base dell’osservazione della struttura ripetitiva del modello stesso.
Foglie e nodi interni, insieme ai vari puntatori che posso associare ad essi, possono assumere significati diversi, appropriati all’applicazione che voglio implementare. Vedremo nella sezione successiva alcuni esempi molto distintivi di uso dell’albero dell’albero in campo biologico, situazioni che altrimenti non potrebbero essere risolte in un tempo lineare.
Qui di seguito focalizzeremo l’attenzione sulle applicazioni più classiche, a cui molte altre problematiche possono essere ricondotte.
- Pattern matching (exact string matching)
Gli alberi dei suffissi permettono l’individuazione di un pattern di lunghezza n in un tempo O(n+k), dove k è il numero di occorrenze del pattern nel data set. E, naturalmente, per semplice estensione è chiaro come si possa risolvere con la stessa facilità il problema dell’Exact Set Matching. Questo problema comporta la ricerca di tutti i match esatti per un set di stringhe. Il tempo di risoluzione con l’albero dei suffissi è ancora una volta in O(n + k), dove n è la lunghezza totale del set di patterns (Gusfield, 1997, p.123).
Il procedimento è immediato: si segue, a partire dalla radice, l’arco etichettato con i caratteri del pattern cercato, ci si ferma o quanodo arrivo in fondo al pattern e si osserva la foglia finale (il cui indice rappresenta il punto dove inizia un’occorrenza del pattern) o quando si trova un mis-match sull’arco (nel qual caso il pattern non è presente tra i dati).
Notiamo che il cammino percorso durante la ricerca è unico, proprio per la struttura stessa dell’albero dei suffissi che non permette ci siano nodi da cui partono archi etichettati da stringhe con il medesimo primo elemento.
1. La più lunga sottostringa comune
Questo problema può essere risolto, attraverso un albero dei suffissi generalizzato di dimensione m, in un tempo O(m). Per farlo è richiesto sfruttare due valori associati ad ogni nodo interno:
String coverage c(v) – il numero di stringhe distinte sottese dai suffissi nei figli di v.
string-depth d(v) – il numero di caratteri che costituiscono l’etichetta suffisso per il nodo v.
Dati questi due valori, la più lunga sottostringa comune è identificata dal nodo interno marcato ( string coverage) da tutte le stringhe, e con la maggiore profondità di stringa. Il valore di di c(v) e d(v) possono essere calcolate mentre si crea l’albero o durante un attraversamento dell’albero in tempo O(m).
- Sottostringhe comuni per più di due stringhe
Questo problema è una semplice estensione concettuale della ricerca della più lunga sottostringa comune. Al posto di calcolare singolarmente i coverage string per ogni nodo si può pensare di generare una lista delle profondità di stringa e una lista di stringhe uniche, come sotto riportato:
Ogni nodo ha sotteso più di un finale di stringa. Per esempio il nodo 8 indica che le stringhe 1, 2, 3 e 4 hanno una comune sottostringa di lunghezza 8. Ugualmente interessante sono i nodi interni che sottendono solo una stringa. Il tempo per implementare queste liste è pari ad O(Kn).
- Problema dell’accavallamento ( prefisso-suffisso comune)
Si tratta di riuscire a discernere la più lunga parte comune di stringa in un data set di stringhe, nell’ipotesi ovvia che nessuna stringa sia sottostringa di un’altra. In sostanza la risoluzione di questo problema si riduce alla determinazione del prefisso non comune all’altra stringa. Per esempio, date due sequenze S1=ABACD e S2=acdef
A B A C D
a c d e f
La componente comune è “acd” e il prefisso non comune è “AB”. Per cercare di individuarlo si ricorre alla ricerca di un arco terminale ( ovvero un arco dell’albero etichettato dal solo terminatore di stringa $). Infatti la presenza di un arco terminale mi indica che l’arco che lo precede sul cammino sarà un suffisso finale, ma al contempo esso rappresenterà un prefisso per l’altro cammino che parte da quel nodo.
Applicazioni biologiche dell’albero dei suffissi.
Le sequenze di informazioni biologiche sono comunemente archiviate in locazioni contigue della memoria del computer. Questo metodo di stoccaggio non risulta efficiente per un certo numero di applicazioni. Il nodo del problema sta nel fatto che i dati archiviati in modo sequenziale devono in buona sostanza essere processate in modo sequenziale.
Invece, spesso, il valore informativo all’interno della sequenza risulta essere caratterizzato dalla presenza di certe sottosequenze, ripetute o meno; come può capitare in sequenze di DNA codificanti per una determinata proteina. Risulta ovvio come il dover necessariamente accedere sequenzialmente ad ogni stringa dati – quando si cerca una determinata sottosequenza all’interno di un intero dataset, risulta inefficace e dispersivo; specie se il volume di dati da analizzare cresce in modo esponenziale come è avvenuto negli ultimi anni con la genomica e la proteomica. Il tempo di accesso diventa il fattore limitante. Quello che allora serve è un sistema di indicizzazione delle sequenze efficiente. Un sistema che permetta di accedere ad una sequenza in termini di cosa contenga, senza dover specificare dove essa sia contenuta. L’albero dei suffissi.
Lo stesso Dan Gusfield, in un suo breve scritto “Suffix trees (and relatives) come of age in bioinformatics”, mette l’accento su quante possano essere le applicazioni in bioinformatica di questa struttura dati.
“ […] Much has changed since 1997. Suffix trees and close relatives are now widely taught in graduate level courses on computer algorithms and on bioinformatics; there are several good expositions (I think) on suffix tree algorithms and uses; the space requirements have been substantially reduced; machines memories have greatly increased; additional variants of suffix trees have been introduced that address some of their deficiencies; and suffix tree code is publicly available. As a result, and to some extent as a cause, there are now many more applications in bioinformatics of suffix trees and related data structures. Since the publication of the book, I have been aware of the wider uses of suffix trees in bioinformatics, but I had not systematically followed the field. This talk (and the paper I am writing based on it) is an attempt to catch up. I will try to survey here several (about twenty in the paper) recent papers that use suffix trees in bioinformatics, and papers that helped enable those applications. I also mention a few results on suffix trees that are presently only motivated by computational biology, but may later have significant application. However, the survey will not be exhaustive, and I apologize to those people whose work I have (unintentionally) overlooked. I view the recent results as falling into the following overlapping categories: new fundamental algorithms; implementation improvements (mainly space); important new variations on suffix trees and arrays (for example virtual suffix arrays); new algorithms for tandem repeats; algorithms for approximate repeats; algorithms for fast lookups in databases; algorithms to study and display substring frequencies; motif and pattern discovery algorithms; hybrid dynamic programming and pairwise alignment methods; oligo construction and microarray design algorithms; sequence assembly and resequencing; (multiple) whole genome comparisons; miscellaneous applications; less used, related data structures – affix trees, DAWG; unsolved problems.”
- All’atto in cui divenne disponibile l’intera sequenza genomica di due organismi filogeneticamente omologhi, una delle prime questioni che venne posta fu la necessità di compiere un allineamento genomico.
Esistono molti, sofisticati algoritmi adatti per l’allineamento di due sequenze, includendo i famosi metodi di Needleman & Wunsch e di Smith & Waterman. Essi funzionano bene quando si tratta di allineare sequenze relativamente brevi (singole proteine, per esempio), ma spesso risultano o troppo lenti o necessitano di troppa memoria quando si tratta di allineare sequenze di milioni di nucleotidi.
Gli algoritmi standard ottimali di programmazione dinamica hanno un funzionamento con tempo e spazio proporzionale a O(n^2); invece tecniche euristiche come Fasta e Blast sono mediamente più veloci, ma sono anch’esse basate su una strategia “match and extend”, dove la seconda parte prende anch’essa un tempo O(n^2). Risulta quindi conveniente utilizzare una struttura come l’albero dei suffissi, che risulta in tali situazioni molto più efficace.
Vedremo poco più avanti come questo problema sia affrontato da due software, il MUMmer e il MGA, quali siano i diversi approcci e a quali risultati giungono.
¨ Una seconda applicazione molto interessante degli alberi dei suffissi è quella di individuare una eventuale contaminazione del DNA.
Il problema che si pone è meno banale di quanto si creda, se si pensa a quante possano essere le fonti di contaminazione all’atto di sequenziare (il classico problema dell’individuazione del DNA di un dinosauro). Generalizzando il problema, si tratta di riuscire confrontare due sequenze, e distinguere all’interno della prima sequenza la presenza di possibili sottostringhe della seconda.
Per risolvere efficacemente la questione, si può optare per costruire un albero dei suffissi generalizzato contenente le sequenze S1 (quella del presunto dinosauro) e la sequenza S2 (quella dell’elemento contaminante; il DNA del tecnico che ha lavorato sui dati, per esempio). Si marcano quindi i nodi interni che presentano nel relativo sottoalbero sia suffissi di S1 che di S2, ed infine si selezionano, tra questi, i nodi che presentano una profondità di stringa superiore ad una determinata soglia.
¨ Strutture ripetitive in sequenze biologiche. E’ noto che, specialmente per gli eucarioti, sono state individuate migliaia di famiglie di sequenze ripetitive di DNA.
Esse giocano un ruolo fondamentale per alcune funzioni biologiche, e per l’interesse che generano nello studio dell’evoluzione. Usualmente si distinguono tre strutture ripetitive: ripetizioni locali, ripetizioni singole (le cui funzioni sono meno chiare), ripetizioni complesse. Un esempio di architettura biologica molto importante e strutturate come ripetizioni locali sono le forcine (hairpin) che hanno una tipica struttura palindrome, o anche i siti di taglio degli enzimi di restrizione. Una palindrome è una stringa dati che può essere letta ugualmente in avanti o indietro. Strutture palindrome sono comuni nelle sequenze di DNA; sequenze di DNA sono palindrome complementari, ove A-T e C-G sono complementi, se ogni carattere in metà della stringa è cambiato con il suo carattere complementare, per esempio: AGCTCGCGAGCT.
Il problema dell’individuazione in tempo lineare di tutte le “maximal repeats” è risolvibile proprio con gli alberi dei suffissi.
¨ Altre applicazioni citate in rete sono il “Circular DNA Sequences Problems”. Ovvero, data una sequenza circolare S di lunghezza n è definita come una sequenza nella quale il carattere n è considerato precedente al carattere 1.
I caratteri nella sequenza sono numerati sequenzialmente da 1 ad n, partendo da un punto arbitrario di S. Date due sequenze della medesima lunghezza, un albero dei suffissi può essere usata per compararle, per determinare se sono uguali, in tempo lineare. Si può operare tagliando la prima sequenza circolare S1 in un punto arbitrario e quindi ottenere una sequenza lineare L1. Duplicando L1, si crea la sequenza L1L1. A questo punto, si costruisce l’albero dei suffissi T1 per L1L1.
Quindi si attraversa T1 secondo la regola per cui, ad ogni nodo, l’attraversamento segue l’arco il cui primo carattere è lessicalmente il più piccolo di tutti i primi caratteri dei vari archi del nodo. Il percorso continua finchè il path P1 attraversato ha una profondità di sequenza n.
Dopo di che si ripete l’operazione per la sequenza S2 fino a raggiungere il path P2. Infine si comparano P1 and P2 per verificare la loro eventuali uguaglianza.
¨ Il problema del “The k-mismatch (error)”, che tratta la ricerca di sequenze con errori. In special modo, ci si riferisce al match di sequenze con un dato (k) numero di errori.
Per esempio, dato un set di stringhe, si cerchino tutte le occorrenze del pattern P, tipo sequenza aminoacidica, permettendo un solo errore. P può presentarsi differentemente come P’ in ognuna delle stringhe, seguendo una dei tre possibili errori: inserzione, cancellazione, o sostituzione. Per risolvere questo problema, abbiamo bisogno di generare ogni possibile stringa P’ che può essere derivata da P cambiando un solo carattere. Si costruisce quindi l’albero dei suffissi generalizzato contenente la sequenza proteica di base e tutte queste stringhe. Infine si attraversa l’albero per individuare tutte le locazioni di partenza di tutte le possibili occorrenze di P’. Questa ricerca può essere effettuata in tempo lineare ed è proporzionale alla lunghezza di P’.
Infine può essere interessante leggere l’articolo (di cui riportiamo l’abstract) “Database indexing for large DNA and protein sequence collections” di Ela Hunt, Malcolm P. Atkinson, Robert W. Irving, per rendersi conto di quanto l’uso dell’albero dei suffissi in questi ultimi anni stia assumendo sempre una maggiore importanza e attenzione in campo biologico.
“Our aim is to develop new database technologies for the approximate matching of unstructured string data using indexes. We explore the potential of the suffix tree data structure in this context. We present a new method of building suffix trees, allowing us to build trees in excess of RAM size, which has hitherto not been possible. We show that this method performs in practice as well as the O(n) method of Ukkonen. Using this method we build indexes for 200 Mb of protein and 300 Mbp of DNA, whose disk-image exceeds the available RAM. We show experimentally that suffix trees can be effectively used in approximate string matching with biological data. For a range of query lengths and error bounds the suffix tree reduces the size of the unoptimised O(mn) dynamic programming calculation required in the evaluation of string similarity, and the gain from indexing increases with index size. In the indexes we built this reduction is significant, and less than 0.3% of the expected matrix is evaluated. We detail the requirements for further database and algorithmic research to support efficient use of large suffix indexes in biological applications”.
Allineamento genomico: 2 diversi approcci
Sono state implementate due versioni distinte del MUMmer, il cui fondamento algoritmico è lo stesso.
Esso è una combinazione di tre idee distinte: l’albero dei suffissi, la LIS (longest increasing subsequence), e l’allineamento secondo Smith-Waterman. L’ipotesi che si assume è che le sequenze da comparare siano filogeneticamente omologhe (comune ancestore).
Il processo di allineamento consiste nei seguenti step:
· Vengono identificati all’interno dei due genomi i relativi MUMs (maximal unique match), ovvero le sottosequenze che occorrono esattamente una volta nel genoma A e una volta nel genoma B. Questa operazione è effettuata in tempo lineare proporzionale alla somma delle lunghezze dei genomi, attraverso la costruzione e lettura dell’albero dei suffissi relativo ai due genomi. Il principio sottostante è il fatto che: se esiste un match perfetto di una lunga sequenza che si presenta una volta sola in entrambi i genomi, essa farà sicuramente parte dell’allineamento globale.
· Si analizzano i match trovati, e si estrae il set più lungo possibile di stringhe che occorrono nel medesimo ordine in entrambi i genomi.
· Vengono chiusi i gap tra i vari MUM, sfruttando l’algoritmo di allineamento locale di Smith-Waterman per tutte le regioni inter-MUM.
Il passaggio chiave sta nell’individuare i MUMs. Questa operazione è effettuata attraverso un albero dei suffissi,ricordando che ogni foglia rappresenta un suffisso unico, e che un nodo interno in un albero corrisponde ad una sequenza ripetuta nel genoma originale.
L’albero viene costruito secondo l’algoritmo di McCreght. Ogni foglia è etichettata per indicare quale suffisso rappresenta e in quale genoma (A o B). Identificare i MUMs significa identificare un nodo interno dotato di esattamente due figli, ognuno dei quali deve essere foglia di differenti genomi.
Per testare l’efficacia dell’algoritmo si sono confrontati i genomi di due ceppi di tubercolosi. L’allineamento rivela migliaia di differenze individuali, il più delle quali sono cambiamenti di singole basi. Sono state individuate alcune dozzine di inserzioni. Per quanto riguarda l’efficienza, l’albero dei suffissi viene costruito in 5 sec., il sorting per individuare i LIS prende 45 sec, mentre l’allineamento dei gap prende solo 5 sec (in questo caso perché i due genomi sono in partenza simili al 99%, e quindi non necessita molto lavoro).
Confrontando invece il genoma umano con quello di topo, servono 1,6 secondi per costruire l’albero dei suffissi, e 29 sec sono richiesti per completare l’allineamento.
Il secondo software che citiamo è il MGA (Multiple Genome Aligner). Esso si basa sull’individuazione di tutti i MultiMEMs (maximal multiple exact matches) la cui lunghezza supera una certa soglia. L’algoritmo impiega un tempo O(kn+r), dove k è il numero dei genomi, n è la loro lunghezza totale ed r è il numero di MEMs. Anche questa operazione è implementata attraverso l’uso di un albero dei suffussi.
Nella seconda fase, MGA calcola le ancore, che consistono nelle più lunghe sequenze senza overlapping che si presentano nel medesimo ordine in ognuno dei genomi. Nel caso peggiore questa operazione è compiuta in O(k*m^2).
Confronto tra i due metodi di allineamento (MUMs e MEMs):
Sebbene entrambi i programmi usino la medesima stuttura dati ad albero dei sufissi, le due applicazioni sviluppano diversi approcci per l’allineamento del genoma.
MUMmer estrae i “Maximal Unique Matches” (MUMs) – ovvero sequenze the occorrono esattamente una volta in ogni genoma, analizza queste sequenze per individuare il più lungo set di MUMs che si presenta in entrambe le sequenze nello stesso ordine, e quindi usa questo set come “ancora” per l’allinneamento multiplo. I gaps tra ancore sono riempiti usando l’algoritmo di allignamento dinamico di Needleman Wunsch. A causa di questo (il tempo e lo spazio richiesto cresce esponenzialmente con il numero delle stringhe), l’uso del MUMmer per lo più rimane ristretto al confronto fra due genomi.
Il limite maggiore dell’algoritmo su cui è basato il MUMmer è che match esatti presenti più di una volta in un genoma possono risultare significativi (come già osservato in precedenza). Inoltre l’algoritmo di HIS usato per concatenare i MUMs non è completamente adeguato perché la risultante catena di MUMs potrebbe contenere overlapping, che genererebbero un’inconsistenza dei risultati.
Questo limite è poi stato rimosso nella versione successiva del software, oltre al fatto che l’algoritmo nuova versione procede allo storaggio nell’albero dei suffissi di una sola sequenza (sequenza di riferimento), e la seconda viene comparata all’albero secondo la tecnica sviluppata da Chang & Lawer (“Sublinear expected time approssimate string matching and biological application”). Per ottimizzare i tempi di elaborazione infine vengono usati i suffix link
MGA, invece calcola la più lunga sequenza di MEMs senza overlapping e usa questa come guida per l’allineamto multiplo. Un MEM è definito come una (K+1)-tupla (l, p_0, p_1, … p_k-1) dove l indica la lunghezza del MEM, e p_i indica la coordinata di partenza del match esatto nel genoma I-esimo. Un MEM massimale non può essere esteso a destra o a sinistra. I gaps inoltre sono riempiti sfruttando ClustalW.
Appendice A: Definizioni ed algoritmi d’implementazione
Un albero dei suffissi è una struttura dati che -per sua natura- evidenzia la struttura di una stringa di caratteri, dandone una rappresentazione interna, mediante i suoi suffissi.
In modo più rigoroso possiamo dire che la sua definizione ne caratterizza le parti da cui è composto:
- Un albero dei suffissi per una stringa di caratteri S di m elementi, è un albero direzionato con esattamente m foglie numerate da 1 ad m, che rappresentano la posizione iniziale del suffisso che termina su quella determinata foglia.
- Ogni nodo interno ha almeno due figli, e ogni arco è etichettato con una sottostringa non vuota di S
- La concatenazione delle labels degli archi percorsi dalla radice fino alla foglia determinano l’esatto suffisso che comincia dalla posizione indicata dalla foglia stessa
Si noti che: Se un suffisso s’ della stringa S è anche prefisso di un altro suffisso s, non vengono rispettate le proprietà dell’albero. Per impedire tale problema si fa terminare ogni stringa con un simbolo che non compare in nessun’altra posizione (una sorta di sentinella, informaticamente parlando) che permette di evitare situazioni equivoche.
Il primo algoritmo per la costruzione di alberi dei suffissi in tempi lineari è stato sviluppato da Weiner nel 1973. Un più efficente algoritmo per la la riduzione dello spazio necessario è stato introdotto da McCreight nel 1976, e per finire Ukkonen (1995) produsse una variante “on-line” di McCreight che semplifica molto la procedura, sebbene sia intrinsecamente meno efficiente. Esso viene ottimizzato attraverso 3 tecniche/osservazioni che riducono la necessità di scorrere i vari archi dell’albero in fase di lettura e/o estensione dell’albero.
Definiamo un albero implicito di una stringa S come un albero ottenuto dall’albero di S$ ma rimuovendo ogni coppia del simbolo terminale, e rimuovendo ogni nodo che non ha almeno due fi
Ukkonen definì un algoritmo in grado di costruire una sequenza di alberi impliciti, uno per ogni prefisso s[1…i]. Incrementando di passo in passo l’albero implicito (per i che va da 1 ad m) si riesce a costruire l’albero dei suffissi della stringa S di lunghezza m. Il tempo per costruire tale albero è pari a O(m^2) .
L’algoritmo inizia con un albero implicito contenente il primo carattere della stringa. Quindi gli step successivi constano in aggiunte successive di caratteri finchè l’albero non è completo.
Ad ogni passo dell’estensione dei rami dell’albero vengono seguite 3 regole:
- Se non esiste un arco che comincia con il prefisso che voglio collocare creo un nuovo arco a partire dalla radice
- Se esiste già una foglia, aggiorno l’arco aggiungendo alla fine dell’etichetta corrispondente il carattere nuovo
- Se c’è già non faccio nulla (non inserisco archi terminali $).
Per un immediato e certo più comprensibile esempio grafico si veda l’appendice B
Una trattazione completa per “Building Suffix Trees in O(m) time” è consultabile alla pagina web http://homepage.usask.ca/~ctl271/857/suffix_tree.shtml (una presentazione powerpoint step by step).
Questa implementazione naive dell’algoritmo richiede nel caso peggiore un tempo O(m^2), infatti ogni volta che si deve estendere l’albero occorre, secondo questi presupposti ripercorrere tutti gli archi fino alle foglie.
Sono state allora introdotte delle implementazioni che accelerano il processo (definiti tricks).
1. Il primo trick è il concetto di Suffix link. Per un nodo v con label generica x-alfa, se esiste un altro nodo s(v) con label uguale ad alfa, allora posso creare un link tra v e s(v), una sorta di puntatore, o percorso alternativo che mi permette di passare direttamente da un nodo all’altro.
L’algoritmo di Ukkonen quindi per ogni nuovo nodo creato presenterà un suffix link da esso fino alla fine dell’estensione successiva. I suffix links permettono quindi estensioni dell’albero senza dover ripartire dalla radice perchè essi puntano direttamente alla prossima estensione.
- Il secondo concetto per migliorare i tempi di calcolo è lo Skip/count . Si basa sul concetto di profondità dei nodi, come mostrato in figura.
Sulla base dell’osservazione che la profondità di nodo di v sarà sempre superiore di quella di s(v), si può effettivamente ridurre il tempo di lettura dei vari archi fino ad O(m), in quanto non sarà più necessario leggere tutti i rami ma saltare da un nodo all’altro.
- Infine per ridurre lo spazio di memoria necessario per memorizzare l’albero dei suffissi si può pensare di ricorrere all’edge label compression. Ovvero non associare più ad ogni arco la corrispettiva sottostringa, ma etichettare ogni arco con una coppia di indici [i,j] che individuano la posizione e la lunghezza della sottostringa all’interno della stringa di partenza.
Sfruttando questi tre accorgimenti è possibile ridurre il tempo di costruzione dell’albero, il tempo di percorrenza e lo spazio necessario a O(m).
Può essere utile introdurre un’ultima definizione prima di passare a discutere le possibili applicazioni, ovvero l’albero generalizzato, che viene utilizzato quando occorre fare operazioni su più di una singola stringa. In tale albero, ogni foglia rappresenta sia un suffisso di una delle due stringhe, sia un suffisso che occorre in entrambe le stringhe. Inoltre ogni nodo interno v è marcato con 1 (o 2) dipendentemente se esiste una foglia nel sotto albero di v che rappresenta la stringa S1 (o S2). Un albero generalizzato può essere costruito in un tempo O(m1+m2) dove m1 e m2 sono la lunghezza delle due stringhe
Appendice B: esempio di Implementazione di albero dei suffissi secondo Ukkonen
