Assembling large genomes with single-molecule sequencing and locality-sensitive hashing

Long-read, single-molecule real-time (SMRT) sequencing is routinely used to finish microbial genomes, but available assembly methods have not scaled well to larger genomes. We introduce the MinHash Alignment Process (MHAP) for overlapping noisy, long reads using probabilistic, locality-sensitive hashing. Integrating MHAP with the Celera Assembler enabled reference-grade de novo assemblies of Saccharomyces cerevisiae, Arabidopsis thaliana, Drosophila melanogaster and a human hydatidiform mole cell line (CHM1) from SMRT sequencing. The resulting assemblies are highly continuous, include fully resolved chromosome arms and close persistent gaps in these reference genomes. Our assembly of D. melanogaster revealed previously unknown heterochromatic and telomeric transition sequences, and we assembled low-complexity sequences from CHM1 that fill gaps in the human GRCh38 reference. 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.

• Publication year

  2014

• Venue

  Nature Biotechnology

• Publication date

  2014-08-14

• Fields of study

  Biology, Medicine, Computer Science

• Identifiers
  DOI 10.1038/nbt.3238PMID 26006009
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• One chromosome, one contig: complete microbial genomes from long-read sequencing and assembly.

  2015cited by this paper
• Reconstructing complex regions of genomes using long-read sequencing technology

  2014cited by this paper
• Near-optimal assembly for shotgun sequencing with noisy reads

  2014cited by this paper
• Resolving the complexity of the human genome using single-molecule sequencing

  2014cited by this paper
• Long-read, whole-genome shotgun sequence data for five model organisms

  2014cited by this paper
• A P. aeruginosa serotype-defining single read from our first Oxford Nanopore run

  2014cited by this paper
• Extensive Error in the Number of Genes Inferred from Draft Genome Assemblies

  2014influential reference
• A reference bacterial genome dataset generated on the MinION™ portable single-molecule nanopore sequencer

  2014cited by this paper
• RepARK—de novo creation of repeat libraries from whole-genome NGS reads

  2014cited by this paper
• Error correction and assembly complexity of single molecule sequencing reads

  2014influential reference
• Illumina TruSeq Synthetic Long-Reads Empower De Novo Assembly and Resolve Complex, Highly-Repetitive Transposable Elements

  2014cited by this paper
• Single haplotype assembly of the human genome from a hydatidiform mole

  2014cited by this paper
• Efficient Local Alignment Discovery amongst Noisy Long Reads

  2014cited by this paper
• The second Oxford Nanopore read ever published

  2014cited by this paper
• Characterizing and measuring bias in sequence data

  2013influential reference
• PBSIM: PacBio reads simulator - toward accurate genome assembly

  2013cited by this paper
• Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM

  2013cited by this paper
• Nonhybrid, finished microbial genome assemblies from long-read SMRT sequencing data

  2013cited by this paper
• FlyBase 102—advanced approaches to interrogating FlyBase

  2013cited by this paper
• The UCSC Genome Browser database: 2014 update

  2013cited by this paper
• Sequence assembly demystified

  2013cited by this paper
• Chromosome-scale scaffolding of de novo genome assemblies based on chromatin interactions

  2013cited by this paper
• Reducing assembly complexity of microbial genomes with single-molecule sequencing

  2013cited by this paper
• Optimal assembly for high throughput shotgun sequencing

  2013cited by this paper
• High-throughput genome scaffolding from in-vivo DNA interaction frequency

  2013cited by this paper
• MC-MinH: Metagenome Clustering using Minwise based Hashing

  2013cited by this paper
• GAGE-B: an evaluation of genome assemblers for bacterial organisms

  2013cited by this paper
• Whole-genome haplotype reconstruction using proximity-ligation and shotgun sequencing

  2013cited by this paper
• Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality

  2012cited by this paper
• Mind the Gap: Upgrading Genomes with Pacific Biosciences RS Long-Read Sequencing Technology

  2012cited by this paper
