How lh3/minimap2 works
1. This repository is the source tree for Minimap2, a C-based sequence aligner and mapper. The core product is both a command-line tool (minimap2) and a reusable alignment library exposed through minimap.h.
2. The highest-level runtime flow is: read reference sequences or a prebuilt index, build/load a minimizer index, stream query sequences, find seed matches, chain them into candidate mappings, optionally perform base-level alignment, and emit PAF or SAM output. The README’s algorithm steps map directly onto the codebase’s main stages.
3. The code is split into a small set of core alignment subsystems:
- indexing and seeding (index.c, seed.c, sketch.c, splitidx.c)
- chaining and mapping (chain logic spread across lchain.c, map.c, main.c)
- base-level alignment and scoring (align.c, ksw2*, esterr.c, sdust.c)
- output formatting and record handling (format.c, hit.c, bseq.c)
- option parsing and execution control (options.c, main.c)
4. main.c is the CLI orchestrator. It owns the top-level control loop, parses options, loads reference/index data, dispatches query processing, and coordinates which subsystems run depending on presets such as map-ont, splice, sr, ava-pb, or asm5.
5. minimap.h is the public API boundary for library use. External C callers can build/load an index and run alignments without going through the CLI. mmpriv.h contains internal/private structures and functions that are not intended to be stable.
6. Sequence I/O is handled by a dedicated layer centered on bseq.c/bseq.h and the bundled sequence readers (kseq.h, krmq.h). This layer isolates FASTA/FASTQ parsing, gzip-aware input handling, and batched query streaming from the alignment logic.
7. The low-level performance core relies on a collection of reusable utility headers and SIMD-aware code:
- memory and allocation (kalloc.c, kalloc.h)
- dynamic arrays/heaps/sorting/hash utilities (kvec.h, kdq.h, khash.h, ksort.h)
- threading (kthread.c, kthread.h)
- pairwise sequence alignment kernels (ksw2.h, ksw2_dispatch.c, ksw2_*_sse.c)
- ARM compatibility via sse2neon/ and optional SIMDe support via Makefile.simde
This is where most architecture-specific performance behavior lives.
8. The alignment pipeline includes repeat/low-complexity filtering and error-aware heuristics before final extension. Files such as sdust.c/sdust.h, esterr.c, misc.c, jump.c, and align.c support the accuracy-focused parts of the mapper, especially for noisy long reads and spliced RNA alignment.
9. The repository supports multiple mapping modes, but they all share the same pipeline with different presets and scoring rules. The distinct use cases in the README are not separate products; they are configuration profiles layered over the same seeding/chaining/alignment engine.
10. Output is intentionally dual-format: approximate or detailed mappings can be emitted as PAF, SAM, or index files. The -a, -c, and -d modes correspond to different boundaries in the pipeline: final alignment output, CIGAR-rich alignment output, and serialized reference index output.
11. Python support is a separate binding layer rather than a second implementation. The python/ directory contains the Cython-based mappy extension (mappy.pyx, cmappy.*, minimap2.py) that wraps a subset of the C API for embedding Minimap2 in Python applications and packaging it on PyPI/BioConda.
12. Utility and post-processing tooling lives outside the core aligner. misc/paftools.js and misc/pafcluster.js operate on PAF output for downstream conversion, evaluation, liftover, and variant/summary workflows. This is an auxiliary analysis layer, not part of the alignment engine.
13. Testing and validation are lightweight but data-backed. The test/ directory contains small reference/query fixtures and expected alignments, while tex/ holds evaluation material and benchmark-related documentation. The GitHub Actions workflow (.github/workflows/ci.yaml) drives automated build and regression checks.
14. Packaging and distribution are first-class concerns. setup.py, pyproject.toml, MANIFEST.in, and the release/docs references in the README show that the repo targets both native builds from source and packaged Python distribution, while the Makefile family is the primary native build entry point.
15. In diagram terms, the key boundaries are: input parsing, reference indexing, query seeding/chaining, base-level alignment, output formatting, and optional wrappers/tooling. The main internal dependency direction is from high-level orchestration in main.c down into reusable alignment kernels and utility libraries, with Python/JS tooling consuming the same core outputs rather than bypassing them.
Main entry points: main.c CLI · align.c Alignment · index.c Indexing · format.c Output
Components 27
Core aligner
Main indexing, mapping, alignment, and CLI orchestration pipeline.
- CLI · Top-level command-line control flow and preset-driven execution.
main.c - Options · Command-line option parsing and preset configuration.
options.c - Indexing · Builds and loads minimizer indexes from reference sequences.
index.c - Seeding · Seed generation and lookup logic for query/reference matches.
seed.c - Split index · Handles split/reference index layouts and serialized index boundaries.
splitidx.c - Chaining · Clusters seed hits into candidate mapping chains.
lchain.c - Mapping · Coordinates mapping decisions and chaining-to-alignment flow.
map.c - Alignment · Base-level alignment, scoring, and extension heuristics.
align.c - Output · Formats alignments into PAF, SAM, and index outputs.
format.c - Hits · Core hit and alignment record structures used across the pipeline.
hit.c - Dust filter · Low-complexity masking and repeat filtering heuristics.
sdust.c - Error model · Error-rate estimation and alignment heuristics.
esterr.c - Aux heuristics · Miscellaneous alignment helpers and jump/trace utilities.
misc.c - Public API · Stable library boundary for embedding the aligner in C code.
minimap.h - Private API · Internal structures and non-stable implementation details.
mmpriv.h
Runtime support
Sequence I/O, threading, memory, and SIMD utility layers used by the core.
- Sequence I/O · FASTA/FASTQ parsing and batched query streaming.
bseq.c - DP kernels · Pairwise alignment kernels and SIMD dispatch layer.
ksw2_dispatch.c - Threads · Threading primitives and work scheduling support.
kthread.c - Allocator · Memory allocation helpers used by performance-critical code.
kalloc.c - Core utils · Reusable vector, queue, hash, and sort utilities.
kvec.h
Bindings
Python packaging and Cython wrapper around the C API.
- Python binding · Cython-based Python extension and packaging glue.
python/mappy.pyx
Tooling
Auxiliary analysis scripts and distribution/build entry points.
- PAF tools · JavaScript utilities for downstream PAF analysis and conversion.
misc/paftools.js - PAF cluster · Clustering and summary tool for PAF-based workflows.
misc/pafcluster.js - Build files · Makefile and packaging entry points for native and Python distribution.
Makefile
Validation
Fixtures, benchmarks, and CI checks.
- CI · Automated build and regression checks.
.github/workflows/ci.yaml - Fixtures · Small reference, query, and expected alignment fixtures.
test/x3s-ref.fa - Benchmarks · Evaluation and benchmarking materials for mapping accuracy.
tex/minimap2.tex
Connections 29
- CLI → Options: parse · CLI reads options and presets before execution.
- CLI → Indexing: load/build · Main orchestrator builds or loads the reference index.
- CLI → Sequence I/O: stream queries · Main orchestrator consumes batched sequence input.
- CLI → Mapping: dispatch · Top-level control passes work into the mapping pipeline.
- Mapping → Seeding: seed · Mapping starts by finding minimizer hits.
- Seeding → Chaining: chain · Seed matches are chained into candidate mappings.
- Chaining → Alignment: extend · Candidate chains are optionally extended into base-level alignments.
- Alignment → Output: emit · Final alignments are prepared for output formatting.
- Indexing → Seeding: index data · Index structures feed seeding and lookup.
- Split index → Indexing: layout · Split-index support shapes how reference data is organized.
- Sequence I/O → Hits: records · Sequence batching produces query records used throughout mapping.
- Mapping → Hits: track · Mapping updates and reuses hit/alignment records.
- Dust filter → Alignment: filter · Low-complexity masking influences extension and scoring.
- Error model → Alignment: score · Error-aware heuristics tune alignment decisions.
- Aux heuristics → Alignment: helpers · Auxiliary heuristics support extension and traceback behavior.
- DP kernels → Alignment: kernel · SIMD pairwise alignment kernels implement the DP core.
- Threads → CLI: parallelize · Threading support enables concurrent mapping work.
- Allocator → Indexing: alloc · Allocator support underpins memory-heavy index structures.
- Core utils → Indexing: containers · Generic containers and hashing support indexing and chaining data structures.
- Core utils → Chaining: containers · Chaining uses shared vector, queue, hash, and sort utilities.
- Public API → Python binding: wrap · Python extension wraps the public C API.
- Public API → CLI: shared engine · CLI and library share the same core alignment engine.
- Private API → CLI: internal state · Private structures are used internally by the orchestrator and subsystems.
- PAF tools → Output: consume · PAF tooling operates on mapper output.
- PAF cluster → Output: consume · Clustering tool consumes PAF output.
- Build files → Python binding: package · Build and packaging files support the Python binding.
- CI → Build files: validate · CI runs build and regression checks.
- Fixtures → CLI: regress · Fixtures exercise the mapper end-to-end.
- Benchmarks → Output: evaluate · Benchmark material compares mapper output and accuracy.