New results on optimizing rooted triplets consistency
From MaRDI portal
Publication:708349
DOI10.1016/j.dam.2010.03.004zbMath1221.05041OpenAlexW2036921810MaRDI QIDQ708349
Jaroslaw Byrka, Sylvain Guillemot, Jesper Jansson
Publication date: 11 October 2010
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://infoscience.epfl.ch/record/140352/files/51c.pdf
approximation algorithmphylogenetic treehardness of approximationsupertreepseudorandomnessrooted triplet
Related Items
Binets: fundamental building blocks for phylogenetic networks ⋮ Complexity Insights of the Minimum Duplication Problem ⋮ Encoding and constructing 1-nested phylogenetic networks with trinets ⋮ Complexity of modification problems for best match graphs ⋮ The Approximability of Maximum Rooted Triplets Consistency with Fan Triplets and Forbidden Triplets ⋮ Kernel and fast algorithm for dense triplet inconsistency ⋮ Optimizing phylogenetic supertrees using answer set programming ⋮ Building a small and informative phylogenetic supertree ⋮ Orthology relations, symbolic ultrametrics, and cographs ⋮ Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique ⋮ Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees ⋮ Constructing the R* consensus tree of two trees in subcubic time ⋮ Complexity insights of the minimum duplication problem ⋮ Gene tree correction for reconciliation and species tree inference: complexity and algorithms ⋮ Comparing and aggregating partially resolved trees ⋮ The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets ⋮ On the weighted quartet consensus problem ⋮ Constructing a Consensus Phylogeny from a Leaf-Removal Distance (Extended Abstract) ⋮ The matroid structure of representative triple sets and triple-closure computation ⋮ Trinets encode tree-child and level-2 phylogenetic networks ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Rooted maximum agreement supertrees
- Inferring a level-1 phylogenetic network from a dense set of rooted triplets
- Analytic solutions for three taxon ML trees with variable rates across sites
- The complexity of reconstructing trees from qualitative characters and subtrees
- Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology
- On the complexity of constructing evolutionary trees
- A supertree method for rooted trees
- Constructing the maximum consensus tree from rooted Triples
- Reconstruction of rooted trees from subtrees
- Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks
- Maximum agreement and compatible supertrees
- Hardness of fully dense problems
- A Polynomial Time Approximation Scheme for Inferring Evolutionary Trees from Quartet Topologies and Its Application
- Algorithmic construction of sets for k -restrictions
- Fixed-Parameter Tractability of the Maximum Agreement Supertree Problem
- Level-k Phylogenetic Networks Are Constructable from a Dense Triplet Set in Polynomial Time
- Computing a Smallest Multi-labeled Phylogenetic Tree from Rooted Triplets
- Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
- Determining the Evolutionary Tree Using Experiments
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network
- Ranking Tournaments
