Генерирование молекулярных графов с заданными структурными ограничениями

• Автор: Молодцов, Сергей Георгиевич
• Шифр специальности: 05.13.16
• Научная степень: Кандидатская
• Год защиты: 1997
• Место защиты: Новосибирск
• Количество страниц: 79 с.

Содержание
Введение

Глава 1. Алгоритмы генерации графов

1.1. Генерация неупорядоченных графов .

1.1.1. Простые алгоритмы генерации структур.

1.12. Генераторы структур в системе X

1.1.3. Генератор структур

1.1.4. Другие алгоритмы генерации неупорядоченных графов

1.2. Генерация канонических графов.

12.1. Алгоритм построения полного набора структурных

формул
122. Генератор структур в системе I.
12.3. Генерирование неизоморфных графов с заданным
распределением степеней вершин
12.4. Другие алгоритмы генерации канонических графов .
Глава 2. Алгоритм генерации молекулярных графов
2.1. Определения.
2.2. Алгоритм генерации .
2.3. Особенности программной реализации алгоритма
2.3.1. Проверка связности генерируемых графов.
2.32. Построение различных множеств вершин для
генерации распределение Нвершин. . . . .
2.3.3. Упорядочивание классов вершин
2.3.4. Задание обязательных кратностей ребер .
2.3.5. Оценка числа генерируемых графов.
2.3.6. Генерация молекулярных графов
2.3.7. Генерация регулярных графов
Глава 3. Генерация молекулярных графов с заданным
набором непересекающихся фрагментов
3.1. Постановка задачи .
3.2. Определения
3.3. Учет простых фрагментов
3.4. Учет средних фрагментов
3.5. Учет сложных фрагментов
3.6. Результаты генерации структур с заданными фрагментами
Глава 4. Использование программы генерации молекулярных
графов при решении исследовательских задач
4.1. Установление строения синтезированного соединения
4.2. Генерирование и ранжирование структур в массспектрометрической системе установления строения соединений . .
4.3. Выбор исходных данных для генерирования структур
Выводы
Литература


В свою очередь структурная формула может быть представлена с помощью молекулярного графа: мультиграфа, помеченные вершины которого соответствуют атомам и фрагментам, а кратные ребра — типам связей химического соединения. Неслучайно, еще в году Кэли, занимаясь перечислением насыщенных углеводородов СпНап+а-открыл класс графов, называемый сегодня деревьями. Более того, впервые термин граф появился в статье Сильвестра «Химия и алгебра» [1]. Потребность в генерации графов в этой области знания ощущается постоянно. Она возникает при формировании возможных гипотез о строении соединения на основе экспериментальных данных, выявленных, например, по молекулярным спектрам [2]; при поиске структур соединений, гипотетически обладающих заданным свойством [3]; при установлении конечных продуктов реакции, прогнозировании пути ее протекания и т. Наиболее эффективный путь, гарантирующий исчерпывающее решение этой задачи, подразумевает использование ЭВМ. Гарантия исчерпывания: построение всех различных (неизоморфных) графов, отвечающих заданным ограничениям. Минимизация дублирования: в идеале алгоритм не должен строить изоморфные графы. Если этого не удается достигнуть, то должны быть предприняты специальные меры для уменьшения дублирования. Эффективность генерирования: желателен анализ перспективности движения по дереву поиска, каждый узел которого соответствует какому-либо шагу построения молекулярного графа. Алгоритм должен как можно раньше заметить, что любые последующие шаги не приведут к искомому результату. Соответствие ограничениям: алгоритм должен использовать ограничения в форме, удобной для пользователя. Эффективность использования ограничений: заданные ограничения должны сокращать время генерации, а не использоваться при выборе из построенных графов тех, которые соответствуют ограничениям. Настоящая диссертационная работа посвящена разработке и реализации эффективного алгоритма генерации всех связных молекулярных графов (их канонических матриц смежности) из множества помеченных вершин с заданной валентностью, содержащих заданный набор непересека-ющихся фрагментов. Актуальность этой проблемы обусловлена, с одной стороны, существующим и до сих пор не удовлетворенным массовым спросом на ее решение в традиционной химической практике: построение всех возможных продуктов реакции при заданных ограничениях; генерирование гипотез о строении соединения с учетом всех выявленных или постулированных данных: прогнозирование структур с требуемым химическим, физическим или иным свойством и т. С другой стороны — быстрым развитием компьютерных методов в химии, способствующих решению подобных задач средствами ЭВМ. Наиболее яркими примерами последних являютс я системы искусственного интеллекта, компьютерного синтеза. При решении подобных задач роль программной компоненты, выполняющей в ограниченное время эффективную, исчерпывающую генерацию требуемых молекулярных графов, трудно переоценить. Построение полных списков графов с заданными характеристиками имеет и самостоятельное практическое значение. Такие списки, в частности. Целью работы являлось создание эффективного алгоритма и программы генерации из множества помеченных вершин с заданной валентностью всех связных молекулярных графов, содержащих заданный набор непере-секающихся фрагментов. Разработка эффективного алгоритма генерации неизоморфных молекулярных графов из множества помеченных вершин с заданной валентностью. Разработка способа задания информации о фрагментах, обеспечивающего эффективное построение всех молекулярных графов, содержащих заданный набор непересекающихся фрагментов. Создание программы, реализующей разработанный алгоритм, апробация ее и исследование применимости при решении некоторых прикладных задач. Разработан эффективный алгоритм генерации неизоморфных молекулярных графов (их канонических матриц смежности) из множества помеченных вершин с заданной валентностью. Введение ограничений на кратности ребер между вершинами дает возможность более целенаправленной генерации молекулярных графов, а предложенный алгоритм проверки сильной каноничности частично-заполненных матриц ускоряет ее выполнение.