Indeks FM

W informatyce indeks FM to skompresowany pełnotekstowy indeks podciągów oparty na transformacji Burrowsa-Wheelera , z pewnymi podobieństwami do tablicy sufiksów . Został stworzony przez Paolo Ferraginę i Giovanniego Manziniego, którzy opisują go jako oportunistyczną strukturę danych, ponieważ umożliwia kompresję tekstu wejściowego, jednocześnie umożliwiając szybkie zapytania podciągów. Nazwa oznacza indeks pełnotekstowy w przestrzeni minutowej.

Można go użyć do efektywnego znalezienia liczby wystąpień wzorca w skompresowanym tekście, a także zlokalizowania pozycji każdego wystąpienia. Czas zapytania, jak również wymagana przestrzeń dyskowa , mają podliniową złożoność w odniesieniu do rozmiaru danych wejściowych.

Oryginalni autorzy opracowali ulepszenia swojego oryginalnego podejścia i nazwali je „FM-Index version 2”. Kolejne ulepszenie, przyjazny dla alfabetu indeks FM, łączy wykorzystanie wzmocnienia kompresji i drzew falkowych , aby znacznie zmniejszyć wykorzystanie miejsca na duże alfabety.

Indeks FM znalazł zastosowanie między innymi w bioinformatyce .

Tło

Korzystanie z indeksu jest powszechną strategią efektywnego przeszukiwania dużej części tekstu. Kiedy tekst jest większy niż to, co rozsądnie mieści się w pamięci głównej komputera, istnieje potrzeba skompresowania nie tylko tekstu, ale także indeksu. Kiedy wprowadzono indeks FM, zaproponowano kilka rozwiązań, które były oparte na tradycyjnych metodach kompresji i próbowały rozwiązać problem dopasowywania skompresowanych danych. Natomiast indeks FM jest skompresowanym indeksem własnym, co oznacza, że jednocześnie kompresuje dane i indeksuje je.

Struktura danych indeksu FM

Indeks FM jest tworzony przez uprzednie pobranie transformaty Burrowsa-Wheelera (BWT) tekstu wejściowego. Na przykład BWT łańcucha $T =$ „abracadabra $” to „ard $ rcaaaabb”, a tutaj jest reprezentowany przez macierz $M$ , w której każdy wiersz jest obrotem tekstu, a wiersze zostały posortowane leksykograficznie. Transformacja odpowiada ostatniej kolumnie oznaczonej $L$ .

$I$	$F$		$Ł$
1	$	abrakadabr	A
2	A	$abrakadab	R
3	A	stanik	D
4	A	bracadabra	$
5	A	cadabra$ab	R
6	A	dabra$abra	C
7	B	ra$abracad	A
8	B	racadabra $	A
9	C	adabra$abr	A
10	D	abra$abrac	A
11	R	a$abracada	B
12	R	acadabra$a	B

Sam BWT pozwala na pewną kompresję, na przykład move to front i Huffman encoding , ale transformacja ma jeszcze więcej zastosowań. Wiersze w macierzy są zasadniczo posortowanymi sufiksami tekstu, a pierwsza kolumna F macierzy jest podobna do tablic sufiksów . To, w jaki sposób tablica sufiksów odnosi się do BWT, leży u podstaw indeksu FM.

Możliwe jest wykonanie odwzorowania kolumny od ostatniej do pierwszej kolumny $LF(i)$ z indeksu $i$ na indeks $j$ , tak że $F[j]$ = $L[i]$ , za pomocą tabeli $C[c]$ i funkcja $Occ(c, k)$ .

$C[c]$ to tabela, która dla każdego znaku $c$ w alfabecie zawiera liczbę wystąpień leksykalnie mniejszych znaków w tekście.
Funkcja $Occ(c, k)$ to liczba wystąpień znaku $c$ w prefiksie $L[1..k]$ . Ferragina i Manzini wykazali, że możliwe jest obliczenie $Occ(c, k)$ w czasie stałym.

$C[c]$ „ard$rcaaaabb”
$C$	$	A	B	C	D	R
$C[c]$	0	1	6	8	9	10

Mapowanie od ostatniego do pierwszego można teraz zdefiniować jako $LF(i) = C[L[i]] + Occ(L[i], i)$ . Na przykład w wierszu 9 $L$ to $a$ i to samo $a$ można znaleźć w wierszu 5 w pierwszej kolumnie $F$ , więc $LF(9)$ powinno wynosić 5, a $LF(9) = C[a] + Occ(a, 9 ) = 5$ . Dla dowolnego $i$ wiersza macierzy znak w ostatniej kolumnie $L[i]$ poprzedza znak w pierwszej kolumnie $F[i]$ również w T. Wreszcie, jeśli $L[i] = T[k]$ , to $L[LF (i)] = T[k - 1]$ , a za pomocą równości można wyodrębnić ciąg $T$ z $L$ .

