Chen Duhong, Eulenstein Oliver, Fernandez-Baca David, Sanderson Michael
Department of Computer Science, Iowa State University, Ames, IA 50011-1040, USA.
IEEE/ACM Trans Comput Biol Bioinform. 2006 Apr-Jun;3(2):165-73. doi: 10.1109/TCBB.2006.26.
The input to a supertree problem is a collection of phylogenetic trees that intersect pairwise in their leaf sets; the goal is to construct a single tree that retains as much as possible of the information in the input. This task is complicated by inconsistencies due to errors. We consider the case where the input trees are rooted and are represented by the clusters they exhibit. The problem is to find the minimum number of flips needed to resolve all inconsistencies, where each flip moves a taxon into or out of a cluster. We prove that the minimum-flip problem is NP-complete, but show that it is fixed-parameter tractable and give approximation algorithms for special cases.
超树问题的输入是一组系统发育树，这些树在叶集上两两相交；目标是构建一棵单一的树，尽可能多地保留输入中的信息。由于错误导致的不一致性使这项任务变得复杂。我们考虑输入树是有根的且由它们所展示的簇来表示的情况。问题是找到解决所有不一致性所需的最少翻转次数，其中每次翻转将一个分类单元移入或移出一个簇。我们证明最少翻转问题是NP完全问题，但表明它是固定参数可处理的，并给出了特殊情况下的近似算法。
