автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Алгоритмические программные средства поддержки преобразования данных для химически ориентированных экспертных систем типа ДСМ

Р Г Б ОД 2 О ДОГ 1995

На правах рукописи

ЛЕЙБОВ Александр Ефимович

АЛГОРИТМИЧЕСКИЕ И ПРОГРАММНЫЕ СРЕДСТВА

ПОДДЕРЖКИ ПРЕОБРАЗОВАНИЯ ДАННЫХ ДЛЯ ХИМИЧЕСКИ ОРИЕНТИРОВАННЫХ ЭКСПЕРТНЫХ СИСТЕМ ТИПА ДСМ

Специальность - 05.13.17 Теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва 1995

Работа выполнена во Всероссийском институте научной и технической информации Российской Академии наук и Министерства науки и технической политики Российской Федерации

Научный руководитель: доктор технических наук, профессор Финн Виктор Константинович

Официальные оппоненты: доктор технических наук, профессор Миронов Георгий Акимович кандидат технических наук, доцент Хорошевский Владимир Федорович

Ведущая организация: Российский Государственный Гуманитарный Университет (факультет информатики)

Защита состоится " '9-У 1995 г. часов на за-

седании диссертационного совета Д 003.02л) 1 во Всероссийском институте научной и технической информации по адресу: 125219, Москва, ул. Усиевича, д. 20-а.

С диссертацией можно ознакомиться в библиотеке Всероссийского института научной и технической информации

Автореферат разослан 61 ^г.

Ученый секретарь диссертационного совета доктор биологических наук,

профессор М.А. Каменская

Общая характеристика работы

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

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

Перспективным направлением в развитии интеллектуальных систем являются гибридные интегрированные интеллектуальные системы, содержащие представления объектов в БД в виде двухмерных или трехмерных образов, а также системы обнаружения закономерностей в БД. Системы, основанные на ДСМ-методе автоматического порождения гипотез, являются гибридными интегрированными интеллектуальными системами, используемыми для порождения закономерностей в базах данных с неполной информацией. В представленной диссертации решается ряд полезных задач в рамках указанных направлений развития интеллектуальных систем.

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

Актуальность темы диссертации определяется тем, что в ней реализуется принцип сохранения структуры основных правил решателя, представляющих правдоподобные выводы, при варьировании структур

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

В процессе работы над диссертацией получены следующие научные результаты:

1. Создана система автоматизированного ввода представлений структурных формул органической химии, обеспечивающая интерфейс пользователю с экспертными системами типа ДСМ для задач порождения зависимостей "структура химического соединения - множество биологических активностей". Указанная подсистема содержит химический редактор \VChar [8] и подсистему автоматического кодирования [5] структурных формул органической химии посредством языка ФКСП (фрагментарный .код суперпозиций подструктур, предложенный В.В. Авидоном) [1]. Созданная подсистема автоматического кодирования кодом ФКСП решает задачу преобразования молекулярных графов в булевскую структуру, что означает покрытие этих графов множеством дескрипторов, ориентированных на комплимен-тарность рецепторам.

2. Разработаны алгоритмические и программные средства реализации операции сходства и отношений вложения для химических графов [8], что означает создание инструментальных средств для применения ДСМ-метода автоматического порождения гипотез к структуре данных, в которой объектами являются молекулярные графы.

3. Проведен сравнительный анализ операций сходства, применяемый в решателе задач типа ДСМ, реализованных для химических соединений, представленных посредством кода ФКСП (в булевской структуре данных), и посредством химических графов (в структуре данных, являющейся дистрибутивной решеткой, но не булевской) [4].

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

5. Рассмотрены возможные способы использования фильтров при поиске в БД по фрагменту структурной формулы, ориентированные на решение задач прогнозирования биологической активности химических соединений в ЭС типа ДСМ.

6. Решена задача распараллеливания решателя задач ЭС типа ДСМ (проведены эксперименты с этой целью с использованием транспьютера).

Научная новизна работы заключается в следующем:

