GPU-accelerated graph construction for the whole genome assembly
[ 1 ] Instytut Informatyki, Wydział Informatyki, Politechnika Poznańska | [ P ] employee
[ 1 ] Instytut Informatyki, Wydział Informatyki, Politechnika Poznańska | [ P ] employee
PL Konstrukcja grafu w problemie asemblacji całego genomu z wykorzystaniem procesorów kart graficznych
english
- DNA de novo assembly
- DNA overlap graphs
- k-mer sequence analysis
- GPU computing
- sequence alignment
- asemblacja DNA typu de novo
- grafy nałożeń DNA
- k-merowa analiza sekwencji
- obliczenia na GPU
- dopasowywanie sekwencji
EN Thesis presents a new heuristic algorithm for DNA overlap graph construction. Such graphs are widely used in the process of DNA de novo assembly. The proposed algorithm is based on k-mer analysis of the biological sequences, which is used for efficient preselection of reads that are likely to be similar. Subsequently, the overlapping properties of these pairs of reads are verified by an exact sequence alignment on GPU. This process minimizes the number of false positive arcs in the constructed graph. Afterwards, the quality of the graph is further improved by four additional procedures. The accuracy of the proposed algorithm was tested on synthetic as well as real data sets. The confusion matrix was used to measure both sensitivity and precision of the algorithm, which were between 97% and 99%, and up to 99%, respectively. Therefore, the results are considered to be very good.
PL Niniejsza praca przedstawia nowy algorytm heurystyczny do konstrukcji grafów nałożeń DNA, które z kolei są szeroko wykorzystywane w procesie asemblacji DNA typu de novo. Zaproponowany algorytm oparty jest na k-merowej analizie sekwencji biologicznych, która została wykorzystana do efektywnej preselekcji podobnych do siebie odczytów z sekwenatora. Weryfikacja występowania nałożeń między poszczególnymi sekwencjami, tj. łuków w konstruowanym grafie, jest dokonywana za pomocą dokładnego dopasowywania sekwencji na GPU, co pozwala zminimalizować liczbę błędnych połączeń w grafie. W dalszej kolejności jakość grafu jest podnoszona za pomocą czterech dodatkowych procedur. Dokładność zaproponowanego algorytmu została zweryfikowana zarówno na syntetycznych jak i prawdziwych zbiorach danych. W przypadku badania jakość grafu na podstawie macierzy pomyłek, czułość zaproponowanej metody wahała się pomiędzy 97% a 99%, co w połączeniu z wysoką precyzją sięgającą 99% dało bardzo dobre wyniki.
131
computer sciences and computer science
computer science
DrOIN 1661
public
Pascal Bouvry
Luksemburg, Luksemburg
27.04.2015
english
public
Franciszek Seredyński
Warszawa, Polska
21.04.2015
english
public
dissertation
Poznań, Polska
06.05.2015
Rada Wydziału Informatyki Politechniki Poznańskiej
doktor nauk technicznych w dyscyplinie: informatyka, w specjalności: bioinformatyka