Подструктурный поиск химических соединений в базах данных

Одной из задач в процессе разработки лекарств является задача поиска химических соединений, содержащих заданный фрагмент, в больших базах данных. Такие базы химических соединений содержат описание свойств, способы производства, результаты исследований, ссылки на статьи и другую связанную с данным веществом информацию. Сами молекулы задаются в виде своих структурных формул в виде помеченных графов. С формальной точки зрения задача поиска фрагмента химического соединения в другом соединении — это задача поиска изоморфного подграфа, которая является NP-полный. Для эффективного поиска используются различные критерии для отсеивания графов, которые заведомо не содержат заданный фрагмент. Одним из таких критериев является проверка на основе «битовых отпечатоков», в которых каждый бит соответствует какому-либо свойству графа.

В докладе будет рассмотрены все промежуточные задачи и основные алгоритмы, которые позволяют производить быстрый поиск химических соединений, а именно: алгоритм VF2 для задачи поиска изоморфного подграфа [1] и его возможные улучшения, способы построения и организации хранения «битовых отпечатков» молекул, метод реверсивного поиска [2] и его применение для перебора всех подграфов и поддеревьев определенного размера для заданного графа для построения битовых отпечатков.

В докладе также будет освещены некоторые альтернативные подходы к данной задаче.