1. Впервые созданы алгоритмические и программные средства для ЭС типа ДСМ, ориентированные на решение задач прогнозирования свойств химических соединений такие, что объектами в БД и базе знаний являются молекулярные графы, а не их фрагментарные представления. Для этого реализованы алгоритмические средства поиска сходства химических соединений, используемые для порождения гипотез о причинах биологической активности этих соединений, а также созданы средства автоматического представления химических соединений в коде ФКСП (как объектов булевской структуры данных).

2. При участии автора диссертации разработана новая версия ЭС типа ДСМ, объектами которой являются молекулярные графы. Данная ЭС используется в качестве инструмента молекулярного дизайна в исследовательских целях биохимиками и фармакологами.

Практическая значимость работы определяется значимостью задач молекулярного дизайна и компьютерного мониторинга химических соединений. Результаты исследований автора опубликованы в пяти статьях.

Краткое содержание работы

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

Настоящая работа посвящена алгоритмическим и программным средствам преобразования данных для химически ориентированных ЭС типа ДСМ [11], применяемых для решения задач молекулярного дизайна. Во введении имеется сравнительный анализ ЭС типа ДСМ с другими ЭС, решаюхцими аналогичные задачи. ДСМ - процедура осуществляет правдоподобный вывод, результатом которого является информация о наличии или отсутствии свойств у объектов на основании анализа прецедентов (объектов с заранее известными свойствами). Для работы ДСМ - системы требуется набор объектов, про которые известно, что они обладают каким-либо свойством ("+" - объекты) и набор объектов, про которые известно, что они не обладают соответствующим свойством ("-" - объекты). Также может быть набор объектов, свойства которых требуется определить ("т" - объекты).

ДСМ-система работает в четыре этапа.

На первом этапе осуществляется правдоподобный логический вывод на основе анализа "+" и "-" - объектов о причинах, ответственных за наличие исследуемого свойства ("+" - причины) и причинах, ответственных за отсутствие исследуемого свойства ("-" - причины). Т.к. вывод правдоподобный, то эти причины являются на самом деле гипотезами о причинах наличия или отсутствия свойства.

На втором этане осуществляется правдоподобный логический вывод, реализующий доопределение "т" - объектов на основании "+" и "-" - гипотез, порожденных на первом этапе. После этого процесс может повторяться, в случае, если остались недоопределенные объекты, до стабилизации исходной выборки.

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

На четвертом этапе осуществляется порождение индуктивных обобщений для базы знаний (в случае работы с несколькими активностями). На рис. 1 представлена схема работы ЭС типа ДСМ.

¡Внешняя БД, 'содержащая юбъекты и их ¡свойства.

П ольэователь

_г

Подготовка исходных данных для ДСМ - процедуры.

Исходная выборка

"+* объекты

объекты

'Т* объекты

гт

Стратегия вычислений.

Операция поиска сходства на объектах.

ДСМ - решатель

г

ППВ - I

ППВ - II

рис. 1

1

Средства визуализации исходных объектов и гипотез

База знаний

гипотезы

- гипотезы

ППВ - I — правила правдоподобного вывода Iй рода, осуществляющие правдоподобный логический вывод на первом этапе работы ДСМ -решателя.

ППВ - 2 — правила правдоподобного вывода 2й рода, осуществляющие правдоподобный вывод на втором этапе работы ДСМ - решателя.

Во внешней БД должны храниться структурные формулы химических соединений и их свойства.

Блок подготовки исходных данных осуществляет поиск необходимых структур в БД и их перекодирование в представление, необходимое для работы ДСМ - решателя. В случае отсутствия внешней БД исходные структуры могут вводиться непосредственно пользователем.

Операция сходства необходима для работы ДСМ - решателя и является внешней по отношению к нему. Смысл операции сходства сводится к поиску общих частей у исходных объектов. Конкретная реализация операции сходства и структура данных зависит от предметной области (ПО). Качество работы всей системы сильно зависит от разум-

ной реализации операции сходства над объектами. Под разумной реализацией операции сходства понимается операция над парами объектов такая, что, во-первых, она является алгебраической, а во-вторых, она осмысленно интерпретируется относительно рассматриваемой ПО.

