Treewidth based algorithms for Tree Containment in phylogenetics

Treewidth based algorithms for Tree Containment in phylogenetics

Huijsman, Robbert (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Discrete Mathematics and Optimization)

van Iersel, L.J.J. (mentor)
Jones, M.E.L. (mentor)
de Weerdt, M.M. (graduation committee)

Delft University of Technology

Applied Mathematics

2023-01-31

TreeContainment is a well-known problem within phylogenetics, which asks whether a binary phylogenetic tree is embedded in a binary phylogenetic network. For this problem, Jones, Weller and van Iersel (2022) have created an algorithm that uses dynamic programming on tree-decompositions to achieve a running time that is exponential in the tree-width parameter instead of in the number of reticulations. However, due to the implicit formulations of two crucial steps in this algorithm, this running time cannot be achieved in practice without finding ways to generate the required structures explicitly. This paper provides two new sub-algorithms that can do that. To further improve the performance of the algorithm, I introduce a number of criteria and other methods that can be used to reduce the number of structures generated. Additionally, I describe a way to manipulate the nice tree-decompositions to create a more favorable order of bags for the dynamic programming. These sub-algorithms and improvements are used by two new algorithms TWITCH and PITCH, whose implementations are compared to a brute force algorithm and a new branching cherry-picking algorithm named BOTCH. The latter has an FPT running time that is exponential in the number of vertices that have only reticulations as children. The comparisons show that the implementations of the dynamic programming algorithms TWITCH and PITCH are slower in practice than the brute force algorithm, despite their numerous improvements. Of the four new implementations, BOTCH has the best test results and it is shown to be fast in practice.

Phylogenetic network
tree containment
tree-width
fixed-parameter tractability
Phylogenetic tree
display graph
embedding

http://resolver.tudelft.nl/uuid:3906ebda-d667-4d3e-8bee-3f1f4df78387

Student theses

master thesis

© 2023 Robbert Huijsman