Archives

Categories

Y
Y

Building an NGS Reference List (de novo assembly category)

Homolog.us blog is written by professional janitors dedicated to clean up US science. During lunch breaks and other time off from the job, we discuss bioinformatics. The name 'homolog.us' is not a spelling mistake, but is derived by taking Arabic translation of the 'O' in the original word.

Please follow us on twitter – @homolog_us.

-------------------------------------------------------------------------------------------------------------

Did we miss any important category/paper?

Not all t’s are crossed and i’s are dotted yet. We will also add hyperlinks soon.

 

We created this list for our own convenience. However, it took us some time to get all the pieces together, and we thought posting the full list here would help someone else go to sleep early. Wherever we could, we added short narration about the papers or the section (again for our own convenience). There is no guarantee that the texts describe the papers accurately. Neither is there guarantee that the texts describe the papers inaccurately.

The papers mentioned here are related to bioinformatics problems, when no reference genome exists. We split the other set of papers with alignment, SNP calling, etc. into another set.

1. Pre-NGS Genome Assemblers

This section includes old assembly-related papers that we may need to cite from time to time. The first subgroup has links to base-calling and error correction programs such as phred, phrap and consed. The second subgroup has more sophisticated assemblers, but they mostly belong to overlap-layout-consensus type. Those dinosaurs used to rule over the world in not too distant past.

CAP3 and Celere are the only programs that we like. They are our pet dinosaurs. That does not mean the others are bad. We heard very good opinions about them from, well, the genome centers that nurture them. Most programs are associated with one or other genome centers. TIGR is from TIGR. ARACHNE belongs to Broad. Phusion is from EMBL. Atlas came from Baylor. Celera was written by J. C. Venter’s company, but is maintained by the bioinformatics group from Maryland.

Base-calling and error detection

Krawetz SA (1989) Sequence errors described in GenBank: a means to determine the accuracy of DNA sequence interpretation.Nucleic Acids Res. 17(10):3951-7. Link

Bonfield JK, Staden R (1995) The application of numerical estimates of base calling accuracy to DNA sequencing projects.Nucleic Acids Res. 23(8):1406-10. Link

Ewing B, Hillier L, Wendl M, Green P: Basecalling of automated sequencer traces using phred. I. Accuracy assessment.Genome Research 8:175-185 (1998). Link

Ewing B, Green P: Base calling of automated sequencer traces using phred. II. Error probabilities.Genome Research 8:186-194 (1998). Link

Gordon D, Abajian C, Green P: (1998) Consed: a graphical tool for sequence finishing.Genome Research 8:195-202 Link

Assembler

Sutton, G. G., White, O., Adams, M. D., Kerlavage, A. R. (1995) TIGR Assembler: A new tool for assembling large shotgun sequencing projects.Genome Science and Technology. 1(1): 9-19. Link

Huang X, Madan A, (1999) CAP3: A DNA sequence assembly program.Genome Res. 9(9):868-77. Link

Myers EW, Sutton GG, Delcher AL, Dew IM, Fasulo DP, Flanigan MJ, Kravitz SA, Mobarry CM, Reinert KHJ, Remington KA, et al.: (2000) A whole-genome assembly of Drosophila. Science287(5461):2196-2204. Link

Batzoglou S, Jaffe DB, Stanley K, Butler J, Gnerre S, Mauceli E, Berger B, Mesirov JP, Lander ES: (2002) ARACHNE: A whole-genome shotgun assembler. Genome Res12(1):177-189. Link

Mullikin JC, Ning ZM: (2003) The phusion assembler. Genome Res13(1):81-90. Link

Istrail, S. et al. (2004) Whole-Genome Shotgun Assembly and Comparison of Human Genome Assemblies. Proc. Nat. Acad. Sci. USA 101:1916-1921. Link

David B. Jaffe, Jonathan Butler, Sante Gnerre, Evan Mauceli, Kerstin Lindblad-Toh,Jill P. Mesirov, Michael C. Zody,and Eric S. Lander (2003) Whole-Genome Sequence Assembly for Mammalian Genomes: Arachne 2 Genome Res. 13(1): 91–96. Link