В первой главе подробно рассматривается формализация операций сходства (в смысле ДСМ-метода) для объектов, представленных в специальном проблемно-ориентированном коде ФКСП [1], а также для объектов, представленных в виде молекулярных графов. Описываются алгоритмы поиска сходства, вложения и изоморфизма графов. Приводится сравнительный анализ операций сходства, реализованных для ФКСП и для графов. Описывается работа ДСМ-решателя, оперирующего с графовым представлением исходных объектов.

ЭС типа ДСМ [11] может применяться в случаях, когда данные ПО хорошо структурированы, а знания о ней плохо формализованы. Под хорошей структурированностью данных понимается возможность выразить локальное сходство между объектами с определенной структурой как алгебраическую операцию и возможность имитации алгебраическими средствами операций сходства, вложения и изоморфизма для различных структур данных. При вариациях структур данных (множества, кортежи, графы и т.п.) структура решающих правил правдоподобного вывода не меняется, а изменения касаются только соответствующих операций сходства, отношений вложения и т.п.

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

В ЭС, решающих задачи типа "структура химического соединения -биологическая активность", исходными данными (в БД) будут структура соединения и проявляемые этим соединением биологические активности.

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

частности, пространственная структурная формула, просто структурная химическая формула, а также описание соединений с помощью дескрипторов, выражающих отдельные фрагменты структуры.

Сходство на ФКСП.

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

Среди различных дескрипторных языков для представления исходных химических соединений был выбран код ФКСП [1], предложенный в начале 70-х годов В.В.Авидоном. Этот код предназначен для дискретного описания химического соединения в виде набора всех имеющихся в нем подструктур, представляющих собой центры локализации тс-электронов.

Идея этого кода основана на предположении, в соответствии с которым в природе существует "язык распознавания структуры" специальными приемниками информации (молекулярными рецепторами) [10]. Рецептор распознает структуру в результате образования относительно слабых химических связей между своими активными центрами и соответствующими активными центрами в фармакофоре (иод фармакофо-ром понимается фрагмент химического соединения, непосредственно воздействующий на рецептор). Поэтому дескрипторы кода ФКСП содержат в себе по два активных центра, разделенных друг от друга цепочкой атомов углерода.

ЭС, решающие задачи типа "структура химического соединения -биологическая активность", могут использовать код ФКСП в качестве средства представления химической структуры в своей БД. С применением этого кода проводились' десятки экспериментов, реализующие ДСМ-метод автоматического порождения гипотез [2]. В настоящее время на IBM PC реализована ЭС типа ДСМ, использующая в качестве исходных данных ФКСП-коды соединений и проявляемые ими биологические активности [13]. Такое представление химического соединения посредством множества дескрипторов является булевой структурой данных. Операция сходства при этом сводится к пересечению множеств.

Преимуществом ФКСП является хорошая структурированность выдаваемых кодов, простота реализации теоретико - множественных операций и отношений (п, и, \, с, в) над объектами, а также получение результатов с меньшей долей шума, чем при работе с молекулярными графами.. По сравнению с другими дескрипторными языками ФКСП имеет ряд важных преимуществ для решаемой задачи, так как он ориентирован на фрагменты, непосредственно взаимодействующие с рецепторами, а другие языки или не отражают этого механизма (например код Весвессера), или сильно усложняют структуру данных (МСДЦ [10]).

Недостатками ФКСП являются: потеря информации при кодировании конкретных фрагментов структуры, "рассыпание" . структуры и невозможность получения полной информации о взаимном расположении фрагментов. Существенным недостатком ФКСП можно также назвать громоздкость правил кодирования, из-за чего затруднено ручное кодирование и алгоритмизация этих правил для автоматического кодирования.

Сходство на графах.

Другим способом представления объектов является представление структуры в виде молекулярного графа с помеченными вершинами и ребрами. Из-за требования хорошей структурированности данных такое представление объектов предполагает возможность определения на них полурешеточных операций сходства и вложения. В [4] были определены соответствующие операции, которые на самом деле задают на графах дистрибутивную решетку. Следует заметить, что результатом пересечения двух графов может быть не один подграф, а множество подграфов. Гипотезами при этом будут множества не вкладывающихся друг в друга подграфов.

