# Parsimony-distance neighborhoods in tree space

I have the following question about the paper A parsimony-based metric for phylogenetic trees by V. Moulton and T. Wu. In this paper, the authors define a "parsimony-distance" between phylogenetic trees on the same set of taxa. They study how this distance is related to other common distances used in phylogenetics, such as counting tree bisection and reconnection (TBR) moves.

For each notion of distance, we can define the "neighborhood" of a tree as the set of trees which have distance one from the first specified tree. It is claimed in the paper that the parsimony-distance neighborhood contains the TBR-distance neighborhood, for any tree.

Lemma 6.2 states that only caterpillar trees have unit distance to some other tree. This seems to suggest that for any non-caterpillar tree, the parsimony-neighborhood should be empty. However, the TBR-neighborhood of any tree should be non-empty, since it is possible to apply a TBR move and obtain a different tree. Are there some assumptions I am missing about when the parsimony-neighborhood is empty, or when the TBR-neighborhood is contained in the parsimony neighborhood?

Also, when applying the formula in Corollary 6.6 to the non-caterpillar tree on 6 leaves, I am unsure how to apply the formula to give the neighborhood size $$|N_p| = 0$$, which should be implied by Lemma 6.2.

• Another term for "caterpillar tree" is "ladderized tree", the former seems more common in the math community. Apr 12, 2023 at 20:53

The divergence in language makes it difficult to conceptualise and without that it's difficult to approach algebraic abstraction, albeit I've worked on tree space and its landscapes. I suspect I get point 3, but not much more.

1. "Caterpillar tree" is a term in graph theory. If that is the definition used here then every parsimony tree would be a caterpillar tree, there would never be a "non-caterpillar tree". This is because each branch length defines one "step": "parsimony's version of a mutation", so each "step" within the branch could be considered to be a "branch-less node", or else bifurcating node.

Ladderized tree I don't understand that. Maybe Np = 0 means a complete polytomy, i.e. a star tree, but could be a branch length = 0, i.e. genetically identical taxa.

1. The concept for an empty neighborhood ... possibly if all topologies are equally parsimonious this could degenerate into an empty tree neighborhood, again a star tree. What parsimony does is always define a bifurcating tree regardless, over replication all alternative solutions may result collectively in an "empty neighborhood". This might be fine from an algebraic perspective, its weird from algorithm perspective though.

2. When a TBR-neighborhood is equal to a parsimony neighborhood that actually makes sense. I define that as the TBR-neighborhood being "trapped" within the parsimony neighborhood and thats convergence. Here the "step length" has reached its minimum plateau and that tree is the most parsimonious tree ... that makes complete sense. This also makes sense within the context of the paper (I haven't read it - but I can see where they are heading).

What the authors want to do is pick holes in TBR so they want to define the point at which TBR has reached its most parsimonious tree ... I assume they want to show TBR can make errors and their solution is better. Thus they need to define the "end point". At this "end point" they want to show their measure outperforms TBR to reach a lower step size.

Thus they will want to imply that TBR should be replaced with their derivation. Its a nice methodological way to basic (or "fundamental") phylogentics.