The tree compatibility problem is a problem arising in the theory of computational biology. For a species set S, the problem asks whether /spl tau/, a family of trees on S, is compatible, in the sense that there is a single tree T from which each tree of the family can be derived by a sequence of edge contractions. Steel (1992) demonstrated that this problem is NP-complete if /spl tau/ is a family of unrooted trees. Polynomial time algorithms exist when /spl tau/ is a finite family of rooted trees. In this paper, we present an algorithm for constructing a rooted tree from a set of constraints on subsets of a set of elements. We then apply this algorithm to synthesize a rooted supertree, compatible with two given rooted trees.
展开▼
机译：树兼容性问题是计算生物学理论中出现的问题。对于一个物种集S，该问题询问/ spl tau /（S上的一棵树）是否兼容，从某种意义上说，存在一个单一的树T，可以通过一系列边沿从该树导出该树的每棵树收缩。 Steel（1992）证明，如果/ spl tau /是无根树木家族，则此问题是NP完全的。当/ spl tau /是根树的有限族时，存在多项式时间算法。在本文中，我们提出了一种从一组元素子集上的一组约束中构造一棵根树的算法。然后，我们应用此算法来合成与两个给定的根树兼容的根超级树。
展开▼
