FM endeksi

Gelen bilgisayar bilimleri , bir FM-endeksi dayalı bir kayıpsız sıkıştırma olduğunu Burrows-Wheeler Transform bazı benzerlikler ile, son ekler Tablo . Bu sıkıştırma yöntemi, onu şık bir veri yapısına dayalı çok amaçlı bir algoritma olarak tanımlayan Paolo Ferragina ve Giovanni Manzini tarafından oluşturuldu. Adı açılımı " F içinde ull metin dizini M inute alanı " .

Bu algoritma, sıkıştırmaya ek olarak, sıkıştırılmış metindeki bir desenin görülme sayısını verimli bir şekilde bulmak ve ayrıca sıkıştırılmış metindeki desenin her bir oluşumunun konumunu bulmak için kullanılabilir. Hem zaman hem de depolama alanı, girdi verilerinin boyutuna kıyasla alt doğrusal karmaşıklığa sahiptir. Yani, gereken yürütme süresi ve depolama alanı, giriş verilerinin boyutuyla orantılı değildir.

Yazarlar, orijinal yaklaşımlarında iyileştirmeler geliştirdiler ve bu yeni sıkıştırma yöntemini "FM-Index sürüm 2" olarak adlandırdılar. Diğer bir iyileştirme olan "alfabe dostu" FM, büyük alfabe kullanırken alan kullanımını önemli ölçüde azaltmak için sıkıştırma uyarımı ve dalgacıkların kullanımını birleştirir .

FM indeksi, biyoinformatikte diğer şeylerin yanı sıra kullanılmıştır .

Çerçeve

Dizin kullanmak, büyük bir metin gövdesini verimli bir şekilde aramak için yaygın bir stratejidir. Metin, bilgisayarın ana belleğinin tutabileceğinden daha büyük olduğunda, yalnızca metni değil dizini de sıkıştırmak gerekir. FM endeksi tanıtıldığında, bu ikili hedefe ulaşmak için halihazırda birkaç çözüm önerilmişti. İndeks sıkıştırma problemini de çözmeye çalışan geleneksel sıkıştırma yöntemlerine dayanıyorlardı. Bunun aksine, FM-indeksi doğal olarak sıkıştırılmış bir indeks kullanır, bu da eş zamanlı olarak verileri sıkıştırıp indeksleyebildiği anlamına gelir.

FM indeks yapıları

İlk olarak giriş metninin Burrows-Wheeler Dönüşümü (BWT) alınarak bir FM-indeksi oluşturulur . Örneğin, $T =$ "abracadabra" dizesinin BWT'si "ard $ rcaaaabb" dir ve burada, her satırın metnin bir dönüşü olduğu ve satırların sözlüksel olarak sıralandığı $M$ matrisi ile temsil edilir . Dönüşüm, $L$ etiketli son sütundur .

$ben$	$F$		$L$
1	$	abrakadabr	-de
2	-de	$ abracadab	r
3	-de	sutyen $ abraca	d
4	-de	bracadabra	$
5	-de	kadabra $ ab	r
6	-de	dabra $ abra	vs
7	b	ra $ abracad	-de
8	b	racadabra $	-de
9	vs	adabra $ abr	-de
10	d	abra $ abrac	-de
11	r	a $ abracada	b
12	r	acadabra $ a	b

BWT'nin kendisi, örneğin ileri kaydırma ve Huffman kodlamasıyla sıkıştırmaya izin verir , ancak diğer kullanımlara dönüştürülür. Matrisin satırları temelde metnin sıralı son ekleridir ve matrisin ilk F sütunu son eklerin Tablosu ile benzerliklere sahiptir . Son ek tablosu ile BWT arasındaki bu bağlantı, FM endeksinin merkezindedir.

Bir $C [c]$ tablosu yardımıyla, $i$ indeksinden $F [j]$ = $L [i]$ gibi bir $j$ indeksine son ve ilk sütun $LF (i)$ arasında bir yazışma tablosu yapmak mümkündür. ve $"OCC (c, k)$ .

$C [c]$ , alfabedeki her $c$ karakteri için , metinde yer alan sözcüksel olarak daha küçük karakter oluşumlarının sayısını içeren bir tablodur .
$OCC (c, k)$ fonksiyonu $,$ $"L [1..k]$ önekindeki $c$ karakterinin oluşum sayısıdır . Ferragina ve Manzini , zaman sabitinde $OCC (c, k) '$ yi hesaplamanın mümkün olduğunu göstermiştir .

"Ard $ rcaaaabb" nin

C [c]

$vs$	$	-de	b	vs	d	r
$CC]$	0	1	6	8	9	10

Son ve ilk sütun arasındaki yazışma tablosu artık $LF (i) = C [L [i]] + Occ (L [i], i) olarak tanımlanabilir$ . Örneğin, 9. satırda $L$ , 'a' ve aynı 'a', ilk $F$ sütununda 5. $satırdadır$ , bu nedenle $LF (9)$ 5 olmalı ve $LF (9) = C [a] + Occ (a , 9) = 5$ . Bir satır için $i$ matris, son sütununda karakteri $L [i]$ önce gelir, birinci sütunda karakter $F [i] '$ de T. Son olarak, eğer $L [i] = durumunda T [k]$ , daha sonra $L [LF (i)] kullanılarak, T [k = 1 -]$ ve eşitliği kullanarak, bir dizi elde etmek mümkündür $T$ arasında $L$ .

