On the weighted quartet consensus problem

DOI10.1016/J.TCS.2018.10.005MaRDI QIDQ1737590zbMATH OpenOpenAlexWikidataFDO

Authors Manuel Lafond, Celine Scornavacca

Publication date 23 April 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

phylogenetic treeapproximation algorithmsbioinformaticsderandomizationNP-hardness

Mathematics Subject Classification ID

Problems related to evolution (92D15) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Abstract: In phylogenetics, the consensus problem consists in summarizing a set of phylogenetic trees that all classify the same set of species into a single tree. Several definitions of consensus exist in the literature; in this paper we focus on the Weighted Quartet Consensus problem, a problem with unknown complexity status so far. Here we prove that the Weighted Quartet Consensus problem is NP-hard and we give a 1/2-factor approximation for this problem. During the process, we propose a derandomization procedure of a previously known randomized 1/3-factor approximation. We also investigate the fixed-parameter tractability of this problem.

Recommendations

• On the weighted quartet consensus problem
• scientific article; zbMATH DE number 6297767
• Reconstructing approximate phylogenetic trees from quartet samples
• scientific article; zbMATH DE number 1305402
• scientific article; zbMATH DE number 1786463

Cites work

• scientific article; zbMATH DE number 1974599 (Why is no real title available?)
• scientific article; zbMATH DE number 1786463 (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 New Quartet Approach for Reconstructing Phylogenetic Trees: Quartet Joining Method
• A polynomial time approximation scheme for inferring evolutionary trees from quartet topologies and its application
• Basic phylogenetic combinatorics.
• Combinatorial optimization solutions for the maximum quartet consistency problem
• Comparing and Aggregating Partially Resolved Trees
• Comparing and aggregating partially resolved trees
• Consensus n-trees
• Constructing optimal trees from quartets
• Cyclic ordering is NP-complete
• 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
• New results on optimizing rooted triplets consistency
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• The complexity of reconstructing trees from qualitative characters and subtrees
• The median procedure for n-trees

Cited in

(3)

• On the weighted quartet consensus problem
• The large-sample asymptotic behaviour of quartet-based summary methods for species tree inference
• A bound on partitioning clusters

Describes a project that uses

Uses Software

• ASTRAL-II

This page was built for publication: On the weighted quartet consensus problem

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