如何根据与Perl的配对关系列表创建唯一集？

Question

背景：我从生物数据聚类中得到了一些结果，它显示了聚类之间共享连接的数量。我试图完成的是将这种成对关系列表减少为基于共享连接的唯一标识符集。数据格式是直接的，它有三列，显示1）簇ID 我，2）集群ID Ĵ，以及3）我和Ĵ之间的共享连接数。实际数据的示例在下面的代码中。

这里是我到目前为止的代码：

#!/usr/bin/env perl 

use v5.10; 
use strict; 
use warnings; 

my %linkage; 

while (my $line = <DATA>) { 
    my ($i, $j, $score) = split /\s+/, $line; 
    if (exists $linkage{$i} && not exists $linkage{$j}) { 
     push @{$linkage{$i}}, $j; 
    } 
    elsif (exists $linkage{$j}) { 
     push @{$linkage{$j}}, $i; 
    } 
    else { 
     $linkage{$i} = [$j]; 
    } 
} 

for my $key (sort keys %linkage) { 
    say join "\t", $key, join ",", @{$linkage{$key}}; 
} 

__DATA__ 
CL21 CL9  2628 
CL36 CL33 2576 
CL29 CL59 2384 
CL65 CL36 2318 
CL65 CL47 2151 
CL32 CL17 2147 
CL21 CL31 2136 
CL23 CL17 2092 
CL94 CL59 2091 
CL16 CL11 2088 

这将产生：

CL16 CL11 
CL21 CL9,CL31 
CL23 CL17 
CL29 CL59 
CL32 CL17 
CL36 CL33,CL65 
CL65 CL47 
CL94 CL59 

这里有两个问题，我想在解决一些帮助/咨询。第一个问题是第二列（即CL17）中仍然存在重复的条目，我想减少这些条目。第二个问题是如果标识符之前已经被看到，则应该将标识符添加到现有分组中，而不是开始一个新组（即CL65）。请注意，我没有在这个示例中保留输出值，但是您可以看到输入按降序排列，所以根据已经看到的内容以这种方式建立分组是有意义的。

希望的输出：

CL16,CL11 
CL21,CL9,CL31 
CL23,CL17,CL32 
CL29,CL59,CL94 
CL36,CL33,CL65,CL47 

我希望是从该期望的输出，每个行应该是唯一的一组（和接头中的代码/输出加到清楚以上，使其更容易看到问题）。如果以前有人问过这样的问题，或者在其他网页上有过说明，请告诉我（我在此表示歉意）。

Answer 1

的Graph::UnionFind模块是为这个问题写的set partition计算。

#!/usr/bin/env perl 

use v5.10; 
use strict; 
use warnings; 

use Graph::UnionFind; 

my $uf = Graph::UnionFind->new; 
my %vertex; 
while (my $line = <DATA>) { 
    my ($i, $j, $score) = split /\s+/, $line; 

    ++$vertex{$_} for $i, $j; 
    $uf->union($i, $j); 
} 

my %cluster; 
foreach my $v (keys %vertex) { 
    my $b = $uf->find($v); 
    die "$0: no block for $v" unless defined $b; 
    push @{ $cluster{$b} }, $v; 
} 

say join ",", @$_ for values %cluster; 

__DATA__ 
CL21 CL9  2628 
CL36 CL33 2576 
CL29 CL59 2384 
CL65 CL36 2318 
CL65 CL47 2151 
CL32 CL17 2147 
CL21 CL31 2136 
CL23 CL17 2092 
CL94 CL59 2091 
CL16 CL11 2088 

输出：

CL9,CL21,CL31 
CL33,CL65,CL47,CL36 
CL59,CL94,CL29 
CL11,CL16 
CL17,CL23,CL32

Answer 2

以下代码以相反的意义创建散列：每个标识符都是一个键，值是该组的标识符（偶然等于其成员之一）。最后，散列与您尝试构建和打印的结构相反。我不确定在您的数据中是否会出现“合并”（假设CL9 CL11 3000作为最后一行），如果没有，您可以安全地删除它。

#!/usr/bin/perl 
use warnings; 
use strict; 
use feature qw(say); 

my %linkage; 

while (my $line = <DATA>) { 
    my ($i, $j, $score) = split ' ', $line; 
    if (exists $linkage{$i}) { 
     if (exists $linkage{$j}) { 
      warn "Merging $i and $j\n"; 
      $linkage{$_} = $linkage{$i} for grep $linkage{$_} eq $linkage{$j}, keys %linkage; 
     } 
     else { 
      warn "Adding $j to $i\n"; 
      $linkage{$j} = $linkage{$i}; 
     } 
    } 
    elsif (exists $linkage{$j}) { 
     warn "Adding $i to $j\n"; 
     $linkage{$i} = $linkage{$j}; 
    } 
    else { 
     warn "New $i and $j to $i\n"; 
     @linkage{$i, $j} = ($i) x 2; 
    } 
} 

my %groups; 
for my $key (keys %linkage) { 
    push @{ $groups{ $linkage{$key} } }, $key; 
} 

for my $key (sort keys %groups) { 
    say join ',' => @{ $groups{$key} }; 
}