Kabsch algoritm

Kabsch -algoritmen , uppkallad efter Wolfgang Kabsch, är en metod för att beräkna den optimala rotationsmatrisen som minimerar RMSD ( root mean squared deviation) mellan två parade uppsättningar av punkter. Det är användbart i grafik, keminformatik för att jämföra molekylära strukturer, och även bioinformatik för att jämföra proteinstrukturer (se särskilt rot-medelkvadratavvikelse (bioinformatik) ) .

Algoritmen beräknar bara rotationsmatrisen, men den kräver också beräkning av en translationsvektor. När både translationen och rotationen faktiskt utförs kallas algoritmen ibland för partiell Procrustes-överlagring (se även ortogonal Procrustes-problem ) .

Beskrivning

Algoritmen för rotationen av $P$ till $Q$ börjar med två uppsättningar parade punkter, $P$ och $Q$ . Varje uppsättning punkter kan representeras som en $N \times 3$ matris . Den första raden är koordinaterna för den första punkten, den andra raden är koordinaterna för den andra punkten, den $N$ :te raden är koordinaterna för den $N$ :te punkten. Kontrollera matrisen nedan

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

Algoritmen fungerar i tre steg: en translation, beräkningen av en kovariansmatris och beräkningen av den optimala rotationsmatrisen.

Översättning

Båda uppsättningarna av koordinater måste översättas först, så att deras tyngdpunkt sammanfaller med ursprunget för koordinatsystemet . Detta görs genom att subtrahera från punktkoordinaterna för respektive tyngdpunkt.

Beräkning av kovariansmatrisen

Det andra steget består av att beräkna en matris $H$ . I matrisnotation,

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

eller, med summeringsnotation,

H_{ij}=\sum _{k=1}^{N}P_{ki}Q_{kj},

som är en korskovariansmatris när $P$ och $Q$ ses som datamatriser .

Beräkning av den optimala rotationsmatrisen

Det är möjligt att beräkna den optimala rotationen $R$ baserat på matrisformeln

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

men att implementera en numerisk lösning på denna formel blir komplicerad när alla specialfall redovisas (till exempel fallet med $H$ som inte har en invers).

Om rutiner för singular value decomposition (SVD) är tillgängliga, kan den optimala rotationen, $R$ , beräknas med hjälp av följande enkla algoritm.

Beräkna först SVD för kovariansmatrisen $H$ .

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

Bestäm sedan om vi behöver korrigera vår rotationsmatris för att säkerställa ett högerhänt koordinatsystem

d=\mathrm {tecken} \left(\det \left(VU^{\mathsf {T}}\right)\right)

Beräkna slutligen vår optimala rotationsmatris, $R$ , som

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

Den optimala rotationsmatrisen kan också uttryckas i termer av kvaternioner . Denna alternativa beskrivning har använts i utvecklingen av en rigorös metod för att ta bort stela kroppsrörelser från molekylära dynamikbanor hos flexibla molekyler. År 2002 föreslogs också en generalisering för tillämpningen av sannolikhetsfördelningar (kontinuerliga eller ej).

Generaliseringar

Algoritmen beskrevs för punkter i ett tredimensionellt utrymme. Generaliseringen till $D$ -dimensioner är omedelbar.

externa länkar

Denna SVD-algoritm beskrivs mer i detalj på http://cnx.org/content/m11608/latest/

En Matlab- funktion finns tillgänglig på http://www.mathworks.com/matlabcentral/fileexchange/25746-kabsch-algorithm

En C++-implementering (och enhetstest) med Eigen

Ett Python- skript finns tillgängligt på https://github.com/charnley/rmsd . En annan implementering finns i SciPy .

Ett gratis PyMol- plugin som enkelt implementerar Kabsch är [1] . (Detta var tidigare kopplat till CEalign [2] , men detta använder CE-algoritmen . ) VMD använder Kabsch-algoritmen för sin justering.

FoldX - modelleringsverktygspaketet innehåller Kabsch-algoritmen för att mäta RMSD mellan vildtyps- och muterade proteinstrukturer.

Se även

Kabsch, Wolfgang (1976). "En lösning för den bästa rotationen för att relatera två uppsättningar vektorer". Acta Crystallographica . A32 (5): 922. Bibcode : 1976AcCrA..32..922K . doi : 10.1107/S0567739476001873 .
- Med en rättelse i Kabsch, Wolfgang (1978). "En diskussion om lösningen för den bästa rotationen för att relatera två uppsättningar vektorer" . 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 december 2004). En studie om verktyg och algoritmer för justering och jämförelse av 3D-proteinstrukturer . Internationellt datorsymposium. Taipei, Taiwan.
Umeyama, Shinji (1991). "Minsta kvadraters uppskattning av transformationsparametrar mellan tvåpunktsmönster". IEEE Trans. Mönster Anal. Mach. Intell . 13 (4): 376–380. doi : 10.1109/34.88573 .