Home LiteratureArticle Details
PMID: 20211242 Published · ppublish English Journal Article Research Support, N.I.H., Extramural Review

Assembly algorithms for next-generation sequencing data.

Genomics ·Vol. 95 ·No. 6 ·2010-06-00 ·Pages 315-27

Miller JR, Koren S, Sutton G

Abstract

The emergence of next-generation sequencing platforms led to resurgence of research in whole-genome shotgun assembly algorithms and software. DNA sequencing data from the Roche 454, Illumina/Solexa, and ABI SOLiD platforms typically present shorter read lengths, higher coverage, and different error profiles compared with Sanger sequencing data. Since 2005, several assembly software packages have been created or revised specifically for de novo assembly of next-generation sequencing data. This review summarizes and compares the published descriptions of packages named SSAKE, SHARCGS, VCAKE, Newbler, Celera Assembler, Euler, Velvet, ABySS, AllPaths, and SOAPdenovo. More generally, it compares the two standard methods known as the de Bruijn graph approach and the overlap/layout/consensus approach to assembly.

MeSH Terms
Algorithms Forecasting Sequence Analysis, DNA/methods,trends Software
Authors & Affiliations
3 authors, click to expand affiliations / ORCID
Miller Jason R
J. Craig Venter Institute, Rockville, MD 20850-3343, USA. [email protected]
Koren Sergey
Sutton Granger
References (81)
81 references, click to expand
  1. Short read fragment assembly of bacterial genomes.
    Genome Res. 2008 Feb;18(2):324-30 PMID: 18083777
  2. Metagenomics: read length matters.
    Appl Environ Microbiol. 2008 Mar;74(5):1453-63 PMID: 18192407
  3. SOAP: short oligonucleotide alignment program.
    Bioinformatics. 2008 Mar 1;24(5):713-4 PMID: 18227114
  4. The impact of next-generation sequencing technology on genetics.
    Trends Genet. 2008 Mar;24(3):133-41 PMID: 18262675
  5. Bioinformatics challenges of new sequencing technology.
    Trends Genet. 2008 Mar;24(3):142-9 PMID: 18262676
  6. Using quality scores and longer reads improves accuracy of Solexa read mapping.
    BMC Bioinformatics. 2008;9:128 PMID: 18307793
  7. Generating a genome assembly with PCAP.
    Curr Protoc Bioinformatics. 2005 Oct;Chapter 11:Unit11.3 PMID: 18428744
  8. De novo bacterial genome sequencing: millions of very short reads assembled on a desktop computer.
    Genome Res. 2008 May;18(5):802-9 PMID: 18332092
  9. Genome assembly reborn: recent computational challenges.
    Brief Bioinform. 2009 Jul;10(4):354-66 PMID: 19482960
  10. MoDIL: detecting small indels from clone-end sequencing with mixtures of distributions.
    Nat Methods. 2009 Jul;6(7):473-4 PMID: 19483690
  11. Mapping short DNA sequencing reads and calling variants using mapping quality scores.
    Genome Res. 2008 Nov;18(11):1851-8 PMID: 18714091
  12. Aggressive assembly of pyrosequencing reads with mates.
    Bioinformatics. 2008 Dec 15;24(24):2818-24 PMID: 18952627
  13. Real-time DNA sequencing from single polymerase molecules.
    Science. 2009 Jan 2;323(5910):133-8 PMID: 19023044
  14. Generations of sequencing technologies.
    Genomics. 2009 Feb;93(2):105-11 PMID: 18992322
  15. De novo assembly using low-coverage short read sequence data from the rice pathogen Pseudomonas syringae pv. oryzae.
    Genome Res. 2009 Feb;19(2):294-305 PMID: 19015323
  16. De novo fragment assembly with short mate-paired reads: Does the read length matter?
    Genome Res. 2009 Feb;19(2):336-46 PMID: 19056694
  17. Crystallizing short-read assemblies around seeds.
    BMC Bioinformatics. 2009;10 Suppl 1:S16 PMID: 19208115
  18. Combinatorial algorithms for structural variation detection in high-throughput sequenced genomes.
    Genome Res. 2009 Jul;19(7):1270-8 PMID: 19447966
  19. Parametric complexity of sequence assembly: theory and applications to next generation sequencing.
    J Comput Biol. 2009 Jul;16(7):897-908 PMID: 19580519
  20. SOAP2: an improved ultrafast tool for short read alignment.
    Bioinformatics. 2009 Aug 1;25(15):1966-7 PMID: 19497933
  21. A fast hybrid short read fragment assembly algorithm.
    Bioinformatics. 2009 Sep 1;25(17):2279-80 PMID: 19535537
  22. BreakDancer: an algorithm for high-resolution mapping of genomic structural variation.
    Nat Methods. 2009 Sep;6(9):677-81 PMID: 19668202
  23. Sequence and structural variation in a human genome uncovered by short-read, massively parallel ligation sequencing using two-base encoding.
    Genome Res. 2009 Sep;19(9):1527-41 PMID: 19546169
  24. RazerS--fast read mapping with sensitivity control.
    Genome Res. 2009 Sep;19(9):1646-54 PMID: 19592482
  25. Fast mapping of short sequences with mismatches, insertions and deletions using index structures.
    PLoS Comput Biol. 2009 Sep;5(9):e1000502 PMID: 19750212
  26. PerM: efficient mapping of short sequencing reads with periodic full sensitive spaced seeds.
    Bioinformatics. 2009 Oct 1;25(19):2514-21 PMID: 19675096
  27. De novo genome sequence assembly of a filamentous fungus using Sanger, 454 and Illumina sequence data.
    Genome Biol. 2009;10(9):R94 PMID: 19747388
  28. Simultaneous alignment of short reads against multiple genomes.
    Genome Biol. 2009;10(9):R98 PMID: 19761611
  29. ALLPATHS 2: small genomes assembled accurately and with high continuity from short paired reads.
    Genome Biol. 2009;10(10):R103 PMID: 19796385
  30. BOAT: Basic Oligonucleotide Alignment Tool.
    BMC Genomics. 2009;10 Suppl 3:S2 PMID: 19958483
  31. Pebble and rock band: heuristic resolution of repeats and scaffolding in the velvet short-read de novo assembler.
    PLoS One. 2009;4(12):e8407 PMID: 20027311
  32. Building the sequence map of the human pan-genome.
    Nat Biotechnol. 2010 Jan;28(1):57-63 PMID: 19997067
  33. The sequence and de novo assembly of the giant panda genome.
    Nature. 2010 Jan 21;463(7279):311-7 PMID: 20010809
  34. De novo assembly of human genomes with massively parallel short read sequencing.
    Genome Res. 2010 Feb;20(2):265-72 PMID: 20019144
  35. ALLPATHS: de novo assembly of whole-genome shotgun microreads.
    Genome Res. 2008 May;18(5):810-20 PMID: 18340039
  36. Velvet: algorithms for de novo short read assembly using de Bruijn graphs.
    Genome Res. 2008 May;18(5):821-9 PMID: 18349386
  37. Genome assembly forensics: finding the elusive mis-assembly.
    Genome Biol. 2008;9(3):R55 PMID: 18341692
  38. Genome sequence and rapid evolution of the rice pathogen Xanthomonas oryzae pv. oryzae PXO99A.
    BMC Genomics. 2008;9:204 PMID: 18452608
  39. Emerging DNA sequencing technologies for human genomic medicine.
    Drug Discov Today. 2008 Jul;13(13-14):569-77 PMID: 18598911
  40. Substantial biases in ultra-short read data sets from high-throughput DNA sequencing.
    Nucleic Acids Res. 2008 Sep;36(16):e105 PMID: 18660515
  41. ZOOM! Zillions of oligos mapped.
    Bioinformatics. 2008 Nov 1;24(21):2431-7 PMID: 18684737
  42. Applications of next-generation sequencing technologies in functional genomics.
    Genomics. 2008 Nov;92(5):255-64 PMID: 18703132
  43. CloudBurst: highly sensitive read mapping with MapReduce.
    Bioinformatics. 2009 Jun 1;25(11):1363-9 PMID: 19357099
  44. SHRiMP: accurate mapping of short color-space reads.
    PLoS Comput Biol. 2009 May;5(5):e1000386 PMID: 19461883
  45. Ultrafast and memory-efficient alignment of short DNA sequences to the human genome.
    Genome Biol. 2009;10(3):R25 PMID: 19261174
  46. Evaluation of next generation sequencing platforms for population targeted sequencing studies.
    Genome Biol. 2009;10(3):R32 PMID: 19327155
  47. ABySS: a parallel assembler for short read sequence data.
    Genome Res. 2009 Jun;19(6):1117-23 PMID: 19251739
  48. A whole-genome assembly of Drosophila.
    Science. 2000 Mar 24;287(5461):2196-204 PMID: 10731133
  49. Modeling the feasibility of whole genome shotgun sequencing using a pairwise end strategy.
    Genomics. 2000 Sep 15;68(3):237-46 PMID: 10995565
  50. The sequence of the human genome.
    Science. 2001 Feb 16;291(5507):1304-51 PMID: 11181995
  51. Fragment assembly with double-barreled data.
    Bioinformatics. 2001;17 Suppl 1:S225-33 PMID: 11473013
  52. An Eulerian path approach to DNA fragment assembly.
    Proc Natl Acad Sci U S A. 2001 Aug 14;98(17):9748-53 PMID: 11504945
  53. ARACHNE: a whole-genome shotgun assembler.
    Genome Res. 2002 Jan;12(1):177-89 PMID: 11779843
  54. Efficiently detecting polymorphisms during the fragment assembly process.
    Bioinformatics. 2002;18 Suppl 1:S294-302 PMID: 12169559
  55. Whole-genome sequence assembly for mammalian genomes: Arachne 2.
    Genome Res. 2003 Jan;13(1):91-6 PMID: 12529310
  56. Fragment assembly with short reads.
    Bioinformatics. 2004 Sep 1;20(13):2067-74 PMID: 15059830
  57. De novo repeat classification and fragment assembly.
    Genome Res. 2004 Sep;14(9):1786-96 PMID: 15342561
  58. Comparative genome assembly.
    Brief Bioinform. 2004 Sep;5(3):237-48 PMID: 15383210
  59. DNA sequencing with chain-terminating inhibitors.
    Proc Natl Acad Sci U S A. 1977 Dec;74(12):5463-7 PMID: 271968
  60. The genome sequence of Drosophila melanogaster.
    Science. 2000 Mar 24;287(5461):2185-95 PMID: 10731132
  61. A strategy of DNA sequencing employing computer programs.
    Nucleic Acids Res. 1979 Jun 11;6(7):2601-10 PMID: 461197
  62. Cloning in single-stranded bacteriophage as an aid to rapid DNA sequencing.
    J Mol Biol. 1980 Oct 25;143(2):161-78 PMID: 6260957
  63. 1-Tuple DNA sequencing: computer analysis.
    J Biomol Struct Dyn. 1989 Aug;7(1):63-73 PMID: 2684223
  64. Whole-genome random sequencing and assembly of Haemophilus influenzae Rd.
    Science. 1995 Jul 28;269(5223):496-512 PMID: 7542800
  65. Toward simplifying and accurately formulating fragment assembly.
    J Comput Biol. 1995 Summer;2(2):275-90 PMID: 7497129
  66. A new algorithm for DNA sequence assembly.
    J Comput Biol. 1995 Summer;2(2):291-306 PMID: 7497130
  67. On the complexity of multiple sequence alignment.
    J Comput Biol. 1994 Winter;1(4):337-48 PMID: 8790475
  68. Base-calling of automated sequencer traces using phred. II. Error probabilities.
    Genome Res. 1998 Mar;8(3):186-94 PMID: 9521922
  69. Genome sequencing in microfabricated high-density picolitre reactors.
    Nature. 2005 Sep 15;437(7057):376-80 PMID: 16056220
  70. The fragment assembly string graph.
    Bioinformatics. 2005 Sep 1;21 Suppl 2:ii79-85 PMID: 16204131
  71. An analysis of the feasibility of short read sequencing.
    Nucleic Acids Res. 2005;33(19):e171 PMID: 16275781
  72. Identifying repeat domains in large genomes.
    Genome Biol. 2006;7(1):R7 PMID: 16507140
  73. A Sanger/pyrosequencing hybrid approach for the generation of high-quality draft assemblies of marine microbial genomes.
    Proc Natl Acad Sci U S A. 2006 Jul 25;103(30):11240-5 PMID: 16840556
  74. Assembling millions of short DNA sequences using SSAKE.
    Bioinformatics. 2007 Feb 15;23(4):500-1 PMID: 17158514
  75. Whole-genome sequencing and assembly with high-throughput, short-read technologies.
    PLoS One. 2007;2(5):e484 PMID: 17534434
  76. Use of simulated data sets to evaluate the fidelity of metagenomic processing methods.
    Nat Methods. 2007 Jun;4(6):495-500 PMID: 17468765
  77. The Sorcerer II Global Ocean Sampling expedition: northwest Atlantic through eastern tropical Pacific.
    PLoS Biol. 2007 Mar;5(3):e77 PMID: 17355176
  78. SHARCGS, a fast and highly accurate short-read assembly algorithm for de novo genomic sequencing.
    Genome Res. 2007 Nov;17(11):1697-706 PMID: 17908823
  79. Extending assembly of short DNA sequences to handle error.
    Bioinformatics. 2007 Nov 1;23(21):2942-4 PMID: 17893086
  80. Accuracy and quality of massively parallel DNA pyrosequencing.
    Genome Biol. 2007;8(7):R143 PMID: 17659080
  81. Whole-genome sequencing and variant discovery in C. elegans.
    Nat Methods. 2008 Feb;5(2):183-8 PMID: 18204455
Article Info
Journal
Genomics
Abbr.
Genomics
ISSN
1089-8646
DOI
10.1016/j.ygeno.2010.03.001
Email
[email protected]
Published
2010-06-00
Epub
2010-00-06
Pages
315-27
Language
English
Region
United States
NLM ID
8800135
PMCID
PMC2874646
Subset
IM
Grants
NIGMS NIH HHS · R01 GM077117 · United States
NIGMS NIH HHS · R01 GM077117-04A1 · United States
NIGMS NIH HHS · 2R01GM077117-04A1 · United States
External Links
PubMed source DOI: 10.1016/j.ygeno.2010.03.001 PMC Full Text View journal details
Analysis Services
Analysis Services

Contact

No. 2 Wenbo Road, Zhangqiu District, Jinan, Shandong

Qilu Normal University · Genelibs Bioinformatics Lab

750 Shunhua Rd, Jinan

2F, Bldg F, University Science Park

Tel: 0531-88819269

WeChat Official Account

Follow our WeChat subscription account for real-time updates and the latest in medical and biological research.


Business Email

E-mail: [email protected]

Copyright © 2026.Genelibs Jinan Honghui Biotechnology Co., Ltd. 鲁ICP备20007159号-2