Maximum independent sets of commuting and noninterfering inversions.
Maximum independent sets of commuting and noninterfering inversions.
复制标题
DOI：
10.1186/1471-2105-10-s1-s6
复制
发表时间：
2009-01-30
影响因子：
3
通讯作者：
Moret BM
中科院分区：
文献类型：
--
作者：
Swenson KM;To Y;Tang J;Moret BM
给定三个带符号的排列，反转中值是第四个排列，它与其他三个排列之间的成对反转距离之和最小。这个问题是np困难的，也很难近似。然而，基于中位数的系统发育重建方法已被证明是最准确的方法之一，特别是在存在长分支的情况下。大多数现有的方法都使用启发式方法，试图从三个排列中的一个找到最长的倒序序列，在序列的每一步中，向其他两个排列靠拢；然而，人们对这种方法所得到的解决方案的质量知之甚少。最近，Arndt和Tang在使用交换反转集寻找更长的这样的序列方面迈出了一步。在本文中，我们形式化了用我们称为签名的方法来寻找这样的反转序列的问题，并提供了寻找交换和非干扰反转的最大基数集的算法。我们的研究结果提供了一个研究中位数反转问题的框架，更快的算法来获得好的中位数，以及一种沿着进化路径研究特征事件的方法。
Given three signed permutations, an inversion median is a fourth permutation that minimizes the sum of the pairwise inversion distances between it and the three others. This problem is NP-hard as well as hard to approximate. Yet median-based approaches to phylogenetic reconstruction have been shown to be among the most accurate, especially in the presence of long branches. Most existing approaches have used heuristics that attempt to find a longest sequence of inversions from one of the three permutations that, at each step in the sequence, moves closer to the other two permutations; yet very little is known about the quality of solutions returned by such approaches. Recently, Arndt and Tang took a step towards finding longer such sequences by using sets of commuting inversions. In this paper, we formalize the problem of finding such sequences of inversions with what we call signatures and provide algorithms to find maximum cardinality sets of commuting and noninterfering inversions. Our results offer a framework in which to study the inversion median problem, faster algorithms to obtain good medians, and an approach to study characteristic events along an evolutionary path.