신속한 통계 조정
Fast statistical alignment| 개발자 | 로버트 브래들리(UC 버클리), 콜린 듀이(UW 매디슨), 리오르 파처(UC 버클리) |
|---|---|
| 안정된 릴리스 | 1.5.2 |
| 운영 체제 | UNIX, Linux, Mac |
| 유형 | 바이오 인포매틱스 툴 |
| 라이선스 | 오픈 소스 |
FSA는 많은 단백질이나 RNA 또는 긴 게놈 DNA 서열을 정렬하기 위한 다중 배열 프로그램입니다.MUSCLE 및 MAFFT와 함께 FSA는 수백 또는 수천 개의 시퀀스로 구성된 데이터 세트를 정렬할 수 있는 몇 안 되는 시퀀스 정렬 프로그램 중 하나입니다.FSA는 다른 최적화 기준을 사용하여 이러한 다른 프로그램보다 더 확실하게 비호몰로지 시퀀스를 식별할 수 있습니다.단, 이 정확도는 속도 저하로 인해 발생합니다.
FSA는 현재 새로운 웜 게놈 배열 분석, 파리 생체내 전사 인자 결합 분석 등의 프로젝트에 사용되고 있다.
입력/출력
이 프로그램은 FASTA 형식의 시퀀스를 수신하고 FASTA 형식 또는 스톡홀름 형식으로 정렬을 출력합니다.
알고리즘.
입력 시퀀스의 정렬 알고리즘에는 4개의 핵심 구성요소가 있습니다.
사후 확률을 생성하기 위한 쌍 숨겨진 마르코프 모델
알고리즘은 먼저 정렬되는 시퀀스 풀에서 임의의 두 랜덤 시퀀스 의 정렬 Y )\ Y의 후방 확률을 결정하는 것으로 시작합니다.각 열의 후방 확률은 시퀀스 쌍 간의 정렬 확률 예측을 보강하고 신뢰할 수 없이 정렬할 수 있는 열을 필터링합니다.또한 이러한 확률을 통해 시퀀스 쌍 간의 호몰로지를 예측하고 추정할 수 있습니다.표준 5-상태 쌍 은닉 마르코프 모델(쌍 HMM)은 임의의 2개의 입력 시퀀스에 대한 정렬의 사후 확률을 결정하기 위해 사용된다.쌍 HMM 모델은 두 세트의 삭제(D) 및 삽입(I) 상태를 사용하여 정렬된 두 시퀀스 간의 기호 삭제 및 삽입을 고려하지만, 정확도 손실 없이 세 가지 상태를 가질 수도 있습니다.
후방 확률을 정렬되는 시퀀스의 양에서 두 쌍의 사후 확률 분포를 결정하는 데 필요한 쌍별 비교의 수는 계산 비용이 많이 들고 2차이기 때문에, 무작위 그래프의 에르도-레니 이론에서 영감을 받은 무작위 접근법을 사용함으로써 감소한다.이를 통해 데이터셋의 런타임과 여러 정렬을 실행하는 데 드는 계산 비용을 크게 절감됩니다.
확률의 결합
시퀀스 쌍의 각 열에 대한 사후 확률은 가장 가파른 알고리즘을 사용하는 가중 함수를 사용하여 정렬됩니다.
시퀀스 어닐링
다중 시퀀스 정렬 알고리즘을 실행하는 대부분의 기존 프로그램은 프로세스가 "null alignment"(시퀀스가 정렬되지 않은 상태)로 시작하는 프로그레시브 얼라인먼트를 기반으로 합니다.그런 다음 시퀀스 풀은 쌍별 비교 또는 한 쌍의 부분 정렬을 통해 정렬됩니다.이 프로세스에서는 여러 시퀀스 정렬이 시작 시 정렬된 시퀀스에 따라 크게 달라질 수 있으므로 정렬에 문제가 발생할 수 있습니다.MSA를 수정할 수 있는 이전에 정렬된 시퀀스의 재정렬은 없습니다.
FSA는 시퀀스 어닐링 기술을 사용하여 이 문제를 해결합니다.정렬된 후방 확률은 시퀀스 어닐링 기법과 함께 다중 정렬을 생성하기 위해 사용됩니다.이 기술은 두 시퀀스 간의 정렬을 찾아 실제까지의 예상 거리를 최소화합니다.이 경우, 두 시퀀스 사이의 거리는 한 시퀀스의 문자가 두 번째 시퀀스의 같은 컬럼에 있는 문자와 상동하지 않는 열의 수입니다.
시퀀스 어닐링 기법은 진실에 대한 최소 예상 거리로 정렬을 결정함으로써 반대로 최대 예상 정확도로 정렬을 찾습니다.정렬의 정확도는 "참" 정렬을 기준으로 하여 결정되며 시퀀스가 상동하는 열의 비율을 나타냅니다.그런 다음 이 정확도는 정렬되지 않은 시퀀스(늘 정렬)에서 시작하여 정렬의 정확도 증가에 따라 서로 다른 열의 문자를 정렬하는 목적 함수로 사용됩니다.
정렬 순서
FSA는 인델과 치환을 엄격하게 고려하는 대신 열 내에서 호몰로지에 따라 여러 시퀀스를 정렬합니다.따라서 FSA는 양쪽 정렬의 시퀀스를 따라 모든 위치에 대해 호몰로지에 대한 동일한 진술을 할 수 있는 경우 정렬이 동등하다고 간주합니다.예를 들어 쌍별 비교를 고려할 때, 2개의 정렬에서 특정 위치에 갭이 있는 경우, 비교되는 2개의 시퀀스가 해당 위치에서 상동하지 않는다고 할 수 있다.이로 인해 갭 오픈 이벤트가 다를 수 있지만 동등하다고 간주될 수 있는 정렬이 발생할 수 있습니다.따라서 FSA는 '틈새 개구부'가 최소가 되는 얼라인먼트를 출력한다.
병렬화
지나치게 큰 데이터셋을 처리하기 위해 FSA는 필요한 모든 쌍별 비교 및 정렬 작업을 서로 다른 프로세서로 분할할 수 있습니다.이것은, 사용 가능한 각 프로세서에 대해서 쌍으로 비교한 「고정 사이즈의 청킹」전략을 사용해 처리됩니다.따라서 각 프로세서는 수집된 데이터를 시퀀스 어닐링을 위해 단일 프로세서에 Marge하기 전에 쌍별 비교 청크로 사후 확률 계산을 실행할 수 있다.
시각화
FSA에서 다중 시퀀스 정렬 결과는 FSA 자체 GUI 아래에 표시할 수 있습니다.GUI는 얼라인먼트 자체의 문자 열에 여러 얼라인먼트 품질 측정값을 표시 및 색칠할 수 있습니다.FSA 모델에 따라 관측할 수 있고 대략적인 5가지 척도는 정확도, 민감도, 확실도, 특이성 및 일관성을 포함한다.
다른 얼라인먼트 프로그램과의 비교
FSA는 단백질에 대한 다중 정렬 데이터베이스에 대해 벤치마킹되었다(SABmark 1.65 및 BAliB).ASE 3), RNA(BRALIBase 2.1 및 Consanmix80) 및 DNA 염기서열.이러한 벤치마크는 ClusteralW, MAFFT, MUSCLE, T-Coffee 등과 같은 다른 일반적인 얼라인먼트 프로그램과 함께 실시되었습니다.전반적으로 FSA의 요약 및 연구논문이 검토용으로 접수되었을 때, FSA는 MAFFT 및 ProbConsRNA와 같은 고성능 프로그램과 동등한 정확성과 양의 예측값에서 대부분의 얼라인먼트 프로그램을 능가했다.런타임 비교는 또한 16S 리보솜 시퀀스를 정렬하기 위한 타이밍을 비교하여 수행되었다.MAFFT는 다른 얼라인먼트 프로그램보다 빠르게 얼라인먼트를 수행했지만 MUSCLE과 FSA(3-상태 HMM을 사용하고 반복 미세화가 비활성화된)는 다음으로 빠른 프로그램이었다.
레퍼런스
Bradley RK, Roberts A, Smoot M, Juvekar S, Do J, Dewey C, Holmes I, Pachter L (2009). "Fast Statistical Alignment". PLOS Computational Biology. 5 (5): e1000392. Bibcode:2009PLSCB...5E0392B. doi:10.1371/journal.pcbi.1000392. PMC 2684580. PMID 19478997.
Schwartz AS, Patchter L(2007) 시퀀스 어닐링에 의한 다중 얼라인먼트.생체정보학 23: e24-9.
에디 SR숨겨진 마르코프 모델을 사용한 다중 정렬.Proc Int Conf Intel Syst Mol Biol. 1995; 3:114-20.PMID: 7584426
