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

Kabsch алгоритм , названный в честь Wolfgang Kabsch , является методом расчета оптимального вращения матрицы , что сводит к минимуму СКО ( Среднее квадратическое отклонение) между двумя парными наборами точек. Это полезно в графике, хеминформатике для сравнения молекулярных структур, а также в биоинформатике для сравнения структур белков (в частности, см. Среднеквадратичное отклонение (биоинформатика) ).

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

Описание [ править ]

Алгоритм для вращения $P$ в $Q$ начинается с двумя наборами парных точек, $P$ и $Q$ . Каждый набор точек можно представить в виде матрицы $размером$ $N \times 3$ . Первая строка - это координаты первой точки, вторая строка - координаты второй точки, $N-$ я строка - координаты $N-$ й точки.

{\ 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$ . В матричных обозначениях

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

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

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

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

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

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

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

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

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

Во- первых, вычислить СВД из ковариационной матрицы $H$ .

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

Затем решите, нужно ли нам корректировать нашу матрицу вращения, чтобы обеспечить правостороннюю систему координат.

{\ Displaystyle d = \ mathrm {знак} \ left (\ det \ left (VU ^ {\ mathsf {T}} \ right) \ right)}

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

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

Оптимальная матрица вращения также может быть выражена через кватернионы . ^[1]^[2]^[3]^[4] Это альтернативное описание было недавно использовано при разработке строгого метода удаления движений твердого тела из молекулярно-динамических траекторий гибких молекул. ^[5] В 2002 г. было также предложено обобщение для применения к распределениям вероятностей (непрерывным или нет). ^[6]

Обобщения [ править ]

Алгоритм описан для точек в трехмерном пространстве. Обобщение на измерения $D.$ Немедленно.

Внешние ссылки [ править ]

Этот алгоритм SVD более подробно описан на http://cnx.org/content/m11608/latest/

Функция Matlab доступна по адресу http://www.mathworks.com/matlabcentral/fileexchange/25746-kabsch-algorithm

C ++ , реализация (и модульное тестирование) с использованием Эйгена

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

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

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

См. Также [ править ]

Проблема Вахбы
Ортогональная проблема Прокруста

Ссылки [ править ]

^ Хорн, Бертольд КП (1987-04-01). «Замкнутое решение абсолютной ориентации с использованием единичных кватернионов». Журнал Оптического общества Америки A . 4 (4): 629. Bibcode : 1987JOSAA ... 4..629H . CiteSeerX 10.1.1.68.7320 . DOI : 10,1364 / josaa.4.000629 . ISSN 1520-8532 .
^ Кнеллер, Джеральд Р. (1991-05-01). «Суперпозиция молекулярных структур с использованием кватернионов». Молекулярное моделирование . 7 (1–2): 113–119. DOI : 10.1080 / 08927029108022453 . ISSN 0892-7022 .
^ Coutsias, EA; Seok, C .; Дилл, К.А. (2004). «Использование кватернионов для расчета RMSD». J. Comput. Chem . 25 (15): 1849–1857. DOI : 10.1002 / jcc.20110 . PMID 15376254 . S2CID 18224579 .
^ Петижан, М. (1999). «О среднеквадратичных количественных мерах хиральности и количественной симметрии» (PDF) . J. Math. Phys . 40 (9): 4587–4595. Bibcode : 1999JMP .... 40.4587P . DOI : 10.1063 / 1.532988 .
^ Шевро, Гийом; Каллигари, Паоло; Хинсен, Конрад; Кнеллер, Джеральд Р. (2011-08-24). «Метод наименьших ограничений для извлечения внутренних движений из молекулярно-динамических траекторий гибких макромолекул». J. Chem. Phys . 135 (8): 084110. Bibcode : 2011JChPh.135h4110C . DOI : 10.1063 / 1.3626275 . ISSN 0021-9606 . PMID 21895162 .
^ Petitjean, М. (2002). «Хиральные смеси» (PDF) . J. Math. Phys . 43 (8): 4147–4157. Bibcode : 2002JMP .... 43.4147P . DOI : 10.1063 / 1.1484559 .

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

[1] Хорн, Бертольд КП (1987-04-01). «Замкнутое решение абсолютной ориентации с использованием единичных кватернионов». Журнал Оптического общества Америки A . 4 (4): 629. Bibcode : 1987JOSAA ... 4..629H . CiteSeerX 10.1.1.68.7320 . DOI : 10,1364 / josaa.4.000629 . ISSN 1520-8532 .

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

[Coutsias2004-3] Coutsias, EA; Seok, C .; Дилл, К.А. (2004). «Использование кватернионов для расчета RMSD». J. Comput. Chem . 25 (15): 1849–1857. DOI : 10.1002 / jcc.20110 . PMID 15376254 . S2CID 18224579 .

[Petitjean1999-4] Петижан, М. (1999). «О среднеквадратичных количественных мерах хиральности и количественной симметрии» (PDF) . J. Math. Phys . 40 (9): 4587–4595. Bibcode : 1999JMP .... 40.4587P . DOI : 10.1063 / 1.532988 .

[5] Шевро, Гийом; Каллигари, Паоло; Хинсен, Конрад; Кнеллер, Джеральд Р. (2011-08-24). «Метод наименьших ограничений для извлечения внутренних движений из молекулярно-динамических траекторий гибких макромолекул». J. Chem. Phys . 135 (8): 084110. Bibcode : 2011JChPh.135h4110C . DOI : 10.1063 / 1.3626275 . ISSN 0021-9606 . PMID 21895162 .

[Petitjean2002-6] Petitjean, М. (2002). «Хиральные смеси» (PDF) . J. Math. Phys . 43 (8): 4147–4157. Bibcode : 2002JMP .... 43.4147P . DOI : 10.1063 / 1.1484559 .

[1]