Hispanopedia Wiki
Articulo de referencia

Algoritmo de Kabsch

El algoritmo de Kabsch , también conocido como algoritmo de Kabsch-Umeyama , [ 1 ] nombrado en honor a Wolfgang Kabsch y Shinji Umeyama, es un método para calcular la matriz de ...

Hispanopedia WikiContenido en espanolLectura gratuita

El algoritmo de Kabsch , también conocido como algoritmo de Kabsch-Umeyama , [ 1 ] nombrado en honor a Wolfgang Kabsch y Shinji Umeyama, es un método para calcular la matriz de rotación óptima que minimiza la desviación cuadrática media ( RMSD ) entre dos pares de conjuntos de puntos. Es útil para el registro de conjuntos de puntos en gráficos por computadora , y en quimioinformática y bioinformática para comparar estructuras moleculares y proteicas (en particular, véase desviación cuadrática media (bioinformática) ).

El algoritmo solo calcula la matriz de rotación, pero también requiere el cálculo de un vector de traslación. Cuando se realizan tanto la traslación como la rotación, el algoritmo se denomina a veces superposición parcial de Procrustes (véase también problema de Procrustes ortogonal ).

Descripción

Sean P y Q dos conjuntos, cada uno con N puntos enRnorte{\displaystyle \mathbb {R} ^{n}}. Queremos encontrar la transformación de Q a P . Para simplificar, consideraremos el caso tridimensional (norte=3{\displaystyle n=3}Los conjuntos P y Q pueden representarse cada uno mediante matrices de N × 3, donde la primera fila contiene las coordenadas del primer punto, la segunda fila las coordenadas del segundo punto, y así sucesivamente, como se muestra en esta matriz:

(incógnita1y1z1incógnita2y2z2⋮⋮⋮incógnitanorteynorteznorte){\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}}}

El algoritmo funciona en tres pasos: una traslación, el cálculo de una matriz de covarianza y el cálculo de la matriz de rotación óptima.

Traducción

Ambos conjuntos de coordenadas deben trasladarse primero, de modo que su centroide coincida con el origen del sistema de coordenadas . Esto se logra restando las coordenadas del centroide a las coordenadas del punto.

Cálculo de la matriz de covarianza

El segundo paso consiste en calcular una matriz H. En notación matricial,

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

o, utilizando la notación de sumatoria,

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

que es una matriz de covarianza cruzada cuando P y Q se consideran matrices de datos .

Cálculo de la matriz de rotación óptima

Es posible calcular la rotación óptima R basándose en la fórmula matricial.

R=(HTH)12H−1,{\displaystyle R=\left(H^{\mathsf {T}}H\right)^{\frac {1}{2}}H^{-1},}

pero implementar una solución numérica a esta fórmula se vuelve complicado cuando se tienen en cuenta todos los casos especiales (por ejemplo, el caso de que H no tenga inversa).

Si se dispone de rutinas de descomposición en valores singulares (SVD), la rotación óptima, R , se puede calcular utilizando el siguiente algoritmo.

Primero, calcule la SVD de la matriz de covarianza H ,

H=UΣVT{\displaystyle H=U\Sigma V^{\mathsf {T}}}

donde U y V son ortogonales yΣ{\displaystyle \Sigma }es diagonal. A continuación, registre si las matrices ortogonales contienen una reflexión,

d=det(UVT)=det(U)det(V).{\displaystyle d=\det \left(UV^{\mathsf {T}}\right)=\det(U)\det(V).}

Finalmente, calculamos nuestra matriz de rotación óptima R como

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

Esta R minimiza∑k=1norte‖Rqk−pagk‖22{\displaystyle \sum _{k=1}^{N}\|Rq_{k}-p_{k}\|_{2}^{2}}, dóndeqk{\displaystyle q_{k}}ypagk{\displaystyle p_{k}}son filas en Q y P respectivamente.

Alternativamente, la matriz de rotación óptima también puede evaluarse directamente como un cuaternión . [ 2 ] [ 3 ] [ 4 ] [ 5 ] Esta descripción alternativa se ha utilizado en el desarrollo de un método riguroso para eliminar los movimientos de cuerpo rígido de las trayectorias de dinámica molecular de moléculas flexibles. [ 6 ] En 2002 también se propuso una generalización para la aplicación a distribuciones de probabilidad (continuas o no). [ 7 ]

Generalizaciones

El algoritmo se describió para puntos en un espacio tridimensional. La generalización a D dimensiones es inmediata.

Este algoritmo SVD se describe con más detalle en https://web.archive.org/web/20140225050055/http://cnx.org/content/m11608/latest/

Una función de Matlab está disponible en http://www.mathworks.com/matlabcentral/fileexchange/25746-kabsch-algorithm

