다중서열정렬

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

다중 서열 정렬은 여러 개의 서열에 갭을 삽입하여 모든 서열의 길이를 동일하게 만들고, 동일한 위치에 갭만 존재하는 경우가 없도록 정렬하는 것을 목표로 한다. 계산 복잡도가 높아 다양한 알고리즘과 접근 방식이 사용되며, 동적 프로그래밍, 점진적 정렬, 반복적 정렬, 합의 정렬, 은닉 마르코프 모델, 계통 발생 인식 방법, 모티프 찾기 등 다양한 방법이 존재한다. 다중 서열 정렬은 계통수 생성, 기능적 도메인 식별 등 계통 발생 분석에 활용된다.

더 읽어볼만한 페이지

마르코프 모형 - 강화 학습
강화 학습은 에이전트가 환경과의 상호작용을 통해 누적 보상을 최대화하는 최적의 정책을 학습하는 기계 학습 분야이며, 몬테카를로 방법, 시간차 학습, Q-러닝 등의 핵심 알고리즘과 탐험과 활용의 균형, 정책 경사법 등의 다양한 연구 주제를 포함한다.
마르코프 모형 - 칼만 필터
칼만 필터는 잡음이 있는 측정값들을 이용하여 선형 동적 시스템의 상태를 추정하는 재귀 필터로, 예측과 보정 단계를 반복하며 항법 시스템, 레이더 추적, 컴퓨터 비전 등 다양한 분야에 응용된다.
생물정보학 - Rosetta@home
Rosetta@home은 분산 컴퓨팅 플랫폼 BOINC를 활용하여 단백질 구조 예측 연구를 수행하며, 신약 개발 및 질병 연구에 기여하는 것을 목표로 한다.
생물정보학 - 발현체학

다중서열정렬

2. 문제 정의

