python DNA序列匹配问题求算法

anna_bi

有一个DNA序列，ACGUAGCU，A和U，C和G匹配，但是中间不能有交叉，比如第二位C和第六位G不能匹配，因为他俩要是匹配，第三位G必定只能跟第七位C匹配，这样的话就有交叉。所以这个序列只有两种匹配方式，第一位A和第四位U,第二位C和第三位G,第五位A和第八位U,第六位G和第七位C。或者第一位A和第八位U,第四位U和第五位A,第二位C和第三位G,第六位G和第七位C匹配。求有多少种匹配的可能，序列有300bp，希望运行时间不要太长。求大神算法。

icymirror

回复 1# anna_bi
思路大体如下：
0. 读入一个基因进入等待匹配序列
1. 读入一个基因字符，（成功读取，进行后续判断，失败读取－－假设为到总串尾部，整理并输入之前的匹配串。）
2. 分两支进行匹配检测：
    1). 进行后向匹配（和当前基因字符之前进入序列的字符进行匹配）
        如果匹配，在等等匹配的字符序列中移除被匹配的字符，进入序列完成检测
              如果匹配的结果使得剩余的待匹配序列长度变为0，那么，记录此子序列的开始和结束位置，从下个基因字符开始新的子序列匹配过程（分布式或者并行运算时，这里可以分支出新的进程作子序列匹配），并且重复匹配过程
        如果不匹配，把当前字符也放入到等待匹配序列里面去。
        跳转到步骤1开始循环。
    2). 进行前向匹配（就是和后面要读进来的字符进行匹配）
        如果匹配，读取位置跳过下一基因字符
                如果无法读取，说明到文件尾，
        如果不匹配，把当前字符也放入到等待匹配序列里面去。
        跳转到步骤1开始循环。

问题是：这个算法需要的太多的空间（线程、存储），不太合适单机跑－－当数据量太大时。

patagonia2

数据量太大是问题

substr函数

LZ我有2个问题。
问题1：
dna 序列
len(dna) 是多少？

问题2：
这对马？

dan = ACGUAGCU
[AU|UA] [GC|CG]

[ [ 1, 4 ], [ 5, 8 ] ]        [ [ 2, 3 ], [ 6, 7 ] ]
[ [ 1, 8 ], [ 4, 5 ] ]        [ [ 2, 3 ], [ 6, 7 ] ]

COUNT = 2

dna = ACGUAGCUACGUAGCU
[AU|UA] [GC|CG]

[ [ 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 ] ]

COUNT = 22

substr函数

回复 2# icymirror


大神。
有没有代码？
学习学习？

icymirror

回复 4# substr函数
对于问题一，楼主的原贴里面写了，是：300bp (估计应当是300pb=300*1024 Tb = 300 * 1024 * 1024 Mb, 数据量还是相当大的。)

substr函数

回复 6# icymirror


谢谢大神

假设是长度 100 好了
len(dna) = 100

我想学习学习大神的代码

anna_bi

回复 4# substr函数
是这样的啊


   

anna_bi

回复 2# icymirror
大神可不可以写下代码？


   

icymirror

少量数据的代码如下：

1. total_patterns = 0
   
2. 
   
3. def is_match(item, to_check):
   
4.     available_pairs = (('A', 'U'), ('U', 'A'), ('G', 'C'), ('C', 'G'))
   
5.     return (item, to_check) in available_pairs
   
6. 
   
7. def search_pattern(series, start, current, unmatched, tabs=0):
   
8.     if is_match(series[current], unmatched[-1]) == True:
   
9.         if current == len(series) - 1:
   
10.             if len(unmatched[:-1]) == 0:
    
11.                 # print "Pattern: " + "--" * tabs + "start-{0}, end-{1}".format(start, current)
    
12.                 # print "Found SUCCESSFUL match!\n"
    
13.                 global total_patterns
    
14.                 total_patterns = total_patterns + 1
    
15.             else:
    
16.                 # print "Railed reach end!\n"
    
17.                 pass
    
18.         else:
    
19.             if len(unmatched[:-1]) == 0:
    
20.                 # print "Pattern: " + "--" * tabs + "start-{0}, end-{1}".format(start, current)
    
21.                 search_pattern(series, current + 1, current + 2, series[current + 1], tabs + 1)
    
22.             else:
    
23.                 search_pattern(series, start, current + 1, unmatched[:-1], tabs)
    
24. 
    
25.     if current == len(series) - 1:
    
26.         return
    
27.     if is_match(series[current], series[current + 1]) == True:
    
28.         current = current + 2
    
29.         search_pattern(series, start, current, unmatched, tabs)
    
30.     else:
    
31.         unmatched = unmatched + series[current]
    
32.         current = current + 1
    
33.         search_pattern(series, start, current + 1, unmatched, tabs)
    
34. 
    
35. def main():
    
36.     dna_serie = "ACGUAGCUACGUAGCU"
    
37.     search_pattern(dna_serie, 0, 1, dna_serie[0])
    
38.     print "Found {0} types of successful split.".format(total_patterns)
    
39. 
    
40. if __name__ == '__main__':
    
41.     main()

复制代码

可以把注释用的"#"号去除，去查看下匹配的各个子串的起始和结束位置。
但是这个代码只适用于少量数据的情况下。
大量数据的情况下，代码就不一样了。
很多的过程要再分拆。