python DNA序列匹配问题求算法

anna_bi

回复 10# icymirror
谢谢谢谢


   

anna_bi

回复 10# icymirror
结果是8吗 不是22啊
[ [ 1, 4 ], [ 5, 8 ], [ 9, 12 ], [ 13, 16 ] ]        [ [ 2, 3 ], [ 6, 7 ], [ 10, 11 ], [ 14, 15 ] ]
[ [ 1, 4 ], [ 5, 8 ], [ 9, 16 ], [ 12, 13 ] ]        [ [ 2, 3 ], [ 6, 7 ], [ 10, 11 ], [ 14, 15 ] ]
[ [ 1, 4 ], [ 5, 12 ], [ 8, 9 ], [ 13, 16 ] ]        [ [ 2, 3 ], [ 6, 7 ], [ 10, 11 ], [ 14, 15 ] ]
[ [ 1, 4 ], [ 5, 16 ], [ 8, 9 ], [ 12, 13 ] ]        [ [ 2, 3 ], [ 6, 7 ], [ 10, 11 ], [ 14, 15 ] ]
[ [ 1, 4 ], [ 5, 16 ], [ 9, 12 ], [ 8, 13 ] ]        [ [ 2, 3 ], [ 6, 7 ], [ 10, 11 ], [ 14, 15 ] ]
[ [ 1, 4 ], [ 5, 16 ], [ 8, 9 ], [ 12, 13 ] ]        [ [ 2, 3 ], [ 6, 15 ], [ 10, 11 ], [ 7, 14 ] ]
[ [ 1, 4 ], [ 5, 16 ], [ 9, 12 ], [ 8, 13 ] ]        [ [ 2, 3 ], [ 6, 15 ], [ 10, 11 ], [ 7, 14 ] ]
[ [ 1, 8 ], [ 4, 5 ], [ 9, 12 ], [ 13, 16 ] ]        [ [ 2, 3 ], [ 6, 7 ], [ 10, 11 ], [ 14, 15 ] ]
[ [ 1, 8 ], [ 4, 5 ], [ 9, 16 ], [ 12, 13 ] ]        [ [ 2, 3 ], [ 6, 7 ], [ 10, 11 ], [ 14, 15 ] ]
[ [ 1, 12 ], [ 4, 5 ], [ 8, 9 ], [ 13, 16 ] ]        [ [ 2, 3 ], [ 6, 7 ], [ 10, 11 ], [ 14, 15 ] ]
[ [ 1, 12 ], [ 5, 8 ], [ 4, 9 ], [ 13, 16 ] ]        [ [ 2, 3 ], [ 6, 7 ], [ 10, 11 ], [ 14, 15 ] ]
[ [ 1, 12 ], [ 4, 5 ], [ 8, 9 ], [ 13, 16 ] ]        [ [ 3, 10 ], [ 6, 7 ], [ 2, 11 ], [ 14, 15 ] ]
[ [ 1, 12 ], [ 5, 8 ], [ 4, 9 ], [ 13, 16 ] ]        [ [ 3, 10 ], [ 6, 7 ], [ 2, 11 ], [ 14, 15 ] ]
[ [ 1, 16 ], [ 4, 5 ], [ 8, 9 ], [ 12, 13 ] ]        [ [ 2, 3 ], [ 6, 7 ], [ 10, 11 ], [ 14, 15 ] ]
[ [ 1, 16 ], [ 4, 5 ], [ 9, 12 ], [ 8, 13 ] ]        [ [ 2, 3 ], [ 6, 7 ], [ 10, 11 ], [ 14, 15 ] ]
[ [ 1, 16 ], [ 4, 5 ], [ 8, 9 ], [ 12, 13 ] ]        [ [ 2, 3 ], [ 6, 15 ], [ 10, 11 ], [ 7, 14 ] ]
[ [ 1, 16 ], [ 4, 5 ], [ 9, 12 ], [ 8, 13 ] ]        [ [ 2, 3 ], [ 6, 15 ], [ 10, 11 ], [ 7, 14 ] ]
[ [ 1, 16 ], [ 5, 8 ], [ 4, 9 ], [ 12, 13 ] ]        [ [ 2, 3 ], [ 6, 7 ], [ 10, 11 ], [ 14, 15 ] ]
[ [ 1, 16 ], [ 5, 8 ], [ 9, 12 ], [ 4, 13 ] ]        [ [ 2, 3 ], [ 6, 7 ], [ 10, 11 ], [ 14, 15 ] ]
[ [ 1, 16 ], [ 5, 12 ], [ 8, 9 ], [ 4, 13 ] ]        [ [ 2, 3 ], [ 6, 7 ], [ 10, 11 ], [ 14, 15 ] ]
[ [ 1, 16 ], [ 4, 5 ], [ 8, 9 ], [ 12, 13 ] ]        [ [ 3, 10 ], [ 6, 7 ], [ 2, 11 ], [ 14, 15 ] ]
[ [ 1, 16 ], [ 5, 8 ], [ 4, 9 ], [ 12, 13 ] ]        [ [ 3, 10 ], [ 6, 7 ], [ 2, 11 ], [ 14, 15 ] ]


   