Havlak P, Chen R, Durbin KJ, Egan A, Ren YR, Song XZ, Weinstock GM, Gibbs RA (2004) The atlas genome assembly system. Genome Res14(4):721-732. Link

Chapman JA, Ho I, Sunkara S, Luo S, Schroth GP, et al. (2011) Meraculous: De Novo Genome Assembly with Short Paired-End Reads.PLoS ONE 6(8): e23501. Link

Mihai Pop, Adam Phillippy, Arthur L. Delcher, Steven L. Salzberg (2004) Comparative Genome Assembly, Briefings in Bioinformatics 5 (3):237-248. Link

R. Xia and A. Kim (2012) MERmaid: A Parallel Genome Assembler for the Cloud.Link

Weber JL, Myers EW (1997) Human whole-genome shotgun sequencing. Genome Res 7: 401–409. Link

2. NGS Genome Assemblers

non de Bruijn, k-mer based

You need a video to understand this category (pay attention to the guys, who jumped early).

Sundquist A, Ronaghi M, Tang HX, Pevzner P, Batzoglou S: (2007) Whole-Genome Sequencing and Assembly with High-Throughput, Short-Read Technologies. PLoS ONE, 2(5). Link

Warren RL, Sutton GG, Jones SJM, Holt RA: Assembling millions of short DNA sequences using SSAKE. Bioinformatics 2007, 23(4):500-501. Link

SHORTY (Chen and Skiena, 2007) [specialised in localising the use of paired-end reads.]

Daniel D Sommer, Arthur L Delcher, Steven L Salzbergand Mihai Po (2007) Minimus: a fast, lightweight genome assembler BMC Bioinformatics 2007, 8:64. Link

de Bruijn graph-based assemblers

Many articles in our blog explained this class of assemblers.

Idury RM, Waterman MS (1995) A new algorithm for DNA sequence assembly. J Comput Biol 2: 291–306. Link

Pevzner, Pavel A.; Tang, Haixu (2001). Fragment Assembly with Double-Barreled Data. Bioinformatics/ISMB 1: 1–9. Link

Chaisson M, Pevzner P, Tang H (2004) Fragment assembly with short reads. Bioinformatics 20: 2067-74. Link

Pevzner PA, Tang H, Waterman MS: An Eulerian path approach to DNA fragment assembly. Proc. Nat. Acad. Sci. USA 2001, 98(17):9748-9753. Link

Zerbino DR, Birney E: Velvet: Algorithms for de novo short read assembly using de Bruijn graphs. Genome Research 2008, 18(5):821-829. Link

Zerbino, D., Genome assembly and comparison using de Bruijn graphs Ph.D. Thesis, EBI, UK. Link

Butler J, MacCallum I, Kleber M, Shlyakhter IA, Belmonte MK, Lander ES, Nusbaum C, Jaffe DB: ALLPATHS: De novo assembly of whole-genome shotgun microreads. Genome Research 2008, 18(5):810-820. Link

Simpson JT, Wong K, Jackman SD, Schein JE, Jones SJ, Birol I: ABySS: A parallel assembler for short read sequence data. Genome Research 2009, 19(6):1117-1123. Link

Boisvert S, Laviolette F, Corbeil J. J Comput Biol. (2010) Ray: simultaneous assembly of reads from a mix of high-throughput sequencing technologies. Nov;17(11):1519-33. Epub 2010 Oct 20. Link

Applications

Li R, Zhu H, Ruan J, Qian W, Fang X, Shi Z, Li Y, Li S, Shan G, Kristiansen K, Li S, Yang H, Wang J, Wang J (2010) De novo assembly of human genomes with massively parallel short read sequencing. Genome Research20(2):265-272. Link

Li R, Fan W, Tian G, et al. (2010) The sequence and de novo assembly of the giant panda genome. Nature463 (7279):311-317. Link

