Velvet: algorithms for de novo short read assembly using de Bruijn graphs.
We have developed a new set of algorithms, collectively called "Velvet," to manipulate de Bruijn graphs for genomic sequence assembly. A de Bruijn graph is a compact representation based on short words (k-mers) that is ideal for high coverage, very short read (25-50 bp) data sets. Applying Velvet to very short reads and paired-ends information only, one can produce contigs of significant length, up to 50-kb N50 length in simulations of prokaryotic data and 3-kb N50 on simulated mammalian BACs. When applied to real Solexa data sets without read pairs, Velvet generated contigs of approximately 8 kb in a prokaryote and 2 kb in a mammalian BAC, in close agreement with our simulated results without read-pair information. Velvet represents a new approach to assembly that can leverage very short reads in combination with read pairs to produce useful assemblies.
Zerbino
Daniel R
DR
EMBL-European Bioinformatics Institute, Wellcome Trust Genome Campus, Hinxton, Cambridge CB10 1SD, United Kingdom.
Birney
Ewan
E
D000465:Algorithms; D000818:Animals; D022202:Chromosomes, Artificial, Bacterial; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D016680:Genome, Bacterial; D015894:Genome, Human; D023281:Genomics; D006801:Humans; D008322:Mammals / Q000235:genetics; D017422:Sequence Analysis, DNA / Q000379:methods* / Q000592:standards; D013291:Streptococcus / Q000235:genetics