Для реализации сходства был разработан специальный пакет программ, реализующий пересечение графов, а также определения вложения и изоморфизма графов. Программы реализованы в среде MS - DOS и WINDOWS.

Другие аналогичные программы, реализующие определение пересечения, вложения и изоморфизма графов имеются в [9]. Однако, сходство для ДСМ-решателя имеет свою специфику в обработке вершин и ребер,

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

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

Во второй главе рассматривается проблема распараллеливания основного решающего модуля ДСМ-системы. Предлагается возможная архитектура параллельной версии решателя. Приводится алгоритм распараллеливания процедуры поиска всех исчерпывающих пересечений в ДСМ-решателе.

Одним из основных этапов работы ДСМ-системы [11] является нахождение всех возможных различных пересечений на объектах каждого знака (т.е. на положительных и отрицательных примерах).

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

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

ботка, даже довольно больших выборок, занимает максимум несколько минут.

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

Поэтому появилась необходимость распараллеливания вычислений. Был проведен ряд экспериментов на четырех-транспьютерной плате фирмы MICROWAY, с транспьютерами типа Т800.

Данная плата обладала следующими характеристиками:

1) Оперативная память каждого транспьютера - 1Мб.

2) Быстродействие одного транспьютера примерно в три раза выше, чем у INTEL 80386/25.

3) Транспьютеры не имеют общей оперативной памяти, и обмен информацией возможен только через каналы связи.

4) Каждый транспьютер имеет четыре канала обмена, три из которых связаны с соседними транспьютерами. Четвертый канал у трех транспьютеров незадействован, а у четвертого - связан с PC. Этот тран-пьютер назовем корневым.

5) Транспьютерная плата вставляется в слот PC, и соединение процессора PC с корневым транспьютером происходит через систему прерываний.

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

Система коммутации PC и транспьютеров представлена на рис. 2:

рис. 2

Исходя из указанных характеристик становятся понятны требования, которым должна отвечать задача, ориентированная на транспьютер.

1) Задача может быть разбита на большие подзадачи, каждая из которых мало зависит (или лучше совсем не зависит) от другой, и требует непосредственно для себя большой временной ресурс.

2) Эта задача может быть распараллелена таким образом, чтобы простои транспьютеров были минимальны.

Ядро ДСМ-системы идеально подходит под вышеизложенные требования.

Были разработаны эффективные алгоритмы, позволяющие поставлять одновременно много пар объектов на пересечение. По мере завершения какого-либо пересечения, алгоритм, как правило, может выдавать сразу новую пару, не дожидаясь завершения остальных пересечений, находящихся в транспьютере. Кроме этого, появляется возможность использовать процессор персонального компьютера одновременно с процессорами транспьютерной платы.

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

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

В диссертации предлагается подробная архитектура параллельной версии ДСМ-решателя (схема распределения задач по транспьютерам) для 4х и 16™ транспьютерной платы. Приводится также подробное опи-

сание параллельного алгоритма поиска всех исчерпывающих пересечений на N объектах.

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

Решатель ДСМ-системы может манипулировать с относительно большими массивами (порядка 100 - 200 соединений), а для проведения большего числа ДСМ-экспериментов необходима БД, содержащая до нескольких тысяч соединений. Кодировать все соединения вручную не представляется возможным. Кроме того, дескрипторы кода ФКСП могут быть использованы в качестве классификационных и поисковых признаков в БД, содержащих значительно большее число соединений и предназначенных для других целей (не для ДСМ-системы). Вследствие этого, в рамках разработки химического интерфейса для ЭС типа ДСМ, были разработаны алгоритмические и программные средства автоматического кодирования химических структур кодом ФКСП [5].

В процессе разработки программы язык, на который происходит перевод химической структуры, несколько видоизменился.- Этот новый язык ФКСП (назовем его ФКСП-1а) частично отличается от языка ФКСП-1, описанного в [10]. Внесенные изменения в ряде случаев уточняют нестрогие и неоднозначные толкования языка ФКСП-1, который писался для ручного кодирования, а иногда и дополняют его. Изменения не затрагивают сути языка и логики его построения. Кодирование подавляющего большинства соединений вообще не будет отличаться от кодирования на языке ФКСП-1.

