On the fixed parameter tractability of agreement-based phylogenetic distances

DOI10.1007/s00285-016-1023-3zbMath1354.05129OpenAlexW2407777965WikidataQ50639269 ScholiaQ50639269MaRDI QIDQ504072

Magnus Bordewich, Nihan Tokac, Celine Scornavacca, Mathias Weller

Publication date: 25 January 2017

Published in: Journal of Mathematical Biology (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/18815/1/18815.pdf

zbMATH Keywords

phylogenetic networkhybridization numberSPR distancecluster reductionTBR distance

Mathematics Subject Classification ID

Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Computational methods for problems pertaining to biology (92-08) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Treewidth distance on phylogenetic trees, The agreement distance of unrooted phylogenetic networks, New reduction rules for the tree bisection and reconnection distance, Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm, Scanning Phylogenetic Networks Is NP-hard, On unrooted and root-uncertain variants of several well-known phylogenetic network problems, Exploring the tiers of rooted phylogenetic network space using tail moves, Treewidth of display graphs: bounds, brambles and applications, Reflections on kernelizing and computing unrooted agreement forests, A Tight Kernel for Computing the Tree Bisection and Reconnection Distance between Two Phylogenetic Trees, Computing Maximum Agreement Forests without Cluster Partitioning is Folly

Cites Work

• Unnamed Item
• Fixed-parameter and approximation algorithms for maximum agreement forests of multifurcating trees
• A cluster reduction for computing the subtree distance between phylogenies
• Inferring a level-1 phylogenetic network from a dense set of rooted triplets
• Computing the minimum number of hybridization events for a consistent evolutionary history
• On unrooted and root-uncertain variants of several well-known phylogenetic network problems
• On the computational complexity of the rooted subtree prune and regraft distance
• When two trees go to war
• Faster exact computation of rSPR distance
• Bounding the number of hybridisation events for a consistent evolutionary history
• Fixed-Parameter Algorithms for Maximum Agreement Forests
• Parameterized and Approximation Algorithms for the MAF Problem in Multifurcating Trees
• Fast Algorithms for Finding Nearest Common Ancestors
• Subtree transfer operations and their induced metrics on evolutionary trees
• On the complexity of comparing evolutionary trees