Reconstructing phylogenetic trees from multipartite quartet systems
From MaRDI portal
Publication:2149097
DOI10.1007/S00453-022-00945-9zbMATH Open1494.92078arXiv1904.01914OpenAlexW4214586829MaRDI QIDQ2149097FDOQ2149097
Publication date: 28 June 2022
Published in: Algorithmica (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1904.01914
Cites Work
- Title not available (Why is that?)
- Reconstructing the shape of a tree from observed dissimilarity data
- Tree structures for proximity data
- The complexity of reconstructing trees from qualitative characters and subtrees
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- A fixed-parameter algorithm for minimum quartet inconsistency
- Title not available (Why is that?)
- Extension operations on sets of leaf-labelled trees
- Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
- A supertree method for rooted trees
- New fixed-parameter algorithms for the minimum quartet inconsistency problem
- A polynomial time approximation scheme for inferring evolutionary trees from quartet topologies and its application
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Tractable Class of Binary VCSPs via M-Convex Intersection
Cited In (5)
- Logic Programming and Nonmonotonic Reasoning
- Identifying species network features from gene tree quartets under the coalescent model
- Title not available (Why is that?)
- Using the tangle: A consistent construction of phylogenetic distance matrices for quartets
- QUARTET CONSISTENCY COUNT METHOD FOR RECONSTRUCTING PHYLOGENETIC 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)
