How to swap parts of an unrooted tree

Unrooted trees are conceptually unordered, but sometimes one order is intuitively clearer than another. We may then wish to swap two subtrees to obtain the more intuitively order representation. This looks straightforward, but sometimes it is not, due to the implementation of unrooted trees.

Suppose, you have a clustering that you want to display as an unrooted tree:

lnjtree -h -f 24 vb.clu > vb1.ps

The result looks like this:

This tree would be clearer if you would swap the subtree containing B and C and the subtree containing D and E. You can do this using the -s option with two labels, one from each subtree:

lnjtree -h -f 24 -s B D vb.clu > vb2.ps

And you will get this:

For clarity, the same tree rotated 90 degrees, with the initial tree on the right:


modified tree	initial tree

Only D and E have swapped. This is not what was intended. What went wrong? (Actually, E hasn't swapped, and D swapped with every item except E.)

You need to understand the internal representation of the clustering. Each node, each fork, consists of one parent edge and two daughter edges. Except one node, which doesn't have a parent node, just three daughter nodes. Call this the root node. The tree itself has no root node, but internally, there is, though it hasn't any special status. Any node could be the root node.

Back to the initial tree:

The blue circle is where you want to swap two edges.

When you use the -s option to swap two subtrees, the program will locate the node where those subtrees join, so each subtree contains one of the labels. This node has those two subtrees as daughters.

This could be any node on the path joining the two labels! From B to D, these are three candidate nodes, and apparently the one node found is not the one in the blue circle.

How to solve this?

You start by running the program with the -r option. Then the program will mark the root node with a red dot:

lnjtree -h -f 24 -r vb.clu > vb3.ps

It looks like this:

The edge coming from the red dot is the parent edge of the node in the blue circle. You cannot swap a parent edge and a daughter edge. You can only swap two daughter edges. As you can see, one daughter is the subtree with B and C, and the other is the one with A, F, G, and H. You can swap these subtrees by using the labels B and A:

lnjtree -h -f 24 -s B A vb.clu > vb4.ps

And it will look like this:

Finally, you can use the -a option to rotate the tree, so it will mostly match the initial tree:

lnjtree -h -f 24 -s B A -a 90 vb.clu > vb5.ps

And this is what you'll get:


modified tree	initial tree

Note: you can use the -s option any number of times, to swap more parts of the tree.