PaperlayerView exact revision on arXiv

Source-linked AI summary

Minimap2: pairwise alignment for nucleotide sequences

Heng Li

arXiv:1708.01492v5q-bio.GN

TL;DR

Existing aligners struggle to process long, noisy genomic and RNA-seq reads efficiently at scale. Minimap2 provides a versatile nucleotide-sequence mapper and pairwise aligner, often outperforming specialized tools in speed and accuracy across alignment tasks.

  • Problem

    Existing aligners are slow or inefficient for long, noisy genomic and spliced RNA-seq reads, limiting alignment of emerging sequencing data at scale.

  • Method

    Minimap2 uses efficient hash-table seeding, chaining heuristics, and alignment strategies to map short, long noisy, spliced, and assembled nucleotide sequences.

  • Results

    Minimap2 often achieves higher accuracy while outperforming other alignment tools in speed across long genomic, spliced RNA, and related alignment tasks.

  • Takeaways & Limitations

    Minimap2 is a versatile, efficient option for mapping short reads, long noisy genomic and RNA-seq reads, assembly contigs, and whole genomes.

  • Takeaways & Limitations

    Local misalignment from misplaced anchors remains a limitation that the authors identify for future improvement.

Abstract

from arXiv · show

Motivation: Recent advances in sequencing technologies promise ultra-long reads of $\sim$100 kilo bases (kb) in average, full-length mRNA or cDNA reads in high throughput and genomic contigs over 100 mega bases (Mb) in length. Existing alignment programs are unable or inefficient to process such data at scale, which presses for the development of new alignment algorithms. Results: Minimap2 is a general-purpose alignment program to map DNA or long mRNA sequences against a large reference database. It works with accurate short reads of $\ge$100bp in length, $\ge$1kb genomic reads at error rate $\sim$15%, full-length noisy Direct RNA or cDNA reads, and assembly contigs or closely related full chromosomes of hundreds of megabases in length. Minimap2 does split-read alignment, employs concave gap cost for long insertions and deletions (INDELs) and introduces new heuristics to reduce spurious alignments. It is 3-4 times faster than mainstream short-read mappers at comparable accuracy and $\ge$30 times faster at higher accuracy for both genomic and mRNA reads, surpassing most aligners specialized in one type of alignment. Availability and implementation: https://github.com/lh3/minimap2 Contact: hengli@broadinstitute.org

Motivation: · 1 INTRODUCTION

Long-read SMRT and ONT sequencing creates a need for faster alignment because reads exceed 10kbp at ∼15% error rates, while existing aligners can be substantially slower. Minimap2 addresses genomic and mRNA alignment with a common base algorithm and is evaluated across simulated and real datasets for performance, accuracy, and versatility.

  • Motivation:: 10kbp-plus SMRT and ONT reads arrive at an error rate of ∼15%, motivating alignment methods designed for noisy long-read data.The passage identifies both sequencing technologies and their characteristic read length and error rate.
  • Motivation:: Five times slower than mainstream short-read aligners, most existing long-read aligners were inefficient in mapped bases per second.This comparison is reported specifically for the number of bases mapped per second.
  • 1 INTRODUCTION: Traditional mRNA aligners can process spliced mRNAs but are not optimized for long noisy reads.Both SMRT and ONT have been applied to RNA-seq, creating a need for specialized long-read handling.
  • 1 INTRODUCTION: Tens of times slower than dedicated long-read aligners, traditional mRNA aligners are inefficient for long noisy sequence reads.The passage contrasts traditional mRNA aligners with dedicated long-read aligners.
  • 1 INTRODUCTION: Minor modifications to the genomic-DNA base algorithm enable minimap2 to map mRNAs as well.The development began with genomic DNA alignment and extended the same base algorithm to mRNA mapping.
  • 1 INTRODUCTION: Minimap2 is described through its algorithm and applications to different input-sequence types, with performance and accuracy evaluated on simulated and real datasets.The article also aims to demonstrate minimap2’s versatility.

2 METHODS

