C++で繰り返し現れるDNA配列を効率的に検出する方法

DNA配列について考えてみましょう。ご存知の通り、すべてのDNAはA、C、G、Tという4種類のヌクレオチド(塩基)の連なりで構成されています。例えば「ACGAATTCCG」のような文字列です。DNAを研究する際には、配列内に繰り返し現れるシーケンス(部分列)を特定することが重要になる場合があります。

本記事では、DNA分子の中で2回以上出現する10文字長の配列(部分文字列)をすべて見つけるメソッドをC++で実装します。

例えば、入力が「AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT」の場合、出力は["AAAAACCCCC", "CCCCCAAAAA"]となります。

解決のアプローチ

この問題を解くためには、以下の手順に従います。

• 結果を格納する配列retを定義し、n := 文字列sの長さとします。また、visited と visited2 という2つのセットを作成します。
• bitValというマップを定義します。
• A、C、G、Tに対応する値としてそれぞれ0、1、2、3をbitValに格納します。
• mask := 0 で初期化します。
• i を 0 から n−1 までループさせます。
  • mask := mask × 4(2ビット左シフト)
  • mask := mask OR bitVal[s[i]]
  • mask := mask AND 0xFFFFF(下位20ビットのみ保持)
  • i < 9 の場合は次の反復へ進みます。
  • それ以外の場合、visitedにmaskが存在し、かつvisited2に存在しなければ、インデックス i−9 から長さ10の部分文字列をretに挿入し、maskをvisited2に追加します。
  • maskをvisitedに挿入します。
• 最後にretを返します。

ポイント解説： ビットマスクによる効率化

各ヌクレオチド(A・C・G・T)を2ビットで表現することで、10文字の配列全体をわずか20ビットの整数値に変換できます。これにより、文字列同士の比較ではなく高速な整数比較が可能になり、計算量を大幅に削減できます。さらに、0xFFFFFとのAND演算を行うことで、maskには常に直近10文字分の情報だけが保持されます。

また、visited2を用意してすでに結果へ追加済みのパターンを記録することで、同じ配列が3回以上出現しても重複して出力されることを防いでいます。

サンプルコード(C++)

以下の実装を見ると、より理解が深まるでしょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
typedef long long int lli;
class Solution {
public:
    vector<string>findRepeatedDnaSequences(string s) {
        vector <string> ret;
        int n = s.size();
        set <int> visited;
        set <int> visited2;
        map <char, int> bitVal;
        bitVal['A'] = 0;
        bitVal['C'] = 1;
        bitVal['G'] = 2;
        bitVal['T'] = 3;
        lli mask = 0;
        for(int i = 0; i < n; i++){
            mask <<= 2;
            mask |= bitVal[s[i]];
            mask &= 0xfffff;
            if(i < 9) continue;
            if(visited.count(mask) && !visited2.count(mask)){
                ret.push_back(s.substr(i - 9, 10));
                visited2.insert(mask);
            }
            visited.insert(mask);
        }
        return ret;
    }
};
main(){
    Solution ob;
    print_vector(ob.findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"));
}

入力

"AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

出力

[AAAAACCCCC, CCCCCAAAAA]