Gnerre S, MacCallum I, Przybylski D, Ribeiro FJ, Burton JN, Walker BJ, Sharpe T, Hall G, Shea TP, Sykes S, et al. (2011) High-quality draft assemblies of mammalian genomes from massively parallel sequence data. P Natl Acad Sci USA108(4):1513-1518. Link

Chitsaz H, Yee-Greenbaum J, Tesler G, Lombardo M, Dupont C, et al. (2011) Efficient de novo assembly of single-cell bacterial genomes from short-read data sets. Nat Biotechnol 29: 915-21. Link

Rodrigue S, Malmstrom R, Berlin A, Birren B, Henn M, et al. (2009) Whole genome amplication and de novo assembly of single bacterial cells. PLoS One 4: e6864. Link

Schuster SC, Miller W, Ratan A, Tomsho LP, Giardine B, et al. (2010) Complete Khoisan and Bantu genomes from southern Africa.Nature 463: 943–947. Link

Comparison

Deng HW, Lin Y, Li J, Shen H, Zhang L, Papasian CJ (2011) Comparative studies of de novo assembly tools for next-generation sequencing technologies. Bioinformatics27(15):2031-2037. Link

Salzberg SL, Phillippy AM, Zimin AV, Puiu D, Magoc T, Koren S, Treangen T, Schatz MC, Delcher AL, Roberts M, et al. (2011) GAGE: A critical evaluation of genome assemblies and assembly algorithms. Genome Res. Link

Zhang WY, Chen JJ, Yang Y, Tang YF, Shang J, Shen BR (2011) A Practical Comparison of De Novo Genome Assembly Software Tools for Next-Generation Sequencing Technologies. PLoS ONE, 6(3). Link

Magoč T, Salzberg SL (2011) FLASH: Fast Length Adjustment of Short Reads to Improve Genome Assemblies. Bioinformatics. Link

Salzberg SL, Kurtz S, Phillippy A, Delcher AL, Smoot M, Shumway M, Antonescu C (2004) Versatile and open software for comparing large genomes. Genome Biol, 5(2). Link

D. Earl et al. (2011) Assemblathon 1: A competitive assessment of de novo short read assembly methods, Genome Research, 21:2224-2241. Link

3. Exomes, Transcriptomes, Metagenomes and Highly Polymorphic Genomes

Transcriptome Assemblers

Robertson D, Schein J, Chiu R, Corbett R. Field M et al. (2010) De novo assembly and analysis of RNA-seq data Nature Methods 7, 909–912. Link

Grabherr MG, Haas BJ, Yassour M, Levin JZ, Thompson DA et al. (2011) Full-length transcriptome assembly from RNA-seq data without a reference genome. Nat Biotechnol. 29(7):644-52. Link

Schulz M, Zerbino D, Vingron M, Birney E (2012) Oases: robust de novo rna-seq assembly across the dynamic range of expression levels. Bioinformatics 28: 1086-92. Link

Metagenomes

Namiki T, Hachiya T, Tanaka H, Sakakibara Y (2011) MetaVelvet: An extension of Velvet assem-bler to de novo metagenome assembly from short sequence reads. ACM Conference on Bioinformatics, Computational Biology and Biomedicine. Link

Peng Y, Leung H, Yiu S, Chin F (2011) Meta-idba: a de novo assembler for metagenomic data. Bioinformatics 27: i94-101. Link

Vaughn Iverson, Robert M. Morris, Christian D. Frazar, Chris T. Berthiaume, Rhonda L. Morales, E. Virginia Armbrust (2012) Untangling Genomes from Metagenomes: Revealing an Uncultured Class of Marine Euryarchaeota, Science 335(6068):587-590. Link

C. T. B. on scaling metagenome

Polymorphic Genomes

Iqbal Z, Caccamo M, Turner I, Flicek P, McVean G (2012) De novo assembly and genotyping of variants using colored de bruijn graphs. Nat Genet 44: 226-32. Link

S. Huang et al. (2012) HaploMerger: Reconstructing allelic relationships for polymorphic diploid genome assemblies, Genome Research. Link

Targeted Assembly

