니들맨 –운슈 알고리즘

	그림 1: Needleman-Wunsch 쌍방향 시퀀스 정렬
학급	순서 정렬
최악의 경우 성능
최악의 경우 공간 복잡도

니들맨-운슈 알고리즘은 단백질이나 뉴클레오티드 서열을 정렬하기 위해 생물정보학에서 사용되는 알고리즘입니다. 생물학적 서열을 비교하는 동적 프로그래밍의 첫 번째 응용 프로그램 중 하나였습니다. 이 알고리즘은 Saul B에 의해 개발되었습니다. 니들맨과 크리스찬 D. 운슈는 1970년에 출판되었습니다.^[1] 알고리즘은 기본적으로 큰 문제(예: 전체 시퀀스)를 일련의 작은 문제로 나누고, 작은 문제에 대한 해결책을 사용하여 더 큰 문제에 대한 최적의 해결책을 찾습니다.^[2]^[3] 최적 매칭 알고리즘, 글로벌 정렬 기법이라고도 합니다. 니들맨-운슈 알고리즘은 특히 글로벌 정렬의 품질이 가장 중요한 경우 최적의 글로벌 정렬을 위해 여전히 널리 사용됩니다. 알고리즘은 가능한 모든 정렬에 점수를 할당하며, 알고리즘의 목적은 가장 높은 점수를 갖는 모든 정렬을 찾는 것입니다.

서론

이 알고리즘은 모든 두 줄에 사용할 수 있습니다. 이 가이드에서는 그림 1과 같은 두 개의 작은 DNA 서열을 예로 들어 설명합니다.

GCATGCG GATTACA

그리드 구성

먼저 위 그림 1과 같은 격자를 구성합니다. 세 번째 열의 맨 위에서 첫 번째 문자열을 시작하고 세 번째 행의 시작에서 다른 문자열을 시작합니다. 나머지 열 및 행 헤더는 그림 1과 같이 작성합니다. 아직 그리드에 숫자가 없어야 합니다.

		G	C	A	T	G	C	G

G
A
T
T
A
C
A

채점 시스템 선택

다음으로, 각 글자의 점수를 매기는 방법을 결정합니다. 위의 예를 사용하면 한 가지 가능한 정렬 후보가 될 수 있습니다. 12345678 GCATG-CG G-ATTACA 문자가 일치하거나 일치하지 않거나 간격(삭제 또는 삽입(인델))과 일치할 수 있습니다.

일치: 현재 인덱스의 두 문자가 동일합니다.
불일치: 현재 인덱스의 두 글자가 다릅니다.
삽입(삽입 또는 삭제): 가장 좋은 정렬은 한 문자가 다른 문자열의 공백에 정렬되는 것을 포함합니다.

각 시나리오에는 점수가 할당되고 모든 쌍의 점수의 합이 전체 정렬 후보의 점수입니다. 점수를 할당하기 위한 다양한 시스템이 존재하며, 일부 시스템은 아래 스코어링 시스템 섹션에 설명되어 있습니다. 현재 Needleman과 Wunsch가^[1] 사용하는 시스템은 다음과 같습니다.

매치 : +1
불일치 또는 Indel: -1

위의 예제에서 선형의 점수는 0입니다.

+−++−−+− −> 1*4 + (−1)*4 = 0

표 채우기

두 번째 행, 두 번째 열에서 0부터 시작합니다. 각 셀의 점수를 계산하면서 셀을 행 단위로 이동합니다. 점수는 셀의 왼쪽, 왼쪽 상단 또는 왼쪽 상단(각형)에 인접한 셀의 점수를 비교하고 일치, 불일치 또는 인델에 대한 적절한 점수를 추가하여 계산됩니다. 세 가지 가능성 각각에 대한 후보 점수를 계산합니다.

