Incorporating indel channels into average-case analysis of seed-chain-extend.

Abstract

Given a sequence s1 of n letters drawn independently and identically (i.i.d.) from an alphabet of size σ and a mutated substring s2 of length m<n, we want to recover the mutation history that generated s2 from s1. Many modern sequence aligners for this task use seed-chain-extend with k-mer seeds. Previously, Shaw and Yu showed linear-gap cost chaining can produce a chain with 1-O(1m) recoverability, the proportion of the mutation history that is recovered, in O(mn2.43θ log n) expected time for seed-chain-extend (assuming pre-seeded reference), where θ<0.206 is the mutation rate under a substitution-only channel and s1 is uniformly random. A gap remains between theory and practice, as real genomes include insertions and deletions (indels). We introduce mathematical machinery to deal with the two new obstacles introduced by indel channels: the dependence of neighbouring anchors and the presence of anchors that are only partially correct. We prove that expected recoverability of an optimal chain is ≥1-O(1m) and expected runtime is O(mn3.15·θT log n), given the total mutation rate θT=θi+θd+θs (sum of substitution, insertion, and deletion rates) is θT≤0.159. We thus narrow (but not close) the gap between theory and practice. https://github.com/Lazarus42/seed_chainer_indels.