perl聚类

3gipnet

• @12@vip.com#20120307/1
  
• BCDBCDBD
  
• +
  
• AAAAAAAA
  
• @18@vip.com#20120307/1
  
• BBDACCDA
  
• +
  
• AAAAAAAA
  
• @13@vip.com#20120307/1
  
• BCDBCDAA
  
• +
  
• AAAAAAAA
  
• @14@vip.com#20120307/1
  
• BCDAAABC
  
• +
  
• AAAAAAAA
  
• @15@vip.com#20120307/1
  
• BCDCCABC
  
• +
  
• AAAAAAAA
  
• @16@vip.com#20120307/1
  
• BCDBBABC
  
• +
  
• AAAAAAAA
  
• @12@vip.com#20120307/1
  
• BBDABBDA
  
• +
  
• AAAAAAAA
  
• ...
  

我想对上面的数据进行一个聚类，每四行是一段，假设每段第二行前三个字符相同，且后五个字符差异度（对应位置不同，比如BC和BB差异度为1，BC和AB差异度为2）相近的归为一段、类，（计算出所有的差异度，选取差异度最大的那段为第一凝聚点，再在第一凝聚点距离D（D=2d）之外寻找第二凝聚点，依此类推，直到遍历所有为止）　　每类之间空行隔开，生成下面这样的结果：

• BBD BBD BBDACCDA BBDABBDA
  
• 
  
  
• BCD BCD BCDBCDBD BCDBCDAA
  
• 
  
  
• BCD BCD BCDAAABC BCDBBABC
  
• BCD BCD BCDAAABC BCDCCABC
  

　　————————————————————————————————————————————
    比如：
1、BCDAAABC 2、BCDBBABC 3、BCDCCABC 4、BCDBCDBD 5、BCDBCDAA
五个字符串，1和2的差异度是2；1和3的差异度是2；1和4的差异度是4；1和5的差异度是5；2和3的差异度是2；2和4的差异度是3；2和5的差异度是4；3和4的差异度是3；3和5的差异度是4；4和5的差异度是2；
那么：
   1 2 3 4 5
1 0 2 2 4 5
2    0 2 3 4
3       0 3 4
4          0 2
5             0
那么2的频率是最多的，所有差异度为2的归为一类，所以1、2；1、3；4、5；归为一类；所有的都有归类了，就结束。如果还没有结束，再选下一个，也就是4，所有差异度为4的归为一类。。直到所有的归为一类。。。


—————————————————————————————————————————————————






1 #!/usr/bin/perl
2 my ( $A, $B ) = ( 3, 5 );
3 my ( @A, %G );
4
5 while (<>) {
6     chomp( my $L = <> );
7     push @A, $L; <>, <>;
8 }
9
10 for my $i ( 0 .. $#A - 1 ) {
11     for my $j ( $i + 1 .. $#A ) {
12         next if substr( $A[$i], 0, $A ) ne substr( $A[$j], 0, $A );
13         my $dif;
14         substr( $A[$i], $_, 1 ) ne substr( $A[$j], $_, 1 ) and $dif++
15           for $A .. $A + $B - 1;
16         push @{ $G{$dif} }, [ $i, $j ];
17     }
18 }
19
20 for my $v ( sort { @$b <=> @$a } values %G ) {
21     for my $ij (@$v) {
22         my @H = map substr( $A[$_], 0, $A ), @$ij;
23         print join( "\t", @H, @A[@$ij] ), $/;
24     }
25     print $/;
26 }