ลำดับ DNA ซ้ำใน C++

สมมุติว่าเรามีลำดับดีเอ็นเอ ดังที่เราทราบ DNA ทั้งหมดประกอบด้วยชุดของนิวคลีโอไทด์ที่ย่อ เช่น A, C, G และ T ตัวอย่างเช่น "ACGAATTCCG" เมื่อเรากำลังศึกษา DNA ในบางครั้ง การระบุลำดับที่ซ้ำกันภายใน DNA ก็มีประโยชน์

เราต้องเขียนวิธีหนึ่งเพื่อค้นหาลำดับความยาว 10 ตัวอักษร (สตริงย่อย) ทั้งหมดที่เกิดขึ้นมากกว่าหนึ่งครั้งในโมเลกุลดีเอ็นเอ

ดังนั้นหากอินพุตเป็นเหมือน “AAAAACCCCCAAAACCCCCAAAAGGGTTT” เอาต์พุตจะเป็น ["AAAAACCCCCC", "CCCCCAAAAA"]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดอาร์เรย์ ret, n :=ขนาดของ s, สร้างสองชุดที่เรียกว่า visit และ visit2

• กำหนดแผนที่ที่เรียกว่า bitVal

• เก็บค่าที่สอดคล้องกันสำหรับ ACGT เช่น 0123 ลงใน butVal

• หน้ากาก :=0

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

  • หน้ากาก :=หน้ากาก * 4

  • หน้ากาก :=เสาหรือ bitVal[s[i]]

  • หน้ากาก :=หน้ากากและ FFFFF

  • ถ้าฉัน <9 ก็แค่ทำซ้ำต่อไป

    • แทรกดัชนีรูปแบบสตริงย่อย i – 9 ถึง 9 ลงใน ret

    • ใส่เครื่องหมายลงใน visit2.

  • ใส่หน้ากากเข้าไป

• รีเทิร์น

ตัวอย่าง(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, ]