python DNA序列匹配问题求算法

bskay

感觉要用动态规划来做

Springcolor

太牛了，我只想叫一声大神，你好！回复 19# icymirror


   

rubyish

回复 18# anna_bi

1: function catalan

normal:

1. 
   
2. def cat n
   
3.     n < 2 ? 1 : (0...n).reduce(0) { |s, i| s + cat(i) * cat(n - 1 - i) }
   
4. end
   

复制代码

cache:

1. 
   
2. $deze = [1, 1]
   
3. def cat n
   
4.     return $deze[n] if $deze[n]
   
5.     $deze[n] = (0...n).reduce(0) { |s, i| s + cat(i) * cat(n - 1 - i) }
   
6. end
   

复制代码

2:

{'AU' => 1, 'UA' => 1, 'CG' => 1, 'GC' => 1, '' => 1}

ACGUAGCU    (): 0, []: 1
01_3_5_7

'' x AC(GUAGCU) + A[CG]U x [AGCU] + A(CGUA)G x (CU) + A[CGUAGC]U x ''
AC => 0, AU => 1, AG => 0
0 + CG x AGCU + 0 + CGUAGC

count = 1 x X + Y


X: AGCU
'' x AG(CU) + A[GC]U x ''
X = 0 + 1 x 1 = 1

Y: CGUAGC
'' x CG[UAGC] + C(GU)A x [GC] + C(GUAG)C x ''
Y = UAGC + 0 + 0 = Z
Y = Z

Z: UAGC
'' x UA[GC] + U(AG)C x ''
Z = 1 x 1 + 0 = 1


count =
1 x X + Y =
1 x X + Z =
1 x 1 + 1 = 2


   

anna_bi

回复 23# rubyish
谢谢大神


   

rubyish

回复 19# icymirror

1. 
   
2. if series in pairs.keys():
   
3. if series[0] + series[index] in pairs.keys():
   

复制代码

==> good

1. 
   
2. if series in pairs:
   
3. if series[0] + series[index] in pairs:
   

复制代码