De novo sequence assemblers


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.

Types of de novo 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 bacterial genomes, 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 perform well on read sets that contain repeat regions. Early de novo sequence assemblers, such as SEQAID and CAP, used greedy algorithms, such as overlap-layout-consensus algorithms. These algorithms find overlap between all reads, use the overlap to determine a layout of the reads, and then produce a consensus sequence. Some programs that used OLC algorithms featured filtration and heuristic methods to increase speed of the analyses.
Graph method assemblers come in two varieties: string and De Bruijn. String graph and De Bruijn graph method assemblers were introduced at a DIMACS workshop in 1994 by Waterman and Gene Myers. 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 nodes in the graph assembly. Nodes that overlap by some amount are then 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.

Commonly used programs

Different assemblers are designed for different type of read technologies. Reads from second generation technologies like Illumina are typically short 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 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.

SPAdes

is a De Bruijn graph method assembler that is designed to assemble small genomes, such as bacterial genomes. It uses a multi-sized De Bruijn graph to guide assembly.

Ray

Ray is suite of assemblers that includes: Ray, RayMeta, RayCommunities, RayOntologies, and RaySurveyor. Ray also has a web-interface, called Ray Cloud Browser.

ABySS

A de novo, parallel, paired-end sequence assembler designed for large genome assembly of short reads. There are two versions: ABySS and Trans-ABySS.

ALLPATHS-LG

ALLPATHS-LG is a software designed for the de novo assembly of large and small genomes. The software features algorithms to handle large sequence repeats, correct errors, use data from jumping libraries, be more efficient in memory usage, and assemble low coverage regions.

Trinity

Trinity utilizes a three step process to produce high-quality transcriptome assemblies: 1) Inchworm develops a k-mer library and uses a greedy algorithm to assemble transcript contigs, 2) Chrysalis finds overlap in the Inchworm contigs and assembles De Bruijn graphs, and 3) Butterfly reconciles the Chrysalis De Bruijn graphs with the original read set to reconstruct transcripts. This method has been found to reconstruct high quality transcriptomes.

HGAP

HGAP was the first long read assembler. It was developed by Pacific Biosciences and Joint Genomics Institute and was designed mainly for haploid organisms. It is available .

Falcon

Falcon is a long read assembler designed by Pacific Biosciences to work on diploid organisms. It is available . FALCON-Phase, developed in collaboration with Phase Genomics, uses Hi-C data to phase haplotypes.

Canu

Canu is a long read assembler which works on both third and fourth generation reads. It is a successor of the old Celera Assembler. It is available .

Hinge

Hinge is also a long read assembler which works on both third and fourth generation reads but is designed mainly for shorter microbial genomes rather than large scale genomes. It is available .

Velvet

is designed to deal with de novo genome assembly and short read sequencing alignments. This is achieved through the manipulation of de Bruijn graphs for genomic sequence assembly via the removal of errors and the simplification of repeated regions.

Assemblathon

There 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 and a third is in progress. Teams of researchers from across the world choose a program and assemble simulated genomes and the genomes of model organisms whose that have been previously assembled and annotated. The assemblies are then compared and evaluated using numerous metrics.

Assemblathon 1

Assemblathon 1 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 that was generated using Evolver. Numerous metrics were used to assess the assemblies, including: NG50, LG50, genome coverage, and substitution error rate.
Assemblathon 2 improved on Assemblathon 1 by incorporating the genomes of multiples vertebrates, a fish, and a snake ) 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 data, including Illumina and Roche 454 sequence data.