This is a good article. Click here for more information.

다중 시퀀스 정렬

Multiple sequence alignment
여러 유기체에서 산성 리보솜 단백질 P0(L10E) 인스턴스들의 단백질 다중 시퀀스 정렬의 처음 90개 위치.ClustalX로 생성됨.

다중 시퀀스 정렬(MSA)은 세 개 이상의 생물학적 시퀀스(일반적으로 단백질, DNA 또는 RNA)의 시퀀스 정렬 프로세스 또는 결과를 나타낼 수 있다.많은 경우에, 질의 시퀀스의 입력 세트는 그들이 연계를 공유하고 공통 조상의 후손인 진화적 관계를 갖는 것으로 가정된다.결과 MSA로부터 시퀀스 동질학을 유추할 수 있으며, 시퀀스의 공유 진화 기원을 평가하기 위해 계통생성 분석을 수행할 수 있다.오른쪽 이미지에서와 같은 선형의 시각적 묘사는 단일 선형 열에서 서로 다른 문자로 나타나는 점 돌연변이(단일 아미노산 또는 뉴클레오티드 변화)와 선형에서 하나 이상의 시퀀스에서 하이픈으로 나타나는 삽입 또는 삭제 돌연변이(인델 또는 간격)와 같은 돌연변이 사건을 나타낸다.다중 시퀀스 정렬은 종종 단백질 영역, 3차 및 2차 구조, 심지어 개별 아미노산 또는 뉴클레오티드의 시퀀스 보존을 평가하기 위해 사용된다.

계산 알고리즘은 생물학적으로 관련된 길이가 주어진 시퀀스를 수동으로 처리하기가 어렵고 난해하기 때문에 MSA를 생산하고 분석하는 데 사용된다.MSA는 계산적으로 더 복잡하기 때문에 쌍방향 정렬보다 더 정교한 방법론을 요구한다.대부분의 다중 시퀀스 정렬 프로그램은 적당한 길이의 몇 개 이상의 시퀀스 사이의 최적 정렬을 식별하는 것은 엄청나게 계산적으로 비싸기 때문에 글로벌 최적화보다는 경험적 접근법을 사용한다.반면에 경험적 접근법은 일반적으로 솔루션 품질에 대한 보증을 제공하지 못하며 경험적 접근법은 벤치마크 사례에서 최적 솔루션보다 훨씬 낮은 경우가 많다.[1][2][3]

문제명세서

시퀀스 = , 이(가) 아래 형식과 유사함:

된 시퀀스인 의 각 {i 시퀀스에 필요한 만큼의 간격을 삽입하여 이 시퀀스 의 복수 시퀀스 길이 L i = 을 준수한다., 의 에 있는 값은 공백으로만 구성되지 않는다.상기 시퀀스 세트의 MSA의 수학적 형태는 다음과 같다.

각 특정 시퀀스 에서 으)로 돌아가려면 모든 간격을 제거하십시오

그래프 작성 접근법

다중 시퀀스 선형을 계산할 때 일반적인 접근법은 그래프를 사용하여 모든 다른 선형을 식별하는 것이다.그래프를 통해 선형을 찾을 때, 정점 집합과 가장자리 집합을 포함하는 가중 그래프에 완전한 선형이 작성된다.각 그래프 가장자리는 원래 그래프의 각 정렬 또는 부분 집합을 점수화하는 데 도움이 되는 특정 경험적 경험에 기초한 가중치를 가진다.

선형 추적

각 MSA에 가장 적합한 맞춤을 결정할 때 일반적으로 추적이 생성된다.트레이스는 해당 정점들 사이에서 선택된 가장자리에 기초하여 특정한 가중치를 갖는 실현된 정점들 또는 해당 정점과 정렬된 정점의 집합이다.시퀀스 집합에 대한 트레이스를 선택할 때는 시퀀스의 최적 정렬을 위해 최대 중량을 가진 트레이스를 선택해야 한다.

정렬 방법

선형의 점수 및 정확성을 극대화하기 위해 여러 시퀀스 내에서 다양한 정렬 방법이 사용된다.각각은 보통 진화 과정에 대한 통찰력을 가진 어떤 휴리스틱스에 기초한다.대부분의 사람들은 시퀀스 사이의 관계를 가장 잘 예측하기 위해 가능한 가장 현실적인 정렬을 얻기 위해 진화를 복제하려고 한다.

동적 프로그래밍

MSA를 생산하는 직접적인 방법은 동적 프로그래밍 기법을 사용하여 전지구적으로 최적의 정렬 솔루션을 식별한다.단백질의 경우, 이 방법은 보통 두 가지 매개변수 세트를 포함한다. 즉, 아미노산의 화학적 특성의 유사성과 돌연변이의 진화적 확률을 바탕으로 각각의 가능한 아미노산 쌍의 정렬에 점수나 확률을 할당하는 갭 벌과 대체 매트릭스.뉴클레오티드 시퀀스의 경우 유사한 갭 페널티가 사용되지만, 동일한 일치와 불일치만 고려되는 훨씬 간단한 대체 매트릭스가 대표적이다.대체 행렬의 점수는 모두 양수이거나 전역 정렬의 경우 양수 및 음수일 수 있지만 국소 정렬의 경우 양수 및 음수여야 한다.[4]

n개의 개별 시퀀스에 대해, 순진한 방법은 표준 쌍들의 시퀀스 정렬에서 형성된 행렬의 n차원 등가물을 구성해야 한다.따라서 검색 공간은 n이 증가함에 따라 기하급수적으로 증가하며 시퀀스 길이에 따라 크게 달라진다.계산 복잡성을 측정하는 데 일반적으로 사용되는 큰 O 표기법으로 표현되며, 순수 MSA는 생산에 O(LengthNseqs) 시간이 걸린다.n 시퀀스에 대한 글로벌 최적화를 찾기 위해 이 방법은 NP-완전성 문제로 나타났다.[5][6][7]1989년 알츠철은 카리요-립만 알고리즘을 기반으로 쌍방향 맞춤을 이용해 n차원 검색 공간을 제약하는 실용적인 방법을 도입했다.[8][9]이 접근법에서 쌍방향 동적 프로그래밍 선형은 쿼리 세트의 각 시퀀스 쌍에 대해 수행되며, 이러한 선형의 n차원 교차점 근처의 공간만 n-way 선형에 대해 검색된다.MSA 프로그램은 정렬의 각 위치에서 모든 문자 쌍의 합(일명 쌍 점수 합)을 최적화하며, 다중 시퀀스 정렬을 구성하기 위한 소프트웨어 프로그램에서 구현되었다.[10]2019년 호세인나사브와 판 호베는 의사결정도를 이용하여 다항 공간 복잡도에서 MSA를 모델링할 수 있다는 것을 보여주었다.[3]