В диссертации описаны правила кодирования языка ФКСП-1а, которыми руководствуется программа. Приведены также все те формальные признаки, по которым программа приписывает тем или иным фрагментам структуры конкретные химические свойства: ароматичность, сопряженность и т.н.

В четвертой главе рассматривается графический редактор для ввода химических соединений, используемый для ввода исходных объектов в ЭС типа ДСМ.

Интерфейсные средства ввода исходных соединений в ЭС типа ДСМ должны обладать следующими возможностями:

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

2) Автоматическое порождение матрицы смежности или списка инце-дентности атомов и связей для каждой вводимой структуры.

3) Возможность непосредственного обмена структурами между химическим редактором и экспертной системой.

4) Встроенный контроль корректности вводимых соединений.

5) Необходимо наличие независимой от редактора программы (встраиваемой в экспертную систему) показа (визуализации) введенных соединений и их фрагментов.

В рамках настоящей работы в среде WINDOWS был создан графический химический редактор WChar [8] (Химический редактор WChar под WINDOWS является развитием химического редактора Char [12] под MS-DOS, разработанного К.П. Хазановским. Вся программная часть целиком написана заново), возможности которого существенно расширены по сравнению с требованиями, перечисленными выше.

WChar обладает следующими характеристиками и возможностями:

1) Максимальное число вводимых атомов или связей в одном соединении более трех тысяч.

2) Используются следующие виды связей:

| - одинарная, || - двойная, ||| - тройная,

4 - клинообразная (одинарная для стереохимии), | - жирная (одинарная для стереохимии),

А - штрихклинообразная (одинарная для стереохимии), 1 - штриховая (одинарная для стереохимии), j - половинная, |i - мезомерная (полуторная), f - координационная, j - слабая;

5 - одинарная волнистая (для полимеров), $ - двойная волнистая (для полимеров),

5 - тройная волнистая (для полимеров), |: - ароматическая, ||| - специальная связь для обозначения пересечения двойной и тройной связи,

- специальная связь для обозначения пересечения одинарной и двойной связи.

3) Имеется возможность ввода любых элементов таблицы Менделеева, а также, вместо элементов могут быть использованы специальные символы И, Ш, И2,113, И4,115, Ы6, М, Ъ, X, Ь, Н1 для обозначения заместителей, лигандов, галоидов, гетероатомов, металлов и неметаллов.

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

5) Имеется возможность ввода не только классических (+,-) зарядов на атомах, но и любых целочисленных, а также дробных зарядов, введенных как в виде простой, так и в виде десятичной дробей. Обыкновенная дробь используется так же, как и целочисленные заряды, для обозначения валентных зарядов. Десятичная дробь используется для обозначения реальной электронной плотности на атоме.

6) Имеется возможность ввода номеров изотопов на атомах.

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

8) Имеется возможность вставлять в вершинах (вместо символа обозначения атома) произвольный текст до 20 символов.

Таким образом, по своим возможностям редактор ЛУСЬаг достиг того состояния, когда его можно использовать не только в качестве интерфейса ввода в химически ориентированную ЭС типа ДСМ, но и для задачи ввода химических структур в БД (в том числе для массивов, содержащих рефераты статей по химии), занимающуюся регистрацией всех вновь получаемых или ранее полученных низкомолекулярных органических соединений. Редактор позволяет ввести подавляющее

большинство различных экзотических химических соединений. Исключение составляют катенаны и соли. Однако, редактор может быть доработан до того состояния, когда он сможет вводить и эти типы структур. Использование редактора для ввода в глобальные регистрационные БД возможно также и потому, что имеется комплекс программ, описанных в главе 5, для поиска вложения подструктуры в структуру, введенных редактором \У'СЬаг. Причем, этот комплекс работает для любого типа структур, вводимых редактором, включая гиперграфы, и может быть использован для поиска в БД по подструктуре.

\YChar поддерживает для редактирования многооконный интерфейс МБ1, что позволяет одновременно иметь на экране несколько различных редактируемых структур. Редактор обладает большим количеством сервисных средств, делающих ввод' весьма удобным и комфортным для пользователя. В частности, он, помимо перечисленных выше, имеет следующие средства:

