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

^ РОССИЙСКАЯ АКАДЕМИЯ НАУК ^ СИБИРСКОЕ ОТДЕЛЕНИЕ

^ ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

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

МОЛОДЦОВ Сергей Георгиевич

ГЕНЕРИРОВАНИЕ МОЛЕКУЛЯРНЫХ ГРАФОВ С ЗАДАННЫМИ СТРУКТУРНЫМИ ОГР АНИЧЕНИЯМИ

05.13.1С — применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук-

Новосибирск — 1997

Работа выполнена в Научно-техническом центре по химической информатике Новосибирского института органичесой химии СО РАН.

Научный консультант: доктор химических наук,

профессор Б.Г. Дерендяев

Официальные оппоненты: доктор физ.-мат. наук

профессор В. А. Евстигнеев

кандидат технических наук

Е.В. Константинова

Ведущая организация: Новосибирский государственный

университет

Защита состоится " 21 " октября 1997 года в 14"''° часов на заседании диссертационного совета Д002.10.02 при Вычислительном центре СО РАН по адресу: 630090, Новосибирск, пр. академика Лаврентьева, 6.

С диссертацией можно ознакомиться в библиотеке ВЦ СО РАН.

Ч ■< сенгл<у>я

Автореферат разослан '' 1С "CéV/fjе.6Ь2 1997 г.

Ученый секретарь дпс< ертацпонноп) совета

Г.И.Забнняко

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Задача генерации графов заданного класса важна как в комбинаторном анализе, так II при решении прикладных проблем в различных областях знания, например, в химии, где структурные формулы соединений могут быть представлены молекулярными графами. В этой области эффективная генерация молекулярных графов необходима, с одной стороны, для традиционной химической практики при формировании гипотез о строении соединения с учетом выявленных данных; прогнозировании структур с заданными свойствами; построении всех возможных продуктов реакции н т. п. С другой стороны, не менее актуально развитие алгоритмов генерации графов для совершенствования компьютерных методов в химии, способствующих решению подобных задач. Наиболее яркие примеры: системы искусственного интеллекта, компьютерного синтеза, помощи исследователю при установлении строения соединений по молекулярным спектрам. При их реализации роль программной компоненты, выполняющей в ограниченное время эффективную, исчерпывающую генерацию требуемых молекулярных графов, трудно переоценить.

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

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

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

Практическая ценность работы определяется тем. что на основе

предложенного алгоритма генерации молекулярных графов разработана программа GENM, которая включена в состав систем для установления строения органических соединении по молекулярным спектрам: КОМПАС п CliemArt (НИОХ СО РАН, Новосибирск), РАСТР (ВНИИОС, Москва). Программа GENM может использоваться и как средство пользователя (химика, математика), и как необходимый инструментарий, позволяющий выдвигать и проверять новые приемы в решении прикладных химических задач.

Апробация работы. Основные результаты работы представлены на на VI и VIII Всесоюзных конференциях «Использование вычислительных машин в спектроскопии молекул и химических исследованиях» (Новосибирск. 1983. 1989), III Всесоюзном совещании «Методы и программы решения оптимизационных задач на графах и сетях» (Ташкент, 1984), II Всесоюзной конференции «Математические методы п ЭВМ в аналитической химии» (Москва, 1991), IX Всесоюзной конференции «Химическая информатика» (Черноголовка, 1992), II Сибирском конгрессе по приклад-нон и индустриальной математике (Новосибирск, 1996) и др.

Публикации. По теме; диссертации опубликовано 15 работ.

Структура и объем работы. Диссертация состоит из введения, четырех глав, выводов, списка литературы из 84.наименований, приложенных актов о внедрении. Общий объем диссертации — 79 страниц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

I! разделе ■).] вводятся определения п доказываются утверждения, используемые nidi описании алгоритма генерации.

Молпгулярным нрафом (далее для краткости графом) называется муль-тпгрлф G> = Е) порядка р. где множество вершин (|V| = р). Е

множество ребер, если вершинам приписаны какие-либо метки. В качестве меток рассматриваются алфавитно-цифровые последовательности.

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

Разобьем множество V на классы вершин, имеющие одинаковые метки и валентности. Упорядочим классы каким-нибудь образом: V] < 1 ]> < .. . < V). Рассмотрим графы, заданные на данном множестве вершин V и имеющие те же самые упорядоченные классы. Нумерация вершин графа допусти.иа, если вершины из меньшего класса имеют меньший номе]). Для допустимой нумерации множество Лг = {1.2,... .р} разбивается в свою очередь на классы А*!, N-2,..., Л?), где Л';. — номера вершин из Обозначим вершину с номером г через а ее валентность через са1,.

Поставим в соответствие графу матрицу смежности А = («,■;). где а,^ равно либо кратности ребер между смежными г,-и и е_,-й вершинами, либо нулю. Матрица смежности, соответствующая допустимой нумерации вершин, называется допустимой.

Введем на множестве матриц одинакового размера отношение линейного порядка: А < В (п1Ь ..., пгр) ■< ('>ц, !> 12.....ЬР1,). где порядок на

множестве векторов определен лексикографически.

Пусть 3(М) = ф5'(Лг);), где 5(ЛГ<.) — симметрическая группа матрица-

подстановок, действие которых приводит к одинаковой перестановке строк и столбцов матрицы смежности с номерами из Л";-.

Матрица смежности .4 называется канонической, если для \/г/ 6 5(Л") выполняется дАд~1 < А.

Графы изоморфны, если существует взаимно-однозначное соответствие вершин графов, сохраняющее отношения смежности и помеченностн. УТВЕРЖДЕНИЕ 2. Если вершины из различных классов имеют различные метки, то разли'чным каноническим матрицам смежности соответствуют неизоморфные графы.

Рассматриваются частично-залюлненные матрицы В = (/),,) — симметричные квадратные матрицы (р х р) с нулевой диагональю, где1 либо натуральное число, либо символ Л. Элементы ф () называются заполненными, остальные — незаполненными. Строка и столбец матрицы В заполнены, если все их элементы заполнены, и н/ заполнены — в противном случае. Пусть 1(В). 1(В) — множества номеров заполненных и незаполненных строк матрицы В.

Матрица С называется пополнением члетпчно-заполненной матрицы В. если с/] = Ь)1 при /),; ф Ь.

