автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Программная система генерации молекулярных графов с использованием метрик на графах

Введение.

Глава 1. Программные системы генерации молекулярных графов.

§1. Методы и программные системы генерации молекулярных графов.

1.1. Генерация по брутто-формуле.

1.2. Генерация по основе и списку заместителей.

§2. Базовые программные средства для работы с графами.

§3. Объектно-ориентированные библиотеки для работы с графами.

3.1. Преимущества объектно-ориентированного программирования при создании библиотек для работы с графами.

3.2. Существующие объектно-ориентированные библиотеки для работы с графами.

§4. Особенности объектно-ориентированных библиотек для работы с графами.

4.1. Внутреннее представление графов в оперативной памяти ЭВМ.

4.2. Привязка атрибутов к вершинам и ребрам графа.

4.3. Поддержка различных видов графов.

Выводы.

Глава 2. Генерация молекулярных графов с использованием метрик на графах

§ 1. Метод генерации.

1.1. Постановка задачи.

1.2. Общая схема генерации.

1.3. Построение метрики.

1.4. Эволюционный алгоритм.

§2. Варианты совершенствования метода генерации.

2.1. Селекция метрик на основе генетического алгоритма.

2.2. Совершенствование эволюционного алгоритма генерации.

Выводы.

Глава 3. Библиотека классов для работы с помеченными графами.

§ 1. Актуальность разработки библиотек для работы с графами.

§2. Библиотека AGraph.

2.1. Общая характеристика.

2.2. Библиотека Vectors.

2.3. Внутреннее представление графов.

2.4. Базовые средства.

2.5. Использование атрибутов.

2.6. Поддержка различных видов графов.

2.7. Алгоритмы, реализованные в библиотеке АОгарЬ.

2.8. Тестирование средств библиотеки.

2.9. Ввод/вывод графов.

2.10. Создание специализированных классов графов.

2.11. Эффективность реализации.

Выводы.

Глава 4. Программная система генерации молекулярных графов МоЮеп.

§ 1. Программа генерации.

1.1. Функциональные возможности программы генерации.

1.2. Использование программы генерации при решении обратной ККСС-задачи.

1.3. Основные программные модули и классы программы генерации.

1.4. Обеспечение бесповторности генерации и способ хранения сгенерированных структур.

§2. Редактор молекулярных графов.

§3. Программа визуализации молекулярных графов.

§4. Результаты опытной эксплуатации системы МоЮеп.

Выводы.

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

