Treewidth distance on phylogenetic trees

Kelk, Steven, Stamoulis, Georgios and Wu, Taoyang ORCID: https://orcid.org/0000-0002-2663-2001 (2018) Treewidth distance on phylogenetic trees. Theoretical Computer Science, 731. pp. 99-117. ISSN 0304-3975

Preview

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

Abstract

In this article we study the treewidth of the display graph, an auxiliary graph structure obtained from the fusion of phylogenetic (i.e., evolutionary) trees at their leaves. Earlier work has shown that the treewidth of the display graph is bounded if the trees are in some formal sense topologically similar. Here we further expand upon this relationship. We analyse a number of reduction rules, commonly used in the phylogenetics literature to obtain fixed parameter tractable algorithms. In some cases (the subtree reduction) the reduction rules behave similarly with respect to treewidth, while others (the cluster reduction) behave very differently, and the behaviour of the chain reduction is particularly intriguing because of its link with graph separators and forbidden minors. We also show that the gap between treewidth and Tree Bisection and Reconnect (TBR) distance can be infinitely large, and that unlike, for example, planar graphs the treewidth of the display graph can be as much as linear in its number of vertices. A number of other auxiliary results are given. We conclude with a discussion and list a number of open problems.

Item Type:	Article
Uncontrolled Keywords:	graph theory,phylogenetics,treewidth,algorithmic graph theory,computational biology
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 Centres > Centre for Ecology, Evolution and Conservation Faculty of Science > Research Groups > Data Science and AI
Depositing User:	Pure Connector
Date Deposited:	17 Apr 2018 13:31
Last Modified:	10 Dec 2024 01:31
URI:	https://ueaeprints.uea.ac.uk/id/eprint/66789
DOI:	10.1016/j.tcs.2018.04.004

Downloads

Actions (login required)

View Item