The Gapped Alignment Problem, Longest Increasing Subsequence

The Gapped Alignment Problem

 

두개의 문자열이 주어졌을 때, score을 최대화하는 gapped alignment를 구하여라.

match라면 1점, mismatch라면 -1점, gap이라면 -2점을 준다.

 

두개의 문자열이 주어졌을 때, Gapped Alignment가 생성되는 방법의 수는 3가지로 나오게 된다.(문자열 A,B가 있다고 가정)

 

1. 두 문자를 match하는 경우( 문자가 다를 수도 있음)

2. A의 문자열에 gap을 넣는 경우

3. B의 문자열에 gap을 넣는 경우

위를 식으로 표현하면 다음과 같다.

#include <iostream>
#include <string>

using namespace std;
 
// function to find out the minimum penalty
void getMinimumPenalty(string x, string y, int pxy, int pgap)
{
    int i, j; // initialising variables
     
    int m = x.length();
    int n = y.length();
     
    // table for storing optimal substructure answers
    int dp[256][256]={0};
 
    // initialising the table
    for (i = 0; i <= (n+m); i++)
    {
        dp[i][0] = i * pgap;
        dp[0][i] = i * pgap;
    }
    int cnt=0;
    // calculating the minimum penalty
    for (i = 1; i <= m; i++)
    {
        for (j = 1; j <= n; j++)
        {
            if (x[i - 1] == y[j - 1])
            {
                dp[i][j] = dp[i - 1][j - 1];
            }
            else
            {
                dp[i][j] = min(dp[i - 1][j - 1] + pxy ,min(dp[i - 1][j] + pgap, dp[i][j - 1] + pgap));
            }
        }
    }
 
    // Reconstructing the solution
    int l = n + m; // maximum possible length
     
    i = m; j = n;
     
    int xpos = l;
    int ypos = l;
 
    // Final answers for the respective strings
    int xans[l+1], yans[l+1];
     
    while ( !(i == 0 || j == 0))
    {
        if (x[i - 1] == y[j - 1])
        {
            xans[xpos--] = (int)x[i - 1];
            yans[ypos--] = (int)y[j - 1];
            cnt++;
            i--; j--;
        }
        else if (dp[i - 1][j - 1] + pxy == dp[i][j])
        {
            xans[xpos--] = (int)x[i - 1];
            yans[ypos--] = (int)y[j - 1];
            i--; j--;
        }
        else if (dp[i - 1][j] + pgap == dp[i][j])
        {
            xans[xpos--] = (int)x[i - 1];
            yans[ypos--] = (int)'_';
            i--;
        }
        else if (dp[i][j - 1] + pgap == dp[i][j])
        {
            xans[xpos--] = (int)'_';
            yans[ypos--] = (int)y[j - 1];
            j--;
        }
    }
    while (xpos > 0)
    {
        if (i > 0) xans[xpos--] = (int)x[--i];
        else xans[xpos--] = (int)'_';
    }
    while (ypos > 0)
    {
        if (j > 0) yans[ypos--] = (int)y[--j];
        else yans[ypos--] = (int)'_';
    }
 
    // Since we have assumed the answer to be n+m long,
    // we need to remove the extra gaps in the starting
    // id represents the index from which the arrays
    // xans, yans are useful
    int id = 1;
    for (i = l; i >= 1; i--)
    {
        if ((char)yans[i] == '_' && (char)xans[i] == '_')
        {
            id = i + 1;
            break;
        }
    }
 
    // Printing the final answer
    cout << "Maximum score in aligning the genes = ";
    cout << cnt*2-dp[m][n] << "\n";
    cout << "The aligned genes are :\n";
    for (i = id; i <= l; i++)
    {
        cout<<(char)xans[i];
    }
    cout << "\n";
    for (i = id; i <= l; i++)
    {
        cout << (char)yans[i];
    }
    return;
}
 
// Driver code
int main(int argc, char* argv[]){
    // input strings
    string gene1 = argv[1];
    string gene2 = argv[2];
     
    // initialising penalties of different types
    int misMatchPenalty = 1;
    int gapPenalty = 2;
 
    // calling the function to calculate the result
    getMinimumPenalty(gene1, gene2,
        misMatchPenalty, gapPenalty);
    return 0;
}

---

Longest Increasing Subsequence (LIS)

문자열이 주어졌을 때, 가장 긴 문자열을 구해야 한다.

예를 들어,

(10,22,9,33,21,50,41,60,80) -> (10,22,33,50,60,80) 이 된다.

a[j]<a[i]인 경우 중 가장 큰 d[j]값을 찾아서 1을 더해주면 LIS의 크기를 구할 수 있다.

#include <stdio.h>
#include <stdlib.h>

int LIS( int* a, int N ) {
    int *best, *prev, i, j, max = 0;
    best = (int*) malloc ( sizeof( int ) * N );
    prev = (int*) malloc ( sizeof( int ) * N );
    for ( i = 0; i < N; i++ ) best[i] = 1, prev[i] = i;
    
    for ( i = 1; i < N; i++ )
        for ( j = 0; j < i; j++ )
            if ( a[i] > a[j] && best[i] < best[j] + 1 )
                best[i] = best[j] + 1, prev[i] = j;
    
    for ( i = 0; i < N; i++ )
        if ( max < best[i] ) max = best[i];
    
    // Print the LIS using prev[] here. free( best ); free( prev );
    return max;
}

int main(){
    int a[] = {10,22,9,33,21,50,41,60,80};
    for(int i=0;i<sizeof(a)/sizeof(int);i++) printf("%d ",a[i]);
    putchar('\n');
    printf("%d",LIS(a,sizeof(a)/sizeof(int)));
}