Reconstructing phylogenetic trees from multipartite quartet systems

DOI10.1007/S00453-022-00945-9MaRDI QIDQ2149097zbMATH OpenOpenAlexFDO

Authors Hiroshi Hirai, Yuni Iwamasa

Publication date 28 June 2022

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.01914

zbMATH Keywords

phylogenetic treereconstructionsupertreequartet system

Mathematics Subject Classification ID

Problems related to evolution (92D15) Graph algorithms (graph-theoretic aspects) (05C85)

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. {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.

Recommendations

• On the compatibility of quartet trees
• On the compatibility of quartet trees
• scientific article; zbMATH DE number 1305402
• Extension operations on sets of leaf-labelled trees
• scientific article; zbMATH DE number 1302377

Cites work

• scientific article; zbMATH DE number 1026279 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• scientific article; zbMATH DE number 1405796 (Why is no real title available?)
• scientific article; zbMATH DE number 1445316 (Why is no real title available?)
• A fixed-parameter algorithm for minimum quartet inconsistency
• A polynomial time approximation scheme for inferring evolutionary trees from quartet topologies and its application
• A supertree method for rooted trees
• A tractable class of binary VCSPs via M-convex intersection
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Extension operations on sets of leaf-labelled trees
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• New fixed-parameter algorithms for the minimum quartet inconsistency problem
• Reconstructing the shape of a tree from observed dissimilarity data
• The complexity of reconstructing trees from qualitative characters and subtrees
• Tree structures for proximity data

Cited in

(9)

• On the compatibility of quartet trees
• On the compatibility of quartet trees
• Using the tangle: A consistent construction of phylogenetic distance matrices for quartets
• Quartet compatibility and the quartet graph
• scientific article; zbMATH DE number 6297767 (Why is no real title available?)
• Logic Programming and Nonmonotonic Reasoning
• Identifying species network features from gene tree quartets under the coalescent model
• QUARTET CONSISTENCY COUNT METHOD FOR RECONSTRUCTING PHYLOGENETIC TREES
• Slim sets of binary trees

This page was built for publication: Reconstructing phylogenetic trees from multipartite quartet systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2149097)