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