Un script de Python está disponible en https://github.com/charnley/rmsd . Otra implementación se puede encontrar en SciPy .

Un plugin gratuito de PyMol que implementa fácilmente Kabsch es. (Esto estaba vinculado previamente a CEalign, pero este utiliza el algoritmo de Extensión Combinatoria (CE).) VMD utiliza el algoritmo de Kabsch para su alineación.

El conjunto de herramientas de modelado FoldX incorpora el algoritmo de Kabsch para medir la desviación cuadrática media (RMSD) entre las estructuras de proteínas de tipo salvaje y mutadas.

Véase también

Referencias

  1. ↑ Lawrence, Jim; Bernal, Javier; Witzgall, Christoph (09-10-2019). "Una justificación puramente algebraica del algoritmo de Kabsch-Umeyama" ( PDF) . Journal of Research of the National Institute of Standards and Technology . 124 : 124028. doi : 10.6028/jres.124.028 . ISSN 2165-7254 . PMC 7340555. PMID 34877177 .   
  2. ↑ Horn, Berthold KP (1987-04-01). "Solución en forma cerrada de la orientación absoluta usando cuaterniones unitarios". 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 . S2CID 11038004 .   
  3. ↑ Kneller, Gerald R. (1991-05-01). "Superposición de estructuras moleculares mediante cuaterniones". Simulación molecular . 7 ( 1– 2): 113– 119. doi : 10.1080/08927029108022453 . ISSN 0892-7022 . 
  4. ↑ Coutsias, EA; Seok, C.; Dill, KA (2004). "Uso de cuaterniones para calcular RMSD". J. Comput. Chem . 25 (15): 1849– 1857. doi : 10.1002/jcc.20110 . PMID 15376254. S2CID 18224579 .  
  5. ↑ Petitjean, M. (1999). "Sobre la raíz cuadrática media de las medidas cuantitativas de quiralidad y simetría" (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). "Enfoque de mínima restricción para la extracción de movimientos internos a partir de trayectorias de dinámica molecular de macromoléculas flexibles". J. Chem. Phys . 135 (8): 084110. Bibcode : 2011JChPh.135h4110C . doi : 10.1063/1.3626275 . ISSN 0021-9606 . PMID 21895162 .  
  7. ↑ Petitjean, M. (2002). "Mezclas quirales" (PDF) . J. Math. Phys . 43 (8): 4147– 4157. Bibcode : 2002JMP....43.4147P . doi : 10.1063/1.1484559 . S2CID 85454709 . 
  • Kabsch, Wolfgang (1976). "Una solución para la mejor rotación que relaciona dos conjuntos de vectores". Acta Crystallographica . A32 (5): 922. Bibcode : 1976AcCrA..32..922K . doi : 10.1107/S0567739476001873 .
    • Con una corrección en Kabsch, Wolfgang (1978). "Una discusión sobre la solución para la mejor rotación que relaciona dos conjuntos de vectores" . 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 de diciembre de 2004). Estudio sobre herramientas y algoritmos para la alineación y comparación de estructuras proteicas tridimensionales . Simposio Internacional de Informática. Taipéi, Taiwán.
  • Umeyama, Shinji (1991). "Estimación por mínimos cuadrados de parámetros de transformación entre dos patrones de puntos". IEEE Trans. Pattern Anal. Mach. Intell . 13 (4): 376– 380. doi : 10.1109/34.88573 .
Lecturas relacionadas
6 articulos
{\displaystyle R={\begin{bmatrix}\cos \theta &-\sin \theta \\\sin \theta &\cos \theta \end{bmatrix}}}Matriz de rotaciónEn álgebra lineal , una matriz de rotación es una matriz de transformación que se utiliza para realizar una rotación en el espacio euclidiano . Por...Estilo de visualización x_{i}}Raíz cuadrada mediaEn matemáticas , la raíz cuadrada media (abreviada como RMS , RMS o rms ) de un conjunto de números es la raíz cuadrada de la media cuadrada del co...desviación cuadrática mediadesviación cuadrática mediaLa desviación cuadrática media ( RMSD ) o el error cuadrático medio ( RMSE ) es una medida frecuentemente utilizada para cuantificar la diferencia ...Registro de conjuntos de puntosEl registro de conjuntos de puntos es el proceso de alinear dos conjuntos de puntos. En este caso, el pez azul se está registrando con el pez rojo....Gráficos de computadoraGráficos de computadoraLos gráficos por computadora se ocupan de generar imágenes y arte con la ayuda de computadoras . Los gráficos por computadora son una tecnología fu...QuimioinformáticaQuimioinformáticaLa quimioinformática (también conocida como quimioinformática ) se refiere al uso de la teoría de la química física con técnicas de informática y c...