biotechnologia


 
 

Macierz Farragina Manziniego

Wygenerowany wcześniej indeks Farragina Manziniego, został zoptymalizowany w odstępach w oparciu o dane wprowadzone przez użytkownika.
Wzór: cad
Stos: abracadabra

Z powyższych danych przykładowych, wyniki są następujące.

Xbwt = Zdrcraaaabba
Macierz Ferragina - Manzini generowana jest jak poniżej, gdy nie ma optymalizacji Occ. Tutaj za wartość K przyjmuje się 1.




W macierzy Ferragina Manzini dla wartości K jest równa 4.




3.3




Implementacja tego algorytmu będzie miała złożoność O(n) + O(m*m), ponieważ funkcja LF wymaga dalszego zaangażowania pętli.

Również optymalizacja Occ obędzie prowadziła do wolniejszych odpowiedzi, ponieważ BWT musi być liczony od indeksu FM. Xibwt można obliczyć bez znajomości xbwt. Ale jeśli będzie więcej indeksów funkcja lokalizacji będzie szybsza, jeśli bęszie mniej indeksów funkcja lokalizacji będzie wolniejsza.

Jak wyszukiwać szybciej korzystając z optymalizacji Occ?
Aby temu zaradzić możemy użyć następujących metod:
 Musimy znaleźć optymalną wartość dla K, gdzie K jest nie za wysokie aby doprowadzić do wolniejszych wyszukiwań, nie jest zbyt zbliżone do 1 i ma duży indeks.
 Wartość K może być ustalona na postawie łańcucha stosu. Jeśli prawdopodobieństwo większego łańcucha jest wyższe, wówczas wartość K może być relatywnie mniejsza, tak, że indeksy są wyższe, a lokalizowanie szybsze. Jednakże jeśli ciąg stosu będzie mały, czyli mniej niż 50 znaków, wartość K może być relatywnie wyższa, tak, że indeksy są niższe, a lokalizacja wystarczająco szybka.


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


Autor: Krzysztof Wołk

Komentarze

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

Podręcznik biotechnologii

Kto jest online

61 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