Хемоинформатика

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

Поиск схожих молекул

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

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

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

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

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

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

  • 1 англ. molecular fingerprints

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

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

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

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

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

  • 3 Molecular ACCess System

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

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

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

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

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

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

  • 5 с англ.: «круговые» отпечатки (реже: отпечатки Моргана)

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

  • 6 от англ. molecular similarity

    • Для численной характеристики схожести молекулярных структур используются их векторное представление. Между векторами-отпечатками можно определить метрику расстояния. Чаще всего структурное подобие двух молекул оценивается по индексу Танимото: \[ T(A, B) := \dfrac{ c }{a + b - c}, \]{eq:tanimoto} где \(A\) и \(B\) — векторы-отпечатки, \(a\) и \(b\) — число \(1\) в отпечатках соответственно, \(c\) — число \(1\) общих для обоих отпечатков. Например, для \[A = (0, 0, \bf 1, \bf 1, 1), \qquad B = (0, 1, \bf 1, \bf 1, 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}. \]

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

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

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

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

    Источники

    1.
    Durant J.L. и др. Reoptimization of MDL keys for use in drug discovery. // J Chem Inf Comput Sci. United States. Т. 42, № 6. С. 1273–1280.