Jak przyspieszyć analizę DNA z wykorzystaniem algorytmu BLAST na superkomputerach
Genetyka jest jedną z najszybciej rozwijających się dziedzin nauki. Znajomość kodu DNA pozwala na coraz bardziej wyrafinowane zastosowania: od diagnostyki różnych chorób, poprzez opracowywanie nowych leków i metod leczenia aż po przewidywanie prawdopodobieństwa wystąpienia określonych schorzeń. Pierwsze analizy genomu ludzkiego wykonane kilkanaście lat temu były olbrzymim i bardzo kosztownym międzynarodowym przedsięwzięciem (Human Genome Project). Obecnie, wraz z postępem biochemii i rozwojem niezbędnych technologii (w tym informatycznych), poznanie kluczowych fragmentów DNA jest szybkie i stosunkowo tanie, a zebranie informacji o całym DNA człowieka (Whole Genome Sequencing) nie jest już tak kosztowne i może zostać wykonane w stosunkowo krótkim czasie – dni czy tygodni. Współczesne techniki znajdowania kolejności aminokwasów w DNA nazwa się powszechnie sekwencjonowaniem nowej generacji (Next Generation Sequencing). Dzięki temu coraz częściej wykorzystuje się informację genetyczną do diagnostyki, zwłaszcza w przypadku chorób rzadkich, mających często podłoże autoimmunologiczne, a więc genetyczne. Znajomość DNA jest także pomocna w określeniu prawdopodobieństwa zachorowania na niektóre choroby (w tym onkologiczne) czy w określeniu typu schorzenia i dobrania odpowiedniej kuracji.
Z tego powodu sekwencjonowanie DNA staje się coraz ważniejszą metodą diagnostyczną, a urządzenia do sekwencjonowania znajdują się coraz częściej w laboratoriach szpitalnych. Proces sekwencjonowania oparty jest na potraktowaniu materiału pobranego od człowieka (zazwyczaj w postaci krwi) odpowiednimi enzymami. Efekty odczytywane są za pomocą odpowiednich układów detekcji. Przygotowanie próbki a następnie jej analiza jest stosunkowo szybka i z wykorzystaniem współczesnych sekwencerów zajmuje kilka godzin. Niestety, informacja uzyskana w wyniku reakcji biochemicznych wymaga dalszego przetworzenia, co wykonywane jest za pomocą komputerów.
W wyniku analiz biochemicznych otrzymujemy krótkie (długości około 100 znaków) ciągi zasad występujące w analizowanym DNA. Fragmenty te (tzw. reads) należy porównać z informacją znajdującą się w dostępnych bazach danych. I to właśnie ten etap– wyszukiwania analogicznych fragmentów DNA w bazach danych – jest najbardziej czasochłonny i wymaga zaangażowania dużych mocy obliczeniowych. W zależności od stawianych pytań, a więc w zależności od tego, ile i jakie bazy danych przeszukujemy i jak dużego podobieństwa wymagamy, proces ten może na typowym komputerze trwać godziny, tygodnie, a nawet miesiące.
Dlaczego tak długo? Wydawałoby się, że znalezienie podobnych ciągów znaków nie jest takie trudne. Jednak problem tkwi w poszukiwaniu podobnych, lecz niekoniecznie identycznych ciągów. O ile znalezienie takich samych ciągów znaków nie jest trudne, to dopuszczenie modyfikacji (mutacji, jak to nazywają genetycy) znacząco komplikuje problem. Algorytmy oparte na przeszukiwaniu wszystkich możliwych kombinacji są niestety zbyt wolne i dopiero opracowania algorytmów heurystycznych, opartych o modele stochastyczne, pozwoliło na znaczące przyspieszenie wyszukiwania. Pierwszym takim algorytmem, wykorzystywanym do tej pory, jest algorytm BLAST (Basic Local Alignment Search Tool) opublikowany na początku 1990 r. Opracowanie tego algorytmu było wydarzeniem przełomowym i jest przez wiele osób uważane za początek bioinformatyki.
BLAST, a w zasadzie jego implementacja stworzona i rozwijana przez amerykańskie National Center for Biotechnology Information (NCBI), jest powszechnie wykorzystywana przez naukowców na całym świecie. Niestety, oprogramowanie to jest dostosowane do pracy na pojedynczym komputerze (stacji roboczej) i nie jest w stanie wykorzystać możliwości współczesnych komputerów równoległych. W ostatnich latach pojawiło się wiele prób implementacji BLAST-a na komputery równoległe jednak, nie były one odpowiednio wydajne bądź nie nadążały za szybko zmieniającymi się wersjami BLAST-a. W rezultacie analiza danych genetycznych trwała zbyt długo, by mogła być wykorzystywana w diagnostyce czy nawet w badaniach naukowych.
Z wspomnianym problemem zetknęli się nasi współpracownicy z Karolinska Instituet w Sztokholmie. W swojej pracy zajmowali się identyfikacją fragmentów DNA człowieka, które są podobne do sekwencji DNA wirusów. Szacuje się, że kilka–kilkanaście procent DNA człowieka to sekwencje wirusopodobne – czyli fragmenty zbliżone do tych występujących u wirusów. Prawdopodobnie służą one jako swego rodzaju pamięć wykorzystywana przy syntetyzowaniu przeciwciał czy białek zwalczających konkretne wirusy. Mechanizmy te nie są jeszcze dobrze zbadane, ale wydaje się, że mogą mieć istotny związek z odpornością człowieka na infekcje wirusowe.
Ze względu na wymaganą dużą dokładność porównania, ale także ze względu na wielkość przeszukiwanych baz danych, analizy wykonywane z wykorzystaniem oprogramowania z NCBI i dostępnego sprzętu (stacji roboczych) trwało miesiącami. Aby przyspieszyć prace, wykorzystano doświadczenie ICM UW w zrównoleglaniu aplikacji i wykorzystano rozwijane przez nas narzędzia. W krótkim czasie (niecałe 3 miesiące) udało się przygotować program zaimplementowany z użyciem biblioteki PCJ, który pozwolił na podzielenie danych do analizy na mniejsze fragmenty i jednoczesne uruchomienie wielu instancji BLAST-a. Opracowane rozwiązanie wykorzystuje dynamiczne przydzielanie zadań dla poszczególnych procesorów, dzięki czemu okazało się kilka razy bardziej wydajne (szybsze) od rozwiązań konkurencyjnych. Pozwala ono na wykorzystywanie różnych wersji NCBI BLAST i jest tak samo proste w użyciu jak oryginalny kod. Jednocześnie umożliwia znaczące (ponad 100-krotne) skrócenie czasu oczekiwania na wynik, ograniczając go do kilku czy kilkunastu godzin.
Obecnie pracujemy nad uruchomieniem aplikacji na klastrach hadoopowych i zasobach chmurowych. Oprogramowanie jest dostępne na licencji BSD i może być bezpłatnie wykorzystywane (https://github.com/hpdcj/PCJ-blast). Artykuł na temat wykorzystania PCJ do analizy DNA został niedawno opublikowany w „Journal of Computational Biology”.
Piotr Bała
Prof. dr hab. Piotr Bała – fizyk, programista, specjalizuje się w fizyce molekularnej i komputerowej, obliczeniach równoległych i rozproszonych oraz modelowaniu układów dynamicznych metodami klasyczno-kwantowymi. Twórca biblioteki PCJ pozwalającej na efektywne zrównoleglanie obliczeń w języku Java. Współtwórca oprogramowania UNICORE umożliwiającego obliczenia rozproszone w biologii molekularnej i chemii kwantowej. Autor bądź współautor ponad 120 publikacji naukowych. Od 1993 r. współpracuje z ICM UW. Twórca studiów na kierunku inżynieria obliczeniowa w ICM UW. Pomysłodawca hackathonów Wielkie Wyzwania Programistyczne.