위나 왼쪽 셀에서 오는 경로는 인델 페어링을 나타내므로 왼쪽 셀과 맨 위 셀의 점수를 취하고 각각의 인델에 대한 점수를 더합니다.
대각선 경로는 일치/불일치를 나타내므로 왼쪽 상단 대각선 셀의 점수를 취하여 행과 열의 대응하는 베이스(글자)가 일치하는 경우 일치하는 점수를 더하거나 일치하지 않는 경우 일치하지 않는 점수를 더합니다.

셀의 결과 점수는 세 개의 후보 점수 중 가장 높습니다.

두 번째 행에 '위' 또는 '위-좌' 셀이 없는 경우 왼쪽에 있는 기존 셀만 사용하여 각 셀의 점수를 계산할 수 있습니다. 따라서 오른쪽으로 이동할 때마다 -1이 추가됩니다. 이것은 이전 점수의 지수를 나타내기 때문입니다. 그러면 첫 번째 행이 0, -1, -2, -3, -4, -5, -6, -7이 됩니다. 각 셀 위의 기존 점수만 사용할 수 있으므로 첫 번째 열에도 동일하게 적용됩니다. 따라서 결과 표는 다음과 같습니다.

		G	C	A	T	G	C	G
	0	−1	−2	−3	−4	−5	−6	−7
G	−1
A	−2
T	−3
T	−4
A	−5
C	−6
A	−7

세 방향 모두에 기존 점수가 있는 첫 번째 경우는 우리의 첫 번째 문자(이 경우 G와 G)의 교차점입니다. 주변 세포는 아래와 같습니다.

		G
	0	−1
G	−1	X

이 셀에는 세 가지 가능한 후보 합이 있습니다.

대각선 왼쪽 위 이웃의 점수는 0입니다. G와 G의 짝은 일치하므로 일치 점수를 더하면 0+1 = 1
맨 위 이웃의 점수는 -1이고 여기서 이동하면 indel이 되므로 indel의 점수를 더합니다. (-1) + (-1) = (-2)
왼쪽 이웃도 점수가 -1이고 인델을 나타내며 (-2)를 생성합니다.

가장 높은 후보는 1이며 셀에 입력됩니다.

		G
	0	−1
G	−1	1

가장 높은 후보 점수를 준 셀도 기록해야 합니다. 위 그림 1의 완성도에서 이는 3행과 2행의 셀에서 2행의 셀로 화살표로 표시됩니다.

다음 예제에서 X와 Y 모두에 대한 대각선 단계는 불일치를 나타냅니다.

		G	C
	0	−1	−2
G	−1	1	X
A	−2	Y

X:

상단: (-2)+(-1) = (-3)
Left: (+1)+(−1) = (0)
Top-Left: (−1)+(−1) = (−2)

Y:

상단: (1)+(-1) = (0)
Left: (−2)+(−1) = (−3)
Top-Left: (−1)+(−1) = (−2)

X와 Y 모두에서 가장 높은 점수는 0입니다.

		G	C
	0	−1	−2
G	−1	1	0
A	−2	0

가장 높은 후보 점수는 인접한 두 개의 셀에 의해 달성될 수 있습니다.

	T	G
T	1	1
A	0	X

상단: (1)+(-1) = (0)
Top-Left: (1)+(−1) = (0)
Left: (0)+(−1) = (−1)

이 경우, 가장 높은 후보 점수에 도달하는 모든 방향은 그림 1의 완성도(예: 행 및 열 7의 셀)에서 가능한 원점 셀로 기록되어야 합니다.

이러한 방식으로 표를 채우면 가능한 모든 정렬 후보의 점수가 제공되며, 오른쪽 아래 셀의 점수는 최상의 정렬에 대한 정렬 점수를 나타냅니다.

원점으로 화살표 추적

화살표의 방향을 따라 오른쪽 하단의 셀에서 왼쪽 상단의 셀로 돌아오는 경로를 표시합니다. 이 경로로부터 시퀀스는 다음 규칙에 의해 구성됩니다.

