니들먼-분쉬 서열 정렬 계산기
두 서열(DNA·단백질·문자열)을 일치·불일치·빈칸 점수로 동적계획법 표를 채워 전역 정렬합니다. 삽입·삭제·치환이 섞인 최적 정렬과 점수를 보여줍니다.
최적 정렬 점수
0
서열 A 7글자 · 서열 B 7글자
정렬 결과
동적계획법 표
| G | C | A | T | G | C | U | ||
|---|---|---|---|---|---|---|---|---|
| 0 | -1 | -2 | -3 | -4 | -5 | -6 | -7 | |
| G | -1 | 1 | 0 | -1 | -2 | -3 | -4 | -5 |
| A | -2 | 0 | 0 | 1 | 0 | -1 | -2 | -3 |
| T | -3 | -1 | -1 | 0 | 2 | 1 | 0 | -1 |
| T | -4 | -2 | -2 | -1 | 1 | 1 | 0 | -1 |
| A | -5 | -3 | -3 | -1 | 0 | 0 | 0 | -1 |
| C | -6 | -4 | -2 | -2 | -1 | -1 | 1 | 0 |
| A | -7 | -5 | -3 | -1 | -2 | -2 | 0 | 0 |
계산 방법
- 1두 서열을 입력합니다(DNA·단백질·아무 문자열이나 됩니다).
- 2일치·불일치·빈칸(gap) 점수를 정합니다.
- 3동적계획법 표와 최적 정렬 점수를 확인합니다.
- 4빈칸(-)이 섞인 최적 정렬 결과를 확인합니다.
자주 묻는 질문
두 서열을 처음부터 끝까지 다 맞추면서, 일치·불일치·빈칸(삽입/삭제)에 점수를 매겨 총점이 가장 높은 정렬을 동적계획법으로 찾는 알고리즘입니다. DNA·단백질 서열 비교의 표준 알고리즘 중 하나입니다.
레벤슈타인 편집거리는 삽입·삭제·치환을 모두 1로 세는 편집 횟수만 계산하고, LCS는 공통 부분수열의 길이만 잽니다. 이 도구는 일치·불일치·빈칸에 서로 다른 점수를 매길 수 있어(생물정보학의 BLOSUM 치환행렬처럼) 더 일반화된 정렬입니다.
F(i,j) = max(F(i-1,j-1)+s(a_i,b_j), F(i-1,j)+빈칸점수, F(i,j-1)+빈칸점수)입니다. 대각선은 두 글자를 맞추는 것(일치·치환), 위·왼쪽은 한쪽에 빈칸을 넣는 것(삭제·삽입)입니다. 표의 오른쪽 아래 끝이 최적 정렬 점수이고, 거기서부터 거꾸로 따라가면 실제 정렬이 복원됩니다.
네. 이 도구가 다루는 니들먼-분쉬는 두 서열을 처음부터 끝까지 다 맞추는 «전역 정렬»입니다. 서열의 일부분만 가장 잘 맞는 구간을 찾는 «지역 정렬»은 스미스-워터맨이라는 다른 알고리즘을 씁니다.
네. 세 방향의 점수가 같으면 이 계산기는 대각선을 가장 먼저, 그다음 위, 그다음 왼쪽 순으로 고릅니다. 최고 점수는 유일해도 그 점수를 내는 정렬 자체는 여러 개일 수 있으며, 이 계산기는 그중 하나를 결정적으로 보여줍니다.
알아두면 좋은 점
- 서열은 60글자까지 다룹니다.
- 이 계산기는 빈칸 하나당 같은 점수(선형 빈칸 페널티)를 매깁니다. 빈칸을 여는 것과 늘리는 것에 다른 점수를 매기는 어파인(affine) 빈칸 페널티는 다루지 않습니다.
- 대소문자를 구분해 비교합니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 3일 · 결과는 참고용 추정치입니다.