Alla ricerca di un'elegante espansione della stringa di DNA simile a un globo

Question

Sto cercando di creare un'espansione simile a un globo di un insieme di stringhe di DNA che hanno più basi possibili.

La base delle mie stringhe di DNA contiene le lettere A, C, G e T.Tuttavia, posso avere caratteri speciali come M che potrebbe essere una A o una C.

Ad esempio, supponiamo che io abbia la stringa:

ATMM

Vorrei prendere questa stringa come input e restituire le quattro possibili stringhe corrispondenti:

ATAA ATAC ATCA ATCC

Piuttosto che una soluzione con forza bruta, sento che ci deve essere qualche elegante trucco Python/Perl/Espressione regolare per farlo.

Grazie per qualsiasi consiglio

Modifica, grazie Cortex per l'operatore del prodotto.Questa è la mia soluzione:

Sono ancora un principiante di Python, quindi scommetto che esiste un modo migliore per gestire ciascuna chiave del dizionario rispetto a un altro ciclo for.Qualsiasi suggerimento sarebbe molto apprezzato.

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

Sono d'accordo con altri manifesti che sembra una cosa strana di voler fare. Naturalmente, se si vuole veramente, non v'è (come sempre) un modo elegante per farlo in Python (2.6 +):

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

soluzione completa con la gestione di input:

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

Probabilmente si potrebbe fare qualcosa di simile in Python utilizzando l'operatore di 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: Come ha giustamente fatto notare che stavo facendo un paio di errori. Ecco una versione che ho provato e funziona.

Answer 3

Questo non è davvero un problema di "espansione" e non è quasi certamente fattibile con qualsiasi espressione regolare ragionevole.

Credo che quello che stai cercando è "come generare permutazioni".

Answer 4

Si potrebbe per esempio fare questo in modo ricorsivo. Pseudo-codice:

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

Espressioni regolari incontro stringhe, non sono destinate a essere trasformate in ogni stringa a cui potrebbero corrispondere.

Inoltre, stai osservando molte stringhe generate da questo, ad esempio:

MMMMMMMMMMMMMMMM (16 M's)

produce 65.536 stringhe da 16 caratteri - e immagino che le sequenze di DNA siano solitamente più lunghe di così.

Probabilmente qualsiasi soluzione a questo è praticamente "forza bruta" dal punto di vista informatico, perché il tuo algoritmo è O (2 ^ n) sulla lunghezza della stringa originale.In realtà c'è parecchio lavoro da fare.

Perché vuoi produrre tutte le combinazioni?Cosa ne farai?(Se stai pensando di produrre ogni possibilità di stringa e poi cercarla in una grande sequenza di DNA, allora ci sono tanto modi migliori per farlo.)