Efficient Assembly of Large Genomes Using Single-Molecule Sequencing and Locality Sensitive Hashing

We have developed a new algorithm for the alignment of single-molecule sequencing reads and applied it to the de novo assembly of eukaryotic genomes including fly, mosquito, goat, and human. To date, the assembly of large genomes from single-molecule sequencing has been limited by the significant computational requirements. To address this bottleneck, we developed the MinHash Alignment Process (MHAP), which leverages a dimensionality reduction approach based on locality-sensitive hashing to efficiently assemble the long, noisy reads generated by the PacBio RSII and Oxford Nanopore MinION instruments. Compared to previous approaches, MHAP is hundreds of fold faster, enabling the assembly of gigabase-scale genomes from single-molecule sequencing alone. Together with Celera Assembler, MHAP was used to reconstruct the genomes of Saccharomyces cerevisiae, Arabidopsis thaliana, Anopheles gambiae, Drosophila melanogaster, San Clemente goat, and a human hydatidiform mole from high-coverage PacBio SMRT sequencing. The resulting assemblies are far superior to any previous de novo assemblies of these organisms, and have the potential to fill gaps in the human and D. melanogaster reference genomes that have persisted for over a decade. In D. melanogaster we identified novel heterochromatic and telomeric transition sequences that are absent from the current reference, and in human, we assembled low-complexity gap sequence not present in the GRCh38 reference. Assemblies of the smaller eukaryotic genomes include fully resolved chromosomes arms, and in the case of yeast, a majority of chromosomes are completely spanned from telomere to telomere. Our results demonstrate that single-molecule sequencing alone can produce near-complete eukaryotic genomes at modest cost.