정답
① X[i] == Y[j], ② -1.0 또한 \(X[1..4]=\text{ACGG}\), \(Y[1..4]=\text{CGCG}\) 일 때 \( \displaystyle sim(4,4) = 1.8 \) 이며, 정렬에 사용된 연산은 순서대로 “삭제, 일치, 일치, 삽입, 일치” 이다.
출제 의도
두 문자열(염기 서열)의 유사도를 동적 계획법으로 계산하는 알고리즘을 이해하고, 일치·불일치·삽입·삭제에 대한 점수 체계를 코드에 반영할 수 있는지를 평가한다. 또한 주어진 점수 체계를 이용하여 실제 두 서열의 유사도 값을 구하고, 그에 대응하는 정렬 연산의 순서를 추적하는 능력을 본다.
풀이 과정
설명 (나)에 따르면 두 염기 \(X[i]\)와 \(Y[j]\)가 일치하면 \(\delta = 1\), 불일치하면 \(\delta = -1\) 이다.
의사코드 (가)에서
$$ \text{if } (\text{①}) \text{ then } \delta = 1.0 $$
가 되어야 하므로 조건 ①에는 두 문자가 같은지 비교하는 코드가 들어가야 한다.
따라서 ①은 X[i] == Y[j] 이다.
불일치일 때는 \(\delta = -1\) 이므로, else 부분에서
$$ \delta = \text{②} = -1.0 $$
이 되어야 한다.
유사도 점수는 다음 점화식으로 계산된다.
$$ \begin{aligned} sim(i,0) &= -0.6 i, \\ sim(0,j) &= -0.6 j, \\ sim(i,j) &= \max\big( sim(i-1,j) – 0.6,\; sim(i,j-1) – 0.6,\; sim(i-1,j-1) + \delta \big) \end{aligned} $$
여기서 삽입과 삭제의 점수는 \(-0.6\)이고, 일치·불일치 점수는 각각 \(+1\), \(-1\) 이다.
이미 제시된 표는 \(X[1..3]=\text{ACG}\), \(Y[1..4]=\text{CGCG}\) 에 대한 \(sim(i,j)\) 값이다. 이 표의 마지막 행(i=3)을 사용하여 \(X[1..4]=\text{ACGG}\) 에 대한 i=4 행을 이어서 계산한다. 새로 추가된 문자는 \(X[4]=\text{G}\) 이다.
경계 조건은
$$ sim(4,0) = -0.6 \times 4 = -2.4 $$
이다. 이제 \(j=1\)부터 \(4\)까지 차례로 계산한다.
\(j=1\)에서 \(Y[1]=\text{C}\), 불일치이므로 \(\delta=-1\) 이다.
$$ \begin{aligned} sim(4,1) &= \max\big( sim(3,1)-0.6,\; sim(4,0)-0.6,\; sim(3,0)+\delta \big) \\ &= \max(-0.2-0.6,\; -2.4-0.6,\; -1.8-1) \\ &= \max(-0.8,\; -3.0,\; -2.8) = -0.8 \end{aligned} $$
\(j=2\)에서 \(Y[2]=\text{G}\), \(X[4]=\text{G}\) 이므로 일치, \(\delta=1\) 이다.
$$ \begin{aligned} sim(4,2) &= \max\big( sim(3,2)-0.6,\; sim(4,1)-0.6,\; sim(3,1)+1 \big) \\ &= \max(1.4-0.6,\; -0.8-0.6,\; -0.2+1) \\ &= \max(0.8,\; -1.4,\; 0.8) = 0.8 \end{aligned} $$
\(j=3\)에서 \(Y[3]=\text{C}\), 불일치 \(\delta=-1\) 이다.
$$ \begin{aligned} sim(4,3) &= \max\big( sim(3,3)-0.6,\; sim(4,2)-0.6,\; sim(3,2)-1 \big) \\ &= \max(0.8-0.6,\; 0.8-0.6,\; 1.4-1) \\ &= \max(0.2,\; 0.2,\; 0.4) = 0.4 \end{aligned} $$
\(j=4\)에서 \(Y[4]=\text{G}\), 일치 \(\delta=1\) 이다.
$$ \begin{aligned} sim(4,4) &= \max\big( sim(3,4)-0.6,\; sim(4,3)-0.6,\; sim(3,3)+1 \big) \\ &= \max(0.4-0.6,\; 0.4-0.6,\; 0.8+1) \\ &= \max(-0.2,\; -0.2,\; 1.8) = 1.8 \end{aligned} $$
따라서 유사도는
$$ sim(4,4) = 1.8 $$
이다.
이제 \(sim(4,4)\) 값이 어떻게 만들어졌는지 거꾸로 추적하여 정렬에 사용된 연산을 찾는다.
\(sim(4,4)=1.8\) 은 대각선 값 \(sim(3,3)+1\) 에서 왔으므로, \((X[4]=G, Y[4]=G)\)는 일치 연산이다.
\(sim(3,3)=0.8\) 은 왼쪽 값 \(sim(3,2)-0.6\) 과 같으므로, \((X[3], Y[3])\) 위치에는 Y 쪽 염기만 정렬되고 X 쪽에는 공백이 들어가며, 이는 삽입 연산이다.
\(sim(3,2)=1.4\) 는 대각선 \(sim(2,1)+1\) 에서 왔으므로 \((X[3]=G, Y[2]=G)\) 는 일치 연산, \(sim(2,1)=0.4\) 도 대각선 \(sim(1,0)+1\)에서 왔으므로 \((X[2]=C, Y[1]=C)\) 역시 일치 연산이다.
마지막으로 \(sim(1,0)=-0.6\) 은 \(sim(0,0)-0.6\)에서 왔으므로, \((X[1]=A, \text{공백})\) 에 해당하는 삭제 연산이 한 번 발생한 것이다.
이를 앞에서부터 나열하면 정렬은
\(X\) : A C G – G \\ \(Y\) : – C G C G
이고, 사용된 연산의 순서는
삭제, 일치, 일치, 삽입, 일치
가 된다. 각 연산의 점수 합은
$$ -0.6 + 1 + 1 – 0.6 + 1 = 1.8 $$
으로, 앞에서 구한 \(sim(4,4)\)와 일치함을 확인할 수 있다.
<풀이가 부정확할 수 있으니 반드시 교차검증 확인 바랍니다.>