अधिकतम स्कोर के साथ दो अनुक्रमों के सभी संरेखणों को प्रिंट करना

Question

Sequence Alignment काफी मानक समस्या है और जैव सूचना विज्ञान के क्षेत्र में डीएनए या प्रोटीन संरेखण में आवेदन पाता है। मैं हाल ही में इस समस्या के एक अलग संस्करण में आया था।

A C G T - 
A 5 -1 -2 -1 -3 
C -1 5 -3 -2 -4 
G -2 -3 5 -2 -2 
T -1 -2 -2 5 -1 
- -3 -4 -2 -1 Not Allowed 

-

को देखते हुए दो इनपुट तार (मान लेते हैं कि तार केवल के बने होते हैं ए, सी, जी, टी), समस्या मूल रूप से निम्नलिखित मैट्रिक्स के आधार पर स्कोर अधिकतम संरेखण को खोजने के लिए था इसलिए, यदि ए के साथ गठबंधन किया गया है -, हम संरेखण स्कोर में -3 ​​जोड़ते हैं या यदि जी को टी के साथ गठबंधन किया जाता है, तो हम स्कोर में -2 जोड़ते हैं या यदि सी को सी के साथ गठबंधन किया जाता है, तो हम 5. जोड़ते हैं तो इनपुट स्ट्रिंग के लिए एजीटीजीएटीजी और जीटीएजी, अधिकतम संरेखण स्कोर 14 है और अधिकतम स्कोर वाले संरेखणों में से एक को

AGTGATG 
-GTTA-G 

के रूप में प्रदर्शित किया जा सकता है

संरेखण स्कोर की गणना निम्नानुसार की जाती है: ए- = -3, जीजी = 5, टीटी = 5, जीटी = -2, एए = 5, टी- = -1 और जीजी = 5. उन्हें जोड़ना, -3+ 5 + 5-2 + 5-1 + 5 = 14 जो तारों की इस जोड़ी के लिए अधिकतम संभव संरेखण स्कोर है।

मैं गतिशील प्रोग्रामिंग का उपयोग करके इसे कोड करने में सक्षम हूं और संरेखण स्कोर मैट्रिक्स प्राप्त कर रहा हूं लेकिन मुझे अधिकतम संरेखण स्कोर के साथ दो तारों के सभी संभावित संरेखणों को मुद्रित करने में समस्याएं आ रही हैं। मैंने बैकट्रैक करने की कोशिश की क्योंकि हम एलसीएस में करते हैं लेकिन यह काम नहीं कर सका। मैं अपना कोड संलग्न कर रहा हूं।