• De novo assembly of highly diverse viral populations

  2012cited by this paper
• Mapping single molecule sequencing reads using basic local alignment with successive refinement (BLASR): application and theory

  2012influential reference
• The Saccharomyces cerevisiae W303-K6001 cross-platform genome sequence: insights into ancestry and physiology of a laboratory mutt

  2012cited by this paper
• SPAdes: A New Genome Assembly Algorithm and Its Applications to Single-Cell Sequencing

  2012cited by this paper
• Finished bacterial genomes from shotgun sequence data

  2012cited by this paper
• RazerS 3: Faster, fully sensitive read mapping

  2012cited by this paper
• Hybrid error correction and de novo assembly of single-molecule sequencing reads

  2012cited by this paper
• GAGE: A critical evaluation of genome assemblies and assembly algorithms.

  2012cited by this paper
• Faster and More Accurate Sequence Alignment with SNAP

  2011cited by this paper
• Assembly of large genomes using second-generation sequencing.

  2010cited by this paper
• Nanopore Sequencing: Electrical Measurements of the Code of Life

  2010cited by this paper
• High-resolution human genome structure by single-molecule analysis

  2010cited by this paper
• Assembly algorithms for next-generation sequencing data.

  2010cited by this paper
• Real-time DNA sequencing from single polymerase molecules.

  2010cited by this paper
• Real-Time DNA Sequencing from Single Polymerase Molecules

  2009cited by this paper
• Genome assembly reborn: recent computational challenges

  2009cited by this paper
• Continuous base identification for single-molecule nanopore DNA sequencing.

  2009cited by this paper
• The potential and challenges of nanopore sequencing

  2008cited by this paper
• Near Duplicate Image Detection: min-Hash and tf-idf Weighting

  2008cited by this paper
• Genome assembly forensics: finding the elusive mis-assembly

  2008cited by this paper
• Sequence Finishing and Mapping of Drosophila melanogaster Heterochromatin

  2007cited by this paper
• Efficient q-Gram Filters for Finding All epsilon-Matches over a Given Length

  2006cited by this paper
• Genomic organization of the Drosophila telomere retrotransposable elements.

  2006cited by this paper
• Univariate Discrete Distributions

  2006cited by this paper
• Telomeres and human disease: ageing, cancer and beyond

  2005cited by this paper
• Repbase Update, a database of eukaryotic repetitive elements

  2005cited by this paper
• Efficient q-Gram Filters for Finding All ∊-Matches over a Given Length

  2005cited by this paper
• Comparative genome assembly

  2004cited by this paper
• Gapped Local Similarity Search with Provable Guarantees

  2004cited by this paper
• Reducing storage requirements for biological sequence comparison

  2004cited by this paper
• Versatile and open software for comparing large genomes

  2004cited by this paper
• GeneFarm, structural and functional annotation of Arabidopsis gene and protein families by a network of experts

  2004cited by this paper
• Xorshift RNGs

  2003cited by this paper
• Similarity estimation techniques from rounding algorithms

  2002cited by this paper
• Multiple sequence alignment using partial order graphs

  2002cited by this paper
• The transposable elements of the Drosophila melanogaster euchromatin: a genomics perspective

  2002cited by this paper
• Initial sequencing and analysis of the human genome

  2001cited by this paper
• Efficient large-scale sequence comparison by locality-sensitive hashing

  2001cited by this paper
• The sequence of the human genome (abstract only)

  2001cited by this paper
• The genome sequence of Drosophila melanogaster.

  2000cited by this paper
• Identifying and Filtering Near-Duplicate Documents

  2000cited by this paper
• Analysis of the genome sequence of the flowering plant Arabidopsis thaliana

  2000cited by this paper
• A whole-genome assembly of Drosophila.

  2000cited by this paper
• Complete sequence and gene map of a human major histocompatibility complex

  1999cited by this paper
• Complete sequence and gene map of a human major histocompatibility complex

  1999cited by this paper
