Practical Colinear Chaining on Sequences Revisited
摘要
Colinear chaining is a classical heuristic for sequence alignment and is widely used in modern practical aligners. Jain et al. (J. Comput. Biol. 2022) proposed an \(O(n \log ^3 n)\) time algorithm to chain a set of n anchors so that the chaining cost matches the edit distance of the input sequences, when anchors are all the maximal exact matches. Moreover, assuming a uniform and sparse distribution of anchors, they provided a practical solution (ChainX) working in \(O(n \cdot \textrm{SOL} + n \log n)\) average-case time, where \(\textrm{SOL}\) is the cost of the output chain. This practical solution is not guaranteed to be optimal: we study the failing cases, introduce the anchor diagonal distance, and find and implement an optimal algorithm working in \(O(n \cdot \textrm{OPT} + n \log n)\) average-case time, where \(\textrm{OPT}\) \(\le \textrm{SOL}\) is the optimal chaining cost. We validate the results by Jain et al., show that ChainX can be suboptimal with a realistic long read dataset, and show minimal computational slowdown for our solution.