c# - 打印具有最高分数的两个序列的所有比对

Question

Sequence Alignment是一个相当标准的问题，并在生物信息学领域的 DNA 或蛋白质比对中得到应用。我最近遇到了这个问题的不同版本。

给定两个输入字符串(假设字符串仅由 A、C、G、T 组成)，问题基本上是根据以下矩阵找到最大对齐分数 --

   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

因此，如果 A 与 - 对齐，我们将 -3 添加到对齐分数，或者如果 G 与 T 对齐，我们将 -2 添加到分数，或者如果 C 与 C 对齐，我们添加 5。 因此，对于输入字符串 AGTGATG 和 GTTAG，最大对齐分数为 14，其中一个具有最大分数的对齐可以表示为

AGTGATG
-GTTA-G

对齐分数计算如下:A- = -3, GG = 5, TT = 5, GT= -2, AA = 5, T-= -1 和 GG = 5。将它们相加，-3 +5+5-2+5-1+5 = 14，这是这对字符串的最大可能对齐分数。

我能够使用动态编程对其进行编码并获得对齐分数矩阵，但我在打印具有最大对齐分数的两个字符串的所有可能对齐时遇到问题。我试着像在 LCS 中那样回溯，但没能成功。我附上了我的代码。

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();
    }
}