Parallel algorithm for the DNA short-read sequences alignment problem

Problem dopasowania krótkich sekwencji DNA pochodzi z badań genetycznych. Do odczytywania DNA wykorzystuje się sekwencery, w wyniku działania których otrzymuje się serie krótkich fragmentów danego DNA (ang. short-reads). Takie odczyty porównuje się do zadanego genomu referencyjnego – celem jest znalezienie dla każdego odczytu miejsca w genomie referencyjnym, które jest identyczne lub podobne do tego odczytu.Z algorytmicznego punktu jest to problem niedokładnego dopasowania wielu wzorców do zadanego tekstu, przy czym pracujemy na alfabecie 4-literowym (litery A, C, G, T). Możliwość niedokładnego dopasowania sprawia, że znalezienie wystąpień wzorców wymaga dużo czasu pracy procesora. Opracowano kilka technik, które są wykorzystywane do rozwiązania tego problemu – ich zrównoleglenie dokonuje się w większości w oparciu o wspólną pamięć.Niniejsza praca stanowi przegląd algorytmów niedokładnego dopasowania wzorca do tekstu, analizuje możliwość ich zrównoleglenia i przedstawia implementację tego problemu w środowisku rozproszonym – wielu procesorów komunikujących się ze sobą, bez współdzielenia pamięci.The problem of short-read alignment comes from bioinformatics. DNA is read using sequencing technologies which produce lots of short DNA sequences, so called short-reads. These short-reads are then matched against reference genome. The goal is to find for every short-read all positions at which the given short-read occurs in the reference genome. The main difficulty in this problem is that we also accept errors in such a matching.From an algorithmic point of view short-read alignment is a problem of approximate string matching of many short patterns to the given text in four-letter alphabet (DNA is represented by four letters: A, C, G, T). Finding all occurrences in approximate matching requires a lot of computation. There are several techniques for this problem and most of them can be effectively parallelized in a shared memory model.In this paper we review existing algorithms for approximate string matching and consider how to parallelize them. Then we propose our own method with implementation in distributed environment with many processors communicating with each other without using shared memory