Частнчно-заполненная матрица В допустима, если существует допустимая матрица смежности .4. являющаяся ее пополнением.

Допустимые матрицы удовлетворяют трем условиям допустимости:

— G —

УСЛОВИЕ 1 (Допустимость заполнения). Сумма элементов заполненной

строки допустимой частпчно-заполненной матрицы равна валентности сор

ответствующей вершины: b¡j = val¡ для V¿ 6 1{В).

j=\

УСЛОВИЕ 2 (Допустимость по минимуму). Сумма заполненных элементов незаполненной строки допустимой матрицы не превышает валентности соответствующей вершины: ^¡j ^ Для ^ 6 J{B)-

rKí*

Вводится R = (j'y) — матрица максимально-возможных крагпностей ребер между вершинами рассматриваемых графов следующим образом: r¡j — си для Vi € iVjt, j G Аг/, где c¿; — максимально-возможная кратность ребер, соединяющих вершины из классов 14 и Vi между собой. Таким образом, с помощью матрицы R можно налагать запрет на образование ребер между вершинами отдельных классов (си = 0).

Пусть матрица смежности А удовлетворяет ограничениям, заданным матрицей R, и является пополнением В. Обозначим val¡ = val¡— b¡j.

r\ j¿S

Очевидно, что на незаполненных элементах матрицы В выполняется a¡j < uim(rij,vul¡,valj). Определим В!(В) = (r¡--) — матрицу максимальных кратностей для В:

mil\(r¡j,valnvulj) при b¡j = S при b¿j Ф- ñ.

г'- = / Illh

I ''и

УСЛОВИЕ 3 (Допустимость по максимуму). Сумма максимальных кратностей незаполненной строки допустимой матрицы не меньше валентно. V

стн соответствующей вершины: Y1 г'ц — vaдля 6 J{B)-

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

УСЛОВИЕ 4 (Форсированно по минимуму). Сумма заполненных элементов равна валентности соответствующей вершины: ^ b.¡j = val¡.

УСЛОВИЕ 5 (Форсирование по максимуму). Сумма максимальных крат-

ноетей равна валентности соответствующей вершины: r',j = vaU-

j=i

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

Пусть -h — множества номеров заполненных и незаполненных строк

матрицы В в классе Рассмотрим группу S(I, •/) = 0(5(Д.) ffj S(.Jk)),

k

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

Частнчно-заполненная матрица В называется силъно-каноничсской. если ее головной фрагмент не увеличивается под действием любой подстав новки из группы 5(7, ,7): (дВд'1)^- < В—г для е 5(7, .7). УТВЕРЖДЕНИЕ 2. Любая матрица смежности, являющаяся пополнением, не сильно-канонической матрицы, не канонична,.

Введем на множестве .7 = 7(В) \ т отношение эквивалентности: Л ~ 72 37 : 7Ь7-2 € Л и V«' < т Ь,]х = />,•;,. т. е. незаполненные столбцы (строки) эквивалентны, если они принадлежат одному классу Л^. и в них совпадают первые т — 1 элементов. Тогда множество 7 разбивается на классы эквивалентности {У;}, называемые кусками постоянства. Пусть 5(У) = ф5(У;) — группа, действие

элементов которой приводит к одинаковой перестановке незаполненных строк и столбцов независимо внутри всех кусков постоянств. в частности, к независимой перестановке элементов ее т-й строки внутри кусков постоянств. Обозначим т-ю строку матрицы В через В,„ .

Матрица С называется слабо-каноническим пополнением матрицы В. если она является допустимым пополнением с заполненной ш-й строкой и для каждого д в 5(У) выполняется (дСд~1),п < С,„.

УТВЕРЖДЕНИЕ 3. Матрица, не являющаяся слабо-каноническим пополнением, не сильно-канонична.

Максимальное значение (дСд~1)т при д 6 5(У) достигается тогда, когда элементы ш-й строки матрицы С упорядочены по убыванию внутри каждого куска постоянства. Таким образом, каждому слабо-канонпческо-му пополнению матрицы В соответствует распределение элементов т-п строки, упорядоченных по убыванию внутри каждого куска постоянства.

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

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

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

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

По сравнению с известным алгоритмом*' удалось получить сокращение перебора за счет свойств форсированно заполненных строк. УТВЕРЖДЕНИЕ 4. Если для некоторого 1 < k < s существует иод-становка у G S(I,J), для которой выполняется (уВу~1)^ = В—г , т<> (дВу~1)тк+1_1 = B,„k-n_i ] где т^ — ном,ер строки (столбца), заполненной на k-м таге.

Из утв. 4 следует, что форсированно заполненные строки матрицы В полностью определяются строками с номерами тк, к = 1s — 1. Поэтому при поиске подстановки из S(I,J), действие которой увеличивает матрицу В, достаточно проверять перестановки строк и столбцов только на места тк\ к = 1,.. ., .s — 1.

Такой подход существенно сокращает высоту дерева перебора подстановок из S(I. .7) при форсированном заполнении многих строк. В частности, все строки, стоящие в конце матрицы смежности и соответствующие одновалентным вершинам, заполняются форсированно. ТЕОРЕМА. Если вершины из различных исходных классов имеют различные метки, то алгоритм генерации строит все неизоморфные молекулярные графы (их канонические матрицы смежности) из множества помеченных вершин с заданной валентностью, удовлетворяющих ограничениям в -матрице It.

Доказательство. Полнота построения всего множества молекулярных графов достигается путем исчерпывающего перебора на каждом шаге алгоритма всех слабо-канонических пополнении. Из утв. 3 следует, что остальные пополнения не могут привести к каноническим матрицам смежности. Как следует из утв. 2, полученные не сильно-канонические матрицы далее можно не рассматривать. Таким образом, полнота решения задачи генерации сохраняется. Факт генерации только неизоморфных графов в случае, когда вершины из различных. исходных классов имеют различные метки, прямо следует из утв. 1.

В разделе 2.3 подробно описаны особенности и дополнительные возможности программы GENM, реализующей описанный выше алгоритм.

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

"î.kî'H'HMj В Л и jî] 1 //Л.пор и i мич' гкнг in r.ifjioH.iiinn к комол па j орлкс. /Пол |х'Д. Фарад-

женя И Л -Мошна Ibiyk.i l!J7« - e.V.) 2'i.

\

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

В конце раздела для иллюстрации эффективности программы СЕХМ приведены результаты построения ряда молекулярных графов с различными циклическими рангами, а также связных регулярных графов и муль-тиграфов с числом вершин р (б < р < 20) и степенями к (3 < к < б). Число и время генерации последних даны в табл. 1. Знак «?» указывает, что для данных значений р и к эксперимент не проводился из-за ожидаемого большого времени генерации.

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

3 4 5 6

с 6 0:00 19 0:00 49 0:00 20 0:00

7 50 0:00 • 933 0:00

8 20 0:00 204 0:00 1689 0:00 13303 0:03

9 832 0:00 252207 0:54

10 91 0:00 4330 0:02 187392 0:51 6450828 2.3:51

11 25227 0:11 205475039 13:19:43

12 509 0:00 171886 1:16 46738368 3:58:24 7

13 1303725 10:16 7

14 3608 0:04 10959478 1:33:02 7

15 100230117 1 5:16:23 7

1С 31856 0:41 ? ? 7

17 7 7

18 340416 8:12 ? 7 ■?

Время генерации дано для Регйшт-120 в формате час:мин:сек

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

В разделе 3.1 поставлена задача генерации графов с заданными структурными ограничениями. Очевидно, что даже для небольшого числа вершин можно построить сотни тысяч нензоморфных графов, что требует значительного времени. Между тем часто известна дополнительная информация о строении графов. Если соответствие ограничениям проверять после построения каждого графа, общее время счета еще более

1>ч =

возрастет. Поэтому важно учитывать особенности молекулярных графов в процессе их генерации.

В разделе 3.2 даются определения, необходимые для описания задания информации о фрагментах в исходной матрице для генерации.

Фрагментом графа С? называется граф, изоморфный индуцированному подграфу С. 'Заметим, что условие связности не накладывается.

Пусть {.Г4' = (ик,Хк)} — набор непересекающихся фрагментов графа С, где ик — множество вершин (Г/* П С/' = 0 при к ф /), Л'* — множество ребер к-го фрагмента. Рассмотрим частнчно-заполненную матрицу В с элементами

(^¡j при 1',, V] 6 ик для некоторого к; 0 при г = /; (1)

() в остальных случаях.

Очевидно, что графы, матрицы смежности которых являются пополнениями В. содержат набор фрагментов {■Р4}. Для того, чтобы можно было взять В в качестве исходной матрицы, необходимо построить разбиение вершин фрагментов на классы и определить соответствующие данному разбиению обязательные кратности ребер в матрице Я..

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

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

Фрагменты, имеющие только одну внешнюю вершину, называются простыми. Представителями простых фрагментов являются:

О •=•

Х=о д /7

он

. "Здесь и далее свободные валентности показаны короткими черточками, выходящими из вершины фрагмента; на месте вершины приводится ее метка: для непомеченных вершин предполагается метка вида СНд. Подразумеваются следующие валентности помеченных вершин: С 4, Н - 1, N — 3, О • - 2, и т. д.

На множестве вершин каждого фрагмента вводится отношение эквивалентности. Вершины м и V фрагмента эквивалентны, если существует взаимно-однозначное соответствие вершин фрагмента, сохраняющее отношение смежности и помеченностн и переводящее н в V. Тогда множество вершин фрагмента разбивается на классы эквивалентности, известные как орбиты.

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

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

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

-сн2-сн2- хп-х-аь- '\/<

I ^

Следующие фрагменты являются сложными:

\ /

ХН-ННЧ-СНС У У

I I >—< ^ _ ^

/ ч

В разделе 3.3 описывается способ задания простых фрагментов.

Пусть {Рк} — набор непересекающихся, изоморфных между собой простых фрагментов. Разобьем вершины фрагментов Рк на два класса: в первый класс отнесем все внутреннее вершины фрагментов, во второй — внешние. Свободные вершины разобьем на классы вершин, имеющие одинаковые метки и валентности.

Построим матрицу В согласно (1). Определим матрицу Е:

при Ьу ф 5; си при ll¡j = И и 1 е Л'<, ./' 6 Л7/, где гд; максимально-возможная кратность ребер между вершинами из 1 к II V/ классов.

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

Если заданы непзоморфные простые фрагменты, разобьем их на подмножества изоморфных между собой фрагментов. Тогда последовательно обработаем каждое из подмножеств указанным выше способом.

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

Например, пусть требуется построить все карбоновые кислоты с молекулярной формулой СбНюО,), определяемые наличием карбоксильной

Р

группы: фрагмента -с

ОН

Вершины фрагмента разбиваются на два класса. В первый класс попадают внутренние вершины с метками О и ОН, во второй — С-вершина со свободной валентностью. Тогда исходные классы для генерации класс VI: О- и ОН-вершнны валентности 0; класс У-2: 1 С-верщнна валентности 1; класс У:!: 5 С-вершин валентности 4; класс У^: 2 О-вершины валентности 2; класс УГ): 9 Н-вершпн валентности 1.