static Dictionary<string, int> dict; 

    static void Main(string[] args) 
    { 
     //This has been assumed that the strings contain only A,C,G,T and -(?)..caps 

     Console.WriteLine("Enter first string : "); 
     string a = Console.ReadLine(); 
     a = "-" + a; 
     Console.WriteLine("Enter second string : "); 
     string b = Console.ReadLine(); 
     b = "-" + b; 
     int[,] SQ = new int[a.Length, b.Length]; 
     #region Create Dictionary 
     dict = new Dictionary<string, int>(); 
     dict.Add("AA", 5); 
     dict.Add("AC", -1); 
     dict.Add("AG", -2); 
     dict.Add("AT", -1); 
     dict.Add("A-", -3); 

     dict.Add("CA", -1); 
     dict.Add("CC", 5); 
     dict.Add("CG", -3); 
     dict.Add("CT", -2); 
     dict.Add("C-", -4); 

     dict.Add("GA", -2); 
     dict.Add("GC", -3); 
     dict.Add("GG", 5); 
     dict.Add("GT", -2); 
     dict.Add("G-", -2); 

     dict.Add("TA", -1); 
     dict.Add("TC", -2); 
     dict.Add("TG", -2); 
     dict.Add("TT", 5); 
     dict.Add("T-", -1); 

     dict.Add("-A", -3); 
     dict.Add("-C", -4); 
     dict.Add("-G", -2); 
     dict.Add("-T", -1); 
     dict.Add("--", 0); 
     #endregion Create Dictionary 

     for (int i = 0; i < a.Length; i++) 
     { 
      for (int j = 0; j < b.Length; j++) 
      { 
       int key = 0, key1 = 0, key2 = 0; 
       dict.TryGetValue(a[i].ToString() + b[j].ToString(), out key); 
       dict.TryGetValue("-" + b[j].ToString(), out key1); 
       dict.TryGetValue(a[i].ToString() + "-", out key2); 
       if (i == 0) 
        SQ[i, j] = key1; 
       else if (j == 0) 
        SQ[i, j] = key2; 
       else 
        SQ[i, j] = Math.Max(SQ[i - 1, j - 1] + key, Math.Max(SQ[i - 1, j] + key1, SQ[i, j - 1] + key2)); 
      } 
     } 
     for (int i = 0; i < a.Length; i++) 
     { 
      for (int j = 0; j < b.Length; j++) 
      { 
       Console.Write(SQ[i, j] + " "); 
      } 
      Console.WriteLine(); 
     } 

     Console.WriteLine("Alignment Score : " + SQ[a.Length - 1, b.Length - 1]);    
     printAllAlignmentsWithHighestAlignmentScore(); 
     Console.Read(); 
    } 

किसी ने मुझसे लागू करने printAllAlignmentsWithHighestAlignmentScore() फ़ंक्शन में मदद सकते हैं?

Answer 1

अंत में, मेरे पास ऐसा करने के लिए काम करने वाला कोड है जो मैं करना चाहता था। समस्या वास्तव में की एक मामूली बदलाव है Needleman–Wunsch algorithm

कोड:

class Program 
{ 
    static Dictionary<string, int> dict; 
    static void printAllAlignments(int[,] SQ, string a, string b, int p, int q, string str1, string str2){ 
     if (p == 0 || q == 0){ 
      while (p == 0 && q != 0){ 
       str1 = "-" + str1; 
       str2 = b[--q]+str2; 
      } 
      while (q == 0 && p != 0){ 
       str1 = a[--p]+str1; 
       str2 = '-' + str2; 
      } 
      Console.WriteLine("\n"+str1+"\n"+str2+"\n"); 
      return; 
     } 

     if (SQ[p, q] == (dict[a[p - 1] + b[q - 1].ToString()] + SQ[p - 1, q - 1])) 
      printAllAlignments(SQ, a, b, p - 1, q - 1, a[p-1]+str1, b[q-1]+str2); 

     if (SQ[p, q] == (dict[a[p - 1]+ "-"] + SQ[p - 1, q])) 
      printAllAlignments(SQ, a, b, p - 1, q, a[p-1]+str1, "-"+str2); 

     if (SQ[p, q] == (dict["-" + b[q-1]] + SQ[p, q - 1]))    
      printAllAlignments(SQ, a, b, p, q - 1, "-"+str1, b[q-1]+str2); 


    } 
    static void Main(string[] args) 
    { 
     //This has been assumed that the strings contain only A,C,G,T and -(?)..caps 

     Console.WriteLine("Enter first string : "); 
     string a = Console.ReadLine();   
     Console.WriteLine("Enter second string : "); 
     string b = Console.ReadLine();   
     int[,] SQ = new int[a.Length+1, b.Length+1]; 

     #region Create Dictionary 
     dict = new Dictionary<string, int>(); 
     dict.Add("AA", 5); 
     dict.Add("AC", -1); 
     dict.Add("AG", -2); 
     dict.Add("AT", -1); 
     dict.Add("A-", -3); 

     dict.Add("CA", -1); 
     dict.Add("CC", 5); 
     dict.Add("CG", -3); 
     dict.Add("CT", -2); 
     dict.Add("C-", -4); 

     dict.Add("GA", -2); 
     dict.Add("GC", -3); 
     dict.Add("GG", 5); 
     dict.Add("GT", -2); 
     dict.Add("G-", -2); 

     dict.Add("TA", -1); 
     dict.Add("TC", -2); 
     dict.Add("TG", -2); 
     dict.Add("TT", 5); 
     dict.Add("T-", -1); 

     dict.Add("-A", -3); 
     dict.Add("-C", -4); 
     dict.Add("-G", -2); 
     dict.Add("-T", -1); 
     dict.Add("--", 0); 
     #endregion Create Dictionary 

     SQ[0, 0] = 0;    
     for (int i = 1; i <= a.Length; i++)    
      SQ[i, 0] = dict["-" + a[i - 1].ToString()] + SQ[i - 1, 0]; 

     for (int i = 1; i <= b.Length; i++) 
      SQ[0, i] = dict[b[i - 1].ToString() + "-"] + SQ[0, i - 1]; 

     for (int i = 1; i <= a.Length; i++) 
      for (int j = 1; j <= b.Length; j++) 
       SQ[i, j] = Math.Max(SQ[i - 1, j - 1] + dict[a[i-1].ToString() + b[j-1]], Math.Max(SQ[i - 1, j] + dict[a[i-1] + "-"], SQ[i, j - 1] + dict["-" + b[j-1]]));   


     Console.WriteLine("Max Alignment Score : " + SQ[a.Length, b.Length]); 
     printAllAlignments(SQ, a, b, a.Length , b.Length,"",""); 
     Console.Read(); 
    } 
} 

