Siepel Adam C
Department of Computer Science, University of New Mexico, Albuquerque, NM 87131, USA.
J Comput Biol. 2003;10(3-4):575-97. doi: 10.1089/10665270360688200.
The rearrangement distance between single-chromosome genomes can be estimated as the minimum number of inversions required to transform the gene ordering observed in one into that observed in the other. This measure, known as "inversion distance," can be computed as the reversal distance between signed permutations. During the past decade, much progress has been made both on the problem of computing reversal distance and on the related problem of finding a minimum-length sequence of reversals, which is known as "sorting by reversals." For most problem instances, however, many minimum-length sequences of reversals exist, and in the absence of auxiliary information, no one is of greater value than the others. The problem of finding all minimum-length sequences of reversals is thus a natural generalization of sorting by reversals, yet it has received little attention. This problem reduces easily to the problem of finding all "sorting reversals" of one permutation with respect to another - that is, all reversals rho such that, if rho is applied to one permutation, then the reversal distance of that permutation from the other is decreased. In this paper, an efficient algorithm is derived to solve the problem of finding all sorting reversals, and experimental results are presented indicating that, while the new algorithm does not represent a significant improvement in asymptotic terms (it takes O(n(3)) time, for permutations of size n; the problem can now be solved by brute force in Theta(n(3)) time), it performs dramatically better in practice than the best known alternative. An implementation of the algorithm is available at www.cse.ucsc.edu/~acs.
单染色体基因组之间的重排距离可以估计为将一个基因组中观察到的基因顺序转换为另一个基因组中观察到的基因顺序所需的最小反转次数。这种度量，即“反转距离”，可以作为有符号排列之间的反转距离来计算。在过去十年中，在计算反转距离的问题以及寻找最小长度反转序列（即“通过反转排序”）的相关问题上都取得了很大进展。然而，对于大多数问题实例，存在许多最小长度的反转序列，并且在没有辅助信息的情况下，没有一个序列比其他序列更有价值。因此，寻找所有最小长度反转序列的问题是通过反转排序的自然推广，但它很少受到关注。这个问题很容易归结为寻找一个排列相对于另一个排列的所有“排序反转”的问题——也就是说，所有的反转ρ，使得如果将ρ应用于一个排列，那么该排列与另一个排列的反转距离会减小。在本文中，我们推导了一种高效算法来解决寻找所有排序反转的问题，并给出了实验结果，表明虽然新算法在渐近意义上没有显著改进（对于大小为n的排列，它需要O(n(3))时间；现在可以通过暴力方法在Theta(n(3))时间内解决这个问题），但在实际应用中它比最知名的替代算法表现得要好得多。该算法的实现可在www.cse.ucsc.edu/~acs上获取。
