El buscar elegante expansión cadena de ADN Glob-al igual

Question

Estoy tratando de hacer una expansión glob-como de un conjunto de cadenas de ADN que tienen varias bases posibles.

La base de mis cadenas de ADN contiene las letras A, C, G, y T. Sin embargo, puedo tener caracteres especiales como M, que podría ser una A o una C.

Por ejemplo, decir que tengo la cadena:

ATMM

Me gustaría aprovechar esta cadena como entrada y salida de los cuatro posibles cadenas coincidentes:

ATAA ATAC ATCA ATCC

En lugar de la fuerza bruta una solución, siento que debe haber algún truco elegante / de expresiones regulares de Python / Perl para hacer esto.

Gracias por cualquier consejo.

Editar, la corteza gracias por el operador del producto. Esta es mi solución:

Todavía un novato Python, así que apuesto a que hay una mejor manera de manejar cada clave de diccionario que otro bucle. Cualquier sugerencia sería grande.

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

De acuerdo con otros críticos que se parece como una cosa extraña que querer hacerlo. Por supuesto, si usted realmente quiere, no es (como siempre) una manera elegante de hacerlo en Python (2.6 +):

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

solución completa con la manipulación 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

Probablemente se podría hacer algo como esto en Python usando el operador de rendimiento

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 se señaló correctamente que estaba haciendo algunos errores. Aquí está una versión que he probado y funciona.

Answer 3

Esto no es realmente un problema de "expansión" y no es casi ciertamente factible con cualquier expresión regular sensible.

Creo que lo que estás buscando es "cómo generar permutaciones".

Answer 4

Por ejemplo, puede hacer esto 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

expresiones regulares partido cadenas, no se han diseñado para ser convertido en toda cadena que podrían coincidir.

Además, usted está buscando en una gran cantidad de cadenas están siendo emitidas por esto - por ejemplo:

MMMMMMMMMMMMMMMM (16 M's)

produce 65.536 16 cadenas de caracteres - y supongo que las secuencias de ADN son por lo general más que eso.

Podría decirse que cualquier solución a esto es más o menos 'fuerza bruta' desde la perspectiva de la informática, debido a que su algoritmo es O (2 ^ n) de la longitud de cadena original. De hecho, hay un buen montón de trabajo por hacer.

¿Por qué desea para producir todas las combinaciones? que vas a hacer con ellos? (Si usted está pensando en producir todas las posibilidades cadena y luego buscarlo en una secuencia de ADN grande, entonces hay mucho mejores maneras de hacer eso.)