Reduction rules for the maximum parsimony distance on phylogenetic trees
From MaRDI portal
Publication:306268
DOI10.1016/J.TCS.2016.07.010zbMATH Open1348.68068arXiv1512.07459OpenAlexW2964224095MaRDI QIDQ306268FDOQ306268
Authors: Steven Kelk, Mareike Fischer, Vincent Moulton, Taoyang Wu 
Publication date: 31 August 2016
Published in: Theoretical Computer Science (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1512.07459
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
Problems related to evolution (92D15) Trees (05C05) Analysis of algorithms and problem complexity (68Q25)
Cites Work
- A parsimony-based metric for phylogenetic trees
- Graph theory
- Fundamentals of parameterized complexity
- Subtree transfer operations and their induced metrics on evolutionary trees
- On the maximum parsimony distance between phylogenetic trees
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Easy problems for tree-decomposable graphs
- Title not available (Why is that?)
- Graph minors. V. Excluding a planar graph
- Quickly excluding a planar graph
- Phylogenetic incongruence through the lens of monadic second order logic
- Excluded grid theorem: improved and simplified
- On low treewidth graphs and supertrees
- Compatibility, incompatibility, tree-width, and forbidden phylogenetic minors
- Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees
- Compatibility of unrooted phylogenetic trees is FPT
- Treewidth computations. I: Upper bounds
Cited In (12)
- On the maximum parsimony distance between phylogenetic trees
- A near-linear kernel for bounded-state parsimony distance
- Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm
- 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
Uses Software
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)
