2

主な DNA シーケンス (文字列) が与えられ (文字列 1 とします)、検索する別の文字列 (文字列 2 とします) が与えられます。string2 がサブシーケンスである string1 で最小長のウィンドウを見つける必要があります。
string1 = "abcdefababaef"
string2 = "abf"

私が考えたが、機能していないように見えるアプローチ:
1. 最長共通サブシーケンス (LCS) アプローチを使用し、(LCS の長さ = string2 の長さ) かどうかを確認します。しかし、これにより、string2 がサブシーケンスとして string1 に存在するかどうかがわかりますが、最小のウィンドウではありません。
2. KMP アルゴリズムですが、変更方法がわかりません。
3. string2 にある string1 の {characters: pos of characters} のマップを準備します。次のように: { a : 0,6,8,10
b : 1,7,9
f : 5,12 }
そして、最小ウィンドウを見つけて「abf」の順序を維持するためのいくつかのアプローチ

自分が正しい方向に考えているのか、それとも完全に間違っているのか、よくわかりません。
これには既知のアルゴリズムがありますか、または誰かがアプローチを知っていますか? よろしくお願いします。
前もって感謝します。

4

3 に答える 3

0

動的プログラミング！ここにCの実装があります

#include <iostream>
#include <vector>

using namespace std;

int main() {
    string a, b;
    cin >> a >> b;

    int m = a.size(), n = b.size();
    int inf = 100000000;

    vector < vector < int > > dp (n + 1, vector < int > (m + 1, inf)); // length of min string a[j...k] such that b[i...] is a subsequence of a[j...k]
    dp[n] = vector < int > (m + 1, 0); // b[n...] = "", so dp[n][i] = 0 for each i

    for (int i = n - 1; i >= 0; --i) {
        for (int j = m - 1; j >= 0; --j) {
            if(b[i] == a[j])    dp[i][j] = 1 + dp[i+1][j+1];
            else                dp[i][j] = 1 + dp[i][j+1];
        }
    }

    int l, r, min_len = inf;

    for (int i = 0; i < m; ++i) {
        if(dp[0][i] < min_len) {
            min_len = dp[0][i];
            l = i, r = i + min_len;
        }
    }

    if(min_len == inf) {
        cout << "no solution!\n";
    } else {
        for (int i = l; i < r; ++i) {
            cout << a[i];
        }
        cout << '\n';
    }

    return 0;
}
于 2014-08-28T10:22:41.687 に答える
0

LCSを実行し、 LCS結果の DP テーブルで再帰を使用String1して、すべての最大サブシーケンスを見つけることができます。次に、各LCSのウィンドウ長を計算すると、最小値を取得できます。見つかった現在の最小ウィンドウのサイズをすでに超えている場合は、ブランチを停止することもできます。String2

すべての LCS の読み取りを確認してください:-

http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

于 2014-08-28T09:44:50.997 に答える