如何根據與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} }; 
}