• Complete sequence and gene map of a human major histocompatibility complex. The MHC sequencing consortium.

  1999cited by this paper
• Base-calling of automated sequencer traces using phred. I. Accuracy assessment.

  1998cited by this paper
• Human whole-genome shotgun sequencing.

  1997cited by this paper
• On the resemblance and containment of documents

  1997cited by this paper
• Syntactic Clustering of the Web

  1997cited by this paper
• Overview of the yeast genome.

  1997cited by this paper
• ReAligner: A Program for Refining DNA Sequence Multi-Alignments

  1997cited by this paper
• Structure, function, and replication of Saccharomyces cerevisiae telomeres.

  1996cited by this paper
• Transposons in place of telomeric repeats at a Drosophila telomere.

  1993cited by this paper
• Ordered restriction maps of Saccharomyces cerevisiae chromosomes constructed by optical mapping.

  1993cited by this paper
• Suffix arrays: a new method for on-line string searches

  1993cited by this paper
• Univariate Discrete Distributions

  1993cited by this paper
• Approximate String Matching with q-grams and Maximal Matches

  1992cited by this paper
• Frequent transpositions of Drosophila melanogaster HeT‐A transposable elements to receding chromosome ends.

  1992cited by this paper
• Basic local alignment search tool.

  1990cited by this paper
• AnO(ND) difference algorithm and its variations

  1986cited by this paper
• Sequence the Human Genome

  1986cited by this paper
• Estimating Parameters in Continuous Univariate Distributions with a Shifted Origin

  1983cited by this paper
• Identification of common molecular subsequences.

  1981cited by this paper
• A new computer method for the storage and manipulation of DNA gel reading data.

  1980cited by this paper
• A rapid method for determining sequences in DNA by primed synthesis with DNA polymerase.

  1975cited by this paper
• Error detecting and error correcting codes

  1950cited by this paper
• Distribution de la flore alpine dans le bassin des Dranses et dans quelques régions voisines

  year unknowncited by this paper
• SLOW-GROWING SUBDIVISIONS IN ANY DIMENSION: TOWARDS REMOVING THE CURSE OF DIMENSIONALITY

  year unknowncited by this paper

• Hubeiibacter gen. nov., a new genus of Moraxellaceae: identification of Hubeiibacter jixunmingi sp. nov. isolated from blowhole swab samples of Yangtze finless porpoise (Neophocaena asiaeorientalis asiaeorientalis).

  2026cites this paper
• Compressed inverted indexes for scalable sequence similarity

  2026cites this paper
• Carbonicoccus gen. nov., Carbonicoccus zhangzhihongae sp. nov. and Carbonicoccus niuqiaonis sp. nov., novel taxa assignable to the family Propionibacteriaceae and derived from the coal mine dust samples in Shanxi Province of China.

  2026cites this paper
• Paracoccus jiaweipingae sp. nov. and Paracoccus zhouxuedongae sp. nov., isolated from blowhole swab samples of Yangtze finless porpoise (Neophocaena asiaeorientalis asiaeorientalis).

  2026cites this paper
• Direct interspecies electron transfer-based methanogenic aggregate: A survival strategy to overcome defensive attack from type VI secretion system during syntrophic cooperation.

  2026cites this paper
• A case report of bacteriophage therapy for the treatment of lung infection due to carbapenem-resistant Pseudomonas aeruginosa

  2025cites this paper
• Adaptive Feeding Strategies Facilitate Resilience of Deep‐Sea Cold Seep Molluscs Confronting Climate Change

  2025influential citation
• MELO-ED: learning locality-sensitive multi-embeddings for edit distance

  2025cites this paper
• Telomere-to-telomere DNA replication timing profiling using single-molecule sequencing with Nanotiming

  2025cites this paper
• First Report and Pathogenicity Analysis of Photobacterium damselae subsp. piscicida in Cage-Cultured Black Rockfish (Sebastes schlegelii) Associated with Skin Ulcers

  2025influential citation
