Bootstrap, root, reroot...

[Tristan Lefebure-2]

Hello,

I have been bumping into problems while rerooting trees that
contained bootstrap scores. Basically, after re-rooting the
tree, some scores end-up at the wrong place (i.e. node) and
some nodes lose their score. I found this thread from Bank
Beszter, back in 2007, that exactly explains the same
problems:

http://lists.open-bio.org/pipermail/bioperl-l/2007-
May/025599.html

I attach a script that reproduces the bug and implements the
fix that Bank described (at least this is my understanding,
and it works on this example):


#! /usr/bin/perl

use strict;
use warnings;
use Bio::TreeIO;


my $in = Bio::TreeIO->new(-format => 'newick',
    -fh => \*DATA,
    -internal_node_id => 'bootstrap');
   
my $out = Bio::TreeIO->new(-format => 'newick', -file =>
">out.tree");

while( my $t = $in->next_tree ){
    my $old_root = $t->get_root_node();
    my ($b) = $t->find_node(-id =>"B");
    my $b_anc = $b->ancestor;
    $out->write_tree($t);

        #reroot with B -> wrong, and the tree is kind of weird
    $t->reroot($b);
    $out->write_tree($t);

        #reroot with B ancestor -> wrong
    $t->reroot($b_anc);
    $out->write_tree($t);
   
    #a fix, following Bank Beszteri description
    my $node = $old_root;
    while (my $anc_node = $node->ancestor) {
         $node->bootstrap($anc_node->bootstrap());
         $anc_node->bootstrap('');
         $node = $anc_node;
    }
    $out->write_tree($t); #->good this time
}


__DATA__
(A:52,(B:46,C:50)68:11,D:70);


Here is the output:

(A:52,(B:46,C:50)68:11,D:70);
((C:50,(A:52,D:70):11)68:46)B;
(B:46,C:50,(A:52,D:70):11)68;
(B:46,C:50,(A:52,D:70)68:11);


Tree #2 and #3 have the score 68 moved to the wrong node,
while tree #4 is OK. (BTW tree #2 is really weird, except if
B, is the real ancestor (a fossil ?), it really does not
make much sense to me).

My understanding here is that the problem is linked to the
well-known difficulty to differentiate node from branch
labels in newick trees. Bootstrap scores are branch
attributes not node attributes, but since Bio::TreeI has no
branch/edge/bipartition object they are attached to a node,
and in fact reflects the bootstrap score of the ancestral
branch leading to that node. Troubles naturally come when
you are dealing with an unrooted tree or reroot a tree: a
child can become an ancestor, and, if the bootstrap scores
is not moved from the old child to the new child, it will
end up attached at the wrong place (i.e. wrong node).

I see several fix to that:

1- incorporate Bank's fix into the root() method. I.e. if
there is bootstrap score, after re-rooting, the one on the
old to new ancestor path, should be moved to the right node.

2- Modify the way trees are stored in bioperl to incorporate
branch/edge/bipartition object, and move the bootstrap
scores to them. That won't be easy and will break many
things...


What do you think?

--Tristan







_______________________________________________
Bioperl-l mailing list
Bioperl-l@...
http://lists.open-bio.org/mailman/listinfo/bioperl-l

[Mark A. Jensen]

Hi Tristan--
Would you enter this in bugzilla? I did an overhaul of the root/reroot a while
back, and maybe you're running into some stuff I need to check out.
Thanks a lot-
Mark
----- Original Message -----
From: "Tristan Lefebure" <tristan.lefebure@...>
To: "BioPerl List" <bioperl-l@...>
Sent: Thursday, July 09, 2009 11:50 AM
Subject: [Bioperl-l] Bootstrap, root, reroot...

> Hello,
>
> I have been bumping into problems while rerooting trees that
> contained bootstrap scores. Basically, after re-rooting the
> tree, some scores end-up at the wrong place (i.e. node) and
> some nodes lose their score. I found this thread from Bank
> Beszter, back in 2007, that exactly explains the same
> problems:
>
> http://lists.open-bio.org/pipermail/bioperl-l/2007-
> May/025599.html
>
> I attach a script that reproduces the bug and implements the
> fix that Bank described (at least this is my understanding,
> and it works on this example):
>
>
> #! /usr/bin/perl
>
> use strict;
> use warnings;
> use Bio::TreeIO;
>
>
> my $in = Bio::TreeIO->new(-format => 'newick',
>    -fh => \*DATA,
>    -internal_node_id => 'bootstrap');
>    
> my $out = Bio::TreeIO->new(-format => 'newick', -file =>
> ">out.tree");
>
> while( my $t = $in->next_tree ){
>    my $old_root = $t->get_root_node();
>    my ($b) = $t->find_node(-id =>"B");
>    my $b_anc = $b->ancestor;
>    $out->write_tree($t);
>
> #reroot with B -> wrong, and the tree is kind of weird
>    $t->reroot($b);
>    $out->write_tree($t);
>
> #reroot with B ancestor -> wrong
>    $t->reroot($b_anc);
>    $out->write_tree($t);
>    
>    #a fix, following Bank Beszteri description
>    my $node = $old_root;
>    while (my $anc_node = $node->ancestor) {
> $node->bootstrap($anc_node->bootstrap());
> $anc_node->bootstrap('');
> $node = $anc_node;
>    }
>    $out->write_tree($t); #->good this time
> }
>
>
> __DATA__
> (A:52,(B:46,C:50)68:11,D:70);
>
>
> Here is the output:
>
> (A:52,(B:46,C:50)68:11,D:70);
> ((C:50,(A:52,D:70):11)68:46)B;
> (B:46,C:50,(A:52,D:70):11)68;
> (B:46,C:50,(A:52,D:70)68:11);
>
>
> Tree #2 and #3 have the score 68 moved to the wrong node,
> while tree #4 is OK. (BTW tree #2 is really weird, except if
> B, is the real ancestor (a fossil ?), it really does not
> make much sense to me).
>
> My understanding here is that the problem is linked to the
> well-known difficulty to differentiate node from branch
> labels in newick trees. Bootstrap scores are branch
> attributes not node attributes, but since Bio::TreeI has no
> branch/edge/bipartition object they are attached to a node,
> and in fact reflects the bootstrap score of the ancestral
> branch leading to that node. Troubles naturally come when
> you are dealing with an unrooted tree or reroot a tree: a
> child can become an ancestor, and, if the bootstrap scores
> is not moved from the old child to the new child, it will
> end up attached at the wrong place (i.e. wrong node).
>
> I see several fix to that:
>
> 1- incorporate Bank's fix into the root() method. I.e. if
> there is bootstrap score, after re-rooting, the one on the
> old to new ancestor path, should be moved to the right node.
>
> 2- Modify the way trees are stored in bioperl to incorporate
> branch/edge/bipartition object, and move the bootstrap
> scores to them. That won't be easy and will break many
> things...
>
>
> What do you think?
>
> --Tristan
>
>
>
>
>
>
>
> _______________________________________________
> Bioperl-l mailing list
> Bioperl-l@...
> http://lists.open-bio.org/mailman/listinfo/bioperl-l
>
>

