Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks

DOI10.1016/j.jda.2009.01.004zbMath1181.90270arXiv0710.3258OpenAlexW1778865519MaRDI QIDQ2266938

Jaroslaw Byrka, Katharina T. Huber, Steven Kelk, Paweł Gawrychowski

Publication date: 26 February 2010

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

phylogenetic networktripletlevel-\(k\) network

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Related Items

The Approximability of Maximum Rooted Triplets Consistency with Fan Triplets and Forbidden Triplets ⋮ Building a small and informative phylogenetic supertree ⋮ Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees ⋮ The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets ⋮ New heuristics for rooted triplet consistency ⋮ Constructing the simplest possible phylogenetic network from triplets ⋮ New results on optimizing rooted triplets consistency ⋮ Unnamed Item ⋮ Computing the rooted triplet distance between phylogenetic networks ⋮ Level-k Phylogenetic Networks Are Constructable from a Dense Triplet Set in Polynomial Time ⋮ The Structure of Level-k Phylogenetic Networks

Cites Work

• Inferring a level-1 phylogenetic network from a dense set of rooted triplets
• Optimization, approximation, and complexity classes
• On the complexity of constructing evolutionary trees
• A framework for representing reticulate evolution
• Phylogenetic supertrees. Combining information to reveal the tree of life
• Constructing the maximum consensus tree from rooted Triples
• Tripartitions do not always discriminate phylogenetic networks
• Phylogenetic networks from multi-labelled trees
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item