2

背景：我从生物数据的聚类中得到了一些结果，这些结果显示了集群之间共享连接的数量。我想要完成的是将此成对关系列表减少为基于共享连接的唯一标识符集。数据格式很简单，它有三列显示 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

我希望从这个期望的输出中可以清楚地看出，每一行都应该是一个唯一的集合（并且在上面的代码/输出中添加了选项卡，以便更容易地查看问题）。如果以前有人问过这样的问题，或者在其他页面上说明过这样的问题，请告诉我（在这种情况下我很抱歉）。

4

2 回答 2

1

Graph::UnionFind模块是为这个问题编写的，计算集分区。

#!/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
于 2013-03-05T23:11:53.253 回答
1

The following codes creates the hash in the opposite sense: each identifier is a key, the value is the identifier of the group (by chance equal to one of its members). At the end, the hash is reversed to the structure you tried to build and printed. I am not sure whether the "merging" might occur in your data (imagine CL9 CL11 3000 as the last line), if not, you can safely remove it.

#!/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} };
}
于 2013-03-05T22:52:32.000 回答