Different reduction rules for the Maximum Parsimony distance on phylogenetic trees

Different reduction rules for the Maximum Parsimony distance on phylogenetic trees

Deen, Elise (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Optimization)

Jones, M.E.L. (mentor)
van Iersel, L.J.J. (mentor)
Dubbeldam, J.L.A. (graduation committee)

Delft University of Technology

Applied Mathematics

2021-07-06

In this report, the bounded Maximum Parsimony distance will be considered when
applying three different reduction rules. The distance is a measure on how dissimilar two trees are and is calculated based on the number of mutations that occur when looking at heritable traits. The first rule considered, is the chain reduction. For this rule, it is proven that the bounded MP distance is preserved after applying this rule. This is done by adapting the proof from Steven Kelk et al. [10]. For the second rule considered, the generalized subtree reduction, it is also proven that the bounded MP distance is preserved after applying this reduction. Again, this is done by adapting the proof in the paper by Steven Kelk et al. [10]. Then, at last, we looked at a new reduction rule for the TBR distance, introduced by Steven Kelk and Simone Linz [12], the (2,1,2)-reduction. In this report, it is shown with help of a counterexample that this rule does not necessarily reduce the distance with one like it is the case for the TBR distance. However, it can be concluded that the distance is either preserved or reduced with one.

Phylogenetic trees
Maximum parsimony distance
Reduction rules

http://resolver.tudelft.nl/uuid:0deb0697-bc1d-4cd9-96ed-f516872f24b0

Student theses

bachelor thesis

© 2021 Elise Deen