4

ADの文字のシーケンスが非常に多く、正確には40億個あるとします。私の目標は、その大きな文字シーケンス内で長さが30に設定されているいくつかの新しい文字シーケンスのインデックスを見つけることです。探しているシーケンスに小さなエラーがある場合（文字が間違っている場合）にも、問題はさらに難しくなります。この問題にどのように取り組むべきですか？

簡単な方法は、40億のテキストファイル全体で一度に1文字を繰り返すことですが、メモリが不足すると、それは永遠にかかります。

ハッシュマップを使用するように言われましたが、キーと値のペアとして何を使用するか正確にはわかりません。正規表現を使用するというアイデアも出てきましたが、それが私の問題で機能するかどうかは完全にはわかりません。方向性の面での助けをいただければ幸いです。ありがとう！

これが私が求めているものの実例です：

4

3 に答える 3

4

これは、最長共通部分列（LCS）と呼ばれる古典的な問題です。それを解決するための多くのアルゴリズムがあります。ゲノムプロジェクトはこの種の検索をたくさん行います。提供されているwikiリンクには多くの例があります。エラーのしきい値は特殊なケースになります。

遺伝子シーケンシングで何かをしていますか？私はあなたが4つの変数だけに言及しているという理由だけで尋ねます:)

于 2012-05-20T19:20:24.617 に答える
3

文字でエンコードすることにより、使用する2つごとに14ビットが無駄になります。1バイトで4つのヌクレオチド文字をエンコードできれば、必要なのは0.5ギガバイトだけです。アルゴリズムについては、ボイヤームーアアルゴリズムjava.lang.String.indexOfのウィキペディアのページでコードを調べることができます。

ところで、これにLuceneインデックスを使用すると、検索を瞬時に行うことができます。アイデアは、30文字のサブシーケンスごとにLuceneの個別のドキュメントとしてインデックスを作成することです。エラー耐性については、Nグラムを使用するか、あいまい検索を行う必要があります（Lucene 4には、編集距離が2または3までの文字列をすばやく見つけるための新しいアルゴリズムがあります）。

于 2012-05-20T19:42:47.287 に答える
1

これは、表現を処理するためのすばやく簡単なコードです。

public static enum Nucleotide { 
    A,B,C,D;
}

public static int setbit(int val, int pos, boolean on) {
    if (on) {
                    // set bit
        return val | (1 << (8-pos-1));
    }
    else {
                    // unset bit
        return val & ~(1 << (8-pos-1));         
    }
}

public static int set2bits(int val, int pos, int bits) {
            // set/unset the first bit 
    val = setbit(val, pos, (bits & 2) > 0);
            // set/unset the second bit
    val = setbit(val, pos+1, (bits & 1) > 0);

    return val;
}

public static int setNucleotide(int sequence, int pos, Nucleotide tide) {
            // set both bits based on the ordinal position in the enum
    return set2bits(sequence, pos*2, tide.ordinal());
}

public static void setNucleotide(int [] sequence, int pos, Nucleotide tide) {
            // figure out which element in the array to work with
    int intpos = pos/4;
            // figure out which of the 4 bit pairs to work with.
    int bitpos = pos%4;
    sequence[intpos] = setNucleotide(sequence[intpos], bitpos, tide);       
}

public static Nucleotide getNucleotide(int [] sequence, int pos) {
    int intpos = pos/4;
    int bitpos = pos%4;
    int val = sequence[intpos];
            // get the bits for the requested on, and shift them
            // down into the least significant bits so we can
            // convert batch to the enum.
    int shift = (8-(bitpos+1)*2);       
    int tide = (val & (3 << shift)) >> shift;
    return Nucleotide.values()[tide];

}

public static void main(String args[]) {
    int sequence[] = new int[4];
    setNucleotide(sequence, 4, Nucleotide.C);
    System.out.println(getNucleotide(sequence, 4));
}

明らかに、多くのビットシフトが行われていますが、コメントの数が少ないことは、何が起こっているかについて意味があるはずです。

もちろん、この表現の欠点は、4つのグループで作業していることです。たとえば10ヌクレオチドが必要な場合は、シーケンスの最後の2ヌクレオチドがそうではないことがわかるように、カウントとともに別の変数をどこかに保持する必要があります。使える。

あいまいマッチングは、他に何もない場合でもブルートフォースで実行できます。Nヌクレオチドのシーケンスを取り込んでから、0から始めて、ヌクレオチド0：N-1と照合し、一致するヌクレオチドの数を確認します。次に、1：N、2：N+1などから移動します。

于 2012-05-21T03:12:27.747 に答える