[Biopython] Bio.Phylo: midpoint root?

[Eric Talevich]

On Wed, May 30, 2012 at 9:40 AM, Tanya Golubchik <golubchi at stats.ox.ac.uk>wrote:

> Hello,
>
> Does anyone have a quickie method for calculating the midpoint root of a
> given tree?
>
>
It's been on my to-do list. (The first step was adding the keyword argument
'outgroup_branch_length' to root_with_outgroup.) The tree method 'depths'
should also be handy.

The algorithm I had in mind looks like:
1. Take the depths() of each clade under the root.
2. Identify the deepest tip under each clade.
3. Assuming the tree is bifurcating, take the shallower tip as the
"out_tip" and the deeper tip as the "in_tip".
4. If the difference between the depths of "out_tip" and "in_tip" are
greater than the length of the branch connecting the two clades below the
root (tree.clade[0].branch_length + tree.clade[1].branch_length), there's a
possibility that a better out_tip is hiding inside the deeper clade. So,
repeat the operation on tree.clade[1], recursively, until meeting the stop
condition I just described.
5. To identify the midpoint, halve the distance between in_tip and out_tip,
and trace backward from in_tip by that distance to reach the new root.

With multifurcations, the algorithm looks similar, but with more loops.

I too would be delighted to see a better algorithm for this.

-E