Алгоритм Кабша

Алгоритм Кабша , также известный как алгоритм Кабша-Умеямы , ^[1] названный в честь Вольфганга Кабша и Синдзи Умеямы, представляет собой метод расчета оптимальной матрицы вращения , которая минимизирует RMSD ( среднеквадратичное отклонение) между двумя парными наборами точек. Это полезно для регистрации набора точек в компьютерной графике , а также в хемоинформатике и биоинформатике для сравнения молекулярных и белковых структур (в частности, см. Среднеквадратичное отклонение (биоинформатика) ).

Алгоритм вычисляет только матрицу вращения, но также требует вычисления вектора перемещения. Когда фактически выполняются и сдвиг, и вращение, алгоритм иногда называют частичным наложением Прокруста (см. также ортогональную задачу Прокруста ).

Описание

Пусть $P$ и $Q$ — два множества, каждое из которых содержит $N$ точек из $\mathbb {R} ^{n}$ . найти преобразование $Q$ в $P.$ Мы хотим Для простоты рассмотрим трехмерный случай ( $n=3$ ). Каждое из множеств $P$ и $Q$ может быть представлено $N \times 3$ матрицами размера , где первая строка содержит координаты первой точки, вторая строка содержит координаты второй точки и т. д., как показано в этой матрице:

