ALLPATHS: de novo assembly of whole-genome shotgun microreads.

By Jonathan Butler, Iain MacCallum, M. Kleber, I. Shlyakhter, Matthew K. Belmonte, Eric S. Lander, Chad Nusbaum, David B. Jaffe. Genome Research, 2008

888 citations recorded by the source corpus.

New DNA sequencing technologies deliver data at dramatically lower costs but demand new analytical methods to take full advantage of the very short reads that they produce. We provide an initial, theoretical solution to the challenge of de novo assembly from whole-genome shotgun "microreads." For 11 genomes of sizes up to 39 Mb, we generated high-quality assemblies from 80x coverage by paired 30-base simulated reads modeled after real Illumina-Solexa reads. The bacterial genomes of Campylobacter jejuni and Escherichia coli assemble optimally, yielding single perfect contigs, and larger genomes yield assemblies that are highly connected and accurate. Assemblies are presented in a graph form that retains intrinsic ambiguities such as those arising from polymorphism, thereby providing information that has been absent from previous genome assemblies. For both C. jejuni and E. coli, this assembly graph is a single edge encompassing the entire genome. Larger genomes produce more complicated graphs, but the vast majority of the bases in their assemblies are present in long edges that are nearly always perfect. We describe a general method for genome assembly that can be applied to all types of DNA sequence data, not only short read data, but also conventional sequence reads.

Subfields: Archeology, Civil and Structural Engineering, Mechanical Engineering

View Paper: https://www.semanticscholar.org/paper/9cbccbe327e51dffd5c9b8b3199b6958d000b902

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Archeology

1. Mihai Pop
2. Daniel R. Zerbino
3. Pavel A. Pevzner

In Civil and Structural Engineering

1. Mihai Pop
2. Daniel R. Zerbino
3. Pavel A. Pevzner
4. Sergey I. Nikolenko

In Mechanical Engineering

1. Mihai Pop
2. Daniel R. Zerbino
3. Pavel A. Pevzner
4. Sergey I. Nikolenko

Citations in the corpus

• Oases: robust de novo RNA-seq assembly across the dynamic range of expression levels (2012, methodology): “Scaffold construction takes place in two stages similarly to the approach described by Butler et al. (2008).”
• ABySS: a parallel assembler for short read sequence data. (2009, methodology): “The de Bruijn graph representation is prevalent in current short read assemblers, with Velvet (Zerbino and Birney 2008), ALLPATHS (Butler et al. 2008), and EULER-SR (Chaisson and Pevzner 2008) all following this approach.”
• SPAdes: A New Genome Assembly Algorithm and Its Applications to Single-Cell Sequencing (2012, methodology): “…for analysis of read-pairs (called bireads below) have been proposed (Pevzner et al., 2001; Pevzner and Tang, 2001; Zerbino and Birney, 2008; Butler et al., 2008; Simpson et al., 2009; Chaisson et al., 2009; Li et al., 2010), proper utilization of bireads remains, arguably, the most poorly…”
• Assembly of large genomes using second-generation sequencing. (2010, methodology): “These assemblers include Velvet (Zerbino and Birney 2008; Zerbino et al. 2009), ALLPATHS (Butler et al. 2008; Maccallum et al. 2009), ABySS (Simpson et al. 2009) SOAPdenovo (Li et al. 2010), and Contrail (http://contrailbio.sf.net).”
• High-quality draft assemblies of mammalian genomes from massively parallel sequence data (2010, methodology): “In its initial assembly representation (called a unipath graph), ALLPATHS collapses repeats of length ≥K, where K is chosen to be short enough that overlaps of length K between reads are abundant (16).”
• Musket: a multistage k-mer spectrum-based error corrector for Illumina sequence data (2013, methodology): “SGA (Simpson and Durbin, 2012) uses a memoryefficient Burrows Wheeler transform (Burrows and Wheeler, 1994) and an FM-index (Ferragina and Manzini, 2005) to represent the k-mer spectrum.”
• A window into third-generation sequencing. (2010, methodology): “A number of assemblers for de novo assembly have been written for SGS, including overlap graph approaches in which contigs are assembled by looking at sequence overlaps, like Edna (46), VCAKE (47) and SHARCGS (48); those based on the de Bruijn graph data structure (49), like Velvet (50), EULER-SR (5”
• IDBA-UD: a de novo assembler for single-cell and metagenomic sequencing data with highly uneven depth (2012, methodology): “To speed up the process, an error correction step is conducted to correct reads of high-depth regions that can be aligned to highconfident contigs.”
• Genome assembly reborn: recent computational challenges (2009, methodology): “Two recently developed assem-blers specifically targeted at short-read sequence data use the Eulerian strategy: Velvet [41], and Allpaths [42].”
• Assembly of long error-prone reads using de Bruijn graphs (2016, methodology): “De Bruijn graphs are a key algorithmic technique in genome assembly [23, 9, 12, 56, 61, 6].”
• Mind the Gap: Upgrading Genomes with Pacific Biosciences RS Long-Read Sequencing Technology (2012, methodology): “Second-generation genome assemblies have been based on shorter read, massively parallel sequencing technologies and De Bruijn graph assembly techniques [12–15] Depending on the dataset quality, polymorphism, and repetitiveness of the target genome, both approaches generate draft genomes with contig ”
• IDBA - A Practical Iterative de Bruijn Graph De Novo Assembler (2010, background): “shorter length, higher covera g , but relatively higher error rates) when compared to traditional Sanger reads, new asse mbly tools have emerged [2-11].”
• Next-generation DNA sequencing (2008, methodology): “Several assembly tools have recently been adapted or independently developed for generating assemblies from short, unpaired sequencing read”