Bio::Tree::Compatible(3)

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

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

  my ($incompat, $ilabels, $inodes) = $t1->is_compatible($t2);
  if ($incompat) {
    my %cluster1 = %{ $t1->cluster_representation };
    my %cluster2 = %{ $t2->cluster_representation };
    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
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/MailList.shtml  - About the mailing lists

  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:

  http://bugzilla.bioperl.org/

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. Manuscript (2005).

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 list 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