점진적 정렬 구조

다중 시퀀스 정렬에 가장 널리 사용되는 접근법은 1987년 다페이펑과 두리틀이 개발한 진보적 기법(위계적 또는 트리적 방법이라고도 함)으로 알려진 경험적 접근법을 사용한다.[11]점진적 정렬은 가장 유사한 쌍으로 시작하고 가장 먼 관련으로 진행하면서 쌍방향 정렬을 결합하여 최종 MSA를 구축한다.모든 진행적 정렬 방법에는 두 가지 단계가 필요하다. 즉, 시퀀스 사이의 관계를 안내 트리라고 하는 트리로 나타내는 첫 번째 단계와 가이드 트리에 따라 성장하는 MSA에 시퀀스를 순차적으로 추가하여 MSA를 구축하는 두 번째 단계가 필요하다.초기 안내 트리는 인접 결합 또는 UPGMA와 같은 효율적인 클러스터링 방법에 의해 결정되며, 동일한 2글자 하위 시퀀스 수에 기초하여 거리를 사용할 수 있다(동적 프로그래밍 정렬이 아닌 FASTA에서).[12]

점진적 정렬은 전 세계적으로 최적화가 보장되지 않는다.가장 큰 문제는 MSA를 성장시킬 때 어느 단계에서든 오류가 발생하면 이러한 오류들이 최종 결과를 통해 전파된다는 것이다.또한 세트의 모든 시퀀스가 다소 멀리 연관되어 있을 때 성능은 특히 나쁘다.대부분의 현대적 프로그레시브 방식은 가장 가까운 이웃과의 계통생성 거리를 바탕으로 비선형 방식으로 설정된 쿼리 구성원의 개별 구성원에게 스케일링 계수를 할당하는 2차 가중 기능으로 채점 기능을 수정한다.이것은 정렬 프로그램에 주어진 시퀀스의 무작위 선택을 보정한다.[12]

점진적 정렬 방법은 많은(100~1000초) 시퀀스에 대해 대규모로 구현할 수 있을 정도로 효율적이다.점진적 정렬 서비스는 일반적으로 공개적으로 액세스할 수 있는 웹 서버에서 제공되므로 사용자는 관심 애플리케이션을 로컬로 설치할 필요가 없다.가장 인기 있는 진보적 정렬 방법은 Clustal 계열, 특히 [13]게놈넷, EBI, EMBNet 등 다수의 웹 포털이 접속을 제공하는 가중변형 ClustalW이다[14].다른 포털이나 구현은 사용자 인터페이스에 따라 다를 수 있으며 사용자가 다른 매개변수에 접근할 수 있도록 할 수 있다.ClustalW는 이러한 연구에서 수정되지 않은 선형을 사용해서는 안 된다는 저자의 명시적 경고에도 불구하고 계통생성 트리 구축에 광범위하게 사용되며 동질학 모델링에 의한 단백질 구조 예측을 위한 입력으로 사용된다.Clustal 계열의 현재 버전은 ClustalW2이다.엠블-EBI는 CLustalW2가 2015년 8월 만료된다고 발표했다.그들은 씨앗을 뿌린 안내 나무와 단백질 정렬을 위한 HMH 프로파일링 기술을 기반으로 하는 Clustal Omega를 추천한다.그들은 진행형 DNA 정렬을 위한 다른 MSA 도구를 제공한다.그 중 하나가 MAFFT(Fast Fourier Transform을 이용한 다중 정렬)이다.[15]

T-Coffee라고[16] 불리는 또 다른 일반적인 진행 정렬 방법은 Clustal과 그 파생 모델보다 느리지만 일반적으로 멀리 관련된 시퀀스 세트에 대해 더 정확한 정렬을 생성한다.T-커피는 쌍의 각 순서를 세 번째 순서로 정렬하는 간접 맞춤과 쌍의 직접 정렬을 결합하여 쌍의 선형을 계산한다.Clustal의 출력과 두 시퀀스 사이에 로컬 정렬의 여러 영역을 찾는 또 다른 로컬 정렬 프로그램 LALING을 사용한다.결과 정렬과 계통생성 트리는 새롭고 더 정확한 가중 인자를 생성하기 위한 지침으로 사용된다.

진보적 방법은 글로벌 최적으로 수렴할 수 있는 것이 보장되지 않는 휴리스틱스이기 때문에 정렬 품질을 평가하기 어려울 수 있고 그 진정한 생물학적 중요성이 불명확해질 수 있다.다항식 시간대에 계속 실행되는 동안 정렬 품질을 개선하고 손실 휴리스틱을 사용하지 않는 반진행 방식이 PSAlign 프로그램에서 구현됐다.[17]

반복적 방법

진행적 방법에 내재된 오류를 줄이면서 MSA를 생성하는 일련의 방법은 진행적 방법과 유사하게 작용하지만, 증가하는 MSA에 새로운 시퀀스를 추가하는 것은 물론 초기 시퀀스를 반복적으로 재조정하기 때문에 "반복적"으로 분류된다. 한 가지 이유는 진행적 방법은 고품질 초기화에 매우 강하게 의존한다.l 정렬은 이러한 정렬이 항상 최종 결과에 통합된다는 사실 즉, 시퀀스가 MSA에 정렬되면 그 정렬은 더 이상 고려되지 않는다.이 근사치는 정확성을 희생하여 효율을 향상시킨다.대조적으로, 반복적인 방법은 높은 품질의 정렬 점수를 찾는 것과 같은 일반적인 목표 함수를 최적화하는 수단으로 쿼리 시퀀스의 하위 집합을 포함하는 이전에 계산된 쌍방향 맞춤 또는 하위 MSA로 돌아갈 수 있다.[12]

