خوارزمية كابش

الموسوعة الحرة

خوارزمية كابش ، المعروفة أيضًا باسم خوارزمية كابش-أومياما ، [ 1 ] نسبةً إلى فولفغانغ كابش وشينجي أومياما، هي طريقة لحساب مصفوفة الدوران المثلى التي تُقلل من متوسط ​​الانحراف التربيعي الجذري ( RMSD ) بين مجموعتين من النقاط. وهي مفيدة لتسجيل مجموعات النقاط في رسومات الحاسوب ، وفي المعلوماتية الكيميائية والمعلوماتية الحيوية لمقارنة البنى الجزيئية والبروتينية ( انظر على وجه الخصوص: متوسط ​​الانحراف التربيعي الجذري (المعلوماتية الحيوية) ).

لا تحسب الخوارزمية سوى مصفوفة الدوران، ولكنها تتطلب أيضًا حساب متجه الإزاحة. عندما يتم تنفيذ كل من الإزاحة والدوران فعليًا، تُسمى الخوارزمية أحيانًا بالتراكب الجزئي لبروكروستس (انظر أيضًا مسألة بروكروستس المتعامدة ).

وصف

ليكن P و Q مجموعتين، تحتوي كل منهما على N نقطة فيRن{\displaystyle \mathbb {R} ^{n}}نريد إيجاد التحويل من Q إلى P. ولتبسيط الأمر، سننظر في الحالة ثلاثية الأبعاد (ن=3{\displaystyle n=3}). يمكن تمثيل المجموعتين P و Q كل منهما بمصفوفات N × 3 حيث يحتوي الصف الأول على إحداثيات النقطة الأولى، ويحتوي الصف الثاني على إحداثيات النقطة الثانية، وهكذا، كما هو موضح في هذه المصفوفة:

(x1y1z1x2y2z2⋮⋮⋮xشمالyشمالzشمال){\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}}}

تعمل الخوارزمية في ثلاث خطوات: عملية الترجمة، وحساب مصفوفة التغاير ، وحساب مصفوفة الدوران الأمثل.

ترجمة

يجب أولاً تحويل كلا مجموعتي الإحداثيات، بحيث يتطابق مركزهما مع نقطة الأصل في نظام الإحداثيات . ويتم ذلك عن طريق طرح إحداثيات المركز من إحداثيات النقطة.

حساب مصفوفة التغاير

تتمثل الخطوة الثانية في حساب المصفوفة H. في تدوين المصفوفات،

ح=Pتيسؤال{\displaystyle H=P^{\mathsf {T}}Q\,}

أو باستخدام رمز الجمع،

حأناج=∑ك=1شمالPكأناسؤالكج،{\displaystyle H_{ij}=\sum _{k=1}^{N}P_{ki}Q_{kj},}

وهي مصفوفة التغاير المتقاطع عندما يُنظر إلى P و Q على أنهما مصفوفتا بيانات .

حساب مصفوفة الدوران المثلى

من الممكن حساب الدوران الأمثل R بناءً على صيغة المصفوفة

R=(حتيح)12ح-1،{\displaystyle R=\left(H^{\mathsf {T}}H\right)^{\frac {1}{2}}H^{-1},}

لكن تطبيق حل عددي لهذه الصيغة يصبح معقدًا عند مراعاة جميع الحالات الخاصة (على سبيل المثال، حالة عدم وجود معكوس لـ H ).

إذا كانت إجراءات تحليل القيم المفردة (SVD) متاحة ، فيمكن حساب الدوران الأمثل، R ، باستخدام الخوارزمية التالية.

أولاً، احسب تحليل القيم المفردة لمصفوفة التغاير H ،

ح=يوΣVتي{\displaystyle H=U\Sigma V^{\mathsf {T}}}

حيث U و V متعامدان وΣ{\displaystyle \Sigma }قطري. بعد ذلك، سجل ما إذا كانت المصفوفات المتعامدة تحتوي على انعكاس.

د=المحقق(يوVتي)=المحقق(يو)المحقق(V).{\displaystyle d=\det \left(UV^{\mathsf {T}}\right)=\det(U)\det(V).}

وأخيرًا، احسب مصفوفة الدوران المثلى R كما يلي:

R=يو(10001000د)Vتي.{\displaystyle R=U{\begin{pmatrix}1&0&0\\0&1&0\\0&0&d\end{pmatrix}}V^{\mathsf {T}}.}

هذا R يقلل∑ك=1شمال‖Rqك-صك‖22{\displaystyle \sum _{k=1}^{N}\|Rq_{k}-p_{k}\|_{2}^{2}}، أينqك{\displaystyle q_{k}}وصك{\displaystyle p_{k}}تمثل الصفوف في Q و P على التوالي.

بدلاً من ذلك، يمكن أيضاً تقييم مصفوفة الدوران الأمثل مباشرةً كرباعي . [ 2 ] [ 3 ] [ 4 ] [ 5 ] وقد استُخدم هذا الوصف البديل في تطوير طريقة دقيقة لإزالة حركات الجسم الصلب من مسارات ديناميكيات الجزيئات المرنة. [ 6 ] وفي عام 2002، اقتُرح أيضاً تعميم لتطبيقه على التوزيعات الاحتمالية (سواء كانت متصلة أم لا). [ 7 ]