P. Peterlongo and R. Chikhi (2011) Mapsembler, targeted and micro assembly of large NGS datasets on a desktop computer BMC Bioinformatics 2012, 13:48. Link

René L. Warren Robert A. Holt (2011) Targeted Assembly of Short Sequence Reads PLOS ONE. Link

4. Faster, better, cheaper

k-mer counting

Bloom BH (1974) Space/time trade-offs in hash coding with allowable errors. Commun ACM, 13:422-426. Link

Marçais G, Kingsford C (2011) A fast, lock-free approach for efficient parallel counting of occurrences of k-mers. Bioinformatics 2011, 27(6):764-770. Link

Melsted P, Pritchard JK (2011) Efficient counting of k-mers in DNA sequences using a bloom filter. Bmc Bioinformatics12. Link

C. T. Brown khmer https://github.com/ctb/

Storage

Christley S, Lu Y, Li C, Xie X (2009) Human genomes as email attachments. Bioinformatics ;25:274-275.

Conway TC, Bromage AJ (2011) Succinct data structures for assembling large genomes. Bioinformatics27(4):479-486. Link

Fritz MH-Y, Leinonen R, Cochrane G, Birney E. (2011) Efficient storage of high throughput DNA sequencing data using reference-based compression. Genome Res.;21:734-740.

Roberts M, Hayes W, Hunt BR, Mount SM, Yorke JA (2004) Reducing storage requirements for biological sequence comparison. Bioinformatics20(18):3363-3369. Link

Pinho A, Pratas D, Garcia S (2012) GReEn: a tool for efficient compression of genome resequencing data. Nucleic Acids Res 40: e27. Link

Daniel C. Jones, W. L. Ruzzo, X. Peng, M. G. Katze (2012) Compression of next-generation sequencing reads aided by highly efficient de novo assembly, Nucleic Acids Research, Link https://github.com/dcjones/quip#readme

Rayan Chikhiand Guillaume Rizk (2012) Space-efficient and exact de Bruijn graph representation based on a Bloom Filter. Link

Kozanitis C, Saunders C, Kruglyak S, Bafna V, Varghese G. (2011) Compressing genomic sequence fragments using SlimGene. J Comput Biol. (3):401-13.Link

Pell J. et al.(2012) Scaling metagenome sequence assembly with probabilistic de Bruijn graphs, Proc. Nat. Acad. Sci. USA. Link

C. Titus Brown, Adina Howe, Qingpeng Zhang, Alexis B. Pyrkosz, Timothy H. Brom A Reference-Free Algorithm for Computational Normalization of Shotgun Sequencing Data http://arxiv.org/abs/1203.4802

Error correction

Kelley D, Schatz M, Salzberg S: (2010) Quake: quality-aware detection and correction of sequencing errors. Genome Biology11(11):R116.

Medvedev P, Scott E, Kakaradov B, Pevzner P (2011) Error correction of high-throughput sequencing datasets with non-uniform coverage. Bioinformatics 27: i137-41.

C. Titus Brown, Adina Howe, Qingpeng Zhang, Alexis B. Pyrkosz, Timothy H. Brom A Reference-Free Algorithm for Computational Normalization of Shotgun Sequencing Data http://arxiv.org/abs/1203.4802

Hadoop

Schatz M (2009) Cloudburst: highly sensitive read mapping with mapreduce. Bioinformatics 25: 1363-9.

Contrail http://sourceforge.net/apps/mediawiki/contrail-bio/index.php?title=Contrail

Hardware-accelerators

Shi H, Schmidt B, Liu W, Müller-Wittig W (2010) A Parallel Algorithm for Error Correction in High-Throughput Short-Read Data on CUDA-Enabled Graphics Hardware. Journal of Computational Biology17(4):603-615.

Liu Y, Schmidt B, Maskell DL (2011) Parallelized short read assembly of large genomes using de Bruijn graphs. BMC Bioinformatics, 12:354. Link

String graph assembler

Myers EW (2005) The fragment assembly string graph. Bioinformatics21:79-85. Link

