تبحث عن توسيع سلسلة DNA أنيقة

Question

أحاول أن أجعل توسع يشبه الأرض من مجموعة من سلاسل الحمض النووي التي لها قواعد متعددة ممكنة.

تحتوي قاعدة سلاسل الحمض النووي على الحروف A، C، G، و T. ومع ذلك، يمكنني الحصول على أحرف خاصة مثل M والتي يمكن أن تكون A أو C.

على سبيل المثال، أقول لدي السلسلة:

ATMM

أرغب في أخذ هذه السلسلة كمدخلات وإخراج الأوتار الأربعة الممكنة:

ATAA ATAC ATCA ATCC

بدلا من القوة الغاشمة حل، أشعر أنني يجب أن يكون هناك بعض خدعة بيثون / بيرل / بيرل العادية للقيام بذلك.

شكرا لك على أي نصيحة.

تحرير، شكرا القشرة لمشغل المنتج. هذا هو الحل الخاص بي:

لا يزال بيثون مبتدئ، لذلك أراهن أن هناك طريقة أفضل للتعامل مع كل مفتاح القاموس من آخر لحلقة. أي اقتراح يمكن أن يكون عظيما.

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

أتفق مع الملصقات الأخرى التي يبدو أنها شيء غريب تريد القيام به. بالطبع، إذا كنت تريد حقا، فهناك (كما هو الحال) وسيلة أنيقة للقيام بذلك في Python (2.6+):

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

الحل الكامل مع معالجة المدخلات:

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

ربما يمكنك القيام بشيء مثل هذا في بيثون باستخدام مشغل العائد

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

تحرير: كما أشار بشكل صحيح، كنت أقدم بعض الأخطاء. إليك نسخة قمت بها ويعمل.

Answer 3

هذا ليس حقا مشكلة "التوسع"، وبالتأكيد غير قابلة للتنفيذ تقريبا مع أي تعبير منتظم معقول.

أعتقد أن ما تبحث عنه هو "كيفية توليد التباديل".

Answer 4

يمكنك على سبيل المثال القيام بذلك بشكل متكرر. كود مزيف:

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. تطابق سلاسل، لا تهدف إلى تحويلها إلى كل سلسلة قد تتطابق.

أيضا، أنت تنظر إلى الكثير من السلاسل التي يتم إخراجها من هذا - على سبيل المثال:

MMMMMMMMMMMMMMMM (16 M's)

تنتج 65،536 16 سلاسل أحرف - وأنا أظن أن تسلسل الحمض النووي عادة ما تكون أطول من ذلك.

يمكن القول أن أي حل لهذه هي "القوة الغاشمة" إلى حد كبير من منظور علوم الكمبيوتر، لأن خوارزمك هي O (2 ^ n) على طول السلسلة الأصلية. هناك بالفعل الكثير من العمل الذي يتعين القيام به.

لماذا تريد إنتاج جميع المجموعات؟ ماذا ستفعل بها؟ (إذا كنت تفكر في إنتاج كل احتمال سلسلة ثم ابحث عنها في تسلسل الحمض النووي الكبير، فهناك كثير أفضل طرق للقيام بذلك.)