Olhando para a expansão seqüência de DNA elegante glob-like

Question

Eu estou tentando fazer um glob-like expansão de um conjunto de cadeias de ADN que têm várias bases possíveis.

A base das minhas cadeias de ADN contém as letras A, C, G e T. no entanto, que podem ter caracteres especiais como M que poderia ser um A ou um C.

Por exemplo, digamos que eu tenho a string:

ATMM

Eu gostaria de aproveitar esta string como entrada e saída dos quatro possíveis cordas correspondentes:

ATAA ATAC ATCA ATCC

Ao invés de força bruta uma solução, eu sinto que deve haver algum truque Expressão elegante Python / Perl / regular para fazer isso.

Obrigado por qualquer conselho.

Editar, graças córtex para o operador do produto. Esta é a minha solução:

Ainda um novato Python, então eu aposto que há uma maneira melhor de lidar com cada chave do dicionário do que outro para loop. Alguma sugestão seria ótimo.

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

Concordo com outros cartazes que parece ser uma coisa estranha querer fazer. Claro, se você realmente quer, não é (como sempre) uma maneira elegante de fazê-lo em Python (2.6 +):

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

solução completa com a manipulação de entrada:

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

Você provavelmente poderia fazer algo parecido com isso em python usando o operador de rendimento

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

EDIT: Como apontou corretamente Eu estava fazendo alguns erros. Aqui está uma versão que eu tentei e funciona.

Answer 3

Isto não é realmente um problema de "expansão" e é quase certamente não factível com qualquer expressão regular sensata.

Eu acredito que o que você está procurando "como gerar permutações".

Answer 4

Você poderia, por exemplo, fazer isso de forma recursiva. Pseudo-código:

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 jogo cordas, eles não estão destinados a ser transformados em cada corda que poderiam corresponder.

Além disso, você está olhando para um monte de cordas estão a ser enviados a partir deste - por exemplo:

MMMMMMMMMMMMMMMM (16 M's)

produz 65.536 16 cadeias de caracteres - e eu estou supondo que as sequências de DNA são geralmente mais do que isso.

Sem dúvida alguma solução para isso é muito bonito 'força bruta' de uma perspectiva de ciência da computação, porque o seu algoritmo é O (2 ^ n) no comprimento string original. Na verdade, há um monte de trabalho a ser feito.

Por que você quer para produzir todas as combinações? O que você vai fazer com eles? (Se você está pensando para produzir todas as possibilidades de cordas e depois olhar para ele em uma sequência de DNA grande, então há muito melhores maneiras de fazer isso.)