التعميمات

تم وصف الخوارزمية لنقاط في فضاء ثلاثي الأبعاد. والتعميم على الأبعاد D أمر مباشر.

تم شرح خوارزمية SVD هذه بمزيد من التفصيل على الرابط التالي: https://web.archive.org/web/20140225050055/http://cnx.org/content/m11608/latest/

تتوفر دالة MATLAB على الرابط التالي : http://www.mathworks.com/matlabcentral/fileexchange/25746-kabsch-algorithm

يتوفر برنامج بايثون على الرابط التالي: https://github.com/charnley/rmsd . كما يمكن إيجاد تطبيق آخر في مكتبة SciPy .

إضافة PyMol المجانية التي تُسهّل تطبيق Kabsch هي(كان هذا مرتبطًا سابقًا بـ CEalign)، ولكن هذا يستخدم خوارزمية الامتداد التوافقي (CE).) يستخدم VMD خوارزمية Kabsch للمحاذاة.

تتضمن مجموعة أدوات النمذجة FoldX خوارزمية Kabsch لقياس RMSD بين هياكل البروتين من النوع البري والطفرات.

انظر أيضاً

مراجع

  1. ↑ لورانس، جيم؛ بيرنال، خافيير؛ ويتزغال، كريستوف (9 أكتوبر 2019). "تبرير جبري بحت لخوارزمية كابش-أومياما" ( ملف PDF) . مجلة البحوث التابعة للمعهد الوطني للمعايير والتكنولوجيا . 124 : 124028. doi : 10.6028/jres.124.028 . ISSN 2165-7254 . PMC 7340555. PMID 34877177 .   
  2. ↑ هورن، بيرتولد كيه بي (1987-04-01). "حل مغلق للتوجيه المطلق باستخدام الكواترنيونات الوحدوية". مجلة الجمعية البصرية الأمريكية أ . 4 (4): 629. Bibcode : 1987JOSAA...4..629H . CiteSeerX 10.1.1.68.7320 . doi : 10.1364/josaa.4.000629 . ISSN 1520-8532 . S2CID 11038004 .   
  3. ↑ كنيلر، جيرالد ر. (1991-05-01). "تراكب البنى الجزيئية باستخدام الكواترنيونات". المحاكاة الجزيئية . 7 ( 1-2 ): 113-119 . doi : 10.1080/08927029108022453 . ISSN 0892-7022 . 
  4. ↑ كوتسياس، إي. أ.؛ سيوك، سي.؛ ديل، ك. أ. (2004). "استخدام الكواترنيونات لحساب متوسط ​​الانحراف التربيعي الجذري". مجلة الكيمياء الحاسوبية . 25 (15): 1849-1857 . doi : 10.1002/jcc.20110 . PMID 15376254. S2CID 18224579 .  
  5. ↑ بيتيجان، م. (1999). "حول متوسط ​​الجذر التربيعي للكيرالية الكمية ومقاييس التناظر الكمي" (ملف PDF) . مجلة الفيزياء الرياضية . 40 (9): 4587-4595 . Bibcode : 1999JMP....40.4587P . doi : 10.1063/1.532988 .
  6. ↑ شيفر، غيوم؛ كاليغاري، باولو؛ هينسن، كونراد؛ نيلر، جيرالد ر. (24 أغسطس/آب 2011). "نهج أقل القيود لاستخلاص الحركات الداخلية من مسارات الديناميكا الجزيئية للجزيئات الكبيرة المرنة". مجلة الفيزياء الكيميائية . 135 (8): 084110. Bibcode : 2011JChPh.135h4110C . doi : 10.1063/1.3626275 . ISSN 0021-9606 . PMID 21895162 .  
  7. ↑ بيتيجان، م. (2002). "المخاليط الكيرالية" (ملف PDF) . مجلة الفيزياء الرياضية . 43 (8): 4147-4157 . رمز Bibcode : 2002JMP....43.4147P . doi : 10.1063/1.1484559 . S2CID 85454709 . 
  • كابش، فولفغانغ (1976). "حل لأفضل دوران لربط مجموعتين من المتجهات". أكتا كريستالوغرافيكا . A32 (5): 922. Bibcode : 1976AcCrA..32..922K . doi : 10.1107/S0567739476001873 .
  • لين، يينغ-هونغ؛ تشانغ، هسون-تشانغ؛ لين، ياو-لينغ (15-17 ديسمبر 2004). دراسة حول الأدوات والخوارزميات لمحاذاة ومقارنة هياكل البروتينات ثلاثية الأبعاد . ندوة الحاسوب الدولية. تايبيه، تايوان.
  • أوميياما، شينجي (1991). "تقدير المربعات الصغرى لمعاملات التحويل بين نمطين نقطيين". مجلة IEEE للمعاملات في تحليل الأنماط والذكاء الآلي . 13 (4): 376-380 . doi : 10.1109/34.88573 .