Provided by: libbio-perl-perl_1.7.8-1_all bug

NAME

       Bio::Tree::Compatible - Testing compatibility of phylogenetic trees with nested taxa.

SYNOPSIS

         use Bio::Tree::Compatible;
         use Bio::TreeIO;
         my $input = Bio::TreeIO->new('-format' => 'newick',
                                      '-file'   => 'input.tre');
         my $t1 = $input->next_tree;
         my $t2 = $input->next_tree;

         my ($incompat, $ilabels, $inodes) = Bio::Tree::Compatible::is_compatible($t1,$t2);
         if ($incompat) {
           my %cluster1 = %{ Bio::Tree::Compatible::cluster_representation($t1) };
           my %cluster2 = %{ Bio::Tree::Compatible::cluster_representation($t2) };
           print "incompatible trees\n";
           if (scalar(@$ilabels)) {
             foreach my $label (@$ilabels) {
               my $node1 = $t1->find_node(-id => $label);
               my $node2 = $t2->find_node(-id => $label);
               my @c1 = sort @{ $cluster1{$node1} };
               my @c2 = sort @{ $cluster2{$node2} };
               print "label $label";
               print " cluster"; map { print " ",$_ } @c1;
               print " cluster"; map { print " ",$_ } @c2; print "\n";
             }
           }
           if (scalar(@$inodes)) {
             while (@$inodes) {
               my $node1 = shift @$inodes;
               my $node2 = shift @$inodes;
               my @c1 = sort @{ $cluster1{$node1} };
               my @c2 = sort @{ $cluster2{$node2} };
               print "cluster"; map { print " ",$_ } @c1;
               print " properly intersects cluster";
               map { print " ",$_ } @c2; print "\n";
             }
           }
         } else {
           print "compatible trees\n";
         }

DESCRIPTION

       NB: This module has exclusively class methods that work on Bio::Tree::TreeI objects. An
       instance of Bio::Tree::Compatible cannot itself represent a tree, and so typically there
       is no need to create one.

       Bio::Tree::Compatible is a Perl tool for testing compatibility of phylogenetic trees with
       nested taxa represented as Bio::Tree::Tree objects. It is based on a recent
       characterization of ancestral compatibility of semi-labeled trees in terms of their
       cluster representations.

       A semi-labeled tree is a phylogenetic tree with some of its internal nodes labeled, and it
       can represent a classification tree as well as a phylogenetic tree with nested taxa, with
       labeled internal nodes corresponding to taxa at a higher level of aggregation or nesting
       than that of their descendents.

       Two semi-labeled trees are compatible if their topological restrictions to the common
       labels are such that for each node label, the smallest clusters containing it in each of
       the trees coincide and, furthermore, no cluster in one of the trees properly intersects a
       cluster of the other tree.

       Future extensions of Bio::Tree::Compatible include a Bio::Tree::Supertree module for
       combining compatible phylogenetic trees with nested taxa into a common supertree.

FEEDBACK

   Mailing Lists
       User feedback is an integral part of the evolution of this and other Bioperl modules. Send
       your comments and suggestions preferably to the Bioperl mailing list.  Your participation
       is much appreciated.

         bioperl-l@bioperl.org                  - General discussion
         http://bioperl.org/wiki/Mailing_lists  - About the mailing lists

   Support
       Please direct usage questions or support issues to the mailing list:

       bioperl-l@bioperl.org

       rather than to the module maintainer directly. Many experienced and reponsive experts will
       be able look at the problem and quickly address it. Please include a thorough description
       of the problem with code and data examples if at all possible.

   Reporting Bugs
       Report bugs to the Bioperl bug tracking system to help us keep track of the bugs and their
       resolution. Bug reports can be submitted via the web:

         https://github.com/bioperl/bioperl-live/issues

SEE ALSO

       •   Philip Daniel and Charles Semple. Supertree Algorithms for Nested Taxa. In: Olaf R. P.
           Bininda-Emonds (ed.) Phylogenetic Supertrees: Combining Information to Reveal the Tree
           of Life, Computational Biology, vol. 4, chap. 7, pp. 151-171. Kluwer (2004).

       •   Charles Semple, Philip Daniel, Wim Hordijk, Roderic D. M. Page, and Mike Steel:
           Supertree Algorithms for Ancestral Divergence Dates and Nested Taxa. Bioinformatics
           20(15), 2355-2360 (2004).

       •   Merce Llabres, Jairo Rocha, Francesc Rossello, and Gabriel Valiente: On the Ancestral
           Compatibility of Two Phylogenetic Trees with Nested Taxa. J. Math. Biol. 53(3),
           340-364 (2006).

AUTHOR - Gabriel Valiente

       Email valiente@lsi.upc.edu

