2

我正在尝试对一组具有多个可能碱基的 DNA 字符串进行类似球状的扩展。

我的 DNA 字符串的碱基包含字母 A、C、G 和 T。但是，我可以有特殊字符，例如 M，可以是 A 或 C。

例如，假设我有字符串：

ATMM

我想将此字符串作为输入并输出四个可能的匹配字符串：

ATAA ATAC ATCA ATCC

我觉得必须有一些优雅的 Python/Perl/正则表达式技巧才能做到这一点，而不是蛮力解决方案。

谢谢你的任何建议。

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

仍然是 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
4

5 回答 5

2

同意其他发帖人的观点，这似乎是一件奇怪的事情。当然，如果你真的想要，在 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)
于 2009-07-08T14:54:21.413 回答
1

您可能可以使用 yield 运算符在 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

编辑：正如正确指出的那样，我犯了一些错误。这是我尝试过并可以使用的版本。

于 2009-07-08T14:37:12.563 回答
0

这并不是真正的“扩展”问题，而且几乎可以肯定任何合理的正则表达式都不可行。

我相信您正在寻找的是“如何生成排列”。

于 2009-07-08T14:31:13.743 回答
0

例如，您可以递归地执行此操作。伪代码：

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;
于 2009-07-08T14:35:40.197 回答
0

正则表达式匹配字符串，它们并不打算变成它们可能匹配的每个字符串。

此外，您正在查看由此输出的大量字符串 - 例如：

MMMMMMMMMMMMMMMM (16 M's)

产生 65,536 个 16 个字符串 - 我猜 DNA 序列通常比这更长。

从计算机科学的角度来看，可以说任何解决方案都是“蛮力”，因为您的算法在原始字符串长度上是 O(2^n)。其实还有很多工作要做。

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

于 2009-07-08T14:45:23.067 回答