Back to Search
Start Over
Reconstructing Phylogenetic Trees from Multipartite Quartet Systems.
- Source :
-
Algorithmica . Jul2022, Vol. 84 Issue 7, p1875-1896. 22p. - Publication Year :
- 2022
-
Abstract
- 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]
- Subjects :
- *ARBORETUMS
Subjects
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 84
- Issue :
- 7
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 157613812
- Full Text :
- https://doi.org/10.1007/s00453-022-00945-9