Dostępność tysięcy osobnicznych genomów zwiastuje nadejście spersonalizowanej medycyny. Ma też inne doniosłe konsekwencje, np. umożliwia zrozumienie interakcji pomiędzy genotypem a fenotypem. Kluczową operacją w tego typu analizach jest uliniowienie odczytów sekwencjonowania względem kolekcji genomów.

Do tej pory tego typu operacja była wykonywana przede wszystkim w odniesieniu do pojedynczego genomu; koszty pamięciowe wyszukiwania przybliżonego w całej sekwencji genomów sprawiają, że opisany problem algorytmiczny jest niemałym wyzwaniem.
Warto zauważyć, że indeks pełnotekstowy dla pojedynczego genomu ludzkiego został przedstawiony w roku 2001 (Sadakane i Shibuya) i zajmował on ok. 2 GB pamięci, w postaci skompresowanej tablicy sufiksowej. Choć w ostatnich latach pojawiły się też pewne propozycje wyszukiwania w dużych kolekcjach genomów, to wymagają one (dla kolekcji genomów ludzkich) albo >100 GB pamięci RAM, albo są stosunkowo wolne (JST).
Warto zauważyć, że diploidalny genom ludzki zajmuje ok. 6 GB pamięci w postaci nieskompresowanej. Choć podobieństwo dwóch osobnicznych genomów ludzkich jest na poziomie 99%, to nie jest łatwo osiągnąć zarówno wysoki stopień kompresji, jak i wysoką wydajność w kolekcji wielu takich genomów. Adaptacja wcześniej znanych indeksów skompresowanych dla potrzeb bioinformatyki jest tylko w ograniczonym stopniu skalowalna.

Rozważane przez nas podejście zakłada, że reprezentacją wejściową genomów jest format VCF (czy raczej jego uproszczona postać). Mechanizm wyszukiwania bazuje na klasycznym podejściu seed-and-extend, tj. znalezieniu w kolekcji fragmentu identycznego z fragmentem zapytania, a następnie rozważeniu wszystkich jego możliwych przedłużeń. Novum naszego algorytmu polega na wykorzystaniu (zmodyfikowanej) rzadkiej tablicy sufiksowej (ang. sparse suffix array) przechowującej wszystkie k-mery występujące w kolekcji sekwencji, dla zadanego parametru k. Wstępne eksperymenty pokazują, iż możliwa jest w ten sposób obsługa kolekcji 1092 ludzkich genomów osobnicznych (wziętych z zestawu 1000GP) na komputerze PC wyposażonym w zaledwie 16 GB pamięci głównej. W strukturze tej możliwe jest wyszukiwanie zarówno dopasowań dokładnych dla odczytów z sekwencjonowania jak i dopasowań przybliżonych. Dzięki temu możliwe jest udzielenie odpowiedzi, do których osobników kolekcji może być dopasowany dany odczyt z sekwencjonowania. Eksperymenty pokazują, że czasy realizacji takich zapytań są zdecydowanie lepsze niż w podejściach konkurencyjnych, np. wykorzystujących znane algorytmy mapowania odczytów, takie jak GEM, Bowtie.

Szczegóły opracowanego algorytmu oraz wyniki eksperymentalnych testów porównawczych mają być opublikowane w czasopiśmie JCR o współczynniku oddziaływania (IF) większym niż 3.0.