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.

References in zbMATH (referenced in 31 articles )

Showing results 1 to 20 of 31.
Sorted by year (citations)

1 2 next

  1. Chikhi, Rayan: A tale of optimizing the space taken by de Bruijn graphs (2021)
  2. Davot, Tom; Chateau, Annie; Giroudeau, Rodolphe; Weller, Mathias; Tabary, Dorine: Producing genomic sequences after genome scaffolding with ambiguous paths: complexity, approximation and lower bounds (2021)
  3. Liu, Wen-li; Wu, Qing-biao: Analysis method and algorithm design of biological sequence problem based on generalized k-mer vector (2021)
  4. Shieh, Yi-Kung; Shyu, Shyong Jian; Lu, Chin Lung; Lee, Richard Chia-Tung: The exact multiple pattern matching problem solved by a reference tree approach (2021)
  5. Acuña, V.; Grossi, R.; Italiano, G. F.; Lima, L.; Rizzi, R.; Sacomoto, G.; Sagot, M.-F.; Sinaimeri, B.: On bubble generators in directed graphs (2020)
  6. Pellegrina, Leonardo; Pizzi, Cinzia; Vandin, Fabio: Fast approximation of frequent (k)-mers and applications to metagenomics (2019)
  7. Ryšavý, Petr; Železný, Filip: Estimating sequence similarity from read sets for clustering next-generation sequencing data (2019)
  8. Wright, Christopher; Krishnamoorty, Sriram; Kulkarni, Milind: MULKSG: \textitMULtiple\textitK\textitSimultaneous\textitGraphassembly (2019)
  9. Blazewicz, Jacek; Kasprzak, Marta; Kierzynka, Michal; Frohmberg, Wojciech; Swiercz, Aleksandra; Wojciechowski, Pawel; Zurkowski, Piotr: Graph algorithms for DNA sequencing -- origins, current models and the future (2018)
  10. Alipanahi, Bahar; Salmela, Leena; Puglisi, Simon J.; Muggli, Martin; Boucher, Christina: Disentangled long-read de Bruijn graphs via optical maps (2017)
  11. Eugene Goltsman, Isaac Ho, Daniel Rokhsar: Meraculous-2D: Haplotype-sensitive Assembly of Highly Heterozygous genomes (2017) arXiv
  12. Jean, Géraldine; Radulescu, Andreea; Rusu, Irena: The contig assembly problem and its algorithmic solutions (2017)
  13. Keith, Jonathan M. (ed.): Bioinformatics. Volume I. Data, sequence analysis, and evolution (2017)
  14. Liu, Yongchao; Schmidt, Bertil: CUSHAW suite: parallel and efficient algorithms for NGS read alignment (2017)
  15. Quiroz-Ibarra, J. Emilio; Mallén-Fullerton, Guillermo M.; Fernández-Anaya, Guillermo: DNA paired fragment assembly using graph theory (2017)
  16. Rosen, Yohei; Eizenga, Jordan; Paten, Benedict: Describing the local structure of sequence graphs (2017)
  17. Brankovic, Ljiljana; Iliopoulos, Costas S.; Kundu, Ritu; Mohamed, Manal; Pissis, Solon P.; Vayani, Fatima: Linear-time superbubble identification algorithm for genome assembly (2016)
  18. Iliopoulos, Costas S.; Kundu, Ritu; Mohamed, Manal; Vayani, Fatima: Popping superbubbles and discovering clumps: recent developments in biological sequence analysis (2016)
  19. Tomescu, Alexandru I.; Medvedev, Paul: Safe and complete contig assembly via omnitigs (2016)
  20. Nimmy, Sonia Farhana; Kamal, M. S.: Next generation sequencing under de novo genome assembly (2015)

1 2 next