काब्श एल्गोरिथम

काब्श कलन विधि, जिसे काब्श-उमेयामा कलन विधि के रूप में भी जाना जाता है, वोल्फगैंग काब्श और शिनजी उमेयामा के नाम पर, इष्टतम क्रमावर्तन आव्यूह की गणना करने की एक विधि है जो बिंदुओं के दो युग्मित सम्मुच्चयों के बीच आरएमएसडी (घात माध्य वर्ग विचलन) को कम करती है। यह कंप्यूटर चित्रलेख में बिंदु-सम्मुच्चय पंजीकरण के लिए और रसायन सूचना विज्ञान और जैव सूचना विज्ञान में आणविक और प्रोटीन संरचनाओं की तुलना करने के लिए उपयोगी है (विशेष रूप से, घात-माध्य-वर्ग विचलन (जैव सूचना विज्ञान) देखें)।

कलन विधि केवल क्रमावर्तन आव्यूह की गणना करता है, लेकिन इसमें अनुवाद सदिश की गणना की भी आवश्यकता होती है। जब अनुवाद और क्रमावर्तन दोनों वास्तव में किए जाते हैं, तो कलन विधि को कभी-कभी आंशिक प्रोक्रस्टेस अधिरोपण कहा जाता है (आयतीय प्रोक्रस्टेस समस्या भी देखें)।

विवरण

P और Q के घूर्णन के लिए कलन विधि P में Q युग्मित बिंदुओं के दो सम्मुच्चयों से प्रारंभ होता है। बिंदुओं के प्रत्येक सम्मुच्चय को एक N × 3 आव्यूह (गणित) के रूप में दर्शाया जा सकता है। पहली पंक्ति पहले बिंदु के निर्देशांक हैं, दूसरी पंक्ति दूसरे बिंदु के निर्देशांक हैं Nवीं पंक्ति Nवें बिंदु के निर्देशांक हैं। नीचे दिए गए आव्यूह की जाँच करें

${\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}}$

कलन विधि तीन चरणों में काम करता है: एक अनुवाद, एक सहप्रसरण आव्यूह की गणना, और इष्टतम क्रमावर्तन आव्यूह की गणना।

अनुवाद

निर्देशांक के दोनों सम्मुच्चयों का पहले अनुवाद किया जाना चाहिए, ताकि उनका केन्द्रक समन्वय प्रणाली की उत्पत्ति के साथ मेल खाए। यह संबंधित केन्द्रक के बिंदु निर्देशांक को घटाकर किया जाता है।

सहप्रसरण आव्यूह की गणना

दूसरे चरण में एक आव्यूह H की गणना करना सम्मिलित है। आव्यूह संकेतन में,

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

या, योग संकेतन का उपयोग करते हुए,

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

जो कि एक तिर्यक्-सहप्रसरण आव्यूह है जब P और Q को अभिकल्पआव्यूह के रूप में देखा जाता है।

इष्टतम क्रमावर्तन आव्यूह की गणना

आव्यूह सूत्र के आधार पर इष्टतम क्रमावर्तन R की गणना करना संभव है

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

लेकिन इस सूत्र का संख्यात्मक समाधान लागू करना तब जटिल हो जाता है जब सभी विशेष स्तिथियों को ध्यान में रखा जाता है (उदाहरण के लिए, H के मामले में व्युत्क्रम नहीं है)।

यदि एकल मूल्य अपघटन (एसवीडी) घातीन उपलब्ध हैं, तो इष्टतम क्रमावर्तन, R, की गणना निम्नलिखित सरल कलन विधि का उपयोग करके की जा सकती है।

सबसे पहले, सहप्रसरण आव्यूह H के एसवीडी की गणना करें

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

इसके बाद, निर्धारित करें कि दाएं हाथ की समन्वय प्रणाली सुनिश्चित करने के लिए हमें अपने क्रमावर्तन आव्यूह को सही करने की आवश्यकता है या नहीं

$d=\mathrm {sign} \left(\det \left(VU^{\mathsf {T}}\right)\right)$

अंत में, हमारे इष्टतम क्रमावर्तन आव्यूह R की गणना करें, जैसे

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

इष्टतम क्रमावर्तन आव्यूह को चतुर्भुज के संदर्भ में भी व्यक्त किया जा सकता है। इस वैकल्पिक विवरण का उपयोग विभक्तिग्राही अणुओं के आणविक गतिशीलता प्रक्षेप पथ से कठोर-शरीर गतियों को हटाने के लिए एक कठोर विधि के विकास में किया गया है। 2002 में संभाव्यता वितरण (निरंतर या नहीं) के अनुप्रयोग के लिए एक सामान्यीकरण भी प्रस्तावित किया गया था।

सामान्यीकरण

कलन विधि को त्रि-आयामी स्थल में बिंदुओं के लिए वर्णित किया गया था। D आयामों का सामान्यीकरण सन्निहित है।

बाहरी संबंध

This SVD algorithm is described in more detail at http://cnx.org/content/m11608/latest/

A Matlab function is available at http://www.mathworks.com/matlabcentral/fileexchange/25746-kabsch-algorithm

A C++ implementation (and unit test) using Eigen

A Python script is available at https://github.com/charnley/rmsd. Another implementation can be found in SciPy.

A free PyMol plugin easily implementing Kabsch is [1]. (This previously linked to CEalign [2], but this uses the Combinatorial Extension (CE) algorithm.) VMD uses the Kabsch algorithm for its alignment.

The FoldX modeling toolsuite incorporates the Kabsch algorithm to measure RMSD between Wild Type and Mutated protein structures.

यह भी देखें

• वहबा की समस्या|वहबा की समस्या
• आयतीय प्रोक्रस्ट्स समस्या

संदर्भ

• 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.
  • With a correction in Kabsch, Wolfgang (1978). "A discussion of the solution for the best rotation to relate two sets of vectors". Acta Crystallographica. A34 (5): 827–828. Bibcode:1978AcCrA..34..827K. doi:10.1107/S0567739478001680.
• 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.