On the maximum parsimony distance between phylogenetic trees

DOI10.1007/s00026-015-0298-1zbMath1332.05043arXiv1402.1553OpenAlexW2964179375MaRDI QIDQ259724

Steven Kelk, Mareike Fischer

Publication date: 18 March 2016

Published in: Annals of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

maximum parsimonysubtree prune and regrafttree metric

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Problems related to evolution (92D15) Extremal problems in graph theory (05C35) Distance in graphs (05C12)

Related Items (17)

Sharp upper and lower bounds on a restricted class of convex characters ⋮ Reduction rules for the maximum parsimony distance on phylogenetic trees ⋮ Treewidth distance on phylogenetic trees ⋮ On the complexity of computing MP distance between binary phylogenetic trees ⋮ Statistical inconsistency of maximum parsimony for \(k\)-tuple-site data ⋮ Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance ⋮ Convex Characters, Algorithms, and Matchings ⋮ A near-linear kernel for bounded-state parsimony distance ⋮ Deep kernelization for the tree bisection and reconnection (TBR) distance in phylogenetics ⋮ New reduction rules for the tree bisection and reconnection distance ⋮ Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm ⋮ New Gromov-inspired metrics on phylogenetic tree space ⋮ A note on convex characters, Fibonacci numbers and exponential-time algorithms ⋮ Overlaid species forests ⋮ Reflections on kernelizing and computing unrooted agreement forests ⋮ A Tight Kernel for Computing the Tree Bisection and Reconnection Distance between Two Phylogenetic Trees ⋮ On the Balance of Unrooted Trees

Cites Work

• Unnamed Item
• On agreement forests
• A cluster reduction for computing the subtree distance between phylogenies
• The maximum agreement forest problem: Approximation algorithms and computational experiments
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• Comparison of phylogenetic trees
• The Steiner problem in phylogeny is NP-complete
• Brooks' graph-coloring theorem and the independence number
• Some APX-completeness results for cubic graphs
• On the computational complexity of the rooted subtree prune and regraft distance
• The splits in the neighborhood of a tree
• Fixed-Parameter Algorithms for Maximum Agreement Forests
• Finding a maximum likelihood tree is hard
• A Linear Tree Partitioning Algorithm
• Approximation Algorithms for Nonbinary Agreement Forests
• Subtree transfer operations and their induced metrics on evolutionary trees

This page was built for publication: On the maximum parsimony distance between phylogenetic trees