Source-linked AI summary
Protein-to-genome alignment with miniprot
Heng Li
TL;DR
Protein-to-genome alignment is important for annotating new genomes, but existing tools are inefficient and difficult to scale. Miniprot combines k-mer-based seed-and-chain mapping with dynamic programming for intron-aware protein-to-genome alignment. It is over 30 times faster than Spaln2 and GeMoMa while achieving comparable accuracy to existing tools, though it does not replace full gene-annotation pipelines.
Problem
Protein-to-genome alignment is needed for gene annotation, but existing whole-genome-capable tools are inefficient and difficult to scale to growing genome and protein datasets.
Method
Miniprot uses a seed-chain-extend strategy with genome k-mer indexing, anchor chaining, and dynamic programming across unaligned regions and introns.
Results
Over 30 times faster than Spaln2 and GeMoMa, miniprot achieves accuracy comparable to existing tools on real data.
Takeaways & Limitations
Miniprot can combine approximate protein mapping and exact splice alignment in one step, simplifying existing annotation pipelines.
Takeaways & Limitations
Miniprot aligns proteins independently and cannot merge identical gene models or resolve conflicts between overlapping alignments.
Abstract
from arXiv · showhide
Motivation: Protein-to-genome alignment is critical to annotating genes in non-model organisms. While there are a few tools for this purpose, all of them were developed over ten years ago and did not incorporate the latest advances in alignment algorithms. They are inefficient and could not keep up with the rapid production of new genomes and quickly growing protein databases. Results: Here we describe miniprot, a new aligner for mapping protein sequences to a complete genome. Miniprot integrates recent techniques such as k-mer sketch and SIMD-based dynamic programming. It is tens of times faster than existing tools while achieving comparable accuracy on real data. Availability and implementation: https://github.com/lh3/miniprot
1 INTRODUCTION
Protein-to-genome alignment supports gene annotation when other strategies are inaccurate, costly, or limited by evolutionary divergence. Miniprot is introduced as a new aligner designed to improve this step.
- RNA-seq can improve gene-structure accuracy, but it adds cost and may miss lowly expressed genes.
- Cross-species genome alignment becomes less reliable with evolutionary distance because intron and coding sequences are less conserved.
- Several established tools produce spliced protein-to-genome alignments with exact splice sites.
- Only Spaln2, GenomeThreader, and GeMoMa are practical for whole-genome alignment, yet they may require days for hundreds of thousands of proteins.
- Fast and accurate alignment is difficult because the dynamic program jointly models affine gaps, introns, frameshifts, and splice signals.
- Miniprot is a new protein-to-genome aligner evaluated for performance and accuracy against existing algorithms on real data.
2 METHODS
Miniprot follows a seed-chain-extend workflow to map proteins against genome sequences. It uses k-mer anchors, chaining, gap closure, terminal extension, and dynamic programming.
- Miniprot indexes genome k-mers in all six reading frames on both strands.
- During alignment, protein k-mers generate seed anchors that are chained before unaligned regions are closed and terminal anchors extended with dynamic programming.
- The genome is represented as nucleotide sequence T, while the query is represented as amino-acid sequence P.
2.2 Reduced alphabet
Miniprot compresses protein sequences by replacing the 20-amino-acid alphabet with grouped integer codes. A possible low-bit perturbation can increase seeding sensitivity, but is not used.
- Miniprot reduces the amino-acid alphabet using SE-B(14), merging N and D into one group.
- The reduced alphabet maps amino-acid groups to compact integer codes, including separate codes for stop codons and unknown amino acids.
- Flipping the lowest bit of encoded groups could generate additional seeds, but miniprot omits this strategy because real-data sensitivity appears sufficient.
2.3 Indexing the genome
Miniprot indexes only a hashed subset of genome k-mers to reduce indexing work and storage. It bins positions while retaining strand-specific translated ORF information.
- Miniprot hashes encoded k-mers and indexes only those whose hash lowest bit is 0, sampling about 50% of k-mers on average.
- The index treats each strand independently, enumerates ORFs at least 30 amino acids long, and samples 6-mers from translated ORFs.
- Genome positions are stored as 256-base bins rather than at base resolution, enabling 32-bit position storage for large genomes.
2.4 Chaining
Miniprot chains protein–genome seed anchors using a modified minimap2-like algorithm that accounts for binned genomic positions and intron-scale gaps.
- Miniprot modifies minimap2-like chaining because its index stores binned rather than exact genome positions.The algorithm therefore adjusts gap-size calculation between anchors.
- Anchors are seed matches between genomic and protein positions, ordered by both coordinates before chaining.Each anchor is represented as a 2-tuple of genomic and protein positions.
- Gap size is inferred from coordinate differences, with zero indicating uncertainty from binning and positive or negative values indicating insertions or deletions.The coordinate differences are Δx = x_j − x_i and Δy = y_j − y_i.
- Chaining scores combine prior chain scores, matching residues, and a gap penalty based on the inferred gap.The default k-mer length is 6 amino acids, and α(i,j) counts matching residues between anchors up to that length.
- The logarithmic gap penalty allows chains to join exons across introns up to a default maximum size of 200 kb.The default logarithmic weight is β = 0.75.
2.5 Residue alignment with dynamic programming
Miniprot uses dynamic programming to align proteins to translated genomic sequence while jointly handling affine gaps, frameshifts, introns, and splice phases.
- Dynamic programming closes gaps between chains and extends alignments from terminal anchors while finding frameshifts and splicing.The alignment represents genome, translated protein, and query protein sequences together.
- 2.5.1 DP with affine gap cost: Affine gap costs assign a gap of length g the cost q+e·g, using match, insertion, and deletion states.The AE86 formulation reduces comparisons and can simplify extensions with additional states.
- 2.5.2 DP for protein-to-DNA alignment: Protein-to-DNA alignment adds codon-aware transitions so frameshifts can be modeled without splicing.The four additional transitions represent insertion or deletion of one or two DNA bases within codons.
- 2.5.3 DP for protein-to-genome alignment: Three additional states represent phase-0, phase-1, and phase-2 introns, enabling intron-phase tracking during alignment.The model incorporates splice-signal scores into transitions through these intron states.
- 2.5.3 DP for protein-to-genome alignment: Non-GT-AG introns remain possible but receive a penalty under the simple splice-signal model.GT-AG introns receive the preferred signal treatment.
- 2.5.3 DP for protein-to-genome alignment: The DP omits scoring split codons bridging exons around phase-1 and phase-2 introns, which the authors identify as a weakness.This limitation arises from how transitions enter and leave the phase-specific intron states.
- The formulation is similar to the Viterbi decoding used by GeneWise and Exonerate and should have comparable accuracy under matched parameterization.The implementation uses striped DP with 16-bit integers and 8-way SIMD parallelization.
- Over 50 times faster than GeneWise and Exonerate in exact mode.The implementation targets x86 CPUs with SSE2 and ARM64 CPUs with NEON.
2.6 Splice models
Miniprot uses splice models centered on canonical splice signals, with additional sequence-context features and a deliberately simple parameterization for broader applicability.
- Under distant homology, the splice model can strongly influence junction accuracy.This observation is consistent with prior findings cited by the authors.
- GT-AG is the dominant splice pattern, while GC-AG and AT-AC occur at approximately 1% frequency in total.GT denotes the donor site and AG the acceptor site.
- The default model scores donor and acceptor sequence alternatives, assigning the strongest preference to common GT and AG signals.Human data estimated 99.81% of acceptor sites as AG and 0.10% as AC.
- The human splice model also incorporates a G adjacent to donor sites and poly-pyrimidine sequence near acceptor sites.The authors report applicability to species with these features, including Drosophila.
- Miniprot uses fewer splice-model parameters than Exonerate and omits branching-site modeling used by Spaln2.The simpler model is intended to be more general but may reduce alignment accuracy.
2.7 Avoiding pseudogenes
Miniprot reduces pseudogene interference by rescoring alignments against intron-free translated coding regions and penalizing single-exon matches.
- Miniprot recalculates scores against translated coding regions without introns because unspliced pseudogenes can otherwise avoid intron penalties.It additionally penalizes single-exon alignments by the intron-open score.
3 RESULTS
Miniprot was evaluated against existing protein-to-genome aligners on multiple cross-species datasets, with accuracy, sensitivity, specificity, and runtime compared. It was generally accurate and substantially faster, while competing tools showed different sensitivity and splice-junction trade-offs.
- Evaluation design: Miniprot was evaluated using protein-to-genome alignments compared with annotated genes across several species and cross-species datasets.The evaluation included human, mouse, zebrafish, fruit fly, and mosquito annotations, with metrics including junction and base-level accuracy.
- Evaluated tools: Only miniprot, Spaln2, GeMoMa, and GenomeThreader completed a sampled whole-genome zebrafish alignment within one hour.GenomeThreader found less than 30% of coding regions identified in Spaln2 or miniprot alignments and was not evaluated on the full data.
- Accuracy comparison: Miniprot was slightly more accurate than Spaln2 on most metrics for zebrafish-to-human alignment, whereas Spaln2 found more correct junctions among proteins mapped by both.Spaln2 was more sensitive to small introns and exons, while miniprot sometimes merged them with adjacent alignments; Spaln2 also produced more false junctions in these cases.
- Accuracy comparison: GeMoMa had the highest sensitivity and found more junctions and annotated coding regions, but its junction accuracy was lower than that of miniprot and Spaln2.The authors retained miniprot’s current behavior because additional alignments obtained by increasing sensitivity were less accurate.
- Cross-species comparisons: On human-mouse data miniprot was again slightly better than Spaln2, while on fly-mosquito data Spaln2 had higher junction sensitivity and base specificity.GeMoMa crashed on human-mouse and retained the highest sensitivity but lower junction accuracy and base specificity on fly-mosquito.
- Runtime: Miniprot was over 30 times faster than Spaln2 and GeMoMa, with the performance gap increasing as evolutionary divergence increased.The authors attribute this potentially to miniprot’s faster dynamic programming, which allows alignment through introns regardless of sequence divergence.
4 DISCUSSIONS
Miniprot is intended as a fast, accurate aid for protein-based gene annotation rather than a replacement for full annotation pipelines. The discussion also identifies future HMMER-profile support and the continued importance of efficient annotation as genome sequencing expands.
- Practical use: Miniprot combines approximate protein mapping and exact splice alignment in one step, simplifying workflows that otherwise localize proteins before applying older aligners.The authors describe it as useful for gene annotation and potentially for evaluating de novo assemblies.
- Practical use: Miniprot can find 90% of coding regions in minutes when closely related species are available.This result is reported using base sensitivity on the human-mouse dataset.
- Scope and limitations: Miniprot does not replace full-fledged pipelines such as BRAKER2 because it aligns proteins independently and cannot merge identical models or resolve conflicts.BRAKER2 also includes ab initio prediction and a more sophisticated target-genome-independent splice model.
- Future work: HMMER-profile queries may reduce the number of queries and improve sensitivity for distant homologs, but the required seeding and alignment solutions remain unresolved.The authors identify position-specific substitution and gap costs as one possible alignment direction.
- Motivation: Large sequencing projects are producing many reference-quality genomes, increasing the importance of scalable genome annotation tools.The discussion contrasts rapid advances in sequencing and assembly with continued reliance on older annotation tools.
Aligning proteins to genomes with miniprot
The supplied passages for this section consist of bibliographic references rather than substantive method text. They identify prior work on sequence alignment, gene annotation, genome assembly, and related computational methods.
- Gene annotation: The references include tools and workflows for gene annotation and gene-structure prediction.Examples include CAT, GeMoMa, MAKER2, and related annotation approaches.
- Prior alignment methods: The references include prior work on protein-to-genome and genomic sequence alignment.Cited examples include direct protein-to-genome mapping, spliced alignment, and sequence-comparison methods.
- Computational context: The bibliography also cites methods for large-scale sequence searching, genome assembly, RNA-seq alignment, and profile-HMM analysis.These references include minimap2, MMseqs2, long-read assembly, STAR, and HMMER-related work.