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

Abstract

MOTIVATION: Given a sequence s1 of n letters drawn independently and identically (i.i.d.) from an alphabet of size &#x3c3; 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&#x3b8;&#x2009;log&#x2009;n) expected time for seed-chain-extend (assuming pre-seeded reference), where &#x3b8;<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). RESULTS: 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 &#x2265;1-O(1m) and expected runtime is O(mn3.15&#xb7;&#x3b8;T&#x2009;log&#x2009;n), given the total mutation rate &#x3b8;T=&#x3b8;i+&#x3b8;d+&#x3b8;s (sum of substitution, insertion, and deletion rates) is &#x3b8;T&#x2264;0.159. We thus narrow (but not close) the gap between theory and practice. AVAILABILITY AND IMPLEMENTATION: https://github.com/Lazarus42/seed_chainer_indels.