icymirror

回复 12# anna_bi
不明白这些数字是指什么。

icymirror

回复 12# anna_bi
这些数字是指基因字符位置嘛？那明白你的意思了。

anna_bi

回复 14# icymirror
对啊 是指基因字符位置，那个基因序列如果换成ACGUAGCUACGUAGUCGACU的话，程序会报错


   

anna_bi

回复 14# icymirror
http:  //rosalind.info/  problems/cat/ 这是这个题目的链接 没权限提交链接 所以带了空格



   

rubyish

shibushi
rna = 'ACGUAGCU' * 2
count = 22

rna = 'ACGUAGCU' * 100
count = 13608503128777948922657443526979871651852735451377119775678605848837286264789159184721700297201699277990634072690934696656959074736604858856

shishi ruby

1. #!/usr/bin/ruby
   
2. 
   
3. $deze = {'AU' => 1, 'UA' => 1, 'CG' => 1, 'GC' => 1, '' => 1}
   
4. 
   
5. def gimme k
   
6.     return $deze[k] if $deze.key? k
   
7.     v = 0
   
8.     (1...k.size).step(2) do |i|
   
9.         next unless $deze.key? k[0] + k[i]
   
10.         v += gimme(k[1...i]) * gimme(k[i + 1..-1])
    
11.     end
    
12.     $deze[k] = v
    
13. end
    
14. 
    
15. rna = 'ACGUAGCU' * 100
    
16. puts gimme rna
    

复制代码

anna_bi

回复 17# rubyish
谢谢了，可是我没有学过ruby，可不可以讲下思路啊


   

icymirror

回复 18# anna_bi
rubyish 的代码转换成Python的如下：

1. pairs = {"": 1, "AU": 1, "UA": 1, "CG": 1, "GC":1}
   
2. 
   
3. def RNAPatterns(series):
   
4.     if series in pairs.keys():
   
5.         return pairs[series]
   
6. 
   
7.     count = 0
   
8.     for index in range(1, len(series), 2):
   
9.         if series[0] + series[index] in pairs.keys():
   
10.             count = count + RNAPatterns(series[1:index]) * RNAPatterns(series[index + 1:])
    
11.     pairs[series] = count
    
12. 
    
13.     return count
    
14. 
    
15. def main():
    
16.     dna_serie = "ACGUAGCU" * 2
    
17.     print "Found {0} types of successful split.".format(RNAPatterns(dna_serie))

复制代码

思路是：
用pairs保存查找过程中发现的所有子基因片段和对应的模式数量(用来提高速度)，最后输出当前片段所对应的模式数量。

我之前的代码的问题在于，没有遍历所有的子可能。

anna_bi

回复 19# icymirror
谢谢谢谢