Algorithms for Colinear Chaining with Overlaps and Gap Costs
Algorithms for Colinear Chaining with Overlaps and Gap Costs
复制标题
DOI：
10.1089/cmb.2022.0266
复制
发表时间：
2022-11-01
影响因子：
1.7
通讯作者：
Thankachan, Sharma V.
中科院分区：
文献类型：
--
作者：
Jain, Chirag;Gibney, Daniel;Thankachan, Sharma V.
共线性链接已被证明是一种强大的启发式方法，用于寻找长DNA序列(例如，长阅读或基因组组装)与参考序列的近乎最佳的比对。它被用作几个采用种子链延伸策略的比对工具的中间步骤。尽管这种流行，但对于链支持锚点重叠和间隙成本的一般情况，有效的次二次时间算法目前尚不清楚。我们给出了在(O)over Tilden)时间内具有锚点重叠和缺口代价的共线链接问题的算法，其中n表示锚点的个数。多对数系数的程度取决于所使用的锚链的类型(例如，固定长度的锚链)以及最优锚链需要满足的优先顺序的类型。我们还首次建立了共线链接成本与编辑距离之间的理论联系。具体地，我们证明了对于一组固定的锚点，在精心设计的链接代价函数下，最优的“锚定”编辑距离等于最优的共线链接代价。两个序列和一组锚点的定位编辑距离仅是标准编辑距离的略微概括。对于不受任何锚支持的两个匹配符号的对齐，它增加了1的额外成本。最后，实验证明，在该代价函数下，最优共线链代价的计算速度可以比编辑距离快几个数量级，对于近距离和远距离相关的序列，其相关系数都达到了0.9。
Colinear chaining has proven to be a powerful heuristic for finding near-optimal alignments of long DNA sequences (e.g., long reads or a genome assembly) to a reference. It is used as an intermediate step in several alignment tools that employ a seed-chain-extend strategy. Despite this popularity, efficient subquadratic time algorithms for the general case where chains support anchor overlaps and gap costs are not currently known. We present algorithms to solve the colinear chaining problem with anchor overlaps and gap costs in (O) over tilden) time, where n denotes the count of anchors. The degree of the polylogarithmic factor depends on the type of anchors used (e.g., fixed-length anchors) and the type of precedence an optimal anchor chain is required to satisfy. We also establish the first theoretical connection between colinear chaining cost and edit distance. Specifically, we prove that for a fixed set of anchors under a carefully designed chaining cost function, the optimal ''anchored'' edit distance equals the optimal colinear chaining cost. The anchored edit distance for two sequences and a set of anchors is only a slight generalization of the standard edit distance. It adds an additional cost of one to an alignment of two matching symbols that are not supported by any anchor. Finally, we demonstrate experimentally that optimal colinear chaining cost under the proposed cost function can be computed orders of magnitude faster than edit distance, and achieves correlation coefficient >0.9 with edit distance for closely as well as distantly related sequences.