C++ में न्यूनतम अनुवांशिक उत्परिवर्तन

मान लीजिए कि हमारे पास एक जीन स्ट्रिंग है। इसे एक स्ट्रिंग द्वारा दर्शाया जा सकता है जिसकी लंबाई 8 है, यह स्ट्रिंग इन अक्षरों [ए, सी, जी, टी] से मिलकर बनी है। अब विचार करें कि हम एक उत्परिवर्तन के बारे में जांच करना चाहते हैं, जहां एक उत्परिवर्तन वास्तव में जीन स्ट्रिंग में एक एकल वर्ण बदल गया है। एक उदाहरण के रूप में, "AACCGTTT" को "AACCGTTA" की तरह बदल दिया गया है, जो 1 उत्परिवर्तन है।

हमारे पास एक दिया गया जीन "बैंक" भी है, जहां सभी वैध जीन उत्परिवर्तन मौजूद हैं। एक जीन को वैध जीन स्ट्रिंग बनाने के लिए बैंक में होना चाहिए।

अब मान लीजिए कि हमने 3 चीजें दी हैं - प्रारंभ, अंत, बैंक, हमारा कार्य यह निर्धारित करना है कि "प्रारंभ" से "अंत" में बदलने के लिए आवश्यक न्यूनतम संख्या में उत्परिवर्तन क्या हैं। यदि प्रारंभ से अंत तक रूपांतरण संभव नहीं है, तो वापसी -1.

इसलिए, यदि इनपुट start ="AACCGGTT", end ="AAACGGTA", Bank =["AACCGGTA", "AACCGCTA", "AAACGGTA"] जैसा है, तो आउटपुट 2 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• फ़ंक्शन putStar() को परिभाषित करें, इसमें s,

  . लगेगा

• एक सरणी रिट परिभाषित करें

• प्रारंभ करने के लिए i:=0, जब मैं आकार का s, अद्यतन (i से 1 बढ़ाएँ), करें -

  • अस्थायी :=0 से i-1 में s का प्रतिस्थापन "*" + अनुक्रमणिका i + 1 से अंत तक s का प्रतिस्थापन

  • रिट के अंत में अस्थायी डालें

• वापसी रिट

• मुख्य विधि से निम्न कार्य करें -

• ग्राफ़ नामक एक मानचित्र को परिभाषित करें।

• इनिशियलाइज़ i :=0 के लिए, जब i <बैंक का आकार, अपडेट करें (i 1 से बढ़ाएँ), करें -

  • एस:=बैंक[i]

  • आउट =पुटस्टार (बैंक [i])

  • इनिशियलाइज़ j :=0 के लिए, जब j <साइज़ ऑफ़ आउट, अपडेट करें (1 से j बढ़ाएँ), करें

    • ग्राफ़ के अंत में s डालें[out[j]]

• एक कतार को परिभाषित करें q

• q में प्रारंभ डालें

• देखे गए एक सेट को परिभाषित करें

• विज़िट में प्रारंभ डालें

• lvl को इनिशियलाइज़ करने के लिए:=1, जब q खाली न हो, तो अपडेट करें (lvl को 1 से बढ़ाएँ), करें -

  • sz :=q का आकार

  • जबकि sz गैर-शून्य है, प्रत्येक पुनरावृत्ति में sz घटाएं, −

    . करें

    • नोड:=q का पहला तत्व

    • q से तत्व हटाएं

    • आउट =पुटस्टार (नोड)

    • इनिशियलाइज़ i:=0 के लिए, जब i <साइज़ ऑफ़ आउट, अपडेट (i 1 से बढ़ाएँ), do−

      • आप:=बाहर[i]

      • इनिशियलाइज़ j :=0 के लिए, जब j <ग्राफ़ का आकार [u], अपडेट करें (1 से j बढ़ाएँ), करें -

        • वी:=ग्राफ[यू, जे]

        • अगर vi विज़िट किया गया है, तो लूप से बाहर आएं

        • यदि v अंत के समान है, तो lvl लौटाएं

        • विज़िट किए गए में v डालें

        • q में v डालें

• वापसी -1

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   vector <string> putStar(string s){
      vector <string> ret;
      for(int i = 0; i < s.size(); i++){
         string temp = s.substr(0, i) + "*" + s.substr(i + 1);
         ret.push_back(temp);
      }
      return ret;
   }
   int minMutation(string start, string end, vector<string>& bank) {
      unordered_map < string, vector <string> > graph;
      for(int i = 0; i < bank.size(); i++){
         string s = bank[i];
         vector <string> out = putStar(bank[i]);
         for(int j = 0; j < out.size(); j++){
            graph[out[j]].push_back(s);
         }
      }
      queue <string> q;
      q.push(start);
      set <string> visited;
      visited.insert(start);
      for(int lvl = 1; !q.empty(); lvl++){
         int sz = q.size();
         while(sz--){
            string node = q.front();
            q.pop();
            vector <string> out = putStar(node);
            for(int i = 0; i < out.size(); i++){
               string u = out[i];
               for(int j = 0; j < graph[u].size(); j++){
                  string v = graph[u][j];
                  if(visited.count(v)) continue;
                  if(v == end) return lvl;
                  visited.insert(v);
                  q.push(v);
               }
            }
         }
      }
      return -1;
   }
};
main(){
   Solution ob;
   vector<string> v = {"AACCGGTA", "AACCGCTA", "AAACGGTA"};
   cout << (ob.minMutation("AACCGGTT", "AAACGGTA", v));
}

इनपुट

"AACCGGTT", "AAACGGTA", {"AACCGGTA", "AACCGCTA", "AAACGGTA"}

आउटपुट

2