6

文字列 (DNA シーケンス) のすべての可能な文字列の組み合わせを生成するアルゴリズムはありますか (最大のミスマッチ、最大のハミング距離)。

アルファベットは{A,C,T,G}です。

文字列AGCCと Mismatches の最大数の例2:

Hamming distance is 0
  {AGCC}
Hamming distance is 1
  {CGCC, TGCC, GGCC, AACC, ACCC, ATCC, AGAC, AGTC, ..., AGCG}
Hamming distance is 2
  {?}

考えられるアプローチの 1 つは、特定の文字列のすべての順列を含むセットを生成し、それらを反復処理して、ハミング距離が本来よりも大きいすべての文字列を削除することです。

このアプローチは、指定された 20 文字の文字列と最大ハミング距離 5 によって、非常にリソースを消費します。

そのための別のより効率的なアプローチ/実装はありますか?

4

1 に答える 1