미묘하게 다른 다양한 반복 방법이 구현되어 소프트웨어 패키지로 제공되었다. 검토와 비교는 유용했지만 일반적으로 "최상의" 기법을 선택하는 것은 삼가고 있다.[18]소프트웨어 패키지 PRRN/PRP는 Hill-Climbing 알고리즘을 사용하여 MSA 정렬 점수를[19] 최적화하고, 증가하는 MSA에서 정렬 가중치와 국소적으로 다른 영역 또는 "가피" 영역을 반복적으로 수정한다.[12] PRRP는 이전에 더 빠른 방법으로 구성한 정렬을 정제할 때 최상의 성능을 발휘한다.[12]

또 다른 반복 프로그램인 DIALIGN은 갭 페널티를 도입하지 않고 서브섹션이나 시퀀스 모티브 간의 국부적 정렬에 좁게 집중하는 특이한 접근 방식을 취하고 있다.[20]그런 다음 개별 모티브의 정렬은 한 쌍의 선형으로 도트 매트릭스 그림과 유사한 행렬 표현을 사용하여 달성된다.더 느린 글로벌 얼라인먼트 절차를 위해 빠른 로컬 얼라인먼트를 앵커 포인트 또는 "시드"로 사용하는 대체 방법이 카오스/DIALOGN 스위트에서 구현된다.[20]

세 번째 인기 있는 반복 기반 방법인 MUSIC(Log-expectation에 의한 다중 시퀀스 정렬)은 두 시퀀스의 관련성을 평가하기 위해 보다 정확한 거리 측정으로 진행 방법을 개선한다.[21]거리 측정은 반복 단계 사이에 업데이트된다(단, 원래 형태에서 MUSIC은 정교화 활성화 여부에 따라 2~3회 반복만 포함했다).

컨센서스 방식

컨센서스 방법은 동일한 시퀀스 집합의 서로 다른 여러 정렬이 주어진 최적의 다중 시퀀스 정렬을 찾으려고 시도한다.M-COFFee와 MergeAlign이라는 두 가지 공통적인 합의 방법이 있다.[22]M-COFFee는 7가지 다른 방법에 의해 생성된 다중 시퀀스 얼라인먼트를 사용하여 일치된 얼라인먼트를 생성한다.MergeAlign은 시퀀스 진화의 다른 모델 또는 다중 시퀀스 정렬의 다른 방법을 사용하여 생성된 입력 정렬의 수에서 일치된 정렬을 생성할 수 있다.MergeAlign의 기본 옵션은 91개의 단백질 시퀀스 진화 모델을 사용하여 생성된 선형을 사용하여 일치된 정렬을 추론하는 것이다.

히든 마르코프 모델

다중 시퀀스 정렬을 모델링하는 프로파일 HMM

Hidden Markov 모델은 가장 가능성이 높은 MSA 또는 가능한 MSAs 집합을 결정하기 위해 가능한 모든 간격, 일치 및 불일치 조합에 가능성을 할당할 수 있는 확률론적 모델이다.HMM은 단일 가장 높은 점수의 출력을 생성할 수 있지만 생물학적 중요성을 평가할 수 있는 가능한 선형의 제품군을 생성할 수도 있다.HMM은 글로벌 및 로컬 얼라인먼트를 모두 생산할 수 있다.HMM 기반 방법은 비교적 최근에 개발되었지만, 특히 중복 영역을 포함하는 시퀀스의 경우 계산 속도가 상당히 향상되었다.[12]

일반적인 HMH 기반 방법은 MSA를 MSA의 열에 가능한 항목을 나타내는 일련의 노드로 구성된 부분 순서 그래프라고 알려진 방향의 악순환 그래프의 한 형태로 나타냄으로써 작동한다.이 표현에서 절대적으로 보존된 열(즉, MSA의 모든 시퀀스가 특정 위치에서 특정 문자를 공유한다는 것)은 정렬의 다음 열에 가능한 한 많은 송신 연결을 가진 단일 노드로 코드화된다.전형적인 숨겨진 마르코프 모델의 용어에서 관찰된 상태는 개별 정렬 열이며 "숨겨진" 상태는 쿼리 세트의 시퀀스가 가정된 추정된 조상 순서를 나타낸다.Viterbi 알고리즘이라고 알려진 동적 프로그래밍 방법의 효율적인 검색 변형은 일반적으로 증가하는 MSA를 새로운 MSA를 생성하기 위한 쿼리 세트의 다음 순서에 연속적으로 맞추는 데 사용된다.[23]이는 새로운 시퀀스 추가 시마다 이전 시퀀스의 정렬이 업데이트되기 때문에 점진적 정렬 방식과는 구별된다.그러나, 프로그레시브 방식과 마찬가지로, 이 기법은 특히 시퀀스가 멀리 연관되어 있을 때 질의 집합의 시퀀스가 정렬에 통합되는 순서에 의해 영향을 받을 수 있다.[12]

비록 HMM 방법을 적절하게 사용하는 것이 보다 일반적인 진행 방법을 사용하는 것보다 더 복잡하지만, HM 기반 방법을 구현하고 확장성과 효율성으로 주목받는 여러 소프트웨어 프로그램을 이용할 수 있다.가장 간단한 방법은 POA(부품-주문 정렬)이며,[24] 패키지 SAM(시퀀스 정렬 및 모델링 시스템)에서 유사하지만 보다 일반화된 방법이 구현된다.[25]그리고 HMER.[26] SAM은 CASP 구조 예측 실험에 참여하고 효모종 S. 세레비시아에서 예측 단백질의 데이터베이스를 개발하기 위해 단백질 구조 예측을 위한 정렬의 원천으로 사용되어 왔다.HHsearch는[27] HMHs의 쌍방향 비교를 바탕으로 원격 관련 단백질 시퀀스를 검출하기 위한 소프트웨어 패키지로, HHSearch(HHPred)를 실행하는 서버는 CASP7과 CASP8 구조 예측대회에서 10대 최고 자동구조 예측 서버 중 단연 빨랐다.[28]

