Dziś chcemy bliżej zapoznać się z indeksami sekwencji.
Spróbujmy zaimplementować trzy rodzaje indeksów:
1. Drzewo sufiksowe. Implementujemy funkcje build_ST(genome) i find (ST,word). Nie interesuje nas tak bardzo koszt implementacji drzewa (może być słownik) ani koszt budowy drzewa (może być n^2). Chodzi o to, aby find działał liniowo względem długości słowa i zwracał wszystkie wystąpienia słowa w genomie.
2. Tablica sufiksowa. Implementujemy funkcję build_SA(genome) i find(SA, word). Podobnie jak w p. 1.
3*. FM-Index: możemy podzielić na podproblemy:
– Dla zadanego genomu policz BWT(genome)
– Dla zadanej BWT, policz Last-First mapping
– Przy użyciu BWT i Last-First mapping skonstruuj wyszukiwanie słowa (czy istnieje wystąpienie i gdzie jest w genomie
– dodaj funkcjonalność związaną z wyszukwianiem wszystkich słów
4. Dla zadanego słowa, napisz funkcję, która wyszukuje wariantów tego słowa w ustalonej odległości (<k błędów) w zadanym indeksie (np. wyszukaj słowa podobne do ATGCG z nie więcej niż 2 błędami w zadanej sekwencji).