• Chromosome-level genome assembly of the apple jewel beetle Agrilus mali (Coleoptera: Buprestidae)

  2025cites this paper
• Brachymonas wangyanguii sp. nov., isolated from the coal samples in Shanxi Province of China.

  2025cites this paper
• Two new members of the family Aerococcaceae: Tuanshanicoccus yangjingiae gen. nov., sp. nov. and Tuanshanicoccus lijuaniae sp. nov., isolated from the trachea of Marmota himalayana.

  2025cites this paper
• Discovery of New Angucyclin(on)e Derivatives and Their Genetic Architecture from Streptomyces sp. SYP-A7185 in the Rhizosphere Soil of Panax notoginseng

  2025cites this paper
• Multi-metric locality sensitive hashing enhances alignment accuracy of bisulfite sequencing reads: BisHash

  2025cites this paper
• Molecular characterization, comparative genome analysis and resistance determinants of three clinical Elizabethkingia miricola strains isolated from Michigan

  2025cites this paper
• Comprehensive Analysis of Full-Length Transcriptome Profiling, Genetic and Phenotypic Variation in Multiplier Onion (Allium cepa var. aggregatum) Accessions in China

  2025cites this paper
• Accelerating long-read overlap detection for genome assembly with a two-hash table strategy

  2025cites this paper
• Comparative genome analyses of Aspergillus oryzae and Aspergillus flavus originated from a Korean fermentation starter, nuruk.

  2025cites this paper
• Whole-Genome Characterization of Inonotus hispidus from Ulmus macrocarpa and Its Comparative Genomics with Strains from Morus alba and Acer truncatum

  2025cites this paper
• Genomic and Transcriptomic Characterization of a High-Yield Docosahexaenoic Acid (DHA) Mutant Schizochytrium sp. HS01

  2025influential citation
• Recent advances in the methods and clinical applications of next-generation sequencing in genomic profiling and precision cancer therapy

  2025cites this paper
• Genetic variation in recalcitrant repetitive regions of the Drosophila melanogaster genome

  2025cites this paper
• Loss of a major venom toxin gene in a Western Diamondback rattlesnake population

  2025cites this paper
• Whole genome analysis of Shigella sp. JZ001: a novel strain isolated from diarrheic suckling mice

  2025cites this paper
• Verkko2 integrates proximity-ligation data with long-read De Bruijn graphs for efficient telomere-to-telomere genome assembly, phasing, and scaffolding

  2025cites this paper
• A survey of sequence-to-graph mapping algorithms in the pangenome era

  2025cites this paper
• RE-Trace: Re-identification of Modified GPS Trajectories

  2024cites this paper
• Emergence of a clinical Salmonella enterica serovar 1,4,[5], 12: i:-isolate, ST3606, in China with susceptibility decrease to ceftazidime-avibactam carrying a novel blaCTX-M-261 variant and a blaNDM-5

  2024influential citation
• Comprehensive assessment of 11 de novo HiFi assemblers on complex eukaryotic genomes and metagenomes

  2024cites this paper
• Advancements in long-read genome sequencing technologies and algorithms.

  2024cites this paper
• Dipterocarpoidae genomics reveal their demography and adaptations to Asian rainforests

  2024cites this paper
• Genetic variation in recalcitrant repetitive regions of the Drosophila melanogaster genome

  2024cites this paper
• Asynchronous Distributed Actor-Based Approach to Jaccard Similarity for Genome Comparisons

  2024cites this paper
• NetDS: Distributed Search Framework with Hybrid Acceleration Methods

  2024cites this paper
• Two new members of the genus Sphingobacterium: Sphingobacterium zhuxiongii sp. nov. and Sphingobacterium luzhongxinii sp. nov.

  2024cites this paper
• Low-input PacBio sequencing generates high-quality individual fly genomes and characterizes mutational processes

  2024cites this paper
• Effects of different assembly strategies on gene annotation in activated sludge.

  2024cites this paper
• Thalassemia: Next Generation (NGS) and Third Generation Sequencing (TGS) for the Diagnosis.

  2024cites this paper
• MinCloud: Trusted and transferable MinHash-based framework for unknown malware detection for Linux cloud environments

  2024cites this paper
• Production of polyhydroxyalkanoate from new isolated bacteria of Acidovorax diaphorobacter ZCH-15 using orange peel and its underlying metabolic mechanisms.

  2024cites this paper
• Natural selection and recombination at host-interacting lipoprotein loci drive genome diversification of Lyme disease and related bacteria

  2024cites this paper
• Identifying Anomaly in IoT Traffic Flow With Locality Sensitive Hashes

  2024cites this paper
• Genomic Characterization and Comparative Analysis of Streptococcus zhangguiae sp. nov. Isolated from the Respiratory Tract of Marmota Himalayana

  2024influential citation
• Gut symbiont-derived sphingosine modulates vector competence in Aedes mosquitoes

  2024cites this paper
• A survey of k-mer methods and applications in bioinformatics

  2024cites this paper
• CAREx: context-aware read extension of paired-end sequencing data

  2024cites this paper
• Rapidly engineering an osmotic-pressure-tolerant gut bacterium for efficient non-sterile production of bulk chemicals

  2024cites this paper
• Efficient Seeding for Error-Prone Sequences with SubseqHash2

  2024cites this paper
• Adlercreutzia wanghongyangiae sp. nov., and Adlercreutzia shanghongiae sp. nov., two new members of the genus Adlercreutzia isolated from plateau pika (Ochotona curzoniae).

  2024cites this paper
• Revisiting Main Memory-Based Covert and Side Channel Attacks in the Context of Processing-in-Memory

  2024cites this paper
• MIKE: an ultrafast, assembly-, and alignment-free approach for phylogenetic tree construction

  2024cites this paper
• Genome assembly in the telomere-to-telomere era

  2024cites this paper
• Fast multiple sequence alignment via multi-armed bandits

  2024cites this paper
• Genomic and Proteomic Analyses of Extracellular Products Reveal Major Virulence Factors Likely Accounting for Differences in Pathogenicity to Bivalves between Vibrio mediterranei Strains

  2024influential citation
• The chromosome-scale genome assembly for the West Nile vector Culex quinquefasciatus uncovers patterns of genome evolution in mosquitoes

  2024cites this paper
• Genome sequencing and assembly of Indian golden silkmoth, Antheraea assamensis Helfer (Saturniidae, Lepidoptera).

  2024cites this paper
• Coinfection of Cage-Cultured Spotted Sea Bass (Lateolabrax maculatus) with Vibrio harveyi and Photobacterium damselae subsp. piscicida Associated with Skin Ulcer

  2024influential citation
• ViRAL: Vision Transformer Based Accelerator for ReAL Time Lineage Assignment of Viral Pathogens

  2024cites this paper
• Purines enrich root-associated Pseudomonas and improve wild soybean growth under salt stress

  2024cites this paper
• CONSULT-II: accurate taxonomic identification and profiling using locality-sensitive hashing

  2024cites this paper
• MCHelper automatically curates transposable element libraries across eukaryotic species

  2024cites this paper
• Complete genome sequences of three Porphyromonas gingivalis strains, isolated from patient with esophageal squamous cell carcinoma and healthy individual in China

  2024cites this paper
• BANG: Billion-Scale Approximate Nearest Neighbour Search Using a Single GPU

  2024cites this paper
• Locality Sensitive Hashing for Network Traffic Fingerprinting

  2023cites this paper
• Comparative Genomic Analysis of Warthog and Sus Scrofa Identifies Adaptive Genes Associated with African Swine Fever

  2023cites this paper
• Telomere-to-telomere assemblies of 142 strains characterize the genome structural landscape in Saccharomyces cerevisiae

  2023cites this paper
• Seeding with minimized subsequence

  2023cites this paper
