You could use Algorithm::EquivalenceSets.

There are other modules that might be helpful, depending on what you are wanting to do: Graph::TransitiveClosure, Graph::AdjacencyMatrix, etc.

update: Here is an example using Graph:

Thank you all! Algorithm::EquivalenceSets is perfect.

Unfortunately I broke it when trying to install with CPAN. Devel::CheckOS is a pre-req and I think I accidentally hit "no" when I should have hit "yes" (it asked if I was running unix directly after asking if I was running linux! how was I supposed to know the correct answer was "yes"??). Anyway, now it won't let me install it. "clean Devel::CheckOS" doesn't appear to work. Oh well, I'll figure it out eventually. Thanks again for all your help.

You can try cd ~/.cpan/build/Devel-CheckOS* then perl Makefile.PL. This should take you through the set of questions again and let you set it up right. I just accepted all the defaults, despite wondering whether Linux is Unix. Then the usual make, make test and make install.

use strict;
use warnings;

my %groupOfBact = (
   group1 => {
      strain1 => 1,
      strain2 => 1,
      strain4 => 1,
   },
   group2 => {
      strain3 => 1,
      strain4 => 1,
      strain5 => 1,
   },
   group3 => {
      strain6 => 1,
      strain7 => 1,
   },
);


my %bact_by_strain;

for my $bact ( sort keys %groupOfBact ) {
   for my $strain ( keys %{ $groupOfBact{$bact} } ) {
      push @{ $bact_by_strain{$strain} }, $bact;
   }
}


my %delete;

for my $strain ( keys %bact_by_strain ) {
   my $bacts = $bact_by_strain{$strain};
   next if @$bacts < 2;

   my $dst = $bacts->[0];
   for my $src ( @{$bacts}[ 1..$#$bacts ] ) {
      my $src_bact = $groupOfBact{$src};
      my $dst_bact = $groupOfBact{$dst};
      next if $src_bact == $dst_bact;

      %$dst_bact = ( %$dst_bact, %$src_bact );

      $groupOfBact{$src} = $groupOfBact{$dst};

      $delete{$src} = 1;
   }
}

delete @groupOfBact{ keys %delete };


use Data::Dumper qw( Dumper );
print(Dumper(\%groupOfBact));
[download]

It still does some unnecessary merges, though. ( Actually no, I fixed that before posting )

Update: This is the approach moritz mentioned.

Hi Guys, thanks for getting back to me so quickly. I figured I would elucidate some more before I tried any of your suggestions. First of all, the idea is that these are all strains of the same species of bacteria. We have a clustering algorithm that goes through a set of the different strains, finds which genes in all strains are common (i.e. these are "core" genes) and then finds all the genes which are distributed (not unique to any one bacteria, but not ubiquitous throughout all strains). My program counts, for each strain, the number of distributed genes it has in common with any other particular strain. I divide that number by the total number of distributed genes and then subtract by one to find the "distance" between the strains.

After that the bacteria are then grouped together by the nearest lying other bacteria. Groups consist of bacteria that all share at least one common nearest neighboring bacteria. I have that pretty much under control. However, now that I have a Hash that for each group has a list of these nearest neighboring bacteria, but in some cases they overlap. Say, Bacteria A's nearest neighbor is D so it goes to group one. B is nearest neighbor to C, so it goes into its own group two. But then D is nearest neighbor to B, so D and B go into group one, but B is also part of group 2, so those two first groups should just be one.

Basically at this point the only decision that needs to be made is a binary "are any strains in group1 also in any other group? if so, merge the groups".

Suppose you have four bacteria, A, B, C and D. A and B have one gene in common, B and C have one gene in common, and C and D have one in common. Should they all be merged into the same group?

If yes, then your problem represents an undirected graph, and you're looking for connected subsets - which is and a fairly standard problem, and can be solved easily once you turn the hashes around, ie for each gene you store which bacteria they are part of.

I dunno... It looks more like an AI problem than a perl problem. What's the metric you use to determine 'sameness'? And, are the groups 'real' (ie have defined value/property independent of strains) or just buckets to put things in if they are different enough from others?

My inclination would be to use numerical methods (eg principal component analysis) first. But I'm speaking as a biologist, not a perlie.