2025/12/04 by Gibson, Spencer, Yu, Yun William
#Data Structures and Algorithms (cs.DS) #FOS: Biological sciences #FOS: Computer and information sciences #Quantitative Methods (q-bio.QM)
paper · doi:10.48550/arxiv.2512.05247
Given a sequence s1 of n letters drawn i.i.d. from an alphabet of size σ and a mutated substring s2 of length m < n, we often want to recover the mutation history that generated s2 from s1. Modern sequence aligners are widely used for this task, and many employ the seed-chain-extend heuristic with k-mer seeds. Previously, Shaw and Yu showed that optimal linear-gap cost chaining can produce a chain with 1 - O((1)/(√(m))) recoverability, the proportion of the mutation history that is recovered, in O(mn2.43θ log n) expected time, where θ< 0.206 is the mutation rate under a substitution-only channel and s1 is assumed to be uniformly random. However, a gap remains between theory and practice, since real genomic data includes insertions and deletions (indels), and yet seed-chain-extend remains effective. In this paper, we generalize those prior results by introducing mathematical machinery to deal with the two new obstacles introduced by indel channels: the dependence of neighboring anchors and the presence of anchors that are only partially correct. We are thus able to prove that the expected recoverability of an optimal chain is ≥ 1 - O((1)/(√(m))) and the expected runtime is O(mn3.15 ⋅ θTlog n), when the total mutation rate given by the sum of the substitution, insertion, and deletion mutation rates (θT = θi + θd + θs) is less than 0.159.