Генерирование молекулярных графов с заданными структурными ограничениями тема диссертации и автореферата по ВАК РФ 05.13.16, кандидат физико-математических наук Молодцов, Сергей Георгиевич

• Молодцов, Сергей Георгиевич
• кандидат физико-математических наук
• 1997

Оглавление диссертации кандидат физико-математических наук Молодцов, Сергей Георгиевич

Введение

Глава 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 позволило предложить и проверить схемы сокращения избыточной исходной информации и ранжирования сгенерированных структур в системах установления строения соединений по их молекулярным спектрам.

Список литературы диссертационного исследования кандидат физико-математических наук Молодцов, Сергей Георгиевич, 1997 год

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.