Finding all clades represented in a tree

• Here is a scrap that will return all clades (i.e., maximal sets of leaf/tip taxa descended from a given single node) in a tree, inspired by a question on Evoldir. Other approaches? --Ed.

# get $tree somehow, e.g. from $treeio->next_tree (see Bio::TreeIO)
my @nodes = $tree->get_nodes;
my %clades;
foreach my $n (@nodes) {
    my @desc = $n->get_all_Descendents;
    if ($n->is_Leaf) {
        # degenerate clades...
	$clades{$n->id}++;
    }
    else {
	my @lvs = grep { $_->is_Leaf } @desc;
	$clades{ join(',',sort map {$_->id} @lvs) }++;
    }
}
return keys %clades;

---

• Another approach, using Bio::Tree::Compatible of G. Valiente. If the internal intervening nodes are labeled (have a non-empty id() property), they will also appear in the output.

use Bio::TreeIO;
use Bio::Tree::Compatible;
 
my $tio = Bio::TreeIO->new(-format=>'newick',-fh=>\*DATA);
while (my $t = $tio->next_tree) {
  map { 
      print "(",join(',',@{$_}),")\n" 
  } values %{Bio::Tree::Compatible::cluster_representation( $t ) };
}
 
__DATA__
(((A:5,B:5):2,(C:4,D:4):1):3,E:10);
(((A:5,B:5)x:2,(C:4,D:4)y:1)z:3,E:10)r;

--MAJ