필로겐 인식 방법

반복 방법(a) 및 계통발생 인식 방법(b)에 의한 비호몰성 exon 정렬

대부분의 다중 시퀀스 정렬 방법은 삽입/삭제(갑) 횟수를 최소화하기 위해 노력하며, 그 결과 소형 정렬을 생성한다.이는 정렬할 시퀀스가 비호몰 영역을 포함할 경우, 간격이 계통 분석에서 유용할 경우 몇 가지 문제를 야기한다.이러한 문제는 주석을 제대로 달지 못한 새로 생성된 시퀀스에서 흔히 볼 수 있으며 프레임 변형, 잘못된 도메인 또는 비호몰성 스플라이징 엑손 등이 포함될 수 있다.최초의 그러한 방법은 뢰티노자와 골드먼에 의해 2005년에 개발되었다.[29]같은 저자들이 2008년 'GRYK'라는 소프트웨어 패키지를 출시했다.[30]장난은 삽입이 있을 때 정렬을 개선한다.그럼에도 불구하고, 그것은 몇 년 동안 개발된 진보적 및/또는 반복적 방법에 비해 느리게 실행된다.

2012년에는 두 개의 새로운 혈전 인식 도구가 등장했다.하나는 FROCK과 같은 팀에서 개발한 PANGIAN이라고 한다.[31]다른 하나는 Szalkowski가 개발한 ProGraphMSA이다.[32]두 소프트웨어 패키지는 독립적으로 개발되었지만 공통적인 특징을 공유하며, 특히 그래프 알고리즘을 사용하여 비호몰 지역 인지도를 향상시키고, 코드 개선을 통해 이러한 소프트웨어를 FROCK보다 빠르게 만들었다.

모티브 찾기

MEME에 의해 식별된 모티브에 의해 색칠된 7개의 드로필라카스파스 정렬. 모티브 위치 및 시퀀스 정렬이 독립적으로 생성될 때, 이 예에서와 같이 잘 상관되지만 완벽하지는 않은 경우가 많다.

프로파일 분석이라고도 하는 모티프 소견은 글로벌 MSA에서 시퀀스 모티브를 찾는 방법으로, 더 나은 MSA를 생산하는 수단이며 유사한 모티브를 찾기 위해 다른 시퀀스를 검색하는 데 사용할 채점 매트릭스를 생성하는 수단이다.모티브를 분리하는 다양한 방법이 개발되었지만, 모두 큰 정렬 내에서 보존도가 높은 짧은 패턴을 식별하고, 퍼팅 모티브에서 각 위치의 아미노산 또는 뉴클레오티드 구성을 반영하는 대체 매트릭스와 유사한 매트릭스를 구성하는 것에 기초하고 있다.그런 다음 이러한 행렬을 사용하여 정렬을 조정할 수 있다.표준 프로파일 분석에서 행렬은 가능한 각 문자에 대한 항목과 간격에 대한 항목을 포함한다.[12]또는 통계 패턴 찾기 알고리즘은 모티브를 파생이 아닌 MSA의 전구체로 식별할 수 있다.쿼리 집합이 적은 수의 시퀀스만 포함하거나 관련성이 높은 시퀀스만 포함하는 경우 점수 매트릭스에 반영된 분포를 정상화하기 위해 유사 마운트가 추가되는 경우가 많다.특히 이것은 행렬의 확률 0 항목을 작지만 0이 아닌 값으로 수정한다.

블럭 분석은 모티브를 선형에서 잘리지 않은 영역으로 제한하는 모티브 찾기 방법이다.블록은 MSA에서 생성되거나 이전에 알려진 유전자 제품군에서 생성된 사전 계산된 공통 모티브 집합을 사용하여 정렬되지 않은 시퀀스에서 추출할 수 있다.[33]블록 스코어링은 일반적으로 명시적 대체 매트릭스의 계산보다는 고주파 문자의 간격에 의존한다.블록스 서버는 이러한 모티브를 정렬되지 않은 시퀀스에서 찾을 수 있는 대화형 방법을 제공한다.

통계 패턴 매칭은 기대 최대화 알고리즘과 Gibbs sampler를 모두 사용하여 구현되었다.MEME라고 알려진 가장 일반적인 모티브 찾기 도구 중 하나는 기대 극대화와 숨겨진 마르코프 방법을 사용하여 결합 스위트 MEME/MAST에서 동반자 MAST가 검색 도구로 사용하는 모티브를 생성한다.[34][35]

비코딩 다중 시퀀스 정렬

부호화되지 않은 DNA 지역, 특히 TFBS는 오히려 더 보존되어 있고 진화적으로 반드시 관련이 있는 것은 아니며, 비일반적인 조상으로부터 융합되었을 수도 있다.따라서 단백질 시퀀스와 DNA 코딩 영역을 정렬하는 데 사용되는 가정은 TFBS 시퀀스를 유지하는 가정과는 본질적으로 다르다.돌연변이 연산자를 사용하여 동질 시퀀스에 대한 DNA 코딩 영역을 정렬하는 것은 의미가 있지만, 동일한 전사 인자에 대한 결합 현장 시퀀스의 정렬은 진화 관련 돌연변이 연산에 의존할 수 없다.마찬가지로 점 돌연변이의 진화 연산자는 시퀀스 코딩에 대한 편집 거리를 정의하는 데 사용할 수 있지만, 이는 바인딩 사이트가 작동하기 위해 일정 수준의 특수성을 유지해야 하기 때문에 TFBS 시퀀스에 별 의미가 없다.이것은 동일한 TFBS의 알려지지 않은 위치를 예측하기 위해 감시 모델을 구축하기 위해 알려진 TFBS 시퀀스를 정렬하려고 할 때 특히 중요해진다.따라서 다중 시퀀스 정렬 방법은 결합 부위 EDNA의 특수성을 보존하는 가장 낮은 열역학적 정렬을 검색하는 결합 부지를 정렬하기 위해 인접한 기초 열역학 정보를 통합한 연구에서와 같이 사용되는 운영자와 기본적인 진화 가설을 조정할 필요가 있다.

