2014/02/07 by Mareike Fischer, Steven Kelk, Fischer, Mareike +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Mathematics · #Combinatorics (math.CO) #FOS: Biological sciences #FOS: Mathematics #Populations and Evolution (q-bio.PE) #math.CO #q-bio.PE
paper · pdf · doi:10.48550/arxiv.1402.1553
30 pages, 6 figures
arxiv created 2014/02/07 · arxiv updated 2014/02/10
Within the field of phylogenetics there is great interest in distance measures to quantify the dissimilarity of two trees. Here, based on an idea of Bruen and Bryant, we propose and analyze a new distance measure: the Maximum Parsimony (MP) distance. This is based on the difference of the parsimony scores of a single character on both trees under consideration, and the goal is to find the character which maximizes this difference. In this article we show that this new distance is a metric and provides a lower bound to the well-known Subtree Prune and Regraft (SPR) distance. We also show that to compute the MP distance it is sufficient to consider only characters that are convex on one of the trees, and prove several additional structural properties of the distance. On the complexity side, we prove that calculating the MP distance is in general NP-hard, and identify an interesting island of tractability in which the distance can be calculated in polynomial time.