[컴퓨팅사고력] 염기서열의 공통 부분 서열을 찾아 보자.

원당이는 생명공학의 DNA 에 대해 연구 하고 있습니다.

DNA의 염기서열은 adenine(A),thymine(T),guanine(G),cytosine(C) 와 같이 네가지로 구성되어 있습니다.

고릴라의 염기서열을 분석해 보니 GATACCAGATACCCA 와 같이 이루어져 있고 원숭이의 염기서열을 분석해 보니 AAGATTGCCATTATT 와 같이 이루어져 있는 것을 발견했습니다.

원당이는 이 두개의 염기서열에서 공통부분 서열 중에 최대로 긴 부분 서열을 구하고 싶습니다.

여기서 부분서열이란 원래 문자열에서 임의적으로 몇개의 문자를 제거하여 순서에 맞춰 빈칸 없이 합쳤을 때 만들 수 있는 문자열을 말합니다. 즉 ATGC 와 ATCT 의 가장긴 부분수열은 ATC 3개 입니다. ATGC 에서 G를 제거 하고 ATC를 만들 수 있고 ATCT에서 마지막 T를 제거하여 ATC를 만들면 두개의 서열이 같아짐을 의미합니다.

 

원당이는 고릴라와 원숭이의 염기서열중 최대 공통부분 서열을 구하였지만 제대로 맞는지는 확신할 수가 없습니다.

여러분이 GATACCAGATACCCA 와 AAGATTGCCATTATT 의 최장 공통 부분 서열의 정답을 알려 주세요.

 

문제풀이

순서대로 첫번째 문자열과 두번째 문자열에서 부분 문자를 삭제해서 GATCCAAT 또는 GATCCATA 를 만들 수 있습니다. 따라서 최대 길이는 8글자 입니다.

 

 

 

컴퓨팅 사고력

이 문제는 컴퓨팅과학에서는 동적알고리즘(Dynamic Algorithm) 중에서 최장공통부분수열(LCS) 알고리즘을 이용하는 문제입니다.

LCS 알고리즘의 원리는 다음과 같습니다.

위의 문자열의 문자와 아래 문자열의 문자가 서로 같아진다면 바로 전까지 계산한 값보다 하나 더 많아지는 원리를 이용합니다.

위의 문제를 예로 들면 

아무것도 없을때 초기값으로 0으로 만들어 놓고 GA 의 위치와 A에서를 생각하면 앞의 문자열 G의 위치와 뒤의 문자열 아무것도 없었을때의 같은 값 0 보다 +1 을 한 값이 되는 것입니다.

같지 않은 경우는 그 전에 계산한 값중에서 가장 큰 값을 가져 오면 됩니다.

위에서 첫번째 문자열 GA 와 두번째 문자열 AAG 를 만났을때 A와 G는 서로 다른 문자이므로 G 와 AA를 만난 횟수 0, G와 AAG를 만난 횟수 1, GA와 AA를 만난 횟수 1 중에서 가장 큰 값 1을 선택해 주면 서로 같은 문자 서열은 G 또는 A 1이 됩니다.

이렇게 이전에 구한 값을 이용하여 최장 공통 부분서열을 구할 수 있게 됩니다.

이렇게 구하면 최대로 8글자 GATCCAAT 또는 GATCCATA 인경우 최대로 긴 공통 부분 수열이 됩니다.