Wyznaczanie liczby wystąpień każdego ciągu o długości k (gdzie wartość k jest np. rzędu 20-40), tzw. k-merów, jest ważnym elementem składowym wielu procedur bioinformatycznych. Ważnym zastosowaniem jest procedura asemblacji genomu de novo, gdzie kluczowym elementem jest detekcja odczytów (ang. reads) obarczonych błędami sekwencjonowania; przypadki takie zwykle odpowiadają jedynie pojedynczym wystąpieniom k-merów w zaburzonych odczytach (czy ich odpowiednich fragmentach). Inne znaczące zastosowania statystyk k-merów to uliniowianie wielu sekwencji (MSA), detekcja powtórzeń czy korekta błędów w odczytach.

Choć samo sformułowanie problemu brzmi banalnie prosto, podobnie jak w wielu sytuacjach w bioinformatyce, kluczowym elementem jest wydajność procedury, umożliwiająca jej skalowalność do setek milionów (i więcej odczytów), najlepiej na względnie typowym komputerze klasy PC.

Do najwydajniejszych algorytmów zliczających k-mery należały dotąd Jellyfish, DSK i KMC (Deorowicz, Debudaj-Grabysz i Grabowski, 2013); dwa ostatnie są algorytmami dyskowymi.

W ramach niniejszych prac zaproponowaliśmy jeszcze wydajniejszy algorytm dyskowy, nazwany KMC 2, wykorzystujący interesującą (i budzącą duże zainteresowanie w badaniach bioinformatycznych w ostatnich 2-3 latach) koncepcję tzw. minimizerów (Roberts i in., 2004). Minimizery umożliwiają klasteryzację podciągów odczytów na dysku, w taki sposób iż podciągi zawierające znaczną nakładkę z dużym prawdopodobieństwem umieszczane są w tym samym kubełku dyskowym, co zasadniczo usprawnia ich dalsze przetwarzanie. Koncepcję tę poddaliśmy modyfikacjom i usprawnieniom, co zaowocowało dalszym przyspieszeniem przetwarzania oraz redukcją zużycia pamięci dyskowej oraz pamięci RAM.

KMC 2 jest algorytmem równoległym. Jego implementacja przykładowo umożliwia zliczenie 28-merów danych z sekwencjowowania genomu ludzkiego przy pokryciu 44-krotnym w ok. 20 minut i przy zużyciu 12 GB pamięci RAM na komputerze z 6-rdzeniowym procesorem Intel i7 oraz dyskiem SSD. Wcześniejsze najlepsze algorytmy (KMC, Jellyfish) działają tu ok. 2.5x wolniej.

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ż 4.0.