A linear-time algorithm for computing inversion distance between signed permutations with an experimental study
A linear-time algorithm for computing inversion distance between signed permutations with an experimental study
复制标题
DOI：
10.1089/106652701753216503
复制
发表时间：
2001-01-01
影响因子：
1.7
通讯作者：
Yan, M
中科院分区：
文献类型：
--
作者：
Bader, DA;Moret, BME;Yan, M
Hannenhalli和Pevzner给出了第一个计算两个有符号置换之间的反转距离的多项式时间算法，作为确定将一个置换转换为另一个置换所需的最短反转序列的更大任务的一部分。他们的算法（仅限于距离计算）分两个阶段进行：在第一阶段，由置换引起的重叠图被分解为连通分量;然后，在第二阶段，确定某些图结构（障碍和其他）。Berman和Hannenhalli避免了重叠图的显式计算，并给出了一个O（n alpha（n））的算法，基于Union-Find结构，以找到其连接组件，其中a是逆阿克曼函数。由于实际上alpha（n）是一个不大于4的常数，因此该算法是迄今为止最快的实用算法。本文提出了一种新的计算连通分支的线性时间算法，该算法在理论和实践上都比Berman和Hannenhalli的算法更有效。我们的算法只使用一个堆栈，是非常容易实现的。我们给出了通过模拟进化产生的大范围的置换对的计算实验的结果;我们的实验表明，在连接组件的计算中，速度提高了2到5倍，在整体距离计算中，速度提高了1.3到2倍。
Hannenhalli and Pevzner gave the first polynomial-time algorithm for computing the inversion distance between two signed permutations, as part of the larger task of determining the shortest sequence of inversions needed to transform one permutation into the other. Their algorithm (restricted to distance calculation) proceeds in two stages: in the first stage, the overlap graph induced by the permutation is decomposed into connected components; then, in the second stage, certain graph structures (hurdles and others) are identified. Berman and Hannenhalli avoided the explicit computation of the overlap graph and gave an O(n alpha (n)) algorithm, based on a Union-Find structure, to find its connected components, where a is the inverse Ackerman function. Since for all practical purposes alpha (n) is a constant no larger than four, this algorithm has been the fastest practical algorithm to date. In this paper, we present a new linear-time algorithm for computing the connected components, which is more efficient than that of Berman and Hannenhalli in both theory and practice. Our algorithm uses only a stack and is very easy to implement. We give the results of computational experiments over a large range of permutation pairs produced through simulated evolution; our experiments show a speed-up by a factor of 2 to 5 in the computation of the connected components and by a factor of 1.3 to 2 in the overall distance computation.