Print Email Facebook Twitter Treewidth based algorithms for Tree Containment in phylogenetics Title Treewidth based algorithms for Tree Containment in phylogenetics Author Huijsman, Robbert (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Discrete Mathematics and Optimization) Contributor van Iersel, L.J.J. (mentor) Jones, M.E.L. (mentor) de Weerdt, M.M. (graduation committee) Degree granting institution Delft University of Technology Programme Applied Mathematics Date 2023-01-31 Abstract 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. Subject Phylogenetic networktree containmenttree-widthfixed-parameter tractabilityPhylogenetic treedisplay graphembedding To reference this document use: http://resolver.tudelft.nl/uuid:3906ebda-d667-4d3e-8bee-3f1f4df78387 Part of collection Student theses Document type master thesis Rights © 2023 Robbert Huijsman Files PDF Master_Thesis_Robbert_Hui ... 1_2023.pdf 898.72 KB Close viewer /islandora/object/uuid:3906ebda-d667-4d3e-8bee-3f1f4df78387/datastream/OBJ/view