काब्श एल्गोरिथम: Difference between revisions

From Vigyanwiki
No edit summary
 
(One intermediate revision by one other user not shown)
Line 80: Line 80:
* {{cite conference|last1=Lin|first1=Ying-Hung|last2=Chang|first2=Hsun-Chang|last3=Lin|first3=Yaw-Ling|date=December 15–17, 2004|title=A Study on Tools and Algorithms for 3-D Protein Structures Alignment and Comparison|conference=International Computer Symposium|location=Taipei, Taiwan}}
* {{cite conference|last1=Lin|first1=Ying-Hung|last2=Chang|first2=Hsun-Chang|last3=Lin|first3=Yaw-Ling|date=December 15–17, 2004|title=A Study on Tools and Algorithms for 3-D Protein Structures Alignment and Comparison|conference=International Computer Symposium|location=Taipei, Taiwan}}
* {{cite journal|last=Umeyama|first=Shinji|date=1991|title=Least-Squares Estimation of Transformation Parameters Between Two Point Patterns|journal=IEEE Trans. Pattern Anal. Mach. Intell.|volume=13|issue=4|page=376–380|doi=10.1109/34.88573}}
* {{cite journal|last=Umeyama|first=Shinji|date=1991|title=Least-Squares Estimation of Transformation Parameters Between Two Point Patterns|journal=IEEE Trans. Pattern Anal. Mach. Intell.|volume=13|issue=4|page=376–380|doi=10.1109/34.88573}}
[[Category: जैव सूचना विज्ञान एल्गोरिदम]]


 
[[Category:CS1 English-language sources (en)]]
 
[[Category: Machine Translated Page]]
[[Category:Created On 24/07/2023]]
[[Category:Created On 24/07/2023]]
[[Category:Vigyan Ready]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:जैव सूचना विज्ञान एल्गोरिदम]]

Latest revision as of 11:40, 12 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.


यह भी देखें

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

संदर्भ

  1. 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.
  2. 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.
  3. Kneller, Gerald R. (1991-05-01). "क्वाटरनियंस का उपयोग करके आणविक संरचनाओं का सुपरपोजिशन". Molecular Simulation. 7 (1–2): 113–119. doi:10.1080/08927029108022453. ISSN 0892-7022.
  4. 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.
  5. Petitjean, M. (1999). "मूल माध्य पर वर्ग मात्रात्मक चिरलिटी और मात्रात्मक समरूपता माप" (PDF). J. Math. Phys. 40 (9): 4587–4595. Bibcode:1999JMP....40.4587P. doi:10.1063/1.532988.
  6. 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.
  7. Petitjean, M. (2002). "चिरल मिश्रण" (PDF). J. Math. Phys. 43 (8): 4147–4157. Bibcode:2002JMP....43.4147P. doi:10.1063/1.1484559.