Что это такое Skoal?
Skoal – это демо версия веб-сервиса поиска подобных химических соединений по заданному фрагменту химической формулы. Сервис построен на основе разработки Similarity Searchable DBMS CloudMSW (pdf) компании MeraLabs.
Главной отличительной особенностью поисковой системы Skoal является возможность поиска подобных химических соединений на основании размера общей подструктуры.
Зачем нужен Skoal?
Главной целью создания Skoal было демонстрация возможности хранения и поиска объектов, описываемых нетривиальными структурами, с заданной функцией близости в системе CloudMSW.
С помощью нашего сервиса вы можете по фрагменту химического соединения найти все вещества, содержащие данный фрагмент или вещества, структурно похожие на данный фрагмент.
На сегодняшний день ни одна поисковая система не предоставляет подобной функциональности. Это обусловлено несколькими причинами. Во-первых, определение структурной близости является вычислительно трудной задачей. Во-вторых, множество молекул вместе заданной на этом множестве функцией подобия, образуют метрическое пространство высокой размерности. И в-третьих, построение индекса для метрического пространства имеет сложность экспоненциально зависящей от размерности пространства. Отказ от индексирования пространства приводит к поиску осуществляемому полным перебором (метрика вычисляется между запросом и каждым элементом из базы).
Поэтому для предоставления функциональности поиска по подобию, система Skoal не использует построение традиционных индексов, вместо этого она использует технологию CloudMSW, которая позволяет производить поиск и добавление новых элементов из метрического пространства за логарифмическую сложность от общего числа элементов в структуре и линейную сложность от размерности пространства.
Как это работает?
В качестве сохраняемых в CloudMSW данных Skoal использует два типа объектов и две разные метрики для определения близости между объектами.
В первом случае Skoal объектами являются структурные графы молекул, при этом используется метрика, основанная на выделении максимально общего изоморфного подграфа в структурах двух молекул.
Представленный ниже демонстрационный ролик поясняет принципы организации данных и процесса поиска данных в системе Skoal.
Степень подобия двух химических элементов с графами структур G1 и G2 определяется функцией-метрикой, вычисляемой как:
где V(G1,G2) и E(G1,G2) - соответственно количество вершин и ребер в максимальном общем подграфе.
На Рис. 1 изображены структуры молекул и значения степеней подобия вычисленных между ними используя метрику simcv(G1,G2):
Рисунок 1
Во втором случае, в качестве объектов используются молекулярные фингерпринты – строка бит, где каждый бит соответствует какому-либо фиксированному структурному инварианту (Рис. 2):
Рисунок 2
Для того, чтобы определить степень близости между двумя строками бит (фингерпринтами) используется метрика Tanimoto, вычисляемая как
, где - “a” – количество ненулевых битов в fingerprint построенном для первой молекулы
- “b” – количество ненулевых битов в fingerprint построенном для второй молекулы
- “c” – количество общих ненулевых битов для обоих молекул.
На рисунке 3 приведена мера близости, определенная по метрике tanimoto.
Рисунок 3
Заключение
Система Skoal использует объекты и метрики, созданные специально для работы с данными о химических соединениях. Если вы собираетесь создавать высокотехнологичный продукт, который манипулируют с нетривиальными объектами используя понятие близости, то вас должна заинтересовать технология Similarity Searchable DBMS CloudMSW (pdf) .