Tree-child Network Containment

Bachelor thesis (2019)

Authors

R.V. Huijsman Electrical Engineering, Mathematics and Computer Science

Contributors

L.J.J. van Iersel Discrete Mathematics and Optimization - EEMCS (mentor)
Yukihiro Murakami Discrete Mathematics and Optimization - EEMCS (mentor)
R. Janssen Discrete Mathematics and Optimization - EEMCS (mentor)
B. van den Dries Analysis - EEMCS (graduation committee member)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Copyright: © 2019 Robbert Huijsman
More Info
expand_more

Published Date

24-07-2019

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

Interest in phylogenetic trees for histories of species and DNA has spawned many problems, one of which is TreeContainment; a problem that asks whether a tree is contained within a network. The TreeContainment problem is proven to be NP-hard for general trees and networks, however it is solvable in polynomial time for networks that meet the tree-child restriction. An algorithm to solve TreeContainment for binary tree-child networks has been created previously with quadratic running time (van Iersel, Semple, Steel, 2010). Janssen and Murakami have recently created a new algorithm that solves a larger problem NetworkContainment, for semi-binary tree-child networks (Janssen, Murakami, 2019). This new algorithm uses tree-child sequences introduced by Linz and Semple, but there has not been an implementation of it until now. In this paper I show an implementation (using Python) of this algorithm, in which I have made a modification that increases its speed on networks with large indegrees. Furthermore I have proven in this paper that the output of this algorithm remains correct under this modification, and that the running time of the modified algorithm is now linear without requiring a constant maximum indegree at all.

Files

Tree_child_Network_Containment... (pdf)
(pdf | 0.606 Mb)
Unknown license