Матрица В без класса Н-вершнн задана следующим образом:

В =

/ 0 0 -2 0 0 0 0 0 0

0 0 -1 0 0 0 0 0 0 0

-2 -1 0 1 1 1 1 1 1 1

0 0 1 0 2 2 2 2 2 2

0 0 1 2 0 2 2 2 2 2

0 0 1 2 2 0 2 2 2 2

0 0 1 2 2 2 0 2 2 2

0 0 1 2 2 2 2 0 2 2

0 0 1 2 2 2 2 2 0 1

1 0 0 1 2 2 2 2 2 1 Ч

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

Используя эти данные, программа СЕКМ за 3.1 сек на РС 380 (20 МГц) -генерирует 1974 графа, соответствующих карбоновым кислотам, из которых 1971 различны. Все дважды сгенерированные графы содержат две несимметрично расположенные карбоксильные группы:

о сн;1 о

\\ 1 У/

но

N 1 //

с-с-с н-2-с(

СН., он

О О () о

\\ м ❖ и/

С-СН-СН-2-С С-СН-СН2-СН2-С

но' ¿Н2 ОН НО СН-! он

I

сн:1

Время генерации всех 97394 графов с молекулярной формулой СцНшО), если не задана карбоксильная группа, составило 2 мин 38 сек.

