전역 정렬과 지역 정렬의 차이점은 무엇입니까?

전역 정렬 (Needleman-Wunsch)은 두 서열을 종단 간 정렬하며, 길이가 비슷하고 전체적으로 관련이 있을 것으로 예상될 때 적절합니다. 지역 정렬 (Smith-Waterman)은 가장 잘 일치하는 하위 영역을 찾으며, 더 큰 서열 내의 보존된 도메인과 같이 서열의 일부만 유사할 때 적절합니다.

서열 정렬은 최장 공통 부분 서열과 동일합니까?

밀접하게 관련되어 있습니다. 최장 공통 부분 서열은 특정 점수 (일치에 보상, 갭은 자유, 불일치는 허용되지 않음)를 가진 정렬의 특별한 경우입니다. 일반적인 정렬은 치환 비용과 갭 페널티를 포함하는 더 풍부한 점수를 사용하지만, 둘 다 동일한 종류의 동적 프로그래밍 재귀로 해결됩니다.

서열 정렬 알고리즘

서열 정렬 알고리즘은 삽입, 삭제 및 치환에 대한 동적 프로그래밍을 사용하여 한 문자열을 다른 문자열로 변환하는 가장 낮은 비용의 방법을 찾아 두 문자열 간의 유사성을 측정하고 표시합니다.

PaperMind(으)로 주제 찾기곧 제공Find papers & topics

Tools & resources

슬라이드 다운로드

Learn & explore

동영상곧 제공

Definition

서열 정렬은 갭을 삽입하고 문자를 일치시키거나 불일치시키거나 치환함으로써 두 개 (또는 그 이상)의 문자열 간의 대응을 최대화하기 위한 배열입니다. 정렬 알고리즘은 일반적으로 동적 프로그래밍을 통해 주어진 비용 또는 점수 모델 하에서 최적의 정렬과 그 점수를 계산합니다.

Scope

이 주제는 문자열 비교를 위한 동적 프로그래밍 알고리즘을 다룹니다: 편집 (레벤슈타인) 거리 및 최장 공통 부분 서열, 전역 정렬 (Needleman-Wunsch), 지역 정렬 (Smith-Waterman), 그리고 생물학적 정렬을 형성하는 점수 체계 (갭 페널티, 치환 행렬). 이는 기본 재귀와 그 이차 시간 및 공간 비용, 그리고 공간 절약 개선 사항을 다룹니다. 인덱스 기반 및 정확 일치 방법은 관련 주제에서 다룹니다.

Core questions

두 문자열 간의 유사성은 편집 거리 또는 정렬 점수로 어떻게 정량화됩니까?
동적 프로그래밍 테이블은 최적의 정렬을 어떻게 계산합니까?
전역 정렬과 지역 정렬을 구별하는 것은 무엇이며, 각각은 언제 적절합니까?
갭 페널티와 치환 행렬은 결과 정렬에 어떻게 영향을 미칩니까?
긴 서열에 대한 이차 공간 요구 사항을 어떻게 줄일 수 있습니까?

Key concepts

편집 (레벤슈타인) 거리
최장 공통 부분 서열
전역 정렬
지역 정렬
Needleman-Wunsch 알고리즘
Smith-Waterman 알고리즘
갭 페널티
치환 행렬

Key theories

동적 프로그래밍에 의한 전역 정렬: Needleman-Wunsch 알고리즘은 동적 프로그래밍 테이블을 채우는데, 이 테이블의 항목은 문자열 접두사의 최상의 정렬 점수를 제공하여 두 서열의 길이 곱에 비례하는 시간 내에 최적의 종단 간 (전역) 정렬을 산출합니다.
공유 부분 서열을 위한 지역 정렬: Smith-Waterman 알고리즘은 정렬이 어디에서든 시작하고 끝날 수 있도록 재귀를 수정하여 가장 높은 점수를 얻는 일치 영역 (지역 정렬)을 찾습니다. 이는 그렇지 않은 서열 내에서 보존된 단편을 감지하는 데 필수적입니다.

Clinical relevance

서열 정렬은 계산 생물학의 초석으로, DNA, RNA 및 단백질 서열을 상동성, 진화론적 추론 및 데이터베이스 검색 (휴리스틱 BLAST는 지역 정렬을 기반으로 함)을 위해 비교하는 데 사용됩니다. 생물학 외적으로, 동일한 편집 거리 메커니즘은 맞춤법 검사, 퍼지 텍스트 매칭, 버전 제어 차이, 음성 및 필기 비교에 사용됩니다.

History

레벤슈타인은 1965년에 편집 거리를 도입했습니다. Needleman과 Wunsch는 1970년에 단백질에 대한 최초의 동적 프로그래밍 전역 정렬 알고리즘을 제시했으며, Smith와 Waterman은 1981년에 지역 정렬을 도입했습니다. Hirschberg의 선형 공간 기법 (1975)과 BLAST와 같은 후속 휴리스틱은 정렬을 대규모 실용적 사용으로 확장했습니다.

Key figures

Saul Needleman
Christian Wunsch
Temple Smith
Michael Waterman
Vladimir Levenshtein

Seminal works

needleman1970
smith1981
gusfield1997

Frequently asked questions

전역 정렬과 지역 정렬의 차이점은 무엇입니까?: 전역 정렬 (Needleman-Wunsch)은 두 서열을 종단 간 정렬하며, 길이가 비슷하고 전체적으로 관련이 있을 것으로 예상될 때 적절합니다. 지역 정렬 (Smith-Waterman)은 가장 잘 일치하는 하위 영역을 찾으며, 더 큰 서열 내의 보존된 도메인과 같이 서열의 일부만 유사할 때 적절합니다.
서열 정렬은 최장 공통 부분 서열과 동일합니까?: 밀접하게 관련되어 있습니다. 최장 공통 부분 서열은 특정 점수 (일치에 보상, 갭은 자유, 불일치는 허용되지 않음)를 가진 정렬의 특별한 경우입니다. 일반적인 정렬은 치환 비용과 갭 페널티를 포함하는 더 풍부한 점수를 사용하지만, 둘 다 동일한 종류의 동적 프로그래밍 재귀로 해결됩니다.