Dostępność tysięcy osobnicznych genomów, tak ludzkich, jak i rozmaitych gatunków zwierząt i roślin, oraz wzrost liczby placówek badawczych na świecie zajmujących się biologią obliczeniową pociągają za sobą drastycznie rosnące koszty transferu i składowania danych bioinformatycznych. By mieć wyobrażenie o trudnościach tego typu, wystarczy uświadomić sobie, że dane z sekwencjonowania genomu człowieka, przy standardowym pokryciu 30x, zajmują w postaci surowej (FASTQ) ponad 200 GB (nie licząc informacji o wynikach ich uliniowienia, np. w formacie SAM). Tradycyjne algorytmy kompresji nie są zbyt przydatne dla tego typu danych, osiągając stopień kompresji jedynie rzędu 3-4x (nawet przy dość kosztowej obliczeniowo i pamięciowo kompresji algorytmem LZMA).

Od kilku lat istnieją algorytmy specjalizowane kompresji danych z odczytów sekwencjonowania DNA (FASTQ, SAM), ale osiągane przez nie stopnie kompresji również nie są radykalnie wyższe niż powyżej wskazane osiągi kompresorów ogólnego przeznaczenia. Przyczyny takiego stanu rzeczy są dwojakie:

znaczna redundancja (w dużej mierze za sprawą zaszumienia) danych jakości odczytów poszczególnych symboli DNA,

trudność usunięcia specyficznej redundancji nakładających się na siebie odczytów.

Odpowiedzią na punkt pierwszy są, zaproponowane w ostatnich 3 latach, algorytmy stratnej kompresji danych o jakości odczytów. W naszych badaniach zajmujemy się natomiast aspektem drugim.

Wielkość danych z sekwencjonowania, np. ok. 100 GB strumienia DNA dla typowo zsekwencjonowanego genomu człowieka, uniemożliwia ich przetwarzanie w całości w pamięci RAM typowego komputera. Ponieważ kolejne odczyty DNA odpowiadają "przypadkowym" miejscom w genomie referencyjnym, to znalezienie większych grup odczytów w dużym stopniu nakładających się na siebie jest niemożliwe, jeśli przetwarzamy dane wejściowe tylko we względnie małych blokach (czy przesuwającym się oknie), a jest to podejście typowe w istniejących kompresorach FASTQ.
Aby pokonać ten problem, zaproponowaliśmy algorytm zewnętrzny (dyskowy) do klasteryzacji odczytów. Choć użycie pamięci dyskowej w tym kontekście nie jest podejściem nowym (Yanovsky, 2011; Cox i in., 2012), to nasza metoda, bazująca na tzw. minimizerach (Roberts i in., 2004) cechuje się prostotą i łatwością paralelizacji, a także wysokim stopniem kompresji.
Przykładowo, algorytm Coxa i in. (2012), oparty na transformacie Burrowsa-Wheelera i zwany dalej BWT-SAP, osiąga kompresję 0,518 bit/symbol dla danych z sekwencjonowania genomu ludzkiego o rozmiarze 134.0 Gb (pokrycie rzędu 45x). Nasz algorytm, ORCOM, dla tych samych danych oferuje kompresję 0,317 bit/symbol, czyli umożliwia skompresowanie danego zbioru do rozmiaru 5,31 GB. Co więcej, czas kompresji algorytmu ORCOM to 77 minut, co kontrastuje z 4463 minutami działania kompresora BWT-SAP (eksperymenty na serwerze z czterema 8-rdzeniowymi procesorami AMD Opteron 6136 2,4 GHz, 128 GB pamięci RAM i macierzą zawierającą 6 dysków twardych (HDD) w układzie RAID-5).

Wyniki naszych badań mają być opublikowane w czasopiśmie JCR o współczynniku oddziaływania większym niż 4,0 (wg wykazu JCR 2013).