Sam indeks FM jest kompresją łańcucha $L$ wraz z $C$ i $Occ$ w jakiejś formie, a także informacją, która odwzorowuje wybrane indeksy w $L$ na pozycje w oryginalnym łańcuchu $T$ .

$Occ(c, k)$ z "ard$rcaaaabb"
	A	R	D	$	R	C	A	A	A	A	B	B
	1	2	3	4	5	6	7	8	9	10	11	12
$	0	0	0	1	1	1	1	1	1	1	1	1
A	1	1	1	1	1	1	2	3	4	5	5	5
B	0	0	0	0	0	0	0	0	0	0	1	2
C	0	0	0	0	0	1	1	1	1	1	1	1
D	0	0	1	1	1	1	1	1	1	1	1	1
R	0	1	1	1	2	2	2	2	2	2	2	2

Liczyć

Licznik operacji przyjmuje wzorzec $P[1..p]$ i zwraca liczbę wystąpień tego wzorca w oryginalnym tekście $T$ . Ponieważ wiersze macierzy $M$ są posortowane i zawiera ona każdy sufiks $T$ , wystąpienia wzorca $P$ będą obok siebie w jednym ciągłym zakresie. Operacja wykonuje iterację wstecz nad wzorcem. Dla każdego znaku we wzorcu zostanie znaleziony zakres, w którym ten znak jest sufiksem. Na przykład liczba wzorów „stanik” w „abracadabra” przebiega w następujący sposób:

Pierwszym znakiem, którego szukamy jest $,$ ostatni znak we wzorcu. Początkowy zakres jest ustawiony na $[C[a] + 1..C[a+1]] = [2..6]$ . Ten zakres powyżej $L$ reprezentuje każdy znak $T$ , który ma sufiks rozpoczynający się od .
Następnym znakiem do wyszukania jest $r$ . Nowy zakres to $[C[r] + Occ(r, start-1) + 1..C[r] + Occ(r, end)] =$ $[10 + 0 + 1..10 + 2] =$ $[11 ..12]$ , jeśli $start$ jest indeksem początku zakresu, a $end$ jest końcem. Ten zakres powyżej $L$ to wszystkie znaki $T$ , które mają sufiksy zaczynające się od ra .
Ostatnią postacią, na którą należy zwrócić uwagę, jest $b$ . Nowy zakres to $[C[b] + Occ(b, start-1) + 1..C[b] + Occ(b, end)] =$ $[6 + 0 + 1..6 + 2] =$ $[7 ..8]$ . Ten zakres powyżej $L$ to wszystkie znaki, które mają sufiks rozpoczynający się od bra . Teraz, gdy cały wzór został przetworzony, liczba jest taka sama jak rozmiar zakresu: $8 - 7 + 1 = 2$ .

Jeśli zakres staje się pusty lub granice zakresu przecinają się przed wyszukaniem całego wzorca, wzorzec nie występuje w $T$ . Ponieważ $Occ(c, k)$ można wykonać w czasie stałym, liczenie może zakończyć się w czasie liniowym na długości wzorca: czas $O(p) .$

Znajdź

Operacja zlokalizowania przyjmuje jako dane wejściowe indeks znaku w $L$ i zwraca jego pozycję $i$ w $T$ . Na przykład $zlokalizuj(7) = 8$ . Aby zlokalizować każde wystąpienie wzorca, najpierw znajduje się zakres znaku, którego sufiks jest wzorcem w ten sam sposób, w jaki operacja zliczania znalazła zakres. Następnie można zlokalizować pozycję każdego znaku w zakresie.

Aby odwzorować indeks w $L$ na jeden w T $,$ podzbiór indeksów w $L$ jest powiązany z pozycją w $T.$ Jeśli $L[j]$ ma skojarzoną z nim pozycję, $zlokalizuj(j)$ jest trywialne. Jeśli nie jest powiązany, po łańcuchu występuje $LF(i),$ aż do znalezienia powiązanego indeksu. Łącząc odpowiednią liczbę wskaźników, można znaleźć górną granicę. Locate można zaimplementować, aby znaleźć occ wystąpienia wzorca $P[1..p]$ w tekście $T[1..u]$ w czasie $O(p + occ log ε u)$ z ${\ Displaystyle O \ lewo (H_ {k} (T) + {{\ log \ log u} \ ponad {\ log ^ {\ epsilon} u}} \ prawej)} bitów$ na symbol wejścia dla dowolnego $k \geq 0$ .

Aplikacje

Mapowanie odczytu DNA

Indeks FM ze śledzeniem wstecznym został pomyślnie zastosowany (> 2000 cytowań) do przybliżonego dopasowania ciągów / wyrównania sekwencji, patrz Bowtie http://bowtie-bio.sourceforge.net/index.shtml

Zobacz też