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

 

 

В.А. Кохов, А.А. Незнанов, С.В. Ткаченко

 

 

(Москва, Московский энергетический институт (Технический университет), Россия)

 

 

 

 

 

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

 

ППП «Graph Model Workshop» (далее GMW) предназначен для проведения научных исследований, объектами которых являются графовые модели систем (ГМС), включая обыкновенные и ориентированные графы, с весами на вершинах и рёбрах. В GMW реализован поиск в базах структурной информации, как по стандартным, так и по оригинальным методам.

Особенностями реализации структурного поиска в GMW являются:

1)      поддержка всех видов точной структурной характеризации;

2)      поиск по ранее вычисленному и сохранённому фильтру базы ГМС;

3)      возможность проведения многоэтапного (уточняющего) поиска;

4)      использование g- и b-моделей при реализации обобщённого подструктурного подхода (ОПП) к анализу сходства ГМС [1];

5)      открытый программный интерфейс для улучшения существующих и добавления новых поисковых механизмов.

В качестве шаблона поиска может выступать как специально созданная (в редакторе шаблонов) ГМС, так и одна из ГМС исследуемой базы. Кроме структурного поиска, GMW поддерживает и другие виды поиска (например, по названиям ГМС). На рис. 1 показан вид главного окна GMW.

Эффективная реализация базовых алгоритмов структурного спектрального анализа ГМС позволяет за приемлемое время (менее минуты на одну ГМС на компьютере с процессором AMD Athlon 64 3000+ и 1 ГБ оперативной памяти) обрабатывать ГМС следующей размерности:

1)      при полной идентификации – до 1500 вершин.

2)      при частичной идентификации – до 700 вершин.

3)      при подструктурном сходстве – до 60 вершин.

4)      при приближённой характеризации время определяется видом используемых инвариантов. Например, при использовании спектральных характеристик в базисе цепей малых длин (от 0 до 6) – до 250 вершин.

 

Рис. 1. Главное окно GMW (показан выбор типа поискового запроса)

 

Выделим типы характеристик ГМС и способы сравнения характеристик различных типов:

1)      логические: наличие или отсутствие свойства;

2)      числовые: сравнение на равенство, упорядочение и принадлежность диапазону;

3)      векторные и матричные: поэлементное и интегральное сравнение;

4)      структурные: все способы точной структурной характеризации.

 

Рассмотрим пример иерархического поиска на основе приближённой характеризации ГМС с использованием структурных спектров [2].

Пусть имеется база молекулярных графов G_i (250250 структур из базы свободно доступных молекулярных графов (МГ) National Cancer Institute; среднее число вершин МГ – 40, максимальное – 254) и шаблон GT (выделенный МГ на 17 вершинах). Также задан базис структурных дескрипторов (СД) B (цепи длины от 0 до 6). В базе результатов (см. табл. 1) содержатся: 1) числовые инварианты (индекс структурной спектральной сложности ISC(G/B) и суммарное число фрагментов из B – SumWF(G/B)); 2) векторные инварианты (вектор-индекс структурной спектральной сложности V_ISC(G/B) и полный структурный спектр WF(G/B)); 3) структурные инварианты (b-модели вида V^l Í P^c_0-6).

 

Таблица 1

Объёмы используемых данных и время предварительных вычислений

*  – вычисляется вместе с V_CM.

 

Иерархический поиск проводится в несколько этапов, каждый из которых уточняет результаты предыдущего этапа. На каждом этапе увеличивается трудоёмкость поиска, однако пространство поиска сужается.

На этапах 1–3 применяется методика поиска, использующая первые три уровня обобщённого подструктурного подхода к анализу сходства [1].

Поиск проводится с использованием метаусловия , где Inv – инвариант ГМС, Common – функция определения максимальной общей части двух инвариантов, |Inv| – интегральная числовая характеристика инварианта. Левая часть формулы задаёт количественное значение сходства двух ГМС, правая – порог толерантности. На каждом этапе мера сходства уточняется благодаря тому, что используемые инварианты учитывают расширенную информацию: число фрагментов на первом этапе, их состав – на втором, их расположение – на  третьем. Рассмотрим содержание каждого этапа.

0.      В базе МГ оставляем только связные, получая набор МГ  N₀.

1.      Поиск по числовому инварианту в наборе N₀ с использованием условия . Получаем набор МГ  N₁.

2.      Поиск по векторному инварианту в наборе N₁ с использованием условия ,где [a_i] – WF(GT /B), [b_i] – WF(G_i /B), n – число фрагментов в базисе СД. Получаем набор МГ  N₂.

3.      Поиск по структурному инварианту в наборе N₂ с использованием условия , где E – множество рёбер, MCF – максимальный общий фрагмент, GM – b-модель вида V^l Í P^c_0-6.  Получаем набор МГ  N₃.

Поиск на всех вышеперечисленных этапах выполняется за полиномиальное время. Далее в интерактивном режиме исследуется сходство расположения фрагментов в топологии ГМС – выполняется последовательный поиск по структурному инварианту в наборе МГ N₃ с использованием условия , где, OSG – граф сходства расположения орбит фрагментов.

Результаты поиска МГ, сходных с GT, на каждом этапе приведены в таблице 2. Коэффициенты k₁, k₂, k₃ и k₄ равны 0,96.

 

Таблица 2

Сокращение числа ГМС и времени поиска на разных этапах

№ этапа	Число ГМС	Время поиска по этапам, мс	Время поиска по набору графов N0, мс	Коэффициент ускорения
0	250250	2621	—	—
1	236851	2469	2469	—
2	13546	474	3981	8,3
3	1069	1650	691241	418,9
4	74	Интерактивная обработка	—	—

 

 

Средства структурного поиска, реализованные в GMW, используются также программных средствах учебного назначения (ПСУН) для компьютерной поддержки раздела «Основы структурной информатики» дисциплины «Информатика» и поддержки дисциплин «Структурная информатика», «Дискретная математика», «Теория графов и комбинаторика», «Анализ и проектирование эффективных алгоритмов» и др. [3]. Информация об этих ПСУН доступна в интернете по адресу www.graphmodel.com.

 

 

ЛИТЕРАТУРА

1.     Кохов В.А., Незнанов А.А., Ткаченко С.В. Компьютерные методы анализа сходства графов. // Десятая Национальная конференция по искусственному интеллекту с международным участием. КИИ-2004: Труды конференции. В 3-х т. Том 1. М.: Физматлит, 2004. – С. 162-171.

2.     Кохов В.А. Новые методы характеризации и анализа сходства графов для поиска структурной информации. // См. настоящий сборник.

3.     Ткаченко С.В., Незнанов А.А., Кохов В.А. Компьютерная поддержка курса «Основы Структурной информатики». // Доклады международной конференции «Информационные средства и технологии». (МФИ-2002), Т.2, Москва, 2002. – С. 55-58.