biotechnologia


 
 

Index Farragina Manziniego

Aby zbudować index Farragina Manziniego ℛ musimy najpierw obliczyć uogólniony szereg przyrostków ℛ. Możemy to zrobić tworząc ciąg znaków, który jest połączeniem wszystkich członkówℛ, S=ℛ12…ℛm , a następnie użyć jednego z wydajnych algorytmów tablicy suffixów aby obliczyć SAS .

Dane tablicy suffixów zostały wprowadzone jako reprezentacja zwięzłych leksykograficznych przyrostków łańcucha. Tablica suffixów z ciąguX, oznaczona SAX, jest permutacją liczb {1, 2,…, |X|} takich, że SAX [i]=j wtedy i tylko wtedy X[j, |X|] jest i-tym leksykograficznie najniższym przyrostkiem X.

Na przykład jeśli X=AAGTA$ wówczas SAX=[6, 5, 1, 2, 3, 4]. Ponieważ tablica suffixów jest strukturą posortowaną pozycje startowe dla wszystju unstancji wzorca Q w Q wystąpią w przedziale w SAX. Odwołujemy się do takiego przedziału jako przedziału tablicy suffiksów i kojarzymy z nim parę liczb całkowitych [l, u] oznaczającą pierwszy i ostatni indec w SAX, który odpowiada oryginalnemu ciągowi X, I, który może być skutecznie znaleziony przy pomocy wyszukiwania binarnego dla Q.

Ferragina i Manzini opracowali metodę indeksowania tekstu zwaną FM-index, która wymaga znacznie mniej pamięci niż tablica suffixów i może obliczyćl oraz u w O(|Q|) czas, niezależnie od rozmiaru poszukiwanego tekstu. Centralny do FM-index jest BWT. Pierwotnie opracowana do kompresji tekstu BWT of X, oznaczona BX, jest permutacją z symboli X takich, że




Przekształcone, BX [i] jest symbolem poprzedzającym pierwszy symbol przyrostkiem wyjścia w pozycji SAX [i]. Ferragina and Manzini przedłużył BWT representcję ciągu poprzez dodanie dwóch dodarkowych struktur danych, aby stworzyć strukturę zwaną FM-index.
Niech CX (a) jest liczbą symboli w X, które są leksykograficznie mniejsze niż symbol iOccX (a, i) będzie liczbą wystąpień symbolu w BX [1, i]. Zauważmy, że CX i OccX zawiera liczby dla symbolu posterunkowego $. Wykorzystując te dwie tablice, Ferragina and Manzini dostarczono algorytm aby wyszukać ciągQ w X.
Niech S będzie ciągiem, którego końcówka jest znanym przedziałem z tablicy [l, u]. Przedział dla ciągu S może być obliczony z [l, u] przy użyciu CX oraz OccX:





Implementacja dostępna w pliku FerraginaManziniIndex.zip dostępnego pod adresem
http://cs.elitepc.pl/FerraginaManziniIndex
lub
tutaj


Autor: Krzysztof Wołk

Komentarze

Widok Uszereguj
Tylko zarejestrowani mogą dodawać komentarze. Zarejestruj się/Zaloguj

Podręcznik biotechnologii

Kto jest online

53 gości oraz 0 użytkowników online.

Jesteś niezarejestrowanym lub niezalogowanym użytkownikiem.


 

Facebook

Gadżety

Sklep e-biotechnologia.pl
Tematyczne kubki, koszulki, bluzy etc.


Zapraszamy do sklepu

Na skróty

Ministerstwo Nauki i Szkolnictwa Wyższego Narodowe Centrum Nauki Narodowe Centrum Badań i Rozwoju Ośrodek Przetwarzania Informacji PAP - Nauka w Polsce Forum Akademickie Fundacja na rzecz Nauki Polskiej Wirtualna Biblioteka Nauki Scopus NCBI PubMed Nature Science Cell

 
 
Partnerzy:

laboratoria.net Nauka w Polsce Academio Fundacja NanoNet BioCen - BioCentrum Edukacji Naukowej Notatek.pl cebioforum.com materialyinzynierskie.pl Wspieram.to - POLSKI KICKSTARTER - Polska platforma finansowania społecznoœciowego.Tu zrealizujš się Twoje pomysły. VitaInSilica Portal popularnonaukowy

Portal: Redakcja . Współpraca . Kontakt . Polecamy



Wszystkie prawa zastrzeżone 2006-2016 e-biotechnologia.pl
stat4u