DNA sequence assembly involving an acyclic graph model

• Autorzy: Blazewicz, J. , Frohmberg, W. , Gawron, P. , Kasprzak, M. , Kierzynka, M. , Swiercz, A. , Wojciechowski, P.
• Języki publikacji: EN

Abstrakty

EN

The problem of DNA sequence assembly is well known for its high complexity. Experimental errors of different kinds present in data and huge sizes of the problem instances make this problem very hard to solve. In order to deal with such data, advanced efficient heuristics must be constructed. Here, we propose a new approach to the sequence assembly problem, modeled as the problem of searching for paths in an acyclic digraph. Since the graph representing an assembly instance is not acyclic in general, it is heuristically transformed into the acyclic form. This approach reduces the time of computations significantly and allows to maintain high quality of produced solutions.

Słowa kluczowe

EN

DNA sequence assembly; acyclic graph model; GPU programming

• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2013
• Tom: Vol. 38, No. 1
• Strony: 25--34
• Opis fizyczny: Bibliogr. 13 poz., tab., fig.

Twórcy

autor

Blazewicz, J.

• Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznan, Poland
• Institute of Bioorganic Chemistry, Polish Academy of Sciences, Poznan, Poland

autor

Frohmberg, W.

• Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznan, Poland

autor

Gawron, P.

• Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznan, Poland
• Luxembourg Centre for Systems Biomedicine, University of Luxembourg

autor

Kasprzak, M.

• Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznan, Poland,
• Institute of Bioorganic Chemistry, Polish Academy of Sciences, Poznan, Poland

autor

Kierzynka, M.

• Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznan, Poland
• Institute of Bioorganic Chemistry, Polish Academy of Sciences, Poznan, Poland

autor

Swiercz, A.

• Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznan, Poland
• Institute of Bioorganic Chemistry, Polish Academy of Sciences, Poznan, Poland

autor

Wojciechowski, P.

• Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznan, Poland

Bibliografia

• [1] J. Bang-Jensen and G. Gutin, Digraphs. Theory, Algorithms and Applications, Springer-Verlag (2007).
• [2] J. Blazewicz, M. Bryja, M. Figlerowicz, P. Gawron, M. Kasprzak, E. Kirton, D. Platt, J. Przybytek, A. Swiercz, and L. Szajkowski, Whole genome assembly from 454 sequencing output via modied DNA graph concept, Computational Biology and Chemistry 33 (2009) 224-230.
• [3] J. Blazewicz, P. Formanowicz, M. Kasprzak, W.T. Markiewicz, and A. Swiercz, Tabu search algorithm for DNA sequencing by hybridization with isothermic libraries, Computational Biology and Chemistry 28 (2004) 11-19.
• [4] J. Blazewicz, W. Frohmberg, M. Kierzynka, E. Pesch, and P. Wojciechowski, Protein alignment algorithms with an effcient backtracking routine on multiple GPUs, BMC Bioinformatics (2011) 12:181.
• [5] J. Blazewicz, W. Frohmberg, M. Kierzynka, P. Wojciechowski, G-MSA | a GPU-based, fast and accurate algorithm for multiple sequence alignment, Journal of Parallel and Distributed Computing (2012), in press.
• [6] J. Blazewicz, F. Glover, M. Kasprzak, W.T. Markiewicz, C. Oguz, D. Rebholz- Schuhmann, and A. Swiercz, Dealing with repetitions in sequencing by hybridization, Computational Biology and Chemistry 30 (2006) 313-320.
• [7] L.R. Ford, Jr. and D.R. Fulkerson, Maximal ow through a network, Canadian Journal of Mathematics 8 (1956) 399-404.
• [8] X. Huang, A. Madan, CAP3: a DNA sequence assembly program Genome Research 9 (1999) 868-877.
• [9] R. Li, H. Zhu, J. Ruan, W. Qian, X. Fang, Z. Shi, Y. Li, S. Li, G. Shan, K. Kristiansen, S. Li, H. Yang, J. Wang, and J. Wang, De novo assembly of human genomes with massively parallel short read sequencing, Genome Research 20 (2010) 265-272.
• [10] M. Margulies, M. Egholm, W.E. Altman, S. Attiya, J.S. Bader, et al. Genome sequencing in microfabricated high-density picolitre reactors. Nature 437 (2005) 376-380.
• [11] S.B. Needleman and C.D. Wunsch, A general method applicable to the search for similarities in the amino acid sequence of two proteins, Journal of Molecular Biology 48 (1970) 443-453.
• [12] J.T. Simpson and R. Durbin, Efficient de novo assembly of large genomes using compressed data structures, Genome Research 22 (2012) 549-556.
• [13] D.R. Zerbino and E. Birney, Velvet: Algorithms for de novo short read assembly using de Bruijn graphs, Genome Research 18 (2008) 821-829.