우아한 글로벌 DNA 현악기 확장을 찾고 있습니다

Question

나는 여러 개의 가능한 염기를 갖는 일련의 DNA 현의 글로브와 같은 확장을 만들려고 노력하고 있습니다.

내 DNA 현의 기초에는 문자 A, C, G 및 T가 포함되어 있습니다. 그러나 A 또는 A C와 같은 M과 같은 특수 문자를 가질 수 있습니다.

예를 들어, 문자열이 있다고 가정합니다.

ATMM

이 문자열을 입력으로 가져 와서 가능한 네 가지 일치하는 문자열을 출력하고 싶습니다.

ATAA ATAC ATCA ATCC

용액을 무차별하는 대신, 나는이를 위해 우아한 파이썬/perl/정규식 트릭이 있어야한다고 생각합니다.

조언에 감사드립니다.

편집, 제품 운영자에게 감사합니다. 이것은 내 해결책입니다.

여전히 파이썬 초보자이므로 루프를 위해 각 사전 키를 다른 사전 키보다 처리하는 더 좋은 방법이 있다고 확신합니다. 모든 제안은 좋을 것입니다.

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

이상한 일처럼 보이는 다른 포스터와 동의하십시오. 물론, 당신이 정말로 원한다면, (항상 그렇듯이) 파이썬 (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

수율 연산자를 사용하여 파이썬에서 이와 같은 일을 할 수 있습니다.

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

Regexps 성냥 문자열, 그들은 그들이 일치 할 수있는 모든 문자열로 바뀌는 것은 아닙니다.

또한, 당신은 이것에서 출력되는 많은 문자열을보고 있습니다 - 예를 들어.

MMMMMMMMMMMMMMMM (16 M's)

65,536 16 특성 문자열을 생성합니다.

아마도 이에 대한 모든 해결책은 컴퓨터 과학 관점에서 거의 '무차별'입니다. 알고리즘은 원래 문자열 길이에서 O (2^n)이기 때문입니다. 실제로해야 할 일이 많이 있습니다.

왜 모든 조합을 생산하고 싶습니까? 그들과 무엇을 할 건가요? (모든 현악 가능성을 생성 한 다음 큰 DNA 서열에서 찾으려면 많이 더 나은 방법.)