Estimating how much two evolutionarily related genomes have drifted apart is one of the oldest quantitative questions in molecular evolution, and one of the most computationally demanding at modern scale. With sequencing projects now producing millions of genomes, full alignments have become impractical for many comparisons, and researchers increasingly rely on alignment-free statistics, most commonly counts of short DNA words called k-mers.
The work, published open access in Algorithms for Molecular Biology by Mahmudur Rahman Hera, Paul Medvedev, David Koslicki and Antonio Blanca, addresses a weakness that has quietly limited alignment-free methods for years. Nearly all existing theoretical models treat evolution as a pure substitution process, in which individual letters are swapped but nothing is inserted or removed. Yet insertions and deletions, collectively known as indels, make up a substantial fraction of genomic variation and play crucial roles in evolution. When indels are frequent, substitution-only estimators systematically inflate divergence, and the distortion is not merely cosmetic: it can misplace taxa even in otherwise well-resolved phylogenetic trees of primates built from k-mer Jaccard similarities, as prior work cited by the authors showed.
The core difficulty is mechanical as much as conceptual. A single substitution disrupts every k-mer that overlaps it, so a mutation at one position can corrupt up to k consecutive k-mers. Indels do the same, and substitution-only methods have no way to attribute the resulting mismatches to their true cause. The mismatched k-mers get booked as substitutions, inflating the apparent substitution rate. The new paper confronts this by defining a mutation model that explicitly incorporates single-nucleotide substitutions, deletions, and insertions whose lengths follow a geometric distribution, and then deriving algebraic formulas that recover all three parameters from a handful of observables.
The mathematics rests on three random variables defined over k-spans, intervals of length k along the original sequence. The first, N, counts k-spans containing no mutation at all; the second, D, counts k-spans whose only mutation is exactly one deletion. Alongside the length of the mutated string and a composition-sensitive statistic built from the count of ‘A’ nucleotides, these quantities carry enough information to pin down the model. The authors first derive the expected values of these observables as functions of the unknown parameters, then plug in the observed values and solve the resulting system of linear equations. The payoff of this design choice is that the estimators are closed-form expressions rather than numerical roots of high-degree polynomials, which is what makes rigorous guarantees tractable.
Those guarantees come in the form of concentration inequalities. The central theorem shows that each estimate lands within a symmetric interval around its true value with probability bounded by terms that decay exponentially in the sequence length, provided the mutation parameters and k-mer size are fixed and the sequence is long enough. A corollary makes this precise: under stated assumptions, the probability that any of the three estimates deviates from its true value shrinks like an exponential in L, the length of the original string. The assumptions are mild in practice — they require, for instance, that the count of ‘A’ nucleotides is strictly less than a quarter of the sequence length, a condition the authors note can always be satisfied by relabeling which nucleotide plays the special role, since at least one of the four bases must meet it.
The theory also predicts where the method should fail, and the simulations confirm those predictions. Because the estimators involve division by the quantity L minus four times the count of ‘A’s, they become unstable when the genome’s ‘A’ content sits at exactly 25 percent, and the experiments show erratic, sometimes negative estimates in that regime. Longer k-mers produce more variable estimates, again matching the theory, since a single mutation disrupts more k-mers as k grows. Shorter sequences are less stable than longer ones, consistent with error probabilities that vanish asymptotically in the sequence length. In one sensitivity experiment the variability of the substitution-rate estimate barely changed as k moved from 15 to 39, a behavior the authors flag as not immediately understood and a target for future analysis, possibly involving counts of k-spans with a single substitution.
Across a broad sweep of simulated evolution, the estimators performed strongly. On synthetic genomes of one million nucleotides with 30 percent ‘A’ content, and on the 2.8-million-nucleotide reference assembly of Staphylococcus aureus, the team varied all three parameters from 0.01 to 0.05 and generated ten independent mutated genomes per combination. When the two parameters not being estimated were held at the low value of 0.01, the estimates clustered tightly around the truth, with boxplots so narrow they nearly vanish in the figures. When the other two parameters were raised to 0.05 — total mutation rates exceeding ten percent, which the authors describe as challenging conditions — accuracy decreased slightly and variance grew, but median estimates remained close to the true rates, and the pattern held for both the synthetic and the real bacterial genome.
The most striking comparison comes against a simple mutation model that considers substitutions only. Using k-mer statistics from a recent prior work, the authors estimated substitution rates under that substitution-only framework for the same simulated S. aureus data and plotted the results against their own. Their joint estimator tracked the true substitution rates closely, while the substitution-only model produced gross overestimation. The reason is transparent: with no indel parameters in the model, the effects of all three mutation processes are absorbed into a single substitution rate, and the model cannot disentangle the distinct contributions of substitutions, insertions and deletions. The new model decomposes those components, which is precisely what allows each to be estimated accurately.
Turning theory into software required an ad hoc but workable solution to a genuinely hard subproblem. The estimators need counts of N and D, but k-mers carry no positional context, so identifying which k-mers correspond to unmutated or singly-deleted spans is not trivial — ambiguities arise, for example, when an inserted character matches the one deleted beside it. The implementation builds a de Bruijn graph of the original sequence with the cuttlefish tool, extracts unitigs, and uses semi-global alignment via the edlib library to align unitigs of the mutated sequence against them, scanning windows of length k to accumulate the counts. The authors are candid that efficiency was not the goal; they describe finding an efficient way to compute these counts on large datasets as an open research question, and note that a more thorough evaluation on real genomic data, where the unitig-based approach may become infeasible, is needed to establish practical utility.
What the paper delivers, in the authors’ framing, is a bridge between sequence evolution and combinatorial word statistics: a mutation process rich enough to include indels, yet structured enough to admit closed-form estimators with sub-exponential concentration bounds. An implementation that takes two FASTA files and returns the estimated parameters is available on GitHub, along with code reproducing every experiment in the manuscript. Beyond immediate use, the authors point to several directions: incorporating single-substitution span counts to explain the puzzling stability of the substitution estimator at larger k, extending the framework to heterogeneous or context-dependent rates, and coupling the estimators with sketch-based distance measures to support large-scale applications such as phylogenetic placement in genomes with high indel activity. As sequencing data continues to outpace alignment-based paradigms, tools that quantify mutation honestly — counting insertions and deletions as what they are, rather than disguising them as substitutions — are likely to matter well beyond this one model.
Subject of Research: Alignment-free k-mer-based estimation of substitution, insertion and deletion mutation rates between related sequences
Article Title: Estimation of substitution and indel rates via k-mer statistics
Article References: Hera, M. R., Medvedev, P., Koslicki, D., & Blanca, A. (2026). Estimation of substitution and indel rates via k-mer statistics. Algorithms for Molecular Biology, 21(1), Article 15. https://doi.org/10.1186/s13015-026-00299-9
Image Credits: AI Generated
DOI: 10.1186/s13015-026-00299-9
Keywords: k-mers, mutation rates, substitutions, insertions, deletions, alignment-free methods, concentration inequalities, bioinformatics, comparative genomics, indel model, Staphylococcus aureus, sequence evolution
News Source: Drew Townsend. (October 28, 2026). New k-mer estimators untangle substitutions, insertions and deletions in evolving genomes. Scienmag.
