Regular Language Constrained Sequence Alignment Revisited
Regular Language Constrained Sequence Alignment Revisited
复制标题
重新审视常规语言约束序列比对
DOI：
10.1089/cmb.2010.0291
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Michal Ziv
中科院分区：
文献类型：
--
作者：
G. Kucherov;Tamar Pinhas;Michal Ziv
以有限自动机或正则表达式的形式施加约束是将额外的先验知识结合到序列比对过程中的有效方式。在此基础上，提出了正则表达式约束序列比对问题，并给出了一个时间复杂度为O（n²t ²），空间复杂度为O（n²t²）的算法，其中n是输入字符串的长度，t是输入非确定自动机的状态数。一个更快的O（n²t）时间的算法为相同的问题随后提出。在本文中，我们进一步加快了正则语言约束序列对齐算法，将其最坏情况下的时间复杂度降低到O（n²t）/log t）。这是通过建立一个最佳的边界上的大小的直线程序解决最大计算子问题的基本动态规划算法。我们还研究了基于Steiner树计算的另一种解决方案。虽然它并没有改善最坏的情况下，我们的模拟表明，这两种方法在实践中是有效的，特别是当输入自动机是密集的。
Imposing constraints in the form of a finite automaton or a regular expression is an effective way to incorporate additional a priori knowledge into sequence alignment procedures. With this motivation, the Regular Expression Constrained Sequence Alignment Problem was introduced, which proposed an O(n²t⁴) time and O(n²t²) space algorithm for solving it, where n is the length of the input strings and t is the number of states in the input non-deterministic automaton. A faster O(n²t³) time algorithm for the same problem was subsequently proposed. In this article, we further speed up the algorithms for Regular Language Constrained Sequence Alignment by reducing their worst case time complexity bound to O(n²t³)/log t). This is done by establishing an optimal bound on the size of Straight-Line Programs solving the maxima computation subproblem of the basic dynamic programming algorithm. We also study another solution based on a Steiner Tree computation. While it does not improve the worst case, our simulations show that both approaches are efficient in practice, especially when the input automata are dense.