Minimap2 uses a minimizer-based seed–chain–align procedure, indexing reference minimizers to identify query anchors and colinear chains. It extends minimap with more accurate chaining, base-level alignment, and spliced-alignment support.

  • Seed, chain, and align: Minimap2 indexes reference minimizers in a hash table, then uses query minimizers as seeds to find exact anchors and colinear anchor chains.The hash table maps each minimizer hash to the locations of its copies.
  • Method extensions: Minimap2 builds on minimap’s indexing and seeding algorithms with more accurate chaining, base-level alignment, and spliced-alignment support.These additions extend the predecessor’s capabilities for nucleotide-sequence alignment.

2.1 Chaining

Minimap2 chains anchors with dynamic programming using a generic gap cost, then accelerates chaining with a heuristic that usually preserves the optimal chain. It identifies nonoverlapping primary chains and estimates their mapping quality from chain strength and competing secondary chains.

  • Anchor chaining: 0.01 · w̄ · |l| + 0.5 log2 |l| is the implemented cost for a nonzero gap of length l, while zero-length gaps cost 0.Here, w̄ is the average seed length.
  • Anchor chaining: O(N^2) direct chaining is accelerated to O(hN) by stopping predecessor evaluation after h iterations without improvement.The heuristic almost always finds the optimal chain with h = 50; when it fails, the resulting chain is often close to optimal.
  • Primary chains: 50% or higher overlap of the shorter query chain marks a lower-scoring chain as secondary; otherwise, it is retained as a primary chain.Chains are processed from best to worst by chaining score, and the procedure is not the performance bottleneck.
  • Mapping quality: Mapping quality increases for longer primary chains and weaker best secondary chains, using the primary chain’s anchor count and competing chaining scores.The empirical formula uses m, the number of anchors on the primary chain, f1, its chaining score, and f2, the best secondary-chain score.

2.2 Aligning genomic DNA

Minimap2 aligns genomic DNA between adjacent anchors with dynamic programming, using a two-piece affine gap cost to recover long INDELs and SIMD-optimized heuristics to improve speed and robustness. Its alignment safeguards detect artifacts between anchors, recover short inversions, and filter anchors likely to induce erroneous gaps.

  • Alignment model: Minimap2 performs dynamic-programming global alignment between adjacent anchors with a two-piece affine gap cost.The scoring scheme applies one affine cost to shorter gaps and another to longer gaps.
  • Alignment model: Longer gaps use the lower-extension-cost component when e > ˜e, helping recover longer insertions and deletions.The switch occurs at gap length ⌈(˜q − q)/(e − ˜e)⌉.
  • SSE acceleration: 16-way SSE vectorization is enabled by bounded 8-bit state values, regardless of the alignment’s peak score.The bounds are valid when −128 ≤ −q − e < M + q + e ≤ 127.
  • SSE acceleration: 3 times as fast as Parasail’s 4-way vectorization, minimap2’s 16-way global-alignment implementation becomes considerably faster than Edlib with a 1000bp band.Without banding, the implementation is slower than Edlib; banding is usually applicable between anchors because alignments are expected to stay near the diagonal.
  • Alignment safeguards: Minimap2 breaks global alignments when the accumulative score drops too quickly, then reverse-complements the involved subsequence for local alignment to identify short inversions.The score-drop rule avoids forcing alignment across unrelated sequences and does not break in the presence of a single long gap.
  • Alignment safeguards: >10bp insertion and >10bp deletion simultaneously trigger anchor filtering, while terminal anchors causing long end gaps are also removed.These heuristics greatly alleviate artifacts from misplaced anchors but cannot fix all such errors.

2.3 Aligning spliced sequences

Minimap2 adapts chaining and dynamic-programming gap costs for spliced alignment, explicitly modeling introns and splice-site signals. It also handles unknown RNA-read strand by testing both orientations, at a cost of several-fold slower alignment than genomic DNA mode.

  • Spliced alignment: Minimap2 distinguishes reference insertions from deletions by modifying chaining and dynamic-programming gap costs for spliced alignment.These changes adapt the alignment algorithm to spliced sequences.
  • Spliced alignment: Deletions no shorter than ⌈(q̃−q)/e⌉ are treated as introns and incur no gap-extension cost.The intron criterion applies during alignment.
  • Splice-site scoring: Reference-dependent penalties distinguish canonical and less frequent splice signals to pinpoint precise splicing junctions.Non-canonical donor sites receive p, while GT[C/T] signals receive p/2; analogous penalties model acceptor signals.
  • Strand handling: For unstranded RNA-seq reads, minimap2 aligns each chain under GT–AG and CT–AC assumptions and retains the higher-scoring alignment.This procedure also infers the relative strand for reads spanning canonical splicing sites.
  • Performance: Several times slower than genomic DNA alignment, spliced mode uses denser minimizers, disables banded alignment, and performs two-round DP-based alignment.The slowdown results from the combined spliced-alignment settings.

