काब्श एल्गोरिथम: Difference between revisions
From Vigyanwiki
(Created page with "काब्श एल्गोरिथम, जिसे काब्श-उमेयामा एल्गोरिथम के रूप में भी जाना ज...") |
(text) |
||
| Line 1: | Line 1: | ||
काब्श | '''काब्श कलन विधि''', जिसे काब्श-उमेयामा कलन विधि के रूप में भी जाना जाता है, <ref>{{Cite journal |last=Lawrence |first=Jim |last2=Bernal |first2=Javier |last3=Witzgall |first3=Christoph |date=2019-10-09 |title=काब्श-उमेयामा एल्गोरिथम का एक विशुद्ध बीजगणितीय औचित्य|url=https://nvlpubs.nist.gov/nistpubs/jres/124/jres.124.028.pdf |journal=Journal of Research of the National Institute of Standards and Technology |language=en |volume=124 |pages=124028 |doi=10.6028/jres.124.028 |issn=2165-7254 |pmc=7340555 |pmid=34877177}}</ref> वोल्फगैंग काब्श और शिनजी उमेयामा के नाम पर, इष्टतम [[रोटेशन मैट्रिक्स|क्रमावर्तन आव्यूह]] की गणना करने की एक विधि है जो बिंदुओं के दो युग्मित सम्मुच्चयों के बीच [[आरएमएसडी]] (घात माध्य वर्ग विचलन) को कम करती है। यह [[ कंप्यूटर चित्रलेख |कंप्यूटर चित्रलेख]] में [[बिंदु-सेट पंजीकरण|बिंदु-सम्मुच्चय पंजीकरण]] के लिए और रसायन सूचना विज्ञान और जैव सूचना विज्ञान में आणविक और [[प्रोटीन]] संरचनाओं की तुलना करने के लिए उपयोगी है (विशेष रूप से, घात-माध्य-वर्ग विचलन (जैव सूचना विज्ञान) देखें)। | ||
कलन विधि केवल क्रमावर्तन आव्यूह की गणना करता है, लेकिन इसमें अनुवाद सदिश की गणना की भी आवश्यकता होती है। जब अनुवाद और क्रमावर्तन दोनों वास्तव में किए जाते हैं, तो कलन विधि को कभी-कभी आंशिक [[प्रोक्रस्टेस सुपरइम्पोज़िशन|प्रोक्रस्टेस अधिरोपण]] कहा जाता है ([[ऑर्थोगोनल प्रोक्रस्टेस समस्या|आयतीय प्रोक्रस्टेस समस्या]] भी देखें)। | |||
== विवरण == | == विवरण == | ||
{{mvar|P}} और {{mvar|Q}} के घूर्णन के लिए कलन विधि {{mvar|P}} में {{mvar|Q}} युग्मित बिंदुओं के दो सम्मुच्चयों से प्रारंभ होता है। बिंदुओं के प्रत्येक सम्मुच्चय को एक {{math|''N'' × 3}} [[मैट्रिक्स (गणित)|आव्यूह (गणित)]] के रूप में दर्शाया जा सकता है। पहली पंक्ति पहले बिंदु के निर्देशांक हैं, दूसरी पंक्ति दूसरे बिंदु के निर्देशांक हैं {{mvar|N}}वीं पंक्ति {{mvar|N}}वें बिंदु के निर्देशांक हैं। नीचे दिए गए आव्यूह की जाँच करें | |||
:<math>\begin{pmatrix} | :<math>\begin{pmatrix} | ||
| Line 12: | Line 12: | ||
\vdots & \vdots & \vdots \\ | \vdots & \vdots & \vdots \\ | ||
x_N & y_N & z_N \end{pmatrix}</math> | x_N & y_N & z_N \end{pmatrix}</math> | ||
कलन विधि तीन चरणों में काम करता है: एक अनुवाद, एक सहप्रसरण आव्यूह की गणना, और इष्टतम क्रमावर्तन आव्यूह की गणना। | |||
=== अनुवाद === | === अनुवाद === | ||
निर्देशांक के दोनों | निर्देशांक के दोनों सम्मुच्चयों का पहले अनुवाद किया जाना चाहिए, ताकि उनका [[केन्द्रक]] समन्वय प्रणाली की उत्पत्ति के साथ मेल खाए। यह संबंधित केन्द्रक के बिंदु निर्देशांक को घटाकर किया जाता है। | ||
=== सहप्रसरण | === सहप्रसरण आव्यूह की गणना === | ||
दूसरे चरण में एक | दूसरे चरण में एक आव्यूह {{mvar|H}} की गणना करना सम्मिलित है। आव्यूह संकेतन में, | ||
:<math> H = P^\mathsf{T}Q \, </math> | :<math> H = P^\mathsf{T}Q \, </math> | ||
| Line 24: | Line 24: | ||
:<math> H_{ij} = \sum_{k = 1}^N P_{ki} Q_{kj}, </math> | :<math> H_{ij} = \sum_{k = 1}^N P_{ki} Q_{kj}, </math> | ||
जो कि एक [[ क्रॉस-सहप्रसरण ]] | जो कि एक[[ क्रॉस-सहप्रसरण | तिर्यक्-सहप्रसरण]] आव्यूह है जब {{mvar|P}} और {{mvar|Q}} को अभिकल्पआव्यूह के रूप में देखा जाता है। | ||
=== इष्टतम | === इष्टतम क्रमावर्तन आव्यूह की गणना === | ||
इष्टतम | आव्यूह सूत्र के आधार पर इष्टतम क्रमावर्तन {{mvar|R}} की गणना करना संभव है | ||
:<math> R = \left(H^\mathsf{T} H\right)^\frac12 H^{-1} </math> | :<math> R = \left(H^\mathsf{T} H\right)^\frac12 H^{-1} </math> | ||
लेकिन इस सूत्र का संख्यात्मक समाधान लागू करना तब जटिल हो जाता है जब सभी विशेष | लेकिन इस सूत्र का संख्यात्मक समाधान लागू करना तब जटिल हो जाता है जब सभी विशेष स्तिथियों को ध्यान में रखा जाता है (उदाहरण के लिए, H के मामले में व्युत्क्रम नहीं है)। | ||
यदि एकल मूल्य अपघटन (एसवीडी) | यदि एकल मूल्य अपघटन (एसवीडी) घातीन उपलब्ध हैं, तो इष्टतम क्रमावर्तन, {{mvar|R}}, की गणना निम्नलिखित सरल कलन विधि का उपयोग करके की जा सकती है। | ||
सबसे पहले, सहप्रसरण | सबसे पहले, सहप्रसरण आव्यूह {{mvar|H}} के एसवीडी की गणना करें | ||
:<math> H = U \Sigma V^\mathsf{T} </math> | :<math> H = U \Sigma V^\mathsf{T} </math> | ||
इसके बाद, | इसके बाद, निर्धारित करें कि दाएं हाथ की समन्वय प्रणाली सुनिश्चित करने के लिए हमें अपने क्रमावर्तन आव्यूह को सही करने की आवश्यकता है या नहीं | ||
:<math> d = \mathrm{sign}\left(\det\left(V U^\mathsf{T}\right)\right) </math> | :<math> d = \mathrm{sign}\left(\det\left(V U^\mathsf{T}\right)\right) </math> | ||
अंत में, हमारे इष्टतम | अंत में, हमारे इष्टतम क्रमावर्तन आव्यूह {{mvar|R}} की गणना करें, जैसे | ||
:<math> R = V \begin{pmatrix} | :<math> R = V \begin{pmatrix} | ||
| Line 46: | Line 46: | ||
0 & 1 & 0 \\ | 0 & 1 & 0 \\ | ||
0 & 0 & d \end{pmatrix} U^\mathsf{T} </math> | 0 & 0 & d \end{pmatrix} U^\mathsf{T} </math> | ||
इष्टतम | इष्टतम क्रमावर्तन आव्यूह को चतुर्भुज के संदर्भ में भी व्यक्त किया जा सकता है। <ref>{{Cite journal|last=Horn|first=Berthold K. P.|authorlink=Berthold K.P. Horn|date=1987-04-01|title=इकाई चतुर्भुजों का उपयोग करके निरपेक्ष अभिविन्यास का बंद-रूप समाधान|journal=Journal of the Optical Society of America A|language=EN|volume=4|issue=4|pages=629|doi=10.1364/josaa.4.000629|bibcode=1987JOSAA...4..629H|issn=1520-8532|citeseerx=10.1.1.68.7320}}</ref><ref>{{Cite journal|last=Kneller|first=Gerald R.|date=1991-05-01|title=क्वाटरनियंस का उपयोग करके आणविक संरचनाओं का सुपरपोजिशन|journal=Molecular Simulation|volume=7|issue=1–2|pages=113–119|doi=10.1080/08927029108022453|issn=0892-7022}}</ref><ref name="Coutsias2004">{{cite journal |last1=Coutsias |first1=E. A. |last2=Seok |first2=C. |last3=Dill |first3=K. A. | title = आरएमएसडी की गणना करने के लिए चतुर्भुज का उपयोग करना| journal = J. Comput. Chem. | volume = 25 | issue = 15 | pages = 1849–1857 | year = 2004 | pmid = 15376254 | doi = 10.1002/jcc.20110|s2cid=18224579 }}</ref><ref name="Petitjean1999">{{cite journal | last = Petitjean | first = M. | title = मूल माध्य पर वर्ग मात्रात्मक चिरलिटी और मात्रात्मक समरूपता माप| journal = J. Math. Phys. | volume = 40 | issue = 9 | pages = 4587–4595 | year = 1999 | doi = 10.1063/1.532988| bibcode = 1999JMP....40.4587P | url = https://hal.archives-ouvertes.fr/hal-02122820/file/PMP.JMP_1999.pdf }}</ref> इस वैकल्पिक विवरण का उपयोग विभक्तिग्राही अणुओं के [[आणविक गतिशीलता]] प्रक्षेप पथ से कठोर-शरीर गतियों को हटाने के लिए एक कठोर विधि के विकास में किया गया है। <ref>{{Cite journal|date=2011-08-24|title=लचीले मैक्रोमोलेक्यूल्स के आणविक गतिशीलता प्रक्षेपवक्र से आंतरिक गति के निष्कर्षण के लिए कम से कम बाधा दृष्टिकोण|journal=J. Chem. Phys.|volume=135|issue=8|pages=084110|doi=10.1063/1.3626275|pmid=21895162|issn=0021-9606|last1=Chevrot|first1=Guillaume|last2=Calligari|first2=Paolo|last3=Hinsen|first3=Konrad|last4=Kneller|first4=Gerald R.|bibcode=2011JChPh.135h4110C}}</ref> 2002 में संभाव्यता वितरण (निरंतर या नहीं) के अनुप्रयोग के लिए एक सामान्यीकरण भी प्रस्तावित किया गया था। <ref name="Petitjean2002">{{cite journal | last = Petitjean | first = M. | title = चिरल मिश्रण| journal = J. Math. Phys. | volume = 43 | issue = 8 | pages = 4147–4157 | year = 2002 | doi = 10.1063/1.1484559| bibcode = 2002JMP....43.4147P | url = https://hal.archives-ouvertes.fr/hal-02122882/file/PMP.JMP_2002.pdf }}</ref> | ||
=== सामान्यीकरण === | === सामान्यीकरण === | ||
कलन विधि को त्रि-आयामी स्थल में बिंदुओं के लिए वर्णित किया गया था। D आयामों का सामान्यीकरण सन्निहित है। | |||
== बाहरी संबंध == | == बाहरी संबंध == | ||
| Line 71: | Line 71: | ||
* वहबा की समस्या|वहबा की समस्या | * वहबा की समस्या|वहबा की समस्या | ||
* | * आयतीय प्रोक्रस्ट्स समस्या | ||
== संदर्भ == | == संदर्भ == | ||
Revision as of 02:49, 2 August 2023
काब्श कलन विधि, जिसे काब्श-उमेयामा कलन विधि के रूप में भी जाना जाता है, [1] वोल्फगैंग काब्श और शिनजी उमेयामा के नाम पर, इष्टतम क्रमावर्तन आव्यूह की गणना करने की एक विधि है जो बिंदुओं के दो युग्मित सम्मुच्चयों के बीच आरएमएसडी (घात माध्य वर्ग विचलन) को कम करती है। यह कंप्यूटर चित्रलेख में बिंदु-सम्मुच्चय पंजीकरण के लिए और रसायन सूचना विज्ञान और जैव सूचना विज्ञान में आणविक और प्रोटीन संरचनाओं की तुलना करने के लिए उपयोगी है (विशेष रूप से, घात-माध्य-वर्ग विचलन (जैव सूचना विज्ञान) देखें)।
कलन विधि केवल क्रमावर्तन आव्यूह की गणना करता है, लेकिन इसमें अनुवाद सदिश की गणना की भी आवश्यकता होती है। जब अनुवाद और क्रमावर्तन दोनों वास्तव में किए जाते हैं, तो कलन विधि को कभी-कभी आंशिक प्रोक्रस्टेस अधिरोपण कहा जाता है (आयतीय प्रोक्रस्टेस समस्या भी देखें)।
विवरण
P और Q के घूर्णन के लिए कलन विधि P में Q युग्मित बिंदुओं के दो सम्मुच्चयों से प्रारंभ होता है। बिंदुओं के प्रत्येक सम्मुच्चय को एक N × 3 आव्यूह (गणित) के रूप में दर्शाया जा सकता है। पहली पंक्ति पहले बिंदु के निर्देशांक हैं, दूसरी पंक्ति दूसरे बिंदु के निर्देशांक हैं Nवीं पंक्ति Nवें बिंदु के निर्देशांक हैं। नीचे दिए गए आव्यूह की जाँच करें
कलन विधि तीन चरणों में काम करता है: एक अनुवाद, एक सहप्रसरण आव्यूह की गणना, और इष्टतम क्रमावर्तन आव्यूह की गणना।
अनुवाद
निर्देशांक के दोनों सम्मुच्चयों का पहले अनुवाद किया जाना चाहिए, ताकि उनका केन्द्रक समन्वय प्रणाली की उत्पत्ति के साथ मेल खाए। यह संबंधित केन्द्रक के बिंदु निर्देशांक को घटाकर किया जाता है।
सहप्रसरण आव्यूह की गणना
दूसरे चरण में एक आव्यूह H की गणना करना सम्मिलित है। आव्यूह संकेतन में,
या, योग संकेतन का उपयोग करते हुए,
जो कि एक तिर्यक्-सहप्रसरण आव्यूह है जब P और Q को अभिकल्पआव्यूह के रूप में देखा जाता है।
इष्टतम क्रमावर्तन आव्यूह की गणना
आव्यूह सूत्र के आधार पर इष्टतम क्रमावर्तन 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.
