Vous recherchez élégante extension de chaîne d'ADN semblable à glob

Question

Je suis en train de faire une expansion comme glob d'un ensemble de chaînes d'ADN qui ont de multiples bases possibles.

La base de mes chaînes d'ADN contient les lettres A, C, G et T. Cependant, je peux avoir des caractères spéciaux comme M qui pourrait être un A ou C.

Par exemple, dire que j'ai la chaîne:

ATMM

Je voudrais saisir cette chaîne comme entrée et la sortie des quatre chaînes correspondantes possibles:

ATAA ATAC ATCA ATCC

Plutôt que de force brute une solution, je me sens comme il doit y avoir une certaine élégance Python / Perl astuce / Regular Expression pour ce faire.

Merci pour tout conseil.

Modifier, cortex merci pour l'opérateur du produit. Ceci est ma solution:

Encore un débutant Python, je parie que si il y a une meilleure façon de gérer chaque clé de dictionnaire qu'une autre boucle. Toute suggestion serait 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

D'accord avec les autres commentaires, il semble comme une chose étrange de vouloir faire. Bien sûr, si vous voulez vraiment, il est (comme toujours) d'une manière élégante de le faire en Python (2.6 +):

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

Solution complète avec traitement d'entrée:

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

Vous pourriez probablement faire quelque chose comme ça en python utilisant l'opérateur de rendement

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: Comme on l'a à juste titre que je faisais quelques erreurs. Voici une version que j'ai essayé et fonctionne.

Answer 3

Ce n'est pas vraiment un problème « d'expansion », et il est presque certainement pas faisable avec une expression régulière sensible.

Je crois que ce que vous cherchez est « comment générer des permutations ».

Answer 4

Vous pouvez par exemple faire récursive. Pseudo-code:

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 Match cordes, ils ne sont pas destinés à être transformés en toutes les chaînes qu'ils pourraient correspondre.

En outre, vous regardez beaucoup de cordes étant sortie de ce - par exemple:

MMMMMMMMMMMMMMMM (16 M's)

produit 65.536 16 chaînes de caractères - et je suppose que les séquences d'ADN sont généralement plus que cela.

On peut dire que toute solution à cette question est à peu près « force brute » du point de vue de la science informatique, parce que votre algorithme est O (2 ^ n) sur la longueur de la chaîne d'origine. Il y a en fait beaucoup de travail à faire.

Pourquoi voulez-vous produire toutes les combinaisons? Qu'allez vous faire avec eux? (Si vous envisagez de produire toutes les possibilités de chaîne, puis chercher dans une grande séquence d'ADN, alors il y a beaucoup de meilleures façons de le faire.)