В разделе 3.3 описывается способ задания средних фрагментов.

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

Построим частично-заполненную матрицу В, определим матрицу Я согласно (1) и (2). Заданные таким образом начальные данные обеспечат генерирование графов, содержащих средний фрагмент Р.

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

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

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

Например, при построении графов с молекулярной формулой СпНюМ-,;, содержащих фрагмент -СН^—ХН- (' заданным распределением Н-вершин, изоморфные графы содержат или два фрагмента СП-^ -N11 . или фрагмент -СН2 —СНу -, пли фрагмент МН—СН^ -Т'Ш- , когда вершины заданного фрагмента становятся эквивалентными свободным вершинам. Время генерации всех 7014 графов с молекулярной формулой СиНю^, содержащих фрагмент СН-,г-МН- с заданным распределением Н-вершин, составило 7.5 сек (РС 38С). Из 7044 сгенерированных графов нензоморф-ными являются 0739.

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

Пусть задан только один сложный фрагмент Р. Разобьем вершины фрагмента Р по орбитам. Упорядочим полученные орбиты (классы эквн-

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

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

Для генерации всех графов, содержащих сложный фрагмент, необходимо усилить определение сильно-канонической матрицы. Подгруппу 5(7,-7), сохраняющую подматрицу смежности фрагмента Е, обозначим через /,./). Частпчно-заполненная матрица В называется сильноканонической, если ее головной фрагмент не увеличивается под действием любой подстановки из группы S(F,I,J), т. е. для \/<у 6 3(Е,1,.1) выполняется (дВд~1)щ < Вт, где т — число первых заполненных строк В.

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

Вершины сложного фрагмента должны попадать в первые по счету исходные классы вершин графа. Если перед классами с вершинами сложного фрагмента, находится хотя бы один класс, содержащий вершины со свободными валентностями, то многие заполнения строк из этого класса матрицы В будут невозможны. Действительно, пусть задан сложный фрагмент Т^. Очевидно, что все вершины фрагмента эквивалентны и значит попадают в один исходный класс. Предположим, что перед этим классом находится еще один класс, содержащий О-вершнну валентности 2. Тогда единственное заполнение куска постоянства, соответствующего вершинам фрагмента, будет ( 1 10 0), т.к. куски постоянства всегда заполняются в убывающем порядке. Такому заполнению соответствует фрагмент 7^. Однако, существует еще фрагмент Т^з, неизоморфный фрагменту 7^, который необходимо построить. По этой же причине нельзя воспользоваться процедурой предварительного распределения Н-вершпн.

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

3

3

2 4

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

К сожалению, в случае нескольких сложных фрагментов будет генерироваться относительно большое число изоморфных графов. Например, за 4 мин 2 сек (РС 386) сгенерировано 32554 графов с молекулярной формулой СчгНго^О, содержащих фрагменты

\ _ _ /

/*"

_/

/ \

Из сгенерированных графов 15778 являются непзоморфнымн.

В разделе 3.6 приводятся результаты генерации графов (табл. 3) с молекулярной формулой СаНцРТОг и с фрагментами из табл. 2. Первая строка табл. 2 содержит сложные, вторая — средние, третья — простые фраг-

Таблица 2. Примеры фрагментов

1 ¡1 1 1 2 А V ш 3 С ОН 4 -О-СН-СН-О-1 1

5 Л А 6 II 1 7 О 8

9 О -с' он 10 Х=о и 12

Таблица 3. Результаты генерации графов с молекулярной формулой СдНцГТО2, содержащих заданные фрагменты

Число Число

№ Фрагменты сгенерированных неизоморфных Время

графов графов

1 1 76247 76247 5:54.0

2 1,4 2064 1845 7.6

3 1, 7 802 802 5.0

4 1,8 3855 3855 16.0

5 1,9 203 203 0.9

С 1,10 3234 3234 15.0

7 1,12 13192 13192 46.0

8 1,10,12 553 553 2.3

9 2,4 13584 10264 25.0

10 2,9 860 860 1.9

11 2,10 20316 19896 52.0

12 2,10,10 456 456 1.5

13 3,10, 8 6185 3147 13.0

14 3,10,11 1891 940 3.5

15 3,10,12 36575 17468 51.0

16 5 52965 52965 1:14.0

17 5,4 2990 2945 6.6

18 5, 7 1460 1460 3.3

19 5, 9 235 235 0.5

20 5,10 3560 3560 6,5

21 6 3838 3838 5.9

22 6,4 220 215 0.5

23 6,7 166 166 0.5

24 6, 8 328 328 0.8

25 6, 9 27 27 0.1

26 6,10 392 392 0.9

27 6,12 665 665 1.1

28 7, 7,11 8825 4457 15.0

29 7,10,11 12295 12295 19.0

30 9,11 5866 5866 8.7

31 10,10,11 7533 7533 13.3

Время генерации дано для РС 386 (20 МГц)

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

Из приведенных данных видно, что в большинстве случаев число изоморфных графов относительно невелико. Они появляются в случае задания нескольких сложных фрагментов (см. примеры №2 и №-9 табл. 3), нескольких одинаковых средних фрагментов (№28), при возникновении новых элементов симметрии на множестве вершин (№13, №14 и №15). Вместе с тем время решения задачи генерации при задании фрагментов резко сокращается. Для сравнения время генерации всех 277.810.103 графов с молекулярной формулой СдНцГТОг составило 6 час 23 мин 40 сек на Реп1шт-120, который примерно в 20 раз быстрее РС 380.

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

В четвертой главе описано применение программы генерации

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

В выводах приведены основные результаты диссертации:

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

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

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

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

Основное содержание диссертации опубликовано в работах:

[1] Молодцов С. Г., Ппоттух-Пелецкнй В. Н. Построение всех неизоморфных структурных формул химических соединений, содержащих заданный набор непересекающихся фрагментов. //VI Всесоюзная конференция "Использование вычислительных машин в спектроскопии молекул и химических исследованиях": Тез. докл. - Новосибирск, 1983. - С.174-175.

[2] Молодцов С. Г. Построение всех неизоморфных химических графов, отвечающих заданным структурным ограничениям. //III Всесоюзное совещание "Методы и программы решения оптимизационных задач на графах и сетях": Тез. докл. - Ташкент, 1984. - часть I. - С.149-150.

[3] Молодцов С. Г., Пноттух-Пелецкий В. Н. Построение всех нензомо-морфных химических графов из заданного набора структурных фрагментов. //Алгоритмы анализа структурной информации (Вычислительные системы). - 1984. - Вып.103. - С.51-58.

[4] Кнршанскнн С. П., Молодцов С. Г., Лебедев К. С. Извлечение структурной информации из масс-спектров с помощью ЭВМ. XII. Генерирование структурных гипотез и их ранжирование на основе результатов работы ИПС. //Изв. СО АН СССР, сер. хим. наук. - 1989. - Вып.5. - С.3-9.

[5] Molodtsov S. G. Generation of Molecular Graphs with a Given Set of Nonoverlapping Fragments. //Commun. Math. Clieni.(MATCH) - 1994. -N.30.- P.203-212.

[G] Molodtsov S. G. Computer-Aided Generation of Molecular Graphs. //Commun. Math. Chem.(MATCH) - 1994. - N.30.- P.213-224.

[7] Молодцов С. Г., Лебедев К. С., Дерендяев Б. Г. Выбор информации для генерирования структур в системах установления строения соединений с помощью баз данных по молекулярной спектроскопии. //ЖСХ - 1994. - Т.35. - N.2. - C.4G-53.

Введение

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

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

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

1.1/2. Генераторы структур в системе DENDRAL.

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

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

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

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

1.2.2. Генератор структур в системе CHEMICS.

1.2.3. Генерирование неизоморфных графов с заданным распределением степеней вершин.

1.2.4. Другие алгоритмы генерации канонических графов

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

2.1. Определения.

2/2. Алгоритм генерации

2.3. Особенности программной реализации алгоритма.

2.3.1. Проверка связности генерируемых графов.

2.3.2. Построение различных множеств вершин для генерации (распределение Н-вершин).

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. Выбор исходных данных для генерирования структур

Выводы

Задача генерации графов заданного класса имеет большое значение как в комбинаторном анализе, так и при решении разнообразных прикладных проблем. Наличие списков графов позволяет во многих случаях проверить гипотезы о строении графов, определить и сопоставить характеристики различных классов графов. Естественным образом задача генерации возникает в тех областях, где графы используются как модели для описания соответствующих объектов. В частности, графы находят применение в электротехнике при анализе электрических схем, в теории вероятностей для описании цепей Маркова, в линейном программировании при изучении потока в сетях, в социологии для рассмотрения взаимодействия личностей в коллективе и т. п.

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

Алгоритмы генерации молекулярных графов должны учитывать их характерные особенности и удовлетворять следующим требованиям:

1. Гарантия исчерпывания: построение всех различных (неизоморфных) графов, отвечающих заданным ограничениям.

2. Минимизация дублирования: в идеале алгоритм не должен строить изоморфные графы. Если этого не удается достигнуть, то должны быть предприняты специальные меры для уменьшения дублирования.

3. Эффективность генерирования: желателен анализ перспективности движения по дереву поиска, каждый узел которого соответствует какому-либо шагу построения молекулярного графа. Алгоритм должен как можно раньше заметить, что любые последующие шаги не приведут к искомому результату.

4. Соответствие ограничениям: алгоритм должен использовать ограничения в форме, удобной для пользователя.

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

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

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

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

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

Исходя из этого были поставлены следующие основные задачи:

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

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

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

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

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

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

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

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

Практическая ценность выполненной работы определяется тем. что на основе предложенного алгоритма генерации молекулярных графов разработана программа GENM, которая включена в состав систем для установления строения соединений по их молекулярным спектрам: КОМПАС и ChemArt (НИОХ СО РАН, Новосибирск), РАСТР (ВНИИОС, Москва). Кроме этого программа внедрена в ряде других организаций, что подтверждается соответствующими актами, приложенными в конце работы. Программа генерации молекулярных графов GENM может использоваться и как средство пользователя (химика, математика), и как необходимый инструментарий, позволяющий выдвигать и проверять новые приемы в решении прикладных химических задач, например, установления строения соединений. г

Апробация работы. Основные результаты диссертационной работы представлены на VI и VIII Всесоюзных конференциях «Использование вычислительных машин в спектроскопии молекул и химических исследованиях» (Новосибирск, 1983, 1989), III Всесоюзном совещании «Методы и программы решения оптимизационных задач на графах и сетях» (Ташкент, 1984), X Всесоюзном совещании «Физические методы в координационной химии» (Кишинев, 1990), II Всесоюзной конференции «Математические методы и ЭВМ в аналитической химии» (Москва, 1991). IX Всесоюзной конференции «Химическая информатика» (Черноголовка.

1992), II Сибирском конгрессе по прикладной и индустриальной математике (Новосибирск, 1996), V конференции «Аналитика Сибири и Дальнего Востока» (Новосибирск, 1996).

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

Выводы

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

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

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

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

1. Sylvester J. J. Chemistry and Algebra. //Nature(London) - 1877. - Vol.17. - P. 284

2. Gray N. A.B. Computer-Assisted Structure Elucidation. /Wiley-Interscience: New York, 1986. 536 P.

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

4. Nelson D. В., Munk М. Е., Gash К. В., D. L. Herald, Jr. Alanylactinobicy-clone. An Application of Computer Techniques to Structure Elucidation. //J. Org. Chem. 1969. - Vol.34. - N.12. - P.3800-3805.

5. Нехорошее С. А., Коптюг В. А. Построение полного набора возможных структурных формул исследуемого соединения по заданному набору фрагментов с помощью ЭВМ (усовершенствованный вариант). //Изв. СО АН СССР, сер. хим. наук. 1975. - Вып.6. - С.66-70.

6. Дементьев В. А. Автоматическое построение структурной формулы по результатам анализа ИК спектра соединения с известной брутто-формулой. //ЖПС 1975. - Т.23. - Вып.З. - С.479-485.

7. Smith D. Н., Gray N. А. В., Nourse J. G., Crandell С. W. The DENDRAL Project: Recent Advances in Computer Assisted Structure Elucidation. //Anal. Chim. Acta. 1981. - Vol.133. - N.4. - P.471-497.

8. Lederberg J. DENDRAL-64: A System for Computer Construction, Enumeration and Notation of Organic Molecules as Tree Structures and Cyclic Graphs. /Technical Report CR57029, NASA, 1964.

9. Lederberg J. Topology of Molecules. //The Mathematical Sciences. /The MIT Press: Cambridge, MA, 1969. P.37

10. Masinter L. M., Sridharan N. S., Lederberg J., Smith D. H. Application of Artificial Intelligence for Chemical Inference. 12. Exhaustive Generation of Cyclic and Acyclic Isomers. //J.Am.Chem.Soc. 1974. - Vol.96. -N.25. - P.7702-7714.

11. Masinter L. M., Sridharan N.S., Carhart R. E., Smith D.H. Application of Artificial Intelligence for Chemical Inference. 13. Labelling of Objects Having Symmetry. //J. Am. Chem. Soc. 1974. - Vol.96. - N.25. - P.7714-7723.

12. Brown H., Hjelmeland L., Masinter L.M. Constructive Graph Labelling Using Double Cosets. //Discrete Math. 1974. - N.7. - P.l.

13. Brown H., Masinter L.M. An Algorithm for the Construction of the Graphs of Organic Molecules. //Discrete Math. 1974. - N.8. - P.227.

14. Carhart R. E., Smith D.H., Brown H., Sridharan N. S. Applications of Artificial Intelligence for Chemical Inference 16. Computer Generation of Vertex-Graphs and Ring Systems. //J.Chem. Inf. Comput. Sci. 1975. -Vol.15. - N.2. - P. 124-131.

15. Carhart R.E., Smith D.H., Brown H., Djerassi C. Applications of Artificial Intelligence for Chemical Inference. 17. An Approach to Computer-Assisted Elucidation of Molecular Structure. //J. Am. Chem. Soc. 1975. - Vol.97. - N 20. - P.5755-5762.

16. Carhart R. E., Smith D.H. Application of Artificial Intelligence for Chemical Inference. 20. "Intelligent" Use of Constraints in Computer-Assisted Structure Elucidation. //Comput. Chem. 1977. - Vol.1. - N.2. - P.79-84.

17. Carhart R.E., Varkony Т.Н., Smith D.H. Computer Assistance for the Structural Chemist. //Computer-Assisted Structure Elucidation. /Ed. by Smith D.H., ACS Symposium Series 54, American Chemical Society: Washington, D.C., 1977. P.126-145.

18. Brown H. Molecular Structure Elucidation. //SIAM J.Appl.Math. 1977.- Vol.32. N.3. - P.534-551.

19. Carhart R. E. A Simple Approach to the Computer Generation of Chemical Structures //Memorandum MIP-R-118, Machine Intelligence Research Unit, University of Edinburgh, 1977.

20. Carhart R.E., Smith D.H., Gray N.A.B., Nourse J.G., Djerassi C. GENOA: A Computer Program for Structure Elucidation Utilizing Overlapping and Alternative Substructures. //J. Org. Chem. 1981. - Vol.46.- N.8. P.1708-1718.

21. Shelley C. A., Munk M.E. CASE, a Computer Model of the Structure Elucidation Process. //Anal. Chim. Acta. -1981. Vol.133. - N.4. - P.507-516.

22. Shelley C. A., Munk.M.E. Computer Perception of Topological Symmetry. //J. Chem. Inf. Comput. Sci. 1977. - Vol.17. - N.2. - P.110.

23. Shelley C.A., Hays T.R., Munk M.E, Roman R.V. An Approach to Automated Partial Structure Expansion. //Anal. Chim. Acta. 1978.-Vol.103. - N.2. - P.121-132.

24. Shelley C. A., Munk M.E., Roman R.V. A Unique Computer Representation for Molecular Structures. //Anal. Chim. Acta. 1978. - Vol.103. -N.3.- P.245-251.

25. Shelley C. A., Munk M.E. An Approach to the Assignment of Canonical Connection Tables and Topological Symmetry Perception. //J. Chem. Inf. Comput. Sci. 1979. - Vol.19. - N.4. - P.247-250.

26. Christie B.D., Munk M.E. Structure Generation by Reduction: A New Strategy for Computer-Assisted Structure Elucidation. //J. Chem. Inf. Comput. Sci. 1988. - Vol.28. - N.2. - P.87-93.

27. Kerber A., Laue R., Moser D. Ein Strukturgenerator fur Molekulare Graphen. //Anal. Chim. Acta. 1990. - Vol.235. - N.l. - P.221-228.

28. Grund R., Kerber A., Laue R. Molgen, ein Computeralge-bra System fur die Konstruktion molekularer Graphen. //Com-mun. Math. Chem.(MATCH) - 1992. - N.27. - P.87-131.

29. Contreras M.L., Valdivia R., Rozas R. Exhaustive Generation of Organic Isomers. 1. Acyclic Structures. //J. Chem. Inf. Comput.Sci. 1992. -Vol.32. - N.4 - P.323-330.

30. Contreras M.L., Valdivia R., Rozas R. Exhaustive Generation of Organic Isomers. 2. Cyclic Structures: New Compact Molecular Code. //J.Chem.Inf.Comput.Sci. 1992. -Vol.32. - N.5 - P.483-491.

31. Bangov I.P. Computer-Assisted Generation of Molecular Structures from a Gross Formula. 1. Acyclic saturated compounds. //Com-mun. Math. Chem.(MATCH) 1983. - N.14. - P.235-246.

32. Bangov I. P., Kanev K.D. Computer-Assisted Structure Generation from a Gross Formula: 2. Multiple Bond Unsaturated and Cyclic Compounds. Employment of Fragments. //J. Math. Chem. 1988. - Vol.2. - N.l. -P.31-48.

33. Bangov I. P. Computer-Assisted Structure Generation from a Gross Formula. 3. Allevation of the Combinatorial Problem. //J. Chem. Inf. Com-put. Sci. 1990. - Vol.30. - N.3. - P.277-289.

34. Bangov I.P. Computer-Assisted Structure Generation from a Gross Formula. 4. Fighting Against Graph-Isomorphism Disease. //Com-mun. Math. Chem.(MATCH) 1992. - N.27. - P.3-30.

35. Bangov I. P. Structure Generation from a Gross Formula. 7. Graph Isomorphism: A Consequence of the Vertex Equivalence. //J.Chem.Inf.Comput.Sci. 1994. - Vol.34. - N.2. - P.318-324.

36. Разников В. В., Тальрозе В. JI. Автоматическое построение полного набора структурных формул изомеров соединения определенного элементарного состава и молекулярного веса. //ЖСХ 1970. - Т.П. -N.2. - С.357-360.

37. Митрофанов Ю. JI., Разников В. В., Шкуров В. А. Метод автоматического построения топологических структурных формул органических соединений по заданной брутто-формуле. //ЖАХ 1982. - Т.37. - N.8. - С.1477-1483.

38. Резников В. В., Резникова М. О. Информационно-аналитическая масс-спектрометрия. /Москва: Наука, 1992. С.211-230.

39. Kudo Y., Sasaki S. The Connectivity Stack, A New Format for Representation of Organic Chemical Structures. //J.Chem.Doc. 1974. - Vol.14.- N.4. P.200-202.

40. Kudo Y., Sasaki S. Principle for Exhaustive Enumeration of Unique Structures Consistent with Structural Information. //J. Chem. Inf. Com-put. Sci. 1976. - Vol.16. - N.l. - P.43-49.

41. Sasaki S., Abe H., Hirota Y., Ishida Y., Kudo Y., Ochiai S., Saito K., Yamasaki T. CHEMICS F: A Computer Program System for Structure Elucidation of Organic Compounds. //J. Chem. Inf. Comput. Sci. - 1978.- Vol.18. N.3. - P.211-222.

42. Sasaki S., Fuji war a I., Abe H. A Computer Program System — NEW CHEMICS — for Structure Elucidation of Organic Compounds by Spectral and Other Structural Information. //Anal. Chim. Acta. 1980. -Vol.122. - N.2. - P.87-94.

43. Oshima Т., Ishida Y., Saito K., Sasaki S. Chemics-UBE, A Modified System of Chemics. //Anal. Chim. Acta. 1980. - Vol.122. - N.2. - P.95-102.

44. Abe H., Fujiwara I., Nishimura Т., Okuyama Т., Kida Т., Sasaki S. Recent Advances in the Structure Elucidation System, CHEMICS. //Corn-put. Enhanced Spectrosc. 1983. - Vol.1. - N.2. - P.55-62.

45. Abe H., Okuyama Т., Fujiwara I., Sasaki S. A Computer Program for Generation of Constitutionally Isomeric Structural Formulas. //J. Chem.Inf. Comput. Sci. 1984. - Vol.24. - N.4. - P.220-229.

46. Sasaki S., Kudo Y. Structure Elucidation System Using Structural Information from Multisources: CHEMICS. //J. Chem. Inf. Comput. Sci. -1985. Vol.25. - N.4. - P.252-257.

47. Funatsu К., Carlos A., Carpio D., Sasaki S. Automated Structure Elucidation System — CHEMICS. //Z. Anal. Chem. -1986. Vol.324. - P.750-759.

48. Funatsu K., Miyabayashi N., Sasaki S. Futher Development of Structure Generation in the Automated Structure Elucidation System CHEMICS. //J. Chem. Inf. Comput. Sci. 1988. - Vol.28. - N.l. - P. 18-28.

49. Faradzev I. A. Constructive enumeration of combinatorial objects, Problems Combinatoires et Theorie des Graphes. //Colloque Internationale CNRS 260, CNRS Paris, 1978. - P. 131-135.

50. Фараджев И. А. Конструктувное перечисление комбинаторных объектов. //Алгоритмические исследования в комбинаторике. /Под ред. Фараджева И. А. Москва: Наука, 1978. - С.3-11.

51. Фараджев И. А. Генерирование неизоморфных графов с заданным распределением степеней вершин. //Алгоритмические исследования в комбинаторике. /Под ред. Фараджева И. А. Москва: Наука, 1978.- С.11-19.

52. Зайченко В. А., Иванов А. В., Розельфельд М. 3., Фараджев И. А. Алгоритм проверки каноничности частично-заполненной матрицы смежности графа. //Алгоритмические исследования в комбинаторике. /Под ред. Фараджева И. А. Москва: Наука, 1978. - С. 19-25.

53. Серов В. В., Эляшберг М.Е., Грибов JI. А. Система математического синтеза и анализа всех структурных формул органических соединений, соответствующих заданной брутто-формуле. //Докл. АН СССР- 1975. Т.224. - N.I.- С.109-111.

54. Serov V. V., Eliashberg М. Е., Gribov L. A. Mathematical synthesis and analysis of molecular structures. //J. Mol. Struct.(Theochem.) 1976. -Vol.31. - N.2. - P.381-397.

55. Серов В. В., Эляшберг М.Е., Грибов JI. А. Математический «синтез» всех топологических изомеров бензола. //Изв. Тимирязевск. с.-х. акад.- 1977. N.1. - С.214-216.

56. Эляшберг М.Е., Грибов JLA., Серов В. В. Математический синтез и анализ молекулярных структур. //Молекулярный спектральный анализ и ЭВМ. /Москва: Наука, 1980. С. 141-168.

57. Zhu S., Zhang J. Exhaustive Generation of Structural Isomers for a Given Empirical Formula — A New Algorithm. //J. Chem. Inf. Comput. Sci. -1982. Vol.22 - N.l. - P.34-38.

58. Субоч В. П., Мелкозерова JI. Г., Павлова А. П., Гуринович Г. П. Построение структурных изомеров органических соединений с помощью ЭВМ. //ЖПС 1985. - Т.42. - Вып.6. - С.985-991.

59. Черемисинов Д. И. Генерация графов, представляющих структурные формулы изомеров молекул. //ЖПС 1978. - Т.29. - Вып.5. - С.894-899.

60. Kvasnicka V., Pospichal J. Canonical Indexing and Constructive Enumeration of Molecular Graphs. //J. Chem. Inf. Comput. Sci. 1990. - Vol.30. - N.2. - P.99-105.

61. Kvasnicka V., Pospichal J. Constructive Enumiration of Molecular Graphs with Prescribed Valence States. //Chemom. Intell. Lab. Syst. -1991. Vol.11. - P. 137-147.

62. Kvasnicka V., Pospichal J. Constructive Enumeration of Acyclic Molecules. //Collect. Czech. Chem. Commun. 1991. - Vol.56. - P.1777-1802.

63. Kvasnicka V., Pospichal J. An Improved Method of Constructive Enumiration of Graphs. //J. Math. Chem. 1992. - Vol.9. - P.181-196.

64. Kvasnicka V., Pospichal J. An Improved Version of the Constructive Enumiration of Molecular Graphs with Prescribed Sequence of Valence States. //Chemom. Intell. Lab. Syst.- 1993. Vol.18. - P.171-181.

65. Molchanova M. S., Shcherbukhin V. V., Zefirov N. S. Structure Generation of Molecular Structures by the SMOG Program. //J. Chem. Inf. Comput. Sci. 1996. - Vol.36 - N.4. - P.888-899.

66. Abstracts of the XI International Conference on Computers in Chemical Reseach and Education. (C-05, €07, C24) /Paris, 1996.

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

68. Molodtsov S. G. Generation of Molecular Graphs with a Given Set of Nonoverlapping Fragments. //Commun. Math. Chem. (MATCH) 1994. -N.30.- P.203-212.

69. Molodtsov S. G. Computer-Aided Generation of Molecular Graphs. //Commun. Math. Chem.(MATCH) 1994. - N.30.- P.213-224.

70. Харари Ф. Теория графов. /Москва: Мир, 1973. 300 С.

71. Robinson R.W., Wormald N.C. Numbers of Cubic Graphs. //J. Graph Theory. 1983. - Vol.7. - N.4. - P.463-467.

72. Лебедев К. С., Дерендяев Б. Г., Нехорошев С. А. Извлечение структурной информации из масс-спектров с помощью ЭВМ. IV. Определение формальной ненасыщенности соединения. //Изв.СО АН СССР, сер.хим.наук. 1981. - Вып.2. - С.91-93.

73. Lebedev К. S., Tormyshev V.M., Derendyaev В. G., Koptyug В. А. А Computer Search System for Chemical Structure Elucidation Based on Low-resolution Mass Spectra. //Anal. Chim. Acta. 1981. - V.133. -P.517-525.

74. Пиоттух-Пелецкий В. Н., Богданова Т.Ф., Деревдяев Б. Г. Полные наборы фрагментных составов структур при мнтерпритации ИК спектров. //ЖСХ 1996. - Т.37. - N.2. - С.368-378.

75. Молодцов С. Г., Лебедев К. С., Дерендяев Б. Г. Выбор информации для генерирования структур в системах установления строения соединений с помощью баз данных по молекулярной спектроскопии. //ЖСХ 1994. - Т.35. - N.2. - С.46-53.

76. Лебедев К. С., Шарапова О. Н., Коробейничева И. К., Кохов В. А. Опознание крупных структурных фрагментов неизвестного соединения с помощью поисковой системы по ИК-спектрам. //Сиб. хим. журнал. -1993. Вып.1. - С.50-56.

77. Лебедев К. С. Использование баз данных по ИК- и масс-спектрам для установления строения органических соединений. //ЖАХ 1993. -Т.48. - Вып.5. - С.851-863.

78. Fuchs P. L., Bunnell С. A. Carbon-13 NMR Based Organic Spectral Problems. /Wiley-Interscience: New York, 1979.