1. bookVolume 38 (2013): Issue 1 (March 2013)
Journal Details
License
Format
Journal
eISSN
2300-3405
ISSN
0867-6356
First Published
24 Oct 2012
Publication timeframe
4 times per year
Languages
English
Open Access

Dna Sequence Assembly Involving an Acyclic Graph Model

Journal Details
License
Format
Journal
eISSN
2300-3405
ISSN
0867-6356
First Published
24 Oct 2012
Publication timeframe
4 times per year
Languages
English
Abstract

The problem of DNA sequence assembly is well known for its high complexity. Experimental errors of di erent 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.

Keywords

[1] J. Bang-Jensen and G. Gutin, Digraphs. Theory, Algorithms and Applications, Springer-Verlag (2007).Search in Google Scholar

[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.Search in Google Scholar

[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.Search in Google Scholar

[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.10.1186/1471-2105-12-181Search in Google Scholar

[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.10.1016/j.jpdc.2012.04.004Search in Google Scholar

[6] J. Blazewicz, F. Glover, M. Kasprzak, W.T. Markiewicz, C. Oguz, D. Rebholz- Schuhmann, and A. Swiercz, Dealing with repetitions in sequencing by hybridiza- tion, Computational Biology and Chemistry 30 (2006) 313{320.Search in Google Scholar

[7] L.R. Ford, Jr. and D.R. Fulkerson, Maximal ow through a network, Canadian Journal of Mathematics 8 (1956) 399{404.Search in Google Scholar

[8] X. Huang, A. Madan, CAP3: a DNA sequence assembly program Genome Re- search 9 (1999) 868-877.Search in Google Scholar

[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.Search in Google Scholar

[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.Search in Google Scholar

[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.10.1016/0022-2836(70)90057-4Search in Google Scholar

[12] J.T. Simpson and R. Durbin, Efficient de novo assembly of large genomes using compressed data structures, Genome Research 22 (2012) 549{556.Search in Google Scholar

[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. Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo