Source-linked AI summary
Minimap and miniasm: fast mapping and de novo assembly for noisy long sequences
Heng Li
TL;DR
Long-read assembly pipelines traditionally include error correction, but correction is computationally intensive. This paper presents minimap and miniasm for mapping and assembling noisy reads without correction, achieving fast assembly while retaining comparable contiguity and large-scale accuracy in repeat-sparse genomes.
Problem
Long-read assembly pipelines require computationally intensive error-correction stages before assembly, motivating a faster correction-free approach.
Method
Minimap maps raw-read overlaps and miniasm performs the overlap-layout steps to directly assemble uncorrected reads, with PAF and GFA formats supporting modular interoperability.
Results
Miniasm produced a single contig per chromosome or plasmid for 13 of 17 bacterial data sets, with no observed large-scale misassemblies.
Takeaways & Limitations
Correction-free assembly can greatly accelerate and simplify long-read assembly while retaining comparable contiguity and large-scale accuracy for genomes without excessive repeats.
Takeaways & Limitations
Miniasm leaves unitig sequences with the raw-read error rate because it does not yet implement consensus generation, and its performance on repeat-rich genomes remains unknown.
Abstract
from arXiv · showhide
Motivation: Single Molecule Real-Time (SMRT) sequencing technology and Oxford Nanopore technologies (ONT) produce reads over 10kbp in length, which have enabled high-quality genome assembly at an affordable cost. However, at present, long reads have an error rate as high as 10-15%. Complex and computationally intensive pipelines are required to assemble such reads. Results: We present a new mapper, minimap, and a de novo assembler, miniasm, for efficiently mapping and assembling SMRT and ONT reads without an error correction stage. They can often assemble a sequencing run of bacterial data into a single contig in a few minutes, and assemble 45-fold C. elegans data in 9 minutes, orders of magnitude faster than the existing pipelines. We also introduce a pairwise read mapping format (PAF) and a graphical fragment assembly format (GFA), and demonstrate the interoperability between ours and current tools. Availability and implementation: https://github.com/lh3/minimap and https://github.com/lh3/miniasm Contact: hengli@broadinstitute.org
1 INTRODUCTION
Short reads struggle with repeats and segmental duplications, while noisy long reads enable improved assembly but traditionally require multistage processing. This paper proposes correction-free mapping and assembly alongside concise formats to support faster, more modular long-read pipelines.
- Short reads often cannot resolve repetitive sequences and segmental duplications longer than the reads, limiting de novo assembly contiguity and completeness.
- SMRT and ONT provide long reads that support high-quality bacterial assembly despite substantial per-base error rates.
- Existing long-read pipelines map raw reads, correct errors, assemble corrected reads, and polish contigs across four stages.
- Minimap maps raw-read overlaps and miniasm assembles directly from them, omitting sequencing-error correction and producing unpolished contigs.
- The paper proposes concise mapping and assembly formats to improve interoperability and encourage modular tool design.
2.1 General notations
This section defines DNA-sequence notation and introduces minimizers as the core reduced representation used by the mapping algorithms. It also specifies the minimizer-sketch algorithm’s inputs and outputs.
- DNA sequences use the nucleotide alphabet Σ = {A, C, G, T}, with reverse-complement and strand functions defined for sequence representation.
- Table 1 catalogs tools used in noisy long-read assembly pipelines.
- Algorithm 1 computes (w,k)-minimizers, their positions, and strands from a sequence s using parameters w and k.
- The minimizer procedure scans each window, selects the minimum hash value, skips strand-ambiguous cases, and collects minimizer records without duplicates.
- A k-mer is a DNA substring of length k, and Σ^k denotes the set of all k-mers.
2.2 Minimap
Minimap represents sequences with minimizers, indexes target minimizers, and maps queries by clustering approximately colinear minimizer hits. Its design combines sketching, hashing, and sorting to support efficient sequence mapping.
- Overview of k-mer based sequence similarity search: Minimap uses minimizers as a reduced sequence representation, unlike BLAST, BLAT, and DALIGNER’s k-mer matching strategies.It is also designed for read overlap, read-to-genome, and genome-to-genome mapping.
- Computing minimizers: A (w, k)-minimizer is the smallest k-mer in a window of w consecutive k-mers.Minimap uses k = 15 and w = 5 for read overlapping.
- Computing minimizers: The invertible hash function preserves distinct 2k-bit values for distinct k-mers and reduces oversampling of poly-A k-mers.The transformation also helps reduce hash collisions.
- Indexing: Minimap indexes target minimizers in a hash table keyed by hash, storing target sequence, position, and strand information.The implementation collects minimizers in an array and sorts them before constructing indexed intervals.
- Mapping: For each query minimizer, minimap collects matching target entries, encodes strand-specific coordinates, sorts hits, and clusters them by target and strand.Same-strand hits use i − i′, whereas opposite-strand hits use i + i′.
- Mapping: Minimap retains the maximal colinear subset of clustered hits as the final mapping result, using a longest increasing subsequence procedure.The default minimum subset size is 4, and approximately colinear hits are grouped within a 500bp band.
2.3 Assembly graph
The assembly graph represents reads as vertices and sequence overlaps as directed edges. Overlap edges encode the unaligned prefix length, while graph completeness requires complementary sequence relationships.
- Assembly graph: A suffix-prefix match between reads defines an overlap v →w and a directed graph edge between the reads.The edge length is the length of v’s prefix outside the suffix-prefix match.
- Assembly graph: A Watson-Crick-complete graph contains each read’s complement and the complementary reverse edge for every overlap.The definition imposes both vertex and edge complement conditions.
- Assembly graph: For mapped reads, sufficiently small overhangs imply reciprocal edges whose approximate lengths are computed from mapping coordinates.The figure gives ℓ(v →w) = b[1] −b[2] and the complementary edge length from right overhangs.
- Assembly graph: Collapsing bubbles is preferred for high contiguity in multi-ploidy samples or paralogs, but it introduces information loss.This is an explicit trade-off in graph simplification.
2.4 Miniasm
Miniasm preprocesses read mappings, builds and simplifies an overlap graph, and spells unitigs from graph paths. It omits sequencing-error correction, so unitig accuracy remains constrained by raw-read errors.
- Mapping preprocessing: Miniasm estimates per-base coverage from good read mappings, retains the longest region with coverage at least 3, and trims bases outside it.Good mappings require reads longer than 2000bp and at least 100bp of non-redundant matching-minimizer bases.
- Graph construction: It classifies trimmed mappings, ignores internal matches, drops contained reads, and adds overlaps to the assembly graph.For each read pair, miniasm keeps only the longest overlap to avoid multi-edges.
- Graph simplification: Graph simplification removes transitive edges, trims tipping unitigs composed of few reads, and pops small bubbles.Bubble detection uses a maximum path length of 50kb by default and can backtrack to collapse a bubble to one path.
- Graph simplification: Miniasm removes some shorter overlaps after transitive reduction when their ratio is small, reducing repeat-derived alternatives but risking missing overlaps and misassemblies.The default ratio threshold is 70%.
- Generating unitig sequences: A unitig is a maximal path whose adjacent vertices can be unambiguously merged without changing the original graph’s connectivity.Its sequence is obtained by concatenating vertex substrings along the path.
- Generating unitig sequences: Without error correction, miniasm’s unitig sequences retain the raw input reads’ error rate.The paper notes that a consensus tool could improve unitig sequences but was not implemented.
2.5 Formats: PAF and GFA
PAF provides a lightweight mapping interchange, while GFA concisely represents assembly graphs across pipeline stages. GFA differs from FASTG in terminology and avoids its nesting-related representational complications.
- 2.5.1 Pairing mapping format (PAF): PAF stores key mapping information and connects minimap output directly to miniasm input.Scripts also convert DALIGNER, MHAP, and SAM mappings to PAF.
- 2.5.2 Graphical fragment assembly format (GFA): GFA represents assembly graphs with S lines for vertices and L lines for edges, including their complements.It can encode stages from initial read overlaps through final unitig relationships.
- 2.5.2 Graphical fragment assembly format (GFA): GFA was proposed by the authors and later improved by the community.The format is described as concise and linked to an assembly-graph representation.
- 2.5.2 Graphical fragment assembly format (GFA): Bubble detection starts only at vertices with at least two outgoing edges and searches within a specified maximum probe distance.The algorithm returns a sink vertex or nil when it encounters a circle or exceeds the distance limit.
- 2.5.2 Graphical fragment assembly format (GFA): The bubble detector tracks minimum distances and unvisited incoming edges while traversing the graph in topological order.A sink is returned when the search identifies a single remaining path condition.
- 2.5.2 Graphical fragment assembly format (GFA): FASTG uses different names for graph vertices and edges and permits nested subgraphs.The paper identifies nesting as a limitation because tools do not support nested graphs and one graph can have distinct representations.
2.6 Evaluating the layout accuracy
Miniasm evaluates layout accuracy by checking whether read adjacencies in the assembly agree with their order on the true assembly, using a window of five reads.
- Miniasm maps trimmed reads to the true assembly and selects the best mapping for each read.
- An adjacency is w-consistent when reads share a unitig and lie within w positions, or both lie near unitig ends.The evaluation uses w = 5.
- The method uses w = 5 to detect large structural misassemblies.
3 RESULTS
The results assess minimap’s mapping accuracy, miniasm’s bacterial and C. elegans assemblies, runtime, interoperability, and resource requirements. Minimap is fast and accurate, while miniasm produces rapid assemblies but leaves raw-read errors uncorrected and can encounter memory limits.
- 3.1 The accuracy of minimap: Minimap is 50 times faster than BWA-MEM while finding similar best mapping positions on a human PacBio run.Only 0.7% of reads excluding decoy hits failed to overlap the best minimap mapping.
- 3.1 The accuracy of minimap: Minimap finds 93% of tested read overlaps, compared with 78% for sensitive MHAP and 98% for DALIGNER.
- 3.2 Assembling bacterial genomes: Miniasm derives a single contig per chromosome or plasmid for all but four of 17 bacterial data sets, with no observed large-scale misassemblies.Its layouts are 5-consistent with reference assemblies except for ERS473430, where the NCTC assembly may be erroneous.
- 3.2 Assembling bacterial genomes: 14 seconds and 2 minutes are miniasm’s assembly times for 30-fold PBcR-PB-ec and 160-fold PB-ecoli data, while PBcR is about 700 and 60 times slower, respectively.The comparison excludes miniasm’s error-correction stage because miniasm has none.
- 3.3 Assembling a C. elegans genome: 9 minutes is miniasm’s assembly time for 45-fold C. elegans data, yielding N50 = 2.8Mb; HGAP3 yields N50 = 1.6Mb without visible large-scale misassemblies.Miniasm’s dotter plot shows three structural misassemblies.
- 3.3 Assembling a C. elegans genome: Minimap peaks at 27GB RAM on the C. elegans data set, while miniasm uses 1.3GB but may become memory-limited on larger data sets.
4 DISCUSSIONS
Miniasm accelerates long-read assembly by omitting error correction and implementing only the overlap and layout stages, while retaining comparable contiguity and large-scale accuracy in repeat-sparse genomes. Its main boundaries are missing consensus generation and uncertain scalability to repeat-rich, complex genomes.
- Assembly approach: Miniasm omits error correction and implements the overlap and layout stages of the OLC assembly paradigm.This directly produces unpolished, uncorrected contigs rather than consensus-polished sequences.
- Assembly approach: Comparable contiguity and large-scale accuracy are achieved for genomes without excessive repetitive sequences.
- Limitations and opportunities: Without the consensus step, miniasm cannot produce high-quality consensus for many analyses.A fast consensus tool matching minimap and miniasm remains an open need.
- Limitations and opportunities: Repeat-rich genomes remain an unresolved boundary because low-identity matches can reflect either sequencing errors or recent segmental duplications.The evaluated bacterial and C. elegans genomes are repeat sparse, and miniasm has not been optimized for large repeat-rich genomes.
- Limitations and opportunities: Future long-read tooling would benefit from standardized input and output formats that support modular components developed by different groups.The paper introduces concise mapping and assembly formats to encourage this interoperability.