${\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$ . В матричной записи

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

или, используя обозначение суммирования,

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

которая представляет собой матрицу перекрестной ковариации , когда $P$ и $Q$ рассматриваются как матрицы данных .

Вычисление оптимальной матрицы вращения

можно $Рассчитать оптимальное вращение R$ по матричной формуле

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

но реализация численного решения этой формулы усложняется, если учитывать все особые случаи (например, случай, когда $H$ не имеет обратного).

Если разложения по сингулярным значениям доступны процедуры $(SVD), оптимальное вращение R$ можно рассчитать с помощью следующего простого алгоритма.

Сначала вычислите SVD ковариационной матрицы $H$ ,

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

где $U$ и $V$ ортогональны и $\Sigma$ является диагональным. Далее запишите, содержат ли ортогональные матрицы отражение:

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

Наконец, вычислите нашу оптимальную матрицу вращения $R$ как

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

Этот $R$ минимизирует $\sum _{k=1}^{N}|Rq_{k}-p_{k}|$ , где $q_{k}$ и $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.

Реализация C++ (и модульный тест) с использованием Eigen

Сценарий Python доступен по адресу https://github.com/charnley/rmsd . Другую реализацию можно найти в SciPy .

Бесплатный плагин PyMol, легко реализующий Kabsch, — [1] . (Ранее это было связано с CEalign [2] , но здесь используется алгоритм комбинаторного расширения (CE).) VMD использует алгоритм Кабша для выравнивания.

Набор инструментов моделирования FoldX включает алгоритм Кабша для измерения RMSD между белковыми структурами дикого типа и мутировавшими.

См. также

Ссылки

^ Лоуренс, Джим; Берналь, Хавьер; Вицгалл, Кристоф (9 октября 2019 г.). «Чисто алгебраическое обоснование алгоритма Кабша-Умеямы» (PDF) . Журнал исследований Национального института стандартов и технологий . 124 : 124028. doi : 10.6028/jres.124.028 . ISSN 2165-7254 . ПМК 7340555 . ПМИД 34877177 .
^ Хорн, Бертольд К.П. (1 апреля 1987 г.). «Решение абсолютной ориентации в замкнутой форме с использованием единичных кватернионов». Журнал Оптического общества Америки А. 4 (4): 629. Бибкод : 1987JOSAA...4..629H . CiteSeerX 10.1.1.68.7320 . дои : 10.1364/josaa.4.000629 . ISSN 1520-8532 . S2CID 11038004 .
^ Кнеллер, Джеральд Р. (1 мая 1991 г.). «Суперпозиция молекулярных структур с использованием кватернионов». Молекулярное моделирование . 7 (1–2): 113–119. дои : 10.1080/08927029108022453 . ISSN 0892-7022 .
^ Кусиас, Э.А.; Сок, К.; Дилл, К.А. (2004). «Использование кватернионов для расчета RMSD». Дж. Компьютер. Хим . 25 (15): 1849–1857. дои : 10.1002/jcc.20110 . ПМИД 15376254 . S2CID 18224579 .
^ Петижан, М. (1999). «О среднеквадратических количественных мерах киральности и количественной симметрии» (PDF) . Дж. Математика. Физ . 40 (9): 4587–4595. Бибкод : 1999JMP....40.4587P . дои : 10.1063/1.532988 .
^ Шевро, Гийом; Каллигари, Паоло; Хинсен, Конрад; Кнеллер, Джеральд Р. (24 августа 2011 г.). «Подход с наименьшими ограничениями к извлечению внутренних движений из молекулярно-динамических траекторий гибких макромолекул». Дж. Хим. Физ . 135 (8): 084110. Бибкод : 2011JChPh.135х4110C . дои : 10.1063/1.3626275 . ISSN 0021-9606 . ПМИД 21895162 .
^ Петижан, М. (2002). «Хиральные смеси» (PDF) . Дж. Математика. Физ . 43 (8): 4147–4157. Бибкод : 2002JMP....43.4147P . дои : 10.1063/1.1484559 . S2CID 85454709 .

Кабш, Вольфганг (1976). «Решение для наилучшего вращения, чтобы связать два набора векторов». Акта Кристаллографика . A32 (5): 922. Бибкод : 1976AcCrA..32..922K . дои : 10.1107/S0567739476001873 .
- С поправкой в Кабш, Вольфганг (1978). «Обсуждение решения наилучшего вращения для связи двух наборов векторов» . Акта Кристаллографика . А34 (5): 827–828. Бибкод : 1978AcCrA..34..827K . дои : 10.1107/S0567739478001680 .
Линь, Ин-Хун; Чанг, Сюнь-Чанг; Лин, Яу-Линг (15–17 декабря 2004 г.). Исследование инструментов и алгоритмов для выравнивания и сравнения трехмерных белковых структур . Международный компьютерный симпозиум. Тайбэй, Тайвань.
Умеяма, Синдзи (1991). «Оценка параметров преобразования между двухточечными шаблонами методом наименьших квадратов». IEEE Транс. Паттерн Анал. Мах. Интелл . 13 (4): 376–380. дои : 10.1109/34.88573 .

[1] Лоуренс, Джим; Берналь, Хавьер; Вицгалл, Кристоф (9 октября 2019 г.). «Чисто алгебраическое обоснование алгоритма Кабша-Умеямы» (PDF) . Журнал исследований Национального института стандартов и технологий . 124 : 124028. doi : 10.6028/jres.124.028 . ISSN 2165-7254 . ПМК 7340555 . ПМИД 34877177 .

[2] Хорн, Бертольд К.П. (1 апреля 1987 г.). «Решение абсолютной ориентации в замкнутой форме с использованием единичных кватернионов». Журнал Оптического общества Америки А. 4 (4): 629. Бибкод : 1987JOSAA...4..629H . CiteSeerX 10.1.1.68.7320 . дои : 10.1364/josaa.4.000629 . ISSN 1520-8532 . S2CID 11038004 .

[3] Кнеллер, Джеральд Р. (1 мая 1991 г.). «Суперпозиция молекулярных структур с использованием кватернионов». Молекулярное моделирование . 7 (1–2): 113–119. дои : 10.1080/08927029108022453 . ISSN 0892-7022 .

[Coutsias2004-4] Кусиас, Э.А.; Сок, К.; Дилл, К.А. (2004). «Использование кватернионов для расчета RMSD». Дж. Компьютер. Хим . 25 (15): 1849–1857. дои : 10.1002/jcc.20110 . ПМИД 15376254 . S2CID 18224579 .

[Petitjean1999-5] Петижан, М. (1999). «О среднеквадратических количественных мерах киральности и количественной симметрии» (PDF) . Дж. Математика. Физ . 40 (9): 4587–4595. Бибкод : 1999JMP....40.4587P . дои : 10.1063/1.532988 .

[6] Шевро, Гийом; Каллигари, Паоло; Хинсен, Конрад; Кнеллер, Джеральд Р. (24 августа 2011 г.). «Подход с наименьшими ограничениями к извлечению внутренних движений из молекулярно-динамических траекторий гибких макромолекул». Дж. Хим. Физ . 135 (8): 084110. Бибкод : 2011JChPh.135х4110C . дои : 10.1063/1.3626275 . ISSN 0021-9606 . ПМИД 21895162 .

[Petitjean2002-7] Петижан, М. (2002). «Хиральные смеси» (PDF) . Дж. Математика. Физ . 43 (8): 4147–4157. Бибкод : 2002JMP....43.4147P . дои : 10.1063/1.1484559 . S2CID 85454709 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]