개요 #

두 개의 시퀀스(일반적으로 DNA, RNA 또는 단백질 시퀀스) 사이의 전역 정렬(global alignment)을 수행하는 알고리즘입니다. 이 알고리즘은 문자열 비교에 기반하여 시퀀스 간의 유사성을 찾아내는데 사용됩니다. DNA 시퀀스 비교, 단백질 시퀀스 비교, 생물학적 진화와 같은 분야에서 널리 사용됩니다.

단계 #

1. Score Matrix Initialization: 차원이 (m+1) x (n+1)인 2차원 행렬을 만듭니다. 여기서 m과 n은 정렬할 두 시퀀스의 길이입니다. 행렬의 각 셀은 두 시퀀스의 해당 부분에 대한 정렬 점수를 나타냅니다.

2. Initialization: 간격 페널티를 기준으로 행렬의 첫 번째 행 및 첫 번째 열 값을 설정합니다. 첫 번째 행은 간격이 있는 첫 번째 시퀀스 정렬을 나타내고 첫 번째 열은 간격이 있는 두 번째 시퀀스 정렬을 나타냅니다.

3. Scoring : 세 가지 가능한 작업을 기반으로 정렬 점수를 계산하여 매트릭스의 나머지 셀을 채웁니다. 1) 일치/불일치: 점수는 두 시퀀스에 있는 문자의 유사성을 기반으로 합니다. 2)시퀀스 1의 간격: 점수는 첫 번째 시퀀스에 간격을 삽입한 것에 대한 페널티를 기반으로 합니다. 3)시퀀스 2의 간격: 점수는 두 번째 시퀀스에 간격을 삽입한 것에 대한 페널티를 기반으로 합니다. 각 셀에 대한 점수는 인접한 3개 셀(왼쪽, 대각선 및 위)의 점수를 고려하고 적절한 일치/불일치 또는 간격 페널티를 추가하여 결정됩니다.

4. Traceback : 채점 매트릭스가 완료되면 매트릭스의 오른쪽 아래 모서리에서 왼쪽 위 모서리까지 역추적하여 최적의 정렬이 결정됩니다. 이 역추적은 가장 높은 점수의 정렬을 제공합니다