代码之家 › 专栏 › 技术社区 › Rich

寻找优雅的球形DNA串扩展

dna-sequence glob permutation python

Rich · 技术社区 · 16 年前

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

我的DNA字符串的基部包含字母A、C、G和T。但是,我可以有像M这样的特殊字符,可以是A或C。

例如,假设我有字符串:

ATMM

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

ATAA ATAC ATCA ATCC

我觉得必须有一些优雅的python/perl/RegularExpression技巧才能做到这一点,而不是强行执行解决方案。

谢谢你的建议。

编辑,感谢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

5 回复 | 直到 16 年前

Joakim Lundborg 16 年前

同意其他海报,这似乎是一个奇怪的事情要做。当然,如果您真的想这样做,有(一如既往)一种用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)

Il-Bhima 16 年前

在Python中,您可能可以使用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

编辑:正如正确指出的那样,我犯了一些错误。这是一个我试用过的版本。

Alnitak 16 年前

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

我相信你要找的是“如何产生排列”。

schnaader 16 年前

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

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;

ijw 16 年前

正规表示法比赛字符串,它们并不打算被转换成它们可能匹配的每一个字符串。

此外,您还会看到许多字符串正从中输出,例如:

MMMMMMMMMMMMMMMM (16 M's)

产生65536个16字符的字符串-我猜DNA序列通常比这个长。

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

为什么要生产所有的组合?你打算怎么处理它们?(如果你想产生每一个可能的串,然后寻找一个大的DNA序列,那么 许多的 更好的方法。)