_______________________________________________
Bioperl-l mailing list
Bioperl-l@...
http://lists.open-bio.org/mailman/listinfo/bioperl-l

[Tristan Lefebure-2]

Done. bug #2877.
-Tristan

On Thursday 09 July 2009 14:02:01 Mark A. Jensen wrote:

> Hi Tristan--
> Would you enter this in bugzilla? I did an overhaul of
> the root/reroot a while back, and maybe you're running
> into some stuff I need to check out. Thanks a lot-
> Mark
> ----- Original Message -----
> From: "Tristan Lefebure" <tristan.lefebure@...>
> To: "BioPerl List" <bioperl-l@...>
> Sent: Thursday, July 09, 2009 11:50 AM
> Subject: [Bioperl-l] Bootstrap, root, reroot...
>
> > Hello,
> >
> > I have been bumping into problems while rerooting trees
> > that contained bootstrap scores. Basically, after
> > re-rooting the tree, some scores end-up at the wrong
> > place (i.e. node) and some nodes lose their score. I
> > found this thread from Bank Beszter, back in 2007, that
> > exactly explains the same problems:
> >
> > http://lists.open-bio.org/pipermail/bioperl-l/2007-
> > May/025599.html
> >
> > I attach a script that reproduces the bug and
> > implements the fix that Bank described (at least this
> > is my understanding, and it works on this example):
> >
> >
> > #! /usr/bin/perl
> >
> > use strict;
> > use warnings;
> > use Bio::TreeIO;
> >
> >
> > my $in = Bio::TreeIO->new(-format => 'newick',
> >    -fh => \*DATA,
> >    -internal_node_id => 'bootstrap');
> >
> > my $out = Bio::TreeIO->new(-format => 'newick', -file
> > => ">out.tree");
> >
> > while( my $t = $in->next_tree ){
> >    my $old_root = $t->get_root_node();
> >    my ($b) = $t->find_node(-id =>"B");
> >    my $b_anc = $b->ancestor;
> >    $out->write_tree($t);
> >
> > #reroot with B -> wrong, and the tree is kind of weird
> >    $t->reroot($b);
> >    $out->write_tree($t);
> >
> > #reroot with B ancestor -> wrong
> >    $t->reroot($b_anc);
> >    $out->write_tree($t);
> >
> >    #a fix, following Bank Beszteri description
> >    my $node = $old_root;
> >    while (my $anc_node = $node->ancestor) {
> > $node->bootstrap($anc_node->bootstrap());
> > $anc_node->bootstrap('');
> > $node = $anc_node;
> >    }
> >    $out->write_tree($t); #->good this time
> > }
> >
> >
> > __DATA__
> > (A:52,(B:46,C:50)68:11,D:70);
> >
> >
> > Here is the output:
> >
> > (A:52,(B:46,C:50)68:11,D:70);
> > ((C:50,(A:52,D:70):11)68:46)B;
> > (B:46,C:50,(A:52,D:70):11)68;
> > (B:46,C:50,(A:52,D:70)68:11);
> >
> >
> > Tree #2 and #3 have the score 68 moved to the wrong
> > node, while tree #4 is OK. (BTW tree #2 is really
> > weird, except if B, is the real ancestor (a fossil ?),
> > it really does not make much sense to me).
> >
> > My understanding here is that the problem is linked to
> > the well-known difficulty to differentiate node from
> > branch labels in newick trees. Bootstrap scores are
> > branch attributes not node attributes, but since
> > Bio::TreeI has no branch/edge/bipartition object they
> > are attached to a node, and in fact reflects the
> > bootstrap score of the ancestral branch leading to that
> > node. Troubles naturally come when you are dealing with
> > an unrooted tree or reroot a tree: a child can become
> > an ancestor, and, if the bootstrap scores is not moved
> > from the old child to the new child, it will end up
> > attached at the wrong place (i.e. wrong node).
> >
> > I see several fix to that:
> >
> > 1- incorporate Bank's fix into the root() method. I.e.
> > if there is bootstrap score, after re-rooting, the one
> > on the old to new ancestor path, should be moved to the
> > right node.
> >
> > 2- Modify the way trees are stored in bioperl to
> > incorporate branch/edge/bipartition object, and move
> > the bootstrap scores to them. That won't be easy and
> > will break many things...
> >
> >
> > What do you think?
> >
> > --Tristan
> >
> >
> >
> >
> >
> >
> >
> > _______________________________________________
> > Bioperl-l mailing list
> > Bioperl-l@...
> > http://lists.open-bio.org/mailman/listinfo/bioperl-l

_______________________________________________
Bioperl-l mailing list
Bioperl-l@...
http://lists.open-bio.org/mailman/listinfo/bioperl-l

[Tristan Lefebure-2]

I just add a quick look at the reroot() function of TreeFunctionsI, and it
looks like that what should be done for the bootstrap scores is what is
already done for the branch lengths. See this loop starting line 954:

    # reverse the ancestor & children pointers
    my $former_anc = $tmp_node->ancestor;
    my @path_from_oldroot = ($self->get_lineage_nodes($tmp_node),
$tmp_node);
    for (my $i = 0; $i < @path_from_oldroot - 1; $i++) {
        my $current = $path_from_oldroot[$i];
        my $next = $path_from_oldroot[$i + 1];
        $current->remove_Descendent($next);
        $current->branch_length($next->branch_length);
        $next->add_Descendent($current);
    }

 It makes sense to me to treat bootstrap and branch lenght in a similar way:
the branch lengths are stored inside the node object, but as the bootstrap,
they really are branch attributes... Nope?