최적화

유전자 알고리즘 및 시뮬레이션 어닐링

컴퓨터 과학의 표준 최적화 기법(두 가지 모두 물리적 프로세스에서 영감을 받았으나 직접 재현하지는 않음)도 질 높은 MSA를 보다 효율적으로 생산하기 위한 시도로 사용되어 왔다.그러한 기법 중 하나인 유전 알고리즘은 MSA 생산에 사용되어 왔는데, 이는 쿼리 세트의 차이를 초래한 가설의 진화 과정을 광범위하게 시뮬레이션하기 위한 시도였다.이 방법은 일련의 가능한 MSA를 조각으로 부수고, 다양한 위치에서 틈새의 도입으로 조각들을 반복적으로 재배열하는 방식으로 작동한다.일반적인 목표 함수는 시뮬레이션 중에 최적화되며, 대부분 동적 프로그래밍 기반 MSA 방법에 도입된 "쌍의 합" 최대화 함수가 대부분이다.소프트웨어 프로그램 SAGA(유전자 알고리즘에 의한 시퀀스 정렬)[37]에서 단백질 시퀀스 기법이 구현되어 RNA에서 동등한 것을 RAGA라고 한다.[38]

다른 방법에 의해 생성된 기존 MSA가 입력 정렬이 이미 점유하고 있는 것보다 정렬 공간의 더 나은 영역을 찾도록 설계된 일련의 재배열로 정제되는 시뮬레이션 어닐링의 기법.유전자 알고리즘 방법과 마찬가지로, 시뮬레이션된 어닐링은 총합 함수와 같은 객관적 함수를 최대화한다.시뮬레이션된 어닐링은 재배열이 진행되는 속도와 각 재배열의 가능성을 결정하는 은유적인 "온도 인자"를 사용한다. 일반적인 용도는 낮은 비율과 높은 리켈의 기간으로 상대적으로 낮은 확률의 높은 재배열률 기간을 대체한다.새로운 "입식" 지역 근처에 있는 지역 미니마를 보다 철저하게 탐구하기 위한 ihoods.이 접근방식은 MSASA(Multiple Sequence Alignment by Simulated Annealing) 프로그램에서 구현되었다.[39]

수학적 프로그래밍 및 정확한 솔루션 알고리즘

수학 프로그래밍과 특히 혼합 정수 프로그래밍 모델은 MSA 문제를 해결하기 위한 또 다른 접근법이다.이러한 최적화 모델의 장점은 기존의 DP 방식에 비해 최적의 MSA 솔루션을 보다 효율적으로 찾을 수 있다는 점이다.이는 부분적으로 MSA 모델이 더 작은 부분으로 분해되어 최적의 해결책이 발견될 때까지 반복적으로 해결되는 수학 프로그램에 대한 분해 기법의 적용 가능성 때문이다.MSA의 혼합 정수 프로그래밍 모델을 해결하기 위해 사용되는 알고리즘에는 지점과 가격[40], Benders 분해 등이 있다.[3]정확한 접근법은 MSA에 대한 경험적 경험적 알고리즘에 비해 계산적으로 느리지만, 큰 규모의 문제라도 결국 최적의 해결책에 도달할 수 있도록 보장된다.

시뮬레이션 양자 컴퓨팅

2017년 1월 D-Wave Systems는 자사의 qbsolv 오픈소스 양자 컴퓨팅 소프트웨어가 MSA 문제에 대한 보다 빠른 해결책을 찾기 위해 성공적으로 사용되었다고 발표했다.[41]

정렬 시각화 및 품질 관리

다중 정렬에 필요한 휴리스틱스의 사용은 임의의 단백질 집합의 경우 정렬에 오류가 포함될 가능성이 항상 높다는 것을 의미한다.예를 들어, BAliBase 벤치마크를 사용하여 몇 가지 선도적인 정렬 프로그램을 평가한 결과 정렬된 아미노산의 모든 쌍 중 적어도 24%가 잘못 정렬된 것으로 나타났다.[2]이러한 오류는 하나 이상의 시퀀스 영역에 고유한 삽입 또는 시퀀스만으로 쉽게 정렬되지 않는 단백질로 이어지는 좀 더 복잡한 진화 과정을 통해 발생할 수 있다.시퀀스의 수와 그 차이가 증가함에 따라 MSA 알고리즘의 경험적 발견적 특성 때문에 더 많은 오류가 발생할 것이다.다중 시퀀스 정렬 뷰어는 종종 두 개 이상의 시퀀스에서 주석 처리된 기능 현장의 정렬 품질을 검사하여 선형을 시각적으로 검토할 수 있다.또한 대부분의 경우 계통발생학적 분석 또는 비교 모델링에 사용하기에 적합한 최적의 '커스트' 정렬을 얻기 위해 이러한 (대개 사소한) 오류를 수정하기 위해 선형을 편집할 수 있다.[42]