Answer 2

दिलचस्प समस्या। आपके कोड में "गतिशील प्रोग्रामिंग" कहां है?

मुझे यकीन नहीं है कि आप सभी संभावित संरेखण छापने में क्या खोज रहे हैं लेकिन नीचे मेरा त्वरित और गंदा कोड मदद कर सकता है।

- 0 
- 

- -2 
G 

. 
. 
. 

AGTGATG 8 
-GTTTTA 

AGTGATTG 14 
-GTTTTAG 

ध्यान दें कि संरेखण संयोजन आपके द्वारा उल्लेखित उत्पादन में दिखाई नहीं देता::

AGTGATG 
-GTTA-G 

"समस्याओं से इस तुम क्या मतलब है यह दो लाइनों पर प्रत्येक संरेखण, इस तरह प्रिंट सभी संभावित संरेखण छापने में "?

वैसे भी यहां मेरे कोड (शब्दकोश प्रारंभ निकाला गया) है:

public struct Alignment 
{ 
    public string substringA; 
    public string substringB; 
    public int key; 
} 

[MTAThread] 
static void Main(string[] args) 
{ 
    //This has been assumed that the strings contain only A,C,G,T and -(?)..caps 

    Console.WriteLine("Enter first string : "); 
    var a = Console.ReadLine(); 
    a = "-" + a; 
    Console.WriteLine("Enter second string : "); 
    var b = Console.ReadLine(); 
    b = "-" + b; 
    Alignment[,] SQ = new Alignment[a.Length, b.Length]; 

    #region Create Dictionary 
    ... 
    #endregion Create Dictionary 

    for (int i = 0; i < a.Length; i++) 
    { 
     for (int j = 0; j < b.Length; j++) 
     { 
      int key = 0, key1 = 0, key2 = 0; 
      dict.TryGetValue(a[i].ToString() + b[j].ToString(), out key); 
      dict.TryGetValue("-" + b[j].ToString(), out key1); 
      dict.TryGetValue(a[i].ToString() + "-", out key2); 
      if (i == 0) 
      { 
       SQ[i, j].substringA = "-"; 
       SQ[i, j].substringB = b[j].ToString(); 
       SQ[i, j].key = key1; 
      } 
      else if (j == 0) 
      { 
       SQ[i, j].substringA = a[i].ToString(); 
       SQ[i, j].substringB = "-"; 
       SQ[i, j].key = key2; 
      } 
      else 
      { 
       // Get the maximum key value, and the substrings associated with it. 
       int score; 
       var score1 = SQ[i - 1, j].key + key1; 
       var score2 = SQ[i, j - 1].key + key2; 
       if (score1 >= score2) 
       { 
        SQ[i, j].substringA = SQ[i - 1, j].substringA; 
        SQ[i, j].substringB = SQ[i - 1, j].substringB; 
        score = score1; 
       } 
       else 
       { 
        SQ[i, j].substringA = SQ[i, j - 1].substringA; 
        SQ[i, j].substringB = SQ[i, j - 1].substringB; 
        score = score2; 
       } 

       var score3 = SQ[i - 1, j - 1].key + key; 
       if (score3 >= score) 
       { 
        SQ[i, j].substringA = SQ[i - 1, j - 1].substringA; 
        SQ[i, j].substringB = SQ[i - 1, j - 1].substringB; 
        score = score3; 
       } 
       SQ[i, j].substringA += a[i]; 
       SQ[i, j].substringB += b[j]; 
       SQ[i, j].key = score; 
      } 
     } 
    } 

    PrintAlignments(SQ, a.Length, b.Length); 

    Console.WriteLine("Alignment Score : " + SQ[a.Length - 1, b.Length - 1].key);    
    Console.Read(); 
} 

