Kabschův algoritmus - Kabsch algorithm - Wikipedia

The Kabschův algoritmus, pojmenoval podle Wolfgang Kabsch, je metoda pro výpočet optima rotační matice který minimalizuje RMSD (kořenová střední hodnota na druhou odchylka) mezi dvěma spárovanými sadami bodů. Je to užitečné v grafice, cheminformatika porovnat molekulární struktury a také bioinformatika pro srovnání protein struktury (zejména viz odchylka od odmocniny (bioinformatika) ).

Algoritmus počítá pouze rotační matici, ale také vyžaduje výpočet vektoru překladu. Když se skutečně provádí překlad i rotace, algoritmus se někdy nazývá částečný Překrývá superpozici (viz také ortogonální Procrustesův problém ).

Popis

Algoritmus pro rotaci $P$ do $Q$ začíná dvěma sadami spárovaných bodů, $P$ a $Q$ . Každá sada bodů může být reprezentována jako $N \times 3$ matice. První řádek je souřadnice prvního bodu, druhý řádek je souřadnice druhého bodu, $N$ tento řádek je souřadnice $N$ bod.

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

Algoritmus pracuje ve třech krocích: překlad, výpočet kovarianční matice a výpočet optimální rotační matice.

Překlad

Obě sady souřadnic musí být nejprve přeloženy, aby byly těžiště se shoduje s původem souřadnicový systém. To se provádí odečtením souřadnic příslušného těžiště od souřadnic bodu.

Výpočet kovarianční matice

Druhý krok spočívá ve výpočtu matice $H$ . V maticové notaci

{ displaystyle H = P ^ { mathsf {T}} Q ,}

nebo pomocí součtové notace

{ displaystyle H_ {ij} = součet _ {k = 1} ^ {N} P_ {ki} Q_ {kj},}

což je křížově kovarianční matice když $P$ a $Q$ jsou považovány za datové matice.

Výpočet optimální matice rotace

Je možné vypočítat optimální rotaci $R$ na základě maticového vzorce

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

ale implementace numerického řešení tohoto vzorce se komplikuje, když se zohlední všechny speciální případy (například případ $H$ bez inverze).

Li rozklad singulární hodnoty (SVD) jsou k dispozici rutiny, optimální rotace, $R$ , lze vypočítat pomocí následujícího jednoduchého algoritmu.

Nejprve vypočítejte SVD kovarianční matice $H$ .

{ displaystyle H = U Sigma V ^ { mathsf {T}}}

Dále se rozhodněte, zda potřebujeme opravit naši rotační matici, abychom zajistili pravostranný souřadnicový systém

{ displaystyle d = mathrm {znamení} vlevo ( det vlevo (VU ^ { mathsf {T}} vpravo) vpravo)}

Nakonec vypočítáme naši optimální rotační matici, $R$ , tak jako

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

Optimální rotační matici lze také vyjádřit pomocí čtveřice.^[1]^[2]^[3]^[4] Tento alternativní popis byl nedávno použit při vývoji přísné metody odstraňování pohybů tuhého těla z molekulární dynamika trajektorie flexibilních molekul.^[5] V roce 2002 bylo rovněž navrženo zobecnění pro aplikaci na rozdělení pravděpodobnosti (kontinuální nebo ne).^[6]

Zobecnění

Algoritmus byl popsán pro body v trojrozměrném prostoru. Zobecnění na $D$ rozměry jsou okamžité.

externí odkazy

Tento algoritmus SVD je podrobněji popsán na http://cnx.org/content/m11608/latest/

A Matlab funkce je k dispozici na http://www.mathworks.com/matlabcentral/fileexchange/25746-kabsch-algorithm

A C ++ implementace (a test jednotky) pomocí Vlastní

A Krajta skript je k dispozici na https://github.com/charnley/rmsd

Zdarma PyMol plugin snadno implementující Kabsch je [1]. (To dříve souvisí s CEalign [2], ale toto používá Algoritmus CE. ) VMD používá k zarovnání Kabschův algoritmus.

The FoldX modeling toolsuite zahrnuje Kabschův algoritmus pro měření RMSD mezi strukturami divokého typu a mutovaného proteinu.

Viz také

Reference

