| Autor: |
Hirai, Hiroshi, Iwamasa, Yuni |
| Předmět: |
|
| Zdroj: |
Algorithmica; Jul2022, Vol. 84 Issue 7, p1875-1896, 22p |
| Abstrakt: |
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. 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 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 Quartet Compatibility for these systems. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
Full text from SpringerLink