다중 서열 정렬은 주어진 여러 개의 서열( $S_1, S_2, ..., S_m$ )에 갭('-')을 삽입하여 모든 서열의 길이를 같게( $S'_1, S'_2, ..., S'_m$ ) 만들고, 동일한 위치(열)에 갭만 존재하는 경우가 없도록 정렬하는 것이다. 정렬된 서열에서 각 열을 비교하면 어떤 부분이 잘 유지되고(conserved residues), 어떤 부분이 변이가 많은지(variable residues) 알 수 있다. 잘 유지되는 부분은 진화적으로 서열의 기능에 매우 중요한 부분일 가능성이 높다.^[1]

최근에는 잘 유지되는 열들 간의 상호 관계를 분석하여, 서로 연관되어 진화하는 부분이 구조 및 기능에 중요하다는 연구도 발표되고 있다. 이러한 분석 방법의 대표적인 예로 SCA(Statistical Coupling Analysis)가 있다.^[1]

수학적으로, m개의 서열 $S_i$ ( $i = 1,\cdots,m$ )는 다음과 같이 표현된다.^[1]

>

$S :=\begin{cases}S_1 = (S_{11},S_{12},\ldots, S_{1n_1}) \\S_2 = (S_{21},S_{22},\cdots, S_{2n_2}) \\\,\,\,\,\,\,\,\,\,\,\vdots \\S_m = (S_{m1},S_{m2},\ldots, S_{mn_m})\end{cases}$

>

다중 서열 정렬은 각 서열 $S_i$ 에 갭을 삽입하여, 수정된 서열 $S'_i$ 의 길이가 모두 $L \ge \max\{n_i \mid i = 1,\ldots,m\}$ 를 만족하고, 동일한 열에 갭만 있는 경우가 없도록 만든다. 다중 서열 정렬의 결과는 다음과 같이 표현된다.^[1]

>

$S' :=\begin{cases}S'_1 = (S'_{11},S'_{12},\ldots, S'_{1L}) \\S'_2 = (S'_{21},S'_{22},\ldots, S'_{2L}) \\\,\,\,\,\,\,\,\,\,\,\vdots \\S'_m = (S'_{m1},S'_{m2},\ldots, S'_{mL})\end{cases}$

>

각 $S'_i$ 에서 갭을 모두 제거하면 원래 서열 $S_i$ 로 되돌아간다.^[1]

3. 정렬 방법

다중 서열 정렬은 여러 생물학적 서열(DNA, RNA, 단백질 등)을 비교하여 유사성과 차이점을 파악하는 방법이다. 정렬된 서열에서 각 열을 비교하면 보존된 부분(conserved residues)과 변이가 있는 부분(variable residues)을 확인할 수 있다. 보존된 부분은 진화적으로 해당 서열의 기능에 중요한 부분이라고 추측할 수 있다.^[3]

최근에는 보존된 열들 간의 상호 관계를 분석하여, 서로 연관되어 진화하는 부분이 구조 및 기능에 중요하다는 연구도 발표되고 있다. 이러한 방법의 대표적인 예로 SCA(Statistical Coupling Analysis)가 있다.

다중 서열 정렬은 그래프를 사용하여 모든 가능한 정렬을 식별하는 방식으로 접근할 수 있다. 가중 그래프에서 "완전 정렬"을 생성하고, 각 간선에 특정 휴리스틱 기반의 가중치를 부여한다. 최적의 정렬은 최대 가중치를 갖는 "추적(trace)"을 선택하여 결정된다.

다중 서열 정렬에는 정렬의 점수와 정확성을 극대화하기 위해 다양한 정렬 방법이 사용된다. 각 방법은 대개 진화 과정에 대한 통찰력을 가진 특정 휴리스틱을 기반으로 한다. 대부분의 방법은 진화를 모방하여 가능한 가장 현실적인 정렬을 얻어 서열 간의 관계를 가장 잘 예측하려고 시도한다.

다중 서열 정렬은 계산 복잡도가 높은 문제이므로, 다음과 같은 다양한 알고리즘과 접근 방식이 사용된다.

동적 프로그래밍 (Dynamic Programming): 전역 최적해를 찾는 방법.^[3]
점진적 정렬 (Progressive Alignment): 가장 유사한 서열 쌍부터 시작하여 점진적으로 정렬을 확장하는 방법.^[10]
반복적 정렬 (Iterative Alignment): 초기 정렬을 반복적으로 수정하여 정확도를 높이는 방법.^[18]
합의 정렬 (Consensus Alignment): 여러 정렬 결과를 조합하여 최적의 정렬을 찾는 방법.^[21]
은닉 마르코프 모델 (Hidden Markov Model, HMM): 확률 모델을 사용하여 가능한 모든 정렬 조합을 고려하는 방법.^[18]
계통 발생 인식 방법 (Phylogeny-aware Methods): 비상동 영역을 고려하여 정렬하는 방법.^[28]
모티프 찾기 (Motif Finding): 보존된 패턴(모티프)을 찾아 정렬에 활용하는 방법.^[18]

이 방법들은 각각 장단점을 가지며, 정렬할 서열의 특성과 목적에 따라 적절한 방법을 선택해야 한다.

3. 1. 동적 프로그래밍 (Dynamic Programming)

다중 서열 정렬(MSA)을 위한 직접적인 방법은 전역적으로 최적의 정렬 해답을 찾기 위해 동적 프로그래밍 기법을 사용하는 것이다. 단백질의 경우, 이 방법은 갭 패널티와 치환 행렬이라는 두 가지 매개변수를 사용한다. 치환 행렬은 아미노산의 화학적 특성 및 돌연변이의 진화적 확률에 따라 각 아미노산 쌍의 정렬에 점수를 할당한다. 뉴클레오티드 서열의 경우에도 비슷한 갭 패널티가 사용되지만, 더 단순한 치환 행렬이 일반적이다.^[3]

''n''개의 서열을 정렬할 때, 단순한 방법은 표준 쌍별 서열 정렬에서 형성된 행렬의 ''n''차원과 동일한 행렬을 구성하는 것이다. 그러나 검색 공간은 ''n''이 증가함에 따라 지수적으로 증가하며, 서열 길이에 크게 의존한다. 빅 오 표기법으로 표현하면, 단순한 MSA는 ''O(길이^서열수)'' 시간이 소요된다. ''n''개 서열에 대한 전역 최적값을 찾는 것은 NP-완전 문제임이 밝혀졌다.^[4]^[5]^[6] 1989년, Carrillo-Lipman 알고리즘을 기반으로^[7], Altschul은 쌍별 정렬을 사용하여 n차원 검색 공간을 제한하는 실용적인 방법을 도입했다.^[8] 이 방법에서는 각 서열 쌍에 대해 쌍별 동적 프로그래밍 정렬을 수행하고, n차원 교차점 근처의 공간만 n방향 정렬에 대해 검색한다. MSA 프로그램은 각 위치에서 모든 문자 쌍의 합(''쌍의 합'' 점수)을 최적화한다.^[9] 2019년, Hosseininasab과 van Hoeve는 결정 다이어그램을 사용하면 MSA를 다항식 공간 복잡도로 모델링할 수 있음을 보였다.^[2]

3. 2. 점진적 정렬 (Progressive Alignment)

점진적 정렬(Progressive Alignment)은 다중 서열 정렬(MSA)을 구축하는 휴리스틱 검색 기법으로, 1987년 Da-Fei Feng과 Doolittle에 의해 개발되었다.^[10] 이 방법은 가장 유사한 서열 쌍에서 시작하여 가장 거리가 먼 서열로 진행하면서 쌍별 정렬을 결합하여 최종 MSA를 구축한다.

점진적 정렬 방법은 다음 두 단계를 거친다.

단계	설명
첫 번째 단계	서열 간의 관계를 계통수(가이드 트리)로 표시한다.
두 번째 단계	가이드 트리에 따라 서열을 순차적으로 추가하여 MSA를 구축한다.

초기 ''가이드 트리''는 Neighbor-joining 또는 UPGMA와 같은 군집 분석 방법으로 결정된다.^[18]

점진적 정렬은 전역적으로 최적화되지 않을 수 있으며, 초기 단계에서 발생한 오류가 최종 결과로 전파될 수 있다는 단점이 있다. 또한, 모든 서열이 서로 멀리 떨어져 있을 때 성능이 저하된다.^[18] 이러한 문제점을 개선하기 위해, 최신 프로그레시브 방법은 쿼리 세트의 개별 구성원에 비선형 방식으로 스케일링 인자를 할당하는 이차 가중치 함수를 사용하여 정렬 프로그램에 제공된 서열의 비무작위 선택을 수정한다.^[18]

점진적 정렬 방법은 많은 수(100개에서 1000개)의 서열에 대해 대규모로 구현할 수 있을 만큼 효율적이다. 널리 사용되는 점진적 정렬 방법에는 Clustal 제품군,^[11]^[12] MAFFT,^[13] T-Coffee^[14] 등이 있다. 특히 ClustalW는 계통수 구축에 광범위하게 사용되지만, 저자는 수정되지 않은 정렬을 상동성 모델링에 의한 단백질 구조 예측에 사용해서는 안 된다고 경고한다.

T-Coffee는 Clustal 및 그 파생 제품보다 느리지만, 일반적으로 서로 거리가 먼 서열 집합에 대해 더 정확한 정렬을 생성한다. T-Coffee는 쌍의 직접 정렬과 간접 정렬을 결합하여 쌍별 정렬을 계산하며, Clustal의 출력과 LALIGN을 사용하여 새롭고 더 정확한 가중치 인자를 생성하는 가이드로 사용한다.

점진적 방법은 전역 최적점으로 수렴할 것이라는 보장이 없는 휴리스틱이므로 정렬 품질을 평가하기 어렵고 실제 생물학적 중요성은 모호할 수 있다.

3. 3. 반복적 정렬 (Iterative Alignment)

반복적 방법은 초기 시퀀스를 반복적으로 재정렬하고, 증가하는 다중서열정렬(MSA)에 새로운 시퀀스를 추가하여 점진적 방법에서 발생하는 오류를 줄인다. 점진적 방법은 고품질의 초기 정렬에 크게 의존하며, 한 번 정렬된 시퀀스는 더 이상 고려되지 않는다. 이러한 접근 방식은 효율성을 높이지만 정확성을 떨어뜨린다. 반면, 반복적 방법은 이전에 계산된 쌍별 정렬 또는 쿼리 시퀀스의 하위 집합을 통합하여 고품질 정렬 점수와 같은 목적 함수를 최적화한다.^[18]

여러 반복 방법들이 구현되어 소프트웨어 패키지로 제공되고 있다.^[16] PRRN/PRRP는 MSA 정렬 점수를 최적화하기 위해 언덕 오르기 알고리즘을 사용하며,^[17] 증가하는 MSA의 정렬 가중치와 국부적으로 발산하거나 "갭이 있는" 영역을 반복적으로 수정한다.^[18] PRRP는 이전에 더 빠른 방법으로 구성된 정렬을 개선할 때 가장 좋은 성능을 보인다.^[18]

DIALIGN은 갭 패널티를 도입하지 않고 하위 세그먼트 또는 시퀀스 모티프 사이의 국부 정렬에 초점을 맞추는 접근 방식을 사용한다.^[19] 개별 모티프의 정렬은 쌍별 정렬에서 도트 매트릭스 플롯과 유사한 매트릭스 표현으로 수행된다. CHAOS/DIALIGN에는 느린 전체 정렬 절차를 위한 앵커 포인트 또는 "시드"로 빠른 국부 정렬을 사용하는 방법이 구현되어 있다.^[19]

MUSCLE (로그-기댓값에 의한 다중 시퀀스 정렬)은 두 시퀀스의 관련성을 평가하기 위한 더 정확한 거리 측정을 통해 점진적 방법을 개선했다.^[20] 거리 측정은 반복 단계 사이에서 업데이트된다(원래 MUSCLE은 2-3번의 반복만 포함했다).

다중 서열 정렬은 일반적으로 컴퓨터로 계산되며, 쌍별 정렬보다 계산 복잡도가 높고 더 정교한 알고리즘이 필요하다. 최적의 다중 정렬을 구하는 것은 계산량이 매우 크기 때문에, 일반적으로 사용되는 프로그램은 휴리스틱을 사용한다.

반복법은 누진법의 단점을 극복하기 위해 새로운 서열을 추가할 때 이미 만들어진 부분도 다시 정렬하는 방식이다. 누진법에서는 한 번 다중 정렬에 포함된 서열은 재검토 없이 최종 결과에 반영되지만, 반복법에서는 다중 정렬을 반복적으로 재구축하여 정확성을 높인다.

3. 4. 합의 정렬 (Consensus Alignment)

합의 정렬은 동일한 서열에 대한 여러 정렬 결과를 조합하여 최적의 다중 서열 정렬을 찾는 방법이다. M-COFFEE와 MergeAlign은 대표적인 합의 정렬 알고리즘이다.^[21] M-COFFEE는 7가지 다른 방법으로 생성된 다중 서열 정렬을 결합하여 합의 정렬을 만든다. MergeAlign은 다양한 서열 진화 모델이나 다중 서열 정렬 방법을 사용하여 만들어진 여러 입력 정렬로부터 합의 정렬을 생성할 수 있다. MergeAlign의 기본 설정은 91가지 단백질 서열 진화 모델을 기반으로 생성된 정렬을 통해 합의 정렬을 추론하는 것이다.

3. 5. 은닉 마르코프 모델 (Hidden Markov Model, HMM)

은닉 마르코프 모델(HMM)은 가능한 모든 갭, 일치 및 불일치의 조합에 확률을 할당하여 가장 가능성이 높은 다중서열정렬(MSA) 또는 가능한 MSA 집합을 결정할 수 있는 확률 모델이다.^[18] HMM은 전역 정렬과 국소 정렬을 모두 생성할 수 있으며, 단일 최고 점수 출력뿐만 아니라 생물학적 중요성을 평가할 수 있는 가능한 정렬 집합도 생성할 수 있다. HMM 기반 방법은 비교적 최근에 개발되었지만 특히 중복 영역을 포함하는 서열의 경우 계산 속도가 크게 향상된다.^[18]

일반적인 HMM 기반 방법은 MSA를 부분 순서 그래프라고 하는 방향 비순환 그래프 형태로 표현하여 작동하며, MSA 열의 가능한 항목을 나타내는 일련의 노드로 구성된다. 이 표현에서 절대적으로 보존된 열(즉, MSA의 모든 서열이 특정 위치에서 특정 문자를 공유하는 열)은 정렬의 다음 열에 가능한 문자 수만큼 많은 발신 연결이 있는 단일 노드로 코딩된다. 일반적인 은닉 마르코프 모델의 관점에서 관찰된 상태는 개별 정렬 열이고 "숨겨진" 상태는 쿼리 세트의 서열이 추정적으로 파생된 것으로 가정한 추정 조상 서열을 나타낸다. 비터비 알고리즘이라는 동적 프로그래밍 방법의 효율적인 검색 변형은 일반적으로 성장하는 MSA를 쿼리 세트의 다음 서열에 연속적으로 정렬하여 새로운 MSA를 생성하는 데 사용된다.^[22] 이는 이전 서열의 정렬이 각 새로운 서열 추가 시 업데이트되기 때문에 점진적 정렬 방법과 구별된다. 그러나 점진적 방법과 마찬가지로 이 기술은 특히 서열이 서로 멀리 관련되어 있는 경우 쿼리 세트의 서열이 정렬에 통합되는 순서의 영향을 받을 수 있다.^[18]

HMM 기반 방법의 변형은 여러 소프트웨어 프로그램에 구현되어 확장성과 효율성으로 유명하지만, HMM 방법을 제대로 사용하는 것은 더 일반적인 점진적 방법을 사용하는 것보다 더 복잡하다. 가장 간단한 것은 부분 순서 정렬(POA)이고,^[23] 유사하고 더 일반적인 방법은 시퀀스 정렬 및 모델링 시스템(SAM) 소프트웨어 패키지^[24] 및 HMMER에 구현되어 있다.^[25] SAM은 단백질 구조 예측을 위한 정렬 소스로 사용되어 구조 예측 실험인 구조 예측 중요 평가(CASP)에 참여하고 효모 종 ''S. cerevisiae''에서 예측된 단백질 데이터베이스를 개발했다. HHsearch^[26]는 HMM의 쌍별 비교를 기반으로 원격으로 관련된 단백질 서열을 감지하기 위한 소프트웨어 패키지이다. HHsearch를 실행하는 서버(HHpred)는 CASP7 및 CASP8 구조 예측 경쟁에서 10개의 자동 구조 예측 서버 중 가장 빨랐다.^[27]

3. 6. 계통 발생 인식 방법 (Phylogeny-aware Methods)

대부분의 다중 서열 정렬 방법은 삽입/결손(갭) 수를 최소화하려고 시도하며, 그 결과 압축된 정렬을 생성한다. 이는 정렬할 서열에 비상동 영역이 포함되어 있거나, 갭이 계통 발생 분석에서 유용한 정보를 제공하는 경우 몇 가지 문제를 야기한다. 이러한 문제는 새롭게 생성된 서열에서 흔히 발생하며, 주석이 부족하고 프레임 시프트, 잘못된 단백질 도메인 또는 비상동 RNA 스플라이싱 엑손을 포함할 수 있다.

반복적 방법을 통한 비상동 엑손 정렬 (a) 및 계통 인식 방법을 통한 정렬 (b)

이러한 방법 중 최초의 방법은 2005년 Löytynoja와 Goldman에 의해 개발되었다.^[28] 같은 저자들은 2008년에 ''PRANK''라는 소프트웨어 패키지를 출시했다.^[29] PRANK는 삽입이 있는 경우 정렬을 개선하지만, 수년 동안 개발되어 온 점진적 및/또는 반복적 방법에 비해 속도가 느리다.

2012년, 두 개의 새로운 계통 인식 도구가 등장했다. 하나는 PRANK와 동일한 팀에서 개발한 ''PAGAN''이다.^[30] 다른 하나는 Szalkowski가 개발한 ''ProGraphMSA''이다.^[31] 두 소프트웨어 패키지는 독립적으로 개발되었지만, 비상동 영역의 인식을 개선하기 위해 그래프 알고리즘을 사용하고, PRANK보다 이러한 소프트웨어의 속도를 향상시키는 코드 개선이라는 공통적인 특징을 공유한다.

3. 7. 모티프 찾기 (Motif Finding)

모티프 찾기(프로파일 분석)는 더 나은 다중 서열 정렬(MSA)을 생성하고, 유사한 모티프를 검색하는 데 사용할 수 있는 점수 행렬을 만드는 방법으로, 전역 MSA에서 서열 모티프를 찾는 방법이다. 여러 방법들이 개발되었지만, 모두 더 큰 정렬 내에서 짧고 보존된 패턴을 식별하고, 잠정적인 모티프의 각 위치의 아미노산 또는 뉴클레오티드 조성을 반영하는 치환 행렬과 유사한 행렬을 구성하는 것을 기반으로 한다. 그런 다음 이러한 행렬을 사용하여 정렬을 개선할 수 있다. 표준 프로파일 분석에서 행렬은 각 가능한 문자와 갭에 대한 항목을 포함한다.^[18] 통계적 패턴 찾기 알고리즘은 MSA의 파생물이 아닌 전구체로 모티프를 식별할 수도 있다. 쿼리 세트에 소수의 서열만 포함되거나, 관련성이 높은 서열만 포함하는 경우, 가상 계수를 추가하여 점수 행렬에 반영된 분포를 정규화한다. 특히, 이는 행렬의 0 확률 항목을 작지만 0이 아닌 값으로 수정한다.

블록 분석은 정렬에서 갭이 없는 영역으로 모티프를 제한하는 모티프 찾기 방법이다. 블록은 MSA에서 생성되거나, 알려진 유전자 계열에서 이전에 생성된 공통 모티프의 미리 계산된 세트를 사용하여 정렬되지 않은 서열에서 추출할 수 있다.^[32] 블록 점수는 명시적 치환 행렬의 계산보다는 빈번한 문자의 간격에 일반적으로 의존한다.

통계적 패턴 매칭은 기대 값 최대화 알고리즘과 깁스 샘플러를 사용하여 구현되었다. 가장 일반적인 모티프 찾기 도구 중 하나인 Multiple EM for Motif Elicitation(MEME)는 기대 값 최대화 및 은닉 마르코프 방법을 사용하여 모티프를 생성한 다음, 결합된 MEME/MAST 제품군에서 해당 컴패니언 MAST에 의해 검색 도구로 사용된다.^[33]^[34]

MEME로 식별된 모티프에 따라 색상이 지정된 7개의 초파리 카스파제의 정렬. 모티프 위치와 서열 정렬이 독립적으로 생성될 때, 이 예시에서처럼 종종 잘 상관관계를 가지지만 완벽하지는 않다.

4. 비암호화 서열 정렬 (Non-coding Sequence Alignment)

전사 인자 결합 부위(TFBS)와 같은 비부호화 DNA 영역은 보존되지만 반드시 진화적으로 관련이 있는 것은 아니며, 공통 조상에서 기원하지 않았을 수 있다. 따라서 단백질 서열과 DNA 부호화 영역을 정렬하는 데 사용되는 가정은 TFBS 서열에 적용되는 가정과 본질적으로 다르다. 돌연변이 연산자를 사용하여 상동 서열의 DNA 부호화 영역을 정렬하는 것은 의미가 있지만, 동일한 전사 인자에 대한 결합 부위 서열의 정렬은 진화적으로 관련된 돌연변이 연산을 사용할 수 없다. 마찬가지로, 점 돌연변이의 진화 연산자는 부호화 서열의 편집 거리를 정의하는 데 사용할 수 있지만, TFBS 서열에는 거의 의미가 없다. 왜냐하면 모든 서열 변이는 결합 부위가 기능하기 위해 특정 수준의 특이성을 유지해야 하기 때문이다.

이는 알려진 TFBS 서열을 정렬하여 동일한 TFBS의 알려지지 않은 위치를 예측하기 위한 지도 학습 모델을 구축하려는 경우 특히 중요해진다. 따라서 다중 서열 정렬 방법은 결합 부위의 특이성을 보존하면서 가장 낮은 열역학적 정렬을 검색하기 위해 인접한 염기 열역학 정보를 통합해야 한다.^[35]

5. 최적화 기법

컴퓨터 과학의 표준 최적화 기법은 품질 좋은 다중 서열 정렬(MSA)을 보다 효율적으로 생성하기 위해 사용되어 왔다. 이러한 기법에는 유전자 알고리즘, 시뮬레이티드 어닐링, 수리 최적화, 양자 컴퓨팅 등이 있다.

시뮬레이티드 어닐링 기법은 다른 방법에 의해 생성된 기존의 MSA를 개선하여 정렬 공간의 더 나은 영역을 찾는다. 이 기법은 유전자 알고리즘 방법과 마찬가지로 쌍의 합 함수와 같은 목적 함수를 최대화한다. 시뮬레이티드 어닐링은 재배열 속도와 각 재배열의 가능성을 결정하는 "온도 계수"를 사용하며, 높은 재배열 속도와 낮은 가능성을 갖는 기간(정렬 공간의 먼 영역 탐색)과 낮은 속도와 높은 가능성을 갖는 기간(새 영역 근처의 국소 최소값 탐색)을 번갈아 사용한다. 이 접근 방식은 MSASA(Multiple Sequence Alignment by Simulated Annealing)라는 프로그램에 구현되었다.^[38]

5. 1. 유전 알고리즘 (Genetic Algorithm)

유전자 알고리즘은 진화 과정을 광범위하게 시뮬레이션하여 다중 서열 정렬(MSA)을 생성하는 데 사용된다. 이 방법은 가능한 MSA들을 조각으로 분해하고, 다양한 위치에 갭을 도입하여 조각들을 반복적으로 재배열한다. 시뮬레이션 중에는 목적 함수가 최적화되는데, 주로 동적 프로그래밍 기반 MSA 방법에서 사용되는 "쌍의 합" 함수를 최대화한다. 단백질 서열 정렬에는 SAGA(Sequence Alignment by Genetic Algorithm) 소프트웨어가 사용되며,^[36] RNA 서열 정렬에는 RAGA가 사용된다.^[37]

5. 2. 시뮬레이티드 어닐링 (Simulated Annealing)

다중 서열 정렬은 수작업으로도 가능하지만, 일반적으로 컴퓨터를 사용한다. 1:1로 정렬하는 '''쌍별 정렬'''(pairwise alignment)보다 계산 복잡도가 높아 더 정교한 알고리즘이 필요하다. 최적의 다중 정렬을 계산하는 것은 매우 어렵기 때문에, 일반적으로 사용되는 프로그램들은 휴리스틱을 사용한다.

5. 3. 수리 계획법 (Mathematical Programming)

수리 최적화 및 특히 혼합 정수 계획법 모델은 다중서열정렬(MSA) 문제를 해결하는 또 다른 접근 방식이다. 이러한 최적화 모델은 기존의 동적 프로그래밍 접근 방식보다 더 효율적으로 최적의 MSA 해답을 찾을 수 있다는 장점이 있다. 이는 MSA 모델을 더 작은 부분으로 분해하고 최적의 해답이 발견될 때까지 반복적으로 해결하는 수리 계획법에 대한 분해 기술을 적용할 수 있기 때문이다. MSA의 혼합 정수 계획법 모델을 해결하는 데 사용되는 알고리즘으로는 분기 및 가격^[39] 및 벤더스 분해^[2]가 있다. 정확한 접근 방식은 MSA에 대한 휴리스틱 알고리즘에 비해 계산 속도가 느리지만, 대규모 문제에서도 결국 최적의 해답에 도달할 수 있다.

5. 4. 양자 컴퓨팅 (Quantum Computing)

2017년 1월, D-Wave Systems는 자사의 오픈 소스 양자 컴퓨터 소프트웨어인 qbsolv가 다중서열정렬(MSA) 문제에 대한 더 빠른 해결책을 찾는 데 성공적으로 사용되었다고 발표했다.^[40] 다중 서열 정렬은 일반적으로 컴퓨터로 계산하는데, 이는 배열을 1:1로 정렬하는 쌍별 정렬(pairwise alignment)보다 계산 복잡도가 높고 더 정교한 알고리즘이 필요하기 때문이다. 최적의 다중 정렬을 구하려면 매우 많은 계산량이 요구되므로, 일반적으로 사용되는 프로그램은 휴리스틱을 사용한다.

6. 정렬 시각화 및 품질 관리

다중 서열 정렬 결과는 다중 서열 정렬 뷰어를 통해 시각적으로 검토할 수 있으며, 종종 두 개 이상의 서열에서 주석이 달린 기능적 부위의 정렬 품질을 검사하여 검토할 수 있다.^[42] 또한, 필요한 경우 수동으로 편집하여 계통 발생 분석이나 비교 모델링에 적합한 최적의 '큐레이션된' 정렬을 얻을 수 있다.^[42]

그러나 많은 수의 서열을 다루거나 게놈 전체 연구와 같이 많은 MSA를 포함하는 경우에는 모든 정렬을 수동으로 큐레이션하는 것은 불가능하며, 수동 큐레이션은 주관적이다.^[43] 또한, 최고의 전문가조차도 매우 분기된 서열의 모호한 경우를 자신 있게 정렬할 수 없다. 이러한 경우 신뢰할 수 없는 정렬 영역을 MSA에서 제외하기 위해 자동 절차를 사용하는 것이 일반적이다.^[43]

계통 발생 재구성을 위해 Gblocks 프로그램은 정렬 열에서 갭이 있는 서열의 수에 대한 다양한 컷오프에 따라 품질이 낮은 것으로 의심되는 정렬 블록을 제거하는 데 널리 사용된다.^[43] SOAP 프로그램^[44]은 CLUSTALW의 매개변수에서 각 열의 견고성을 테스트한다. T-Coffee 프로그램^[45]은 최종 MSA를 구성하는 데 정렬 라이브러리를 사용하며, 해당 출력 MSA는 각 정렬 잔기에 대해 라이브러리의 다른 정렬 간의 일치를 반영하는 신뢰도 점수에 따라 색상이 지정된다. 확장 기능인 전이 일관성 점수(TCS)는 T-Coffee 라이브러리 쌍별 정렬을 사용하여 모든 타사 MSA를 평가한다.^[46]^[47] FSA^[48]는 정렬의 불확실성을 계산할 수 있는 통계 모델을 사용하며, HoT(Heads-Or-Tails) 점수^[49]는 여러 최적 솔루션의 존재로 인한 사이트별 정렬 불확실성의 척도로 사용할 수 있다. GUIDANCE 프로그램^[50]은 점진적 정렬 프로그램에 사용되는 가이드 트리의 불확실성에 대한 정렬의 견고성을 기반으로 유사한 사이트별 신뢰도 척도를 계산한다. BAli-Phy 프로그램^[51]은 베이즈 접근 방식을 사용하여 추정된 계통 발생 및 정렬의 사후 확률을 계산하고, 정렬의 각 사이트에 대해 사후 확률을 계산할 수 있다.

Jalview 및 UGENE과 같은 무료 프로그램을 사용하여 다중 서열 정렬을 시각화할 수 있다.

7. 계통 발생 분석에서의 활용

다중 서열 정렬은 계통수를 생성하여 생물 간의 진화 관계를 추론하는 데 사용된다.^[52] 이는 두 가지 이유로 가능하다. 첫째, 주석이 달린 서열에서 알려진 기능적 도메인이 주석이 없는 서열의 정렬에 사용될 수 있다. 둘째, 기능적으로 중요한 것으로 알려진 보존된 영역을 찾을 수 있다. 이를 통해 다중 서열 정렬을 사용하여 서열 간의 상동성을 통해 진화적 관계를 분석하고 찾을 수 있다. 점 돌연변이와 삽입 또는 삭제 이벤트(인델이라고 함)를 감지할 수 있다.

다중 서열 정렬은 보존된 도메인을 찾아 결합 부위, 활성 부위 또는 기타 주요 기능에 해당하는 부위와 같이 기능적으로 중요한 부위를 식별하는 데도 사용된다. 다중 서열 정렬을 통해 서열을 비교할 때 서열의 동일성, 유사성 및 상동성과 같은 다른 측면을 고려하는 것이 유용하다. 동일성은 서열이 각 위치에서 동일한 잔기를 갖는다는 것을 의미한다. 유사성은 비교되는 서열이 정량적으로 유사한 잔기를 갖는 것을 의미한다. 예를 들어, 뉴클레오티드 서열의 경우 피리미딘은 서로 유사한 것으로 간주되며, 퓨린도 마찬가지다. 유사성은 궁극적으로 상동성으로 이어진다. 즉, 서열이 유사할수록 상동성에 가까워진다. 그런 다음 서열의 이러한 유사성은 공통 조상을 찾는 데 도움이 될 수 있다.^[52]

정렬 뒤 서열의 열 위치별로 유지가 잘 되고 있는 것들(conserved residues)과 유지가 되지 않고 있는 것들(variable residues)을 비교해 보면, 유지가 잘 되는 부분은 진화적으로 서열의 기능에 매우 중요한 부분으로 생각할 수 있다.

최근에는 적절히 유지되고 있는 열들끼리의 상호관계를 분석하여 서로 연관되어 진화하는 부분이 구조 및 기능에 중요하다는 연구 발표도 있으며, 이의 대표적인 방법으로 SCA(Statistical Coupling Analysis) 방법이 있다.

8. 참고 문헌

Duret, L.|듀렛^영어과 S. Abdeddaim|압데다임^영어 (2000). 〈Multiple alignment for structural functional or phylogenetic analyses of homologous sequences^영어〉. D. Higgins and W. Taylor. 《Bioinformatics sequence structure and databanks^영어》. Oxford: Oxford University Press^영어.
Notredame, C.|노르트담^영어 (2002). “Recent progresses in multiple sequence alignment: a survey^영어”. 《Pharmacogenomics^영어》 3 (1): 131–144.
Thompson, J. D.|톰슨^영어, F. Plewniak|플레우니악^영어, O. Poch|포치^영어 (1999). “A comprehensive comparison of multiple sequence alignment programs^영어”. 《Nucleic Acids Research^영어》 27 (13): 12682–2690.
Wallace, I.M.|월리스^영어, G. Blackshields|블랙실즈^영어, D.G. Higgins|히긴스^영어 (2005). “Multiple sequence alignments^영어”. 《Curr Opin Struct Biol^영어》 15 (3): 261–266.
Notredame, C.|노르트담^영어 (2007). “Recent Evolutions of Multiple Sequence Alignment Algorithms^영어”. 《PLOS Computational Biology^영어》 3 (8): e123.
http://cmb.molgen.mpg.de/ 다중 서열 정렬 강의 – 막스 플랑크 분자 유전학 연구소
https://web.archive.org/web/20120305164700/http://www.embl.de/~seqanal/courses/commonCourseContent/commonMsaExercises.html 강의 노트 및 실습 유럽 분자 생물학 연구소 (EMBL)
https://web.archive.org/web/20110904184621/http://www.avatar.se/molbioinfo2001/ 분자 생물 정보학 강의 노트
https://web.archive.org/web/20090821192233/http://bioinf.may.ie/school02/notes.html 분자 진화 및 생물 정보학 강의 노트

참조

_[1] 논문 A comprehensive benchmark study of multiple sequence alignment methods: current challenges and future perspectives
_[2] 논문 Exact Multiple Sequence Alignment by Synchronized Decision Diagrams
_[3] 웹사이트 Help with matrices used in sequence comparison tools http://www.ebi.ac.uk[...] European Bioinformatics Institute 2010-03-03
_[4] 논문 On the complexity of multiple sequence alignment
_[5] 논문 Computational complexity of multiple sequence alignment with SP-score
_[6] 논문 Settling the intractability of multiple alignment
_[7] 논문 The Multiple Sequence Alignment Problem in Biology https://zenodo.org/r[...]
_[8] 논문 A tool for multiple sequence alignment
_[9] 웹사이트 Genetic analysis software https://www.ncbi.nlm[...] National Center for Biotechnology Information 2010-03-03
_[10] 논문 Progressive sequence alignment as a prerequisitet to correct phylogenetic trees
_[11] 논문 CLUSTAL: a package for performing multiple sequence alignment on a microcomputer
_[12] 논문 CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice 1994-11
_[13] 웹사이트 EMBL-EBI-ClustalW2-Multiple Sequence Alignment http://www.ebi.ac.uk[...]
_[14] 논문 T-Coffee: A novel method for fast and accurate multiple sequence alignment 2000-09
_[15] 논문 A polynomial time solvable formulation of multiple sequence alignment
_[16] 논문 Comprehensive study on iterative algorithms of multiple sequence alignment
_[17] 논문 Significant improvement in accuracy of multiple protein sequence alignments by iterative refinement as assessed by reference to structural alignments
_[18] 서적 Bioinformatics: Sequence and Genome Analysis Cold Spring Harbor Laboratory Press
_[19] 논문 Fast and sensitive multiple alignment of large genomic sequences 2003-12
_[20] 논문 MUSCLE: multiple sequence alignment with high accuracy and high throughput
_[21] 논문 MergeAlign: improving multiple sequence alignment performance by dynamic reconstruction of consensus multiple sequence alignments
_[22] 논문 Hidden Markov models for sequence analysis: extension and analysis of the basic method
_[23] 논문 Combining partial order alignment and progressive multiple sequence alignment increases alignment speed and scalability to very large alignment problems
_[24] 간행물 SAM: Sequence alignment and modeling software system University of California 1996-09
_[25] 서적 Biological sequence analysis: probabilistic models of proteins and nucleic acids Cambridge University Press
_[26] 논문 Protein homology detection by HMM-HMM comparison
_[27] 논문 Automated server predictions in CASP7
_[28] 논문 An algorithm for progressive multiple alignment of sequences with insertions
_[29] 논문 Phylogeny-aware gap placement prevents errors in sequence alignment and evolutionary analysis 2008-06
_[30] 논문 Accurate extension of multiple sequence alignments using a phylogeny-aware graph algorithm 2012-07
_[31] 논문 Fast and robust multiple sequence alignment with phylogeny-aware gap placement 2012-06
_[32] 논문 Automated assembly of protein blocks for database searching 1991-12
_[33] 서적 Proceedings of the Second International Conference on Intelligent Systems for Molecular Biology AAAI Press
_[34] 논문 Combining evidence using p-values: application to sequence homology searches 1998
_[35] 논문 A non-independent energy-based multiple sequence alignment improves prediction of transcription factor binding sites 2013-11
_[36] 논문 SAGA: sequence alignment by genetic algorithm 1996-04
_[37] 논문 RAGA: RNA sequence alignment by genetic algorithm
_[38] 논문 Multiple sequence alignment using simulated annealing
_[39] 논문 A branch-and-cut algorithm for multiple sequence alignment
_[40] 웹사이트 D-Wave Initiates Open Quantum Software Environment 11 January 2017 http://www.dwavesys.[...] 2017-01-20
_[41] 논문 The accuracy of several multiple sequence alignment programs for proteins
_[42] 웹사이트 Manual editing and adjustment of MSAs http://www.embl.de/~[...] European Molecular Biology Laboratory 2010-03-07
_[43] 논문 Selection of conserved blocks from multiple alignments for their use in phylogenetic analysis 2000-04
_[44] 논문 SOAP, cleaning multiple alignments from unstable blocks 2001-06
_[45] 논문 Tcoffee@igs: A web server for computing, evaluating and combining multiple sequence alignments 2003-07
_[46] 논문 TCS: A New Multiple Sequence Alignment Reliability Measure to Estimate Alignment Accuracy and Improve Phylogenetic Tree Reconstruction. 2014-06
_[47] 논문 TCS: a web server for multiple sequence alignment evaluation and phylogenetic reconstruction 2015-07
_[48] 논문 Fast statistical alignment 2009-05
_[49] 서적 Biocomputing 2008 2008
_[50] 논문 An alignment confidence score capturing robustness to guide tree uncertainty 2010-08
_[51] 논문 Joint Bayesian estimation of alignment and phylogeny 2005-06
_[52] 웹사이트 Multiple sequence alignment exercises and demonstrations http://www.embl.de/~[...] European Molecular Biology Laboratory 2009-02-10
_[53] 논문 On the complexity of multiple sequence alignment
_[54] 논문 Computational complexity of multiple sequence alignment with SP-score
_[55] 논문 Settling the intractability of multiple alignment http://www.lieberton[...]
_[56] 문서 Bioinformatics: Sequence and Genome Analysis 2nd ed Cold Spring Harbor Laboratory Press 2004
_[57] 논문 CLUSTAL: a package for performing multiple sequence alignment on a microcomputer
_[58] 논문 CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice
_[59] 논문 T-Coffee: A novel method for fast and accurate multiple sequence alignment

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com