多序列匹配问题

anna_bi

匹配得分（包括gap对gap)，错配得-1分
测试序列：
>Rosalind_7
ATATCCG
>Rosalind_35
TCCG
>Rosalind_23
ATGTACTG
>Rosalind_44
ATGTCTG
输出结果：
-18
ATAT - CCG
- T-  -  - CCG
ATGTACTG
ATGT- CTG
求大神赐教

icymirror

回复 1# anna_bi
匹配的规则是什么？

anna_bi

回复 2# icymirror
ATAT - CCG
- T-  -  - CCG
ATGTACTG
ATGT- CTG
就是得到最大得分。
使每一列尽可能相同，比如第二，六，八列全都相同，得分0.
不相同的话，比如第一列，‘-’分别和三个A不同，得分为-3，三个A相同，得分为0,所以总的分为-3.
第三列，A和‘-’，G，G不同，‘-’和A，G，G不同，得分为-5


   

rubyish

maybe:

1. #!/usr/bin/ruby
   
2. $seq  = [ 'ATATCCG', 'TCCG', 'ATGTACTG', 'ATGTCTG' ]
   
3. $len  = $seq.size
   
4. $sgor = ( 0 .. $len ).map { |x| x * ( x - 1 ) / 2 }
   
5. $that = $sgor[-1]
   
6. $this = { [0] * $len => [ 0, 0 ] }
   
7. $it   = [ 0, 1 ].product( *[ [ 0, 1 ] ] * ( $len - 1 ) )
   
8. 
   
9. def gimme pos
   
10.     $this[pos] = [ -999999999, 0 ]
    
11.     $it.each_with_index do |a, i|
    
12.         poz = ( 0 ... $len ).map { |j| pos[j] - a[j] }
    
13.         next if poz.min < 0
    
14.         char = Hash.new 0
    
15.         poz.each_with_index do |p, j|
    
16.             a[j] > 0 ? char[ $seq[j][p] ] += 1 : char['-'] += 1
    
17.         end
    
18.         scor = $this.key?(poz) ? $this[poz][0] : gimme(poz)
    
19.         scor = char.values.reduce(scor) {|s, e| s + $sgor[e] }
    
20.         scor -= $that
    
21.         $this[pos] = [ scor, i ] if scor > $this[pos][0]
    
22.     end
    
23.     $this[pos][0]
    
24. end
    
25. 
    
26. posi  = $seq.map(&:length)
    
27. score = gimme posi
    
28. align = [''] * $len
    
29. 
    
30. until ( i = $this[posi][1] ) == 0
    
31.     ( 0 ... $len ).each do |j|
    
32.         align[j] += $it[i][j] > 0 ? $seq[j][ posi[j] -= 1 ] : '-'
    
33.     end
    
34. end
    
35. 
    
36. puts score, align.map(&:reverse)
    
37. 
    
38. __END__
    

复制代码