

























A phylogenetic tree is a graphical representation of an evolutionary history of taxa in which the leaves correspond to the taxa and the non-leaves correspond to speciations. One of important problems in phylogenetic analysis is to assemble a global phylogenetic tree from small phylogenetic trees, particularly, quartet trees. {\sc Quartet Compatibility} is the problem of deciding whether there is a phylogenetic tree inducing a given collection of quartet trees, and to construct such a phylogenetic tree if it exists. It is known that {\sc Quartet Compatibility} is NP-hard and that there are only a few results known for polynomial-time solvable subclasses. In this paper, we introduce two novel classes of quartet systems, called complete multipartite quartet system and full multipartite quartet system, and present polynomial-time algorithms for {\sc Quartet Compatibility} for these systems.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。