building all possible phylogenies.

Question

[Zev.Kronenberg]

Given a starting phylogeny, something like:

(susie_ggo,(clint_ptr,(yri_hsa,chm13_hsa)),susie_pab);

Is there a tool to generate all other possible trees?

i.e:

(susie_ggo,(clint_ptr,(yri_hsa,chm13_hsa)),susie_pab);
(clint_ptr,(susie_ggo,(yri_hsa,chm13_hsa)),susie_pab);
(susie_ggo,(susie_ggo,(yri_hsa,chm13_hsa)),clint_ptr);
...
...

[h.mon]

By the way, why do you want / need this? Just curious.

[5heikki]

This can be done by piping GNU parallel to e.g. awk or sed. I don't have an access to a terminal right now but basically just following this

Answer 1

[h.mon]

This should do it (the sub perm code has been shamelessly stolen from a StackOverflow answer, but I lost track of it):

   #!/usr/bin/env perl
    use strict;
    use warnings;

    my $tree = "(susie_ggo,(clint_ptr,(yri_hsa,chm13_hsa)),susie_pab);";
    my @tips = split( /[\(\),]+/, $tree);
    my $comma = pop @tips;
    my $space = shift @tips;
    (my $topology = $tree) =~ s/[a-z1-9_]+/PLACEHOLDER/gi;

    sub perm;
    foreach (perm \@tips) { 
      my $tmp = $topology;
      foreach my $tip (@$_) {
        $tmp =~ s/PLACEHOLDER/$tip/ ;
      }
      print "$tmp\n";
    }

    sub perm {
      my ($list) = @_;
      my $n = scalar @$list;
      return map [$_], @$list if $n <= 1;
      my @perm;
      for my $i (0 .. $#$list) {
        my @rest = @$list;
        my $val  = splice @rest, $i, 1;
        push @perm, [$val, @$_] for perm \@rest, $n-1;
      }
      return @perm;
    }