DNAMatching.cpp

//Hackerrank code challenge

//DNA alignment and scoring

#include<iostream>

using namespace std;


int m[5][5] = {
                    {5,-1,-2,-1,-3},
                    {-1,5,-3,-2,-4},
                    {-2,-3,5,-2,-2},
                    {-1,-2,-2,5,-1},
                    {-3,-4,-2,-1,0}
              };

int getIndex(char ch)
{
   if(ch == 'A')
   {
        return 0;
   }
   
   if(ch == 'C')
   {
        return 1;
   }

   if(ch == 'G')
   {
        return 2;
   }

   if(ch == 'T')
   {
        return 3;
   }

   return 4;
}

int Max(int i, int j)
{
   return i > j ? i : j;
}

int Max_3(int i , int j, int k)
{
   int m = Max(i,j);
   return Max(m,k);
}


int ScoreDNA(const char* str1,const char* str2,char* r1,char* r2, int index,int &mLen)
{
   
    if(*str1 == '\0' && *str2 == '\0')
    {
        r1[index] = '\0';
        r2[index] = '\0';
        return 0;
    }

    if(*str1 == '\0')
    {
          int score = 0;
          while(*str2 != '\0')
          {
             r1[index] = '-';
             r2[index] = *str2;
             index++;
             score = score + m[4][getIndex(*str2)];
             str2++;
          }
          
          r1[index] = '\0';
          r2[index] = '\0';
          return score;
    }

    if(*str2 == '\0')
    {
          int score = 0;
          while(*str1 != '\0')
          {
             r1[index] = *str1;
             r2[index] = '-';
             index++;
             score = score + m[getIndex(*str1)][4];
             str1++;
          }
          r1[index] = '\0';
          r2[index] = '\0';

          return score;
    }

    if(*str1 == *str2)
    {
        int i1 = getIndex(*str1);
        int i2 = getIndex(*str2);
       
        int x = m[i1][i2] + ScoreDNA(str1+1,str2+1,r1,r2,index+1,mLen);

        if(x > mLen)
        {
            r1[index] = *str1;
            r2[index] = *str2;
            mLen = x;
        }
        return x;
    }
    else
    {
       int i1 = getIndex(*str1);
       int i2 = getIndex(*str2);

       //put - in second and use char from 1
       int s1 = m[i1][4] + ScoreDNA(str1+1,str2,r1,r2,index+1,mLen);

       //put - in first and use char from 2

       int s2 = m[4][i2] +  ScoreDNA(str1,str2+1,r1,r2,index+1,mLen);

       int s3 = m[i1][i2] + ScoreDNA(str1+1,str2+1,r1,r2,index+1,mLen);

       int max = Max_3(s1,s2,s3);

       if(max < mLen)
       {
           return max;
       }

       mLen = max;

       if(max == s1)
       {
           r1[index] = *str1; 
           r2[index] = '-';
       }
       else if(max == s2)
       {
           r1[index] = '-'; 
           r2[index] = *str2;
       }
       else
       {
           r1[index] = *str1; 
           r2[index] = *str2;
       }

       return max;
       
    }
}


int DNAMatch(const char* str1, const char* str2)
{

   int s1 = strlen(str1);
   int s2 = strlen(str2);

   int **p = new int*[s1+1];

   for(int i = 0; i < (s1+1); i++)
   {
       p[i] = new int[s2+1];
   }

   p[0][0] = 0;

   for(int i = 1; i <= s1; i++)
   {
       p[i][0] = p[i-1][0] + m[getIndex(str1[i-1])][4];
   }

   for(int i = 1; i <= s2; i++)
   {
       p[0][i] = p[0][i-1] + m[4][getIndex(str2[i-1])];
   }
 
   int mLen = 0;

   for(int i = 1; i <= s1; i++)
   {
      for(int j = 1; j <= s2; j++)
      {

          int i1 = getIndex(str1[i-1]);
          int i2 = getIndex(str2[j-1]);

          if(str1[i-1] == str2[j-1])
          {
              p[i][j] = p[i-1][j-1] + m[i1][i2];
              
          }
          else
          {
              //inset - in first and use char from second
              //insert - in second and use char from first
              //use diff char only
 
             int sum1 = p[i-1][j-1] + m[i1][i2];
             int sum2 = p[i-1][j] + m[4][i2];
             int sum3 = p[i][j-1] + m[i1][4];

             p[i][j] = Max_3(sum1,sum2,sum3);
          }
      }
   }
   
   return p[s1][s2];
}

int main()
{
    const char* str1 = "AGTGATG";
    const char* str2 = "GTTAG";

    int s1 = strlen(str1);
    int s2 = strlen(str2);

    char* r1 = new char[s1+s2+1];
    char* r2 = new char[s1+s2+1];
   
    int mLen = 0;

    cout<<"Using Recursion-"<<ScoreDNA(str1,str2,r1,r2,0,mLen)<<endl;
  
    cout<<r1<<endl;
    cout<<r2<<endl;

    cout<<"Using DP-"<<DNAMatch(str1,str2)<<endl;

    
    return 0;

}