-Tristan

On Thu, Jul 9, 2009 at 2:30 PM, Tristan Lefebure <tristan.lefebure@...
> wrote:

> Done. bug #2877.
> -Tristan
>
> On Thursday 09 July 2009 14:02:01 Mark A. Jensen wrote:
> > Hi Tristan--
> > Would you enter this in bugzilla? I did an overhaul of
> > the root/reroot a while back, and maybe you're running
> > into some stuff I need to check out. Thanks a lot-
> > Mark
> > ----- Original Message -----
> > From: "Tristan Lefebure" <tristan.lefebure@...>
> > To: "BioPerl List" <bioperl-l@...>
> > Sent: Thursday, July 09, 2009 11:50 AM
> > Subject: [Bioperl-l] Bootstrap, root, reroot...
> >
> > > Hello,
> > >
> > > I have been bumping into problems while rerooting trees
> > > that contained bootstrap scores. Basically, after
> > > re-rooting the tree, some scores end-up at the wrong
> > > place (i.e. node) and some nodes lose their score. I
> > > found this thread from Bank Beszter, back in 2007, that
> > > exactly explains the same problems:
> > >
> > > http://lists.open-bio.org/pipermail/bioperl-l/2007-
> > > May/025599.html
> > >
> > > I attach a script that reproduces the bug and
> > > implements the fix that Bank described (at least this
> > > is my understanding, and it works on this example):
> > >
> > >
> > > #! /usr/bin/perl
> > >
> > > use strict;
> > > use warnings;
> > > use Bio::TreeIO;
> > >
> > >
> > > my $in = Bio::TreeIO->new(-format => 'newick',
> > >    -fh => \*DATA,
> > >    -internal_node_id => 'bootstrap');
> > >
> > > my $out = Bio::TreeIO->new(-format => 'newick', -file
> > > => ">out.tree");
> > >
> > > while( my $t = $in->next_tree ){
> > >    my $old_root = $t->get_root_node();
> > >    my ($b) = $t->find_node(-id =>"B");
> > >    my $b_anc = $b->ancestor;
> > >    $out->write_tree($t);
> > >
> > > #reroot with B -> wrong, and the tree is kind of weird
> > >    $t->reroot($b);
> > >    $out->write_tree($t);
> > >
> > > #reroot with B ancestor -> wrong
> > >    $t->reroot($b_anc);
> > >    $out->write_tree($t);
> > >
> > >    #a fix, following Bank Beszteri description
> > >    my $node = $old_root;
> > >    while (my $anc_node = $node->ancestor) {
> > > $node->bootstrap($anc_node->bootstrap());
> > > $anc_node->bootstrap('');
> > > $node = $anc_node;
> > >    }
> > >    $out->write_tree($t); #->good this time
> > > }
> > >
> > >
> > > __DATA__
> > > (A:52,(B:46,C:50)68:11,D:70);
> > >
> > >
> > > Here is the output:
> > >
> > > (A:52,(B:46,C:50)68:11,D:70);
> > > ((C:50,(A:52,D:70):11)68:46)B;
> > > (B:46,C:50,(A:52,D:70):11)68;
> > > (B:46,C:50,(A:52,D:70)68:11);
> > >
> > >
> > > Tree #2 and #3 have the score 68 moved to the wrong
> > > node, while tree #4 is OK. (BTW tree #2 is really
> > > weird, except if B, is the real ancestor (a fossil ?),
> > > it really does not make much sense to me).
> > >
> > > My understanding here is that the problem is linked to
> > > the well-known difficulty to differentiate node from
> > > branch labels in newick trees. Bootstrap scores are
> > > branch attributes not node attributes, but since
> > > Bio::TreeI has no branch/edge/bipartition object they
> > > are attached to a node, and in fact reflects the
> > > bootstrap score of the ancestral branch leading to that
> > > node. Troubles naturally come when you are dealing with
> > > an unrooted tree or reroot a tree: a child can become
> > > an ancestor, and, if the bootstrap scores is not moved
> > > from the old child to the new child, it will end up
> > > attached at the wrong place (i.e. wrong node).
> > >
> > > I see several fix to that:
> > >
> > > 1- incorporate Bank's fix into the root() method. I.e.
> > > if there is bootstrap score, after re-rooting, the one
> > > on the old to new ancestor path, should be moved to the
> > > right node.
> > >
> > > 2- Modify the way trees are stored in bioperl to
> > > incorporate branch/edge/bipartition object, and move
> > > the bootstrap scores to them. That won't be easy and
> > > will break many things...
> > >
> > >
> > > What do you think?
> > >
> > > --Tristan
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > > _______________________________________________
> > > Bioperl-l mailing list
> > > Bioperl-l@...
> > > http://lists.open-bio.org/mailman/listinfo/bioperl-l
>
>
>

_______________________________________________
Bioperl-l mailing list
Bioperl-l@...
http://lists.open-bio.org/mailman/listinfo/bioperl-l

[Aidan Budd]

On Thu, 9 Jul 2009, Tristan Lefebure wrote:

> ...
>
> My understanding here is that the problem is linked to the
> well-known difficulty to differentiate node from branch
> labels in newick trees. Bootstrap scores are branch
> attributes not node attributes, but since Bio::TreeI has no
> branch/edge/bipartition object they are attached to a node,
> and in fact reflects the bootstrap score of the ancestral
> branch leading to that node. Troubles naturally come when
> you are dealing with an unrooted tree or reroot a tree: a
> child can become an ancestor, and, if the bootstrap scores
> is not moved from the old child to the new child, it will
> end up attached at the wrong place (i.e. wrong node).
>
> I see several fix to that:
>
> 1- incorporate Bank's fix into the root() method. I.e. if
> there is bootstrap score, after re-rooting, the one on the
> old to new ancestor path, should be moved to the right node.
>
> 2- Modify the way trees are stored in bioperl to incorporate
> branch/edge/bipartition object, and move the bootstrap
> scores to them. That won't be easy and will break many
> things...

Just wanted to add that, from my point of view, it would be great if it
were possible to add edge/branch objects as part of the bioperl trees.  
Perhaps so that the previous set of methods still behaved as before, but
with some new methods on the trees such as get_splits() or
get_branches() along with associated split/branch/etc. objects...?