그러나 시퀀스의 수가 증가하고 특히 많은 MSA를 포함하는 게놈 전체 연구에서 모든 정렬을 수동으로 큐레이션하는 것은 불가능하다.게다가 수동 큐레이션은 주관적이다.그리고 마지막으로, 아무리 뛰어난 전문가라도 고도로 갈린 시퀀스의 더 모호한 사례들을 자신 있게 정렬할 수는 없다.이러한 경우 신뢰할 수 없는 정렬 영역을 MSA에서 제외하기 위해 자동 절차를 사용하는 것이 일반적인 관행이다. 계통발생 재구성을 위해(아래 참조) Gblock 프로그램은 정렬 열의 절단된 시퀀스 수에 대한 다양한 컷오프에 따라 낮은 품질의 정렬 블록을 제거하기 위해 널리 사용된다.[43]그러나 이러한 기준은 여전히 신뢰성 있게 정렬될 수 있는 삽입/삭제 이벤트가 있는 영역을 과도하게 필터링할 수 있으며, 이러한 영역은 긍정적 선택 검출과 같은 다른 목적을 위해 바람직할 수 있다.몇 개의 정렬 알고리즘은 높은 신뢰도의 영역을 선택할 수 있는 사이트별 점수를 출력한다.그러한 서비스는 SOAP 프로그램에 의해 처음 제공되었는데,[44] SOAP 프로그램은 인기 있는 정렬 프로그램 CLUSTALW의 파라미터에서 각 컬럼의 동요를 위한 강건성을 시험한다.T-Coffee[45] 프로그램은 최종 MSA 구성 시 선형 라이브러리를 사용하며, 출력 MSA는 각 정렬 잔여물에 대한 라이브러리의 서로 다른 선형 간의 합의를 반영하는 신뢰도 점수에 따라 색상이 지정된다.그것의 확장인 TCS : (Transitive Consistency Score)는 제3자 MSA를 평가하기 위해 쌍방향 정렬의 T-Coffee 라이브러리를 사용한다. 쌍방향 예측은 빠르고 느린 방법을 사용하여 생성될 수 있으므로 속도와 정확성 사이의 절충이 가능하다.[46][47]신뢰도 점수로 MSA를 출력할 수 있는 또 다른 정렬 프로그램은 FSA로,[48] 정렬의 불확실성을 계산할 수 있는 통계적 모델을 사용한다.HoT(Heads-Or-Tails) 점수는 여러 개의 공동 최적 솔루션이 존재하기 때문에 현장 고유의 정렬 불확실성의 척도로 사용할 수 있다.[49]GUIDE 프로그램은[50] 진행적 정렬 프로그램에 사용되는 가이드 트리의 불확실성에 대한 정렬의 견고성에 기초하여 유사한 현장 고유 신뢰도를 계산한다.선형 불확실성을 평가하기 위한 대안적이고 통계적으로 더 정당화된 접근방식은 계통생성과 선형의 공동 추정에 확률론적 진화 모델을 사용하는 것이다.베이지안 접근방식은 추정 혈전생성과 정렬의 후측 확률을 계산할 수 있으며, 이는 이러한 추정치에 대한 신뢰도의 척도다.이 경우 선형에서 각 부지에 대해 후방 확률을 계산할 수 있다.그러한 접근법은 BALI-Py 프로그램에서 구현되었다.[51]

Jalview와 UGENE와 같은 다중 시퀀스 얼라인먼트의 시각화를 위한 무료 프로그램이 있다.

계통적 이용

여러 개의 시퀀스 정렬을 사용하여 계통 생성 트리를 만들 수 있다.[52]이것은 두 가지 이유로 가능하다.첫째는 주석 처리된 시퀀스에서 알려진 기능 도메인을 비고지 시퀀스에서 정렬하는 데 사용할 수 있기 때문이다.다른 하나는 기능적으로 중요하다고 알려진 보존 지역을 찾을 수 있다는 것이다.이를 통해 여러 시퀀스 정렬을 사용하여 시퀀스 간의 호몰로학을 통해 진화적 관계를 분석하고 찾을 수 있다.포인트 돌연변이와 삽입 또는 삭제 이벤트(인델이라고 함)를 검출할 수 있다.

또한 복수의 시퀀스 정렬을 사용하여 보존된 도메인을 찾아 바인딩 사이트, 활성 사이트 또는 기타 주요 기능에 해당하는 사이트와 같은 기능적으로 중요한 사이트를 식별할 수 있다.다중 시퀀스 정렬을 볼 때 시퀀스를 비교할 때 시퀀스의 다른 측면을 고려하는 것이 유용하다.이러한 측면에는 정체성, 유사성, 호몰로지 등이 포함된다.ID는 시퀀스가 각자의 위치에서 동일한 잔류물을 갖는 것을 의미한다.반면에 유사성은 유사한 잔류물을 정량적으로 가지고 있는 시퀀스와 비교되는 것과 관련이 있다.예를 들어 뉴클레오티드 시퀀스 측면에서 피리미딘은 청개처럼 서로 유사한 것으로 간주된다.유사성은 결국 동음이의어로 연결되는데, 유사한 시퀀스일수록 동음이의어가 되는 데 더 가깝다.이러한 시퀀스에서의 유사성은 공통 조상을 찾는 데 도움이 될 수 있다.[52]

참고 항목

