エレガントな球状の DNA 文字列展開を探しています

StackOverflow https://stackoverflow.com/questions/1098461

質問

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

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

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

ATMM

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

ATAA ATAC ATCA ATCC

これを強引に解決するのではなく、これを行うにはエレガントな Python/Perl/正規表現のトリックが必要だと感じます。

アドバイスをありがとうございます。

編集、製品オペレーターに感謝します。これが私の解決策です:

まだ 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
役に立ちましたか？

解決

他の投稿者も、それをやりたいと思うのは奇妙に思えるという意見に同意します。もちろん、本当にそうしたい場合は、(いつものように) 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)

他のヒント

おそらく、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

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

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

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

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

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;

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

また、ここから出力される多くの文字列も確認できます。たとえば、次のようになります。

MMMMMMMMMMMMMMMM (16 M's)

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

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

なぜすべての組み合わせを生成したいのですか？彼らをどうするつもりですか？(すべての文字列の可能性を生成し、それを大きな DNA 配列内で検索することを考えている場合は、次のようなものがあります。 多くの もっと良い方法があります。)

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top