寻找优雅的glob-like DNA字符串扩展

Question

我试图做一个具有多个可能基地的DNA字符串集glob-like扩展。

我的DNA串的基础包含字母A，C，G，和T.然而，我可以有特殊字符，如中号，其可以是A或C.

例如，说我有字符串：

ATMM

我想借这个字符串作为输入和输出的四种可能的匹配字符串：

ATAA ATAC ATCA ATCC

而不是蛮力的解决方案，我觉得一定是有优雅的Python/Perl的/正则表达式把戏做到这一点。

谢谢你的任何建议。

编辑，感谢皮质的产品运营商。这是我的解决方案：

还有一个Python新手，所以我打赌有更好的方式来处理比其他for循环每个字典的关键。任何建议都会很棒。

import sys 
from itertools import product 

baseDict = dict(M=['A','C'],R=['A','G'],W=['A','T'],S=['C','G'], 
        Y=['C','T'],K=['G','T'],V=['A','C','G'], 
        H=['A','C','T'],D=['A','G','T'],B=['C','G','T']) 
def glob(str): 
    strings = [str] 

    ## this loop visits very possible base in the dictionary 
    ## probably a cleaner way to do it 
    for base in baseDict: 
     oldstrings = strings 
     strings = [] 
     for string in oldstrings: 
      strings += map("".join,product(*[baseDict[base] if x == base 
           else [x] for x in string])) 
    return strings 

for line in sys.stdin.readlines(): 
    line = line.rstrip('\n') 
    permutations = glob(line) 
    for x in permutations: 
     print x 

Answer 1

同意其他海报，它似乎是一个奇怪的事情想要做。当然，如果你真的想要，有（总是）一种优雅的方式来做到这一点在Python（2.6+）：

from itertools import product 
map("".join, product(*[['A', 'C'] if x == "M" else [x] for x in "GMTTMCA"])) 

与输入处理完整的解决方案：

import sys 
from itertools import product 

base_globs = {"M":['A','C'], "R":['A','G'], "W":['A','T'], 
       "S":['C','G'], "Y":['C','T'], "K":['G','T'], 

       "V":['A','C','G'], "H":['A','C','T'], 
       "D":['A','G','T'], "B":['C','G','T'], 
       } 

def base_glob(glob_sequence): 
    production_sequence = [base_globs.get(base, [base]) for base in glob_sequence] 
    return map("".join, product(*production_sequence)) 

for line in sys.stdin.readlines(): 
    productions = base_glob(line.strip()) 
    print "\n".join(productions) 

Answer 2

这不是一个真正的“扩展”问题，它几乎肯定不适用于任何明智的正则表达式。

我相信你在寻找什么是“如何生成排列”。

Answer 3

例如，你可以做到这一点递归。伪代码：

printSequences(sequence s) 
    switch "first special character in sequence" 
    case ... 
    case M: 
     s1 = s, but first M replaced with A 
     printSequences(s1) 
     s2 = s, but first M replaced with C 
     printSequences(s2) 
    case none: 
     print s; 

Answer 4

你可能使用yield操作

def glob(str): 
     if str=='':   
      yield '' 
      return  

     if str[0]!='M': 
      for tail in glob(str[1:]): 
       yield str[0] + tail     
     else: 
     for c in ['A','G','C','T']: 
      for tail in glob(str[1:]): 
       yield c + tail     
     return 

编辑可以做这样的事情在python：作为正确地指出，我做了一些错误。这是我尝试并运作的一个版本。

Answer 5

正则表达式匹配串，他们不打算变成每一次他们可能匹配的字符串。

而且，你看很多的字符串从这个被输出的 - 例如：

MMMMMMMMMMMMMMMM (16 M's) 

产生65536个16字符串 - 我猜，DNA序列通常都比较长。

可以说，任何解决方案，这是从计算机科学的角度非常“暴力”，因为你的算法是O（2^n）的原始字符串的长度。其实还有很多工作要做。

你为什么要生产的所有组合？你打算怎么处理他们？（如果你想要产生每一个字符串的可能性，然后在一个大的DNA序列中寻找它，那么很多这样做的更好的方法。）