Paper Info
Title
Reconstructing Phylogenetic Tree From Multipartite Quartet System.
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. We also see that complete/full multipartite quartet systems naturally arise from a limited situation of block-restricted measurement.
Year
DOI
Venue
2018
10.4230/LIPIcs.ISAAC.2018.57
ISAAC
Field
DocType
Citations 
Discrete mathematics,Combinatorics,Phylogenetic tree,Multipartite,Time complexity,Taxon,Mathematics
Conference
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Hiroshi Hirai182.99
Yuni Iwamasa252.84