[2612] python : DNA 유사도

 

https://www.acmicpc.net/problem/2612

2612번: DNA 유사도

 

 

 

문제

모든 생물의 DNA 서열은 A, C, G, T 네 개의 문자로 표현된다.

두 DNA 서열이 얼마나 비슷한가를 알아내기 위하여 유사도를 측정한다. 두DNA 서열의 유사도를 측정하기 위해서 먼저 각 서열의 임의의 위치에 공백을 넣어 길이를 같게 만든다.

이렇게 길이가 같아진 두 서열 간의 점수는 다음과 같이 계산된다.

1. 같은 위치에 공백이 아닌 같은 문자가 있으면 3을 더한다. 
2. 같은 위치에 서로 다른 문자가 있거나 둘 중 하나의 위치에 공백이 있으면 2를 뺀다.

두 DNA 서열의 유사도는 각 DNA 서열의 임의의 위치에 공백을 넣어 위의 방법대로 얻을 수 있는 최대 점수이다. 예를 들어 AGTCAG와 ATGTG라는 두 DNA서열의 경우 , <그림 1>과 같이 공백을 넣으면 점수가 3이 되고, <그림 2>와 같이 공백을 넣으면 점수는 6이 된다.

A G T C A G
|   |     |
A   T G T G

<그림 1>

A   G T C A G
|   | |     |
A T G T     G

<그림 2>

AGTCAG와 ATGTG의 경우 임의의 위치에 공백을 넣어 얻을 수 있는 최대 점수는 6이므로 AGTCAG와 ATGTG의 유사도는 6이 된다.

DNA 서열의 부분 서열은 DNA 서열 중 연속한 일부분을 추출하여 얻을 수 있는 서열을 말한다.예를 들어 AGTCAG라는 서열에서 첫 번째 문자부터 세 번째 문자까지를 추출하면 AGT라는 부분 서열을 얻을 수 있고,두 번째 문자부터 다섯 번째 문자까지 추출하면 GTCA라는 부분 서열을 얻을 수 있다.

두 DNA 서열에서 같은 정보를 담고 있는 부분을 찾아내는 방법 중에 하나는 두 DNA의 부분 서열 쌍 중 유사도가 가장 큰것을 찾아내는 것이다.

예를 들어 두 DNA 서열 AGTCAG 와 ATGTG의 경우 AGTCAG에서 부분 서열 AGT를 얻고, ATGTG에서 부분 서열 ATGT를 얻으면 이 둘의 유사도는 아래와 같이 7이 된다.

A   G T
|   | |
A T G T

두 DNA 서열을 입력받아 이들 DNA의 부분 서열 쌍 중 유사도가 가장 큰것을 찾아 그 유사도와 부분 서열 쌍을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 첫 번째 DNA의 서열의 길이가 추어지고 둘째 줄에는 첫 번째 DNA서열이 주어진다. 셋째 줄에는 두 번째 DNA의 서열의 길이가 주어지고 넷째 줄에는 두 번째 DNA 서열이 주어진다. DNA 서열의 길이는 1000이하이며, DNA 서열을 나타내는 문자들 사이에는 공백이 없다. 첫 번째 DNA와 두 번째 DNA는 적어도 하나 이상 공통 문자를 갖는다.

출력

첫째 줄에는 두 DNA 서열의 부분 서열 쌍 중 유사도가 가장 큰 것의 유사도를 출력한다. 둘째 줄과 셋째 줄에는 유사도가 가장 큰 부분 서열의 쌍을 출력하는데, 둘째 줄에는 첫 번째 DNA 서열에서 추출한 부분 서열을 출력하고, 셋째 줄에는 두 번째 DNA 서열에서 추출한 부분 서열을 출력한다. 만약 두 DNA 서열의 부분 서열 쌍 중 유사도가 가장 큰 쌍이 둘 이상일 경우 하나만 출력하면 된다.

예제 입력 1 

6
AGTCAG
5
ATGTG

예제 출력 1

7
AGT
ATGT

 

문제 설명

local alignment를 사용하면 되는 문제이다. 이에 대한 개념 설명은 아래 글을 참고하길 바란다.

2023.05.22 - [Computer Science/Data structure & Algorithm] - [algorithm] Smith-waterman algorithm

[algorithm] Smith-waterman algorithm

 

Smith-Waterman algorithm을 이용하여 구현한 코드는 아래와 같다. 

import sys
sys.setrecursionlimit(10**6)

LEFT = 1
UP = 2
CROSS = 3

MISMATCH = -2 #gap, mismatch
MATCH = 3 #match

def issame(a, b):
    if a == b:
        return MATCH
    else:
        return MISMATCH    

def maxupdate(new, ni, nj, max, maxi, maxj):
    if new >= max:
        return new, ni, nj
    return max, maxi, maxj

def main():
    x_len = int(input())
    x = input()
    y_len = int(input())
    y = input()
 
    maxi = 0
    maxj = 0
    maxval = 0


    c = [[ [0,0] for _ in range(y_len+1) ] for _ in range(x_len+1)]
    #init

    #needleman-Wunsch algorithm
    for i in range(1, x_len+1):
        for j in range(1, y_len+1):
            xi = x[i-1]
            yj = y[j-1]
            cr = issame(xi, yj) + c[i-1][j-1][0]            
            left = MISMATCH + c[i][j-1][0]
            up = MISMATCH + c[i-1][j][0]

            if cr < 0 and left < 0 and up < 0:
                c[i][j][0] = 0
                c[i][j][1] = 0
            elif cr >= left and cr >= up:
                c[i][j][0] = cr
                c[i][j][1] = CROSS
                maxval, maxi, maxj = maxupdate(cr, i, j, maxval, maxi, maxj)
            elif left > up and left > cr:
                c[i][j][0] = left
                c[i][j][1] = LEFT
                maxval, maxi, maxj = maxupdate(left, i, j, maxval, maxi, maxj)
            else:
                c[i][j][0] = up
                c[i][j][1] = UP
                maxval, maxi, maxj = maxupdate(up, i, j, maxval, maxi, maxj)
            
    print(maxval)
    resultx = []
    resulty = []
    while(1):
        arrow = c[maxi][maxj][1]
        if arrow == 0:
            break
        if arrow == CROSS:
            resultx.append(x[maxi-1])
            resulty.append(y[maxj-1])
            maxi -= 1
            maxj -= 1
        elif arrow == LEFT:
            resulty.append(y[maxj-1])
            maxj -= 1
        else:
            resultx.append(x[maxi-1])
            maxi -= 1    

    resultx.reverse()
    resulty.reverse()
    for t in resultx:
        print(t, end='')
    print()
    for t in resulty:
        print(t, end='')
    print()


main()