寻找优雅的水珠般的DNA串扩张

Question

我试图使一组具有多个可能的碱基的DNA串的水珠样扩张。

我的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

您也许可以使用运营商的产量做这样的事在python

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

编辑：由于正确地指出，我做了一些错误。这里是我尝试了和工作的版本。

Answer 3

这是不是一个真正的“扩张”问题和它几乎肯定不可行与任何合理的正则表达式。

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

Answer 4

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

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 5

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

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

MMMMMMMMMMMMMMMM (16 M's)

产生65536个16字符串 - 和我猜测，DNA序列通常长于。

可以说任何解决方案，这是从计算机科学的角度几乎“蛮力”，因为你的算法是对原始字符串长度O（2 ^ N）。实际上，有相当多的工作要做。

为什么要生产的所有组合？你打算怎么跟他们做什么？ （如果你想制作每串可能性，然后寻找它在一个大的DNA序列，然后还有的多的更好这样做的方式。）