Level-k Phylogenetic Networks Are Constructable from a Dense Triplet Set in Polynomial Time

DOI10.1007/978-3-642-02441-2_25zbMath1247.92019OpenAlexW1821350330MaRDI QIDQ3637119

Thu-Hien To, Michel A. Habib

Publication date: 7 July 2009

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02441-2_25

Mathematics Subject Classification ID

Problems related to evolution (92D15) Complexity and performance of numerical algorithms (65Y20) Computational methods for problems pertaining to biology (92-08) Systems biology, networks (92C42)

Related Items

Encoding and constructing 1-nested phylogenetic networks with trinets ⋮ On encodings of phylogenetic networks of bounded level ⋮ Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable ⋮ Reconstructing a phylogenetic level-1 network from quartets ⋮ When two trees go to war ⋮ New results on optimizing rooted triplets consistency ⋮ Hierarchies from lowest stable ancestors in nonbinary phylogenetic networks ⋮ The Structure of Level-k Phylogenetic Networks

Cites Work

• Unnamed Item
• Inferring a level-1 phylogenetic network from a dense set of rooted triplets
• Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology
• Computing the maximum agreement of phylogenetic networks
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks
• Constructing the Simplest Possible Phylogenetic Network from Triplets
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• Computing and Combinatorics
• Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network