Being a bioperl user but keeping well away from coding objects in perl,
the lack of such methods/objects meant I chose, in the end, not to use a
bioperl solution to work with my trees (going instead for a homemade
clunky python solution, where I'm happier with the OO stuff)

No idea how difficult/problematic this would be to implement, though -
just my 2 cents worth...

> What do you think?
>
> --Tristan
>
>
>
>
>
>
>
> _______________________________________________
> Bioperl-l mailing list
> Bioperl-l@...
> http://lists.open-bio.org/mailman/listinfo/bioperl-l
>

--
----------------------------------------------------------------------
Aidan Budd                                    tel:[phone]
EMBL - European Molecular Biology Laboratory  fax:[phone]
Meyerhofstr. 1, 69117 Heidelberg, Germany

http://www.embl-heidelberg.de/~budd/
http://www-db.embl.de/jss/EmblGroupsHD/per_1807.html

_______________________________________________
Bioperl-l mailing list
Bioperl-l@...
http://lists.open-bio.org/mailman/listinfo/bioperl-l

[Mark A. Jensen]

After fooling around with bug 2877,
I'm thinking seriously about starting the edge-branch
project in bioperl-dev, building out an implementation
off the interfaces B:T:TreeI and B:T:NodeI. It would
give the opp'y for some code rationalization too.

Anyone out there have a problem with that?
cheers MAJ
----- Original Message -----
From: "Aidan Budd" <budd@...>
To: "BioPerl List" <bioperl-l@...>
Sent: Saturday, July 11, 2009 3:52 AM
Subject: Re: [Bioperl-l] Bootstrap, root, reroot...

> On Thu, 9 Jul 2009, Tristan Lefebure wrote:
>
>> ...
>>
>> My understanding here is that the problem is linked to the
>> well-known difficulty to differentiate node from branch
>> labels in newick trees. Bootstrap scores are branch
>> attributes not node attributes, but since Bio::TreeI has no
>> branch/edge/bipartition object they are attached to a node,
>> and in fact reflects the bootstrap score of the ancestral
>> branch leading to that node. Troubles naturally come when
>> you are dealing with an unrooted tree or reroot a tree: a
>> child can become an ancestor, and, if the bootstrap scores
>> is not moved from the old child to the new child, it will
>> end up attached at the wrong place (i.e. wrong node).
>>
>> I see several fix to that:
>>
>> 1- incorporate Bank's fix into the root() method. I.e. if
>> there is bootstrap score, after re-rooting, the one on the
>> old to new ancestor path, should be moved to the right node.
>>
>> 2- Modify the way trees are stored in bioperl to incorporate
>> branch/edge/bipartition object, and move the bootstrap
>> scores to them. That won't be easy and will break many
>> things...
>
> Just wanted to add that, from my point of view, it would be great if it
> were possible to add edge/branch objects as part of the bioperl trees.  
> Perhaps so that the previous set of methods still behaved as before, but
> with some new methods on the trees such as get_splits() or
> get_branches() along with associated split/branch/etc. objects...?
>
> Being a bioperl user but keeping well away from coding objects in perl,
> the lack of such methods/objects meant I chose, in the end, not to use a
> bioperl solution to work with my trees (going instead for a homemade
> clunky python solution, where I'm happier with the OO stuff)
>
> No idea how difficult/problematic this would be to implement, though -
> just my 2 cents worth...
>
>> What do you think?
>>
>> --Tristan
>>
>>
>>
>>
>>
>>
>>
>> _______________________________________________
>> Bioperl-l mailing list
>> Bioperl-l@...
>> http://lists.open-bio.org/mailman/listinfo/bioperl-l
>>
>
> --
> ----------------------------------------------------------------------
> Aidan Budd                                    tel:[phone]
> EMBL - European Molecular Biology Laboratory  fax:[phone]
> Meyerhofstr. 1, 69117 Heidelberg, Germany
>
> http://www.embl-heidelberg.de/~budd/
> http://www-db.embl.de/jss/EmblGroupsHD/per_1807.html
>
> _______________________________________________
> Bioperl-l mailing list
> Bioperl-l@...
> http://lists.open-bio.org/mailman/listinfo/bioperl-l
>
>

_______________________________________________
Bioperl-l mailing list
Bioperl-l@...
http://lists.open-bio.org/mailman/listinfo/bioperl-l

[Chris Fields-5]

On Jul 11, 2009, at 2:52 AM, Aidan Budd wrote:

> On Thu, 9 Jul 2009, Tristan Lefebure wrote:
>
>> ...
>>
>> My understanding here is that the problem is linked to the
>> well-known difficulty to differentiate node from branch
>> labels in newick trees. Bootstrap scores are branch
>> attributes not node attributes, but since Bio::TreeI has no
>> branch/edge/bipartition object they are attached to a node,
>> and in fact reflects the bootstrap score of the ancestral
>> branch leading to that node. Troubles naturally come when
>> you are dealing with an unrooted tree or reroot a tree: a
>> child can become an ancestor, and, if the bootstrap scores
>> is not moved from the old child to the new child, it will
>> end up attached at the wrong place (i.e. wrong node).
>>
>> I see several fix to that:
>>
>> 1- incorporate Bank's fix into the root() method. I.e. if
>> there is bootstrap score, after re-rooting, the one on the
>> old to new ancestor path, should be moved to the right node.
>>
>> 2- Modify the way trees are stored in bioperl to incorporate
>> branch/edge/bipartition object, and move the bootstrap
>> scores to them. That won't be easy and will break many
>> things...
>
> Just wanted to add that, from my point of view, it would be great if  
> it
> were possible to add edge/branch objects as part of the bioperl trees.
> Perhaps so that the previous set of methods still behaved as before,  
> but
> with some new methods on the trees such as get_splits() or
> get_branches() along with associated split/branch/etc. objects...?
>
> Being a bioperl user but keeping well away from coding objects in  
> perl,
> the lack of such methods/objects meant I chose, in the end, not to  
> use a
> bioperl solution to work with my trees (going instead for a homemade
> clunky python solution, where I'm happier with the OO stuff)
>
> No idea how difficult/problematic this would be to implement, though -
> just my 2 cents worth...

Mark and Tristan have both indicated some of the problems that lie  
here, so it's worth discussing this on the list.  I think the best way  
to approach this is to suggest what a proposed refactoring of  
Bio::Tree-related classes would look like (i.e. how it would be done,  
what is expected of said classes interface-wise, etc), and then come  
up with data and cases where the current classes don't DTRT,  
preferably as tests we can incorporate into the test suite.

Note this will affect some of the key core classes we now have (seq  
classes specifically, so memory management will be important).  I'll  
have my hands full with a few other refactors, so anyone out there  
willing to take the reins on this one?

chris


_______________________________________________
Bioperl-l mailing list
Bioperl-l@...
http://lists.open-bio.org/mailman/listinfo/bioperl-l

[Tristan Lefebure-2]

This would indeed be very good. It seems that the current
implementation might always be suboptimal. Patch after
patch, I am still harassing Mark with bugs... (see bug #2877
!).

I don't have the necessary OO skills to help building the
core object, but I would be happy to help with some
functions (like get_bipartition_table(),
is_edge_conflicting(), ...).

Not sure this could be helpful, but I find the ape phylo
object of R to be both very simple and quite flexible. See
http://ape.mpl.ird.fr/misc/FormatTreeR_28July2008.pdf for
details.

--Tristan


On Wednesday 15 July 2009 17:54:25 Mark A. Jensen wrote:

> After fooling around with bug 2877,
> I'm thinking seriously about starting the edge-branch
> project in bioperl-dev, building out an implementation
> off the interfaces B:T:TreeI and B:T:NodeI. It would
> give the opp'y for some code rationalization too.
>
> Anyone out there have a problem with that?
> cheers MAJ
> ----- Original Message -----
> From: "Aidan Budd" <budd@...>
> To: "BioPerl List" <bioperl-l@...>
> Sent: Saturday, July 11, 2009 3:52 AM
> Subject: Re: [Bioperl-l] Bootstrap, root, reroot...
>
> > On Thu, 9 Jul 2009, Tristan Lefebure wrote:
> >> ...
> >>
> >> My understanding here is that the problem is linked to
> >> the well-known difficulty to differentiate node from
> >> branch labels in newick trees. Bootstrap scores are
> >> branch attributes not node attributes, but since
> >> Bio::TreeI has no branch/edge/bipartition object they
> >> are attached to a node, and in fact reflects the
> >> bootstrap score of the ancestral branch leading to
> >> that node. Troubles naturally come when you are
> >> dealing with an unrooted tree or reroot a tree: a
> >> child can become an ancestor, and, if the bootstrap
> >> scores is not moved from the old child to the new
> >> child, it will end up attached at the wrong place
> >> (i.e. wrong node).
> >>
> >> I see several fix to that:
> >>
> >> 1- incorporate Bank's fix into the root() method. I.e.
> >> if there is bootstrap score, after re-rooting, the one
> >> on the old to new ancestor path, should be moved to
> >> the right node.
> >>
> >> 2- Modify the way trees are stored in bioperl to
> >> incorporate branch/edge/bipartition object, and move
> >> the bootstrap scores to them. That won't be easy and
> >> will break many things...
> >
> > Just wanted to add that, from my point of view, it
> > would be great if it were possible to add edge/branch
> > objects as part of the bioperl trees. Perhaps so that
> > the previous set of methods still behaved as before,
> > but with some new methods on the trees such as
> > get_splits() or get_branches() along with associated
> > split/branch/etc. objects...?
> >
> > Being a bioperl user but keeping well away from coding
> > objects in perl, the lack of such methods/objects meant
> > I chose, in the end, not to use a bioperl solution to
> > work with my trees (going instead for a homemade clunky
> > python solution, where I'm happier with the OO stuff)
> >
> > No idea how difficult/problematic this would be to
> > implement, though - just my 2 cents worth...
> >
> >> What do you think?
> >>
> >> --Tristan
> >>
> >>
> >>
> >>
> >>
> >>
> >>
> >> _______________________________________________
> >> Bioperl-l mailing list
> >> Bioperl-l@...
> >> http://lists.open-bio.org/mailman/listinfo/bioperl-l
> >
> > --
> > -------------------------------------------------------
> >--------------- Aidan Budd                              
> >      tel:[phone] EMBL - European Molecular
> > Biology Laboratory  fax:[phone]
> > Meyerhofstr. 1, 69117 Heidelberg, Germany
> >
> > http://www.embl-heidelberg.de/~budd/
> > http://www-db.embl.de/jss/EmblGroupsHD/per_1807.html
> >
> > _______________________________________________
> > Bioperl-l mailing list
> > Bioperl-l@...
> > http://lists.open-bio.org/mailman/listinfo/bioperl-l

_______________________________________________
Bioperl-l mailing list
Bioperl-l@...
http://lists.open-bio.org/mailman/listinfo/bioperl-l

[Chris Fields-5]

I don't; code away.

With the edge/branch objects, I'm wondering whether those can be  
created lazily (only when needed); it might lighten up the tree a  
bit.  Also, don't forget to look at Rutger's Bio::Phylo project,  
though I think his modules use inside-out objects (might not be easy  
to work into core unless they are wrapped).

chris

On Jul 15, 2009, at 4:54 PM, Mark A. Jensen wrote:

> After fooling around with bug 2877, I'm thinking seriously about  
> starting the edge-branch
> project in bioperl-dev, building out an implementation off the  
> interfaces B:T:TreeI and B:T:NodeI. It would
> give the opp'y for some code rationalization too.
> Anyone out there have a problem with that?
> cheers MAJ
> ----- Original Message ----- From: "Aidan Budd" <budd@...
> >
> To: "BioPerl List" <bioperl-l@...>
> Sent: Saturday, July 11, 2009 3:52 AM
> Subject: Re: [Bioperl-l] Bootstrap, root, reroot...
>
>
>> On Thu, 9 Jul 2009, Tristan Lefebure wrote:
>>> ...
>>> My understanding here is that the problem is linked to the well-
>>> known difficulty to differentiate node from branch labels in  
>>> newick trees. Bootstrap scores are branch attributes not node  
>>> attributes, but since Bio::TreeI has no branch/edge/bipartition  
>>> object they are attached to a node, and in fact reflects the  
>>> bootstrap score of the ancestral branch leading to that node.  
>>> Troubles naturally come when you are dealing with an unrooted tree  
>>> or reroot a tree: a child can become an ancestor, and, if the  
>>> bootstrap scores is not moved from the old child to the new child,  
>>> it will end up attached at the wrong place (i.e. wrong node). I  
>>> see several fix to that:
>>> 1- incorporate Bank's fix into the root() method. I.e. if there is  
>>> bootstrap score, after re-rooting, the one on the old to new  
>>> ancestor path, should be moved to the right node. 2- Modify the  
>>> way trees are stored in bioperl to incorporate branch/edge/
>>> bipartition object, and move the bootstrap scores to them. That  
>>> won't be easy and will break many things...
>> Just wanted to add that, from my point of view, it would be great  
>> if it
>> were possible to add edge/branch objects as part of the bioperl  
>> trees.  Perhaps so that the previous set of methods still behaved  
>> as before, but
>> with some new methods on the trees such as get_splits() or  
>> get_branches() along with associated split/branch/etc. objects...?
>> Being a bioperl user but keeping well away from coding objects in  
>> perl,
>> the lack of such methods/objects meant I chose, in the end, not to  
>> use a
>> bioperl solution to work with my trees (going instead for a homemade
>> clunky python solution, where I'm happier with the OO stuff)
>> No idea how difficult/problematic this would be to implement,  
>> though - just my 2 cents worth...
>>> What do you think?
>>> --Tristan
>>> _______________________________________________
>>> Bioperl-l mailing list
>>> Bioperl-l@...
>>> http://lists.open-bio.org/mailman/listinfo/bioperl-l
>> --
>> ----------------------------------------------------------------------
>> Aidan Budd                                    tel:[phone]  
>> 8530
>> EMBL - European Molecular Biology Laboratory  fax:[phone]  
>> 8517
>> Meyerhofstr. 1, 69117 Heidelberg, Germany
>> http://www.embl-heidelberg.de/~budd/
>> http://www-db.embl.de/jss/EmblGroupsHD/per_1807.html
>> _______________________________________________
>> Bioperl-l mailing list
>> Bioperl-l@...
>> http://lists.open-bio.org/mailman/listinfo/bioperl-l
>>
> _______________________________________________
> Bioperl-l mailing list
> Bioperl-l@...
> http://lists.open-bio.org/mailman/listinfo/bioperl-l

_______________________________________________
Bioperl-l mailing list
Bioperl-l@...
http://lists.open-bio.org/mailman/listinfo/bioperl-l

[Mark A. Jensen]

To examine rvos' Bio::Phylo was my plan exactly--
Lazy edges can be done I believe, although it seems
that one of the main reasons to have edges is to
attach lengths, bootstrap values, etc to them; so we may
ultimately avoid edge creation only when we construct tree
topology only--prob rare in practice?

----- Original Message -----
From: "Chris Fields" <cjfields@...>
To: "Mark A. Jensen" <maj@...>
Cc: "Aidan Budd" <budd@...>; "BioPerl List"
<bioperl-l@...>; <tristan.lefebure@...>
Sent: Wednesday, July 15, 2009 11:29 PM
Subject: Re: [Bioperl-l] Bootstrap, root, reroot...

>I don't; code away.
>
> With the edge/branch objects, I'm wondering whether those can be  created
> lazily (only when needed); it might lighten up the tree a  bit.  Also, don't
> forget to look at Rutger's Bio::Phylo project,  though I think his modules use
> inside-out objects (might not be easy  to work into core unless they are
> wrapped).
>
> chris
>
> On Jul 15, 2009, at 4:54 PM, Mark A. Jensen wrote:
>
>> After fooling around with bug 2877, I'm thinking seriously about  starting
>> the edge-branch
>> project in bioperl-dev, building out an implementation off the  interfaces
>> B:T:TreeI and B:T:NodeI. It would
>> give the opp'y for some code rationalization too.
>> Anyone out there have a problem with that?
>> cheers MAJ
>> ----- Original Message ----- From: "Aidan Budd" <budd@...
>> >
>> To: "BioPerl List" <bioperl-l@...>
>> Sent: Saturday, July 11, 2009 3:52 AM
>> Subject: Re: [Bioperl-l] Bootstrap, root, reroot...
>>
>>
>>> On Thu, 9 Jul 2009, Tristan Lefebure wrote:
>>>> ...
>>>> My understanding here is that the problem is linked to the well- known
>>>> difficulty to differentiate node from branch labels in  newick trees.
>>>> Bootstrap scores are branch attributes not node  attributes, but since
>>>> Bio::TreeI has no branch/edge/bipartition  object they are attached to a
>>>> node, and in fact reflects the  bootstrap score of the ancestral branch
>>>> leading to that node.  Troubles naturally come when you are dealing with an
>>>> unrooted tree  or reroot a tree: a child can become an ancestor, and, if
>>>> the  bootstrap scores is not moved from the old child to the new child,  it
>>>> will end up attached at the wrong place (i.e. wrong node). I  see several
>>>> fix to that:
>>>> 1- incorporate Bank's fix into the root() method. I.e. if there is
>>>> bootstrap score, after re-rooting, the one on the old to new  ancestor
>>>> path, should be moved to the right node. 2- Modify the  way trees are
>>>> stored in bioperl to incorporate branch/edge/ bipartition object, and move
>>>> the bootstrap scores to them. That  won't be easy and will break many
>>>> things...
>>> Just wanted to add that, from my point of view, it would be great  if it
>>> were possible to add edge/branch objects as part of the bioperl  trees.
>>> Perhaps so that the previous set of methods still behaved  as before, but
>>> with some new methods on the trees such as get_splits() or  get_branches()
>>> along with associated split/branch/etc. objects...?
>>> Being a bioperl user but keeping well away from coding objects in  perl,
>>> the lack of such methods/objects meant I chose, in the end, not to  use a
>>> bioperl solution to work with my trees (going instead for a homemade
>>> clunky python solution, where I'm happier with the OO stuff)
>>> No idea how difficult/problematic this would be to implement,  though - just
>>> my 2 cents worth...
>>>> What do you think?
>>>> --Tristan
>>>> _______________________________________________
>>>> Bioperl-l mailing list
>>>> Bioperl-l@...
>>>> http://lists.open-bio.org/mailman/listinfo/bioperl-l
>>> --
>>> ----------------------------------------------------------------------
>>> Aidan Budd                                    tel:[phone]
>>> EMBL - European Molecular Biology Laboratory  fax:[phone]
>>> Meyerhofstr. 1, 69117 Heidelberg, Germany
>>> http://www.embl-heidelberg.de/~budd/
>>> http://www-db.embl.de/jss/EmblGroupsHD/per_1807.html
>>> _______________________________________________
>>> Bioperl-l mailing list
>>> Bioperl-l@...
>>> http://lists.open-bio.org/mailman/listinfo/bioperl-l
>>>
>> _______________________________________________
>> Bioperl-l mailing list
>> Bioperl-l@...
>> http://lists.open-bio.org/mailman/listinfo/bioperl-l
>
>
>

_______________________________________________
Bioperl-l mailing list
Bioperl-l@...
http://lists.open-bio.org/mailman/listinfo/bioperl-l

[Chris Fields-5]

Well, what I was thinking that Nodes sharing an edge could share the  
same hash ref containing the edge information, with said hash ref  
magically becoming an object when absolutely needed (keys being named  
parameters, values being args for constructor).  Just a thought.

chris

On Jul 15, 2009, at 10:43 PM, Mark A. Jensen wrote:

> To examine rvos' Bio::Phylo was my plan exactly-- Lazy edges can be  
> done I believe, although it seems
> that one of the main reasons to have edges is to
> attach lengths, bootstrap values, etc to them; so we may
> ultimately avoid edge creation only when we construct tree
> topology only--prob rare in practice?
>
> ----- Original Message ----- From: "Chris Fields" <cjfields@...
> >
> To: "Mark A. Jensen" <maj@...>
> Cc: "Aidan Budd" <budd@...>; "BioPerl List" <bioperl-l@...
> >; <tristan.lefebure@...>
> Sent: Wednesday, July 15, 2009 11:29 PM
> Subject: Re: [Bioperl-l] Bootstrap, root, reroot...
>
>
>> I don't; code away.
>>
>> With the edge/branch objects, I'm wondering whether those can be  
>> created lazily (only when needed); it might lighten up the tree a  
>> bit.  Also, don't forget to look at Rutger's Bio::Phylo project,  
>> though I think his modules use inside-out objects (might not be  
>> easy  to work into core unless they are wrapped).
>>
>> chris
>>
>> On Jul 15, 2009, at 4:54 PM, Mark A. Jensen wrote:
>>
>>> After fooling around with bug 2877, I'm thinking seriously about  
>>> starting the edge-branch
>>> project in bioperl-dev, building out an implementation off the  
>>> interfaces B:T:TreeI and B:T:NodeI. It would
>>> give the opp'y for some code rationalization too.
>>> Anyone out there have a problem with that?
>>> cheers MAJ
>>> ----- Original Message ----- From: "Aidan Budd" <budd@...
>>> >
>>> To: "BioPerl List" <bioperl-l@...>
>>> Sent: Saturday, July 11, 2009 3:52 AM
>>> Subject: Re: [Bioperl-l] Bootstrap, root, reroot...
>>>
>>>
>>>> On Thu, 9 Jul 2009, Tristan Lefebure wrote:
>>>>> ...
>>>>> My understanding here is that the problem is linked to the well-  
>>>>> known difficulty to differentiate node from branch labels in  
>>>>> newick trees. Bootstrap scores are branch attributes not node  
>>>>> attributes, but since Bio::TreeI has no branch/edge/bipartition  
>>>>> object they are attached to a node, and in fact reflects the  
>>>>> bootstrap score of the ancestral branch leading to that node.  
>>>>> Troubles naturally come when you are dealing with an unrooted  
>>>>> tree  or reroot a tree: a child can become an ancestor, and, if  
>>>>> the  bootstrap scores is not moved from the old child to the new  
>>>>> child,  it will end up attached at the wrong place (i.e. wrong  
>>>>> node). I  see several fix to that:
>>>>> 1- incorporate Bank's fix into the root() method. I.e. if there  
>>>>> is bootstrap score, after re-rooting, the one on the old to new  
>>>>> ancestor path, should be moved to the right node. 2- Modify the  
>>>>> way trees are stored in bioperl to incorporate branch/edge/  
>>>>> bipartition object, and move the bootstrap scores to them. That  
>>>>> won't be easy and will break many things...
>>>> Just wanted to add that, from my point of view, it would be  
>>>> great  if it
>>>> were possible to add edge/branch objects as part of the bioperl  
>>>> trees. Perhaps so that the previous set of methods still behaved  
>>>> as before, but
>>>> with some new methods on the trees such as get_splits() or  
>>>> get_branches() along with associated split/branch/etc. objects...?
>>>> Being a bioperl user but keeping well away from coding objects  
>>>> in  perl,
>>>> the lack of such methods/objects meant I chose, in the end, not  
>>>> to  use a
>>>> bioperl solution to work with my trees (going instead for a  
>>>> homemade
>>>> clunky python solution, where I'm happier with the OO stuff)
>>>> No idea how difficult/problematic this would be to implement,  
>>>> though - just my 2 cents worth...
>>>>> What do you think?
>>>>> --Tristan
>>>>> _______________________________________________
>>>>> Bioperl-l mailing list
>>>>> Bioperl-l@...
>>>>> http://lists.open-bio.org/mailman/listinfo/bioperl-l
>>>> --
>>>> ----------------------------------------------------------------------
>>>> Aidan Budd                                    tel:[phone]  
>>>> 387  8530
>>>> EMBL - European Molecular Biology Laboratory  fax:[phone]  
>>>> 387  8517
>>>> Meyerhofstr. 1, 69117 Heidelberg, Germany
>>>> http://www.embl-heidelberg.de/~budd/
>>>> http://www-db.embl.de/jss/EmblGroupsHD/per_1807.html
>>>> _______________________________________________
>>>> Bioperl-l mailing list
>>>> Bioperl-l@...
>>>> http://lists.open-bio.org/mailman/listinfo/bioperl-l
>>>>
>>> _______________________________________________
>>> Bioperl-l mailing list
>>> Bioperl-l@...
>>> http://lists.open-bio.org/mailman/listinfo/bioperl-l
>>
>>
>

_______________________________________________
Bioperl-l mailing list
Bioperl-l@...
http://lists.open-bio.org/mailman/listinfo/bioperl-l

[Giles Weaver]

All this talk of nodes and edges makes me thing of
Cytoscape<http://www.cytoscape.org/features2.php>.
Cytoscape was developed to visualise molecular interaction networks, but can
be used to display all kinds of things, including trees.

Has anyone considered a generic Bio::Network to describe nodes and edges? A
Bio::Tree could be implemented as a (relatively) simple Bio::Network. A more
complicated Bio::Network might be something like a Bio::Model, containing a
mathematical model such as those found in the biomodels
database<http://www.ebi.ac.uk/biomodels-main/>.
This could be very useful for systems biology.

Giles

2009/7/16 Chris Fields <cjfields@...>

> Well, what I was thinking that Nodes sharing an edge could share the same
> hash ref containing the edge information, with said hash ref magically
> becoming an object when absolutely needed (keys being named parameters,
> values being args for constructor).  Just a thought.
>
> chris
>
>
> On Jul 15, 2009, at 10:43 PM, Mark A. Jensen wrote:
>
>  To examine rvos' Bio::Phylo was my plan exactly-- Lazy edges can be done I
>> believe, although it seems
>> that one of the main reasons to have edges is to
>> attach lengths, bootstrap values, etc to them; so we may
>> ultimately avoid edge creation only when we construct tree
>> topology only--prob rare in practice?
>>
>> ----- Original Message ----- From: "Chris Fields" <cjfields@...>
>> To: "Mark A. Jensen" <maj@...>
>> Cc: "Aidan Budd" <budd@...>; "BioPerl List" <
>> bioperl-l@...>; <tristan.lefebure@...>
>> Sent: Wednesday, July 15, 2009 11:29 PM
>> Subject: Re: [Bioperl-l] Bootstrap, root, reroot...
>>
>>
>>  I don't; code away.
>>>
>>> With the edge/branch objects, I'm wondering whether those can be  created
>>> lazily (only when needed); it might lighten up the tree a  bit.  Also, don't
>>> forget to look at Rutger's Bio::Phylo project,  though I think his modules
>>> use inside-out objects (might not be easy  to work into core unless they are
>>> wrapped).
>>>
>>> chris
>>>
>>> On Jul 15, 2009, at 4:54 PM, Mark A. Jensen wrote:
>>>
>>>  After fooling around with bug 2877, I'm thinking seriously about
>>>>  starting the edge-branch
>>>> project in bioperl-dev, building out an implementation off the
>>>>  interfaces B:T:TreeI and B:T:NodeI. It would
>>>> give the opp'y for some code rationalization too.
>>>> Anyone out there have a problem with that?
>>>> cheers MAJ
>>>> ----- Original Message ----- From: "Aidan Budd" <
>>>> budd@...
>>>> >
>>>> To: "BioPerl List" <bioperl-l@...>
>>>> Sent: Saturday, July 11, 2009 3:52 AM
>>>> Subject: Re: [Bioperl-l] Bootstrap, root, reroot...
>>>>
>>>>
>>>>  On Thu, 9 Jul 2009, Tristan Lefebure wrote:
>>>>>
>>>>>> ...
>>>>>> My understanding here is that the problem is linked to the well- known
>>>>>> difficulty to differentiate node from branch labels in  newick trees.
>>>>>> Bootstrap scores are branch attributes not node  attributes, but since
>>>>>> Bio::TreeI has no branch/edge/bipartition  object they are attached to a
>>>>>> node, and in fact reflects the  bootstrap score of the ancestral branch
>>>>>> leading to that node.  Troubles naturally come when you are dealing with an
>>>>>> unrooted tree  or reroot a tree: a child can become an ancestor, and, if the
>>>>>>  bootstrap scores is not moved from the old child to the new child,  it will
>>>>>> end up attached at the wrong place (i.e. wrong node). I  see several fix to
>>>>>> that:
>>>>>> 1- incorporate Bank's fix into the root() method. I.e. if there is
>>>>>> bootstrap score, after re-rooting, the one on the old to new  ancestor path,
>>>>>> should be moved to the right node. 2- Modify the  way trees are stored in
>>>>>> bioperl to incorporate branch/edge/ bipartition object, and move the
>>>>>> bootstrap scores to them. That  won't be easy and will break many things...
>>>>>>
>>>>> Just wanted to add that, from my point of view, it would be great  if
>>>>> it
>>>>> were possible to add edge/branch objects as part of the bioperl  trees.
>>>>> Perhaps so that the previous set of methods still behaved  as before, but
>>>>> with some new methods on the trees such as get_splits() or
>>>>>  get_branches() along with associated split/branch/etc. objects...?
>>>>> Being a bioperl user but keeping well away from coding objects in
>>>>>  perl,
>>>>> the lack of such methods/objects meant I chose, in the end, not to  use
>>>>> a
>>>>> bioperl solution to work with my trees (going instead for a homemade
>>>>> clunky python solution, where I'm happier with the OO stuff)
>>>>> No idea how difficult/problematic this would be to implement,  though -
>>>>> just my 2 cents worth...
>>>>>
>>>>>> What do you think?
>>>>>> --Tristan
>>>>>> _______________________________________________
>>>>>> Bioperl-l mailing list
>>>>>> Bioperl-l@...
>>>>>> http://lists.open-bio.org/mailman/listinfo/bioperl-l
>>>>>>
>>>>> --
>>>>> ----------------------------------------------------------------------
>>>>> Aidan Budd                                    tel:[phone]
>>>>> EMBL - European Molecular Biology Laboratory  fax:[phone]
>>>>> Meyerhofstr. 1, 69117 Heidelberg, Germany
>>>>> http://www.embl-heidelberg.de/~budd/<http://www.embl-heidelberg.de/%7Ebudd/>
>>>>> http://www-db.embl.de/jss/EmblGroupsHD/per_1807.html
>>>>> _______________________________________________
>>>>> Bioperl-l mailing list
>>>>> Bioperl-l@...
>>>>> http://lists.open-bio.org/mailman/listinfo/bioperl-l
>>>>>
>>>>>  _______________________________________________
>>>> Bioperl-l mailing list
>>>> Bioperl-l@...
>>>> http://lists.open-bio.org/mailman/listinfo/bioperl-l
>>>>
>>>
>>>
>>>
>>
> _______________________________________________
> Bioperl-l mailing list
> Bioperl-l@...
> http://lists.open-bio.org/mailman/listinfo/bioperl-l
>

_______________________________________________
Bioperl-l mailing list
Bioperl-l@...
http://lists.open-bio.org/mailman/listinfo/bioperl-l