Алгоритм Кабша - Википедия - Kabsch algorithm

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

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

Описание

Алгоритм вращения $п$ в $Q$ начинается с двух наборов парных точек, $п$ и $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}}}

Алгоритм состоит из трех этапов: перевод, вычисление ковариационной матрицы и вычисление оптимальной матрицы вращения.

Перевод

Сначала необходимо преобразовать оба набора координат, чтобы их центроид совпадает с происхождением система координат. Это делается путем вычитания из координат точки координаты соответствующего центроида.

Вычисление ковариационной матрицы

Второй шаг состоит в вычислении матрицы $ЧАС$ . В матричных обозначениях

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

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

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

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

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

Есть возможность рассчитать оптимальный поворот $р$ на основе матричной формулы

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

но реализация численного решения этой формулы становится сложной, если учесть все частные случаи (например, случай $ЧАС$ не имеющий обратного).

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

Сначала вычислите SVD ковариационной матрицы $ЧАС$ .

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

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

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

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

{ 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

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

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

Смотрите также

Рекомендации

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

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

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

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

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

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]