대각선 화살표는 일치 또는 불일치를 나타내므로 열의 문자와 원점 셀의 행의 문자가 정렬됩니다.
가로 또는 세로 화살표는 인델을 나타냅니다. 세로 화살표는 간격("-")을 행의 문자("측면" 순서)에 맞추고, 가로 화살표는 간격을 열의 문자("상위" 순서)에 맞춥니다.
선택할 수 있는 화살표가 여러 개 있는 경우 선형의 분기를 나타냅니다. 두 개 이상의 가지가 모두 오른쪽 하단에서 왼쪽 상단 셀까지의 경로에 속하면 동일하게 실행 가능한 정렬입니다. 이 경우 경로를 별도의 정렬 후보로 기록합니다.

이러한 규칙에 따라 그림 1의 한 가지 가능한 정렬 후보에 대한 단계는 다음과 같습니다.

G → CG → GCG → -GCG → T-GCG → AT-GCG → CAT-GCG → GCAT-GCG A → CA → ACA → TACA → TTACA → ATTACA → -ATTACA → G-ATTACA              ↓     (branch) → TGCG → -TGCG → ...              → TACA → TTACA → ...

채점 시스템

기본 채점 방식

가장 간단한 채점 체계는 단순히 각 경기, 불일치 및 지수에 대한 값을 제공합니다. 위의 단계별 가이드는 match = 1, match = -1, indel = -1을 사용합니다. 따라서 정렬 점수가 낮을수록 편집 거리가 커지므로 이 채점 시스템에 대해 높은 점수를 원합니다. 또 다른 채점 시스템은 다음과 같습니다.

일치 = 1
인델 = -2
불일치 = -1

이 시스템의 경우 정렬 점수는 두 문자열 사이의 편집 거리를 나타냅니다. 상황에 따라 다른 채점 시스템을 고안할 수 있습니다. 예를 들어 간격이 정렬에 매우 나쁘다고 생각되는 경우 다음과 같이 간격에 큰 불이익을 주는 채점 시스템을 사용할 수 있습니다.

일치 = 1
불일치 = -1
인델 = -2

유사행렬

더 복잡한 채점 시스템은 변경 유형뿐만 아니라 관련된 문자에 대한 값을 속성합니다. 예를 들어, A와 A의 경기는 1로 주어질 수 있지만, T와 T의 경기는 4로 주어질 수 있습니다. 여기서 (첫 번째 점수 체계를 가정할 때) As보다 Ts 매칭에 더 중요성이 부여됩니다. 즉, Ts 매칭이 정렬에 더 중요하다고 가정합니다. 문자를 기준으로 한 이 가중치는 불일치에도 적용됩니다.

가능한 모든 문자 조합과 결과 점수를 나타내기 위해 유사도 행렬이 사용됩니다. 가장 기본적인 시스템에 대한 유사성 행렬은 다음과 같이 표시됩니다.

	A	G	C	T
A	1	−1	−1	−1
G	−1	1	−1	−1
C	−1	−1	1	−1
T	−1	−1	−1	1

각 점수는 셀이 일치하는 문자 중 하나에서 다른 문자로의 전환을 나타냅니다. 따라서 이것은 (ACGT의 알파벳에 대해) 가능한 모든 일치 및 불일치를 나타냅니다. 모든 경기는 대각선을 따라 진행되며, 모든 표를 채울 필요는 없으며, 점수는 상호이기 때문에 이 삼각형만 가능합니다.= (A → C = C → A의 점수). T-T = 4 규칙을 위에서 구현하면 다음과 같은 유사도 행렬이 생성됩니다.

	A	G	C	T
A	1	−1	−1	−1
G	−1	1	−1	−1
C	−1	−1	1	−1
T	−1	−1	−1	4

통계적으로 특정 시나리오에 적합한 다양한 작업에 가중치를 부여하는 다양한 점수 매김 행렬이 구성되었습니다. 가중 점수 행렬을 갖는 것은 다양한 아미노산의 빈도가 다르기 때문에 단백질 서열 정렬에서 특히 중요합니다. 점수 매김 행렬에는 두 개의 광범위한 계열이 있으며, 각각은 특정 시나리오에 대한 추가 변경 사항이 있습니다.