Одним из быстро развивающихся научных направлений является разработка методов поиска количественных корреляций "структура-свойство" — ККСС-моделирование (или (^АН-моделирование) [1-5]. К настоящему времени созданы программные системы, позволяющие автоматизировать построение ККСС-моделей. После построения модели возникает задача нахождения химических структур, которые можно назвать "активными в рамках построенной модели прогноза" (обратная ККСС-задача) [6]. ККСС-модель, получив на входе такую структуру, должна выдать высокое значение активности. Поскольку построенная модель прогноза, как правило, является нелинейной многопараметрической функциональной зависимостью либо объединением нескольких функциональных зависимостей, практическое решение обратной задачи осуществляется путем скрининга ("просеивания" через математическую модель) химических соединений — "кандидатов" на активные структуры [7]. Химические соединения для скрининга могут браться из существующих баз данных, либо, если ставится задача нахождения новых активных соединений, должны каким-то образом генерироваться. Генератор, используемый для скрининга, должен удовлетворять противоречивым условиям. С одной стороны, ограниченные вычислительные ресурсы заставляют сужать множество структур, подаваемых на вход ККСС-модели. С другой стороны, желательно получать соединения не только известных классов, но и принципиально новые. Таким образом, актуальной является разработка новых методов генерации и, на их основе, программных систем, которые порождают неизвестные, но в то же время "потенциально активные" структуры (модель прогноза, получив на вход такую структуру, с большой вероятностью выдаст высокое значение её активности). Предлагаемый в работе метод генерации отвечает поставленным условиям в большей степени, чем другие известные методы.

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

Целью работы являлась автоматизация решения обратной задачи поиска количественных корреляций "структура-свойство": разработка метода генерации молекулярных графов, ориентированного на решение обратной ККСС-задачи, и его программная реализация на основе объектно-ориентированной библиотеки обработки помеченных графов.

В соответствии с этим в работе были поставлены и решены следующие задачи:

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

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

3. На основе библиотеки классов разработаны программы эволюционной генерации молекулярных графов, визуализации и редактирования графов.

Научная новизна работы:

1. Разработан и реализован новый метод генерации молекулярных графов.

2. Создана новая объектно-ориентированная библиотека обработки помеченных графов.

Основные результаты диссертации изложены в 6 работах и 1 статья сдана в редакцию журнала "Программирование". Результаты докладывались на Международной конференции по эволюционным вычислениям и их приложениям (EvCA'96, Москва), Российско-германском открытом семинаре "Распознавание образов и понимание изображений" (1996, Валдай), Международной конференции "Распознавание образов и обработка информации" (PRIP'97, Минск), семинаре "Автоматизация программирования" (под руководством проф. М.Р.Шура-Бура, 1999), семинаре "Компьютерная химия" (под руководством академика Н.С.Зефирова, 1999), 9-ой Всероссийской конференции по математическим методам распознавания образов (ММРО-9).

Работа была частично поддержана Российским фондом фундаментальных исследований по грантам 96-01-01598, 97-07-90307 и 98-01-00324.

Разработанная программная система генерации молекулярных графов внедрена и используется в лаборатории математической химии Института Органической Химии им. Н.Д.Зелинского РАН, а также на кафедре органической химии Химического факультета МГУ им.М.В.Ломоносова. Созданная библиотека классов AGraph для работы с помеченными графами свободно доступна в исходных текстах в глобальной сети Интернет1.

Диссертация состоит из введения, четырех глав основного текста, заключения и приложений.

Выводы

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

Глава 4. Программная система генерации молекулярных графов MolGen

Алгоритм генерации молекулярных графов с использованием метрик был реализован в программной системе MolGen [50-51]. В состав программной системы входит программа генерации молекулярных графов, программы ввода молекулярных графов (графический редактор молекулярных графов) и визуализации результатов. В главе /описаны функциональные возможности программ, входящих в систему MolGen, порядок использования программы генерации при решении обратной ККСС-задачи, существенные детали ее реализации. Пользовательский интерфейс программ описан в приложении 1.

§1. Программа генерации

Центральной частью программной системы MolGen является программа генерации, реализующая предложенный алгоритм генерации молекулярных графов. Программа написана на языке Object Pascal в среде быстрой разработки программ Delphi 3.0. При создании программы широко использовались средства библиотек Vectors и AGraph. Ниже будут рассмотрены вопросы применения программы генерации для решения обратной ККСС-задачи, ее внутренняя структура (основные программные модули и классы), особенности реализации.

1.1. Функциональные возможности программы генерации

На вход программы поступают две структуры — стартовая и притягивающая. Программа обеспечивает диалоговый выбор этих структур, а также их визуализацию (см. рис.5).

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

Рис. 6. Форма настройки параметров генерации.

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

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

I Generation Info Е3|

Step: (||1|

Structures generated яИЯМИИИИИ

Structures selected:

Distance to goal: 14 247806848775

Time elapsed. Ill

Cancel I

Рис. 7. Информационное окно программы-генератора.

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

1.2. Использование программы генерации при решении обратной ККСС-задачи

При решении обратной ККСС-задачи программа генерации применяется совместно с программной системой прогнозирования свойств химических соединений. Примерами систем прогнозирования являются OASIS [52], BIBIGON MATCH (Basic Instrument for Building Interactive Generation of Optimized Networks of Marked ATom Chains) и ChemAdd [53].

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

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

2. одна из этих структур загружается в программу-генератор в качестве стартовой структуры, другая — в качестве притягивающей;

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

4. осуществляется генерация структур с заданными параметрами;

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

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

7. полученные структуры подаются на вход программной системы прогнозирования свойств химических соединений; если среди них будут найдены структуры, активные в рамках используемой модели прогноза, то они будут являться решением обратной ККСС-задачи.

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

1.3. Основные программные модули и классы программы генерации

Генерация молекулярных графов с использованием метрик на графах и эволюционного алгоритма реализована в модуле GenMol. В данном модуле определены классы TGenMol и TMolGenerator, которые играют основную роль в ходе генерации.

Класс TGenMol предназначен для хранения молекулярных графов, участвующих в процессе генерации. Для хранения собственно молекулярного графа используется поле Mol (это объект класса TChemGraph). Вместе с молекулярным графом хранится его структурный спектр, информация об операции, исfunction SubdivideEdge(Edgelndex: Integer): TGenMol; {TIV2} function RenameEdge(Edgelndex: Integer; BondType: Int8): TGenMol; {TRE} function MoveEdge(Edgelndex, Vertexlndexl, Vertexlndex2: Integer): TGenMol; {TME} end;

Пример 11. Описание класса TGenMol.

Элементарные операции над молекулярными графами реализованы как методы-функции класса TGenMol. Параметры функций зависят от конкретной операции: это могут быть номера атомов и ребер, которые участвуют в операции, типы связи и т.п. Результатом каждой из этих функций является либо новый объект класса TGenMol — потомок графа, к которому применяется данная элементарная операция, либо nil, если элементарная операция неприменима к графу (например, потому, что в результате ее применения происходит нарушение валентности атомов или потеря связности молекулярного графа). Таким образом, проверка применимости элементарной операции возлагается на сам объект класса TGenMol — молекулярный граф. Благодаря этому упрощается реализация класса TMolGenerator, добавление в систему новых элементарных операций и модификация поведения существующих операций.

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

Класс TMolGenerator инкапсулирует собственно генератор молекулярных графов. Его конструктор принимает в качестве параметров два объекта класса TChemGraph, представляющих, соответственно, стартовую и притягивающую структуры. Метод Execute осуществляет генерацию и возвращает True или False в зависимости от того, была ли достигнута притягивающая структура. type

TMolGenerator = class protected

SourceMol, DestinMol: TChemGraph; function Generate(GenMoll, GeriMol2: TGenMol; GenPath: TClassList): Bool; public

Paused, Stopped: Bool;

Step, NumGenerated, NumSelected: Integer; InitialDistance, CurrentDistance: Float;

ResultList: TMultiList; {

TAutoFreeClassList, , , TGenlnfo; constructor Create(ASourceMol, ADestinMol: TChemGraph); destructor Destroy; override; function Execute(GenPath: TClassList): Bool;

True,

DestinMol , False - ;

GenPath <> nil,

TChemGraph) ,

ASourceMol ADestinMol (ASourceMol /

ADestinMol - ; ;

AttrOperation, , end;

Пример 12. Описание класса TMolGenerator.

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

1.4. Обеспечение бесповторности генерации и способ хранения сгенерированных структур

Наиболее существенной проблемой, возникающей при генерации структур, является обеспечение бесповторности генерации, т.е. проверка того, что очередная сгенерированная структура С не изоморфна ни одной из ранее полученных структур {С*}. Для полного решения данной проблемы необходимо было бы хранить список отобранных структур всех шагов. Такой подход, однако, привел бы к неоправданно высоким требованиям к объему оперативной памяти ЭВМ, либо, в случае использования внешней памяти, к значительному замедлению процесса генерации. В программе-генераторе применяется компромиссный подход: в памяти хранятся структуры, сгенерированные на текущем и предыдущем шагах генерации, и только они используются при проверке "уникальности" очередной сгенерированной структуры. Таким образом, гарантируется отсутствие изоморфных структур в пределах двух шагов генерации. Практика показала, что, хотя данный подход не гарантирует отсутствие повторов, вероятность появления изоморфных структур мала.

Проверка на то, что структура С не изоморфна ни одной из хранящихся в памяти структур {в*}, осуществляется не более чем в два этапа. На первом этапе вычисленное расстояние с1(С,Ст) между С и притягивающей структурой сравнивается с аналогичными расстояниями с1(С*,Ст). Расстояние до притягивающей структуры является достаточно сильным инвариантом: в большинстве случаев оказывается, что расстояния не равны, и, следовательно, структура С не изоморфна ни одной из структур {в*}. Если же с1(С,Ст)=с1(С|*,Ст) для некоторых С|*е{С*}, то начинается второй этап с использованием точного алгоритма распознавания изоморфизма помеченных графов.

Благодаря тому, что программе генерации достаточно хранить только структуры текущего и предыдущего шагов генерации, становится возможным использовать простой и эффективный способ хранения полного списка отобранных структур: фактически в памяти хранится список списков (мультисписок) объектов класса ТСеп1пГо (поле КевиМлв! класса ТМоЮепега(;ог), где каждый список соответствует одному шагу генерации. Объекты ТСеп1п1х> содержат числовые идентификаторы данной структуры и структуры-"родителя", а также код и параметры операции, примененной к "родителю" для получения данной структуры, поэтому расход памяти для их хранения невелик. При сохранении в файл общего списка отобранных структур или последовательности структур, образующих путь минимальной длины в пространстве молекулярных графов, программа "на ходу" восстанавливает сгенерированные структуры, начиная со стартовой, используя информацию, хранящуюся в объектах ТСеп1Мо (это возможно благодаря тому, что все реализованные в ТСепМо1 элементарные операции являются детерминированными).

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

§2. Редактор молекулярных графов

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

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

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

Ввод молекулярных графов в программной системе MolGen обеспечивается редактором Molecular Editor (для ввода могут быть использованы и другие редакторы, поддерживающие стандартный MOL-формат). Редактор Molecular Editor первоначально разрабатывался с использованием системы программирования Borland Pascal 7.0 и библиотеки Object Windows 2.0, затем — в среде быстрой разработки программ Delphi 1.0. При создании данного редактора учитывался опыт использования других редакторов молекулярных графов, в том числе ChemBase из пакета Chemist's Personal Software Series, ISIS/Draw и ISIS/Base (MDL Information System; http://www.mdli.com). ChemWindow (BioRad Sadtler [formerly SoftShell]; http://www.softshell.com). а также рекомендации профессиональных химиков. Модифицированные варианты Molecular Editor интегрированы в ряде программных продуктов фирмы Advanced Chemistry Development Inc. (http://www.acdlabs.com). в том числе в распространяемом бесплатно редакторе ACD/ChemSketch [54-55].

К достоинствам редактора Molecular Editor относится:

• современный графический интерфейс (см. рис.8-9), интуитивно понятный для пользователя-химика;

• поддержка стандартного коммуникативного формата записи молекулярных графов (MOL-формат);

• обнаружение некоторых ошибок ввода и автоматическая корректировка атрибутов атомов при изменении структуры;

• поддержка использования стандартных "заготовок молекул" — шаблонов.

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

§3. Программа визуализации молекулярных графов

Программа визуализации молекулярных графов Chem Viewer обеспечивает удобный просмотр сгенерированных структур. Chem Viewer позволяет загружать как отдельные структуры из MOL- и GML-файлов, так и наборы структур из SDF- и GML-файлов. При загрузке файлов, сохраненных программой генерации, Chem Viewer отображает в строке статуса информацию о том, в результате какой элементарной операции была получена текущая структура (см. рис.10). При необходимости пользователь может включить режим автоматического рисования структур (эта возможность реализована с использованием внешней библиотеки). Как и программа генерации, Chem Viewer был разработан в среде Delphi 3.0 с использованием библиотеки AGraph.

Заключение

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

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

На основе библиотеки АвгарЬ была разработана программная система генерации молекулярных графов МоЮеп. В состав системы входит программа генерации молекулярных графов, программы ввода молекулярных графов (графический редактор молекулярных графов) и визуализации результатов. Программа генерации реализует один из вариантов описанного в работе метода генерации. При решении обратной ККСС-задачи программа генерации должна применяться совместно с программной системой прогнозирования свойств химических соединений. Программа ввода молекулярных графов обеспечивает ввод и редактирование химических структур. Программа визуализации результатов предназначена для просмотра полученных в ходе генерации молекулярных графов.

Программная система генерации молекулярных графов МоЮеп внедрена и используется на кафедре органической химии Химического факультета МГУ, а также в лаборатории математической химии Института Органической Химии им.Н.Д.Зелинского РАН. Библиотека АвгарЬ свободно доступна в исходных текстах в глобальной сети Интернет.

1. Джуре О.П., Айзенауэр Т. Распознавание образов в химии / Пер. с англ. — М., Мир, 1977, 248 с.

2. Стьюпер Э., Брюггер У., Джуре П. Машинный анализ связи химической структуры и биологической активности. — М., Мир, 1982, 235 с.

3. Kier L.B., Hall L.H. Molecular connectivity in structure-activity analysis / Wiley, London, 1986.

4. Химические приложения топологии и теории графов. Под ред. Кинга Р. / Пер. с англ. — М., Мир, 1987, 560 с.

5. Искусственный интеллект: применение в химии/Под ред. Пирса Т., Хони Б. / Пер. с англ. — М., Мир, 1988, 430 с.

6. Баскин И.И., Гордеева Е.В., Девдариани Р.О., Зефиров Н.С., Палюлин В.А., Станкевич М.И. Методология решения обратной задачи в проблеме структура-свойство для некоторых топологических индексов / ДАН АН СССР, 1989, т. 307, с. 613-617.

7. Зыков А.А. Теория конечных графов. — Новосибирск: Наука, 1969.

8. Харари Ф. Теория графов. — М., Мир, 1973, 300 с.

9. Станкевич И.В. Графы в структурной химии / В сб.: Применение теории графов в химии. Под ред. Н.С.Зефирова, С.Н.Кучанова. Новосибирск, Наука, 1988, с.7-69.

10. Молодцов С.Г., Пиоттух-Пелецкий В.Н. Конструирование неизоморфных графов по данному набору структурных параметров. В сб. "Алгоритмы анализа структурной информации", Вычислительные системы, Новосибирск, т. 103, 1984, с. 51.

11. Lomova О.А., Sukhachev D.V., Kumskov M.I., Palyulin V.A., Tratch S.S., Zefi-rov N.S. The Génération of Molecular Graphs for QSAR Studies by theAcyclic fragment combining / Commun. Mathem. Chem. (MATCH), 1992, n.27, p.153-174.

12. Т. Wieland, А. Kerber, R. Laue. Principles of the generation of constitutional and configurational isomers / to appear in J. Chem. Inf. Comput. Sei.http •■//www.mathe2.uni-bayreuth.de/mo1gen/PRINCIPL/principl.htmn.

13. MolchanovaM.S., Shcherbukhin V.V., Zefirov N.S. Computer Generation of Chemical Structures by the SMOG program/J. Chem. Inf. Comput. Sei., 1996, vol.36, no.4, pp.888-899.

14. Mityushev D.F., Kumskov M.I. An Integrated Software System to Predict Properties of Chemical Compounds on a Personal Computer /Pattern Recognition and Image Analyses, 1996, v.6, n.4, p.809-822.

15. Чернобаев А. AGraph: библиотека классов для работы с помеченными графами / Программирование (сдана в редакцию).

16. Нечепуренко М.И., Попков В.К., Майнагашев С.М. и др. Алгоритмы и программы решения задач на графах и сетях. — Новосибирск, Наука (сибирское отделение), 1990.

17. Stroustrup В. The С++ Programming Language, Third Edition / Addison-Wesley, 1998.

18. Mehlhorn К., Näher St. The LED A Platform of Combinatorial and Geometric Computing. — Cambridge University Press, 1999.

19. Plauger P.J., Stepanov A., Lee M., Musser D. The Standard Template Library / Prentice-Hall, 1998.

20. Цыпнятов Е. Библиотека классов для программирования задач теории графов, дипломная работа. — Нижний Новгород, 1998.

21. Kumskov M.I., Chernobaev A. A., Mityushev D.F. The Generation of Marked Molecular Graphs Using Evolutionary Programming and Graph's Metrics /Proc. 1st Intern. Conf. on Evolutionary Computation and Its Application (EvCA'96), Moscow, 1996, p.321-329.

22. Kumskov M.I., Chernobaev A.A., Mityushev D.F. The Generation of Labeled Molecular Graphs Using Metrics and Evolutionary Programming / Pattern Recognition and Image Analysis, 1997, v.7, n.l, p.70-75.

23. Зыков А.А. Основы теории графов. — М.: Наука, 1987.

24. Константинова Е.В., Скоробогатов В.А. Структурные и численные инварианты обыкновенных и молекулярных графов / Математические методы в химической информатике. — Новосибирск, 1991. — Вып. 140: Вычислительные системы, с.87-129.

25. Букатова И.Л. Эволюционное моделирование и его приложения. — Москва: Наука, 1979.

26. Davis L. Handbook of genetic algorithms / Van Nostrand Reinhold, New York, 1991.

27. Fogel D.B. Applying evolutionary programming to selected control problems / Comput. Math. Applic., 1994, vol.27, no.ll, p.89-104.

28. Object Pascal Language Guide. Borland Delphi 3 for Windows 95 and Windows NT— Borland International Inc., 1997.

29. Скоробогатов В.А. Алгоритмический анализ молекулярных графов. (Основы метрического анализа) / Новосибирск, НГУ, 1988, 84 с.

30. Balaban А.Т. Highly Discriminating Distance-Based Topological Index. / Chem. Phys. Lett., 1982, v.80, p.399-404.

31. Цой С., Цхай C.M. Прикладная теория графов. —Алма-Ата: Наука, 1971.

32. Басакер Р., Саати Т. Конечные графы и сети. — М.: Наука, 1974.

33. Кристофидес Н. Теория графов. Алгоритмический подход. — М., Мир, 1978.

34. Майника Э. Алгоритмы оптимизации на сетях и графах. — М., Мир, 1981.

35. Ловас JL, Пламмер М. Прикладные задачи теории графов. Теория паросоче-таний в математике, физике, химии/Пер. с англ. — М., Мир, 1998, 635 с.

36. Cordella L.P., Foggia P., Sansone С., Vento M. An Efficient Algorithm for the Inexact Matching of ARG Using a Contextual Transformational Model / Proc. of the 13th ICPR, IEEE Computer Society Press, 1996, vol.III, pp. 180-184.

37. Mehrotra A., Trick M.A. A Column Generation Approach for Exact Graph Coloring / INFORMS Journal on Computing, 8:4,1996.

38. Meyer B. Object-Oriented Software Construction / Prentice Hall, 1997.

39. Himsolt M. GML: A Portable Graph File Format / Technical Report, Universität Passau, 1997, cf. (http://infosun.fini.uni-passau.de/Graphlet/GML/index.html).

40. Description of Several Chemical Structure File Formats Used by Computer Programs Developed at Molecular Design Limited / J. Chem. Inf. Comput. Sei. 1992, 32, 244-255.

41. Чернобаев А.А., Кумсков М.И. Программа-генератор для решения обратной задачи распознавания молекулярных графов /Ргос. Fourth International Conf. "Pattern Recognition and Information Processing" (PRIP'97), Minsk, Belarus, 1997, v.2, p.311-315.

42. Mekenyan О., Karabunarliev S., Bonchev D. The microcomputer OASIS system for predicting the biological activity of chemical compounds / Сотр. Chem., 1990, V. 14, p. 193-200.

43. Митюшев Ф. Программная система прогнозирования свойств химических соединений, диссертация. — Москва, 1998.

44. Fred A. Turner. ACD/ChemSketch and ACD/CNMR 2.0: Software Review ACD/Labs / The Chemistry Bulletin, 1996, November, p.30.

45. Gary O. Spessard. ACD Labs/LogP dB 3.5 and ChemSketch 3.5 / J. Chem. Inf. Comput. Sci., Vol. 38, No. 6,1998.