1) Возможность менять длину любой ациклической связи как с большим, так и с маленьким шагом.

2) Изменение масштаба.

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

4) Запись обозначений функциональных групп как в прямом, так и в обратном порядке (-СНОН, НОНС-).

5) Имеется возможность зеркального отображения по вертикали или по горизонтали как всей редактируемой структуры, так и каждой ее отдельной связной компоненты.

6) Имеется возможность осуществлять поворот на 90° в любую сторону как всей редактируемой структуры, так и каждой ее отдельной компоненты.

7) Имеется возможность осуществить поворот ациклического ребра вокруг одной из образующих его вершин.

8) Имеется возможность вводить 3-х, 4-х, 5-ти, 6-ти, 7-ми и 8-ми членные циклы одним нажатием кнопки.

9) Имеется возможность одним нажатием кнопки менять как расположение цикла относительно задаваемого ребра, так и размер цикла.

10) Имеется возможность двигать по экрану редактирования с большим или маленьким шагом как всю редактируемую структуру, так и каждую отдельную связную компоненту.

11) Имеется возможность помещать как целиком редактируемую структурную формулу, так и каждый ее отдельный связный фрагмент во внутреннем формате редактора на WINDOWS Clipboard и вставлять его содержимое в требуемое место окна редактирования структуры, что дает возможность копировать структуры внутри редактора.

12) Имеется возможность помещать структуру в формате bitmap на WINDOWS Clipboard для того, чтобы вставлять их оттуда в различные текстовые редакторы, такие как Write, Word, Ami Pro и т.п.

13) Имеется встроенное средство расчета брутто-формулы и молекулярной массы.

14) Имеется встроенный контроль валентностей.

Редактор весьма удобен в использовании. Поясним это путем сравнения. Посчитаем количество необходимых нажатий клавишей мыши для ввода требуемого типа атома в нужную вершину для редакторов WChar и ISIS/Draw (MDL Information Systems, Inc.).

Для ввода наиболее часто употребляемых атомов (С, Н, N, О, S, Р) в редакторе WChar требуется 1-2 нажатия клавиши, а в ISIS/Draw 6-7 нажатий. Для ввода более редких типов атомов в WChar требуется от 1 до 4 нажатий, а в ISIS/Draw от 8 до 9 нажатий.

В диссертации подробно описан программный интерфейс взаимодействия редактора с ЭС или БД.

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

При подходе к решению задачи вложения подструктуры в структуру, как к составной части задачи поиска по подструктуре химического соединения в БД с большим числом разнообразных структур в формате редактора \VChar, необходимо учитывать следующее:

1) Программа поиска вложения должна уметь работать на любых структурных формулах, которые редактор ДУСЬаг позволяет ввести.

а) Число атомов и связей в структурах может быть более 3х тысяч.

б) Необходимо уметь обрабатывать гиперграфы (связи между атомом и циклом или между атомом и связью).

в) Необходимо уметь учитывать изотопы.

г) Необходимо уметь обрабатывать целые и дробные заряды на атомах.

д) Необходимо уметь обрабатывать любые типы атомов и связей, применяемых в редакторе \VChar.

2) Необходимо уметь задавать различные отношения между различными типами атомов или связей. Причем, необходимо средство, когда пользователь сам с экрана может задавать требуемые ему в настоящий момент отношения. В редакторе \VChar зарезервированы специальные обозначения"для атомов (М.Н1, X, И,...) и связей (|;, |;|, ...), которые могут использоваться в установке различных отношений при вложении.

В диссертации подробно описаны способы решения этих проблем.

Заключение по работе.

В результате настоящей работы был разработан комплекс алгоритмических и программных средств поддержки преобразования данных для химически ориентированных ЭС типа ДСМ.

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

либо свойством ("+" - объекты) и набор объектов, про которые известно, что они не обладают соответствующим свойством ("-" - объекты). Кроме этого, могут быть объекты, свойства которых требуется определить.

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

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

В химически ориентированных ЭС исходными объектами являются структурные формулы химических соединений. Для их ввода был разработан специальный графический редактор ЛУСЬаг. Редактор весьма прост в обращении и позволяет легко и удобно вводить самые разнообразные химические структуры.

