On Incremental Computation of Transitive Closure and Greedy Alignment
On Incremental Computation of Transitive Closure and Greedy Alignment
复制标题
传递闭包与贪婪对齐的增量计算
DOI：
10.1007/3-540-63220-4_58
复制
发表时间：
1997
期刊：
影响因子：
5.8
通讯作者：
Saïd Abdeddaïm
中科院分区：
文献类型：
--
作者：
Saïd Abdeddaïm
针对序列的多重比对问题，提出了几种基于启发式算法的算法。最有效的时间计算通常是贪婪算法。在每一步中，贪婪对齐算法必须知道两个字符是否可对齐，根据之前确定对齐的字符。我们证明了这个问题是可约的，可以在有向图中找到路径。我们给出了一种增量算法，它维持了一个图的传递闭包，对于这个图我们知道有k个不连接路径的生成集。我们的算法在O（k 2m +n min, n）时间和O（kn）空间内维持了n个顶点和m条边（最终状态）的图的传递闭包。对于总长度为n的k个序列，通过在O（k2n+n2）时间和O（kn）空间内保持对齐图的传递闭包，我们证明了该算法可用于任何贪婪对齐算法，以在常数时间内知道两个字符是否可对齐。作为应用示例，我们实现了TwoAlign一个基于贪婪计算两两局部对齐的高效多对齐程序。
Several algorithms based on heuristics have been proposed for the multiple alignment of sequences. The most efficient in time computation are often greedy algorithms. At each step a greedy alignment algorithm must know if two characters are alignable or not, regarding to the characters definitely aligned before. We show that this problem is reducible to find paths in a directed graph. We give an incremental algorithm that maintains the transitive closure of a graph for which we know a spanning set of k disjoined paths. Our algorithm maintains the transitive closure of a graph of n vertices and m edges (in the final state) in O(k 2 m+n minm, n) time and O(kn) space. We show that this algorithm can be used by any greedy alignment algorithm to know in constant time if two characters are alignable or not, by maintaining the transitive closure of an alignment graph in O(k2n+n2) time and O(kn) space, for k sequences whose total length is n. As an example of application we have implemented TwoAlign a efficient multiple alignment program based on greedy computation of pairwise local alignments.