Indicele FM

În informatică , un indice FM este o compresie fără pierderi bazată pe Transformarea Burrows-Wheeler , cu unele asemănări cu Tabelul Sufixelor . Această metodă de compresie a fost creată de Paolo Ferragina și Giovanni Manzini, care o descriu ca un algoritm multifuncțional bazat pe o structură de date inteligentă. Numele vine de la „ F indicele ull text în M spațiu inute “ .

Acest algoritm poate fi utilizat, pe lângă compresie, pentru a găsi eficient numărul de apariții ale unui model în textul comprimat, precum și pentru a localiza poziția fiecărei apariții a modelului în textul comprimat. Atât timpul cât și spațiul de stocare necesare au o complexitate subliniară în comparație cu dimensiunea datelor de intrare. Adică, timpul de execuție și spațiul de stocare necesar nu sunt proporționale cu dimensiunea datelor de intrare.

Autorii au dezvoltat îmbunătățiri la abordarea lor originală și au denumit această nouă metodă de compresie „FM-Index versiunea 2”. O altă îmbunătățire, FM „prietenoasă cu alfabetul”, combină utilizarea stimulării compresiei și a undelor pentru a reduce dramatic utilizarea spațiului atunci când se utilizează alfabete mari.

Indicele FM a fost utilizat printre altele în bioinformatică .

Cadru

Utilizarea unui index este o strategie comună pentru căutarea eficientă a unui corp mare de text. Când textul este mai mare decât poate păstra memoria principală a computerului, este necesar să comprimați nu numai textul, ci și indexul. Când a fost introdus indicele FM, au fost deja sugerate mai multe soluții pentru atingerea acestui obiectiv dublu. S-au bazat pe metode tradiționale de compresie, care au încercat, de asemenea, să rezolve problema compresiei indexului. În schimb, indexul FM folosește un indice comprimat nativ, ceea ce înseamnă că este capabil simultan să comprime date și să indexeze.

Structuri de index FM

Un index FM se creează luând mai întâi Transformarea Burrows-Wheeler (BWT) a textului de intrare. De exemplu, BWT al șirului $T =$ "abracadabra" este "ard $ rcaaaabb", iar aici este reprezentat de matricea $M$ unde fiecare rând este o rotație a textului, iar rândurile au fost sortate lexicografic. Transformarea este ultima coloană marcată $L$ .

$Eu$	$F$		$L$
1	$	abracadabr	la
2	la	$ abracadab	r
3	la	bra $ abraca	d
4	la	bracadabra	$
5	la	cadabra $ ab	r
6	la	dabra $ abra	vs.
7	b	ra $ abracad	la
8	b	racadabra $	la
9	vs.	adabra $ abr	la
10	d	abra $ abrac	la
11	r	a $ abracada	b
12	r	acadabra $ a	b

BWT în sine permite compresia cu, de exemplu, schimbarea înainte și codificarea Huffman , dar transformarea în alte utilizări. Rândurile matricei sunt în principiu sufixurile sortate ale textului, iar prima coloană F a matricei are similarități cu Tabelul sufixelor . Această legătură între tabela de sufixe și BWT se află în centrul indexului FM.

Este posibil să se facă un tabel de corespondență între ultima și prima coloană $LF (i) de$ la un index i la un index $j$ , cum ar fi $F [j]$ = $L [i]$ , cu ajutorul unui tabel $C [c]$ și $„OCC (c, k)$ .

$C [c]$ este un tabel care, pentru fiecare caracter $c$ din alfabet, conține numărul de apariții de caractere mai mici din punct de vedere lexical care sunt conținute în text.
Funcția $OCC (c, k)$ este numărul de apariții ale caracterului $c$ din prefixul $"L [1..k]$ . Ferragina și Manzini au arătat că este posibil să se calculeze $OCC (c, k)$ în constantă de timp.

C [c]

din „ard $ rcaaaabb”

$vs.$	$	la	b	vs.	d	r
$CC]$	0	1	6	8	9	10

Tabelul de corespondență dintre ultima și prima coloană poate fi definit acum ca $LF (i) = C [L [i]] + Occ (L [i], i)$ . De exemplu, în rândul 9, $L$ este „a” și aceleași „a” sunt pe rândul 5 din prima coloană $F$ , deci $LF (9)$ ar trebui să fie 5 și $LF (9) = C [a] + Occ (a , 9) = 5$ . Pentru orice rând $i$ al matricei, caracterul din ultima coloană $L [i]$ precede caracterul din prima coloană $F [i]$ și în T. În cele din urmă, dacă $L [i] = T [k]$ , atunci $L [LF (i)] = T [k - 1]$ , și folosind egalitatea, este posibil să se extragă un șir $T$ de $l$ .

