Berry Vincent, Nicolas François
Equipe Méthodes et Algorithmes pour la Bioinformatique-L.I.R.M.M., Montpellier, France.
IEEE/ACM Trans Comput Biol Bioinform. 2006 Jul-Sep;3(3):289-302. doi: 10.1109/TCBB.2006.39.
Given a set of evolutionary trees on a same set of taxa, the maximum agreement subtree problem (MAST), respectively, maximum compatible tree problem (MCT), consists of finding a largest subset of taxa such that all input trees restricted to these taxa are isomorphic, respectively compatible. These problems have several applications in phylogenetics such as the computation of a consensus of phylogenies obtained from different data sets, the identification of species subjected to horizontal gene transfers and, more recently, the inference of supertrees, e.g., Trees Of Life. We provide two linear time algorithms to check the isomorphism, respectively, compatibility, of a set of trees or otherwise identify a conflict between the trees with respect to the relative location of a small subset of taxa. Then, we use these algorithms as subroutines to solve MAST and MCT on rooted or unrooted trees of unbounded degree. More precisely, we give exact fixed-parameter tractable algorithms, whose running time is uniformly polynomial when the number of taxa on which the trees disagree is bounded. The improves on a known result for MAST and proves fixed-parameter tractability for MCT.
给定一组关于同一组分类单元的进化树，最大一致子树问题（MAST）以及最大兼容树问题（MCT），分别是要找到一个最大的分类单元子集，使得限制在这些分类单元上的所有输入树分别是同构的或兼容的。这些问题在系统发育学中有多种应用，比如计算从不同数据集获得的系统发育的共识、识别经历水平基因转移的物种，以及最近推断超级树，例如生命之树。我们提供了两种线性时间算法，分别用于检查一组树的同构性或兼容性，否则识别这些树在一小部分分类单元的相对位置方面的冲突。然后，我们将这些算法用作子程序来解决无根或有根的、度数无界的树上的MAST和MCT问题。更确切地说，我们给出了精确的固定参数可处理算法，当树不一致的分类单元数量有界时，其运行时间是一致多项式的。这改进了MAST的一个已知结果，并证明了MCT的固定参数可处理性。
