Tail move rearrangement algorithm for rooted binary phylogenetic networks

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.