В работе рассмотрено несколько способов представления данных (структурных формул).

1" способ. Структурные формулы химических соединений пред-

ставляются в виде множества дескрипторов специального проблемно ориентированного кода ФКСП [1]. В основу этого кода заложена концепция, в соответствии с которой в природе существует "язык распознавания структуры" молекулярным и рецепторами. [10].

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

использованием этой программы было закодировано более десяти тысяч соединений. На рис. 4 представлена структурная схема ЭС типа ДСМ с исходными данными в виде кодов ФКСП (для общего случая структурная схема ДСМ - системы представлена на рис. 1).

Автоматический перевод структурных формул в код ФКСП.

Операция поиска сходства на объектах (пересечение множеств].

Исходная выборка

V"объекты (химические соединения в коде ФКСП]

"объекты (химические соединения о коде ФКСП)

'т"объекты (химические соединения в коде ФКСП].

ДСМ - решатель

1ППВ - 1

^ППВ - 11 —

Средства визуализации исходных о бъ-ектов и гипотез (визуализация структурных формул и их кодов ФКСП].

База знаний

"+'Ум/ГОТеЗЫ

(фрагменты химически* соединении в коде ФКСП].

"-"гнпогезы {фрагменты химических соединении

в коде ФКСП)

рис. 4

В настоящее время под MS-DOS имеется законченная версия ЭС типа ДСМ, использующая код ФКСП в качестве способа представления данных [13]. С использованием этой ЭС были проведены десятки ДСМ-экспериментов по различным активностям и на различных выборках [2]. Эти эксперименты полностью подтвердили адекватность кода ФКСП в качестве способа представления данных для ДСМ - решателя.

Однако, ФКСП имеет ряд недостатков. При кодировании происходит потеря информации ("рассыпание" структуры), что приводит к невозможности получения полной информации о взаимном расположении фрагментов. Код ФКСП не позволяет исследователю пометить в структурной формуле интересующие его фрагменты, из-за чего сужается возможная область его применения. Подробнее недостатки кода рассмотрены в диссертации.

2й способ. Структурные формулы химических соединений пред-

ставляются в виде молекулярных графов. Основные недостатки кода ФКСП при этом снимаются. Такое представление данных не требует

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

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

рис. 5

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

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

Представление структурных формул в виде молекулярных графов является более подробной моделью описания химических соединений, чем в коде ФКСП. Следующий уровень описания химических соединений — это пространственные молекулярные графы. В настоящее время сходство на пространственных молекулярных графах для ДСМ-решателя не реализовано, однако программы поиска сходства на обычных графах могут быть отномРгельно просто переделаны для этой цели.

Для визуализации гипотез, порожденных в результате работы ДСМ - решателя с исходными данными в виде кодов ФКСП, разработана специальная программа обратного декодирования из фрагмента кода в подструктуру. Для этой программы при прямом кодировании сохраняются номера атомов, образующих каждый конкретный дескриптор.

Разработаны специальные средства визуализации гипотез, порожденных в результате работы ДСМ - решателя с исходными данными в виде молекулярных графов.

Для ускорения работы ДСМ - решателя, при реализации операции сходства в виде пересечения графов, был предложен алгоритм распараллеливания его основного модуля и были проведены эксперименты на 4* - транспьютерной плате фирмы МЮНСМЛАУ, подтверждающие возможность его реализации.

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

Вцелом, разработанные алгоритмические и программные средства охватывают необходимый комплекс проблем, касающихся преобразования данных для химически ориентированных ЭС типа ДСМ, начиная вводом исходных данных в систему, перекодирования их в требуемый вид, обработки внутренних данных, а также выводом промежуточных и окончательных результатов.

Литература

[1] Авидон В.В., Лексина Л.А //НТИ.сер.2. 1974. № З.С.22.

[2] Блинова В.Г. О результатах применения ДСМ - метода порождения гипотез к задачам анализа связи "структура химического соединения - биологическая активность". НТИ // сер. 2. 1995. № б

[3] Забежайло М.И., Лейбов А.Е., Мельников Н.И., Панкратова Е.С. СВИ-технология в задаче контроля потенциально опасных свойств химических соединений. //IV Национальная конференция с международным участием "Искусственный интеллект - 94", Рыбинск, 1994, том-2, С.271-278.

