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

Одной из задач в процессе разработки лекарств является задача поиска химических соединений, содержащих заданный фрагмент, в больших базах данных. Такие базы химических соединений содержат описание свойств, способы производства, результаты исследований, ссылки на статьи и другую связанную с данным веществом информацию. Сами молекулы задаются в виде своих структурных формул в виде помеченных графов. С формальной точки зрения задача поиска фрагмента химического соединения в другом соединении - это задача поиска изоморфного подграфа (subgraph isomorphism problem), которая является NP-полный. Обычно размер запроса (фрагмента молекулы) содержит не больше 20 вершин, а количество вершин в молекулах в базе около 100–200, и проверка наличия заданного фрагмента для конкретной молекулы занимает небольшое время (около 0.1-1 мс). Но количество молекул в современных базах данных достигает 40 млн., и поэтому явная проверка наличия изоморфного подграфа для каждого соединения в базе займет очень большое время. Для эффективного поиска используются различные критерии для отсеивания графов, которые заведомо не содержат заданный фрагмент. Одним из таких критериев является проверка на основе "битовых отпечатоков" (fingerprints), в которых каждый бит соответствует какому-либо свойству графа. В докладе будет рассмотрены все промежуточные задачи и основные алгоритмы, которые позволяют производить быстрый поиск химических соединений, а именно:

1. Алгоритм VF2 для задачи поиска изоморфного подграфа [1] и его возможные улучшения
2. Способы построения и организации хранения "битовых отпечатков" молекул.
3. Метод реверсивного поиска [2] и его применение для перебора всех подграфов и поддеревьев определенного размера для заданного графа для построения битовых отпечатков. В докладе также будет освещены некоторые альтернативные подходы к данной задаче. 

Литература:

1. A (sub)graph isomorphism algorithm for matching large graphs; Cordella, L.P., Foggia, P., Sansone, C.,Vento, M., 2004
2. Reverse Search for Enumeration; David Avis, Komei Fukuda, 1993

Страница лекции