2.4 Aligning short paired-end reads

Minimap2 aligns short paired-end reads by treating each read pair as a single fragment during chaining, using different gap penalties for within-read and between-read seeds. It then splits primary fragment chains, aligns each read separately, and pairs consistent read-end hits.

  • Chaining: Minimap2 treats a paired-end read pair as one fragment with an unknown middle gap during chaining.It uses a normal gap cost between seeds on the same read and a more permissive cost between seeds on different reads.
  • Chaining: For same-read seeds, the gap cost is 0.01 · ¯w · |l| + 0.5 log2 |l|, while different-read seeds use min{0.01 · ¯w · |l|, log2 |l|}.The stated formula applies when l̸ = 0.
  • Read alignment: After identifying primary chains, minimap2 splits each fragment chain into two read chains and aligns each read separately.Each read is aligned as described in Section 2.2.
  • Read alignment: Finally, minimap2 pairs hits from the two read ends to identify consistent paired-end alignments.This pairing occurs after separate alignment of the two read chains.

3 RESULTS

Minimap2 achieved high accuracy and substantial speed advantages across noisy genomic, spliced RNA, short-read, and assembly-alignment benchmarks. Its assembly-based variant calls also showed higher precision than the compared MUMmer4 pipeline.

  • Long-read genomic alignment: 200 CPU seconds and over 30 times faster than the rest, minimap2 retained higher overall mapping accuracy on simulated long reads.It used 6.8GB peak memory, compared with 5.4GB for BWA-MEM.
  • Long-read genomic alignment: Over 70 times faster than other aligners on ∼100kb human ONT reads, minimap2 remained competitive with similar mapped-read fractions on real human SMRT data.BWA-MEM failed on the ONT dataset.
  • Spliced alignment: Over 40 times faster than GMAP and SpAln, minimap2 found more mouse cDNA junctions with higher exact or approximate correctness; STAR was close in speed but handled noisy reads poorly.
  • Spliced alignment: 10 million human Direct RNA-seq reads were aligned in <1 wall-clock hour using 16 CPU cores, with 94.2% of splice junctions consistent with gene annotations.GMAP was 160 times slower, and 68.7% of its junctions were found in known gene annotations.
  • Short-read alignment: 3–4 times as fast as Bowtie2 and BWA-MEM, minimap2 was more accurate than Bowtie2 and SNAP but less accurate than BWA-MEM on simulated short reads.It was 1.3 times slower than SNAP.
  • Assembly alignment: 7 minutes using 8 CPU cores, minimap2 aligned a SMRT assembly against GRCh38 over 20 times faster than nucmer and produced a callset with higher precision than MUMmer4’s dnadiff.Its ts/tv was 2.01 versus 1.87 for dnadiff, and it called 201 Y-chromosome substitutions versus 9070 for dnadiff.

4 DISCUSSIONS

Minimap2 is a versatile nucleotide mapper and aligner that supports diverse read, contig, overlap, and whole-genome alignment tasks while often outperforming domain-specific tools in speed and accuracy. Its performance derives from fast base-level alignment and chaining algorithms, alongside efficient fixed-length k-mer indexing.

  • Versatility and performance: Minimap2 supports short reads, assembly contigs, long noisy genomic and RNA-seq reads, read mapping, long-read overlapping, and full-genome alignment.It is described as accurate and efficient, often outperforming domain-specific alignment tools in both speed and accuracy.
  • Core algorithms: Minimap2 combines a fast base-level alignment algorithm with an accurate chaining algorithm to support efficient long-query alignment.The Suzuki-Kasahara algorithm alleviates the base-level alignment bottleneck and enables DP-based splice alignment involving >100kb introns.
  • Reference indexing: Minimap2 uses a hash table for fixed-length reference k-mers, which are theoretically inferior to variable-length seeds but computable much more efficiently in practice.Full-text indexes support exact seeds of arbitrary lengths, helping increase seed uniqueness and reduce unsuccessful extensions.
Loading 1708.01492v5…