2

長さ 100 文字の文字列の膨大なリスト (N = ~100 万) があり、それらの間の重複を見つけようとしています。たとえば、1 つの文字列は次のようになります。

XXXXXXXXXXXXXXXXXXAACTGCXAACTGGAAXA (and so on)

すべての文字列と他のすべての文字列の最長重複値を含む N 行 N 列の行列を作成する必要があります。私の現在の方法は（疑似コード）です

すべての文字列を配列に読み込む

空の NxN 行列を作成する

各文字列をより高い配列インデックスを持つすべての文字列と比較します (比較のやり直しを避けるため)

最長オーバーラップを行列に書き込む

他にも多くのことが行われていますが、マトリックスを構築するためのより効率的な方法が本当に必要です。最も強力なコンピューティング クラスターを使用しても、この方法を手に入れるには数日かかります。

ご想像のとおり、これらは DNA フラグメントです。X は「ワイルドカード」 (しきい値の品質スコアを下回るプローブ) を示し、他のすべてのオプションは塩基 (A、C、T、または G) です。四分木アルゴリズムを書き込もうとしましたが、この方法はメモリを大量に消費します。

より効率的な方法についてご提案いただければ幸いです。私は C++ で作業していますが、疑似コード/アイデアまたは他の言語コードも非常に役立ちます。

編集:私の現在の方法を説明するいくつかのコードの抜粋。コンセプトに特に関係のないものはすべて削除されました

//part that compares them all to each other
for (int j=0; j<counter; j++) //counter holds # of DNA
    for (int k=j+1; k<counter; k++)
        int test = determineBestOverlap(DNArray[j],DNArray[k]);

//boring stuff

//part that compares strings. Definitely very inefficient,
//although I think the sheer number of comparisons is the main problem
int determineBestOverlap(string str1, string str2)
{
    int maxCounter = 0, bestOffset = 0;
    //basically just tries overlapping the strings every possible way
    for (int j=0; j<str2.length(); j++)
    {
        int counter = 0, offset = 0;
        while (str1[offset] == str2[j+offset] && str1[offset] != 'X') 
        {
              counter++;
              offset++;
        }
        
        if (counter > maxCounter)
        {
                    maxCounter = counter;
                    bestOffset = j;
        }
    }
    return maxCounter; 
} //this simplified version doesn't account for flipped strings
4

2 に答える 2

0

各文字列をシフトするなど、相互に比較する必要があるという事実を改善する方法はあまりありません。それ自体が非常に長いため、計算クラスターが最良のアプローチのようです。

改善方法がわかる唯一のことは、文字列比較自体です。A、C、T、G、および X をバイナリ パターンに置き換えます。

  • A = 0x01
  • C = 0x02
  • T = 0x04
  • G = 0x08
  • X = 0x0F
このようにして、1 つの項目を 4 ビット、つまり 1 バイトあたり 2 つ (これは良い考えではないかもしれませんが、調査するための可能なオプションです) に格納し、それらを AND 演算ですばやく比較することができます。連続するゼロ以外の値の数を数えなければなりません。これはワイルドカードを処理する方法にすぎません。申し訳ありませんが、全体的な比較の複雑さを軽減するためのより良いアイデアはありません。

于 2014-03-02T21:57:30.983 に答える