• Integration of hybrid and self-correction method improves the quality of long-read sequencing data.

  2023cites this paper
• Comprehensive Assessment of Eleven de novo HiFi Assemblers on Complex Eukaryotic Genomes and Metagenomes

  2023cites this paper
• Exploration of whole genome amplification generated chimeric sequences in long-read sequencing data

  2023cites this paper
• Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases

  2023cites this paper
• Quorum Sensing Is Required for the Colony Establishment of a Plant Phyllosphere Bacterium Rhodopseudomonas palustris Strain GJ-22

  2023cites this paper
• Applications of long-read sequencing to Mendelian genetics

  2023cites this paper
• An Optimized Scaffolding Algorithm for Unbalanced Sequencing

  2023cites this paper
• xRead: a coverage-guided approach for scalable construction of read overlapping graph

  2023influential citation
• Identification and Phylogenetic Analysis of Mycobacterium avium subsp. avium Strain Isolated from Cow

  2023cites this paper
• A complete telomere-to-telomere assembly of the maize genome

  2023cites this paper
• Temporal transcriptomics provides insights into host‒pathogen interactions: a case study of Didymella pinodella and disease-resistant and disease-susceptible pea varieties

  2023cites this paper
• Large scale sequence alignment via efficient inference in generative models

  2023cites this paper
• Error analysis of the PacBio sequencing CCS reads

  2023cites this paper
• Chromosome-level assembly of Dictyophora rubrovolvata genome using third-generation DNA sequencing and Hi-C analysis

  2023influential citation
• Super-pangenome analyses highlight genomic diversity and structural variation across wild and cultivated tomato species

  2023cites this paper
• Proposal to classify Ralstonia solanacearum phylotype I strains as Ralstonia nicotianae sp. nov., and a genomic comparison between members of the genus Ralstonia

  2023cites this paper
• Content-based filter queries on DNA data storage systems

  2023cites this paper
• JASPER: A fast genome polishing tool that improves accuracy of genome assemblies

  2023cites this paper
• Genomics in the long-read sequencing era.

  2023cites this paper
• Comparing assembly strategies for third-generation sequencing technologies across different genomes.

  2023cites this paper
• Era of gapless plant genomes: innovations in sequencing and mapping technologies revolutionize genomics and breeding.

  2023cites this paper
• A practical comparison of the next-generation sequencing platform and assemblers using yeast genome

  2023cites this paper
• Large-Scale Chromosomal Changes Lead to Genome-Level Expression Alterations, Environmental Adaptation, and Speciation in the Gayal (Bos frontalis)

  2023cites this paper
• Guvermectin Biosynthesis Revealing the Key Role of a Phosphoribohydrolase and Structural Insight into the Active Glutamate of a Noncanonical Adenine Phosphoribosyltransferase.

  2023cites this paper
• Advances in sequencing technologies for amyotrophic lateral sclerosis research

  2023cites this paper
• Next-Generation Sequencing (NGS) and Third-Generation Sequencing (TGS) for the Diagnosis of Thalassemia

  2023cites this paper
• HyLight: Strain aware assembly of low coverage metagenomes

  2023cites this paper
• The complete genome sequence of Pseudomonas chengduensis BC1815 for genome mining of PET degrading enzymes.

  2023cites this paper
• Whole genome sequencing of multidrug-resistant Proteus mirabilis strain PM1162 recovered from a urinary tract infection in China.

  2023cites this paper
• Linear: a framework to enable existing software to resolve structural variants in long reads with flexible and efficient alignment-free statistical models

  2023cites this paper
• Comparative genomics reveals cellobiose hydrolysis mechanism of Ruminiclostridium thermocellum M3, a cellulosic saccharification bacterium

  2023cites this paper
• Morphological and genomic characteristics of two novel actinomycetes, Ornithinimicrobium sufpigmenti sp. nov. and Ornithinimicrobium faecis sp. nov. isolated from bat faeces (Rousettus leschenaultia and Taphozous perforates)

  2023cites this paper