2

背景：クラスター間の共有接続の数を示す生物学的データのクラスタリングからいくつかの結果があります。私が達成しようとしているのは、このペアワイズ関係のリストを、共有接続に基づく一意の識別子のセットに減らすことです。データ形式は単純で、1）クラスターID i、2）クラスターID j 、および3） iとjの間の共有接続の数を示す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

ここには2つの問題があり、解決するための支援/アドバイスが必要です。最初の問題は、2番目の列（つまり、CL17）にまだ重複するエントリがあることです。これを減らしたいと思います。2番目の問題は、新しいグループ（CL65など）を開始するのではなく、以前に見られた場合は識別子を既存のグループに追加する必要があることです。この例では出力の値を保持していないことに注意してください。ただし、入力が降順でソートされていることがわかります。したがって、これまでに見たものに基づいてこの方法でグループ化を構築することは（私にとって）理にかなっています。

必要な出力：

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

この望ましい出力から、各行が一意のセットである必要があることが明らかであることを願っています（そして、問題を簡単に確認できるように、上記のコード/出力にタブが追加されました）。このような質問が以前に行われたことがあるか、他のページに示されている場合は、お知らせください（その場合はお詫び申し上げます）。

4

2 に答える 2

1

次のコードは、反対の意味でハッシュを作成します。各識別子はキーであり、値はグループの識別子です（偶然にもそのメンバーの1つに等しい）。最後に、ハッシュは、作成して印刷しようとした構造に逆になります。データで「マージ」が発生する可能性があるかどうかはわかりません（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} };
}
于 2013-03-05T22:52:32.000 に答える
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 に答える