Reduction rules for the maximum parsimony distance on phylogenetic trees
From MaRDI portal
(Redirected from Publication:306268)
Abstract: In phylogenetics, distances are often used to measure the incongruence between a pair of phylogenetic trees that are reconstructed by different methods or using different regions of genome. Motivated by the maximum parsimony principle in tree inference, we recently introduced the maximum parsimony (MP) distance, which enjoys various attractive properties due to its connection with several other well-known tree distances, such as TBR and SPR. Here we show that computing the MP distance between two trees, a NP-hard problem in general, is fixed parameter tractable in terms of the TBR distance between the tree pair. Our approach is based on two reduction rules--the chain reduction and the subtree reduction--that are widely used in computing TBR and SPR distances. More precisely, we show that reducing chains to length 4 (but not shorter) preserves the MP distance. In addition, we describe a generalization of the subtree reduction which allows the pendant subtrees to be rooted in different places, and show that this still preserves the MP distance. On a slightly different note we also show that Monadic Second Order Logic (MSOL), posited over an auxiliary graph structure known as the display graph (obtained by merging the two trees at their leaves), can be used to obtain an alternative proof that computation of MP distance is fixed parameter tractable in terms of TBR-distance. We conclude with an extended discussion in which we focus on similarities and differences between MP distance and TBR distance and present a number of open problems. One particularly intriguing question, emerging from the MSOL formulation, is whether two trees with bounded MP distance induce display graphs of bounded treewidth.
Recommendations
- On the maximum parsimony distance between phylogenetic trees
- On the complexity of computing MP distance between binary phylogenetic trees
- Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm
- Phylogenetic incongruence through the lens of monadic second order logic
- Treewidth distance on phylogenetic trees
Cites work
- scientific article; zbMATH DE number 566078 (Why is no real title available?)
- A parsimony-based metric for phylogenetic trees
- Compatibility of unrooted phylogenetic trees is FPT
- Compatibility, incompatibility, tree-width, and forbidden phylogenetic minors
- Easy problems for tree-decomposable graphs
- Excluded grid theorem: improved and simplified
- Fundamentals of parameterized complexity
- Graph minors. V. Excluding a planar graph
- Graph theory
- On low treewidth graphs and supertrees
- On the maximum parsimony distance between phylogenetic trees
- Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees
- Phylogenetic incongruence through the lens of monadic second order logic
- Quickly excluding a planar graph
- Subtree transfer operations and their induced metrics on evolutionary trees
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Treewidth computations. I: Upper bounds
Cited in
(12)- On the maximum parsimony distance between phylogenetic trees
- Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm
- A near-linear kernel for bounded-state parsimony distance
- Treewidth distance on phylogenetic trees
- A note on convex characters, Fibonacci numbers and exponential-time algorithms
- On the complexity of computing MP distance between binary phylogenetic trees
- A tight kernel for computing the tree bisection and reconnection distance between two phylogenetic trees
- Reflections on kernelizing and computing unrooted agreement forests
- New reduction rules for the tree bisection and reconnection distance
- On the fixed parameter tractability of agreement-based phylogenetic distances
- On compatibility and incompatibility of collections of unrooted phylogenetic trees
- Phylogenetic incongruence through the lens of monadic second order logic
This page was built for publication: Reduction rules for the maximum parsimony distance on phylogenetic trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q306268)
