C++에서 반복되는 DNA 시퀀스

DNA 서열이 있다고 가정합니다. 우리가 알고 있듯이 모든 DNA는 A, C, G 및 T와 같이 약어로 된 일련의 뉴클레오티드로 구성됩니다(예:"ACGAATTCCG"). DNA를 연구할 때 DNA 내에서 반복되는 서열을 식별하는 것이 때때로 유용합니다.

DNA 분자에서 두 번 이상 발생하는 10자 길이의 모든 시퀀스(하위 문자열)를 찾기 위해 하나의 방법을 작성해야 합니다.

따라서 입력이 "AAAAACCCCCAAAAACCCCCCAAAAGGGTTT"와 같으면 출력은 ["AAAAACCCCC", "CCCCCAAAAA"]가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 배열 ret를 정의하고 n :=s의 크기로 방문 및 방문2라는 두 세트를 생성합니다.

• bitVal이라는 맵을 정의합니다.

• 0123과 같은 ACGT에 해당하는 값을 butVal에 저장합니다.

• 마스크 :=0

• 0 ~ n – 1 범위의 i에 대해

  • 마스크 :=마스크 * 4

  • 마스크 :=마스트 OR bitVal[s[i]]

  • 마스크 :=마스크 AND FFFFF

  • i <9이면 다음 반복을 계속합니다.

    • 하위 문자열 형식 인덱스 i – 9에서 9를 ret에 삽입

    • 방문2에 마크를 삽입합니다.

  • 방문에 마스크 삽입

• 리턴 렛

예시(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, ]