Bio/Tree/Compatible.pm

filter: Statementstmt 88.3% 83 / 94 Branchbran 50.0% 8 / 16 Conditioncond 0.0% 0 / 3 MC/DCmcdc 0.0% 0 / 2 Subroutinesub 100% 8 / 8 Podpod 100% 5 / 5 totaltotal 81.2% 104 / 128 CC 16 SCAR 24.9
CC
16
Cov
81%
topological_restriction
31.3
is_compatible
6.0
postorder_traversal
3.0
CRAP 12.1
« Bio/Seq/SimulatedRead.pm ↑ Summary Bio/Tools/Est2Genome.pm »
1 #
2 # BioPerl module for Bio::Tree::Compatible
3 #
4 # Please direct questions and support issues to <bioperl-l@bioperl.org>
5 #
6 # Cared for by Gabriel Valiente <valiente@lsi.upc.edu>
7 #
8 # Copyright Gabriel Valiente
9 #
10 # You may distribute this module under the same terms as Perl itself
11  
12 # POD documentation - main docs before the code
13  
14 =head1 NAME
15  
16 Bio::Tree::Compatible - Testing compatibility of phylogenetic trees
17 with nested taxa.
18  
19 =head1 SYNOPSIS
20  
21 use Bio::Tree::Compatible;
22 use Bio::TreeIO;
23 my $input = Bio::TreeIO->new('-format' => 'newick',
24 '-file' => 'input.tre');
25 my $t1 = $input->next_tree;
26 my $t2 = $input->next_tree;
27  
28 my ($incompat, $ilabels, $inodes) = Bio::Tree::Compatible::is_compatible($t1,$t2);
29 if ($incompat) {
30 my %cluster1 = %{ Bio::Tree::Compatible::cluster_representation($t1) };
31 my %cluster2 = %{ Bio::Tree::Compatible::cluster_representation($t2) };
32 print "incompatible trees\n";
33 if (scalar(@$ilabels)) {
34 foreach my $label (@$ilabels) {
35 my $node1 = $t1->find_node(-id => $label);
36 my $node2 = $t2->find_node(-id => $label);
37 my @c1 = sort @{ $cluster1{$node1} };
38 my @c2 = sort @{ $cluster2{$node2} };
39 print "label $label";
40 print " cluster"; map { print " ",$_ } @c1;
41 print " cluster"; map { print " ",$_ } @c2; print "\n";
42 }
43 }
44 if (scalar(@$inodes)) {
45 while (@$inodes) {
46 my $node1 = shift @$inodes;
47 my $node2 = shift @$inodes;
48 my @c1 = sort @{ $cluster1{$node1} };
49 my @c2 = sort @{ $cluster2{$node2} };
50 print "cluster"; map { print " ",$_ } @c1;
51 print " properly intersects cluster";
52 map { print " ",$_ } @c2; print "\n";
53 }
54 }
55 } else {
56 print "compatible trees\n";
57 }
58  
59 =head1 DESCRIPTION
60  
61 NB: This module has exclusively class methods that work on Bio::Tree::TreeI
62 objects. An instance of Bio::Tree::Compatible cannot itself represent a tree,
63 and so typically there is no need to create one.
64  
65 Bio::Tree::Compatible is a Perl tool for testing compatibility of
66 phylogenetic trees with nested taxa represented as Bio::Tree::Tree
67 objects. It is based on a recent characterization of ancestral
68 compatibility of semi-labeled trees in terms of their cluster
69 representations.
70  
71 A semi-labeled tree is a phylogenetic tree with some of its internal
72 nodes labeled, and it can represent a classification tree as well as a
73 phylogenetic tree with nested taxa, with labeled internal nodes
74 corresponding to taxa at a higher level of aggregation or nesting than
75 that of their descendents.
76  
77 Two semi-labeled trees are compatible if their topological
78 restrictions to the common labels are such that for each node label,
79 the smallest clusters containing it in each of the trees coincide and,
80 furthermore, no cluster in one of the trees properly intersects a
81 cluster of the other tree.
82  
83 Future extensions of Bio::Tree::Compatible include a
84 Bio::Tree::Supertree module for combining compatible phylogenetic
85 trees with nested taxa into a common supertree.
86  
87 =head1 FEEDBACK
88  
89 =head2 Mailing Lists
90  
91 User feedback is an integral part of the evolution of this and other
92 Bioperl modules. Send your comments and suggestions preferably to the
93 Bioperl mailing list. Your participation is much appreciated.
94  
95 bioperl-l@bioperl.org - General discussion
96 http://bioperl.org/wiki/Mailing_lists - About the mailing lists
97  
98 =head2 Support
99  
100 Please direct usage questions or support issues to the mailing list:
101  
102 I<bioperl-l@bioperl.org>
103  
104 rather than to the module maintainer directly. Many experienced and
105 reponsive experts will be able look at the problem and quickly
106 address it. Please include a thorough description of the problem
107 with code and data examples if at all possible.
108  
109 =head2 Reporting Bugs
110  
111 Report bugs to the Bioperl bug tracking system to help us keep track
112 of the bugs and their resolution. Bug reports can be submitted via the
113 web:
114  
115 https://github.com/bioperl/bioperl-live/issues
116  
117 =head1 SEE ALSO
118  
119 =over
120  
121 =item * Philip Daniel and Charles Semple. Supertree Algorithms for
122 Nested Taxa. In: Olaf R. P. Bininda-Emonds (ed.) Phylogenetic
123 Supertrees: Combining Information to Reveal the Tree of Life,
124 I<Computational Biology>, vol. 4, chap. 7, pp. 151-171. Kluwer (2004).
125  
126 =item * Charles Semple, Philip Daniel, Wim Hordijk, Roderic
127 D. M. Page, and Mike Steel: Supertree Algorithms for Ancestral
128 Divergence Dates and Nested Taxa. Bioinformatics B<20>(15), 2355-2360
129 (2004).
130  
131 =item * Merce Llabres, Jairo Rocha, Francesc Rossello, and Gabriel
132 Valiente: On the Ancestral Compatibility of Two Phylogenetic Trees
133 with Nested Taxa. J. Math. Biol. B<53>(3), 340-364 (2006).
134  
135 =back
136  
137 =head1 AUTHOR - Gabriel Valiente
138  
139 Email valiente@lsi.upc.edu
140  
141 =head1 APPENDIX
142  
143 The rest of the documentation details each of the object methods.
144  
145 =cut
146  
147 package Bio::Tree::Compatible;
148 2 $Bio::Tree::Compatible::VERSION = '1.7.8';
149 2 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
150  
151 # Object preamble - inherits from Bio::Root::Root
152  
153 2 ▶use Set::Scalar;
Subroutine BEGIN: called CC=1 SCAR=0.0
154  
155 2 ▶use base qw(Bio::Root::Root);
Subroutine BEGIN: called CC=1 SCAR=0.0
156  
157 =head2 postorder_traversal
158  
159 Title : postorder_traversal
160 Usage : my @nodes = @{ $tree->postorder_traversal }
161 Function: Return list of nodes in postorder
162 Returns : reference to array of Bio::Tree::Node
163 Args : none
164  
165 For example, the postorder traversal of the tree
166 C<(((A,B)C,D),(E,F,G));> is a reference to an array of nodes with
167 internal_id 0 through 9, because the Newick standard representation
168 for phylogenetic trees is based on a postorder traversal.
169  
170 +---A +---0
171 | |
172 +---+---C +---4---2
173 | | | | | |
174 | | +---B | | +---1
175 | | | |
176 + +-------D 9 +-------3
177 | |
178 | +-----E | +-----5
179 | | | |
180 +-----+-----F +-----8-----6
181 | |
182 +-----G +-----7
183  
184 =cut
185  
186 14 ▶sub postorder_traversal {
Subroutine postorder_traversal: called CC=3 SCAR=11.0
Pod documented
187 14 my($self) = @_;
188 14 my @stack;
189 my @queue;
190 14 push @stack, $self->get_root_node;
191 14 ▶ while (@stack) {
Branch: 1 branch
BranchTrueFalseTotal
if (@stack) 103 14 117
192 103 my $node = pop @stack;
193 103 push @queue, $node;
194 103 foreach my $child ($node->each_Descendent(-sortby => 'internal_id')) {
195 89 push @stack, $child;
196 }
197 }
198 14 my @postorder = reverse @queue;
199 14 return \@postorder;
200 }
201  
202 =head2 cluster_representation
203  
204 Title : cluster_representation
205 Usage : my %cluster = %{ $tree->cluster_representation }
206 Function: Compute the cluster representation of a tree
207 Returns : reference to hash of array of string indexed by
208 Bio::Tree::Node
209 Args : none
210  
211 For example, the cluster representation of the tree
212 C<(((A,B)C,D),(E,F,G));> is a reference to a hash associating an array
213 of string (descendent labels) to each node, as follows:
214  
215 0 --> [A]
216 1 --> [B]
217 2 --> [A,B,C]
218 3 --> [D]
219 4 --> [A,B,C,D]
220 5 --> [E]
221 6 --> [F]
222 7 --> [G]
223 8 --> [E,F,G]
224 9 --> [A,B,C,D,E,F,G]
225  
226 =cut
227  
228 4 ▶sub cluster_representation {
Subroutine cluster_representation: called CC=3 SCAR=11.0
Pod documented
229 4 my ($tree) = @_;
230 4 my %cluster;
231 4 my @postorder = @{ postorder_traversal($tree) };
232 4 foreach my $node ( @postorder ) {
233 28 my @labeled = map { $_->id } grep { $_->id } $node->get_Descendents;
234 28 ▶ push @labeled, $node->id if $node->id;
Branch: 1 branch
BranchTrueFalseTotal
if $node->id 16 12 28
235 28 $cluster{$node} = \@labeled;
236 }
237 4 return \%cluster;
238 }
239  
240 =head2 common_labels
241  
242 Title : common_labels
243 Usage : my $labels = $tree1->common_labels($tree2);
244 Function: Return set of common node labels
245 Returns : Set::Scalar
246 Args : Bio::Tree::Tree
247  
248 For example, the common labels of the tree C<(((A,B)C,D),(E,F,G));>
249 and the tree C<((A,B)H,E,(J,(K)G)I);> are: C<[A,B,E,G]>.
250  
251 +---A +---A
252 | |
253 +---+---C +-------H
254 | | | | |
255 | | +---B | +---B
256 | | |
257 + +-------D +-----------E
258 | |
259 | +-----E | +-------J
260 | | | |
261 +-----+-----F +---I
262 | |
263 +-----G +---G---K
264  
265 =cut
266  
267 3 ▶sub common_labels {
Subroutine common_labels: called CC=1 SCAR=0.0
Pod documented
268 3 my($self,$arg) = @_;
269 3 my @labels1 = map { $_->id } grep { $_->id } $self->get_nodes;
270 3 my $common = Set::Scalar->new( @labels1 );
271 3 my @labels2 = map { $_->id } grep { $_->id } $arg->get_nodes;
272 3 my $temp = Set::Scalar->new( @labels2 );
273 3 return $common->intersection($temp);
274 }
275  
276 =head2 topological_restriction
277  
278 Title : topological_restriction
279 Usage : $tree->topological_restriction($labels)
280 Function: Compute the topological restriction of a tree to a subset
281 of node labels
282 Returns : Bio::Tree::Tree
283 Args : Set::Scalar
284  
285 For example, the topological restrictions of each of the trees
286 C<(((A,B)C,D),(E,F,G));> and C<((A,B)H,E,(J,(K)G)I);> to the labels
287 C<[A,B,E,G]> are as follows:
288  
289 +---A +---A
290 | |
291 +---+---+ +---+
292 | | | |
293 | +---B | +---B
294 + |
295 | +---E +-------E
296 | | |
297 +-------+ +---+---G
298 |
299 +---G
300  
301 =cut
302  
303 6 ▶sub topological_restriction {
Subroutine topological_restriction: called CC=7 SCAR=34.4
Pod documented
304 6 my ($tree, $labels) = @_;
305 6 for my $node ( @{ postorder_traversal($tree) } ) {
306 47 ▶ unless (ref($node)) { # skip $node if already removed
Branch: 1 branch
BranchTrueFalseTotal
unless (ref $node) 0 47 47
307 0 my @cluster = map { $_->id } grep { $_->id } $node->get_Descendents;
308 0 ▶ push @cluster, $node->id if $node->id;
Branch: 1 branch
BranchTrueFalseTotal
if $node->id 0 0 0
309 0 my $cluster = Set::Scalar->new(@cluster);
310 0 ▶ if ($cluster->is_disjoint($labels)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($cluster->is_disjoint($labels)) { } 0 0 0
311 0 $tree->remove_Node($node);
312 } else {
313 0 ▶ if ($node->id and not $labels->has($node->id)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($node->id and not $labels->has($node->id)) 0 0 0
Condition0%0/3
$node->id and not $labels->has($node->id)
!ll&&!rl&&r
000
MC/DC0%0/2
$node->id and not $labels->has($node->id)
$node->id not $labels->has($node->id)
Truth table0%0/3
A and not(B)
A= $node->idB= not $labels->has($node->id)
ABresult
0X0
100
111
314 0 $node->{'_id'} = undef;
315 }
316 }
317 }
318 }
319 }
320  
321 =head2 is_compatible
322  
323 Title : is_compatible
324 Usage : $tree1->is_compatible($tree2)
325 Function: Test compatibility of two trees
326 Returns : boolean
327 Args : Bio::Tree::Tree
328  
329 For example, the topological restrictions of the trees
330 C<(((A,B)C,D),(E,F,G));> and C<((A,B)H,E,(J,(K)G)I);> to their common
331 labels, C<[A,B,E,G]>, are compatible. The respective cluster
332 representations are as follows:
333  
334 [A] [A]
335 [B] [B]
336 [E] [E]
337 [G] [G]
338 [A,B] [A,B]
339 [E,G] [A,B,E,G]
340 [A,B,E,G]
341  
342 As a second example, the trees C<(A,B);> and C<((B)A);> are
343 incompatible. Their respective cluster representations are as follows:
344  
345 [A] [B]
346 [B] [A,B]
347 [A,B]
348  
349 The reason is, the smallest cluster containing label C<A> is C<[A]> in
350 the first tree but C<[A,B]> in the second tree.
351  
352 +---A A---B
353 |
354 +
355 |
356 +---B
357  
358 As a second example, the trees C<(((B,A),C),D);> and C<((A,(D,B)),C);>
359 are also incompatible. Their respective cluster representations are as
360 follows:
361  
362 [A] [A]
363 [B] [B]
364 [C] [C]
365 [D] [D]
366 [A,B] [B,D]
367 [A,B,C] [A,B,D]
368 [A,B,C,D] [A,B,C,D]
369  
370 The reason is, cluster C<[A,B]> properly intersects cluster
371 C<[B,D]>. There are further incompatibilities between these trees:
372 C<[A,B,C]> properly intersects both C<[B,D]> and C<[A,B,D]>.
373  
374 +---B +-------A
375 | |
376 +---+ +---+ +---D
377 | | | | |
378 +---+ +---A | +---+
379 | | + |
380 + +-------C | +---B
381 | |
382 +-----------D +-----------C
383  
384 =cut
385  
386 2 ▶sub is_compatible {
Subroutine is_compatible: called CC=6 SCAR=17.9
Pod documented
387 2 my ($tree1, $tree2) = @_;
388 2 my $common = $tree1->Bio::Tree::Compatible::common_labels($tree2);
389 2 $tree1->Bio::Tree::Compatible::topological_restriction($common);
390 2 $tree2->Bio::Tree::Compatible::topological_restriction($common);
391 2 my @postorder1 = @{ postorder_traversal($tree1) };
392 2 my @postorder2 = @{ postorder_traversal($tree2) };
393 2 my %cluster1 = %{ cluster_representation($tree1) };
394 2 my %cluster2 = %{ cluster_representation($tree2) };
395 2 my $incompat = 0; # false
396 2 my @labels;
397 2 foreach my $label ( $common->elements ) {
398 8 my $node1 = $tree1->find_node(-id => $label);
399 8 my @labels1 = @{ $cluster1{$node1} };
400 8 my $cluster1 = Set::Scalar->new(@labels1);
401 8 my $node2 = $tree2->find_node(-id => $label);
402 8 my @labels2 = @{ $cluster2{$node2} };
403 8 my $cluster2 = Set::Scalar->new(@labels2);
404 8 ▶ unless ( $cluster1->is_equal($cluster2) ) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($cluster1->is_equal($cluster2)) 0 8 8
405 0 $incompat = 1; # true
406 0 push @labels, $label;
407 }
408 }
409 2 my @nodes;
410 2 foreach my $node1 ( @postorder1 ) {
411 14 my @labels1 = @{ $cluster1{$node1} };
412 14 my $cluster1 = Set::Scalar->new(@labels1);
413 14 foreach my $node2 ( @postorder2 ) {
414 98 my @labels2 = @{$cluster2{$node2} };
415 98 my $cluster2 = Set::Scalar->new(@labels2);
416 98 ▶ if ($cluster1->is_properly_intersecting($cluster2)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($cluster1->is_properly_intersecting($cluster2)) 3 95 98
417 3 $incompat = 1; # true
418 3 push @nodes, $node1, $node2;
419 }
420 }
421 }
422 2 return ($incompat, \@labels, \@nodes);
423 }
424  
425 2 1;
« Bio/Seq/SimulatedRead.pm ↑ Summary Bio/Tools/Est2Genome.pm »