APPENDIX

       The rest of the documentation details each of the object methods.

   postorder_traversal
        Title   : postorder_traversal
        Usage   : my @nodes = @{ $tree->postorder_traversal }
        Function: Return list of nodes in postorder
        Returns : reference to array of Bio::Tree::Node
        Args    : none

       For example, the postorder traversal of the tree "(((A,B)C,D),(E,F,G));" is a reference to
       an array of nodes with internal_id 0 through 9, because the Newick standard representation
       for phylogenetic trees is based on a postorder traversal.

                 +---A                    +---0
                 |                        |
         +---+---C                +---4---2
         |   |   |                |   |   |
         |   |   +---B            |   |   +---1
         |   |                    |   |
         +   +-------D            9   +-------3
         |                        |
         |     +-----E            |     +-----5
         |     |                  |     |
         +-----+-----F            +-----8-----6
               |                        |
               +-----G                  +-----7

   cluster_representation
        Title   : cluster_representation
        Usage   : my %cluster = %{ $tree->cluster_representation }
        Function: Compute the cluster representation of a tree
        Returns : reference to hash of array of string indexed by
                  Bio::Tree::Node
        Args    : none

       For example, the cluster representation of the tree "(((A,B)C,D),(E,F,G));" is a reference
       to a hash associating an array of string (descendent labels) to each node, as follows:

         0 --> [A]
         1 --> [B]
         2 --> [A,B,C]
         3 --> [D]
         4 --> [A,B,C,D]
         5 --> [E]
         6 --> [F]
         7 --> [G]
         8 --> [E,F,G]
         9 --> [A,B,C,D,E,F,G]

   common_labels
        Title   : common_labels
        Usage   : my $labels = $tree1->common_labels($tree2);
        Function: Return set of common node labels
        Returns : Set::Scalar
        Args    : Bio::Tree::Tree

       For example, the common labels of the tree "(((A,B)C,D),(E,F,G));" and the tree
       "((A,B)H,E,(J,(K)G)I);" are: "[A,B,E,G]".

                 +---A                 +---A
                 |                     |
         +---+---C             +-------H
         |   |   |             |       |
         |   |   +---B         |       +---B
         |   |                 |
         +   +-------D         +-----------E
         |                     |
         |     +-----E         |   +-------J
         |     |               |   |
         +-----+-----F         +---I
               |                   |
               +-----G             +---G---K

   topological_restriction
        Title   : topological_restriction
        Usage   : $tree->topological_restriction($labels)
        Function: Compute the topological restriction of a tree to a subset
                  of node labels
        Returns : Bio::Tree::Tree
        Args    : Set::Scalar

       For example, the topological restrictions of each of the trees "(((A,B)C,D),(E,F,G));" and
       "((A,B)H,E,(J,(K)G)I);" to the labels "[A,B,E,G]" are as follows:

                 +---A             +---A
                 |                 |
         +---+---+             +---+
         |       |             |   |
         |       +---B         |   +---B
         +                     |
         |       +---E         +-------E
         |       |             |
         +-------+             +---+---G
                 |
                 +---G

   is_compatible
        Title   : is_compatible
        Usage   : $tree1->is_compatible($tree2)
        Function: Test compatibility of two trees
        Returns : boolean
        Args    : Bio::Tree::Tree

       For example, the topological restrictions of the trees "(((A,B)C,D),(E,F,G));" and
       "((A,B)H,E,(J,(K)G)I);" to their common labels, "[A,B,E,G]", are compatible. The
       respective cluster representations are as follows:

         [A]                  [A]
         [B]                  [B]
         [E]                  [E]
         [G]                  [G]
         [A,B]                [A,B]
         [E,G]                [A,B,E,G]
         [A,B,E,G]

       As a second example, the trees "(A,B);" and "((B)A);" are incompatible. Their respective
       cluster representations are as follows:

         [A]                  [B]
         [B]                  [A,B]
         [A,B]

       The reason is, the smallest cluster containing label "A" is "[A]" in the first tree but
       "[A,B]" in the second tree.

        +---A         A---B
        |
        +
        |
        +---B

       As a second example, the trees "(((B,A),C),D);" and "((A,(D,B)),C);" are also
       incompatible. Their respective cluster representations are as follows:

         [A]                  [A]
         [B]                  [B]
         [C]                  [C]
         [D]                  [D]
         [A,B]                [B,D]
         [A,B,C]              [A,B,D]
         [A,B,C,D]            [A,B,C,D]

       The reason is, cluster "[A,B]" properly intersects cluster "[B,D]". There are further
       incompatibilities between these trees: "[A,B,C]" properly intersects both "[B,D]" and
       "[A,B,D]".

                 +---B             +-------A
                 |                 |
             +---+             +---+   +---D
             |   |             |   |   |
         +---+   +---A         |   +---+
         |   |                 +       |
         +   +-------C         |       +---B
         |                     |
         +-----------D         +-----------C