Indice FM
In informatica , un indice FM è una compressione senza perdite basata sulla trasformazione di Burrows-Wheeler , con alcune somiglianze con la tabella dei suffissi . Questo metodo di compressione è stato creato da Paolo Ferragina e Giovanni Manzini, che lo descrivono come un algoritmo multiuso basato su un'elegante struttura dati. Il nome sta per " F index ull-testo in M spazio inuti " .
Questo algoritmo può, oltre alla compressione, essere utilizzato per trovare in modo efficiente il numero di occorrenze di un pattern nel testo compresso, nonché per individuare la posizione di ciascuna occorrenza del pattern nel testo compresso. Sia il tempo che lo spazio di archiviazione richiesti hanno una complessità sublineare rispetto alla dimensione dei dati di input. Ovvero, il tempo di esecuzione e lo spazio di archiviazione richiesti non sono proporzionali alla dimensione dei dati di input.
Gli autori hanno sviluppato miglioramenti al loro approccio originale e hanno chiamato questo nuovo metodo di compressione "FM-Index versione 2". Un altro miglioramento, FM "alfabetico", combina l'uso della stimolazione della compressione e delle wavelet per ridurre drasticamente l'utilizzo dello spazio quando si utilizzano alfabeti di grandi dimensioni.
L'indice FM è stato utilizzato tra l'altro in bioinformatica .
Telaio
L'utilizzo di un indice è una strategia comune per cercare in modo efficiente un grande corpo di testo. Quando il testo è più grande della memoria principale del computer, è necessario comprimere non solo il testo, ma anche l'indice. Quando è stato introdotto l'indice FM, erano già state suggerite diverse soluzioni per raggiungere questo duplice obiettivo. Si basavano su metodi di compressione tradizionali che cercavano anche di risolvere il problema della compressione dell'indice. Al contrario, FM-index utilizza un indice compresso in modo nativo, il che significa che è contemporaneamente in grado di comprimere dati e indicizzare.
Strutture FM-index
Un indice FM viene creato prendendo prima la trasformazione Burrows-Wheeler (BWT) del testo di input. Ad esempio, il BWT della stringa T = "abracadabra" è "ard $ rcaaaabb", e qui è rappresentato dalla matrice M dove ogni riga è una rotazione del testo e le righe sono state ordinate lessicograficamente. La trasformazione è l'ultima colonna etichettata L .
| io | F | L | |
|---|---|---|---|
| 1 | $ | abracadabr | a |
| 2 | a | $ abracadab | r |
| 3 | a | reggiseno $ abraca | d |
| 4 | a | bracadabra | $ |
| 5 | a | cadabra $ ab | r |
| 6 | a | dabra $ abra | vs |
| 7 | b | ra $ abracad | a |
| 8 | b | racadabra $ | a |
| 9 | vs | adabra $ abr | a |
| 10 | d | abra $ abrac | a |
| 11 | r | a $ abracada | b |
| 12 | r | acadabra $ a | b |
Lo stesso BWT consente la compressione con, ad esempio, lo spostamento in avanti e la codifica Huffman , ma la trasformazione in altri usi. Le righe della matrice sono fondamentalmente i suffissi ordinati del testo e la prima colonna F della matrice ha somiglianze con la Tabella dei suffissi . Questo collegamento tra la tabella dei suffissi e il BWT è il cuore dell'indice FM.
|
È possibile fare una tabella di corrispondenza tra l'ultima e la prima colonna LF (i) da un indice i a un indice j , come F [j] = L [i] , con l'aiuto di una tabella C [c] e "OCC (c, k) .
|
|
|
La tabella di corrispondenza tra l'ultima e la prima colonna può ora essere definita come LF (i) = C [L [i]] + Occ (L [i], i) . Ad esempio, nella riga 9, L è "a" e la stessa "a" si trova nella riga 5 nella prima colonna F , quindi LF (9) dovrebbe essere 5 e LF (9) = C [a] + Occ (a , 9) = 5 . Per ogni riga i della matrice, il carattere nell'ultima colonna L [i] precede il carattere nella prima colonna F [i] anche in T. Infine, se L [i] = T [k] , allora L [LF (i)] = T [k - 1] , e usando l'uguaglianza, è possibile estrarre una stringa T di L . Lo stesso indice FM è una compressione della catena L con C e OCC , ma anche informazioni che associano una selezione di indici a forma di L a posizioni nella catena T originale . |
|
Contare
Il conteggio dell'operazione prende un pattern P [1..p] e restituisce il numero di occorrenze del pattern nella T originale . Poiché le righe della matrice M sono ordinate e contengono ciascun suffisso di T , le occorrenze del modello P saranno affiancate in un unico intervallo continuo. Questa operazione viene ripetuta in modo retrogrado sullo schema. Per ogni carattere nel motivo, viene trovato l'insieme di righe che ha quel carattere come suffisso. Ad esempio, la ricerca del motivo "reggiseno" in "abracadabra" segue i seguenti passaggi:
- Il primo carattere che stiamo cercando è " a ", l'ultimo carattere nello schema. L'insieme iniziale di righe è definito come [C [a] + 1..C [a + 1] = [2..6] . Questo insieme di righe su L rappresenta ogni carattere in T , che ha un suffisso che inizia con a .
- Il prossimo personaggio da cercare è r . Il nuovo insieme di righe è [C [r] + Occ (r, start-1) + Occ (r, end), 1..C [r]] = [10 + 0 + 1..10 + 2] = [11..12] , se inizio è l'indice iniziale dell'intervallo e fine è la fine. Questo insieme di righe su L contiene tutti i caratteri in T che hanno suffissi che iniziano con ra .
- L'ultimo personaggio da guardare è b . Il nuovo insieme di righe è [C [b] + Occ (b, start-1) + 1..C [b] + Occ (b, end)] = [6 + 0 + 1..6 + 2] = [7..8] . questo insieme di linee su L è composto da tutti i caratteri che hanno un suffisso che inizia con reggiseno . Ora che l'intero modello è stato elaborato, il conteggio è lo stesso della dimensione dell'intervallo: 8-7 + 1 = 2 .
Se l'intervallo è vuoto o se i limiti della serie di linee incrociano prima che l'intero modello è indagato, ciò significa che il disegno non si verifica in T . Poiché OCC (c, k) può essere eseguito a tempo costante, il conteggio può essere eseguito in tempo lineare proporzionale alla lunghezza del pattern: Tempo di O (p) .
Individuare
L'operazione find prende in ingresso un indice di un personaggio in L e restituisce la sua posizione i in T . Ad esempio, individuare (7) = 8 . Per trovare tutte le occorrenze di un modello, devi prima trovare l'intervallo di caratteri il cui suffisso è il modello, allo stesso modo dell'operazione di conteggio . Quindi è possibile trovare la posizione di ciascun carattere nell'intervallo.
Per mappare un indice a L in un indice in T , un sottoinsieme di indici L è associato ad una posizione in T . Se L [j] ha una posizione associata, trovare locate (j) è banale. Se non ci sono posizioni associate, la ricerca continua sulla stringa con LF (i) fino a quando non viene trovato un indice associato. Associando un numero adeguato di indici si troverà un limite superiore. L'operazione di ricerca può essere implementata per trovare le occorrenze di occ P [1..p] in un testo T [1..u] in tempo O (p + occ log ε u) con bit per simbolo di input per ogni k ≥ 0 .
Applicazioni
Mappatura della lettura del DNA
L'indice FM con feedback è stato applicato con successo (> 2000 citazioni) all'allineamento della sequenza genomica, vedere http://bowtie-bio.sourceforge.net/index.shtml p ...
Note e riferimenti
- Paolo Ferragina e Giovanni Manzini (2000). "Strutture dati opportunistiche con applicazioni". Atti del 41 ° simposio annuale sui fondamenti dell'informatica. p. 390 .
- Il nome forse significa anche indice di F erragina e M anzini?
- Paolo Ferragina e Giovanni Manzini (2005). "" Indexing Compressed Text "", Journal of the ACM , 52, 4, (luglio 2005). p. 553- .
- Paolo Ferragina e Rossano Venturini “FM-Index version 2”
- P. Ferragina, G. Manzini, V. Mäkinen e G. Navarro. Un indice FM compatibile con l'alfabeto. In Proc. SPIRE'04, pagine 150-160. LNCS 3246.
- Simpson, Jared T. e Durbin, Richard (2010). "Costruzione efficiente di un grafo di stringhe di assemblaggio utilizzando l'indice FM". Bioinformatica, 26, 12 (17 giugno). p. i367.