스미스-워터맨 지역 서열 정렬 계산기

두 서열 전체를 맞추는 게 아니라, 그 안에서 가장 잘 맞는 부분 구간만 찾아 정렬하는 «지역 정렬» 알고리즘입니다. 한 서열이 다른 서열의 일부분(또는 그 반대)만 닮았을 때, 니들먼-분쉬(전역 정렬)로는 억지로 전체를 맞추려다 점수가 낮아지는데 이 알고리즘은 그 문제가 없습니다.

점화식은 거의 같고 딱 두 가지가 다릅니다. ① 점수가 음수로 내려가면 0으로 자릅니다(여기서부터 정렬을 새로 시작하는 게 낫다는 뜻). ② 표의 오른쪽 아래 끝이 아니라 표 전체에서 가장 점수가 높은 칸에서 거꾸로 되짚기 시작하고, 점수가 0이 되면 멈춥니다. 두 서열이 완전히 일치하면 자를 음수 구간 자체가 없어 두 알고리즘의 점수가 같아집니다.

자르지 않으면 두 서열 사이에 안 맞는 부분이 끼어 있을 때 점수가 계속 음수로 깎여 내려가, 정작 뒤쪽의 잘 맞는 구간까지 낮은 점수에 묻혀 버립니다. 0으로 잘라두면 안 맞는 구간을 지나 어디서든 정렬을 새로 시작할 수 있어, 서열 전체가 아니라 부분만 닮은 경우를 찾아낼 수 있습니다.

표를 읽는 순서(위에서 아래로, 왼쪽에서 오른쪽으로)로 가장 먼저 나오는 칸을 고릅니다. 되짚기 과정에서 방향이 여러 개로 갈릴 때도 대각선을 가장 먼저, 그다음 위, 그다음 왼쪽 순으로 골라 같은 입력에는 항상 같은 정렬이 나오게 합니다.

표의 모든 칸이 0이 되어 점수 0, 빈 정렬로 나옵니다. 두 서열에 공통된 부분이 전혀 없거나(불일치·빈칸 점수가 너무 가혹한) 경우입니다.