Bio/Tree/TreeFunctionsI.pm

filter: Statementstmt 66.9% 283 / 423 Branchbran 52.2% 115 / 220 Conditioncond 48.8% 43 / 88 MC/DCmcdc 23.6% 13 / 55 Subroutinesub 80.7% 21 / 26 Podpod 100% 19 / 19 totaltotal 59.4% 494 / 831 CC 167 SCAR 35.3
CC
167
Cov
60%
distance
132.0
merge_lineage
110.0
splice
64.3
CRAP 34.0
« Bio/Search/Hit/GenericHit.pm ↑ Summary Bio/Index/Swissprot.pm »
1 #
2 # BioPerl module for Bio::Tree::TreeFunctionsI
3 #
4 # Please direct questions and support issues to <bioperl-l@bioperl.org>
5 #
6 # Cared for by Jason Stajich <jason-at-bioperl-dot-org>
7 #
8 # Copyright Jason Stajich
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  
15 =head1 NAME
16  
17 Bio::Tree::TreeFunctionsI - Decorated Interface implementing basic Tree exploration methods
18  
19 =head1 SYNOPSIS
20  
21 use Bio::TreeIO;
22 my $in = Bio::TreeIO->new(-format => 'newick', -file => 'tree.tre');
23  
24 my $tree = $in->next_tree;
25  
26 my @nodes = $tree->find_node('id1');
27  
28 if( $tree->is_monophyletic(-nodes => \@nodes, -outgroup => $outnode) ){
29 #...
30 }
31  
32 =head1 DESCRIPTION
33  
34 This interface provides a set of implemented Tree functions which
35 only use the defined methods in the TreeI or NodeI interface.
36  
37 =head1 FEEDBACK
38  
39 =head2 Mailing Lists
40  
41 User feedback is an integral part of the evolution of this and other
42 Bioperl modules. Send your comments and suggestions preferably to
43 the Bioperl mailing list. Your participation is much appreciated.
44  
45 bioperl-l@bioperl.org - General discussion
46 http://bioperl.org/wiki/Mailing_lists - About the mailing lists
47  
48 =head2 Support
49  
50 Please direct usage questions or support issues to the mailing list:
51  
52 I<bioperl-l@bioperl.org>
53  
54 rather than to the module maintainer directly. Many experienced and
55 reponsive experts will be able look at the problem and quickly
56 address it. Please include a thorough description of the problem
57 with code and data examples if at all possible.
58  
59 =head2 Reporting Bugs
60  
61 Report bugs to the Bioperl bug tracking system to help us keep track
62 of the bugs and their resolution. Bug reports can be submitted via the
63 web:
64  
65 https://github.com/bioperl/bioperl-live/issues
66  
67 =head1 AUTHOR - Jason Stajich, Aaron Mackey, Justin Reese
68  
69 Email jason-at-bioperl-dot-org
70 Email amackey-at-virginia.edu
71 Email jtr4v-at-virginia.edu
72  
73 =head1 CONTRIBUTORS
74  
75 Sendu Bala, bix@sendu.me.uk
76  
77 Rerooting code was worked on by
78  
79 Daniel Barker d.barker-at-reading.ac.uk
80 Ramiro Barrantes Ramiro.Barrantes-at-uvm.edu
81  
82 =head1 APPENDIX
83  
84 The rest of the documentation details each of the object methods.
85 Internal methods are usually preceded with a _
86  
87 =cut
88  
89 # Let the code begin...
90  
91  
92 package Bio::Tree::TreeFunctionsI;
93 80 $Bio::Tree::TreeFunctionsI::VERSION = '1.7.8';
94 80 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
95 80 ▶use base qw(Bio::Tree::TreeI);
Subroutine BEGIN: called CC=1 SCAR=0.0
96  
97 80 ▶use Carp;
Subroutine BEGIN: called CC=1 SCAR=0.0
98  
99 =head2 find_node
100  
101 Title : find_node
102 Usage : my @nodes = $self->find_node(-id => 'node1');
103 Function: returns all nodes that match a specific field, by default this
104 is id, but different branch_length,
105 Returns : List of nodes which matched search
106 Args : text string to search for
107 OR
108 -fieldname => $textstring
109  
110 =cut
111  
112 213 ▶sub find_node {
Subroutine find_node: called CC=7 SCAR=19.8
Pod documented
113 213 my ($self, $type, $field) = @_;
114 213 ▶ if( ! defined $type ) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $type) 0 213 213
115 0 $self->warn("Must request a either a string or field and string when searching");
116 }
117  
118 # all this work for a '-' named field
119 # is so that we could potentially
120 # expand to other constraints in
121 # different implementations
122 # like 'find all nodes with boostrap < XX'
123  
124 213 ▶ if( ! defined $field ) {
Branch: 1 branch
BranchTrueFalseTotal
if (not defined $field) { } 46 167 213
125 # only 1 argument, default to searching by id
126 46 $field = $type;
127 46 $type = 'id';
128 } else {
129 167 $type =~ s/^-//;
130 }
131  
132 # could actually do this by testing $rootnode->can($type) but
133 # it is possible that a tree is implemented with different node types
134 # - although it is unlikely that the root node would be richer than the
135 # leaf nodes. Can't handle NHX tags right now
136  
137 213 ▶ my @nodes = grep { $_->can($type) && defined $_->$type() &&
Condition83%5/6
$_->can($type) && defined $_->$type && $_->$type eq $field
!ll&&!rl&&r
8922636199
$_->can($type) and defined $_->$type
!ll&&!rl&&r
08922835
MC/DC66%2/3
$_->can($type) && defined $_->$type && $_->$type eq $field
$_->can($type) defined $_->$type $_->$type eq $field
Truth table75%3/4
A and B && C
A= $_->can($type)B= defined $_->$typeC= $_->$type eq $field
ABCresult
0XX0
10X0
1100
1111
138 $_->$type() eq $field } $self->get_nodes();
139  
140 213 ▶ if ( wantarray) {
Branch: 1 branch
BranchTrueFalseTotal
if (wantarray) { } 59 154 213
141 59 return @nodes;
142 } else {
143 154 ▶ if( @nodes > 1 ) {
Branch: 1 branch
BranchTrueFalseTotal
if (@nodes > 1) 0 154 154
144 0 $self->warn("More than 1 node found but caller requested scalar, only returning first node");
145 }
146 154 return shift @nodes;
147 }
148 }
149  
150  
151 =head2 remove_Node
152  
153 Title : remove_Node
154 Usage : $tree->remove_Node($node)
155 Function: Removes a node from the tree
156 Returns : boolean represent status of success
157 Args : either Bio::Tree::NodeI or string of the node id
158  
159 =cut
160  
161 1 ▶sub remove_Node {
Subroutine remove_Node: called CC=5 SCAR=21.6
Pod documented
162 1 my ($self,$input) = @_;
163 1 my $node = undef;
164 1 ▶ unless( ref($input) ) {
Branch: 2 branches
BranchTrueFalseTotal
if (ref $input) { } 0 1 1
if (do { not $input->isa('Bio::Tree::NodeI') }) { } 0 0 0
165 1 $node = $self->find_node($input);
166 } elsif( ! $input->isa('Bio::Tree::NodeI') ) {
167 0 $self->warn("Did not provide either a valid Bio::Tree::NodeI object or id to remove_node");
168 0 return 0;
169 } else {
170 0 $node = $input;
171 }
172 1 ▶ if( ! $node->ancestor &&
Branch: 1 branch
BranchTrueFalseTotal
if (not $node->ancestor and $self->get_root_node->internal_id != $node->internal_id) { } 0 1 1
Condition33%1/3
not $node->ancestor and $self->get_root_node->internal_id != $node->internal_id
!ll&&!rl&&r
100
MC/DC0%0/2
not $node->ancestor and $self->get_root_node->internal_id != $node->internal_id
not $node->ancestor $self->get_root_node->internal_id != $node->internal_id
Truth table33%1/3
not(A) and B
A= not $node->ancestorB= $self->get_root_node->internal_id != $node->internal_id
ABresult
0X0
100
111
173 $self->get_root_node->internal_id != $node->internal_id) {
174 0 $self->warn("Node (".$node->to_string . ") has no ancestor, can't remove!");
175 } else {
176 1 $node->ancestor->remove_Descendent($node);
177 }
178 }
179  
180  
181 =head2 get_lineage_nodes
182  
183 Title : get_lineage_nodes
184 Usage : my @nodes = $tree->get_lineage_nodes($node);
185 Function: Given a node or its ID, get its full lineage, i.e. all its ancestors,
186 from the root to the most recent ancestor. Only use the node ID as
187 input if the nodes have been added to the tree.
188 Returns : list of nodes
189 Args : either Bio::Tree::NodeI (or string of the node id)
190  
191 =cut
192  
193 510 ▶sub get_lineage_nodes {
Subroutine get_lineage_nodes: called CC=7 SCAR=19.9
Pod documented
194 510 my ($self, $input) = @_;
195 510 my $node;
196  
197 # Sanity checks
198 510 ▶ if (ref $input) {
Branch: 1 branch
BranchTrueFalseTotal
if (ref $input) { } 510 0 510
199 510 ▶ if (not $input->isa('Bio::Tree::NodeI')) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($input->isa("Bio::Tree::NodeI")) 0 510 510
200 0 $self->throw("Did not provide a valid Bio::Tree::NodeI object or ID string to get_lineage_nodes");
201 }
202 510 $node = $input;
203 } else {
204 0 $node = $self->find_node($input);
205 }
206  
207 # When dealing with Bio::Taxon objects with databases, the root will always
208 # be the database's root, ignoring this Tree's set root node; prefer the
209 # Tree's idea of root.
210 510 ▶ my $root = $self->get_root_node || '';
Condition100%2/2
$self->get_root_node || ''
l!l
295215
MC/DC100%1/1
$self->get_root_node || ''
$self->get_root_node
Truth table100%2/2
A
A= $self->get_root_node
Aresult
11
00
211  
212 510 my @lineage;
213 510 ▶ while ($node) {
Branch: 1 branch
BranchTrueFalseTotal
if ($node) 4596 0 4596
214 4596 ▶ $node = $node->ancestor || last;
Condition100%2/2
$node->ancestor || (last)
l!l
4378218
MC/DC100%1/1
$node->ancestor || (last)
$node->ancestor
Truth table100%2/2
A
A= $node->ancestor
Aresult
11
00
215 4378 unshift(@lineage, $node);
216 4378 ▶ $node eq $root && last;
Branch: 1 branch
BranchTrueFalseTotal
$node eq $root and last 292 4086 4378
217 }
218 510 return @lineage;
219 }
220  
221  
222 =head2 get_lineage_string
223  
224 Title : get_lineage_string
225 Usage : my $lineage = $tree->get_lineage_string($node);
226 Function: Get the string representation of the full lineage of a node, e.g.
227 for the Enterobacteriales node, return
228 Bacteria;Proteobacteria;Gammaproteobacteria;Enterobacteriales.
229 This method uses get_lineage_nodes internally and therefore inherits
230 of all of its caveats.
231 Returns : string
232 Args : * either Bio::Tree::NodeI (or string of the node id)
233 * an optional separator (default: ';')
234  
235 =cut
236  
237 0 ▶sub get_lineage_string {
Subroutine get_lineage_string: not called CC=7 SCAR=40.3
Pod documented
238 0 my ($self, $input, $sep) = @_;
239 0 ▶ $sep ||= ';';
Condition0%0/2
$sep ||= ";"
l!l
00
MC/DC0%0/1
$sep ||= ";"
$sep
Truth table0%0/2
A
A= $sep
Aresult
11
00
240 0 my $node;
241 0 ▶ unless (ref $input) {
Branch: 2 branches
BranchTrueFalseTotal
if (ref $input) { } 0 0 0
if (do { not $input->isa('Bio::Tree::NodeI') }) { } 0 0 0
242 0 $node = $self->find_node($input);
243 }
244 elsif (! $input->isa('Bio::Tree::NodeI')) {
245 0 $self->warn("Did not provide either a valid Bio::Tree::NodeI object or id to get_lineage_nodes");
246 0 return;
247 }
248 else {
249 0 $node = $input;
250 }
251 0 my @nodes = ($self->get_lineage_nodes($node), $node);
252 0 for my $i (0 .. scalar @nodes - 1) {
253 0 ▶ my $node_name = $nodes[$i]->node_name || '';
Condition0%0/2
$nodes[$i]->node_name || ''
l!l
00
MC/DC0%0/1
$nodes[$i]->node_name || ''
$nodes[$i]->node_name
Truth table0%0/2
A
A= $nodes[$i]->node_name
Aresult
11
00
254 0 ▶ if ($node_name =~ m/$sep/) {
Branch: 1 branch
BranchTrueFalseTotal
if ($node_name =~ /$sep/) 0 0 0
255 0 $self->warn("Separator '$sep' is not safe to use because the node ".
256 "called '$node_name' contains it. Consider using another separator".
257 " or sanitizing the node name.");
258 }
259 0 $nodes[$i] = $node_name;
260 }
261 0 return join $sep, @nodes;
262 }
263  
264  
265 =head2 splice
266  
267 Title : splice
268 Usage : $tree->splice(-remove_id => \@ids);
269 Function: Remove all the nodes from a tree that correspond to the supplied
270 args, making all the descendents of a removed node the descendents
271 of the removed node's ancestor.
272 You can ask to explicitly remove certain nodes by using -remove_*,
273 remove them conditionally by using -remove_* in combination with
274 -keep_*, or remove everything except certain nodes by using only
275 -keep_*.
276 Returns : n/a
277 Args : just a list of Bio::Tree::NodeI objects to remove, OR
278 -key => value pairs, where -key has the prefix 'remove' or 'keep',
279 followed by an underscore, followed by a fieldname (like for the
280 method find_node). Value should be a scalar or an array ref of
281 scalars (again, like you might supply to find_node).
282  
283 So (-remove_id => [1, 2]) will remove all nodes from the tree that
284 have an id() of '1' or '2', while
285 (-remove_id => [1, 2], -keep_id => [2]) will remove all nodes with
286 an id() of '1'.
287 (-keep_id => [2]) will remove all nodes unless they have an id() of
288 '2' (note, no -remove_*).
289  
290 -preserve_lengths => 1 : setting this argument will splice out
291 intermediate nodes, preserving the original total length between
292 the ancestor and the descendants of the spliced node. Undef
293 by default.
294  
295 =cut
296  
297 4 ▶sub splice {
Subroutine splice: called CC=27 SCAR=41.6
Pod documented
298 4 my ($self, @args) = @_;
299 4 ▶ $self->throw("Must supply some arguments") unless @args > 0;
Branch: 1 branch
BranchTrueFalseTotal
unless @args > 0 0 4 4
300 4 my $preserve_lengths = 0;
301 4 my @nodes_to_remove;
302 4 ▶ if (ref($args[0])) {
Branch: 1 branch
BranchTrueFalseTotal
if (ref $args[0]) { } 0 4 4
303 0 ▶ $self->throw("When supplying just a list of Nodes, they must be Bio::Tree::NodeI objects") unless $args[0]->isa('Bio::Tree::NodeI');
Branch: 1 branch
BranchTrueFalseTotal
unless $args[0]->isa("Bio::Tree::NodeI") 0 0 0
304 0 @nodes_to_remove = @args;
305 }
306 else {
307 4 ▶ $self->throw("When supplying -key => value pairs, must be an even number of args") unless @args % 2 == 0;
Branch: 1 branch
BranchTrueFalseTotal
unless @args % 2 == 0 0 4 4
308 4 my %args = @args;
309 4 my @keep_nodes;
310 my @remove_nodes;
311 4 my $remove_all = 1;
312 4 ▶ while (my ($key, $value) = each %args) {
Branch: 1 branch
BranchTrueFalseTotal
if (() = each %args) 5 4 9
313 5 ▶ my @values = ref($value) ? @{$value} : ($value);
Branch: 1 branch
BranchTrueFalseTotal
ref $value ? : 2 3 5
314  
315 5 ▶ if ($key =~ s/remove_//) {
Branch: 3 branches
BranchTrueFalseTotal
if ($key =~ s/remove_//) { } 3 2 5
elsif ($key =~ s/keep_//) { } 2 0 2
elsif ($key =~ /preserve/) { } 0 0 0
316 3 $remove_all = 0;
317 3 foreach my $value (@values) {
318 4 push(@remove_nodes, $self->find_node($key => $value));
319 }
320 }
321 elsif ($key =~ s/keep_//) {
322 2 foreach my $value (@values) {
323 8 push(@keep_nodes, $self->find_node($key => $value));
324 }
325 }
326 elsif ($key =~ /preserve/) {
327 0 $preserve_lengths = $value;
328 }
329 }
330  
331 4 ▶ if ($remove_all) {
Branch: 1 branch
BranchTrueFalseTotal
if ($remove_all) 1 3 4
332 1 ▶ if (@keep_nodes == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (@keep_nodes == 0) 0 1 1
333 0 $self->warn("Requested to remove everything except certain nodes, but those nodes were not found; doing nothing instead");
334 0 return;
335 }
336  
337 1 @remove_nodes = $self->get_nodes;
338 }
339 4 ▶ if (@keep_nodes > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (@keep_nodes > 0) { } 2 2 4
340 2 my %keep_iids = map { $_->internal_id => 1 } @keep_nodes;
341 2 foreach my $node (@remove_nodes) {
342 11 ▶ push(@nodes_to_remove, $node) unless exists $keep_iids{$node->internal_id};
Branch: 1 branch
BranchTrueFalseTotal
unless exists $keep_iids{$node->internal_id} 3 8 11
343 }
344 }
345 else {
346 2 @nodes_to_remove = @remove_nodes;
347 }
348 }
349 # do the splicing
350 #*** the algorithm here hasn't really been thought through and tested much,
351 # will probably need revising
352 4 my %root_descs;
353 4 my $reroot = 0;
354 4 foreach my $node (@nodes_to_remove) {
355 5 my @descs = $node->each_Descendent;
356 5 my $ancestor = $node->ancestor;
357 5 ▶ if (! $ancestor && ! $reroot) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($ancestor or $reroot) 0 5 5
Condition33%1/3
$ancestor or $reroot
l!l&&r!l&&!r
500
MC/DC0%0/2
$ancestor or $reroot
$ancestor $reroot
Truth table33%1/3
A or B
A= $ancestorB= $reroot
ABresult
1X1
011
000
358 # we're going to remove the tree root, so will have to re-root the
359 # tree later
360 0 $reroot = 1;
361 0 %root_descs = map { $_->internal_id => $_ } @descs;
362 0 $node->remove_all_Descendents;
363 0 next;
364 }
365 5 ▶ if (exists $root_descs{$node->internal_id}) {
Branch: 1 branch
BranchTrueFalseTotal
if (exists $root_descs{$node->internal_id}) 0 5 5
366 # well, this one can't be the future root anymore
367 0 delete $root_descs{$node->internal_id};
368 # but maybe one of this one's descs will become the root
369 0 foreach my $desc (@descs) {
370 0 $root_descs{$desc->internal_id} = $desc;
371 }
372 }
373 # make the ancestor of our descendents our own ancestor, and give us
374 # no ancestor of our own to remove us from the tree
375 5 foreach my $desc (@descs) {
376 2 $desc->ancestor($ancestor);
377 2 ▶ $desc->branch_length($desc->branch_length + $node->branch_length) if $preserve_lengths;
Branch: 1 branch
BranchTrueFalseTotal
if $preserve_lengths 0 2 2
378 }
379 5 $node->ancestor(undef);
380 }
381 4 ▶ if ($reroot) {
Branch: 1 branch
BranchTrueFalseTotal
if ($reroot) 0 4 4
382 0 my @candidates = values %root_descs;
383 0 ▶ $self->throw("After splicing, there was no tree root!") unless @candidates > 0;
Branch: 1 branch
BranchTrueFalseTotal
unless @candidates > 0 0 0 0
384 0 ▶ $self->throw("After splicing, the original root was removed but there are multiple candidates for the new root!") unless @candidates == 1;
Branch: 1 branch
BranchTrueFalseTotal
unless @candidates == 1 0 0 0
385 0 $self->set_root_node($candidates[0]); # not sure its valid to use the reroot() method
386 }
387 }
388  
389  
390 =head2 get_lca
391  
392 Title : get_lca
393 Usage : get_lca(-nodes => \@nodes ); OR
394 get_lca(@nodes);
395 Function: given two or more nodes, returns the lowest common ancestor (aka most
396 recent common ancestor)
397 Returns : node object or undef if there is no common ancestor
398 Args : -nodes => arrayref of nodes to test, OR
399 just a list of nodes
400  
401 =cut
402  
403 10 ▶sub get_lca {
Subroutine get_lca: called CC=15 SCAR=28.6
Pod documented
404 10 my ($self, @args) = @_;
405 10 my ($nodes) = $self->_rearrange([qw(NODES)],@args);
406 10 my @nodes;
407 10 ▶ if (ref($nodes) eq 'ARRAY') {
Branch: 1 branch
BranchTrueFalseTotal
if (ref $nodes eq 'ARRAY') { } 2 8 10
408 2 @nodes = @{$nodes};
409 }
410 else {
411 8 @nodes = @args;
412 }
413 10 ▶ @nodes >= 2 or $self->throw("At least 2 nodes are required");
Branch: 1 branch
BranchTrueFalseTotal
@nodes >= 2 or $self->throw("At least 2 nodes are required") 10 0 10
414 # We must go root->leaf to get the correct answer to lca (in a world where
415 # internal_id might not be uniquely assigned), but leaf->root is more
416 # forgiving (eg. lineages may not all have the same root, or they may have
417 # different numbers of 'minor' taxa inbeteen 'major' ones).
418 #
419 # I use root->leaf so that we can easily do multiple nodes at once - no
420 # matter what taxa are below the lca, the lca and all its ancestors ought to
421 # be identical.
422 10 my @paths;
423 10 foreach my $node (@nodes) {
424 23 ▶ unless(ref($node) && $node->isa('Bio::Tree::NodeI')) {
Branch: 1 branch
BranchTrueFalseTotal
unless (ref $node and $node->isa("Bio::Tree::NodeI")) 0 23 23
Condition33%1/3
ref $node and $node->isa("Bio::Tree::NodeI")
!ll&&!rl&&r
0023
MC/DC0%0/2
ref $node and $node->isa("Bio::Tree::NodeI")
ref $node $node->isa("Bio::Tree::NodeI")
Truth table33%1/3
A and B
A= ref $nodeB= $node->isa("Bio::Tree::NodeI")
ABresult
0X0
100
111
425 0 $self->throw("Cannot process get_lca() with a non-NodeI object ($node)\n");
426 }
427 23 my @path = ($self->get_lineage_nodes($node), $node);
428 23 push(@paths, \@path);
429 }
430 10 ▶ return unless @paths >= 2;
Branch: 1 branch
BranchTrueFalseTotal
unless @paths >= 2 0 10 10
431 10 my $lca;
432 10 ▶ LEVEL: while ($paths[0] > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($paths[0] > 0) 34 0 34
433 34 my %node_ids;
434 my $node;
435 34 foreach my $path (@paths) {
436 78 ▶ $node = shift(@{$path}) || last LEVEL;
Condition50%1/2
shift @{$path;} || (last LEVEL)
l!l
780
MC/DC0%0/1
shift @{$path;} || (last LEVEL)
shift @{$path;}
Truth table50%1/2
A
A= shift @{$path;}
Aresult
11
00
437 78 my $node_id = $node->internal_id;
438 78 ▶ unless (defined $node_id) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $node_id) 0 78 78
439 0 $self->warn("One of the lineages had a node with no internal_id, can't calculate the common ancestor");
440 0 return;
441 }
442 78 $node_ids{$node_id}++;
443 }
444 34 ▶ if (keys %node_ids == 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (keys %node_ids == 1) { } 24 10 34
445 24 $lca = $node;
446 }
447 else {
448 # at this point in the lineage the nodes are different; the previous
449 # loop had the lca
450 10 last LEVEL;
451 }
452 }
453 # If the tree that we are contains the lca (get_lca could have been called
454 # on an empty tree, since it works with plain Nodes), prefer to return the
455 # node object that belongs to us
456 10 ▶ if ($lca && $self->number_nodes > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($lca and $self->number_nodes > 0) 8 2 10
Condition66%2/3
$lca and $self->number_nodes > 0
!ll&&!rl&&r
028
MC/DC50%1/2
$lca and $self->number_nodes > 0
$lca $self->number_nodes > 0
Truth table66%2/3
A and B
A= $lcaB= $self->number_nodes > 0
ABresult
0X0
100
111
457 8 my $own_lca = $self->find_node(-internal_id => $lca->internal_id);
458 8 ▶ $lca = $own_lca if $own_lca;
Branch: 1 branch
BranchTrueFalseTotal
if $own_lca 8 0 8
459 }
460 10 return $lca;
461 }
462  
463  
464 =head2 merge_lineage
465  
466 Title : merge_lineage
467 Usage : merge_lineage($node)
468 Function: Merge a lineage of nodes with this tree.
469 Returns : true for success, false (and a warning) otherwise
470 Args : Bio::Tree::TreeI with only one leaf, OR
471 Bio::Tree::NodeI which has an ancestor
472  
473 For example, if we are the tree $tree:
474  
475 +---B
476 |
477 A
478 |
479 +---C
480  
481 and we want to merge the lineage $other_tree:
482  
483 A---C---D
484  
485 After calling $tree->merge_lineage($other_tree), $tree looks like:
486  
487 +---B
488 |
489 A
490 |
491 +---C---D
492  
493 =cut
494  
495 0 ▶sub merge_lineage {
Subroutine merge_lineage: not called CC=10 SCAR=47.0
Pod documented
496 0 my ($self, $thing) = @_;
497 0 ▶ $self->throw("Must supply an object reference") unless ref($thing);
Branch: 1 branch
BranchTrueFalseTotal
unless ref $thing 0 0 0
498  
499 0 my $lineage_leaf;
500 0 ▶ if ($thing->isa('Bio::Tree::TreeI')) {
Branch: 2 branches
BranchTrueFalseTotal
if ($thing->isa('Bio::Tree::TreeI')) { } 0 0 0
elsif ($thing->isa('Bio::Tree::NodeI')) { } 0 0 0
501 0 my @leaves = $thing->get_leaf_nodes;
502 0 ▶ $self->throw("The supplied Tree can only have one leaf") unless @leaves == 1;
Branch: 1 branch
BranchTrueFalseTotal
unless @leaves == 1 0 0 0
503 0 $lineage_leaf = shift(@leaves);
504 }
505 elsif ($thing->isa('Bio::Tree::NodeI')) {
506 0 ▶ $self->throw("The supplied Node must have an ancestor") unless $thing->ancestor;
Branch: 1 branch
BranchTrueFalseTotal
unless $thing->ancestor 0 0 0
507 0 $lineage_leaf = $thing;
508 }
509  
510 # Find the lowest node in the supplied lineage that is in the tree
511 # That will be our lca and we can merge at the node below
512 0 my @lineage = ($lineage_leaf, reverse($self->get_lineage_nodes($lineage_leaf)));
513 0 my $merged = 0;
514 0 my $node;
515 0 my $i = 0;
516 0 ▶ while ($i <= $#lineage) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i <= $#lineage) 0 0 0
517 0 $node = $self->find_node(-internal_id => $lineage[$i]->internal_id);
518 0 ▶ if (defined $node) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $node) 0 0 0
519 0 $merged = 1;
520 0 last;
521 }
522 0 $i++;
523 }
524 0 ▶ if (not $merged) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($merged) 0 0 0
525 0 $self->warn("Could not merge the lineage of ".$lineage_leaf->id." with the rest of the tree");
526 }
527  
528 # Merge descendents, recursively
529 0 ▶ while ($i > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i > 0) 0 0 0
530 0 $node->add_Descendent($lineage[$i-1]);
531 0 $node = $self->find_node(-internal_id => $lineage[$i-1]->internal_id);
532 0 $i--;
533 }
534  
535 0 return $merged;
536 }
537  
538  
539 =head2 contract_linear_paths
540  
541 Title : contract_linear_paths
542 Usage : contract_linear_paths()
543 Function: Splices out all nodes in the tree that have an ancestor and only one
544 descendent.
545 Returns : n/a
546 Args : none for normal behaviour, true to dis-regard the ancestor requirement
547 and re-root the tree as necessary
548  
549 For example, if we are the tree $tree:
550  
551 +---E
552 |
553 A---B---C---D
554 |
555 +---F
556  
557 After calling $tree->contract_linear_paths(), $tree looks like:
558  
559 +---E
560 |
561 A---D
562 |
563 +---F
564  
565 Instead, $tree->contract_linear_paths(1) would have given:
566  
567 +---E
568 |
569 D
570 |
571 +---F
572  
573 =cut
574  
575 6 ▶sub contract_linear_paths {
Subroutine contract_linear_paths: called CC=7 SCAR=22.3
Pod documented
576 6 my $self = shift;
577 6 my $reroot = shift;
578 6 my @remove;
579 6 foreach my $node ($self->get_nodes) {
580 30 ▶ if ($node->ancestor && $node->each_Descendent == 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($node->ancestor and $node->each_Descendent == 1) 0 30 30
Condition66%2/3
$node->ancestor and $node->each_Descendent == 1
!ll&&!rl&&r
6240
MC/DC0%0/2
$node->ancestor and $node->each_Descendent == 1
$node->ancestor $node->each_Descendent == 1
Truth table66%2/3
A and B
A= $node->ancestorB= $node->each_Descendent == 1
ABresult
0X0
100
111
581 0 push(@remove, $node);
582 }
583 }
584 6 ▶ $self->splice(@remove) if @remove;
Branch: 1 branch
BranchTrueFalseTotal
if @remove 0 6 6
585 6 ▶ if ($reroot) {
Branch: 1 branch
BranchTrueFalseTotal
if ($reroot) 6 0 6
586 6 my $root = $self->get_root_node;
587 6 my @descs = $root->each_Descendent;
588 6 ▶ if (@descs == 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (@descs == 1) 0 6 6
589 0 my $new_root = shift(@descs);
590 0 $self->set_root_node($new_root);
591 0 $new_root->ancestor(undef);
592 }
593 }
594 }
595  
596  
597 =head2 is_binary
598  
599 Example : is_binary(); is_binary($node);
600 Description: Finds if the tree or subtree defined by
601 the internal node is a true binary tree
602 without polytomies
603 Returns : boolean
604 Exceptions :
605 Args : Internal node Bio::Tree::NodeI, optional
606  
607  
608 =cut
609  
610 41 ▶sub is_binary {
Subroutine is_binary: called CC=6 SCAR=17.9
Pod documented
611 41 my $self = shift;
612 41 ▶ my $node = shift || $self->get_root_node;
Condition66%2/3
shift() || $self->get_root_node
l!l&&r!l&&!r
3920
MC/DC0%0/2
shift() || $self->get_root_node
shift() $self->get_root_node
Truth table66%2/3
A || B
A= shift()B= $self->get_root_node
ABresult
1X1
011
000
613  
614 41 my $binary = 1;
615 41 my @descs = $node->each_Descendent;
616 41 ▶ $binary = 0 unless @descs == 2 or @descs == 0;
Branch: 1 branch
BranchTrueFalseTotal
unless @descs == 2 or @descs == 0 4 37 41
Condition100%3/3
@descs == 2 or @descs == 0
l!l&&r!l&&!r
12254
MC/DC100%2/2
@descs == 2 or @descs == 0
@descs == 2 @descs == 0
Truth table100%3/3
A or B
A= @descs == 2B= @descs == 0
ABresult
1X1
011
000
617 #print "$binary, ", scalar @descs, "\n";
618  
619 # recurse
620 41 foreach my $desc (@descs) {
621 38 $binary += $self->is_binary($desc) -1;
622 }
623 41 ▶ $binary = 0 if $binary < 0;
Branch: 1 branch
BranchTrueFalseTotal
if $binary < 0 2 39 41
624 41 return $binary;
625 }
626  
627  
628 =head2 force_binary
629  
630 Title : force_binary
631 Usage : force_binary()
632 Function: Forces the tree into a binary tree, splitting branches arbitrarily
633 and creating extra nodes as necessary, such that all nodes have
634 exactly two or zero descendants.
635 Returns : n/a
636 Args : none
637  
638 For example, if we are the tree $tree:
639  
640 +---G
641 |
642 +---F
643 |
644 +---E
645 |
646 A
647 |
648 +---D
649 |
650 +---C
651 |
652 +---B
653  
654 (A has 6 descendants B-G)
655  
656 After calling $tree->force_binary(), $tree looks like:
657  
658 +---X
659 |
660 +---X
661 | |
662 | +---X
663 |
664 +---X
665 | |
666 | | +---G
667 | | |
668 | +---X
669 | |
670 | +---F
671 A
672 | +---E
673 | |
674 | +---X
675 | | |
676 | | +---D
677 | |
678 +---X
679 |
680 | +---C
681 | |
682 +---X
683 |
684 +---B
685  
686 (Where X are artificially created nodes with ids 'artificial_n', where n is
687 an integer making the id unique within the tree)
688  
689 =cut
690  
691 42 ▶sub force_binary {
Subroutine force_binary: called CC=13 SCAR=26.0
Pod documented
692 42 my $self = shift;
693 42 ▶ my $node = shift || $self->get_root_node;
Condition66%2/3
shift() || $self->get_root_node
l!l&&r!l&&!r
3570
MC/DC0%0/2
shift() || $self->get_root_node
shift() $self->get_root_node
Truth table66%2/3
A || B
A= shift()B= $self->get_root_node
ABresult
1X1
011
000
694  
695 42 my @descs = $node->each_Descendent;
696 42 ▶ if (@descs > 2) {
Branch: 2 branches
BranchTrueFalseTotal
if (@descs > 2) { } 2 40 42
elsif (@descs == 1) { } 0 40 40
697 # Removed overly verbose warning - cjfields 3-12-11
698
699 # Many nodes have no identifying names, a simple warning is probably
700 # enough.
701  
702 2 $self->warn("Node has more than two descendants\nWill do an arbitrary balanced split");
703 2 my @working = @descs;
704 # create an even set of artifical nodes on which to later hang the descs
705 2 my $half = @working / 2;
706 2 ▶ $half++ if $half > int($half);
Branch: 1 branch
BranchTrueFalseTotal
if $half > int $half 1 1 2
707 2 $half = int($half);
708 2 my @artificials;
709 2 ▶ while ($half > 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($half > 1) 2 2 4
710 2 my @this_level;
711 2 ▶ foreach my $top_node (@artificials || $node) {
Condition33%1/3
@artificials || $node
l!l&&r!l&&!r
020
MC/DC0%0/2
@artificials || $node
@artificials $node
Truth table33%1/3
A || B
A= @artificialsB= $node
ABresult
1X1
011
000
712 2 for (1..2) {
713 4 my $art = $top_node->new(-id => "artificial_".++$self->{_art_num});
714 4 $top_node->add_Descendent($art);
715 4 push(@this_level, $art);
716 }
717 }
718 2 @artificials = @this_level;
719 2 $half--;
720 }
721 # attach two descs to each artifical leaf
722 2 foreach my $art (@artificials) {
723 4 for (1..2) {
724 8 ▶ my $desc = shift(@working) || $node->new(-id => "artificial_".++$self->{_art_num});
Condition66%2/3
shift @working || $node->new('-id', 'artificial_' . ++$self->{'_art_num'})
l!l&&r!l&&!r
710
MC/DC0%0/2
shift @working || $node->new('-id', 'artificial_' . ++$self->{'_art_num'})
shift @working $node->new('-id', 'artificial_' . ++$self->{'_art_num'})
Truth table66%2/3
A || B
A= shift @workingB= $node->new('-id', 'artificial_' . ++$self->{'_art_num'})
ABresult
1X1
011
000
725 8 $desc->ancestor($art);
726 }
727 }
728 }
729 elsif (@descs == 1) {
730 # ensure that all nodes have 2 descs
731 0 $node->add_Descendent($node->new(-id => "artificial_".++$self->{_art_num}));
732 }
733 # recurse
734 42 foreach my $desc (@descs) {
735 35 $self->force_binary($desc);
736 }
737 }
738  
739  
740 =head2 simplify_to_leaves_string
741  
742 Title : simplify_to_leaves_string
743 Usage : my $leaves_string = $tree->simplify_to_leaves_string()
744 Function: Creates a simple textual representation of the relationship between
745 leaves in self. It forces the tree to be binary, so the result may
746 not strictly correspond to the tree (if the tree wasn't binary), but
747 will be as close as possible. The tree object is not altered. Only
748 leaf node ids are output, in a newick-like format.
749 Returns : string
750 Args : none
751  
752 =cut
753  
754 6 ▶sub simplify_to_leaves_string {
Subroutine simplify_to_leaves_string: called CC=4 SCAR=13.9
Pod documented
755 6 my $self = shift;
756  
757 # Before contracting and forcing binary we need to clone self, but Clone.pm
758 # clone() seg faults and fails to make the clone, whilst Storable dclone
759 # needs $self->{_root_cleanup_methods} deleted (code ref) and seg faults at
760 # end of script. Let's make our own clone...
761 6 my $tree = $self->_clone;
762  
763 6 $tree->contract_linear_paths(1);
764 6 $tree->force_binary;
765 6 foreach my $node ($tree->get_nodes) {
766 30 my $id = $node->id;
767 30 ▶ $id = ($node->is_Leaf && $id !~ /^artificial/) ? $id : '';
Branch: 1 branch
BranchTrueFalseTotal
$node->is_Leaf && !($id =~ /^artificial/) ? : 18 12 30
Condition66%2/3
$node->is_Leaf and not $id =~ /^artificial/
!ll&&!rl&&r
12018
MC/DC50%1/2
$node->is_Leaf and not $id =~ /^artificial/
$node->is_Leaf not $id =~ /^artificial/
Truth table66%2/3
A and not(B)
A= $node->is_LeafB= not $id =~ /^artificial/
ABresult
0X0
100
111
768 30 $node->id($id);
769 }
770  
771 6 my %paired;
772 6 my @data = $self->_simplify_helper($tree->get_root_node, \%paired);
773  
774 6 return join(',', @data);
775 }
776  
777  
778 # alias
779 330 ▶sub _clone { shift->clone(@_) }
Subroutine _clone: called CC=1 SCAR=0.0
780  
781  
782 # safe node clone that doesn't seg fault, but deliberately loses ancestors and
783 # descendents
784 340 ▶sub _clone_node {
Subroutine _clone_node: called CC=4 SCAR=13.9
785 340 my ($self, $node) = @_;
786 340 my $clone = $node->new;
787  
788 340 ▶ while (my ($key, $val) = each %{$node}) {
Branch: 1 branch
BranchTrueFalseTotal
if (() = each %{$node;}) 2879 340 3219
789 2879 ▶ if ($key eq '_desc' || $key eq '_ancestor') {
Branch: 1 branch
BranchTrueFalseTotal
if ($key eq "_desc" or $key eq "_ancestor") 664 2215 2879
Condition100%3/3
$key eq "_desc" or $key eq "_ancestor"
l!l&&r!l&&!r
3403242215
MC/DC100%2/2
$key eq "_desc" or $key eq "_ancestor"
$key eq "_desc" $key eq "_ancestor"
Truth table100%3/3
A or B
A= $key eq "_desc"B= $key eq "_ancestor"
ABresult
1X1
011
000
790 664 next;
791 }
792 2215 ${$clone}{$key} = $val;
793 }
794  
795 340 return $clone;
796 }
797  
798  
799 # tree string generator for simplify_to_leaves_string, based on
800 # Bio::TreeIO::newick::_write_tree_Helper
801 30 ▶sub _simplify_helper {
Subroutine _simplify_helper: called CC=8 SCAR=21.2
802 30 my ($self, $node, $paired) = @_;
803 30 ▶ return () if (!defined $node);
Branch: 1 branch
BranchTrueFalseTotal
unless defined $node 0 30 30
804  
805 30 my @data = ();
806 30 foreach my $node ($node->each_Descendent()) {
807 24 push(@data, $self->_simplify_helper($node, $paired));
808 }
809  
810 30 ▶ my $id = $node->id_output || '';
Condition100%2/2
$node->id_output || ''
l!l
1812
MC/DC100%1/1
$node->id_output || ''
$node->id_output
Truth table100%2/2
A
A= $node->id_output
Aresult
11
00
811 30 ▶ if (@data) {
Branch: 2 branches
BranchTrueFalseTotal
if (@data) { } 12 18 30
elsif ($id) { } 18 0 18
812 12 ▶ unless (exists ${$paired}{"@data"} || @data == 1) {
Branch: 1 branch
BranchTrueFalseTotal
unless (exists ${$paired;}{join $", @data} or @data == 1) 12 0 12
Condition33%1/3
exists ${$paired;}{join $", @data} or @data == 1
l!l&&r!l&&!r
0012
MC/DC0%0/2
exists ${$paired;}{join $", @data} or @data == 1
exists ${$paired;}{join $", @data} @data == 1
Truth table33%1/3
A or B
A= exists ${$paired;}{join $", @data}B= @data == 1
ABresult
1X1
011
000
813 12 $data[0] = "(" . $data[0];
814 12 $data[-1] .= ")";
815 12 ${$paired}{"@data"} = 1;
816 }
817 }
818 elsif ($id) {
819 18 push(@data, $id);
820 }
821  
822 30 return @data;
823 }
824  
825  
826 =head2 distance
827  
828 Title : distance
829 Usage : distance(-nodes => \@nodes )
830 Function: returns the distance between two given nodes
831 Returns : numerical distance
832 Args : -nodes => arrayref of nodes to test
833 or ($node1, $node2)
834  
835 =cut
836  
837 0 ▶sub distance {
Subroutine distance: not called CC=11 SCAR=48.8
Pod documented
838 0 my ($self,@args) = @_;
839 0 my ($nodes) = $self->_rearrange([qw(NODES)],@args);
840 0 ▶ if( ! defined $nodes ) {
Branch: 3 branches
BranchTrueFalseTotal
if (not defined $nodes) { } 0 0 0
elsif (ref $nodes eq 'ARRAY') { } 0 0 0
elsif (@args == 2) { } 0 0 0
841 0 $self->warn("Must supply two nodes or -nodes parameter to distance() method");
842 0 return;
843 }
844 elsif (ref($nodes) eq 'ARRAY') {
845 0 1;
846 }
847 elsif ( @args == 2) { # assume these are nodes...
848 0 $nodes = \@args;
849 }
850 else {
851 0 $self->warn("Must supply two nodes or -nodes parameter to distance() method");
852 0 return;
853 }
854 0 ▶ $self->throw("Must provide 2 nodes") unless @{$nodes} == 2;
Branch: 1 branch
BranchTrueFalseTotal
unless @{$nodes;} == 2 0 0 0
855  
856 0 my $lca = $self->get_lca(@{$nodes});
857 0 ▶ unless($lca) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($lca) 0 0 0
858 0 $self->warn("could not find the lca of supplied nodes; can't find distance either");
859 0 return;
860 }
861  
862 0 my $cumul_dist = 0;
863 0 my $warned = 0;
864 0 foreach my $current_node (@{$nodes}) {
865 0 while (1) {
866 0 ▶ last if $current_node eq $lca;
Branch: 1 branch
BranchTrueFalseTotal
if $current_node eq $lca 0 0 0
867 0 ▶ if ($current_node->branch_length) {
Branch: 2 branches
BranchTrueFalseTotal
if ($current_node->branch_length) { } 0 0 0
elsif (not $warned) { } 0 0 0
868 0 $cumul_dist += $current_node->branch_length;
869 }
870 elsif (! $warned) {
871 0 $self->warn("At least some nodes do not have a branch length, the distance returned could be wrong");
872 0 $warned = 1;
873 }
874  
875 0 ▶ $current_node = $current_node->ancestor || last;
Condition0%0/2
$current_node->ancestor || (last)
l!l
00
MC/DC0%0/1
$current_node->ancestor || (last)
$current_node->ancestor
Truth table0%0/2
A
A= $current_node->ancestor
Aresult
11
00
876 }
877 }
878  
879 0 return $cumul_dist;
880 }
881  
882  
883 =head2 is_monophyletic
884  
885 Title : is_monophyletic
886 Usage : if( $tree->is_monophyletic(-nodes => \@nodes,
887 -outgroup => $outgroup)
888 Function: Will do a test of monophyly for the nodes specified
889 in comparison to a chosen outgroup
890 Returns : boolean
891 Args : -nodes => arrayref of nodes to test
892 -outgroup => outgroup to serve as a reference
893  
894 =cut
895  
896 6 ▶sub is_monophyletic{
Subroutine is_monophyletic: called CC=7 SCAR=21.6
Pod documented
897 6 my ($self,@args) = @_;
898 6 my ($nodes,$outgroup) = $self->_rearrange([qw(NODES OUTGROUP)],@args);
899  
900 6 ▶ if( ! defined $nodes || ! defined $outgroup ) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $nodes and defined $outgroup) 0 6 6
Condition33%1/3
defined $nodes and defined $outgroup
!ll&&!rl&&r
006
MC/DC0%0/2
defined $nodes and defined $outgroup
defined $nodes defined $outgroup
Truth table33%1/3
A and B
A= defined $nodesB= defined $outgroup
ABresult
0X0
100
111
901 0 $self->warn("Must supply -nodes and -outgroup parameters to the method
902 is_monophyletic");
903 0 return;
904 }
905 6 ▶ if( ref($nodes) !~ /ARRAY/i ) {
Branch: 1 branch
BranchTrueFalseTotal
unless (ref($nodes) =~ /ARRAY/i) 0 6 6
906 0 $self->warn("Must provide a valid array reference for -nodes");
907 }
908  
909 6 my $clade_root = $self->get_lca(@{$nodes});
910 6 ▶ unless( defined $clade_root ) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $clade_root) 0 6 6
911 0 $self->warn("could not find clade root via lca");
912 0 return;
913 }
914  
915 6 my $og_ancestor = $outgroup->ancestor;
916 6 ▶ while( defined ($og_ancestor ) ) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $og_ancestor) 12 4 16
917 12 ▶ if( $og_ancestor->internal_id == $clade_root->internal_id ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($og_ancestor->internal_id == $clade_root->internal_id) 2 10 12
918 # monophyly is violated
919 2 return 0;
920 }
921 10 $og_ancestor = $og_ancestor->ancestor;
922 }
923 4 return 1;
924 }
925  
926  
927 =head2 is_paraphyletic
928  
929 Title : is_paraphyletic
930 Usage : if( $tree->is_paraphyletic(-nodes =>\@nodes,
931 -outgroup => $node) ){ }
932 Function: Tests whether or not a given set of nodes are paraphyletic
933 (representing the full clade) given an outgroup
934 Returns : [-1,0,1] , -1 if the group is not monophyletic
935 0 if the group is not paraphyletic
936 1 if the group is paraphyletic
937 Args : -nodes => Array of Bio::Tree::NodeI objects which are in the tree
938 -outgroup => a Bio::Tree::NodeI to compare the nodes to
939  
940  
941 =cut
942  
943 2 ▶sub is_paraphyletic{
Subroutine is_paraphyletic: called CC=11 SCAR=26.8
Pod documented
944 2 my ($self,@args) = @_;
945 2 my ($nodes,$outgroup) = $self->_rearrange([qw(NODES OUTGROUP)],@args);
946  
947 2 ▶ if( ! defined $nodes || ! defined $outgroup ) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $nodes and defined $outgroup) 0 2 2
Condition33%1/3
defined $nodes and defined $outgroup
!ll&&!rl&&r
002
MC/DC0%0/2
defined $nodes and defined $outgroup
defined $nodes defined $outgroup
Truth table33%1/3
A and B
A= defined $nodesB= defined $outgroup
ABresult
0X0
100
111
948 0 $self->warn("Must suply -nodes and -outgroup parameters to the method is_paraphyletic");
949 0 return;
950 }
951 2 ▶ if( ref($nodes) !~ /ARRAY/i ) {
Branch: 1 branch
BranchTrueFalseTotal
unless (ref($nodes) =~ /ARRAY/i) 0 2 2
952 0 $self->warn("Must provide a valid array reference for -nodes");
953 0 return;
954 }
955  
956 # Algorithm
957 # Find the lca
958 # Find all the nodes beneath the lca
959 # Test to see that none are missing from the nodes list
960 2 my %nodehash;
961 2 foreach my $n ( @$nodes ) {
962 6 $nodehash{$n->internal_id} = $n;
963 }
964  
965 2 my $clade_root = $self->get_lca(-nodes => $nodes );
966 2 ▶ unless( defined $clade_root ) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $clade_root) 0 2 2
967 0 $self->warn("could not find clade root via lca");
968 0 return;
969 }
970  
971 2 my $og_ancestor = $outgroup->ancestor;
972  
973 # Is this necessary/correct for paraphyly test?
974 2 ▶ while( defined ($og_ancestor ) ) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $og_ancestor) 4 2 6
975 4 ▶ if( $og_ancestor->internal_id == $clade_root->internal_id ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($og_ancestor->internal_id == $clade_root->internal_id) 0 4 4
976 # monophyly is violated, could be paraphyletic
977 0 return -1;
978 }
979 4 $og_ancestor = $og_ancestor->ancestor;
980 }
981 2 my $tree = Bio::Tree::Tree->new(-root => $clade_root,
982 -nodelete => 1);
983  
984 2 foreach my $n ( $tree->get_nodes() ) {
985 8 ▶ next unless $n->is_Leaf();
Branch: 1 branch
BranchTrueFalseTotal
unless $n->is_Leaf 4 4 8
986 # if any leaf node is not in the list
987 # then it is part of the clade and so the list
988 # must be paraphyletic
989 4 ▶ return 1 unless ( $nodehash{$n->internal_id} );
Branch: 1 branch
BranchTrueFalseTotal
unless $nodehash{$n->internal_id} 1 3 4
990 }
991 1 return 0;
992 }
993  
994  
995 =head2 reroot
996  
997 Title : reroot
998 Usage : $tree->reroot($node);
999 Function: Reroots a tree making a new node the root
1000 Returns : 1 on success, 0 on failure
1001 Args : Bio::Tree::NodeI that is in the tree, but is not the current root
1002  
1003 =cut
1004  
1005 18 ▶sub reroot {
Subroutine reroot: called CC=7 SCAR=19.9
Pod documented
1006 18 my ($self,$new_root) = @_;
1007 18 ▶ unless (defined $new_root && $new_root->isa("Bio::Tree::NodeI")) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $new_root and $new_root->isa("Bio::Tree::NodeI")) 0 18 18
Condition33%1/3
defined $new_root and $new_root->isa("Bio::Tree::NodeI")
!ll&&!rl&&r
0018
MC/DC0%0/2
defined $new_root and $new_root->isa("Bio::Tree::NodeI")
defined $new_root $new_root->isa("Bio::Tree::NodeI")
Truth table33%1/3
A and B
A= defined $new_rootB= $new_root->isa("Bio::Tree::NodeI")
ABresult
0X0
100
111
1008 0 $self->warn("Must provide a valid Bio::Tree::NodeI when rerooting");
1009 0 return 0;
1010 }
1011  
1012 18 my $old_root = $self->get_root_node;
1013 18 ▶ if( $new_root == $old_root ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($new_root == $old_root) 1 17 18
1014 1 $self->warn("Node requested for reroot is already the root node!");
1015 1 return 0;
1016 }
1017 17 my $anc = $new_root->ancestor;
1018 17 ▶ unless( $anc ) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($anc) 0 17 17
1019 # this is already the root
1020 0 $self->warn("Node requested for reroot is already the root node!");
1021 0 return 0;
1022 }
1023 17 my $tmp_node = $new_root->create_node_on_branch(-position=>0,-force=>1);
1024 # reverse the ancestor & children pointers
1025 17 my $former_anc = $tmp_node->ancestor;
1026 17 my @path_from_oldroot = ($self->get_lineage_nodes($tmp_node), $tmp_node);
1027 17 ▶ for (my $i = 0; $i < $#path_from_oldroot; $i++) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < $#path_from_oldroot) 43 17 60
1028 43 my $current = $path_from_oldroot[$i];
1029 43 my $next = $path_from_oldroot[$i + 1];
1030 43 $current->remove_Descendent($next);
1031 43 $current->branch_length($next->branch_length);
1032 43 ▶ $current->bootstrap($next->bootstrap) if defined $next->bootstrap;
Branch: 1 branch
BranchTrueFalseTotal
if defined $next->bootstrap 9 34 43
1033 43 $next->remove_tag('B');
1034 43 $next->add_Descendent($current);
1035 }
1036  
1037 17 $new_root->add_Descendent($former_anc);
1038 17 $tmp_node->remove_Descendent($former_anc);
1039
1040 17 $tmp_node = undef;
1041 17 $new_root->branch_length(undef);
1042  
1043 17 $old_root = undef;
1044 17 $self->set_root_node($new_root);
1045  
1046 17 return 1;
1047 }
1048  
1049  
1050 =head2 reroot_at_midpoint
1051  
1052 Title : reroot_at_midpoint
1053 Usage : $tree->reroot_at_midpoint($node, $new_root_id);
1054 Function: Reroots a tree on a new node created halfway between the
1055 argument and its ancestor
1056 Returns : the new midpoint Bio::Tree::NodeIon success, 0 on failure
1057 Args : non-root Bio::Tree::NodeI currently in $tree
1058 scalar string, id for new node (optional)
1059  
1060 =cut
1061  
1062 0 ▶sub reroot_at_midpoint {
Subroutine reroot_at_midpoint: not called CC=7 SCAR=40.3
Pod documented
1063 0 my $self = shift;
1064 0 my $node = shift;
1065 0 my $id = shift;
1066  
1067 0 ▶ unless (defined $node && $node->isa("Bio::Tree::NodeI")) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $node and $node->isa("Bio::Tree::NodeI")) 0 0 0
Condition0%0/3
defined $node and $node->isa("Bio::Tree::NodeI")
!ll&&!rl&&r
000
MC/DC0%0/2
defined $node and $node->isa("Bio::Tree::NodeI")
defined $node $node->isa("Bio::Tree::NodeI")
Truth table0%0/3
A and B
A= defined $nodeB= $node->isa("Bio::Tree::NodeI")
ABresult
0X0
100
111
1068 0 $self->warn("Must provide a valid Bio::Tree::NodeI when rerooting");
1069 0 return 0;
1070 }
1071  
1072 0 my $midpt = $node->create_node_on_branch(-FRACTION=>0.5);
1073 0 ▶ if (defined $id) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $id) 0 0 0
1074 0 ▶ $self->warn("ID argument is not a scalar") if (ref $id);
Branch: 1 branch
BranchTrueFalseTotal
if ref $id 0 0 0
1075 0 ▶ $midpt->id($id) if defined($id) && !ref($id);
Branch: 1 branch
BranchTrueFalseTotal
if defined $id and not ref $id 0 0 0
Condition0%0/3
defined $id and not ref $id
!ll&&!rl&&r
000
MC/DC0%0/2
defined $id and not ref $id
defined $id not ref $id
Truth table0%0/3
A and not(B)
A= defined $idB= not ref $id
ABresult
0X0
100
111
1076 }
1077 0 $self->reroot($midpt);
1078 0 return $midpt;
1079 }
1080  
1081  
1082 =head2 findnode_by_id
1083  
1084 Title : findnode_by_id
1085 Usage : my $node = $tree->findnode_by_id($id);
1086 Function: Get a node by its id (which should be
1087 unique for the tree)
1088 Returns : L<Bio::Tree::NodeI>
1089 Args : node id
1090  
1091  
1092 =cut
1093  
1094 0 ▶sub findnode_by_id {
Subroutine findnode_by_id: not called CC=6 SCAR=37.4
Pod documented
1095 0 my $tree = shift;
1096 0 Carp::carp('use of findnode_by_id() is deprecated; use find_node()');
1097 0 my $id = shift;
1098 0 my $rootnode = $tree->get_root_node;
1099 0 ▶ if ( ($rootnode->id) and ($rootnode->id eq $id) ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($rootnode->id and $rootnode->id eq $id) 0 0 0
Condition0%0/3
$rootnode->id and $rootnode->id eq $id
!ll&&!rl&&r
000
MC/DC0%0/2
$rootnode->id and $rootnode->id eq $id
$rootnode->id $rootnode->id eq $id
Truth table0%0/3
A and B
A= $rootnode->idB= $rootnode->id eq $id
ABresult
0X0
100
111
1100 0 return $rootnode;
1101 }
1102 # process all the children
1103 0 foreach my $node ( $rootnode->get_Descendents ) {
1104 0 ▶ if ( ($node->id) and ($node->id eq $id ) ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($node->id and $node->id eq $id) 0 0 0
Condition0%0/3
$node->id and $node->id eq $id
!ll&&!rl&&r
000
MC/DC0%0/2
$node->id and $node->id eq $id
$node->id $node->id eq $id
Truth table0%0/3
A and B
A= $node->idB= $node->id eq $id
ABresult
0X0
100
111
1105 0 return $node;
1106 }
1107 }
1108 }
1109  
1110  
1111 =head2 move_id_to_bootstrap
1112  
1113 Title : move_id_to_bootstrap
1114 Usage : $tree->move_id_to_bootstrap
1115 Function: Move internal IDs to bootstrap slot
1116 Returns : undef
1117 Args : undef
1118  
1119 =cut
1120  
1121 1 ▶sub move_id_to_bootstrap{
Subroutine move_id_to_bootstrap: called CC=3 SCAR=11.0
Pod documented
1122 1 my ($tree) = shift;
1123 1 for my $node ( grep { ! $_->is_Leaf } $tree->get_nodes ) {
1124 4 ▶ $node->bootstrap(defined $node->id ? $node->id : '');
Branch: 1 branch
BranchTrueFalseTotal
defined $node->id ? : 3 1 4
1125 4 $node->id('');
1126 }
1127 }
1128  
1129  
1130 =head2 add_trait
1131  
1132 Title : add_trait
1133 Usage : my $key = $tree->add_trait($trait_file, 3);
1134 Function: Add traits to the leaf nodes of a Bio::Tree:Tree from a file.
1135 The trait file is a tab-delimited text file and needs to have a
1136 header line giving names to traits. The first column contains the
1137 leaf node ids. Subsequent columns contain different trait value sets.
1138 Single or double quotes are removed from the trait values. Traits
1139 are added to leaf nodes as a tag named $key using the add_tag_value()
1140 method. This means that you can retrieve the trait values using the
1141 get_tag_values() method (see the documentation for Bio::Tree::Node).
1142 Returns : Trait name (a scalar) on success, undef on failure (for example, if
1143 the column index requested was too large).
1144 Args : * Name of trait file (scalar string).
1145 * Index of trait file column (scalar int). Note that numbering starts
1146 at 0. Default: 1 (second column).
1147 * Ignore missing values. Typically, if a leaf node has no value in
1148 the trait file, an exception is thrown. If you set this option to
1149 1, then no trait will be given to the node (no exception thrown).
1150  
1151 =cut
1152  
1153 3 ▶sub _read_trait_file {
Subroutine _read_trait_file: called CC=9 SCAR=22.2
1154 3 my ($self, $file, $column) = @_;
1155 3 ▶ $column ||= 1;
Condition50%1/2
$column ||= 1
l!l
30
MC/DC0%0/1
$column ||= 1
$column
Truth table50%1/2
A
A= $column
Aresult
11
00
1156  
1157 3 my $trait_name;
1158 my $trait_values;
1159 3 ▶ open my $TRAIT, '<', $file or $self->throw("Could not read file '$file': $!");
Branch: 1 branch
BranchTrueFalseTotal
open my $TRAIT, "<", $file or $self->throw("Could not read file '${file}': $!") 3 0 3
1160  
1161 3 my $first_line = 1;
1162 3 ▶ while (<$TRAIT>) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined($_ = readline $TRAIT)) 54 3 57
1163 54 chomp;
1164 54 s/['"]//g;
1165 54 my @line = split /\t/;
1166 54 ▶ if ($first_line) {
Branch: 1 branch
BranchTrueFalseTotal
if ($first_line) 3 51 54
1167 3 $first_line = 0;
1168 3 $trait_name = $line[$column];
1169 3 next;
1170 }
1171  
1172 51 my $id = $line[0];
1173 51 ▶ last if (not defined $id) or ($id eq '');
Branch: 1 branch
BranchTrueFalseTotal
if not defined $id or $id eq "" 0 51 51
Condition33%1/3
not defined $id or $id eq ""
l!l&&r!l&&!r
0051
MC/DC0%0/2
not defined $id or $id eq ""
not defined $id $id eq ""
Truth table33%1/3
not(A) or B
A= not defined $idB= $id eq ""
ABresult
1X1
011
000
1174  
1175 # Skip empty trait values
1176 51 my $value = $line[$column];
1177 51 ▶ next if (not defined $value) or ($value eq '');
Branch: 1 branch
BranchTrueFalseTotal
if not defined $value or $value eq "" 18 33 51
Condition100%3/3
not defined $value or $value eq ""
l!l&&r!l&&!r
17133
MC/DC100%2/2
not defined $value or $value eq ""
not defined $value $value eq ""
Truth table100%3/3
not(A) or B
A= not defined $valueB= $value eq ""
ABresult
1X1
011
000
1178  
1179 33 $trait_values->{$id} = $value;
1180 }
1181  
1182 3 close $TRAIT;
1183 3 return $trait_name, $trait_values;
1184 }
1185  
1186 3 ▶sub add_trait {
Subroutine add_trait: called CC=7 SCAR=19.6
Pod documented
1187 3 my ($self, $file, $column, $ignore) = @_;
1188 3 ▶ $ignore = 0 if not defined $ignore;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $ignore 2 1 3
1189  
1190 3 my ($trait_name, $trait_values) = $self->_read_trait_file($file, $column);
1191  
1192 3 ▶ if (defined $trait_name) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $trait_name) 2 1 3
1193  
1194 2 for my $node ($self->get_leaf_nodes) {
1195  
1196 # strip quotes from the node id
1197 32 ▶ $node->id($1) if $node->id =~ /^['"]+(.*)['"]+$/;
Branch: 1 branch
BranchTrueFalseTotal
if $node->id =~ /^['"]+(.*)['"]+$/ 0 32 32
1198  
1199 32 ▶ if ( not exists $trait_values->{$node->id} ) {
Branch: 1 branch
BranchTrueFalseTotal
unless (exists $$trait_values{$node->id}) 1 31 32
1200 1 ▶ if ($ignore) {
Branch: 1 branch
BranchTrueFalseTotal
if ($ignore) { } 1 0 1
1201 1 next;
1202 } else {
1203 0 $self->throw("No trait for node [".$node->id."/".$node->internal_id."]");
1204 }
1205 }
1206  
1207 31 $node->add_tag_value($trait_name, $trait_values->{ $node->id } );
1208  
1209 }
1210 }
1211 3 return $trait_name;
1212 }
1213  
1214  
1215 80 1;
« Bio/Search/Hit/GenericHit.pm ↑ Summary Bio/Index/Swissprot.pm »