Tail move rearrangement algorithm for rooted binary phylogenetic networks
S. Husanović (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Leo van Van Iersel – Mentor (TU Delft - Discrete Mathematics and Optimization)
Remie Janssen – Graduation committee member (TU Delft - Discrete Mathematics and Optimization)
MB Van Gijzen – Coach (TU Delft - Numerical 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
A common tool for exploring the space of phylogenetic networks is applying rearrangement moves, such as tail moves. Recently, it has been shown by Janssen et al that, given a rooted binary phylogenetic network, it is possible to generate any other alternative network, using only tail moves. The aim of this report is to translate this theory into a tail move rearrangement algorithm, that calculates a sequence of tail moves necessary to transform one network into another, and thus determines an upper bound on the tail distance between the two networks. Furthermore, the goal is to assess the quality of the upper bound as determined by the algorithm, and to try to improve it. To this end, four improvement proposals were made and tested. A comparison was made with the true tail distance for a range of 385 combinations of small networks. It was shown that the original algorithm gives adequate results. However, it was concluded that it generally cannot be predicted which version of the algorithm will perform best. In the case of small and relatively simple networks, the fourth improvement provides the best results.