PAM
BLOSUM

갭페널티

시퀀스를 정렬할 때 간격(즉, 인델)이 있는 경우가 많고, 큰 경우도 있습니다. 생물학적으로 여러 개의 단일 삭제보다 하나의 큰 삭제로 큰 간격이 발생할 가능성이 더 높습니다. 따라서 두 개의 작은 지수는 하나의 큰 지수보다 더 나쁜 점수를 가져야 합니다. 간단하고 일반적인 방법은 새 인델에 대한 큰 간격 시작 점수와 인델을 확장하는 모든 문자에 대한 작은 간격 확장 점수를 통해 수행됩니다. 예를 들어, 새 지수는 -5, 확장 지수는 -1의 비용이 들 수 있습니다. 이러한 방식으로 다음과 같은 정렬을 수행합니다.

GAAAAAAT G--A-A-T

여러 개의 동일한 정렬이 있는 경우, 여러 개의 작은 정렬이 있는 경우 다음과 같이 정렬됩니다.

GAAAAAAT GAA----T

또는 여러 개의 작은 간격보다 선호도가 4개 긴 간격이 있는 정렬.

알고리즘의 고급 프레젠테이션

정렬된 문자의 점수는 유사도 행렬로 지정됩니다. 여기서 $S (a,$ $b)$ 는 문자 a와 b의 유사성입니다. $여기$ 서 d라고 하는 선형 갭 패널티를 사용합니다.

예를 들어, 유사성 행렬이

	A	G	C	T
A	10	−1	−3	−4
G	−1	7	−5	−3
C	−3	−5	9	0
T	−4	−3	0	8

그 다음 정렬:

AGACTAGTTAC CGA---GACGT

갭 페널티가 -5일 경우 다음 점수를 받을 수 있습니다.

S (A,C) + S (G,G) + S (A,A) + (3 \times d) + S (G,G) + S (T,A) + S (T,C) + S (A,G) + S (C,T)

= −3 + 7 + 10 − (3 × 5) + 7 + (−4) + 0 + (−1) + 0 = 1