^ Horn, Berthold K. P. (1987-04-01). "Uzavřené řešení absolutní orientace pomocí jednotkových čtveřic". Journal of the Optical Society of America A. 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. (01.05.1991). "Superpozice molekulárních struktur pomocí čtveřic". Molekulární simulace. 7 (1–2): 113–119. doi:10.1080/08927029108022453. ISSN 0892-7022.
^ Coutsias, E. A .; Seok, C .; Dill, K. A. (2004). Msgstr "Použití čtveřic k výpočtu RMSD". J. Comput. Chem. 25 (15): 1849–1857. doi:10.1002 / jcc.20110. PMID 15376254. S2CID 18224579.
^ Petitjean, M. (1999). „Kvantitativní kvantitativní chirality a kvantitativní symetrické míry na základě odmocniny“ (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). „Přístup nejmenších omezení k extrakci vnitřních pohybů z trajektorií molekulární dynamiky flexibilních makromolekul“. J. Chem. Phys. 135 (8): 084110. Bibcode:2011JChPh.135h4110C. doi:10.1063/1.3626275. ISSN 0021-9606. PMID 21895162.
^ Petitjean, M. (2002). "Chirální směsi" (PDF). J. Math. Phys. 43 (8): 4147–4157. Bibcode:2002JMP .... 43.4147P. doi:10.1063/1.1484559.

Kabsch, Wolfgang (1976). Msgstr "Řešení pro nejlepší rotaci dvou sad vektorů". Acta Crystallographica. A32 (5): 922. Bibcode:1976AcCrA..32..922K. doi:10.1107 / S0567739476001873.
- S opravou v Kabsch, Wolfgang (1978). "Diskuse o řešení pro nejlepší rotaci vztahující se ke dvěma sadám vektorů". Acta Crystallographica. A34 (5): 827–828. Bibcode:1978AcCrA..34..827K. doi:10.1107 / S0567739478001680.
Lin, Ying-Hung; Chang, Hsun-Chang; Lin, Yaw-Ling (15. – 17. Prosince 2004). Studie nástrojů a algoritmů pro srovnávání a srovnání 3-D proteinových struktur. Mezinárodní počítačové sympozium. Taipei, Taiwan.
Umeyama, Shinj (1991). "Odhad nejmenších čtverců parametrů transformace mezi dvěma bodovými vzory". IEEE Trans. Anální vzor. Mach. Intell. 13 (4): 376–380. doi:10.1109/34.88573.

[1] Horn, Berthold K. P. (1987-04-01). "Uzavřené řešení absolutní orientace pomocí jednotkových čtveřic". Journal of the Optical Society of America A. 4 (4): 629. Bibcode:1987JOSAA ... 4..629H. CiteSeerX 10.1.1.68.7320. doi:10,1364 / josaa. 4.000629. ISSN 1520-8532.

[2] Kneller, Gerald R. (01.05.1991). "Superpozice molekulárních struktur pomocí čtveřic". Molekulární simulace. 7 (1–2): 113–119. doi:10.1080/08927029108022453. ISSN 0892-7022.

[Coutsias2004-3] Coutsias, E. A .; Seok, C .; Dill, K. A. (2004). Msgstr "Použití čtveřic k výpočtu RMSD". J. Comput. Chem. 25 (15): 1849–1857. doi:10.1002 / jcc.20110. PMID 15376254. S2CID 18224579.

[Petitjean1999-4] Petitjean, M. (1999). „Kvantitativní kvantitativní chirality a kvantitativní symetrické míry na základě odmocniny“ (PDF). J. Math. Phys. 40 (9): 4587–4595. Bibcode:1999JMP .... 40,4587P. doi:10.1063/1.532988.

[5] Chevrot, Guillaume; Calligari, Paolo; Hinsen, Konrad; Kneller, Gerald R. (2011-08-24). „Přístup nejmenších omezení k extrakci vnitřních pohybů z trajektorií molekulární dynamiky flexibilních makromolekul“. J. Chem. Phys. 135 (8): 084110. Bibcode:2011JChPh.135h4110C. doi:10.1063/1.3626275. ISSN 0021-9606. PMID 21895162.

[Petitjean2002-6] Petitjean, M. (2002). "Chirální směsi" (PDF). J. Math. Phys. 43 (8): 4147–4157. Bibcode:2002JMP .... 43.4147P. doi:10.1063/1.1484559.

[1]

[2]

[3]

[4]

[5]

[6]