Bio/Tree/DistanceFactory.pm

filter: Statementstmt 40.2% 93 / 231 Branchbran 29.8% 37 / 124 Conditioncond 15.3% 6 / 39 MC/DCmcdc 9.5% 2 / 21 Subroutinesub 75.0% 9 / 12 Podpod 100% 4 / 4 totaltotal 35.0% 151 / 431 CC 78 SCAR 52.9
CC
78
Cov
35%
_upgma
462.0
_nj
160.8
check_additivity
156.0
CRAP 198.8
« Bio/Tools/Run/WrapperBase.pm ↑ Summary Bio/SearchIO/Writer/TextResultWriter.pm »
1 #
2 # BioPerl module for Bio::Tree::DistanceFactory
3 #
4 # Please direct questions and support issues to <bioperl-l@bioperl.org>
5 #
6 # Cared for by Jason Stajich <jason-at-bioperl.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 =head1 NAME
15  
16 Bio::Tree::DistanceFactory - Construct a tree using distance based methods
17  
18 =head1 SYNOPSIS
19  
20 use Bio::Tree::DistanceFactory;
21 use Bio::AlignIO;
22 use Bio::Align::DNAStatistics;
23 my $tfactory = Bio::Tree::DistanceFactory->new(-method => "NJ");
24 my $stats = Bio::Align::DNAStatistics->new();
25  
26 my $alnin = Bio::AlignIO->new(-format => 'clustalw',
27 -file => 'file.aln');
28 my $aln = $alnin->next_aln;
29 # Of course matrix can come from a different place
30 # like PHYLIP if you prefer, Bio::Matrix::IO should be able
31 # to parse many things
32 my $jcmatrix = $stats->distance(-align => $aln,
33 -method => 'Jukes-Cantor');
34 my $tree = $tfactory->make_tree($jcmatrix);
35  
36  
37 =head1 DESCRIPTION
38  
39 This is a factory which will construct a phylogenetic tree based on
40 the pairwise sequence distances for a set of sequences. Currently
41 UPGMA (Sokal and Michener 1958) and NJ (Saitou and Nei 1987) tree
42 construction methods are implemented.
43  
44 =head1 REFERENCES
45  
46 Eddy SR, Durbin R, Krogh A, Mitchison G, (1998) "Biological Sequence Analysis",
47 Cambridge Univ Press, Cambridge, UK.
48  
49 Howe K, Bateman A, Durbin R, (2002) "QuickTree: building huge
50 Neighbour-Joining trees of protein sequences." Bioinformatics
51 18(11):1546-1547.
52  
53 Saitou N and Nei M, (1987) "The neighbor-joining method: a new method
54 for reconstructing phylogenetic trees." Mol Biol Evol 4(4):406-25.
55  
56 =head1 FEEDBACK
57  
58 =head2 Mailing Lists
59  
60 User feedback is an integral part of the evolution of this and other
61 Bioperl modules. Send your comments and suggestions preferably to
62 the Bioperl mailing list. Your participation is much appreciated.
63  
64 bioperl-l@bioperl.org - General discussion
65 http://bioperl.org/wiki/Mailing_lists - About the mailing lists
66  
67 =head2 Support
68  
69 Please direct usage questions or support issues to the mailing list:
70  
71 I<bioperl-l@bioperl.org>
72  
73 rather than to the module maintainer directly. Many experienced and
74 reponsive experts will be able look at the problem and quickly
75 address it. Please include a thorough description of the problem
76 with code and data examples if at all possible.
77  
78 =head2 Reporting Bugs
79  
80 Report bugs to the Bioperl bug tracking system to help us keep track
81 of the bugs and their resolution. Bug reports can be submitted the web:
82  
83 https://github.com/bioperl/bioperl-live/issues
84  
85 =head1 AUTHOR - Jason Stajich
86  
87 Email jason-at-bioperl.org
88  
89 =head1 APPENDIX
90  
91 The rest of the documentation details each of the object methods.
92 Internal methods are usually preceded with a _
93  
94 =cut
95  
96 package Bio::Tree::DistanceFactory;
97 2 $Bio::Tree::DistanceFactory::VERSION = '1.7.8';
98 2 ▶use vars qw($DefaultMethod $Precision);
Subroutine BEGIN: called CC=1 SCAR=0.0
99 2 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
100  
101 # some defaults
102 2 $DefaultMethod = 'UPGMA';
103 2 $Precision = 5;
104  
105 2 ▶use Bio::Tree::Node;
Subroutine BEGIN: called CC=1 SCAR=0.0
106 2 ▶use Bio::Tree::Tree;
Subroutine BEGIN: called CC=1 SCAR=0.0
107  
108 2 ▶use base qw(Bio::Root::Root);
Subroutine BEGIN: called CC=1 SCAR=0.0
109  
110 =head2 new
111  
112 Title : new
113 Usage : my $obj = Bio::Tree::DistanceFactory->new();
114 Function: Builds a new Bio::Tree::DistanceFactory object
115 Returns : an instance of Bio::Tree::DistanceFactory
116 Args : -method => 'NJ' or 'UPGMA'
117  
118  
119 =cut
120  
121 1 ▶sub new {
Subroutine new: called CC=2 SCAR=7.2
Pod documented
122 1 my($class,@args) = @_;
123 1 my $self = $class->SUPER::new(@args);
124  
125 1 my ($method) = $self->_rearrange([qw(METHOD)],
126 @args);
127 1 ▶ $self->method($method || $DefaultMethod);
Condition33%1/3
$method || $Bio::Tree::DistanceFactory::DefaultMethod
l!l&&r!l&&!r
100
MC/DC0%0/2
$method || $Bio::Tree::DistanceFactory::DefaultMethod
$method $Bio::Tree::DistanceFactory::DefaultMethod
Truth table33%1/3
A || B
A= $methodB= $Bio::Tree::DistanceFactory::DefaultMethod
ABresult
1X1
011
000
128 1 return $self;
129 }
130  
131 =head2 make_tree
132  
133 Title : make_tree
134 Usage : my $tree = $disttreefact->make_tree($matrix);
135 Function: Build a Tree based on a distance matrix
136 Returns : L<Bio::Tree::TreeI>
137 Args : L<Bio::Matrix::MatrixI> object
138  
139  
140 =cut
141  
142 1 ▶sub make_tree{
Subroutine make_tree: called CC=6 SCAR=26.0
Pod documented
143 1 my ($self,$matrix) = @_;
144 1 ▶ if( ! defined $matrix || !ref($matrix) ||
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $matrix and ref $matrix and $matrix->isa("Bio::Matrix::MatrixI")) 0 1 1
Condition33%2/6
defined $matrix and ref $matrix and $matrix->isa("Bio::Matrix::MatrixI")
!ll&&!rl&&r
001
defined $matrix and ref $matrix
!ll&&!rl&&r
001
MC/DC0%0/3
defined $matrix and ref $matrix and $matrix->isa("Bio::Matrix::MatrixI")
defined $matrix ref $matrix $matrix->isa("Bio::Matrix::MatrixI")
Truth table25%1/4
A and B and C
A= defined $matrixB= ref $matrixC= $matrix->isa("Bio::Matrix::MatrixI")
ABCresult
0XX0
10X0
1100
1111
145 ! $matrix->isa('Bio::Matrix::MatrixI') ) {
146 0 $self->warn("Need to provide a valid Bio::Matrix::MatrixI object to make_tree");
147 0 return;
148 }
149  
150 1 my $method = uc ($self->method);
151 1 ▶ if( $method =~ /NJ/i ) {
Branch: 2 branches
BranchTrueFalseTotal
if ($method =~ /NJ/i) { } 1 0 1
elsif ($method =~ /UPGMA/i) { } 0 0 0
152 1 return $self->_nj($matrix);
153 } elsif( $method =~ /UPGMA/i ) {
154 0 return $self->_upgma($matrix);
155 } else {
156 0 $self->warn("Unknown tree construction method '$method'. Cannot run.");
157 0 return;
158 }
159  
160 }
161  
162  
163 =head2 _nj
164  
165 Title : _nj
166 Usage : my $tree = $disttreefact->_nj($matrix);
167 Function: Construct a tree based on distance matrix using the
168 Neighbor Joining algorithm (Saitou and Nei, 1987)
169 Implementation based on Kevin Howe's Quicktree implementation
170 and uses his tricks (some based on Bill Bruno's work) to eliminate
171 negative branch lengths
172 Returns : L<Bio::Tree::TreeI>
173 Args : L<Bio::Matrix::MatrixI> object
174  
175 =cut
176  
177 1 ▶sub _nj {
Subroutine _nj: called CC=37 SCAR=50.8
178 1 my ($self,$distmat) = @_;
179  
180 # we assume type checking of $aln has already been done
181 # client shouldn't be calling this directly anyways, using the
182 # make_tree method is preferred
183  
184 # so that we can trim the number of digits shown as the branch length
185 1 my $precisionstr = "%.$Precision"."f";
186  
187 1 my @names = $distmat->column_names;
188 1 my $N = scalar @names;
189 1 my ($i,$j,$m,@nodes,$mat,@r);
190 1 my $L = $N;
191  
192 1 ▶ if( $N < 2 ) {
Branch: 2 branches
BranchTrueFalseTotal
if ($N < 2) { } 0 1 1
elsif ($N == 2) { } 0 1 1
193 0 $self->warn("Can only perform NJ treebuilding on sets of 2 or more species\n");
194 0 return;
195 } elsif( $N == 2 ) {
196 0 $i = 0;
197 0 my $d = sprintf($precisionstr,
198 $distmat->get_entry($names[0],$names[1]) / 2);
199 0 my $root = Bio::Tree::Node->new();
200 0 for my $nm ( @names ) {
201 0 $root->add_Descendent( Bio::Tree::Node->new(-id => $nm,
202 -branch_length => $d));
203 }
204 0 return Bio::Tree::Tree->new(-root => $root);
205 }
206 1 my $c = 0;
207  
208 1 ▶ for ( $i = 0; $i < $N; $i++ ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < $N) 14 1 15
209 14 push @nodes, Bio::Tree::Node->new(-id => $names[$i]);
210 14 my $ri = 0;
211 14 ▶ for( $j = 0; $j < $N; $j++ ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($j < $N) 196 14 210
212 196 $mat->[$i][$j] = $distmat->get_entry($names[$i],$names[$j]);
213 196 $ri += $mat->[$i][$j];
214 }
215 14 $r[$i] = $ri / ($L -2);
216 }
217  
218 1 ▶ for( my $nodecount = 0; $nodecount < $N-3; $nodecount++) {
Branch: 1 branch
BranchTrueFalseTotal
if ($nodecount < $N - 3) 11 1 12
219 11 my ($mini,$minj,$min);
220 11 ▶ for($i = 0; $i < $N; $i++ ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < $N) 154 11 165
221 154 ▶ next unless defined $nodes[$i];
Branch: 1 branch
BranchTrueFalseTotal
unless defined $nodes[$i] 55 99 154
222 99 ▶ for( $j = 0; $j < $i; $j++ ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($j < $i) 516 99 615
223 516 ▶ next unless defined $nodes[$j];
Branch: 1 branch
BranchTrueFalseTotal
unless defined $nodes[$j] 65 451 516
224 451 my $dist = $mat->[$i][$j] - ($r[$i] + $r[$j]);
225 451 ▶ if( ! defined $min ||
Branch: 1 branch
BranchTrueFalseTotal
if (not defined $min or $dist <= $min) 32 419 451
Condition100%3/3
not defined $min or $dist <= $min
l!l&&r!l&&!r
1121419
MC/DC100%2/2
not defined $min or $dist <= $min
not defined $min $dist <= $min
Truth table100%3/3
not(A) or B
A= not defined $minB= $dist <= $min
ABresult
1X1
011
000
226 $dist <= $min) {
227 32 ($mini,$minj,$min) = ($i,$j,$dist);
228 }
229 }
230 }
231 11 my $dij = $mat->[$mini][$minj];
232 11 my $dist_i = ($dij + $r[$mini] - $r[$minj]) / 2;
233 11 my $dist_j = $dij - $dist_i;
234  
235 # deal with negative branch lengths
236 # per code in K.Howe's quicktree
237 11 ▶ if( $dist_i < 0 ) {
Branch: 2 branches
BranchTrueFalseTotal
if ($dist_i < 0) { } 0 11 11
elsif ($dist_j < 0) { } 0 11 11
238 0 $dist_i = 0;
239 0 $dist_j = $dij;
240 0 ▶ $dist_j = 0 if( $dist_j < 0 );
Branch: 1 branch
BranchTrueFalseTotal
if $dist_j < 0 0 0 0
241 } elsif( $dist_j < 0 ) {
242 0 $dist_j = 0;
243 0 $dist_i = $dij;
244 0 ▶ $dist_i = 0 if( $dist_i < 0 );
Branch: 1 branch
BranchTrueFalseTotal
if $dist_i < 0 0 0 0
245 }
246  
247 11 $nodes[$mini]->branch_length(sprintf($precisionstr,$dist_i));
248 11 $nodes[$minj]->branch_length(sprintf($precisionstr,$dist_j));
249  
250 11 my $newnode = Bio::Tree::Node->new(-descendents => [ $nodes[$mini],
251 $nodes[$minj] ]);
252  
253 11 $nodes[$mini] = $newnode;
254 11 delete $nodes[$minj];
255  
256 # update the distance matrix
257 11 $r[$mini] = 0;
258 11 my ($dmi,$dmj);
259 11 ▶ for( $m = 0; $m < $N; $m++ ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($m < $N) 154 11 165
260 154 ▶ next unless defined $nodes[$m];
Branch: 1 branch
BranchTrueFalseTotal
unless defined $nodes[$m] 66 88 154
261 88 ▶ if( $m != $mini ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($m != $mini) 77 11 88
262 77 $dmj = $mat->[$m][$minj];
263  
264 77 my ($row,$col);
265 77 ($row,$col) = ($m,$mini);
266 77 $dmi = $mat->[$row][$col];
267  
268 # from K.Howe's notes in quicktree
269 # we can actually adjust r[m] here, by using the form:
270 # rm = ((rm * numseqs) - dmi - dmj + dmk) / (numseqs-1)
271  
272 # Note: in Bill Bruno's method for negative branch
273 # elimination, then if either dist_i is positive and
274 # dist_j is 0, or dist_i is zero and dist_j is positive
275 # (after adjustment) then the matrix entry is formed
276 # from the distance to the node in question (m) to the
277 # node with the zero branch length (whichever it was).
278 # I think my code already has the same effect; this is
279 # certainly true if dij is equal to dist_i + dist_j,
280 # which it should have been fixed to
281  
282 77 my $dmk = $mat->[$row][$col] = $mat->[$col][$row] =
283 ($dmi + $dmj - $dij) / 2;
284  
285 # If we don't want to try and correct negative brlens
286 # this is essentially what is in Edddy et al, BSA book.
287 # $r[$m] = (($r[$m] * $L) - $dmi - $dmj + $dmk) / ($L-1);
288 #
289 77 $r[$m] = (($r[$m] * ($L - 2)) - $dmi - $dmj +
290 $mat->[$row][$col]) / ( $L - 3);
291 77 $r[$mini] += $dmk;
292 }
293 }
294 11 $L--;
295 11 $r[$mini] /= $L - 2;
296 }
297  
298 # should be 3 nodes left
299 1 my (@leftovernodes,@leftovers);
300 1 ▶ for( my $k = 0; $k < $N; $k++ ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($k < $N) 14 1 15
301 14 ▶ if( defined $nodes[$k] ) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $nodes[$k]) 3 11 14
302 3 push @leftovers, $k;
303 3 push @leftovernodes, $nodes[$k];
304 }
305 }
306 1 my ($l_0,$l_1,$l_2) = @leftovers;
307  
308 1 my $dist_i = ( $mat->[$l_1][$l_0] + $mat->[$l_2][$l_0] -
309 $mat->[$l_2][$l_1] ) / 2;
310  
311 1 my $dist_j = ( $mat->[$l_1][$l_0] - $dist_i);
312 1 my $dist_k = ( $mat->[$l_2][$l_0] - $dist_i);
313  
314 # This is Kev's code to get rid of negative branch lengths
315 1 ▶ if( $dist_i < 0 ) {
Branch: 3 branches
BranchTrueFalseTotal
if ($dist_i < 0) { } 0 1 1
elsif ($dist_j < 0) { } 0 1 1
elsif ($dist_k < 0) { } 0 1 1
316 0 $dist_i = 0;
317 0 $dist_j = $mat->[$l_1][$l_0];
318 0 $dist_k = $mat->[$l_2][$l_0];
319 0 ▶ if( $dist_j < 0 ) {
Branch: 2 branches
BranchTrueFalseTotal
if ($dist_j < 0) { } 0 0 0
elsif ($dist_k < 0) { } 0 0 0
320 0 $dist_j = 0;
321 0 $dist_k = ( $mat->[$l_2][$l_0] + $mat->[$l_2][$l_1] ) / 2;
322 0 ▶ $dist_k = 0 if( $dist_k < 0 );
Branch: 1 branch
BranchTrueFalseTotal
if $dist_k < 0 0 0 0
323 } elsif( $dist_k < 0 ) {
324 0 $dist_k = 0;
325 0 $dist_j = ($mat->[$l_1][$l_0] + $mat->[$l_2][$l_1]) / 2;
326 0 ▶ $dist_j = 0 if( $dist_j < 0 );
Branch: 1 branch
BranchTrueFalseTotal
if $dist_j < 0 0 0 0
327 }
328 } elsif( $dist_j < 0 ) {
329 0 $dist_j = 0;
330 0 $dist_i = $mat->[$l_1][$l_0];
331 0 $dist_k = $mat->[$l_2][$l_1];
332 0 ▶ if( $dist_i < 0 ) {
Branch: 2 branches
BranchTrueFalseTotal
if ($dist_i < 0) { } 0 0 0
elsif ($dist_k < 0) { } 0 0 0
333 0 $dist_i = 0;
334 0 $dist_k = ( $mat->[$l_2][$l_0] + $mat->[$l_2][$l_1]) / 2;
335 0 ▶ $dist_k = 0 if( $dist_k < 0 );
Branch: 1 branch
BranchTrueFalseTotal
if $dist_k < 0 0 0 0
336 } elsif( $dist_k < 0 ) {
337 0 $dist_k = 0;
338 0 $dist_i = ( $mat->[$l_1][$l_0] + $mat->[$l_2][$l_0]) / 2;
339 0 ▶ $dist_i = 0 if( $dist_i < 0 );
Branch: 1 branch
BranchTrueFalseTotal
if $dist_i < 0 0 0 0
340 }
341 } elsif( $dist_k < 0 ) {
342 0 $dist_k = 0;
343 0 $dist_i = $mat->[$l_2][$l_0];
344 0 $dist_j = $mat->[$l_2][$l_1];
345 0 ▶ if( $dist_i < 0 ) {
Branch: 2 branches
BranchTrueFalseTotal
if ($dist_i < 0) { } 0 0 0
elsif ($dist_j < 0) { } 0 0 0
346 0 $dist_i = 0;
347 0 $dist_j = ( $mat->[$l_1][$l_0] + $mat->[$l_2][$l_1] ) / 2;
348 0 ▶ $dist_j = 0 if $dist_j < 0;
Branch: 1 branch
BranchTrueFalseTotal
if $dist_j < 0 0 0 0
349 } elsif( $dist_j < 0 ) {
350 0 $dist_j = 0;
351 0 $dist_i = ($mat->[$l_1][$l_0] + $mat->[$l_2][$l_0]) / 2;
352 0 ▶ $dist_i = 0 if $dist_i < 0;
Branch: 1 branch
BranchTrueFalseTotal
if $dist_i < 0 0 0 0
353 }
354 }
355 1 $leftovernodes[0]->branch_length(sprintf($precisionstr,$dist_i));
356 1 $leftovernodes[1]->branch_length(sprintf($precisionstr,$dist_j));
357 1 $leftovernodes[2]->branch_length(sprintf($precisionstr,$dist_k));
358  
359 1 Bio::Tree::Tree->new(-root => Bio::Tree::Node->new
360 (-descendents => \@leftovernodes));
361 }
362  
363 =head2 _upgma
364  
365 Title : _upgma
366 Usage : my $tree = $disttreefact->_upgma($matrix);
367 Function: Construct a tree based on alignment using UPGMA
368 Returns : L<Bio::Tree::TreeI>
369 Args : L<Bio::Matrix::MatrixI> object
370  
371  
372 =cut
373  
374 0 ▶sub _upgma{
Subroutine _upgma: not called CC=21 SCAR=61.4
375 0 my ($self,$distmat) = @_;
376 # we assume type checking of $matrix has already been done
377 # client shouldn't be calling this directly anyways, using the
378 # make_tree method is preferred
379  
380 # algorithm, from Eddy, Durbin, Krogh, Mitchison, 1998
381 # originally by Sokal and Michener 1956
382  
383 0 my $precisionstr = "%.$Precision"."f";
384  
385 0 my ($i,$j,$x,$y,@dmat,@orig,@nodes);
386  
387 0 my @names = $distmat->column_names;
388 0 my $c = 0;
389 my @clusters = map {
390 0 my $r = { 'id' => $c,
391 'height' => 0,
392 'contains' => [$c],
393 };
394 0 $c++;
395 0 $r;
396 } @names;
397  
398 0 my $K = scalar @clusters;
399 0 my (@mins,$min);
400 0 ▶ for ( $i = 0; $i < $K; $i++ ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < $K) 0 0 0
401 0 ▶ for( $j = $i+1; $j < $K; $j++ ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($j < $K) 0 0 0
402 0 my $d = $distmat->get_entry($names[$i],$names[$j]);
403 # get Min here on first time around, save 1 cycle
404 0 $dmat[$j][$i] = $dmat[$i][$j] = $d;
405 0 $orig[$i][$j] = $orig[$j][$i] = $d;
406 0 ▶ if ( ! defined $min || $d <= $min ) {
Branch: 1 branch
BranchTrueFalseTotal
if (not defined $min or $d <= $min) 0 0 0
Condition0%0/3
not defined $min or $d <= $min
l!l&&r!l&&!r
000
MC/DC0%0/2
not defined $min or $d <= $min
not defined $min $d <= $min
Truth table0%0/3
not(A) or B
A= not defined $minB= $d <= $min
ABresult
1X1
011
000
407 0 ▶ if( defined $min && $min == $d ) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $min and $min == $d) { } 0 0 0
Condition0%0/3
defined $min and $min == $d
!ll&&!rl&&r
000
MC/DC0%0/2
defined $min and $min == $d
defined $min $min == $d
Truth table0%0/3
A and B
A= defined $minB= $min == $d
ABresult
0X0
100
111
408 0 push @mins, [$i,$j];
409 } else {
410 0 @mins = [$i,$j];
411 0 $min = $d;
412 }
413 }
414 }
415 }
416 # distance between each cluster is avg distance
417 # between pairs of sequences from each cluster
418 0 ▶ while( $K > 1 ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($K > 1) 0 0 0
419 # fencepost - we already have found the $min
420 # so very first time loop is executed we can skip checking
421 0 ▶ unless( defined $min ) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $min) 0 0 0
422 0 ▶ for($i = 0; $i < $K; $i++ ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < $K) 0 0 0
423 0 ▶ for( $j = $i+1; $j < $K; $j++ ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($j < $K) 0 0 0
424 0 my $dij = $dmat[$i][$j];
425 0 ▶ if( ! defined $min ||
Branch: 1 branch
BranchTrueFalseTotal
if (not defined $min or $dij <= $min) 0 0 0
Condition0%0/3
not defined $min or $dij <= $min
l!l&&r!l&&!r
000
MC/DC0%0/2
not defined $min or $dij <= $min
not defined $min $dij <= $min
Truth table0%0/3
not(A) or B
A= not defined $minB= $dij <= $min
ABresult
1X1
011
000
426 $dij <= $min) {
427 0 ▶ if( defined $min &&
Branch: 1 branch
BranchTrueFalseTotal
if (defined $min and $min == $dij) { } 0 0 0
Condition0%0/3
defined $min and $min == $dij
!ll&&!rl&&r
000
MC/DC0%0/2
defined $min and $min == $dij
defined $min $min == $dij
Truth table0%0/3
A and B
A= defined $minB= $min == $dij
ABresult
0X0
100
111
428 $min == $dij ) {
429 0 push @mins, [$i,$j];
430 } else {
431 0 @mins = [ $i,$j ];
432 0 $min = $dij;
433 }
434 }
435 }
436 }
437 }
438 # randomly break ties
439 0 ($x,$y) = @{ $mins[int(rand(scalar @mins))] };
440  
441 # now we are going to join clusters x and y, make a new cluster
442  
443 0 my $node = Bio::Tree::Node->new();
444 0 my @subids;
445 0 for my $cid ( $x,$y ) {
446 0 my $nid = $clusters[$cid]->{'id'};
447 0 ▶ if( ! defined $nodes[$nid] ) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $nodes[$nid]) 0 0 0
448 0 $nodes[$nid] = Bio::Tree::Node->new(-id => $names[$nid]);
449 }
450 $nodes[$nid]->branch_length
451 0 (sprintf($precisionstr,$min/2 - $clusters[$cid]->{'height'}));
452 0 $node->add_Descendent($nodes[$nid]);
453 0 push @subids, @{ $clusters[$cid]->{'contains'} };
454 }
455 0 my $cluster = { 'id' => $c++,
456 'height' => $min / 2,
457 'contains' => [@subids],
458 };
459  
460 0 $K--; # we are going to drop the last node so go ahead and decrement K
461 0 $nodes[$cluster->{'id'}] = $node;
462 0 ▶ if ( $y != $K ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($y != $K) 0 0 0
463 0 $clusters[$y] = $clusters[$K];
464 0 $dmat[$y] = $dmat[$K];
465 0 ▶ for ( $i = 0; $i < $K; $i++ ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < $K) 0 0 0
466 0 $dmat[$i][$y] = $dmat[$y][$i];
467 }
468 }
469 0 delete $clusters[$K];
470 0 $clusters[$x] = $cluster;
471 # now recalculate @dmat
472 0 ▶ for( $i = 0; $i < $K; $i++ ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < $K) 0 0 0
473 0 ▶ if( $i != $x) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i != $x) { } 0 0 0
474 0 $dmat[$i][$x] = $dmat[$x][$i] =
475 &_upgma_distance($clusters[$i],$clusters[$x],\@orig);
476 } else {
477 0 $dmat[$i][$i] = 0;
478 }
479 }
480 # reset so next loop iteration
481 # we will find minimum distance
482 0 @mins = ();
483 0 $min = undef;
484 }
485 0 Bio::Tree::Tree->new(-root => $nodes[-1]);
486 }
487  
488 # calculate avg distance between clusters - be they
489 # single sequences or the combination of multiple seqences
490 # $cluster_i and $cluster_j are the clusters to operate on
491 # and $distances is a matrix (arrayref of arrayrefs) of pairwise
492 # differences indexed on the sequence ids -
493 # so $distances->[0][1] is the distance between sequences 0 and 1
494  
495 0 ▶sub _upgma_distance {
Subroutine _upgma_distance: not called CC=4 SCAR=30.0
496 0 my ($cluster_i, $cluster_j, $distances) = @_;
497 0 my $ilen = scalar @{ $cluster_i->{'contains'} };
498 0 my $jlen = scalar @{ $cluster_j->{'contains'} };
499 0 my ($d,$count);
500 0 ▶ for( my $i = 0; $i < $ilen; $i++ ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < $ilen) 0 0 0
501 0 my $i_id = $cluster_i->{'contains'}->[$i];
502 0 ▶ for( my $j = 0; $j < $jlen; $j++) {
Branch: 1 branch
BranchTrueFalseTotal
if ($j < $jlen) 0 0 0
503 0 my $j_id = $cluster_j->{'contains'}->[$j];
504 0 ▶ if( ! defined $distances->[$i_id][$j_id] ) {
Branch: 1 branch
BranchTrueFalseTotal
if (not defined $distances->[$i_id][$j_id]) { } 0 0 0
505 0 warn("no value for $i_id $j_id\n");
506 } else {
507 0 $d += $distances->[$i_id][$j_id];
508 }
509 0 $count++;
510 }
511 }
512 0 return $d / $count;
513 }
514  
515 =head2 method
516  
517 Title : method
518 Usage : $obj->method($newval)
519 Function:
520 Example :
521 Returns : value of method (a scalar)
522 Args : on set, new value (a scalar or undef, optional)
523  
524  
525 =cut
526  
527 2 ▶sub method{
Subroutine method: called CC=2 SCAR=6.9
Pod documented
528 2 my $self = shift;
529 2 ▶ return $self->{'_method'} = shift if @_;
Branch: 1 branch
BranchTrueFalseTotal
if @_ 1 1 2
530 1 return $self->{'_method'};
531 }
532  
533  
534 =head2 check_additivity
535  
536 Title : check_additivity
537 Usage : if( $distance->check_additivity($matrix) ) {
538 }
539 Function : See if matrix obeys additivity principal
540 Returns : boolean
541 Args : Bio::Matrix::MatrixI
542 References: Based on a Java implementation by
543 Peter Sestoft, sestoft@dina.kvl.dk 1999-12-07 version 0.3
544 http://www.dina.kvl.dk/~sestoft/bsa.html
545 which in turn is based on algorithms described in
546 R. Durbin, S. Eddy, A. Krogh, G. Mitchison.
547 Biological Sequence Analysis CUP 1998, Chapter 7.
548  
549 =cut
550  
551 0 ▶sub check_additivity{
Subroutine check_additivity: not called CC=12 SCAR=50.5
Pod documented
552 0 my ($self,$matrix) = @_;
553 0 my @names = $matrix->column_names;
554 0 my $len = scalar @names;
555 0 ▶ return unless $len >= 4;
Branch: 1 branch
BranchTrueFalseTotal
unless $len >= 4 0 0 0
556 # look at all sets of 4
557 0 ▶ for( my $i = 0; $i < $len; $i++ ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < $len) 0 0 0
558 0 ▶ for( my $j = $i+1; $j< $len; $j++) {
Branch: 1 branch
BranchTrueFalseTotal
if ($j < $len) 0 0 0
559 0 ▶ for( my $k = $j+1; $k < $len; $k ++ ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($k < $len) 0 0 0
560 0 ▶ for( my $m = $k +1; $m < $len; $m++ ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($m < $len) 0 0 0
561 0 my $DijDkm = $matrix->get_entry($names[$i],$names[$j]) +
562 $matrix->get_entry($names[$k],$names[$m]);
563 0 my $DikDjm = $matrix->get_entry($names[$i],$names[$k]) +
564 $matrix->get_entry($names[$j],$names[$m]);
565 0 my $DimDjk = $matrix->get_entry($names[$i],$names[$m]) +
566 $matrix->get_entry($names[$j],$names[$k]);
567 0 ▶ if( !( ( $DijDkm == $DikDjm && $DijDkm >= $DimDjk)
Branch: 1 branch
BranchTrueFalseTotal
unless ($DijDkm == $DikDjm and $DijDkm >= $DimDjk or $DijDkm == $DimDjk and $DijDkm >= $DikDjm or $DikDjm == $DimDjk and $DikDjm >= $DijDkm) 0 0 0
Condition0%0/15
$DijDkm == $DikDjm and $DijDkm >= $DimDjk or $DijDkm == $DimDjk and $DijDkm >= $DikDjm or $DikDjm == $DimDjk and $DikDjm >= $DijDkm
l!l&&r!l&&!r
000
$DijDkm == $DikDjm and $DijDkm >= $DimDjk or $DijDkm == $DimDjk and $DijDkm >= $DikDjm
l!l&&r!l&&!r
000
$DijDkm == $DikDjm and $DijDkm >= $DimDjk
!ll&&!rl&&r
000
$DijDkm == $DimDjk and $DijDkm >= $DikDjm
!ll&&!rl&&r
000
$DikDjm == $DimDjk and $DikDjm >= $DijDkm
!ll&&!rl&&r
000
MC/DC0%0/6
$DijDkm == $DikDjm and $DijDkm >= $DimDjk or $DijDkm == $DimDjk and $DijDkm >= $DikDjm or $DikDjm == $DimDjk and $DikDjm >= $DijDkm
$DijDkm == $DikDjm $DijDkm >= $DimDjk $DijDkm == $DimDjk $DijDkm >= $DikDjm $DikDjm == $DimDjk $DikDjm >= $DijDkm
Truth table0%0/15
A and B or C and D or E and F
A= $DijDkm == $DikDjmB= $DijDkm >= $DimDjkC= $DijDkm == $DimDjkD= $DijDkm >= $DikDjmE= $DikDjm == $DimDjkF= $DikDjm >= $DijDkm
ABCDEFresult
11XXXX1
0X11XX1
1011XX1
0X0X111
0X10111
100X111
1010111
0X0X0X0
0X0X100
0X100X0
0X10100
100X0X0
100X100
10100X0
1010100
568 || ( $DijDkm == $DimDjk && $DijDkm >= $DikDjm)
569 || ( $DikDjm == $DimDjk && $DikDjm >= $DijDkm) )) {
570 0 return 0;
571 }
572 }
573 }
574 }
575 }
576 0 return 1;
577 }
578  
579 2 1;
« Bio/Tools/Run/WrapperBase.pm ↑ Summary Bio/SearchIO/Writer/TextResultWriter.pm »