FM indeksinin kendisi, $L$ zincirinin $C$ ve $OCC$ ile sıkıştırılmasıdır , ancak aynı zamanda $L şeklindeki$ indekslerin bir seçimini orijinal $T$ zincirindeki konumlara eşleyen bilgidir .

"Ard $ rcaaaabb" için

Occ (c, k)

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

Miktar

İşlem sayısı bir model $P [1..p] alır$ ve orijinal $T'deki$ modelin gerçekleşme sayısını döndürür . $M$ matrisinin satırları sıralandığından ve $T'nin$ her sonekini içerdiğinden , $P$ modelinin oluşumları tek bir sürekli aralıkta yan yana olacaktır. Bu işlem, model üzerinde geriye dönük olarak tekrarlanır. Desendeki her karakter için, o karakteri bir sonek olarak içeren satırlar kümesi bulunur. Örneğin, "abracadabra" da "sütyen" kalıbının aranması aşağıdaki adımları izler:

Aradığımız ilk karakteri ' $bir$ desende', son karakteri. İlk satır kümesi $[C [a] + 1..C [a + 1] = [2..6] olarak tanımlanır$ . $L$ üzerindeki bu satır kümesi, $T'deki$ her bir karakteri temsil eder ve a ile başlayan bir son eki vardır .
Aranacak bir sonraki karakter $r$ . Yeni satır kümesi $[C [r] + Occ (r, start-1) + Occ (r, end), 1..C [r]] =$ $[10 + 0 + 1..10 + 2] =$ $[11..12]$ ; $başlangıç$ , aralığın $başlangıç$ $diziniyse$ ve $bitiş$ , $bitişse$ . $L$ üzerindeki bu satır kümesi, $T'de$ ra ile başlayan son eklere sahip tüm karakterleri içerir .
Bakılması gereken son karakter $b$ . Yeni satır kümesi $[C [b] + Occ (b, start-1) + 1. C [b] + Occ (b, end)] =$ $[6 + 0 + 1..6 + 2] =$ $[7..8]$ . $L$ üzerindeki bu satır dizisi, sütyen ile başlayan bir son eke sahip tüm karakterlerden oluşur . Artık tüm desen işlendiğine göre, sayı aralık boyutuyla aynıdır: $8-7 + 1 = 2$ .

Aralık boşsa veya çizgi kümesinin sınırları, tüm model incelenmeden önce birbirini kesiyorsa, bu, modelin $T'de$ gerçekleşmediği anlamına gelir . Olarak $OCC (c, k)$ : sabit zamanda yapılabilir, sayım desen uzunluğuna doğrusal bir zaman orantılı gerçekleştirilebilir $O (p) Zaman$ .

Bul

İşlem bulmak girdi olarak bir karakter, bir dizin alır $L$ ve konumunu geri $i$ de $T$ . Örneğin, $(7) = 8'i bulun$ . Bir desenin tüm oluşumlarını bulmak için, önce sayma işleminde olduğu gibi, son eki desen olan karakter aralığını bulmanız gerekir . Ardından aralıktaki her karakterin konumu bulunabilir.

Bir dizin eşlemek için $L$ bir endekste $T$ , endeks bir alt kümesi $, L$ içinde bir pozisyonda ile ilişkili $T$ . Eğer $L [j]$ ilişkili bir konuma sahiptir, bulgu $(j) bulun$ basittir. İlişkili konum yoksa, arama ilişkili bir indeks bulunana kadar $LF (i)$ ile dizide devam eder . Yeterli sayıda endeks ilişkilendirilerek, bir üst sınır bulunur. Bul işlemi tekrarlarını bulmak için uygulanabilecek oks $P [1..p]$ metindeki $T [1..u]$ içinde $, O (p + oks log ε u)$ ile zaman bir giriş sembol başına bit $k \geq 0$ . ${\ displaystyle O (H_ {k} (T) + {{\ log \ log u} \ {\ log ^ {\ epsilon} u}} üzerinden)}$

Başvurular

DNA okuma eşlemesi

Geri beslemeli FM indeksi, genomik sekans hizalamasına başarıyla uygulandı (> 2000 alıntı), bkz. Http://bowtie-bio.sourceforge.net/index.shtml p ...

Notlar ve referanslar

Paolo Ferragina ve Giovanni Manzini (2000). "Uygulamalar ile Fırsatçı Veri Yapıları". 41. Yıllık Bilgisayar Biliminin Temelleri Sempozyumu Bildirileri. s. 390 .
Adı belki de F erragina ve M anzini indeksi anlamına mı geliyor?
Paolo Ferragina ve Giovanni Manzini (2005). "" Sıkıştırılmış Metni İndeksleme "", Journal of the ACM , 52, 4, (Temmuz 2005). s. 553- .
Paolo Ferragina ve Rossano Venturini "FM-Index sürüm 2"
P. Ferragina, G. Manzini, V. Mäkinen ve G. Navarro. Alfabe Dostu FM endeksi. Proc. SPIRE'04, sayfalar 150-160. LNCS 3246.
Simpson, Jared T. ve Durbin, Richard (2010). "FM endeksini kullanarak bir montaj dizisi grafiğinin verimli bir şekilde oluşturulması". Bioinformatics, 26, 12 (17 Haziran). s. i367.