private static void PrintAlignments(Alignment[,] SQ, int iLength, int jLength) 
{ 
    for (int i = 0; i < iLength; i++) 
    { 
     for (int j = 0; j < jLength; j++) 
     { 
      Console.WriteLine("{0} {1}", SQ[i, j].substringA, SQ[i, j].key); 
      Console.WriteLine("{0}", SQ[i, j].substringB); 
      Console.WriteLine(); 
     } 
    } 
} 

Answer 3

प्रत्येक राज्य (डी पी सेल) एक्स 3 पूर्ववर्ती राज्यों है; चलो उन्हें एक्स 1, एक्स 2, एक्स 3 कहते हैं। आइए एक राज्य एक्स एस (एक्स) के स्कोर को कॉल करें, और राज्य एक्स से कुछ पड़ोसी राज्य वाई सी (एक्स, वाई) तक पहुंचने की लागत।

किसी भी राज्य एक्स के लिए

, आमतौर पर केवल अपने पूर्ववर्तियों से एक इष्टतम, जब अपने स्वयं के स्कोर के साथ साथ लागत के संदर्भ में मापा हो जाएगा एक्स जैसे इसे से प्राप्त करने के लिए यह हो सकता है कि एस (एक्स 1) + सी (एक्स 1, एक्स)> एस (एक्स 2) + सी (एक्स 2, एक्स) और एस (एक्स 1) + सी (एक्स 1, एक्स)> एस (एक्स 3) + सी (एक्स 3, एक्स): इस मामले में, एक्स 1 एक्स के 3 पूर्ववर्तियों के बीच विशिष्ट रूप से इष्टतम है, और बैकट्रैकिंग केवल X1 का पालन करने की आवश्यकता है।

लेकिन ऐसा हो सकता है कि 2 सर्वोत्तम-बराबर, या यहां तक ​​कि 3 सर्वश्रेष्ठ-बराबर पूर्ववर्ती भी हैं, और इन मामलों में, 2 या 3 इष्टतम पूर्ववर्तियों में से कोई भी (डीपी फॉर्मूलेशन की शुद्धता से) का पालन करेगा इष्टतम संरेखण।आम तौर पर आप केवल एक संरेखण उत्पन्न करने में रुचि रखते हैं, इसलिए बैकट्रैकिंग के दौरान आप मनमाने ढंग से एक इष्टतम पूर्ववर्ती चुनते हैं, और इसका पालन करते हैं। लेकिन यदि आप उन्हें सब कुछ उत्पन्न करना चाहते हैं, तो ऐसा करने के बजाय आपको सभी पूर्ववर्ती राज्यों पर लूप करने की आवश्यकता है और प्रत्येक को संसाधित करने की आवश्यकता है।

