Оценка структурной схожести молекул

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

1 Поиск по подграфу

Самый прямой способ оценить сходство двух молекул, посмотреть на их молекулярные графы и найти в них наибольшую общую подструктуру. На практике, однако, две молекулы могут иметь несколько наибольших общих подграфов (например, метан и этан). Поиск такой подструктуры весьма вычислительно сложная задача и фактически решается перебором; зачастую даже для несложных с химической точки зрения молекул вычисление наибольшего общего подграфа может занимать десятки секунд, что делает этот метод неприменимым для работы с базами миллионов молекул. Для небольшого набора, тем не менее, наибольшие общие подграфы активно применяются для оценки схожести.

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

2 Молекулярные отпечатки

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

¹ англ. molecular fingerprints

² англ. hash — мешанина; урезанное представление данных в виде короткой последовательности битов (как правило фиксированной длины), используется, например, при быстром сравнении двух текстов: тексты совпадают тогда и только тогда, когда совпадают их хеши

Одному молекулярному графу строго соответствует один отпечаток, однако, не требуется выполнение взаимно-однозначного соответствия, т.е. одному отпечатку потенциально могут соответствовать много структур, что роднит молекулярные отпечатки с хешем². На практике, однако, встретить две молекулы с одним молекулярным отпечатком удаётся нечасто. Важными преимуществами молекулярных отпечатков является а) высокая скорость их вычисления по сравнению с операциями над графами и б) простота поиска похожих химических структур.

Многие часто используемые алгоритмы вычисления молекулярных отпечатков были разработаны в составе прикладного ПО. Конкретная реализация алгоритма может охраняться коммерческой тайной или патентами, поэтому существует большое число их реализаций. Приведём лишь некоторые из них.

Структурные отпечатки (ключи)

Структурные ключи MACCS³ [1] являются одними из самых часто используемых методов построения отпечатков. MACCS представляют набор из 166 (960 в расширенном варианте) молекулярных фрагментов, на наличие которых тестируется молекулярный граф, если в молекуле найден фрагмент с номером k, то в итоговом векторе-отпечатке компонента x_k приравнивается 1, иначе 0. Например, для молекулы этана \ce{CH3CH3} отпечаток MACCS будет вектором из 166 компонент, в которых все компоненты будут нулями, кроме 160ой (наличие метильной группы \ce{CH_3} в молекуле) и 149ой (количество метильных групп больше одной), т.е. только 2 бита из 166 несут значимую информацию.

³ Molecular ACCess System

1.

Durant J.L. et al. Reoptimization of MDL keys for use in drug discovery. // J Chem Inf Comput Sci. United States. Vol. 42, № 6. P. 1273–1280.

Хешированные отпечатки

Использование структурных фрагментов для создания отпечатков имеет один недостаток — вид отпечатка сильно зависит от используемой библиотеки фрагментов, если библиотека содержит фрагменты, которые редко встречаются в каком-либо подмножестве молекул, отпечатки будет содержать большое число нулей и не будут информативными. Для борьбы с этой проблемой придуманы хешированные отпечатки.

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

Path-based fingerprints⁴ хешируют различные пути в молекулярном графе, т.е. молекула разбивается на фрагменты определённой длинны, каждый такой фрагмент затем подвергается хешированию и влияет на итоговый отпечаток.

⁴ отпечатки основанные на путях (в молекулярном графе)

⁵ «круговые» отпечатки (реже: отпечатки Моргана)

Circular fingerprints⁵ вводят понятие радиальных фрагментов: фрагмент образуют центральный атом и его ближайшие атомы-соседи, соединённые с центром на отдалении не более чем на n химических связей, где n — радиус. Алгоритм итеративно обновляет хеши для всех атомов в молекуле и конструирует отпечаток, который является сжатым представлением информации обо всех соседях в молекуле.

3 Структурная схожесть

Для численной характеристики схожести молекулярных структур⁶ используются их векторное представление. Между векторами-отпечатками можно определить метрику расстояния. Чаще всего структурное подобие двух молекул оценивается по индексу Танимото: T(A, B) := \dfrac{ c }{a + b - c},

⁶ англ. molecular similarity

где A и B — векторы-отпечатки, a и b — число 1 в отпечатках соответственно, c — число 1 общих для обоих отпечатков. Например, для A = (0, 0, \mathbf1, \mathbf1, 1), \qquad B = (0, 1, \mathbf1, \mathbf1, 0) индекс Танимото T = \dfrac{2}{3 + 3 - 2} = \dfrac{1}{2}. Также используется коэффициент Дайса; для примера выше: D(A, B) := \dfrac{2 c}{a + b} = \dfrac{2 \cdot 2}{3 + 3} = \dfrac{2}{3}.

4 Структурно богатое подмножество

При наличии большого числа кандидатов на экспериментальную проверку неизбежно встаёт вопрос о выделении некоторого набора молекул для первично экспериментальной проверки. Векторное представление молекул позволяет решать и эту задачу.

Структурно близкие молекулы потенциально обладают схожей биологической активностью, при ограниченных ресурсах экспериментальную проверку стоит проводить с молекулами разных классов. Поскольку близкие структуры отображаются в близкие молекулярные отпечатки, задачу можно переформулировать в терминах расстояния: из N векторов отпечатков необходимо выбрать n < N векторов наиболее удалённых друг от друга (например, в смысле Танимото); соответствующие молекулы и будут кандидатами на экспериментальную проверку.

В такой постановке задача обычно решается с помощью алгоритмов двух классов: а) кластеризации (например, Taylor-Butina, K-Means), когда пул кандидатов делится на заданное число кластеров и затем из каждого кластера выбирается одна молекула, и б) MaxMin, когда из пула последовательно выбираются молекулы, достаточно удалённые от уже выбранных.