캅슈 알고리즘

Kabsch algorithm

볼프강 카브치의 이름을 딴 카브치 알고리즘은 쌍을 이룬 두 점 집합 사이의 RMSD(루트 평균 제곱 편차)를 최소화하는 최적 회전 행렬을 계산하는 방법이다.분자구조를 비교하는 것은 그래픽, 체민포매틱스, 그리고 단백질 구조를 비교하는 생물정보학에도 유용하다(특히, 뿌리-평균-제곱 편차(생물정보학) 참조).

알고리즘은 회전 행렬만 계산하지만, 변환 벡터 계산도 필요하다.번역과 회전이 모두 실제로 수행되면 알고리즘을 부분 Procrustes supposition이라고 부르기도 한다(직교적 Procrustes 문제 참조).

설명

P를 Q로 회전하기 위한 알고리즘은 P와 Q라는 두 개의 쌍을 이룬 점 세트로 시작한다.각 점 세트는 N × 3 행렬로 나타낼 수 있다.첫 번째 행은 첫 번째 점의 좌표, 두 번째 행은 두 번째 점의 좌표, N번째 행은 N번째 점의 좌표다.

알고리즘은 세 단계로 동작한다: 번역, 공분산 행렬의 계산, 그리고 최적 회전 행렬의 계산.

번역

두 좌표 세트는 모두 좌표계의 원점과 일치하도록 먼저 번역해야 한다.이는 각 중심점의 점 좌표에서 차감함으로써 이루어진다.

공분산 행렬의 계산

두 번째 단계는 행렬 H를 계산하는 것으로 구성된다.행렬 표기법에서,

또는, 합계 표기법을 사용하여,

P와 Q를 데이터 행렬로 볼 때 교차 공분산 행렬이다.

최적 회전 행렬의 계산

행렬식을 바탕으로 최적 회전 R을 계산할 수 있다.

그러나 이 공식에 대한 수치적 해결책의 구현은 모든 특별한 경우를 설명할 때 복잡해진다(예: H가 역치를 가지지 않는 경우).

단수 값 분해(SVD) 루틴을 사용할 수 있는 경우 다음과 같은 간단한 알고리즘을 사용하여 최적 회전 R을 계산할 수 있다.

먼저 공분산 행렬 H의 SVD를 계산한다.

다음으로, 오른손 좌표계를 보장하기 위해 회전 행렬을 수정할 필요가 있는지 여부를 결정하십시오.

마지막으로 최적 회전 행렬인 R을 다음과 같이 계산하십시오.

최적 회전 행렬은 쿼터니온 단위로도 표현할 수 있다.[1][2][3][4]이러한 대체 설명은 최근 유연한 분자의 분자역학 궤적에서 강체-신체 운동을 제거하기 위한 엄격한 방법의 개발에 사용되었다.[5]2002년에는 확률 분포에 대한 적용 일반화(연속성 여부를 불문함)도 제안되었다.[6]

일반화

알고리즘은 3차원 공간의 포인트에 대해 설명되었다.D 치수에 대한 일반화는 즉각적이다.

외부 링크

이 SVD 알고리즘은 http://cnx.org/content/m11608/latest/에서 더 자세히 설명된다.

Matlab 기능은 http://www.mathworks.com/matlabcentral/fileexchange/25746-kabsch-algorithm에서 이용할 수 있다.

Eigen을 사용한 C++ 구현(및 단위 테스트)

Python 스크립트는 https://github.com/charnley/rmsd에서 이용할 수 있다.또 다른 구현은 SciPy에서 찾을 수 있다.

Kabsch를 쉽게 구현하는 무료 PyMol 플러그인은 [1]이다.(이것은 이전에 CEalign[2]에 연결되었지만, 이것은 CE 알고리즘을 사용한다.) VMD는 정렬을 위해 Kabsch 알고리즘을 사용한다.

FoldX 모델링 툴수이트는 와일드 타입과 돌연변이 단백질 구조 사이의 RMSD를 측정하기 위해 Kabsch 알고리즘을 통합했다.

참고 항목

참조

  1. ^ Horn, Berthold K. P. (1987-04-01). "Closed-form solution of absolute orientation using unit quaternions". Journal of the Optical Society of America A. 4 (4): 629. Bibcode:1987JOSAA...4..629H. CiteSeerX 10.1.1.68.7320. doi:10.1364/josaa.4.000629. ISSN 1520-8532.
  2. ^ Kneller, Gerald R. (1991-05-01). "Superposition of Molecular Structures using Quaternions". Molecular Simulation. 7 (1–2): 113–119. doi:10.1080/08927029108022453. ISSN 0892-7022.
  3. ^ Coutsias, E. A.; Seok, C.; Dill, K. A. (2004). "Using quaternions to calculate RMSD". J. Comput. Chem. 25 (15): 1849–1857. doi:10.1002/jcc.20110. PMID 15376254. S2CID 18224579.
  4. ^ Petitjean, M. (1999). "On the root mean square quantitative chirality and quantitative symmetry measures" (PDF). J. Math. Phys. 40 (9): 4587–4595. Bibcode:1999JMP....40.4587P. doi:10.1063/1.532988.
  5. ^ Chevrot, Guillaume; Calligari, Paolo; Hinsen, Konrad; Kneller, Gerald R. (2011-08-24). "Least constraint approach to the extraction of internal motions from molecular dynamics trajectories of flexible macromolecules". J. Chem. Phys. 135 (8): 084110. Bibcode:2011JChPh.135h4110C. doi:10.1063/1.3626275. ISSN 0021-9606. PMID 21895162.
  6. ^ Petitjean, M. (2002). "Chiral mixtures" (PDF). J. Math. Phys. 43 (8): 4147–4157. Bibcode:2002JMP....43.4147P. doi:10.1063/1.1484559.
  • Kabsch, Wolfgang (1976). "A solution for the best rotation to relate two sets of vectors". Acta Crystallographica. A32 (5): 922. Bibcode:1976AcCrA..32..922K. doi:10.1107/S0567739476001873.
    • 수정 내용 포함
  • Lin, Ying-Hung; Chang, Hsun-Chang; Lin, Yaw-Ling (December 15–17, 2004). A Study on Tools and Algorithms for 3-D Protein Structures Alignment and Comparison. International Computer Symposium. Taipei, Taiwan.
  • Umeyama, Shinji (1991). "Least-Squares Estimation of Transformation Parameters Between Two Point Patterns". IEEE Trans. Pattern Anal. Mach. Intell. 13 (4): 376–380. doi:10.1109/34.88573.