| 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__ |