2011/08/17 by Chengxi Ye, Ye, Chengxi, Charles H. Cannon +8
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Biological sciences #FOS: Computer and information sciences #Genomics (q-bio.GN) #Genomics and Phylogenetic Studies #Modular Robots and Swarm Intelligence #cs.DS #q-bio.GN
paper · pdf · doi:10.48550/arxiv.1108.3556
Corresponding authors: Zhanshan (Sam) Ma, [email protected]; Mihai Pop, [email protected] || Availability: Programs in both Windows and Linux are available at: https://sites.google.com/site/sparseassembler/
openalex publication_date 2011/08/17 · arxiv created 2013/01/09 · arxiv updated 2013/01/10 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
The formal version of our work has been published in BMC Bioinformatics and can be found here: http://www.biomedcentral.com/1471-2105/13/S6/S1 Motivation: To tackle the problem of huge memory usage associated with de Bruijn graph-based algorithms, upon which some of the most widely used de novo genome assemblers have been built, we released SparseAssembler1. SparseAssembler1 can save as much as 90% memory consumption in comparison with the state-of-art assemblers, but it requires rounds of denoising to accurately assemble genomes. In this paper, we introduce a new general model for genome assembly that uses only sparse k-mers. The new model replaces the idea of the de Bruijn graph from the beginning, and achieves similar memory efficiency and much better robustness compared with our previous SparseAssembler1. Results: We demonstrate that the decomposition of reads of all overlapping k-mers, which is used in existing de Bruijn graph genome assemblers, is overly cautious. We introduce a sparse k-mer graph structure for saving sparse k-mers, which greatly reduces memory space requirements necessary for de novo genome assembly. In contrast with the de Bruijn graph approach, we devise a simple but powerful strategy, i.e., finding links between the k-mers in the genome and traversing following the links, which can be done by saving only a few k-mers. To implement the strategy, we need to only select some k-mers that may not even be overlapping ones, and build the links between these k-mers indicated by the reads. We can traverse through this sparse k-mer graph to build the contigs, and ultimately complete the genome assembly. Since the new sparse k-mers graph shares almost all advantages of de Bruijn graph, we are able to adapt a Dijkstra-like breadth-first search algorithm to circumvent sequencing errors and resolve polymorphisms.