On unrooted and root-uncertain variants of several well-known phylogenetic network problems

DOI10.1007/s00453-017-0366-5zbMath1410.68178DBLPjournals/algorithmica/IerselKSSB18arXiv1609.00544OpenAlexW2517904087WikidataQ59514355 ScholiaQ59514355MaRDI QIDQ1755726

Leo van Iersel, Leen Stougie, Georgios Stamoulis, Steven Kelk, Olivier Boes

Publication date: 11 January 2019

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

NP-completenessfixed parameter tractabilitybinary treesphylogenetic networksAPX-hardnesskernelization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problems related to evolution (92D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (11)

Non-essential arcs in phylogenetic networks ⋮ Uprooted phylogenetic networks ⋮ Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance ⋮ Orienting undirected phylogenetic networks ⋮ Deep kernelization for the tree bisection and reconnection (TBR) distance in phylogenetics ⋮ A QUBO formulation for the tree containment problem ⋮ New reduction rules for the tree bisection and reconnection distance ⋮ Tree-based unrooted phylogenetic networks ⋮ On the fixed parameter tractability of agreement-based phylogenetic distances ⋮ Treewidth of display graphs: bounds, brambles and applications ⋮ A Tight Kernel for Computing the Tree Bisection and Reconnection Distance between Two Phylogenetic Trees

Uses Software

• rSPR
• SPRSupertrees
• Dendroscope
• tcp_package

Cites Work

• Unnamed Item
• Reticulation-visible networks
• Kernelizations for the hybridization number problem on multiple nonbinary trees
• Fundamentals of parameterized complexity
• Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable
• Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees
• On the fixed parameter tractability of agreement-based phylogenetic distances
• Approximating maximum agreement forest on multiple binary trees
• Computing the minimum number of hybridization events for a consistent evolutionary history
• Seeing the trees and their branches in the network is hard
• Optimization, approximation, and complexity classes
• Locating a tree in a phylogenetic network
• Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
• Bounding the number of hybridisation events for a consistent evolutionary history
• A quadratic kernel for computing the hybridization number of multiple trees
• Fixed-Parameter Algorithms for Maximum Agreement Forests
• Complexity of Single-Layer Routing
• Cycle Killer...Qu'est-ce que c'est? On the Comparative Approximability of Hybridization Number and Directed Feedback Vertex Set
• Subtree transfer operations and their induced metrics on evolutionary trees

This page was built for publication: On unrooted and root-uncertain variants of several well-known phylogenetic network problems