Answer 4

सिर्फ इसलिए कि समस्या वास्तव में मेरे लिए दिलचस्प थी, और मुझे समाधान के आपके दृष्टिकोण में दिलचस्पी थी, मैंने कुछ परीक्षणों के लिए जल्दी ही ब्रूटफोर्स समाधान को कोड किया। कुछ छोटी समस्याओं के लिए मैंने पाया कि हम विभिन्न समाधान उत्पन्न करते हैं। उदाहरण के लिए टीए और एटी।

TA- 
-AT 

जो 3. पर स्कोर शायद मैं नहीं आपकी समस्या को ठीक है, मैं खुशी होगी था: आपका स्कोर परिणाम 1 (मैं संरेखण उस पर आधारित करता है क्या पता नहीं है) है, जबकि मेरा है अगर आपने इसे चेक आउट किया है।

static Dictionary<string, int> dict; 

    static void Main(string[] args) 
    { 
     //This has been assumed that the strings contain only A,C,G,T and -(?)..caps 

     Console.WriteLine("Enter first string : "); 
     string realInputA = Console.ReadLine(); 
     string inputA = "-" + realInputA; 
     Console.WriteLine("Enter second string : "); 
     string realInputB = Console.ReadLine(); 
     string inputB = "-" + realInputB; 
     int[,] scoreMatrix = new int[inputA.Length, inputB.Length]; 
     #region Create Dictionary 
     dict = new Dictionary<string, int>(); 
     dict.Add("AA", 5); 
     dict.Add("AC", -1); 
     dict.Add("AG", -2); 
     dict.Add("AT", -1); 
     dict.Add("A-", -3); 

     dict.Add("CA", -1); 
     dict.Add("CC", 5); 
     dict.Add("CG", -3); 
     dict.Add("CT", -2); 
     dict.Add("C-", -4); 

     dict.Add("GA", -2); 
     dict.Add("GC", -3); 
     dict.Add("GG", 5); 
     dict.Add("GT", -2); 
     dict.Add("G-", -2); 

     dict.Add("TA", -1); 
     dict.Add("TC", -2); 
     dict.Add("TG", -2); 
     dict.Add("TT", 5); 
     dict.Add("T-", -1); 

     dict.Add("-A", -3); 
     dict.Add("-C", -4); 
     dict.Add("-G", -2); 
     dict.Add("-T", -1); 
     dict.Add("--", 0); 
     #endregion Create Dictionary 

     for (int i = 0; i < inputA.Length; i++) 
     { 
      for (int j = 0; j < inputB.Length; j++) 
      { 
       int score = 0, score1 = 0, score2 = 0; 
       dict.TryGetValue(inputA[i].ToString() + inputB[j].ToString(), out score); 
       dict.TryGetValue("-" + inputB[j].ToString(), out score1); 
       dict.TryGetValue(inputA[i].ToString() + "-", out score2); 
       if (i == 0) 
        scoreMatrix[i, j] = score1; 
       else if (j == 0) 
        scoreMatrix[i, j] = score2; 
       else 
        scoreMatrix[i, j] = Math.Max(scoreMatrix[i - 1, j - 1] + score, Math.Max(scoreMatrix[i - 1, j] + score1, scoreMatrix[i, j - 1] + score2)); 
      } 
     } 
     for (int i = 0; i < inputA.Length; i++) 
     { 
      for (int j = 0; j < inputB.Length; j++) 
      { 
       Console.Write(scoreMatrix[i, j] + " "); 
      } 
      Console.WriteLine(); 
     } 

     Console.WriteLine("Alignment Score : " + scoreMatrix[inputA.Length - 1, inputB.Length - 1]); 
     printAllAlignments(realInputA, realInputB); 
     Console.Read(); 
    } 

    static void printAllAlignments(string inputA, string inputB) 
    { 
     int minLen = Math.Max(inputA.Length, inputB.Length); 
     int maxLen = inputA.Replace("-", "").Length + inputB.Replace("-", "").Length; 

     Dictionary<string, int> solutions = new Dictionary<string, int>(); 

     solutions = prepareStartSequences(inputA, inputB, minLen, solutions); 

     addLongerSequences(inputA, minLen, maxLen, solutions); 

     var solutionsOrdered = solutions.OrderByDescending(x => x.Value); 
     int maxScore = solutionsOrdered.First().Value; 

     foreach (var sol in solutionsOrdered.Where(x => x.Value == maxScore)) 
     { 
      Console.WriteLine("{0}\n{1}\tScore: {2}\n\n", sol.Key.Split('|')[0], sol.Key.Split('|')[1], sol.Value); 
     } 
    } 

    private static void addLongerSequences(string inputA, int minLen, int maxLen, Dictionary<string, int> solutions) 
    { 
     for (int l = minLen + 1; l <= maxLen; l++) 
     { 
      List<Tuple<string, string>> currCombs = solutions 
       .Where(x => x.Key.Length/2 + 1 == l) 
       .Select(x => x.Key.Split('|')) 
       .Select(x => new Tuple<string, string>(x[0], x[1])) 
       .ToList(); 
      foreach (var comb in currCombs) 
      { 
       for (int idxA = 0; idxA <= inputA.Length; idxA++) 
       { 
        for (int idxB = 0; idxB <= inputA.Length; idxB++) 
        { 
         string cA = comb.Item1.Insert(idxA, "-"); 
         string cB = comb.Item2.Insert(idxB, "-"); 
         int score = getScore(cA, cB); 
         string key = cA + "|" + cB; 
         if (!solutions.ContainsKey(key) && score > int.MinValue) 
         { 
          solutions.Add(key, score); 
         } 
        } 
       } 
      } 
     } 
    } 

    private static Dictionary<string, int> prepareStartSequences(string inputA, string inputB, int minLen, Dictionary<string, int> solutions) 
    { 
     if (inputA.Length == inputB.Length) 
      solutions.Add(inputA + "|" + inputB, getScore(inputA, inputB)); 
     else 
     { 
      string shorter = inputA.Length > inputB.Length ? inputB : inputA; 
      string longer = inputA.Length > inputB.Length ? inputA : inputB; 
      int shortLen = shorter.Length; 
      List<string> combinations = new List<string>(); 
      combinations.Add(shorter); 

      while (shortLen < minLen) 
      { 
       List<string> tmpCombinations = new List<string>(); 
       foreach (string str in combinations) 
       { 
        for (int i = 0; i <= shortLen; i++) 
        { 
         tmpCombinations.Add(str.Insert(i, "-")); 
        } 
       } 
       combinations = tmpCombinations.Distinct().ToList(); 
       shortLen++; 
      } 

      foreach (var comb in combinations) 
      { 
       if (inputA.Length > inputB.Length) 
       { 
        solutions.Add(longer + "|" + comb, getScore(longer, comb)); 
       } 
       else 
       { 
        solutions.Add(comb + "|" + longer, getScore(comb, longer)); 
       } 
      } 
     } 

     solutions = solutions.Where(x => x.Value != int.MinValue).ToDictionary(x => x.Key, y => y.Value); 
     return solutions; 
    } 

    static int getScore(string inputA, string inputB) 
    { 
     int result = 0; 
     for (int i = 0; i < inputA.Length; i++) 
     { 
      string key = inputA[i].ToString() + inputB[i].ToString(); 
      if (key == "--") return int.MinValue; 
      result += dict.ContainsKey(key) ? dict[key] : 0; 
     } 
     return result; 
    }