TY - GEN
T1 - Estimation of Substitution and Indel Rates via k-mer Statistics
AU - Rahman Hera, Mahmudur
AU - Medvedev, Paul
AU - Koslicki, David
AU - Blanca, Antonio
N1 - Publisher Copyright:
© Mahmudur Rahman Hera, Paul Medvedev, David Koslicki, and Antonio Blanca.
PY - 2025/8/15
Y1 - 2025/8/15
N2 - Methods utilizing k-mers are widely used in bioinformatics, yet our understanding of their statistical properties under realistic mutation models remains incomplete. Previously, substitution-only mutation models have been considered to derive precise expectations and variances for mutated k-mers and intervals of mutated and non-mutated sequences. In this work, we consider a mutation model that incorporates insertions and deletions in addition to single-nucleotide substitutions. Within this framework, we derive closed-form k-mer-based estimators for the three fundamental mutation parameters: substitution, deletion rate, and insertion rates. We provide theoretical guarantees in the form of concentration inequalities, ensuring accuracy of our estimators under reasonable model assumptions. Empirical evaluations on simulated evolution of genomic sequences confirm our theoretical findings, demonstrating that accounting for insertions and deletions signals allows for accurate estimation of mutation rates and improves upon the results obtained by considering a substitution-only model. An implementation of estimating the mutation parameters from a pair of fasta files is available here: github.com/KoslickiLab/estimate_rates_using_mutation_model.git. The results presented in this manuscript can be reproduced using the code available here: github.com/KoslickiLab/est_rates_experiments.git.
AB - Methods utilizing k-mers are widely used in bioinformatics, yet our understanding of their statistical properties under realistic mutation models remains incomplete. Previously, substitution-only mutation models have been considered to derive precise expectations and variances for mutated k-mers and intervals of mutated and non-mutated sequences. In this work, we consider a mutation model that incorporates insertions and deletions in addition to single-nucleotide substitutions. Within this framework, we derive closed-form k-mer-based estimators for the three fundamental mutation parameters: substitution, deletion rate, and insertion rates. We provide theoretical guarantees in the form of concentration inequalities, ensuring accuracy of our estimators under reasonable model assumptions. Empirical evaluations on simulated evolution of genomic sequences confirm our theoretical findings, demonstrating that accounting for insertions and deletions signals allows for accurate estimation of mutation rates and improves upon the results obtained by considering a substitution-only model. An implementation of estimating the mutation parameters from a pair of fasta files is available here: github.com/KoslickiLab/estimate_rates_using_mutation_model.git. The results presented in this manuscript can be reproduced using the code available here: github.com/KoslickiLab/est_rates_experiments.git.
UR - https://www.scopus.com/pages/publications/105013845165
UR - https://www.scopus.com/pages/publications/105013845165#tab=citedBy
U2 - 10.4230/LIPIcs.WABI.2025.16
DO - 10.4230/LIPIcs.WABI.2025.16
M3 - Conference contribution
C2 - 42022475
AN - SCOPUS:105013845165
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 25th International Conference on Algorithms for Bioinformatics, WABI 2025
A2 - Brejova, Brona
A2 - Patro, Rob
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 25th International Conference on Algorithms for Bioinformatics, WABI 2025
Y2 - 20 August 2025 through 22 August 2025
ER -