New MHAP Algorithm Delivers Fast, High-Quality Genome Assemblies
Tuesday, May 26, 2015
A new publication in Nature Biotechnology reports the development of a lightning-fast genome assembly pipeline optimized for long reads. Scientists from the University of Maryland and the National Biodefense Analysis and Countermeasures Center created the MinHash Alignment Process, known as MHAP, to dramatically reduce assembly time and improve assembly quality. Their results are worth celebrating: assembly times were 600-fold faster compared to existing methods. “Using MHAP and the Celera Assembler, single-molecule sequencing can produce de novo near-complete eukaryotic assemblies that are 99.99% accurate when compared with available reference genomes,” the authors write. In the best cases, entire chromosome arms assembled into single-pieces from telomere to centromere!
MHAP takes a probabilistic approach to overlap-based assembly of long reads. MinHash represents longer text or a string of information as a set of fingerprints, allowing the assembly process to occur with more compact data that’s less computationally intensive. The authors’ MHAP overlapping method has been integrated into Celera Assembler for the assembly of gigabase-sized genomes, and is reported in their new paper “Assembling Large Genomes with Single-Molecule Sequencing and Locality-Sensitive Hashing.”
While the technical approach to MHAP is very clever, what impressed us most from this publication were the results. Lead authors Konstantin Berlin and Sergey Koren, along with their collaborators, tested the algorithm on five different genomes to gauge its performance. The organisms included Escherichia coli, Saccharomyces cerevisiae, Arabidopsis thaliana, Drosophila melanogaster, and a human cell line (CHM1). For E. coli, the assembly of 85x SMRT® Sequencing reads took 20 minutes on a 16-core desktop computer; for S. cerevisiae, assembly time was less than two hours and resulted in a four-fold improvement in N50 size compared to previous assemblies. “For E. coli, the total cost of PBcR-MHAP assembly and Quiver polishing is currently less than $2 [using cloud computing],” Berlin et al. write.
As genomes got larger, the speedup became more pronounced: the D. melanogaster assembly was 600 times faster than previous methods — from 629,000 CPU hours to just 1,086 CPU hours — and produced a contig N50 longer than the scaffold N50 of the Sanger reference assembly, and “hundreds of fold more contiguous” than a synthetic long-read assembly. For yeast, the results were even more impressive. The authors report that “a majority of the 16 chromosomes were completely resolved from telomere to telomere” in their MHAP long-read assembly of S. cerevisiae W303.
The team also assembled a human genome, using the publicly available PacBio® long-read CHM1 haploid human genome dataset. The assembly’s contig N50 is an order of magnitude larger than the original Sanger-based human assembly, the authors report, and may resolve more than 50 of the 800-plus annotated gaps in the latest human reference genome. Zooming in on the highly complex MHC region of the genome, the scientists found that 97 percent of the locus is represented in just two contigs, compared to more than 60 contigs covering the same region in a recently published short-read assembly of the same cell line.
With MHAP, the authors anticipate that pent-up demand for rapid, affordable, and high-quality assembly can now be met. “These results demonstrate that [PacBio] single-molecule sequencing alone can produce near-complete eukaryotic genomes,” they write. We’re certainly excited to see more reference-grade eukaryotic genome assemblies generated using the new MHAP method.