Phylo/Generator.pm

filter: Statementstmt 100% 167 / 167 Branchbran 100% 22 / 22 Conditioncond 48.1% 13 / 27 MC/DCmcdc 6.6% 1 / 15 Subroutinesub 100% 25 / 25 Podpod 100% 8 / 8 totaltotal 89.3% 236 / 264 CC 32 SCAR 17.2
CC
32
Cov
94%
gen_coalescent
11.1
_gen_pure_birth
9.0
_gen_simple
8.2
CRAP 5.6
« Phylo/Forest/Node.pm ↑ Summary Phylo/Unparsers/Nhx.pm »
1 package Bio::Phylo::Generator;
2 1 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
3 1 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
4 1 ▶use Bio::Phylo::Util::CONSTANT 'looks_like_hash';
Subroutine BEGIN: called CC=1 SCAR=0.0
5 1 ▶use Bio::Phylo::Util::Exceptions 'throw';
Subroutine BEGIN: called CC=1 SCAR=0.0
6 1 ▶use Bio::Phylo::Util::Logger;
Subroutine BEGIN: called CC=1 SCAR=0.0
7 1 ▶use Bio::Phylo::Util::Dependency 'Math::Random';
Subroutine BEGIN: called CC=1 SCAR=0.0
8 1 ▶use Bio::Phylo::Factory;
Subroutine BEGIN: called CC=1 SCAR=0.0
9 1 Math::Random->import(qw'random_exponential random_uniform');
10 {
11 1 my $logger = Bio::Phylo::Util::Logger->new;
12 1 my $factory = Bio::Phylo::Factory->new;
13  
14 =head1 NAME
15  
16 Bio::Phylo::Generator - Generator of tree topologies
17  
18 =head1 SYNOPSIS
19  
20 use Bio::Phylo::Factory;
21 my $fac = Bio::Phylo::Factory->new;
22 my $gen = $fac->create_generator;
23 my $trees = $gen->gen_rand_pure_birth(
24 '-tips' => 10,
25 '-model' => 'yule',
26 '-trees' => 10,
27 );
28  
29 # prints 'Bio::Phylo::Forest'
30 print ref $trees;
31  
32 =head1 DESCRIPTION
33  
34 The generator module is used to simulate trees under various models.
35  
36 =head1 METHODS
37  
38 =head2 CONSTRUCTOR
39  
40 =over
41  
42 =item new()
43  
44 Generator constructor.
45  
46 Type : Constructor
47 Title : new
48 Usage : my $gen = Bio::Phylo::Generator->new;
49 Function: Initializes a Bio::Phylo::Generator object.
50 Returns : A Bio::Phylo::Generator object.
51 Args : NONE
52  
53 =cut
54  
55 1 ▶ sub new {
Subroutine new: called CC=1 SCAR=0.0
Pod documented
56  
57 # could be child class
58 1 my $class = shift;
59  
60 # notify user
61 1 $logger->info("constructor called for '$class'");
62  
63 # the object turns out to be stateless
64 1 my $self = bless \$class, $class;
65 1 return $self;
66 }
67  
68 =back
69  
70 =head2 GENERATOR
71  
72 =over
73  
74 =item gen_rand_pure_birth()
75  
76 This method generates a Bio::Phylo::Forest
77 object populated with Yule/Hey trees.
78  
79 Type : Generator
80 Title : gen_rand_pure_birth
81 Usage : my $trees = $gen->gen_rand_pure_birth(
82 '-tips' => 10,
83 '-model' => 'yule',
84 '-trees' => 10,
85 );
86 Function: Generates markov tree shapes,
87 with branch lengths sampled
88 from a user defined model of
89 clade growth, for a user defined
90 number of tips.
91 Returns : A Bio::Phylo::Forest object.
92 Args : -tips => number of terminal nodes (default: 10),
93 -model => either 'yule' or 'hey',
94 -trees => number of trees to generate (default: 10)
95 Optional: -factory => a Bio::Phylo::Factory object
96  
97 =cut
98  
99 44 ▶ sub _yule_rand_bl {
Subroutine _yule_rand_bl: called CC=1 SCAR=0.0
100 44 my $i = shift;
101 44 return random_exponential( 1, 1 / ( $i + 1 ) );
102 }
103  
104 19 ▶ sub _hey_rand_bl {
Subroutine _hey_rand_bl: called CC=1 SCAR=0.0
105 19 my $i = shift;
106 19 random_exponential( 1, ( 1 / ( $i * ( $i + 1 ) ) ) );
107 }
108  
109 101 ▶ sub _make_split {
Subroutine _make_split: called CC=2 SCAR=6.9
110 101 my ( $parent, $length, $fac, $nodes ) = @_;
111 101 my @tips;
112 101 for ( 1 .. 2 ) {
113 202 my $node = $fac->create_node;
114 202 $node->set_branch_length($length);
115 202 $node->set_parent($parent);
116 202 $nodes->{ $node->get_id } = $node;
117 202 push @tips, $node;
118 }
119 101 return @tips;
120 }
121  
122 3 ▶ sub gen_rand_pure_birth {
Subroutine gen_rand_pure_birth: called CC=3 SCAR=11.0
Pod documented
123 3 my $random = shift;
124 3 my %options = looks_like_hash @_;
125 3 my $model = $options{'-model'};
126 3 ▶ if ( $model =~ m/yule/i ) {
Branch: 2 branches
BranchTrueFalseTotal
if ($model =~ /yule/i) { } 1 2 3
elsif ($model =~ /hey/i) { } 1 1 2
127 1 return $random->_gen_pure_birth(
128 '-blgen' => \&_yule_rand_bl,
129 @_,
130 );
131 }
132 elsif ( $model =~ m/hey/i ) {
133 1 return $random->_gen_pure_birth(
134 '-blgen' => \&_hey_rand_bl,
135 @_,
136 );
137 }
138 else {
139 1 throw 'BadFormat' => "model '$model' not implemented";
140 }
141 }
142  
143 5 ▶ sub _gen_pure_birth {
Subroutine _gen_pure_birth: called CC=9 SCAR=22.0
144 5 my $random = shift;
145 5 my %options = looks_like_hash @_;
146 5 ▶ my $factory = $options{'-factory'} || $factory;
Condition33%1/3
$options{'-factory'} || $factory
l!l&&r!l&&!r
050
MC/DC0%0/2
$options{'-factory'} || $factory
$options{'-factory'} $factory
Truth table33%1/3
A || B
A= $options{'-factory'}B= $factory
ABresult
1X1
011
000
147 5 my $blgen = $options{'-blgen'};
148 5 ▶ my $killrate = $options{'-killrate'} || 0;
Condition100%2/2
$options{'-killrate'} || 0
l!l
14
MC/DC100%1/1
$options{'-killrate'} || 0
$options{'-killrate'}
Truth table100%2/2
A
A= $options{'-killrate'}
Aresult
11
00
149 5 ▶ my $ntips = $options{'-tips'} || 10;
Condition50%1/2
$options{'-tips'} || 10
l!l
50
MC/DC0%0/1
$options{'-tips'} || 10
$options{'-tips'}
Truth table50%1/2
A
A= $options{'-tips'}
Aresult
11
00
150 5 ▶ my $ntrees = $options{'-trees'} || 10;
Condition50%1/2
$options{'-trees'} || 10
l!l
50
MC/DC0%0/1
$options{'-trees'} || 10
$options{'-trees'}
Truth table50%1/2
A
A= $options{'-trees'}
Aresult
11
00
151 5 my $forest = $factory->create_forest;
152 5 for ( 0 .. ( $ntrees - 1 ) ) {
153  
154 # instantiate root node
155 5 my $root = $factory->create_node;
156 5 $root->set_branch_length(0);
157 5 my %nodes = ( $root->get_id => $root );
158  
159 # make the first split, insert new tips in @tips, from
160 # which we will draw (without replacement) a new tip
161 # to split until we've reached target number
162 5 push my @tips, _make_split( $root, $blgen->(1), $factory, \%nodes );
163  
164 # start growing the tree
165 5 my $i = 2;
166 5 my @extinct;
167 5 while (1) {
168 96 ▶ if ( rand(1) < $killrate ) {
Branch: 1 branch
BranchTrueFalseTotal
if (rand 1 < $killrate) 6 90 96
169 6 my $extinct_index = int rand scalar @tips;
170 6 my $extinct = splice @tips, $extinct_index, 1;
171 6 push @extinct, $extinct;
172 6 delete $nodes{ $extinct->get_id };
173 }
174  
175 # obtain candidate parent of current split
176 96 my $parent;
177 96 ( $parent, @tips ) = _fetch_equiprobable(@tips);
178  
179 # generate branch length
180 96 my $bl = $blgen->( $i++ );
181  
182 # stretch all remaining tips to the present
183 96 for my $tip (@tips) {
184 903 my $oldbl = $tip->get_branch_length;
185 903 $tip->set_branch_length( $oldbl + $bl );
186 }
187  
188 # add new nodes to tips array
189 96 push @tips, _make_split( $parent, $bl, $factory, \%nodes );
190 96 ▶ last if scalar @tips >= $ntips;
Branch: 1 branch
BranchTrueFalseTotal
if scalar @tips >= $ntips 5 91 96
191 }
192 5 my $tree = $factory->create_tree;
193 $tree->insert(
194 201 map { $_->[0] }
195 831 sort { $a->[1] <=> $b->[1] }
196 5 map { [ $_, $_->get_id ] } values %nodes
197 );
198 5 $tree->prune_tips( \@extinct );
199 5 $tree->_analyze;
200 5 $forest->insert($tree);
201 }
202 5 return $forest;
203 }
204  
205 =item gen_rand_birth_death()
206  
207 This method generates a Bio::Phylo::Forest
208 object populated under a birth/death model
209  
210 Type : Generator
211 Title : gen_rand_birth_death
212 Usage : my $trees = $gen->gen_rand_birth_death(
213 '-tips' => 10,
214 '-killrate' => 0.2,
215 '-trees' => 10,
216 );
217 Function: Generates trees where any growing lineage is equally
218 likely to split at any one time, and is equally likely
219 to go extinct at '-killrate'
220 Returns : A Bio::Phylo::Forest object.
221 Args : -tips => number of terminal nodes (default: 10),
222 -killrate => extinction over speciation rate (default: 0.2)
223 -trees => number of trees to generate (default: 10)
224 Optional: -factory => a Bio::Phylo::Factory object
225 Comments: Past extinction events are retained as unbranched internal
226 nodes in the produced trees.
227  
228 =cut
229  
230 1 ▶ sub gen_rand_birth_death {
Subroutine gen_rand_birth_death: called CC=2 SCAR=7.1
Pod documented
231 1 my $random = shift;
232 1 my %options = looks_like_hash @_;
233 return $random->_gen_pure_birth(
234 '-blgen' => \&_yule_rand_bl,
235 1 ▶ '-killrate' => $options{'-killrate'} || 0.2,
Condition50%1/2
$options{'-killrate'} || 0.2
l!l
10
MC/DC0%0/1
$options{'-killrate'} || 0.2
$options{'-killrate'}
Truth table50%1/2
A
A= $options{'-killrate'}
Aresult
11
00
236 @_,
237 );
238 }
239  
240 =item gen_exp_pure_birth()
241  
242 This method generates a Bio::Phylo::Forest object
243 populated with Yule/Hey trees whose branch lengths
244 are proportional to the expected waiting times (i.e.
245 not sampled from a distribution).
246  
247 Type : Generator
248 Title : gen_exp_pure_birth
249 Usage : my $trees = $gen->gen_exp_pure_birth(
250 '-tips' => 10,
251 '-model' => 'yule',
252 '-trees' => 10,
253 );
254 Function: Generates markov tree shapes,
255 with branch lengths following
256 the expectation under a user
257 defined model of clade growth,
258 for a user defined number of tips.
259 Returns : A Bio::Phylo::Forest object.
260 Args : -tips => number of terminal nodes (default: 10),
261 -model => either 'yule' or 'hey'
262 -trees => number of trees to generate (default: 10)
263 Optional: -factory => a Bio::Phylo::Factory object
264  
265 =cut
266  
267 19 ▶ sub _yule_exp_bl {
Subroutine _yule_exp_bl: called CC=1 SCAR=0.0
268 19 my $i = shift;
269 19 return 1 / ( $i + 1 );
270 }
271  
272 19 ▶ sub _hey_exp_bl {
Subroutine _hey_exp_bl: called CC=1 SCAR=0.0
273 19 my $i = shift;
274 19 return 1 / ( $i * ( $i + 1 ) );
275 }
276  
277 3 ▶ sub gen_exp_pure_birth {
Subroutine gen_exp_pure_birth: called CC=3 SCAR=11.0
Pod documented
278 3 my $random = shift;
279 3 my %options = looks_like_hash @_;
280 3 my $model = $options{'-model'};
281 3 ▶ if ( $model =~ m/yule/i ) {
Branch: 2 branches
BranchTrueFalseTotal
if ($model =~ /yule/i) { } 1 2 3
elsif ($model =~ /hey/i) { } 1 1 2
282 1 return $random->_gen_pure_birth(
283 '-blgen' => \&_yule_exp_bl,
284 @_,
285 );
286 }
287 elsif ( $model =~ m/hey/i ) {
288 1 return $random->_gen_pure_birth(
289 '-blgen' => \&_hey_exp_bl,
290 @_,
291 );
292 }
293 else {
294 1 throw 'BadFormat' => "model '$model' not implemented";
295 }
296 }
297  
298 =item gen_coalescent()
299  
300 This method generates coalescent trees for a given effective population size
301 (popsize) and number of alleles (tips) such that the probability of coalescence
302 in the previous generation for any pair of alleles is 1 / ( 2 * popsize ).
303  
304 Type : Generator
305 Title : gen_coalescent
306 Usage : my $trees = $gen->gen_coalescent(
307 '-tips' => 10,
308 '-popsize' => 100,
309 '-trees' => 10,
310 );
311 Function: Generates coalescent trees.
312 Returns : A Bio::Phylo::Forest object.
313 Args : -tips => number of terminal nodes (default: 10)
314 -popsize => effective population size (default: 100)
315 -trees => number of trees to generate (default: 10)
316 Optional: -factory => a Bio::Phylo::Factory object
317  
318 =cut
319  
320 1 ▶ sub gen_coalescent {
Subroutine gen_coalescent: called CC=11 SCAR=24.1
Pod documented
321 1 my $self = shift;
322 1 my %args = looks_like_hash @_;
323 1 ▶ my $popsize = $args{'-popsize'} || 100;
Condition50%1/2
$args{'-popsize'} || 100
l!l
01
MC/DC0%0/1
$args{'-popsize'} || 100
$args{'-popsize'}
Truth table50%1/2
A
A= $args{'-popsize'}
Aresult
11
00
324 1 ▶ my $ntips = $args{'-tips'} || 10;
Condition50%1/2
$args{'-tips'} || 10
l!l
10
MC/DC0%0/1
$args{'-tips'} || 10
$args{'-tips'}
Truth table50%1/2
A
A= $args{'-tips'}
Aresult
11
00
325 1 ▶ my $ntrees = $args{'-trees'} || 10;
Condition50%1/2
$args{'-trees'} || 10
l!l
10
MC/DC0%0/1
$args{'-trees'} || 10
$args{'-trees'}
Truth table50%1/2
A
A= $args{'-trees'}
Aresult
11
00
326 1 ▶ my $factory = $args{'-factory'} || $factory;
Condition33%1/3
$args{'-factory'} || $factory
l!l&&r!l&&!r
010
MC/DC0%0/2
$args{'-factory'} || $factory
$args{'-factory'} $factory
Truth table33%1/3
A || B
A= $args{'-factory'}B= $factory
ABresult
1X1
011
000
327 1 my $forest = $factory->create_forest;
328 1 my $cutoff = 1 / ( 2 * $popsize );
329 1 for my $i ( 1 .. $ntrees ) {
330 1 my $ngen = 1;
331 1 my ( @tips, @nodes );
332 1 push @tips, $factory->create_node() for 1 .. $ntips;
333  
334 # starting from a pool of all tips, we iterate over all
335 # possible pairs, and for each pair we test to see if
336 # the coalesce at generation $ngen, at probability
337 # 1/2N. When they do, we create a parent for the pair,
338 # take the pair out of the pool and put the parent in it
339 1 ▶ while ( scalar @tips > 1 ) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @tips > 1) 459 1 460
340 459 my $poolsize = $#tips;
341 459 my $j = 0;
342 459 ▶ while ( $j < $poolsize ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($j < $poolsize) 881 459 1340
343 881 my $k = $j + 1;
344 881 ▶ while ( $k <= $poolsize ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($k <= $poolsize) 2461 881 3342
345 2461 my $rand = random_uniform();
346 2461 ▶ if ( $rand <= $cutoff ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($rand <= $cutoff) 19 2442 2461
347 19 my $tip2 = splice @tips, $k, 1;
348 19 my $tip1 = splice @tips, $j, 1;
349 19 my $parent = $factory->create_node(
350 '-generic' => { 'age' => $ngen } );
351 19 unshift @nodes,
352 $tip1->set_parent($parent),
353 $tip2->set_parent($parent);
354 19 push @tips, $parent;
355 19 $poolsize--;
356 }
357 2461 $k++;
358 }
359 881 $j++;
360 }
361 459 $ngen++;
362 }
363 1 push @nodes, shift @tips;
364 1 my $tree = $factory->create_tree()->insert(@nodes);
365 1 $tree->agetobl;
366 1 $forest->insert($tree);
367 }
368 1 return $forest;
369 }
370  
371 =item gen_equiprobable()
372  
373 This method draws tree shapes at random,
374 such that all shapes are equally probable.
375  
376 Type : Generator
377 Title : gen_equiprobable
378 Usage : my $trees = $gen->gen_equiprobable( '-tips' => 10 );
379 Function: Generates an equiprobable tree
380 shape, with branch lengths = 1;
381 Returns : A Bio::Phylo::Forest object.
382 Args : Optional: -tips => number of terminal nodes (default: 10),
383 Optional: -trees => number of trees to generate (default: 1),
384 Optional: -factory => a Bio::Phylo::Factory object
385  
386 =cut
387  
388 134 ▶ sub _fetch_equiprobable {
Subroutine _fetch_equiprobable: called CC=1 SCAR=0.0
389 134 my @tips = @_;
390 134 my $tip_index = int rand scalar @tips;
391 134 my $tip = splice @tips, $tip_index, 1;
392 134 return $tip, @tips;
393 }
394  
395 30 ▶ sub _fetch_balanced {
Subroutine _fetch_balanced: called CC=1 SCAR=0.0
396 30 return @_;
397 }
398  
399 30 ▶ sub _fetch_ladder {
Subroutine _fetch_ladder: called CC=1 SCAR=0.0
400 30 my $tip = pop;
401 30 return $tip, @_;
402 }
403  
404 3 ▶ sub _gen_simple {
Subroutine _gen_simple: called CC=8 SCAR=21.0
405 3 my $random = shift;
406 3 my %options = looks_like_hash @_;
407 3 my $fetcher = $options{'-fetcher'};
408 3 ▶ my $factory = $options{'-factory'} || $factory;
Condition33%1/3
$options{'-factory'} || $factory
l!l&&r!l&&!r
030
MC/DC0%0/2
$options{'-factory'} || $factory
$options{'-factory'} $factory
Truth table33%1/3
A || B
A= $options{'-factory'}B= $factory
ABresult
1X1
011
000
409 3 ▶ my $ntrees = $options{'-trees'} || 1;
Condition50%1/2
$options{'-trees'} || 1
l!l
30
MC/DC0%0/1
$options{'-trees'} || 1
$options{'-trees'}
Truth table50%1/2
A
A= $options{'-trees'}
Aresult
11
00
410 3 ▶ my $ntips = $options{'-tips'} || 10;
Condition50%1/2
$options{'-tips'} || 10
l!l
30
MC/DC0%0/1
$options{'-tips'} || 10
$options{'-tips'}
Truth table50%1/2
A
A= $options{'-tips'}
Aresult
11
00
411 3 my $forest = $factory->create_forest;
412 3 for my $i ( 1 .. $ntrees ) {
413 3 my $tree = $factory->create_tree;
414 3 my ( @tips, @nodes );
415  
416 # each iteration, we will remove two "tips" from this
417 # and add their newly created parent to it
418 push @tips, $factory->create_node( '-branch_length' => 1, )
419 3 for ( 1 .. $ntips );
420  
421 # this stays above 0 because the root ends up in it
422 3 ▶ while ( @tips > 1 ) {
Branch: 1 branch
BranchTrueFalseTotal
if (@tips > 1) 49 3 52
423 49 my $parent = $factory->create_node( '-branch_length' => 1, );
424 49 $tree->insert($parent);
425 49 for ( 1 .. 2 ) {
426 98 my $tip;
427 98 ( $tip, @tips ) = $fetcher->(@tips);
428 98 $tree->insert( $tip->set_parent($parent) );
429 }
430  
431 # the parent becomes a new candidate tip
432 49 push @tips, $parent;
433 }
434 3 $forest->insert($tree);
435 }
436 3 return $forest;
437 }
438  
439 1 ▶ sub gen_equiprobable {
Subroutine gen_equiprobable: called CC=1 SCAR=0.0
Pod documented
440 1 return _gen_simple( @_, '-fetcher' => \&_fetch_equiprobable );
441 }
442  
443 =item gen_balanced()
444  
445 This method creates the most balanced topology possible given the number of tips
446  
447 Type : Generator
448 Title : gen_balanced
449 Usage : my $trees = $gen->gen_balanced( '-tips' => 10 );
450 Function: Generates the most balanced topology
451 possible, with branch lengths = 1;
452 Returns : A Bio::Phylo::Forest object.
453 Args : Optional: -tips => number of terminal nodes (default: 10),
454 Optional: -trees => number of trees to generate (default: 1),
455 Optional: -factory => a Bio::Phylo::Factory object
456  
457 =cut
458  
459 1 ▶ sub gen_balanced {
Subroutine gen_balanced: called CC=1 SCAR=0.0
Pod documented
460 1 return _gen_simple( @_, '-fetcher' => \&_fetch_balanced );
461 }
462  
463 =item gen_ladder()
464  
465 This method creates a ladder tree for the number of tips
466  
467 Type : Generator
468 Title : gen_ladder
469 Usage : my $trees = $gen->gen_ladder( '-tips' => 10 );
470 Function: Generates the least balanced topology
471 (a ladder), with branch lengths = 1;
472 Returns : A Bio::Phylo::Forest object.
473 Args : Optional: -tips => number of terminal nodes (default: 10),
474 Optional: -trees => number of trees to generate (default: 1),
475 Optional: -factory => a Bio::Phylo::Factory object
476  
477 =cut
478  
479 1 ▶ sub gen_ladder {
Subroutine gen_ladder: called CC=1 SCAR=0.0
Pod documented
480 1 return _gen_simple( @_, '-fetcher' => \&_fetch_ladder );
481 }
482  
483 =back
484  
485 =head1 SEE ALSO
486  
487 There is a mailing list at L<https://groups.google.com/forum/#!forum/bio-phylo>
488 for any user or developer questions and discussions.
489  
490 =over
491  
492 =item L<Bio::Phylo::Manual>
493  
494 Also see the manual: L<Bio::Phylo::Manual> and L<http://rutgervos.blogspot.com>.
495  
496 =back
497  
498 =head1 CITATION
499  
500 If you use Bio::Phylo in published research, please cite it:
501  
502 B<Rutger A Vos>, B<Jason Caravas>, B<Klaas Hartmann>, B<Mark A Jensen>
503 and B<Chase Miller>, 2011. Bio::Phylo - phyloinformatic analysis using Perl.
504 I<BMC Bioinformatics> B<12>:63.
505 L<http://dx.doi.org/10.1186/1471-2105-12-63>
506  
507 =cut
508  
509 }
510 1 1;
« Phylo/Forest/Node.pm ↑ Summary Phylo/Unparsers/Nhx.pm »