カブシュアルゴリズム

カブシュアルゴリズムは、ヴォルフガング・カブシュと梅山真治にちなんでカブシュ・梅山アルゴリズムとも呼ばれ、^[1] 2組の点のペアの間のRMSD (平均二乗偏差)を最小化する最適な回転行列を計算する手法です。コンピュータグラフィックスにおける点セットの位置合わせや、化学情報科学や生物情報科学で分子やタンパク質の構造を比較する際に役立ちます (特に、平均二乗偏差 (生物情報科学)を参照)。

このアルゴリズムは回転行列のみを計算しますが、平行移動ベクトルの計算も必要です。平行移動と回転の両方が実際に実行される場合、このアルゴリズムは部分プロクラステス重ね合わせと呼ばれることがあります(直交プロクラステス問題も参照)。

PとQ をそれぞれ 内のN 個の点を含む 2 つの集合とします。Q からPへの変換を求めます。簡単にするために、3 次元の場合 ( ) を考えます。集合PとQ はそれぞれ、次の行列に示すように、最初の行に最初の点の座標、2 番目の行に 2 番目の点の座標などを含む N × 3行列で表すことができます 。${\displaystyle \mathbb {R} ^{n}}$${\displaystyle n=3}$

$${\displaystyle {\begin{pmatrix}x_{1}&y_{1}&z_{1}\\x_{2}&y_{2}&z_{2}\\\vdots &\vdots &\vdots \\x_{N}&y_{N}&z_{N}\end{pmatrix}}}$$

このアルゴリズムは、変換、共分散行列の計算、最​​適な回転行列の 計算という 3 つのステップで動作します。

まず、両方の座標セットを変換して、その重心が座標系の原点と一致するようにする必要があります。これは、点の座標から重心の座標を減算することによって行われます。

2番目のステップは行列Hを計算することです。行列表記では、

${\displaystyle H=P^{\mathsf {T}}Q\,}$

または、加算記法を使用すると、

${\displaystyle H_{ij}=\sum _{k=1}^{N}P_{ki}Q_{kj},}$

これは、 PとQ をデータ行列として見た場合の相互共分散行列です。

行列式に基づいて 最適な回転Rを計算することが可能である。

${\displaystyle R=\left(H^{\mathsf {T}}H\right)^{\frac {1}{2}}H^{-1},}$

しかし、この式の数値解を実装することは、すべての特殊なケース（たとえば、Hに逆関数がない場合）を考慮すると複雑になります。

特異値分解(SVD) ルーチンが利用可能な場合、最適な回転Rは次の単純なアルゴリズムを使用して計算できます。

まず共分散行列HのSVDを計算します。

${\displaystyle H=U\Sigma V^{\mathsf {T}}}$

ここでUとVは直交し、は対角です。次に、直交行列に反射が含まれているかどうかを記録し、 ${\displaystyle \Sigma }$

${\displaystyle d=\det \left(UV^{\mathsf {T}}\right)=\det(U)\det(V).}$

最後に、最適な回転行列Rを次のように 計算します。

${\displaystyle R=U{\begin{pmatrix}1&0&0\\0&1&0\\0&0&d\end{pmatrix}}V^{\mathsf {T}}.}$

このR はを最小化します。ここで、 と はそれぞれQとPの行です。 ${\displaystyle \sum _{k=1}^{N}|Rq_{k}-p_{k}|}$${\displaystyle q_{k}}$${\displaystyle p_{k}}$

あるいは、最適回転行列は、四元数として直接評価することもできる。^{[2] [3] [4] [5]}この代替記述は、柔軟な分子の分子動力学軌道から剛体運動を除去する厳密な方法の開発に使用されてきた。 ^[6] 2002年には、確率分布（連続または非連続）への応用の一般化も提案された。^[7]

このアルゴリズムは3次元空間の点について説明されています。D次元への一般化はすぐに行えます。

このSVDアルゴリズムの詳細については、https://web.archive.org/web/20140225050055/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]にリンクされていましたが、これはCombinatorial Extension (CE)アルゴリズムを使用しています。) VMDはアライメントにKabschアルゴリズムを使用しています。

FoldXモデリング ツールスイートには、野生型と変異したタンパク質構造間の RMSD を測定するための Kabsch アルゴリズムが組み込まれています。

• ワバの問題
• 直交プロクルステス問題

• Kabsch, Wolfgang (1976). 「2組のベクトルを関連付ける最適な回転の解」Acta Crystallographica . A32 (5): 922. Bibcode :1976AcCrA..32..922K. doi :10.1107/S0567739476001873.
  • Kabsch, Wolfgang (1978)の訂正あり。「2 つのベクトル セットを関連付ける最適な回転の解についての考察」Acta Crystallographica。A34 ( 5): 827–828。Bibcode :1978AcCrA..34..827K。doi : 10.1107 /S0567739478001680。
• Lin, Ying-Hung、Chang, Hsun-Chang、Lin, Yaw-Ling (2004 年 12 月 15 ～ 17 日)。「3D タンパク質構造のアラインメントと比較のためのツールとアルゴリズムの研究」国際コンピュータシンポジウム。台北、台湾。
• 梅山 真司 (1991)。「2点パターン間の変換パラメータの最小二乗推定」IEEE Trans. Pattern Anal. Mach. Intell . 13 (4): 376–380. doi :10.1109/34.88573。