참조

  1. ^ Thompson JD, Linard B, Lecompte O, Poch O (2011). "A comprehensive benchmark study of multiple sequence alignment methods: current challenges and future perspectives". PLOS ONE. 6 (3): e18093. Bibcode:2011PLoSO...618093T. doi:10.1371/journal.pone.0018093. PMC 3069049. PMID 21483869.
  2. ^ a b Nuin PA, Wang Z, Tillier ER (2006). "The accuracy of several multiple sequence alignment programs for proteins". BMC Bioinformatics. 7: 471. doi:10.1186/1471-2105-7-471. PMC 1633746. PMID 17062146.
  3. ^ a b c Hosseininasab A, van Hoeve WJ (2019). "Exact Multiple Sequence Alignment by Synchronized Decision Diagrams". INFORMS Journal on Computing. doi:10.1287/ijoc.2019.0937.
  4. ^ "Help with matrices used in sequence comparison tools". European Bioinformatics Institute. Archived from the original on March 11, 2010. Retrieved March 3, 2010.
  5. ^ Wang L, Jiang T (1994). "On the complexity of multiple sequence alignment". J Comput Biol. 1 (4): 337–348. CiteSeerX 10.1.1.408.894. doi:10.1089/cmb.1994.1.337. PMID 8790475.
  6. ^ Just W (2001). "Computational complexity of multiple sequence alignment with SP-score". J Comput Biol. 8 (6): 615–23. CiteSeerX 10.1.1.31.6382. doi:10.1089/106652701753307511. PMID 11747615.
  7. ^ Elias, Isaac (2006). "Settling the intractability of multiple alignment". J Comput Biol. 13 (7): 1323–1339. CiteSeerX 10.1.1.6.256. doi:10.1089/cmb.2006.13.1323. PMID 17037961.
  8. ^ Carrillo H, Lipman DJ (1988). "The Multiple Sequence Alignment Problem in Biology". SIAM Journal on Applied Mathematics. 48 (5): 1073–1082. doi:10.1137/0148063.
  9. ^ Lipman DJ, Altschul SF, Kececioglu JD (1989). "A tool for multiple sequence alignment". Proc Natl Acad Sci U S A. 86 (12): 4412–4415. Bibcode:1989PNAS...86.4412L. doi:10.1073/pnas.86.12.4412. PMC 287279. PMID 2734293.
  10. ^ "Genetic analysis software". National Center for Biotechnology Information. Retrieved March 3, 2010.
  11. ^ Feng DF, Doolittle RF (1987). "Progressive sequence alignment as a prerequisitetto correct phylogenetic trees". J Mol Evol. 25 (4): 351–360. Bibcode:1987JMolE..25..351F. doi:10.1007/BF02603120. PMID 3118049. S2CID 6345432.
  12. ^ a b c d e f g h DM. (2004)을 장착하십시오.생물정보학:시퀀스 및 게놈 분석 2차 개정판Cold Spring Harbor Laboratory Press: Cold Spring Harbor, NY.
  13. ^ Higgins DG, Sharp PM (1988). "CLUSTAL: a package for performing multiple sequence alignment on a microcomputer". Gene. 73 (1): 237–244. doi:10.1016/0378-1119(88)90330-7. PMID 3243435.
  14. ^ Thompson JD, Higgins DG, Gibson TJ (November 1994). "CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice". Nucleic Acids Res. 22 (22): 4673–80. doi:10.1093/nar/22.22.4673. PMC 308517. PMID 7984417.
  15. ^ "EMBL-EBI-ClustalW2-Multiple Sequence Alignment". CLUSTALW2.
  16. ^ Notredame C, Higgins DG, Heringa J (September 2000). "T-Coffee: A novel method for fast and accurate multiple sequence alignment". J. Mol. Biol. 302 (1): 205–17. doi:10.1006/jmbi.2000.4042. PMID 10964570.
  17. ^ Sze SH, Lu Y, Yang Q (2006). "A polynomial time solvable formulation of multiple sequence alignment". J Comput Biol. 13 (2): 309–319. doi:10.1089/cmb.2006.13.309. PMID 16597242.
  18. ^ Hirosawa M, Totoki Y, Hoshida M, Ishikawa M (1995). "Comprehensive study on iterative algorithms of multiple sequence alignment". Comput Appl Biosci. 11 (1): 13–18. doi:10.1093/bioinformatics/11.1.13. PMID 7796270.
  19. ^ Gotoh O (1996). "Significant improvement in accuracy of multiple protein sequence alignments by iterative refinement as assessed by reference to structural alignments". J Mol Biol. 264 (4): 823–38. doi:10.1006/jmbi.1996.0679. PMID 8980688.
  20. ^ a b Brudno M, Chapman M, Göttgens B, Batzoglou S, Morgenstern B (December 2003). "Fast and sensitive multiple alignment of large genomic sequences". BMC Bioinformatics. 4: 66. doi:10.1186/1471-2105-4-66. PMC 521198. PMID 14693042.
  21. ^ Edgar RC (2004). "MUSCLE: multiple sequence alignment with high accuracy and high throughput". Nucleic Acids Research. 32 (5): 1792–97. doi:10.1093/nar/gkh340. PMC 390337. PMID 15034147.
  22. ^ Collingridge PW, Kelly S (2012). "MergeAlign: improving multiple sequence alignment performance by dynamic reconstruction of consensus multiple sequence alignments". BMC Bioinformatics. 13 (117): 117. doi:10.1186/1471-2105-13-117. PMC 3413523. PMID 22646090.
  23. ^ Hughey R, Krogh A (1996). "Hidden Markov models for sequence analysis: extension and analysis of the basic method". CABIOS. 12 (2): 95–107. CiteSeerX 10.1.1.44.3365. doi:10.1093/bioinformatics/12.2.95. PMID 8744772.
  24. ^ Grasso C, Lee C (2004). "Combining partial order alignment and progressive multiple sequence alignment increases alignment speed and scalability to very large alignment problems". Bioinformatics. 20 (10): 1546–56. doi:10.1093/bioinformatics/bth126. PMID 14962922.
  25. ^ Hughey R, Krogh A. SAM: 시퀀스 정렬 및 모델링 소프트웨어 시스템.기술 보고서 UCSC-CRL-96-22, 캘리포니아 대학교 산타 크루즈, CA, 1996년 9월.
  26. ^ 더빈 R, 에디 S, 크로그 A, 미치슨 G. (1998년).생물학적 시퀀스 분석: 단백질과 핵산의 확률론적 모델, 캠브리지 대학 출판부, 1998.
  27. ^ Söding J (2005). "Protein homology detection by HMM-HMM comparison". Bioinformatics. 21 (7): 951–960. CiteSeerX 10.1.1.519.1257. doi:10.1093/bioinformatics/bti125. PMID 15531603.
  28. ^ Battey JN, Kopp J, Bordoli L, Read RJ, Clarke ND, Schwede T (2007). "Automated server predictions in CASP7". Proteins. 69 (Suppl 8): 68–82. doi:10.1002/prot.21761. PMID 17894354. S2CID 29879391.
  29. ^ Loytynoja, A. (2005). "An algorithm for progressive multiple alignment of sequences with insertions". Proceedings of the National Academy of Sciences. 102 (30): 10557–10562. Bibcode:2005PNAS..10210557L. doi:10.1073/pnas.0409137102. PMC 1180752. PMID 16000407.
  30. ^ Löytynoja A, Goldman N (June 2008). "Phylogeny-aware gap placement prevents errors in sequence alignment and evolutionary analysis". Science. 320 (5883): 1632–5. Bibcode:2008Sci...320.1632L. doi:10.1126/science.1158395. PMID 18566285. S2CID 5211928.
  31. ^ Löytynoja A, Vilella AJ, Goldman N (July 2012). "Accurate extension of multiple sequence alignments using a phylogeny-aware graph algorithm". Bioinformatics. 28 (13): 1684–91. doi:10.1093/bioinformatics/bts198. PMC 3381962. PMID 22531217.
  32. ^ Szalkowski AM (June 2012). "Fast and robust multiple sequence alignment with phylogeny-aware gap placement". BMC Bioinformatics. 13: 129. doi:10.1186/1471-2105-13-129. PMC 3495709. PMID 22694311.
  33. ^ Henikoff S, Henikoff JG (December 1991). "Automated assembly of protein blocks for database searching". Nucleic Acids Res. 19 (23): 6565–72. doi:10.1093/nar/19.23.6565. PMC 329220. PMID 1754394.
  34. ^ Bailey TL, Elkan C (1994). "Fitting a mixture model by expectation maximization to discover motifs in biopolymers" (PDF). Proceedings of the Second International Conference on Intelligent Systems for Molecular Biology. Menlo Park, California: AAAI Press. pp. 28–36.
  35. ^ Bailey TL, Gribskov M (1998). "Combining evidence using p-values: application to sequence homology searches". Bioinformatics. 14 (1): 48–54. doi:10.1093/bioinformatics/14.1.48. PMID 9520501.
  36. ^ Salama RA, Stekel DJ (November 2013). "A non-independent energy-based multiple sequence alignment improves prediction of transcription factor binding sites". Bioinformatics. 29 (21): 2699–704. doi:10.1093/bioinformatics/btt463. PMID 23990411.
  37. ^ Notredame C, Higgins DG (April 1996). "SAGA: sequence alignment by genetic algorithm". Nucleic Acids Res. 24 (8): 1515–24. doi:10.1093/nar/24.8.1515. PMC 145823. PMID 8628686.
  38. ^ Notredame C, O'Brien EA, Higgins DG (1997). "RAGA: RNA sequence alignment by genetic algorithm". Nucleic Acids Res. 25 (22): 4570–80. doi:10.1093/nar/25.22.4570. PMC 147093. PMID 9358168.
  39. ^ Kim J, Pramanik S, Chung MJ (1994). "Multiple sequence alignment using simulated annealing". Comput Appl Biosci. 10 (4): 419–26. doi:10.1093/bioinformatics/10.4.419. PMID 7804875.
  40. ^ Althaus E, Caprara A, Lenhof HP, Reinert K (2006). "A branch-and-cut algorithm for multiple sequence alignment". Mathematical Programming. 105 (2–3): 387–425. doi:10.1007/s10107-005-0659-3. S2CID 17715172.
  41. ^ D-Wave, 2017년 1월 11일 오픈 퀀텀 소프트웨어 환경 개시
  42. ^ "Manual editing and adjustment of MSAs". European Molecular Biology Laboratory. 2007. Archived from the original on September 24, 2015. Retrieved March 7, 2010.
  43. ^ Castresana J (April 2000). "Selection of conserved blocks from multiple alignments for their use in phylogenetic analysis". Mol. Biol. Evol. 17 (4): 540–52. doi:10.1093/oxfordjournals.molbev.a026334. PMID 10742046.
  44. ^ Löytynoja A, Milinkovitch MC (June 2001). "SOAP, cleaning multiple alignments from unstable blocks". Bioinformatics. 17 (6): 573–4. doi:10.1093/bioinformatics/17.6.573. PMID 11395440.
  45. ^ Poirot O, O'Toole E, Notredame C (July 2003). "Tcoffee@igs: A web server for computing, evaluating and combining multiple sequence alignments". Nucleic Acids Res. 31 (13): 3503–6. doi:10.1093/nar/gkg522. PMC 168929. PMID 12824354.
  46. ^ Chang, JM; Di Tommaso, P; Notredame, C (Jun 2014). "TCS: A New Multiple Sequence Alignment Reliability Measure to Estimate Alignment Accuracy and Improve Phylogenetic Tree Reconstruction". Molecular Biology and Evolution. 31 (6): 1625–37. doi:10.1093/molbev/msu117. PMID 24694831.
  47. ^ Chang JM, Di Tommaso P, Lefort V, Gascuel O, Notredame C (July 2015). "TCS: a web server for multiple sequence alignment evaluation and phylogenetic reconstruction". Nucleic Acids Res. 43 (W1): W3–6. doi:10.1093/nar/gkv310. PMC 4489230. PMID 25855806.
  48. ^ Bradley RK, Roberts A, Smoot M, Juvekar S, Do J, Dewey C, Holmes I, Pachter L (May 2009). "Fast statistical alignment". PLOS Comput. Biol. 5 (5): e1000392. Bibcode:2009PLSCB...5E0392B. doi:10.1371/journal.pcbi.1000392. PMC 2684580. PMID 19478997.
  49. ^ Landan G, Graur D (2008). "Local reliability measures from sets of co-optimal multiple sequence alignments". Biocomputing 2008. Pac Symp Biocomput. pp. 15–24. doi:10.1142/9789812776136_0003. ISBN 978-981-277-608-2. PMID 18229673.
  50. ^ Penn O, Privman E, Landan G, Graur D, Pupko T (August 2010). "An alignment confidence score capturing robustness to guide tree uncertainty". Mol. Biol. Evol. 27 (8): 1759–67. doi:10.1093/molbev/msq066. PMC 2908709. PMID 20207713.
  51. ^ Redelings BD, Suchard MA (June 2005). "Joint Bayesian estimation of alignment and phylogeny". Syst. Biol. 54 (3): 401–18. doi:10.1080/10635150590947041. PMID 16012107.
  52. ^ a b Budd, Aidan (10 February 2009). "Multiple sequence alignment exercises and demonstrations". European Molecular Biology Laboratory. Archived from the original on 5 March 2012. Retrieved June 30, 2010.

조사기사

외부 링크

강의 노트, 튜토리얼 및 과정