Reduction rules for the maximum parsimony distance on phylogenetic trees

Kelk, Steven, Fischer, Mareike, Moulton, Vincent ORCID: https://orcid.org/0000-0001-9371-6435 and Wu, Taoyang ORCID: https://orcid.org/0000-0002-2663-2001 (2016) Reduction rules for the maximum parsimony distance on phylogenetic trees. Theoretical Computer Science, 646. pp. 1-15. ISSN 0304-3975

Preview

PDF (Manuscript) - Accepted Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (699kB) | Preview

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.

Item Type:	Article
Uncontrolled Keywords:	phylogenetics,parsimony,fixed parameter tractability,chain,incongruence,treewidth
Faculty \ School:	Faculty of Science > School of Computing Sciences
UEA Research Groups:	Faculty of Science > Research Groups > Computational Biology > Phylogenetics (former - to 2018) Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Computational Biology > Computational biology of RNA (former - to 2018) Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre Faculty of Science > Research Centres > Centre for Ecology, Evolution and Conservation Faculty of Science > Research Groups > Data Science and AI
Depositing User:	Pure Connector
Date Deposited:	24 Sep 2016 00:02
Last Modified:	10 Dec 2024 01:27
URI:	https://ueaeprints.uea.ac.uk/id/eprint/59778
DOI:	10.1016/j.tcs.2016.07.010

Downloads

Actions (login required)

View Item