[4] Кузнецов С.О. О решетке на множествах графов с частично упорядоченными пометками. // Тезисы докладов школы семинара "Семиотические аспекты формализации интеллектуальной деятельности", Боржоми, 1988. - М., ВИНИТИ, 1988. т.1. - С.204-207.

[5] Лейбов А.Е. Автоматическое кодирование химических структур кодом ФКСП // Итоги науки и техники. Сер. Информатика Т. 15. (Интеллектуальные информационные системы) - М.:ВИНИТИ, 1991. С.141-158.

[6] Лейбов А.Е. Алгоритмы преобразования графов, используемые для правдоподобных выводов и интеллектуального интерфейса в экспертных системах. // В кн. II Всесоюзная конференция "Искусственный интеллект - 90", Минск, 1990.- Т.1 - С.141-143.

[7] Лейбов А.Е., Блинова В.Г. Автоматическое кодирование химических соединений в коде ФКСП (фрагментарном коде суперпозиции подструктур) // В кн. VIII Всесоюзная конференция "Использование вычислительных машин в спектроскопии молекул в химических исследованиях", Новосибирск, 1989. С.180-181.

[8] Лейбов А.Е. Программные инструменты представления знаний для решателей задач типа "правдоподобный вывод + достоверный вывод" в предметных областях со сложно структурированными объектами. // IV Национальная конференция с международным участием "Искусственный интеллект - 94", Рыбинск, 1994, том-2, С.278-281.

печепуренки 4_..ivi. иинкии о.ал-, типш'ашев v^.ivi. n др. rijjivynj iviui

и программы решения задач на графах и сетях НОВОСИБИРСК: Наука. Сиб. отделение, 1990.

[10] Розенблит А.Б., Голендер В.Е. Логико-комбинаторные методы в конструировании лекарств. - Рига: Зинатне, 1983.г.

[11] Финн В.К Правдоподобные рассуждения в интеллектуальных системах типа ДСМ. // Итоги науки и техники. Сер. Информатика Т.15. (Интеллектуальные информационные системы) -М.:ВИНИТИ, 1991. С.54-101.

[12] Хазановский КП. Графический редактор химических структур CHAR как средство создания новых программных систем по химии // Итоги науки и техники. Сер. Информатика Т.15. (Интеллектуальные информационные системы) - М.'.ВИНИТИ, 1991. С.136-140.

[13] Хазановский К.П. "Программные системы для баз знаний с неполной информацией", Диссертация защищенная в ВИНИТИ, Специальность 05.13.17., 1990, с. 60-65.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Забежайло М.И., Лейбов А.Е., Мельников Н.И., Панкратова Е.С. СЕШ-технология в задаче контроля потенциально опасных свойств химических соединений. // IV Национальная конференция с международным участием "Искусственный интеллект - 94", Рыбинск, 1994, том-2, С.271-278.

2. Лейбов А.Е. Автоматическое кодирование химических структур кодом ФКСП // Итоги науки и техники. Сер. Информатика Т. 15. (Интеллектуальные информационные системы) - М.:ВИНИТИ, 1991. С.141-158.

3. Лейбов А.Е. Алгоритмы преобразования графов, используемые для правдоподобных выводов и интеллектуального интерфейса в экспертных системах. // В кн. II Всесоюзная конференция "Искусственный интеллект - 90", Минск, 1990.- Т.1 - С.141-143.

4. Лейбов А.Е., Блинова В.Г. Автоматическое кодирование химических соединений в коде ФКСП (фрагментарном коде суперпозиции подструктур) // В кн. VIII Всесоюзная конференция "Использование вычислительных машин в спектроскопии молекул в химических исследованиях", Новосибирск, 1989. С.180-181.

5. Лейбов А.Е. Программные инструменты представления знаний для решателей задач типа "правдоподобный вывод + достоверный вывод" в предметных областях со сложно структурированными объектами. //IV Национальная конференция с международным участием "Искусственный интеллект - 94",'Рыбинск, 1994, том-2, С.278-281.