script/tree-clan-splitter.pl untested

filter: Statementstmt 0.0% 0 / 296 Branchbran 0.0% 0 / 50 Conditioncond 0.0% 0 / 6 MC/DCmcdc 0.0% 0 / 3 Subroutinesub 0.0% 0 / 35 Podpod 0.0% 0 / 9 totaltotal 0.0% 0 / 399 CC 18 SCAR 27.2
CC
18
Cov
0%
get_boot_spec_from_newick
72.0
_build_classifier
12.0
change_path
12.0
CRAP 15.1
1 #!/usr/bin/env perl
2 # PODNAME: tree-clan-splitter.pl
3 # ABSTRACT: Extract clans (FASTA files) from trees based on taxonomic filters
4 # CONTRIBUTOR: Mick VAN VLIERBERGHE <mvanvlierberghe@doct.uliege.be>
5  
6 use Modern::Perl '2011';
7 use autodie;
8  
9 use Smart::Comments '###';
10 use Getopt::Euclid qw( :vars );
11  
12 use Carp;
13 use File::Copy;
14 use File::Spec;
15 use Tie::IxHash;
16 use List::Compare;
17 use File::Basename;
18 use File::Find::Rule;
19 use Path::Class 'file', 'dir';
20 use List::AllUtils qw(min sum uniq any partition_by);
21  
22 use Bio::MUST::Core;
23 use Bio::MUST::Core::Utils qw(change_suffix);
24 use aliased 'Bio::MUST::Core::Ali';
25 use aliased 'Bio::MUST::Core::Tree';
26 use aliased 'Bio::MUST::Core::SeqId';
27 use aliased 'Bio::MUST::Core::IdList';
28 use aliased 'Bio::MUST::Core::IdMapper';
29 use aliased 'Bio::MUST::Core::Taxonomy';
30 use aliased 'Bio::MUST::Core::Taxonomy::Filter';
31 use aliased 'Bio::MUST::Core::Taxonomy::Criterion';
32 use aliased 'Bio::MUST::Core::Taxonomy::Category';
33 use aliased 'Bio::MUST::Core::Taxonomy::Classifier';
34  
35 ## no critic (RequireLocalizedPunctuationVars)
36 BEGIN{
37 $ENV{Smart_Comments} = $ARGV_verbosity
38 ? join q{ }, map { '#' x (2 + $_) } 1..$ARGV_verbosity : q{} ;
39 }
40 use Smart::Comments -ENV;
41  
42 # Collect tree(s)
43 my @intrees = File::Find::Rule
44 ->file()
45 ->name( qr{ .* $ARGV_tree_suffix $ }xmsi )
46 ->maxdepth(1)
47 ->in($ARGV_indir)
48 ;
49 ### @intrees
50  
51 #### Building classifier...
52 my $tax = Taxonomy->new_from_cache( tax_dir => $ARGV_taxdir );
53 my $classifier = _build_classifier();
54 ### Done!
55  
56 my @stripped_intrees;
57  
58 TREE:
59 for my $intree (sort @intrees) {
60 ### $intree
61  
62 my $tree = Tree->load($intree);
63 my $stripped_intree = $intree;
64 $stripped_intree =~ s/$_//xms for ($ARGV_tree_suffix);
65 push @stripped_intrees, $stripped_intree;
66 ### $stripped_intree
67  
68 # Eventually restore long ids
69 if ($ARGV_map_ids) {
70 # Load IDM file
71 my $idm = IdMapper->load($stripped_intree . '.idm');
72  
73 # Restore long ids
74 $tree->restore_ids($idm);
75 }
76  
77 # Process intree file
78 my $newick = $tree->tree->to_newick( -nodelabels => 1 );
79 $newick =~ s/\'//xmsg;
80 #### $newick
81  
82 my ($boot_hash, $spec_hash) = get_boot_spec_from_newick($newick);
83 #### $boot_hash
84 #### $spec_hash
85  
86 # optionally classify species and store to hashes
87 my %seq_for;
88 my @ps_idxs;
89 my @all_groups;
90  
91 # classify each species
92 for my $spec ( keys %$spec_hash ) {
93  
94 my $seq_id = SeqId->new( full_id => $spec );
95 my $index = $spec_hash->{$spec};
96 my $group = $classifier->classify($seq_id) // 'unwanted';
97 #### $seq_id
98 #### $index
99 #### $group
100  
101 $seq_for{$index}{seq_id} = $seq_id;
102 $seq_for{$index}{group} = $group;
103  
104 push @ps_idxs, $index if $group eq 'target';
105 push @all_groups, $group;
106 }
107  
108 # skip further processing if only one clan is found
109 if ( uniq(@all_groups) == 1 ) {
110 my ($type) = uniq(@all_groups);
111 ### Only one clan found, type: $type
112 if ( $type eq 'target' ) {
113  
114 my $alifile = $stripped_intree . '.ali';
115 my $clanzerofile = $stripped_intree . '-0.ali';
116 my $ali = Ali->load($alifile);
117 $ali->degap_seqs;
118 ### Storing clan in: $clanzerofile
119 $ali->store($clanzerofile);
120 }
121 ### Moving to next tree
122 next TREE;
123 }
124  
125 ### Reading clans for: $stripped_intree
126 # my $clan_hash;
127 my $clan_hash = get_clan_hash($boot_hash);
128 ### Done reading clans for: $stripped_intree
129  
130 my @ps_clans;
131 my @sorted_clans = sort { $clan_hash->{size}{$a} <=> $clan_hash->{size}{$b} }
132 keys %{ $clan_hash->{size} };
133 #### $clan_hash
134 #### @sorted_clans
135  
136 SPLIT_CLAN:
137 for my $clan (@sorted_clans) {
138  
139 my @idxs = @{ $clan_hash->{idxs}{$clan} };
140 my @seq_ids = map { $seq_for{$_}{seq_id} } @idxs;
141 my @full_orgs = map { $_->full_org } @seq_ids;
142 ##### $clan
143 ##### @idxs
144  
145 # skip clans with only one species
146 next SPLIT_CLAN if scalar uniq (@full_orgs) < 2;
147  
148 my @groups = map { $seq_for{$_}{group} } @idxs;
149 my ($type) = uniq(@groups);
150  
151 # keep only strictly targeted clans
152 next SPLIT_CLAN unless scalar uniq (@groups) == 1;
153 next SPLIT_CLAN unless $type eq 'target';
154  
155 push @ps_clans, $clan;
156 ##### $type
157 ##### $clan
158 ##### @idxs
159 ##### @groups
160 }
161 #### @ps_clans
162  
163 unless ( scalar @ps_clans ) {
164 ### No targeted clan(s) found for: $stripped_intree
165 next TREE;
166 }
167  
168 ### Checking clans layout...
169 my ($is_included, $composition_for) = check_inclusions($clan_hash, \@ps_clans);
170 my @main_clans = grep { ! %$is_included{$_} } @ps_clans;
171 #### @main_clans
172  
173 # fit ali to ali2phylip filtering
174 my $alifile = $stripped_intree . '.ali';
175 my $base_ali = Ali->load($alifile);
176 $base_ali->dont_guess;
177 my $alist = $tree->alphabetical_list;
178 #### $list
179 my $ali = $alist->filtered_ali($base_ali);
180  
181 my $n_ali;
182  
183 IDLIST:
184 for my $main_clan ( @main_clans ) {
185  
186 $n_ali++;
187 #### $main_clan
188 my @clan_idxs = @{ $clan_hash->{idxs}{$main_clan} };
189 my @seq_ids = map { $seq_for{$_}{seq_id} } @clan_idxs;
190 my @full_ids = map { $_->full_id } @seq_ids;
191  
192 # apply list to Ali
193 my $list = IdList->new( ids => \@full_ids );
194 my $pruned_ali = $list->filtered_ali($ali);
195 my $outfile = change_suffix($alifile, "-$n_ali.ali");
196  
197 # build corresponding para files
198 my $nlist = $list->negative_list($ali);
199 my $para_ali = $nlist->filtered_ali($ali);
200 my $parafile = change_suffix($alifile, "-$n_ali.para");
201  
202 ### Output alignment in: $outfile
203 ### Output para file in: $parafile
204 $pruned_ali->degap_seqs;
205 $pruned_ali->store($outfile);
206 $para_ali->degap_seqs;
207 $para_ali->store($parafile);
208 }
209 }
210  
211  
212 SUBROUTINES:
213  
214 sub _build_classifier {
215 if ($ARGV_otu_file) {
216 my @categories;
217 open my $in, '<', file($ARGV_otu_file);
218 while ( my $line = <$in> ) {
219 chomp $line;
220 my ($label, $otu) = split ':', $line;
221  
222 my $list = IdList->new( ids => [ split ',', $otu ] );
223 my $filter = $tax->tax_filter( $list );
224 my $criterion = Criterion->new( tax_filter => $filter );
225 my $category = Category->new(
226 label => $label,
227 criteria => [ $criterion ],
228 );
229 push @categories, $category;
230 }
231 close $in;
232  
233 return Classifier->new( categories => \@categories );
234 }
235 if ($ARGV_taxa_list) {
236  
237 open my $in, '<', $ARGV_taxa_list;
238 chomp( my @ids = <$in> );
239 my $id_list = IdList->new(ids => \@ids);
240 return $tax->tax_labeler_from_list($id_list);
241 }
242 }
243  
244 sub change_path {
245 my $infile = shift;
246 my $new_directories = shift;
247 my $level = shift;
248  
249 my ($filename, $directories) = fileparse($infile);
250 # path::class::file
251  
252 my @dirs = split "/", $directories;
253  
254 my $outfile = file($new_directories ? $new_directories : '.',
255 $level ? File::Spec->catdir(splice @dirs, -$level) : '',
256 $filename
257 );
258 return $outfile->stringify;
259 }
260  
261  
262 # build a hash of bipartitions from a Newick tree
263 my $badtree = "ERROR! The tree is not a valid Newick tree.\n";
264  
265 sub get_topology {
266 my ($tree) = @_;
267  
268 $tree =~ s/_{2,}//xmsg; # delete series of underscores
269 $tree =~ s/\)[0-9Ee\.\-]+/)/xmsg; # delete BPs
270 $tree =~ s/:[0-9Ee\.\-]+//xmsg; # delete branch lengths
271  
272 if ($tree =~ m/.*?(\(.*?\);)/xms) { # not fool-proof for bad trees
273 $tree = $1;
274 }
275 else { croak ($badtree); }
276 return $tree;
277 }
278  
279 sub get_topology_with_support {
280 my ($tree) = @_;
281  
282 $tree =~ s/_{2,}//xmsg; # delete series of underscores
283 # $tree =~ s/\)[0-9Ee\.\-]+/)xms/g; # delete BPs
284 $tree =~ s/:[0-9Ee\.\-]+//xmsg; # delete branch lengths
285  
286 if ($tree =~ m/.*?(\(.*?\);)/xms) { # not fool-proof for bad trees
287 $tree = $1;
288 }
289 else { croak ($badtree); }
290 return $tree;
291 }
292  
293 sub get_boot_spec_from_newick {
294  
295 my $intree = shift;
296 my $topology = get_topology($intree);
297 #### $topology
298  
299 # extract species list
300 $topology =~ s/[\(\)\;]+//xmsg;
301 my @specs = split (',', $topology);
302  
303 # build species hash (numbered from 1 to spec_n)
304 my $spec_n = 0;
305 my $spec_hash = {};
306 for my $spec (@specs) {
307 $spec =~ s/^\s+|\s+$//xmsg; # chop leading and trailing spaces
308 $spec_hash->{$spec} = ++$spec_n;
309 }
310 #### $spec_hash
311  
312 my @bips;
313 tie my %boot_hash, 'Tie::IxHash';
314  
315 my $tree = get_topology_with_support($intree);
316 my $char = substr ($tree, 0, 1);
317  
318 while ($char ne ';') {
319  
320 my $badchar = "Maybe there are forbidden characters such as '$char'\n";
321  
322 # open new bipartition
323 if ($char eq '(') {
324 my $key = "." x $spec_n;
325 push @bips, $key;
326 $tree = substr ($tree, 1);
327 }
328  
329 # close last open bipartition
330 elsif ($char eq ')') {
331  
332 # throw error if not balanced parentheses
333 croak ($badtree) if (@bips == 0);
334  
335 # store last bipartition
336 my $key = pop @bips;
337 my $bp_len = 0;
338 if ($key !~ m/^\*+$/xms) { # skip full tree
339 my $tmp = $key;
340 $tmp =~ s/\.//xmsg; # skip trivial bipartitions
341 my ($bp) = $tree =~ m/^\)(\d+)[\),]/xms;
342 $bp_len = length($bp);
343 $boot_hash{$key} = $bp || 1 if ($tmp ne "*");
344 #### %boot_hash
345 }
346 #### before: $tree
347 my $shift = 1 + $bp_len || 0;
348 $tree = substr ($tree, $shift);
349 #### after: $tree
350 }
351  
352 # skip commas and spaces
353 elsif ($char =~ m/[,\s]/xms) {
354 $tree = substr ($tree, 1);
355 }
356  
357 # process species name
358 elsif ($tree =~ m/^([\#A-Za-z0-9_\@\-\.\ ]+(:?\#NEW\#)?)/xms) {
359  
360 # put stars for corresponding species in all open bipartitions
361 my $col = $spec_hash->{$1};
362 $tree = $'; ## no critic (ProhibitMatchVars)
363  
364 for (my $i = 0; $i < @bips; $i++) {
365 substr ($bips[$i], $col - 1, 1, '*');
366 }
367 }
368 # throw error
369 else { croak ($badtree . $badchar); }
370 # read next char
371 $char = substr ($tree, 0, 1);
372 }
373  
374 return \%boot_hash, $spec_hash;
375 }
376  
377  
378 sub char_idxs {
379 my ($bips, $char) = @_;
380  
381 my @indexes;
382 my $offset = 0;
383  
384 my $index = index($bips, $char, $offset);
385 push @indexes, ++$index;
386  
387 while ($index != 0) {
388  
389 $offset = $index;
390 $index = index($bips, $char, $offset);
391  
392 return \@indexes if $index == -1;
393  
394 push @indexes, ++$index;
395 }
396  
397 return \@indexes;
398 }
399  
400 sub get_clan_hash {
401 my $boot_hash = shift;
402  
403 my $n_clan;
404 my %clan_hash;
405 BIP:
406 while ( my ($bip, $boot) = each %$boot_hash ) {
407  
408 # next BIP if $boot < $ARGV_boot_threshold;
409 my $dots = $bip =~ tr/.//; # compute 1st clan size
410 my $stars = $bip =~ tr/*//; # compute 2nd clan size
411  
412 # compute species indexes for both clans
413 my $dots_idxs = char_idxs($bip, '.');
414 my $stars_idxs = char_idxs($bip, '*');
415 $n_clan++;
416  
417 $clan_hash{size}{"dots_clan$n_clan"} = @$dots_idxs;
418 $clan_hash{idxs}{"dots_clan$n_clan"} = $dots_idxs;
419 $clan_hash{boot}{"dots_clan$n_clan"} = $boot;
420 $clan_hash{size}{"stars_clan$n_clan"} = @$stars_idxs;
421 $clan_hash{idxs}{"stars_clan$n_clan"} = $stars_idxs;
422 $clan_hash{boot}{"stars_clan$n_clan"} = $boot;
423 }
424  
425 return \%clan_hash;
426 }
427  
428  
429 sub check_inclusions {
430 my $clan_hash = shift;
431 my $clans = shift;
432  
433 my %is_included;
434 my @previous_clans;
435 my %composition_for;
436 my @sorted_clans = sort { $clan_hash->{size}{$a} <=> $clan_hash->{size}{$b} } @$clans;
437  
438 for my $clan (@sorted_clans) {
439  
440 my $idxs = $clan_hash->{idxs}{$clan};
441  
442 for my $prev_clan (@previous_clans) {
443  
444 my $prev_idxs = $clan_hash->{idxs}{$prev_clan};
445 my $lc_idxs = List::Compare->new( $prev_idxs, $idxs );
446 my $is_subset = $lc_idxs->is_LsubsetR;
447  
448 $is_included{$prev_clan} = 1 if $is_subset == 1;
449 $composition_for{$clan}{$prev_clan} = 1 if $is_subset == 1;
450 }
451 push @previous_clans, $clan;
452 }
453 return \%is_included, \%composition_for;
454 }
455  
456 # TODO: use YAML taxonomic filters as in classify-mcl-out.pl?
457  
458 __END__