가장 높은 점수를 가진 정렬을 찾기 위해 2차원 배열(또는 행렬) F가 할당됩니다. 행 i 및 열 j의 항목은 여기서 $F_{ij}$ ${\$ 로 표시됩니다 $F_{ij}$ 시퀀스 A에는 각 문자마다 행이 하나씩 있고, 시퀀스 B에는 각 문자마다 열이 하나씩 있습니다. 따라서 크기 n과 m의 시퀀스를 정렬하는 경우 사용되는 메모리 양은 $O(nm)$ ( $O(nm)$ $O(nm)$ ${\display O(nm)}$ 입니다 $O(nm)$ Hirschberg의 알고리즘은 메모리에서 배열의 하위 집합만 유지하고 $\Theta (\min\{n,m\})$ θ( $\Theta (\min\{n,m\})$ {n $,$ m}) ${\displaystyle \Theta(\min\{$ n,m\})} 공간을 사용합니다. 그러나 Needleman-Wunsch와 유사합니다(그러나 $O(nm)$ O( $O(nm)$ {\ $display$ O( $nm)}$ 시간이 $O(nm)$ 필요합니다).

알고리즘이 진행됨에 따라 $F_{ij}$ $F_{ij}$ 는 A의 첫 번째 $i=0,\dotsc ,n$ = 0 $i=0,\dotsc ,n$ n {\ $displaystyle$ i= $0$ ,\dotsc,n} 문자와 B의 첫 번째 j = 0, …, m {\displaystyle j=0,\dotsc,m} 문자의 정렬에 최적의 점수가 되도록 할당됩니다. 최적성의 원리는 다음과 같이 적용됩니다.

기준:

F_{0j}=d*j

F_{i0}=d*i

최적성의 원리에 기초한 재귀:

F_{ij}=\max(F_{i-1,j-1}+S(A_{i},B_{j}),\;F_{i,j-1}+d,\;F_{i-1,j}+d)

따라서 F 행렬을 계산하는 알고리즘의 의사 코드는 다음과 같습니다.

d ← i = 0 ~ 길이(A) F(i,0) ← d * i = 0 ~ 길이(B) F(0,j) ← d * i = 1 ~ 길이(A) = 1 ~ 길이(B) { 일치 ← F(i-1,j-1) + S(A,B) 삭제 ← F(i-1,j) + d 삽입 ← F(i,j-1) + d F(i,j) ← max(Match,Insert,Delete) }

F 행렬이 계산되면 $F_{nm}$ $F_{nm}$ ${\$ 엔트리가 가능한 모든 정렬 중 최대 점수를 제공합니다 $F_{nm}$ . 실제로 이 점수를 제공하는 정렬을 계산하려면 오른쪽 하단 셀에서 시작하여 값을 위의 세 가지 가능한 소스(Match, Insert, Delete)와 비교하여 해당 값이 어디에서 왔는지 확인합니다. 일치하면 $A_{i}$ ${\$ 와 $A_{i}$ $B_{j}$ ${\$ 가 $B_j$ 정렬되고, 삭제하면 $A_{i}$ ${\$ 가 갭으로 정렬되고 $A_{i}$ , 삽입하면 $B_{j}$ ${\$ 가 갭으로 정렬됩니다 $B_{j}$ . (일반적으로 두 개 이상의 선택이 동일한 값을 가질 수 있습니다, 대안적인 최적 정렬로 이어집니다.)

Alignment A ← " Alignment B ← " " " i ← length(A) j ← length(B)" 반면 (i > 0 또는 j > 0) { (i > 0 및 j > 0 및 F(i, j) == F(i-1, j-1) + S(A, B)} { Alignment A ← A + Alignment B ← B + Alignment B i ← i - 1 j ← j - 1 } 다른 경우 (i > 0 및 F(i, j) == F(i-1, j)} j) + d) {AlignmentA ← A + AlignmentA AlignmentB ← "- + AlignmentBi ← i - 1 } 그 외 {AlignmentA ← "- + AlignmentA AlignmentB ← B + AlignmentB j ← j - 1 }

복잡성

표의 각 셀에 대한 $F_{ij}$ 스코어 $F_{ij}$ ${\$ 를 계산하는 $O(1)$ 은 $O(1)$ 1 $)$ {\ $displaystyle$ O $(1$ )} 연산입니다 $O(1)$ . 따라서 길이 $n$ ${\displaystyle$ n $}$ 및 $m$ ${\displaystyle$ m $}$ 의 두 시퀀스에 대한 알고리즘의 시간 복잡도는 $O(mn)$ ${\displaystyle$ O $(mn)}$ 입니다 $m$ $O(mn)$ ^[4] 네 명의 러시아인 방법을 사용하여 실행 시간을 $O(mn/\log n)$ / $O(mn/\log n)$ ⁡ $n$ ) ${\display O(mn/\$ log n)}로 향상시킬 수 있음을 보여주었습니다. 알고리즘이 $n\times m$ × $n\times m$ ${\displaystyle$ n $\times$ m $}$ 테이블을 $n\times m$ 채웠기 때문에 공간 복잡도는 $O(mn).$ 입니다 $.$ {\ $displaystyle$ O $(mn)}$

역사 노트 및 알고리즘 개발

니들맨과 운슈가 설명한 알고리즘의 원래 목적은 두 단백질의 아미노산 서열에서 유사점을 찾는 것이었습니다.^[1]

Needleman과 Wunsch는 정렬이 일치 및 불일치만으로 불이익을 받고 간격이 패널티가 없는 경우(d=0)에 대해 알고리즘을 명시적으로 설명합니다. 1970년의 원본 출판물은 재귀 $F_{ij}=\max _{h<i,k<j}\{F_{h,j-1}+S(A_{i},B_{j}),F_{i-1,k}+S(A_{i},B_{j})\}$ = $max$ $h$ < i, $k$ < $j$ { $Fh,$ j - $1$ + S $(Ai, Bj ),$ Fi - 1, k + S (Ai, Bj )} {\displaystyle F_{ij} =\max _{h<i,k<j}\{F_{h,j-1}+S (A_{i,B_{j})), $F_{i-1,k}+S(A_{i},B_{j})\}}$ .

해당 동적 프로그래밍 알고리즘은 큐빅 시간이 소요됩니다. 이 논문은 또한 재귀가 임의의 갭 벌점 공식을 수용할 수 있다고 지적합니다.

벌점 계수는 간격이 생길 때마다 차감되는 수치로, 간격을 허용하는 데 장애물로 평가될 수 있습니다. 패널티 팩터는 갭의 크기 및/또는 방향의 함수일 수 있습니다. [444페이지]

동일한 문제에 대한 2차 실행 시간(갭 페널티 없음)을 갖는 더 나은 동적 프로그래밍 알고리즘은 이후^[6] 1972년 David Sankoff에 의해 소개되었습니다. 비슷한 2차 시간 알고리즘은 1968년 T. K. Vintsyuk에^[7] 의해 음성 처리("시간 워핑")를 위해 독립적으로 발견되었고, Robert A에 의해 발견되었습니다. 바그너와 마이클 J. 1974년에 끈 맞추기를 위해^[8] Fischer.

Needleman과 Wunsch는 유사성을 극대화하는 측면에서 자신들의 문제를 공식화했습니다. 또 다른 가능성은 Vladimir Levenshtein이 도입한 시퀀스 간 편집 거리를 최소화하는 것입니다. Peter H. Sellers는 1974년에 두 문제가 동등하다는 것을 보여주었습니다^[9].

니들맨-운슈 알고리즘은 특히 글로벌 정렬의 품질이 가장 중요한 경우 최적의 글로벌 정렬을 위해 여전히 널리 사용됩니다. 그러나 알고리즘은 시간과 공간에 대해 비용이 많이 들어 두 시퀀스 길이의 곱에 비례하므로 긴 시퀀스에는 적합하지 않습니다.

최근 개발은 품질을 유지하면서 알고리즘의 시간과 공간 비용을 개선하는 데 초점을 맞추고 있습니다. 예를 들어, 2013년 Fast Optimal Global Sequence Alignment Algorithm (FOGSAA)^[10]는 Needleman을 포함한 다른 최적의 글로벌 정렬 방법보다 더 빠른 뉴클레오티드/단백질 서열 정렬을 제안했습니다.운슈 알고리즘. 이 논문은 니들맨과 비교했을 때 다음과 같이 주장합니다.운슈 알고리즘, FOGSAA는 매우 유사한 뉴클레오티드 서열에 대해 70-90%의 시간 이득을 달성하고(유사도가 > 80%인), 30-80%인 서열에 대해 54-70%의 시간 이득을 달성합니다.

생물정보학 외부의 응용 프로그램

컴퓨터 스테레오 비전

스테레오 매칭은 한 쌍의 스테레오 이미지로부터 3D 재구성 과정에서 필수적인 단계입니다. 이미지가 수정되면 두 작업 모두 두 문자열의 문자 간에 최적의 대응 관계를 설정하는 것을 목표로 하기 때문에 뉴클레오티드 및 단백질 서열을 정렬하고 스캔 라인에 속하는 픽셀을 일치시키는 것 사이에 유사점을 도출할 수 있습니다.

예를 들어 카메라를 절제하거나 보정하는 등 많은 응용 프로그램에서 이미지 보정을 수행할 수 있지만 정확한 보정 모델의 계산 비용으로 인해 실시간 응용 프로그램에서 이미지 보정을 사용할 수 없기 때문에 불가능하거나 비현실적인 경우가 있습니다. 또한 카메라 렌즈가 빗방울, 방수 커버 또는 먼지로 인해 발생하는 것과 같은 예상치 못한 왜곡을 표시할 때 이러한 모델 중 어느 것도 적합하지 않습니다. 니들맨을 확장함으로써-Wunsch 알고리즘은 '왼쪽' 이미지의 선을 3차원 배열(또는 행렬)에서 가장 높은 점수를 갖는 정렬을 찾음으로써 '오른쪽' 이미지의 곡선과 연관시킬 수 있습니다. 실험을 통해 이러한 확장을 통해 보정되지 않거나 왜곡된 이미지 간의 조밀한 픽셀 매칭이 가능하다는 것이 입증되었습니다.^[11]

참고 항목

참고문헌

^ ^a ^b ^c Needleman, Saul B. & Wunsch, Christian D. (1970). "A general method applicable to the search for similarities in the amino acid sequence of two proteins". Journal of Molecular Biology. 48 (3): 443–53. doi:10.1016/0022-2836(70)90057-4. PMID 5420325.
^ "bioinformatics". Retrieved 10 September 2014.
^ Gagniuc, Paul A. (2021). Algorithms in bioinformatics : theory and implementation (1st ed.). Hoboken, NJ: John Wiley & Sons. ISBN 978-1-119-69800-5. OCLC 1240827446.{{cite book}}: CS1 유지보수: 날짜 및 연도(링크)
^ ^a ^b ^c Wing-Kin., Sung (2010). Algorithms in bioinformatics : a practical introduction. Boca Raton: Chapman & Hall/CRC Press. pp. 34–35. ISBN 9781420070330. OCLC 429634761.
^ Masek, William; Paterson, Michael (February 1980). "A faster algorithm computing string edit distances". Journal of Computer and System Sciences. 20: 18–31. doi:10.1016/0022-0000(80)90002-1.
^ Sankoff D (1972). "Matching sequences under deletion/insertion constraints". Proceedings of the National Academy of Sciences of the USA. 69 (1): 4–6. Bibcode:1972PNAS...69....4S. doi:10.1073/pnas.69.1.4. PMC 427531. PMID 4500555.
^ Vintsyuk TK (1968). "Speech discrimination by dynamic programming". Kibernetika. 4: 81–88. doi:10.1007/BF01074755. S2CID 123081024.
^ Wagner RA, Fischer MJ (1974). "The string-to-string correction problem". Journal of the ACM. 21 (1): 168–173. doi:10.1145/321796.321811. S2CID 13381535.
^ Sellers PH (1974). "On the theory and computation of evolutionary distances". SIAM Journal on Applied Mathematics. 26 (4): 787–793. doi:10.1137/0126070.
^ Chakraborty, Angana; Bandyopadhyay, Sanghamitra (29 April 2013). "FOGSAA: Fast Optimal Global Sequence Alignment Algorithm". Scientific Reports. 3: 1746. Bibcode:2013NatSR...3E1746C. doi:10.1038/srep01746. PMC 3638164. PMID 23624407.
^ Thevenon, J; Martinez-del-Rincon, J; Dieny, R; Nebel, J-C (2012). Dense pixel matching between unrectified and distorted images using dynamic programming. International Conference on Computer Vision Theory and Applications. Rome.

외부 링크

NW-정렬: Needleman-Wunsch 알고리즘에 의한 단백질 서열간 정렬 프로그램(온라인 서버 및 소스 코드)
Needleman의 자바스크립트 기반 라이브 데모-운슈
Needleman-Wunsch 알고리즘의 대화형 자바스크립트 기반 시각적 설명
기술 블로그의 시퀀스 정렬 기법
니들맨을 구현하는 바이오스트링 R 패키지 –다른 것들 중에서 운슈 알고리즘

[Needleman-1] Needleman, Saul B. & Wunsch, Christian D. (1970). "A general method applicable to the search for similarities in the amino acid sequence of two proteins". Journal of Molecular Biology. 48 (3): 443–53. doi:10.1016/0022-2836(70)90057-4. PMID 5420325.

[2] "bioinformatics". Retrieved 10 September 2014.

[3] Gagniuc, Paul A. (2021). Algorithms in bioinformatics : theory and implementation (1st ed.). Hoboken, NJ: John Wiley & Sons. ISBN 978-1-119-69800-5. OCLC 1240827446.{{cite book}}: CS1 유지보수: 날짜 및 연도(링크)

[:0-4] Wing-Kin., Sung (2010). Algorithms in bioinformatics : a practical introduction. Boca Raton: Chapman & Hall/CRC Press. pp. 34–35. ISBN 9781420070330. OCLC 429634761.

[5] Masek, William; Paterson, Michael (February 1980). "A faster algorithm computing string edit distances". Journal of Computer and System Sciences. 20: 18–31. doi:10.1016/0022-0000(80)90002-1.

[Sankoff-6] Sankoff D (1972). "Matching sequences under deletion/insertion constraints". Proceedings of the National Academy of Sciences of the USA. 69 (1): 4–6. Bibcode:1972PNAS...69....4S. doi:10.1073/pnas.69.1.4. PMC 427531. PMID 4500555.

[Vintsyuk-7] Vintsyuk TK (1968). "Speech discrimination by dynamic programming". Kibernetika. 4: 81–88. doi:10.1007/BF01074755. S2CID 123081024.

[WagnerFischer-8] Wagner RA, Fischer MJ (1974). "The string-to-string correction problem". Journal of the ACM. 21 (1): 168–173. doi:10.1145/321796.321811. S2CID 13381535.

[Sellers-9] Sellers PH (1974). "On the theory and computation of evolutionary distances". SIAM Journal on Applied Mathematics. 26 (4): 787–793. doi:10.1137/0126070.

[10] Chakraborty, Angana; Bandyopadhyay, Sanghamitra (29 April 2013). "FOGSAA: Fast Optimal Global Sequence Alignment Algorithm". Scientific Reports. 3: 1746. Bibcode:2013NatSR...3E1746C. doi:10.1038/srep01746. PMC 3638164. PMID 23624407.

[11] Thevenon, J; Martinez-del-Rincon, J; Dieny, R; Nebel, J-C (2012). Dense pixel matching between unrectified and distorted images using dynamic programming. International Conference on Computer Vision Theory and Applications. Rome.

[1]

[2]

[3]

[4]

[6]

[7]

[8]

[9]

[10]

[11]

v t 줄들
문자열 메트릭	대략적인 문자열 일치 비트맵 알고리즘 다메로-레벤슈테인 거리 거리 편집 게스탈트 패턴 매칭 해밍 거리 자로-윙클러 거리 리 거리 레벤슈테인 오토마톤 레벤슈테인 거리 바그너-피셔 알고리즘
문자열 검색 알고리즘	사도-지안카를로 알고리즘 보이어-모어 문자열 검색 알고리즘 보이어-무어-호스풀 알고리즘 크누스-모리스-프라트 알고리즘 라빈-카르프 알고리즘 라이타 알고리즘 트리그램 검색 양방향 문자열 일치 알고리즘 Zhu-Takaoka 문자열 일치 알고리즘
다중 문자열 검색	Aho–Corasick Commentz-Walter 알고리즘
정규식	정규 표현식 엔진의 비교 정규문법 톰슨의 작법 비결정론적 유한 오토마톤
순서 정렬	폭발. 허쉬버그의 알고리즘 니들맨 –운슈 알고리즘 스미스-워터맨 알고리즘
자료구조	DAFSA 접미사 배열 접미사 오토마톤 접미사 트리 일반화된 접미사 트리 출렁 삼원검색트리 트리
다른.	구문 분석 패턴매칭 압축패턴매칭 최장공통후계 최장공통부현 순차 패턴 마이닝 정렬 문자열 재작성 시스템 문자열 연산

Search