Indicele FM în sine este o compresie a lanțului $L$ cu $C$ și $OCC$ , dar și informații care mapează o selecție de indici în $formă$ de $L$ la pozițiile din lanțul $T$ original .

Occ (c, k)

din „ard $ rcaaaabb”

	la	r	d	$	r	vs.	la	la	la	la	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
la	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
vs.	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

Numara

Operațiunea conta are un model $P [1..p]$ și returnează numărul de apariții ale modelului în original $T$ . Deoarece rândurile matricei $M$ sunt sortate și conțin fiecare sufix al lui $T$ , aparițiile modelului $P$ vor fi una lângă alta într-un singur interval continuu. Această operație se repetă în mod retrograd pe model. Pentru fiecare caracter din model, se găsește setul de rânduri care are acel caracter ca sufix. De exemplu, căutarea modelului „sutien” în „abracadabra” urmează pașii următori:

Primul personaj pe care îl căutăm este „ $a$ ”, ultimul caracter din model. Setul inițial de rânduri este definit ca $[C [a] + 1..C [a + 1] = [2..6]$ . Acest set de linii peste $L$ reprezintă fiecare caracter din $T$ , care are un sufix care începe cu a .
Următorul personaj de căutat este $r$ . Noul set de rânduri este $[C [r] + Occ (r, start-1) + Occ (r, end), 1..C [r]] =$ $[10 + 0 + 1..10 + 2] =$ $[11..12]$ , dacă $start$ este indicele de $început$ al intervalului și $sfârșitul$ este sfârșitul. Acest set de linii de pe $L$ conține toate caracterele din $T$ care au sufixe începând cu ra .
Ultimul personaj de luat în considerare este $b$ . Noul set de rânduri este $[C [b] + Occ (b, start-1) + 1..C [b] + Occ (b, end)] =$ $[6 + 0 + 1..6 + 2] =$ $[7..8]$ . acest set de linii pe $L$ este format din toate caracterele care au un sufix începând cu sutien . Acum că întregul model este procesat, numărul este același cu dimensiunea intervalului: $8-7 + 1 = 2$ .

În cazul în care intervalul este gol sau în cazul în care limitele setului de linii se intersecteaza , înainte de întregul model este investigat, acest lucru înseamnă că modelul nu are loc în $T$ . Deoarece $OCC (c, k)$ poate fi efectuat în timp constant, numărarea poate fi efectuată în timp liniar proporțional cu lungimea modelului: $Timpul lui O (p)$ .

Localiza

Operațiunea de descoperire are ca intrare un index al unui caracter în $L$ și returnează poziția $I$ în $T$ . De exemplu, $localizați (7) = 8$ . Pentru a găsi toate aparițiile unui model, trebuie mai întâi să găsiți gama de caractere al căror sufix este modelul, în același mod ca și pentru operația de numărare . Apoi poate fi găsită poziția fiecărui personaj din gamă.

Pentru a mapa un index în $L$ într - un index în $T$ , un subset al indicilor $L$ este asociat cu o poziție în $T$ . Dacă $L [j]$ are o poziție asociată, găsirea $localizării (j)$ este banală. Dacă nu există poziții asociate, căutarea continuă pe șir cu $LF (i)$ până când se găsește un index asociat. Prin asocierea unui număr adecvat de indici, se va găsi o limită superioară. Find operație poate fi implementată pentru a găsi aparițiile occ $P [1..p]$ într - un text $T [1..u]$ în $O (p + occ log ε u)$ timp cu biți pe simbol de intrare pentru orice $k \geq 0$ . ${\ displaystyle O (H_ {k} (T) + {{\ log \ log u} \ over {\ log ^ {\ epsilon} u}})}$

Aplicații

Cartarea citirii ADN-ului

Indicele FM cu feedback a fost aplicat cu succes (> 2000 de citate) alinierii secvenței genomice, vezi http://bowtie-bio.sourceforge.net/index.shtml p ...

Note și referințe

Paolo Ferragina și Giovanni Manzini (2000). "Structuri de date oportuniste cu aplicații". Lucrările celui de-al 41-lea Simpozion anual privind fundamentele științei computerizate. p. 390 .
Numele poate înseamnă, de asemenea, indexul lui F erragina și M anzini?
Paolo Ferragina și Giovanni Manzini (2005). "" Indexarea textului comprimat "", Jurnalul ACM , 52, 4, (iul. 2005). p. 553- .
Paolo Ferragina și Rossano Venturini „FM-Index versiunea 2”
P. Ferragina, G. Manzini, V. Mäkinen și G. Navarro. Un indice FM prietenos cu alfabetul. În Proc. SPIRE'04, paginile 150-160. LNCS 3246.
Simpson, Jared T. și Durbin, Richard (2010). "Construcția eficientă a unui grafic de șir de asamblare utilizând indexul FM". Bioinformatică, 26, 12 (17 iunie). p. i367.