Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable

DOI10.1007/s00453-012-9708-5zbMath1350.92036arXiv1108.3653OpenAlexW2092228832MaRDI QIDQ476442

Steven Kelk, Celine Scornavacca

Publication date: 2 December 2014

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

fixed parameter tractabilitydirected acyclic graphsphylogenetics

Mathematics Subject Classification ID

Trees (05C05) Problems related to evolution (92D15) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Kernelizations for the hybridization number problem on multiple nonbinary trees ⋮ Scanning Phylogenetic Networks Is NP-hard ⋮ Finding a most parsimonious or likely tree in a network with respect to an alignment ⋮ On unrooted and root-uncertain variants of several well-known phylogenetic network problems ⋮ Counting Phylogenetic Networks with Few Reticulation Vertices: Tree-Child and Normal Networks ⋮ Hybridization Number on Three Rooted Binary Trees is EPT ⋮ Treewidth of display graphs: bounds, brambles and applications ⋮ A Tight Kernel for Computing the Tree Bisection and Reconnection Distance between Two Phylogenetic Trees ⋮ Computing Maximum Agreement Forests without Cluster Partitioning is Folly ⋮ On Computing the Maximum Parsimony Score of a Phylogenetic Network

Uses Software

• rSPR

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Constructing the simplest possible phylogenetic network from triplets
• Inferring a level-1 phylogenetic network from a dense set of rooted triplets
• An efficiently computed lower bound on the number of recombinations in phylogenetic networks: theory and empirical study
• Computing the minimum number of hybridization events for a consistent evolutionary history
• A new recombination lower bound and the minimum perfect phylogenetic forest problem
• When two trees go to war
• Parametrized complexity theory.
• Fixed-Parameter Algorithms for Maximum Agreement Forests
• Level-k Phylogenetic Networks Are Constructable from a Dense Triplet Set in Polynomial Time
• The Structure of Level-k Phylogenetic Networks
• Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network
• Research in Computational Molecular Biology