SeedsGraph: an efficient assembler for next-generation sequencing data
Open Access
- 29 May 2015
- journal article
- Published by Springer Nature in BMC Medical Genomics
- Vol. 8 (S2) , S13
Abstract
DNA sequencing technology has been rapidly evolving, and produces a large number of short reads with a fast rising tendency. This has led to a resurgence of research in whole genome shotgun assembly algorithms. We start the assembly algorithm by clustering the short reads in a cloud computing framework, and the clustering process groups fragments according to their original consensus long-sequence similarity. We condense each group of reads to a chain of seeds, which is a kind of substring with reads aligned, and then build a graph accordingly. Finally, we analyze the graph to find Euler paths, and assemble the reads related in the paths into contigs, and then lay out contigs with mate-pair information for scaffolds. The result shows that our algorithm is efficient and feasible for a large set of reads such as in next-generation sequencing technology.Keywords
This publication has 19 references indexed in Scilit:
- Readjoiner: a fast and memory efficient string graph-based sequence assemblerBMC Bioinformatics, 2012
- Efficient de novo assembly of large genomes using compressed data structuresGenome Research, 2011
- GAGE: A critical evaluation of genome assemblies and assembly algorithmsGenome Research, 2011
- The Sequence Read ArchiveNucleic Acids Research, 2010
- Assembly algorithms for next-generation sequencing dataGenomics, 2010
- Cloud computingBioinformatics, 2009
- ABySS: A parallel assembler for short read sequence dataGenome Research, 2009
- Velvet: Algorithms for de novo short read assembly using de Bruijn graphsGenome Research, 2008
- Short read fragment assembly of bacterial genomesGenome Research, 2007
- A Whole-Genome Assembly of DrosophilaScience, 2000