Counting cherry-picking sequences in phylogenetic trees
M.A. Dee (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Yukihiro Murakami – Mentor (TU Delft - Discrete Mathematics and Optimization)
Wolter Groenevelt – Graduation committee member (TU Delft - Analysis)
More Info
expand_more
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.
Abstract
Phylogenetic trees are used to represent evolutionary history of, among others, species, genes or languages. Phylogenetic trees can be reduced by so called cherry-picking sequences. In this thesis we take a closer look at cherry-picking sequences to obtain a more fundamental understanding on the structure and behaviour of these sequences on phylogenetic trees. For binary rooted trees, that is trees with a root, outdegree-2 tree nodes, and a set of leaves, we count the number of sequences that can reduce such trees. Furthermore, we try to find the number of sequences of a given tree that is needed to reduce all subtrees of a given tree. Thus, an enumeration problem and an optimization problem are considered in this thesis. For both problems, we first look for results on simply structured trees, such as caterpillars and double caterpillars. Lastly, we try to expand these results to general binary trees in order to find the answers to the two problems.