Simpson JT, Durbin R: Efficient de novo assembly of large genomes using compressed data structures. Genome Res 2011. Link

Simpson J, Durbin R (2010) Efficient construction of an assembly string graph using the fm-index.

Bioinformatics 26: i367-73. Link

Simpson J, Durbin R (2012) Efficient de novo assembly of large genomes using compressed data structures. Genome Res 22: 549-56. Link

Scaffolding

Zerbino DR, McEwen GK, Margulies EH, Birney E (2009) Pebble and rock band: heuristic resolution of repeats and scaffolding in the velvet short-read de novo assembler. PLoS One 4: e8407. Link

Koren S, Treangen T, Pop M (2011) Bambus 2: scaffolding metagenomes.Bioinformatics 27: 2964-71. Link

Alexey A. Gritsenko et al. (2012) GRASS: a generic algorithm for scaffolding next-generation sequencing assemblies Bioinformatics 28(11): 1429-1437 Abstract

Repeats

Zerbino DR, McEwen GK, Margulies EH, Birney E (2009) Pebble and rock band: heuristic resolution of repeats and scaffolding in the velvet short-read de novo assembler. PLoS One 4: e8407. Link

Do H, Choi K, Preparata F, Sung W, Zhang L (2008) Spectrum-based de novo repeat detection in genomic sequences. J Comput Biol 15: 469-87. Link

Novak P, Neumann P, Macas J (2010) Graph-based clustering and characterization of repetitive sequences in next-generation sequencing data. BMC Bioinformatics 11: 378. Link

Gu W, Castoe T, Hedges D, Batzer M, Pollock D (2008) Identification of repeat structure in large genomes using repeat probability clouds. Anal Biochem 380: 77-83. Link

6. Reviews, visions and IMs

Metzker M (2010) Sequencing technologies – the next generation.Nat Rev Genet 11: 31-46. Link

Shendure J. and Ji H. (2008) Next-generation DNA sequencing, Nature Biotechnol. 26, 1135 – 1145. Link

Phillippy AM, Schatz MC, Pop M (2008) Genome assembly forensics: finding the elusive mis-assembly.Genome Biol9(3). Link

Miller J, Koren S, Sutton G (2010) Assembly algorithms for next-generation sequencing data.Genomics 95: 315-27. Link

Trapnell C, Salzberg S (2009) How to map billions of short reads onto genomes.Nat Biotechnol 27: 455-7. Link

Stein L. (2010) The case for cloud computing in genome informatics.Genome Biol 11: 207. Link

Li Y, Hu Y, Bolund L, Wang J (2010) State of the art de novo assembly of human genomes from massively parallel sequencing data.Hum Genomics 4: 271-7. Link

Compeau P, Pevzner P, Tesler G (2011) How to apply de bruijn graphs to genome assembly.Nat Biotechnol. 29: 987-91. Link

Nagarajan N, Pop M (2009) Parametric complexity of sequence assembly: theory and applications to next generation sequencing.J Comput Biol 16: 897-908. Link

Carl Kingsford, Michael C Schatz and Mihai Pop (2010) Assembly Complexity of prokaryotic genomes using short reads BMC Bioinformatics 2010, 11:21 Link

Pop M, Salzberg SL (2008) Bioinformatics challenges of new sequencing technology. Trends Genet 24: 142–149. Link

Flicek P, Birney E (2009) Sense from sequence reads: methods for alignment and assembly. Nat Methods 6: S6–S12. Link (pdf), Link

 




-------------------------------------------------------------------------------------------------------------
Heroes and Heroines of New Media--2014

I am strongly influenced by Charles Hugh Smith, who runs his insightful social blog of Two Minds. I hope he will not mind, if I copy his style of acknowledgement to the supporters of our blog.

Our blog is deeply honored by the generous contribution of the following readers. Without their patronage, this site would go away.

Outstandingly Generous:  
Amemiya C. Schnable J. Bowman B.

We are also looking for subscribers to get help to finish the tutorials. Please see this post for details.

9 comments to Building an NGS Reference List (de novo assembly category)

Leave a Reply

  

  

  

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>