2

複数の可能な塩基を持つ一連の DNA 文字列のグロブのような拡張を作成しようとしています。

私の DNA 文字列のベースには、A、C、G、および T の文字が含まれています。ただし、A または C の M のような特殊文字を使用することはできます。

たとえば、次の文字列があるとします。

ATMM

この文字列を入力として取り、一致する可能性のある 4 つの文字列を出力したいと思います。

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
4

5 に答える 5

2

やりたいことは奇妙なことのように思えるという他のポスターに同意します。もちろん、本当にやりたい場合は、(いつものように) 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)
于 2009-07-08T14:54:21.413 に答える
1

おそらく、yield演算子を使用して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

編集：正しく指摘されたように、私はいくつかの間違いを犯していました。これが私が試したバージョンです。

于 2009-07-08T14:37:12.563 に答える
0

正規表現は文字列と一致します。一致する可能性のあるすべての文字列に変換されることを意図したものではありません。

また、これから出力される多くの文字列を見ています-たとえば：

MMMMMMMMMMMMMMMM (16 M's)

65,536個の16文字の文字列を生成します-そして、DNA配列は通常それよりも長いと思います。

おそらく、これに対する解決策は、コンピュータサイエンスの観点からは、ほとんど「ブルートフォース」です。これは、アルゴリズムが元の文字列の長さに対してO（2 ^ n）であるためです。実際には、やるべきことがかなりたくさんあります。

なぜすべての組み合わせを作りたいのですか？あなたは彼らをどうするつもりですか？（すべての文字列の可能性を生成し、それを大きなDNA配列で探すことを考えている場合は、それを行うためのはるかに優れた方法があります。）

于 2009-07-08T14:45:23.067 に答える
0

これは実際には「拡張」の問題ではなく、適切な正規表現ではほぼ確実に実行できません。

あなたが探しているのは「順列を生成する方法」だと思います。

于 2009-07-08T14:31:13.743 に答える
0

たとえば、これを再帰的に行うことができます。擬似コード:

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;
于 2009-07-08T14:35:40.197 に答える