Suchen elegant glob-ähnliche DNA-String Expansion

Question

Ich versuche, eine glob artige Erweiterung eines Satzes von DNA-Strings zu machen, die mehrere mögliche Basen haben.

Die Basis meiner DNA-Strings enthält die Buchstaben A, C, G und T. Aber ich Sonderzeichen wie M aufweisen kann, die ein A oder ein C sein könnte.

Zum Beispiel, sagen, ich habe die Zeichenfolge:

ATMM

Ich möchte diese Zeichenfolge als Eingabe nehmen und geben die vier möglichen passenden Strings:

ATAA ATAC ATCA ATCC

Anstatt brutale Gewalt eine Lösung, fühle ich mich wie es muss ein eleganter Python / Perl / Regular Expression Trick, dies zu tun.

Vielen Dank für jede Beratung.

Bearbeiten dank Cortex für den Produktoperator. Dies ist meine Lösung:

Noch ein Python-Neuling, so wette ich, gibt es eine bessere Art und Weise jeden Wörterbuch Schlüssel als eine anderen for-Schleife zu behandeln. Irgendwelche Vorschläge wäre toll.

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

Vereinbaren Sie mit anderen Plakaten, die es wie eine seltsame Sache scheint zu wollen, zu tun. Natürlich, wenn Sie wirklich wollen, ist es (wie immer) ein eleganter Weg, um es in Python (2.6 +) zu tun:

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

Voll Lösung mit Eingabebehandlung:

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

Sie wahrscheinlich so etwas wie dies in Python mit der Ausbeute Operator tun könnten

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: Wie ganz richtig gesagt war ich ein paar Fehler zu machen. Hier ist eine Version, die ich ausprobiert und funktioniert.

Answer 3

Das ist nicht wirklich ein „Expansion“ Problem und es ist fast sicher mit jedem vernünftigen regulären Ausdruck nicht machbar.

Ich glaube, was Sie suchen ist „wie Permutationen zu erzeugen“.

Answer 4

Sie könnten zum Beispiel tun dies rekursiv. 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 Spiel Saiten, sind sie nicht dazu gedacht, in jede Saite gedreht werden sie übereinstimmen könnten.

Auch sind Sie auf der Suche auf einer Menge von Strings Ausgabe von dieser zu sein - zum Beispiel:

MMMMMMMMMMMMMMMM (16 M's)

produziert 65.536 16 Zeichenkette - und ich vermute, dass DNA-Sequenzen sind in der Regel länger als das.

Diskutierbar auf diesem jede Lösung ist ziemlich viel ‚Brute-Force‘ von einer Informatik Perspektive, weil Ihre Algorithmus O (2 ^ n) auf der ursprünglichen String-Länge ist. Es gibt tatsächlich eine ganze Menge Arbeit getan werden.

Warum wollen Sie alle Kombinationen produzieren wollen? Was werden Sie mit ihnen zu tun? (Wenn Sie denken, jede Zeichenfolge Möglichkeit zu produzieren und dann suchen sie in einer großen DNA-Sequenz, dann gibt es viel bessere Möglichkeiten, das zu tun.)