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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Practical Colinear Chaining on Sequences Revisited

  • Nicola Rizzo,
  • Manuel Cáceres,
  • Veli Mäkinen

摘要

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.