perl - 给定 Perl 的成对关系列表，如何创建唯一的集合？

Question

背景:我从生物数据聚类中得到了一些结果，其中显示了聚类之间共享连接的数量。我想要完成的是将成对关系列表减少为基于共享连接的唯一标识符集。数据格式很简单，它具有三列，分别显示 1) 集群 ID i、2) 集群 ID j 和 3) 之间的共享连接数 i 和j。实际数据的示例位于下面的代码中。

这是我到目前为止的代码:

#!/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