Ищем элегантное расширение цепочки ДНК в виде шара

Question

Я пытаюсь сделать глобальное расширение набора цепочек ДНК, имеющих несколько возможных оснований.

В основе моей цепочки ДНК содержатся буквы A, C, G и T.Однако у меня могут быть специальные символы, такие как M, которые могут быть A или C.

Например, скажем, у меня есть строка:

ATMM

Я хотел бы принять эту строку в качестве входных данных и вывести четыре возможных совпадающих строки:

ATAA ATAC ATCA ATCC

Я считаю, что вместо того, чтобы искать решение методом грубой силы, для этого должен быть какой-то элегантный трюк Python/Perl/Regular Expression.

Спасибо за любой совет.

Изменить, спасибо Cortex за оператора продукта.Это мое решение:

Я все еще новичок в Python, поэтому могу поспорить, что есть лучший способ обработки каждого ключа словаря, чем другой цикл for.Любые предложения были бы великолепны.

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

Вероятно, вы могли бы сделать что-то подобное в Python, используя оператор доходности.

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

Регулярные выражения соответствовать строки, они не предназначены для преобразования в каждую строку, которой они могут соответствовать.

Кроме того, вы видите, что из этого выводится множество строк, например:

MMMMMMMMMMMMMMMM (16 M's)

выдает 65 536 строк по 16 символов - и я предполагаю, что последовательности ДНК обычно длиннее.

Возможно, любое решение этой проблемы - это в значительной степени «грубая сила» с точки зрения информатики, потому что ваш алгоритм равен O (2 ^ n) для исходной длины строки.На самом деле работы предстоит очень много.

Почему вы хотите создать все комбинации?Что ты собираешься с ними делать?(Если вы хотите создать каждую возможную строку, а затем искать ее в большой последовательности ДНК, то есть много лучшие способы сделать это.)