[Bioperl-l] Rooting a tree

[Iain Wallace]

Hi all,

I am trying to root a tree so that the leaf distribution is balanced. I
think the technical term is a "perfect binary tree". Basically it means
that if I go down one level from the root, each of the two nodes contain
half the number of leaves. If I go down another level each of the four
nodes contain a quarter of the leaves. 

I am able to do this manually by creating an outgroup in the NJPlot
program, so that visually it looks balanced, and then save the rooted
tree. 

I tried to automate the process by using bioperl, and the reroot
function at each internal node to find the best place to put the root
node. This didn't work for me because, when I use the reroot function, I
get 3 descendants instead of two. Does anyone know how to reroot the
tree so that there is only two descendants? 

If anyone has any ideas about how i could accomplish this, i would
really appreciate it....

Here is my code:


#!/usr/bin/perl -w
use strict;
                                                                                                                                                             
use Bio::TreeIO;
use Bio::SeqIO;
my $treefile=$ARGV[0];
                                                                                                                                                             
my $treeio = new Bio::TreeIO( -file => $treefile) ;
my $tree = $treeio->next_tree or die "No Tree\n";
                                                                                                                                                             
my $rootnode = $tree->get_root_node();
my $total;
my %data;
                                                                                                                                                             
for my $treenodes ( $tree->get_nodes) {
                                                                                                                                                             
undef %data;
my %data;
                                                                                                                                                             
if (( !$treenodes->is_Leaf ) && ($treenodes!= $rootnode)) {
        #reroot tree
        print "rerooting\n";
        $tree->reroot($treenodes);
                                                                                                                                                             
        for my $node ( $tree->get_leaf_nodes ) {
        &inc_ancestor($node,\%data);  # This assigns a count for the
number of leaves each node has
        $total++;
        my $leafid=$node->internal_id;
        $data{$leafid}=1;
        }
                                                                                                                                                             
        print "the descendents\n ";
        for my $descendentnode ( $treenodes->each_Descendent()){
        my $leafid=$descendentnode->internal_id;
        print " There are ",$data{$leafid}," leaves here\n";;
        }
                                                                                                                                                             
        $tree->reroot($rootnode);
}
}
                                                                                                                                                                                                                                                                                                                          
sub inc_ancestor {
    my $node = shift;
    my $data = shift;
   return unless defined $node && defined $node->ancestor;
    my $id = $node->ancestor->internal_id;
    $data->{$id}++; # This increments the count for the node..
    &inc_ancestor($node->ancestor,$data);
}