De novo sequence assemblers are a type of program that assembles short nucleotide sequences into longer ones without the use of a reference genome. These are most commonly used in bioinformatic studies to assemble genomes or transcriptomes. Two common types of de novo assemblers are greedy algorithm assemblers and De Bruijn graph assemblers.
There are two types of algorithms that are commonly utilized by these assemblers: greedy, which aim for local optima, and graph method algorithms, which aim for global optima. Different assemblers are tailored for particular needs, such as the assembly of (small) bacterial genomes, (large) eukaryotic genomes, or transcriptomes.
Greedy algorithm assemblers are assemblers that find local optima in alignments of smaller reads. Greedy algorithm assemblers typically feature several steps: 1) pairwise distance calculation of reads, 2) clustering of reads with greatest overlap, 3) assembly of overlapping reads into larger contigs, and 4) repeat. These algorithms typically do not work well for larger read sets, as they do not easily reach a global optimum in the assembly, and do not perform well on read sets that contain repeat regions.[1] Early de novo sequence assemblers, such as SEQAID[2] (1984) and CAP[3] (1992), used greedy algorithms, such as overlap-layout-consensus (OLC) algorithms. These algorithms find overlap between all reads, use the overlap to determine a layout (or tiling) of the reads, and then produce a consensus sequence. Some programs that used OLC algorithms featured filtration (to remove read pairs that will not overlap) and heuristic methods to increase speed of the analyses.
Graph method assemblers[4] come in two varieties: string and De Bruijn. String graph and De Bruijn graph method assemblers were introduced at a DIMACS[5] workshop in 1994 by Waterman[6] and Gene Myers.[7] These methods represented an important step forward in sequence assembly, as they both use algorithms to reach a global optimum instead of a local optimum. While both of these methods made progress towards better assemblies, the De Bruijn graph method has become the most popular in the age of next-generation sequencing. During the assembly of the De Bruijn graph, reads are broken into smaller fragments of a specified size, k. The k-mers are then used as edges in the graph assembly. Nodes are built as (k-1)-mers connect by an edge. The assembler will then construct sequences based on the De Bruijn graph. De Bruijn graph assemblers typically perform better on larger read sets than greedy algorithm assemblers (especially when they contain repeat regions).
| ABySS | parallel, paired-end sequence assembler designed for large genome assembly of short reads (genomic and transcriptomic), employ a Bloom filter to De Bruijn graph | Illumina | [8] [9] | 2009 / 2017 | OS | link |
| Canu | Small and large, haploid/diploid genomes | PacBio/Oxford Nanopore reads | [10] | 2001 / 2018 | OS | link |
| DISCOVAR | paired-end PCR-free reads (successor of ALLPATHS-LG) | Illumina (MiSeq or HiSeq 2500) | [11] | 2014 | OS | link |
| DNA Baser Sequence Assembler | DNA sequence assembly with automatic end trimming & ambiguity correction. Includes a base caller. | Sanger, Illumina | Heracle BioSoft SRL | 2018.09 | C ($69) | NA |
| DNASTAR Lasergene Genomics | Large genomes, exomes, transcriptomes, metagenomes, ESTs. Also de novo assembly and polishing of long read sequencing data from Oxford Nanopore and PacBio, including PacBio Hifi reads. | Illumina, ABI SOLiD, Roche 454, Ion Torrent, Solexa, Sanger | DNASTAR | 2007 / 2023 | C | link |
| Falcon | Diploid genomes | PacBio reads | [12] | 2014 / 2017 | OS | link |
| Flye | genomes and metagenomes. Makes use of repeat graphs | PacBio/Oxford Nanopore reads | [13] | 2018/2023 | OS | link |
| HGAP | Genomes up to 130 MB | PacBio reads | [14] | 2011 / 2015 | OS | link |
| hifiasm | Graph assembly | PacBio HiFi reads | [15] | 2021 | OS | link |
| Hinge | Small microbial genomes | PacBio/Oxford Nanopore reads | [16] | 2016 / 2018 | OS | link |
| MaSuRCA | Any size, haploid/diploid genomes | Illumina and PacBio/Oxford Nanopore data, legacy 454 and Sanger data | [17] | 2011 / 2018 | OS | link |
| Newbler | genomes, ESTs | 454, Sanger | 454 Life Sciences | 2004/2012 | C | link |
| Phrap | genomes | Sanger, 454, Solexa | Green, P. | 1994 / 2008 | C / NC-A | link |
| Plass | Protein-level assembler: assembles six-frame-translated sequencing reads into protein sequences | Illumina | [18] | 2018 / 2019 | OS | link |
| Ray | a suite of assemblers including de novo, metagenomic, ontology and taxonomic profiling; uses a De Bruijn graph | [19] | 2010 | OS | link | |
| SPAdes | (small) genomes, single-cell | Illumina, Solexa, Sanger, 454, Ion Torrent, PacBio, Oxford Nanopore | [20] | 2012 / 2021 | OS | link |
| Trinity | transcriptome assemblies by de Bruijn graph | Illumina RNA-seq | [21] | 2011 | link | |
| Velvet | (small) genomes | Sanger, 454, Solexa, SOLiD | [22] | 2007 / 2011 | OS | link |
*Licences: OS = Open Source; C = Commercial; C / NC-A = Commercial but free for non-commercial and academics|}Different assemblers are designed for different type of read technologies. Reads from second generation technologies (called short read technologies) like Illumina are typically short (with lengths of the order of 50-200 base pairs) and have error rates of around 0.5-2%, with the errors chiefly being substitution errors. However, reads from third generation technologies like PacBio and fourth generation technologies like Oxford Nanopore (called long read technologies) are longer with read lengths typically in the thousands or tens of thousands and have much higher error rates of around 10-20% with errors being chiefly insertions and deletions. This necessitates different algorithms for assembly from short and long read technologies.AssemblathonThere are numerous programs for de novo sequence assembly and many have been compared in the Assemblathon. The Assemblathon is a periodic, collaborative effort to test and improve the numerous assemblers available. Thus far, two assemblathons have been completed (2011 and 2013) and a third is in progress (as of April 2017). Teams of researchers from across the world choose a program and assemble simulated genomes (Assemblathon 1) and the genomes of model organisms whose that have been previously assembled and annotated (Assemblathon 2). The assemblies are then compared and evaluated using numerous metrics. Assemblathon 1Assemblathon 1[23] was conducted in 2011 and featured 59 assemblies from 17 different groups and the organizers. The goal of this Assembalthon was to most accurately and completely assemble a genome that consisted of two haplotypes (each with three chromosomes of 76.3, 18.5, and 17.7 Mb, respectively) that was generated using Evolver. Numerous metrics were used to assess the assemblies, including: NG50 (point at which 50% of the total genome size is reached when scaffold lengths are summed from the longest to the shortest), LG50 (number of scaffolds that are greater than, or equal to, the N50 length), genome coverage, and substitution error rate.
Assemblathon 2Assemblathon 2[24] improved on Assemblathon 1 by incorporating the genomes of multiples vertebrates (a bird (Melopsittacus undulatus), a fish (Maylandia zebra), and a snake (Boa constrictor constrictor)) with genomes estimated to be 1.2, 1.0, and 1.6Gbp in length) and assessment by over 100 metrics. Each team was given four months to assemble their genome from Next-Generation Sequence (NGS) data, including Illumina and Roche 454 sequence data.
See alsoReferences | ||||||