काब्श एल्गोरिथम
काब्श एल्गोरिथम, जिसे काब्श-उमेयामा एल्गोरिथम के रूप में भी जाना जाता है,[1] वोल्फगैंग काब्श और शिनजी उमेयामा के नाम पर, इष्टतम रोटेशन मैट्रिक्स की गणना करने की एक विधि है जो बिंदुओं के दो युग्मित सेटों के बीच आरएमएसडी (रूट माध्य वर्ग विचलन) को कम करती है। यह कंप्यूटर चित्रलेख में बिंदु-सेट पंजीकरण के लिए और रसायन सूचना विज्ञान और जैव सूचना विज्ञान में आणविक और प्रोटीन संरचनाओं की तुलना करने के लिए उपयोगी है (विशेष रूप से, रूट-माध्य-वर्ग विचलन (जैव सूचना विज्ञान) देखें)।
एल्गोरिदम केवल रोटेशन मैट्रिक्स की गणना करता है, लेकिन इसमें अनुवाद वेक्टर की गणना की भी आवश्यकता होती है। जब अनुवाद और रोटेशन दोनों वास्तव में किए जाते हैं, तो एल्गोरिदम को कभी-कभी आंशिक प्रोक्रस्टेस सुपरइम्पोज़िशन कहा जाता है (ऑर्थोगोनल प्रोक्रस्टेस समस्या भी देखें)।
विवरण
के घूर्णन के लिए एल्गोरिथ्म P में Q युग्मित बिंदुओं के दो सेटों से प्रारंभ होता है, P और Q. बिंदुओं के प्रत्येक सेट को एक के रूप में दर्शाया जा सकता है N × 3 मैट्रिक्स (गणित)। पहली पंक्ति पहले बिंदु के निर्देशांक हैं, दूसरी पंक्ति दूसरे बिंदु के निर्देशांक हैं Nवीं पंक्ति के निर्देशांक हैं Nवाँ बिंदु. नीचे दिए गए मैट्रिक्स की जाँच करें
एल्गोरिदम तीन चरणों में काम करता है: एक अनुवाद, एक सहप्रसरण मैट्रिक्स की गणना, और इष्टतम रोटेशन मैट्रिक्स की गणना।
अनुवाद
निर्देशांक के दोनों सेटों का पहले अनुवाद किया जाना चाहिए, ताकि उनका केन्द्रक समन्वय प्रणाली की उत्पत्ति के साथ मेल खाए। यह संबंधित केन्द्रक के बिंदु निर्देशांक को घटाकर किया जाता है।
सहप्रसरण मैट्रिक्स की गणना
दूसरे चरण में एक मैट्रिक्स की गणना करना शामिल है H. मैट्रिक्स संकेतन में,
या, योग संकेतन का उपयोग करते हुए,
जो कि एक क्रॉस-सहप्रसरण |क्रॉस-कोवेरिएंस मैट्रिक्स है P और Q को design_matrix के रूप में देखा जाता है।
इष्टतम रोटेशन मैट्रिक्स की गणना
इष्टतम रोटेशन की गणना करना संभव है Rमैट्रिक्स सूत्र के आधार पर
लेकिन इस सूत्र का संख्यात्मक समाधान लागू करना तब जटिल हो जाता है जब सभी विशेष मामलों को ध्यान में रखा जाता है (उदाहरण के लिए, का मामला)। H व्युत्क्रम नहीं होना)।
यदि एकल मूल्य अपघटन (एसवीडी) रूटीन उपलब्ध हैं, तो इष्टतम रोटेशन, R, की गणना निम्नलिखित सरल एल्गोरिदम का उपयोग करके की जा सकती है।
सबसे पहले, सहप्रसरण मैट्रिक्स के एसवीडी की गणना करें H.
इसके बाद, तय करें कि दाएं हाथ की समन्वय प्रणाली सुनिश्चित करने के लिए हमें अपने रोटेशन मैट्रिक्स को सही करने की आवश्यकता है या नहीं
अंत में, हमारे इष्टतम रोटेशन मैट्रिक्स की गणना करें, R, जैसा
इष्टतम रोटेशन मैट्रिक्स को चतुर्भुज के संदर्भ में भी व्यक्त किया जा सकता है।[2][3][4][5] इस वैकल्पिक विवरण का उपयोग लचीले अणुओं के आणविक गतिशीलता प्रक्षेप पथ से कठोर-शरीर गतियों को हटाने के लिए एक कठोर विधि के विकास में किया गया है।[6] 2002 में संभाव्यता वितरण (निरंतर या नहीं) के अनुप्रयोग के लिए एक सामान्यीकरण भी प्रस्तावित किया गया था।[7]
सामान्यीकरण
एल्गोरिथ्म को त्रि-आयामी अंतरिक्ष में बिंदुओं के लिए वर्णित किया गया था। को सामान्यीकरण 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.
यह भी देखें
- वहबा की समस्या|वहबा की समस्या
- ऑर्थोगोनल प्रोक्रस्ट्स समस्या
संदर्भ
- ↑ Lawrence, Jim; Bernal, Javier; Witzgall, Christoph (2019-10-09). "काब्श-उमेयामा एल्गोरिथम का एक विशुद्ध बीजगणितीय औचित्य" (PDF). Journal of Research of the National Institute of Standards and Technology (in English). 124: 124028. doi:10.6028/jres.124.028. ISSN 2165-7254. PMC 7340555. PMID 34877177.
- ↑ Horn, Berthold K. P. (1987-04-01). "इकाई चतुर्भुजों का उपयोग करके निरपेक्ष अभिविन्यास का बंद-रूप समाधान". Journal of the Optical Society of America A (in English). 4 (4): 629. Bibcode:1987JOSAA...4..629H. CiteSeerX 10.1.1.68.7320. doi:10.1364/josaa.4.000629. ISSN 1520-8532.
- ↑ Kneller, Gerald R. (1991-05-01). "क्वाटरनियंस का उपयोग करके आणविक संरचनाओं का सुपरपोजिशन". Molecular Simulation. 7 (1–2): 113–119. doi:10.1080/08927029108022453. ISSN 0892-7022.
- ↑ Coutsias, E. A.; Seok, C.; Dill, K. A. (2004). "आरएमएसडी की गणना करने के लिए चतुर्भुज का उपयोग करना". J. Comput. Chem. 25 (15): 1849–1857. doi:10.1002/jcc.20110. PMID 15376254. S2CID 18224579.
- ↑ Petitjean, M. (1999). "मूल माध्य पर वर्ग मात्रात्मक चिरलिटी और मात्रात्मक समरूपता माप" (PDF). J. Math. Phys. 40 (9): 4587–4595. Bibcode:1999JMP....40.4587P. doi:10.1063/1.532988.
- ↑ Chevrot, Guillaume; Calligari, Paolo; Hinsen, Konrad; Kneller, Gerald R. (2011-08-24). "लचीले मैक्रोमोलेक्यूल्स के आणविक गतिशीलता प्रक्षेपवक्र से आंतरिक गति के निष्कर्षण के लिए कम से कम बाधा दृष्टिकोण". J. Chem. Phys. 135 (8): 084110. Bibcode:2011JChPh.135h4110C. doi:10.1063/1.3626275. ISSN 0021-9606. PMID 21895162.
- ↑ Petitjean, M. (2002). "चिरल मिश्रण" (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.
- 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.
