Машинное обучение на узорных структурах тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Самохин, Михаил Валерьевич

• Самохин, Михаил Валерьевич
• кандидат технических наук
• 2006

Оглавление диссертации кандидат технических наук Самохин, Михаил Валерьевич

Введение

1 Основные определения

1.1 Теория решёток и Анализ Формальных Понятий.

1.1.1 Частично упорядоченные множества и решётки.

1.1.2 Анализ формальных понятий (АФП)

1.1.3 Узорные структуры и их проекции.

1.1.3.1 Проекции узорных структур. 1.2 Машинное обучение и анализ данных.

1.2.1 Анализ Формальных Понятий и ДСМ-метод.

1.2.1.1 Стратегия последовательного покрытия гипотезами в

ДСМ-методе.

1.2.2 Метод порождения правил с исключениями. RIPPER.

1.2.3 Наивный метод Байеса (Naive Bayes).

1.2.4 Методы индуктивного порождения деревьев решений.

Ф 2 Графы и их проекции

2.1 Общий взгляд.

2.2 Графы и узорные структуры.

2.3 Различные варианты проекций на графах.

3 Алгоритмическая реализация приближенного описания узорных структур

3.1 Общий взгляд.

3.2 Подробное описание.

3.2.1 Порождение кандидатов. f 3.2.2 Алгоритмы для различных вариантов проекции

3.2.3 Использование алгоритма в ДСМ-методе

3.2.4 Оценка быстродействия

4 Машинные эксперименты и результаты

4.1 Эксперименты с химическими данными.

4.1.1 Эксперименты на массиве РТС. ф 4.1.2 Проекции графов "на ROC-диаграмме" (результаты для массива РТС)

4.1.3 Эксперименты по исследованию токсичности спиртов.

4.1.4 Эксперименты по исследованию канцерогенности ариламинов

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

4.2 Анализ канцерогенности и токсичности в рамках модели "структура-активность". Использование комбинированного подхода.

4.2.1 Эксперименты по хронической токсичности и канцерогенности галогензамещённых алифатических углеводородов (ГАУ).

4.2.2 Результаты и обсуждение.

4.3 Эксперименты на массивах ПАУ.

4.3.1 Результаты и обсуждение.

4.3.2 Эксперимент на массиве Theochem [119].

4.4 Прогнозирование биологической активности гликозидов.

4.5 Эксперименты с графами жалоб.

Введение диссертации (часть автореферата) на тему «Машинное обучение на узорных структурах»

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

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

В ряде работ последних лет в области машинного обучения и разработки данных (Machine Learning, Data Mining) внимание исследователей сосредоточено на проблеме обучения на данных, заданных помеченными графами (например, [1—7]).

При решении задач типа "структура-активность" (Structure-Activity Relationship, см., например, [8]) структуры соединений часто представляются различными дескриптор-ными языками (например, язык ФКСП — фрагментарный код суперпозиции подструктур [9]), имеющих простую, с вычислительной точки зрения, реализацию теоретико-множественных операций и отношений над объектами.

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

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

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

1. Разработать математический аппарат приближенного представления различных классов помеченных графов;

2. Исследовать особенности приближенного представления помеченных графов;

3. Разработать на основе метода алгоритмы и программные модули построения проекций;

4. Провести анализ особенностей разработанного подхода на большом экспериментальном материале.

Следующие особенности работы определяют её научную новизну:

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

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

3. Сочетание математических и программных средств построения решёток и средств обработки данных, представленных помеченными графами.

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

Положения, выносимые на защиту:

1. Метод приближенного представления помеченных графов;

2. Эффективность разработанных алгоритмических и программных средств построения приближенного описания помеченных графов;

3. Практическая значимость метода в машинном обучение и обработке данных

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях:

1. 8-й национальной конференции по искусственному интеллекту (КИИ'2002), Коломна, 2002;

2. 6-й международной конференции "Информационное общество, интеллектуальная обработка информации, информационные технологии" (НТИ-2002), Москва, 2002;

3. 12-й международной конференции по понятийным структурам (12th International Conference on Conceptual Structures (ICCS'04)), Huntsville, AL, USA, 2004;

4. 9-й национальной конференции по искусственному интеллекту (КИИ'2004), Тверь, 2004;

5. 13-й международной конференции по понятийным структурам (13th International Conferenece on Conceptual Structures (ICCS'05)), Kassel, Germany, 2005;

6. 15-й международной конференции по индуктивному логическому программированию (15th International Conferenece on Inductive Logic Programming (ILP'05)), Bonn, Germany, 2005;

7. 12-й Всероссийской конференции "Математические методы распознавания образов" (ММРО-12), Звенигород, 2005;

8. 1 -ой международной конференции "Системный анализ и информационные технологии" (САИТ-2005), Переславль-Залесский, 2005;

9. Научно-технической конференции студентов, аспирантов и молодых специалистов "Информационные технологии в бизнесе" (диплом "Лучший доклад"), Москва, ГУ-ВШЭ, 2006;

10. Х111 Российском национальном конгрессе "Человек и лекарство" (3 место в конкурсе работ молодых учёных на симпозиуме "Бионинформатика и компьютерное конструирование лекарств"), Москва, 2006

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

Заключение диссертации по теме «Теоретические основы информатики», Самохин, Михаил Валерьевич

Заключение

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

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

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

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

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

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

Наиболее интересными направлениями дальнейших экспериментальных исследований предлагаемого подхода представляются следующие:

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

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

Список литературы диссертационного исследования кандидат технических наук Самохин, Михаил Валерьевич, 2006 год

1. Borgelt C., Berthold M. R. Mining Molecular Fragments: Finding Relevant Substructures of Molecules // Proc. 2nd IEEE International Conference on Data Mining (ICDM'02)/Ed. by N. Zhong, P. Yu. — Piscataway, NJ: IEEE Press, 2002. — P. 51-58.i

2. Inokuchi A., Washio Т., Motoda H. Complete Mining of Frequent Patterns from Graphs:

3. Mining Graph Data // Machine Learning. — 2003. — Vol. 50, No. 3. — P. 321-354.

4. Washio Т., Motoda H. State of the art of graph-based data mining// j-SIGKDD-EN. — 2003. — Vol. 5, No. 1. — P. 59-68.

5. Yan X., Han J. gSpan: Graph-Based Substructure Pattern Mining // Proc. IEEE International Conference on Data Mining(ICDM'02). — Los Alamitos, CA: IEEE Computer Society, 2002. — P. 721-724.

6. Yan X., Han J. CloseGraph: mining closed frequent graph patterns // Proc. of the 9th

7. G ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

8. SIGKDD'03)/ Ed. by L. Getoor, T. Senator, P. Domingos, C. Faloutsos. — New York, NY: ACM Press, 2003. — P. 286-295.

9. Molecular Similarity in Drug Design / Ed. by P. M. Dean. — London: Blackie Academic, 1995.

10. Блинова В. Г., Добрынин Д. А. Языки представления химических структур в интеллектуальных системах для конструирования лекарств // НТИ, Сер. 2. — 2000. — № 10.— С. 14-21.

11. Фабрикантова Е. Ф. Применение ДСМ-рассуждений для интеллектуального анализа данных и автоматического порождения гипотез о путях биотрансформации // НТИ, Сер. 2. — 2002. — No. 2. — Р. 8-44.

12. Биркгоф Г. Теория решеток. — М.: Наука, 1989.

13. Ganter В., Wille R. Formal Concept Analysis: Mathematical Foundations. — Berlin; Heidelberg: Springer-Verlag, 1999.

14. Davey B. A., Priestley H. A. Introduction to Lattices and Order. — Cambridge: Cambridge University Press, 2002.

15. Wille R. Restructuring Lattice Theory: an Approach Based on Hierarchies of Concepts // Ordered Sets / Ed. by I. Rival. — Dordrecht;Boston: Reidel, 1982. — P. 445-470.

16. Кузнецов С. О. ДСМ-метод как система автоматического обучения // Итоги науки и техники. Сер. Информатика. — 1991. — Т. 15. — С. 17—54.

17. LiquiereM., Sallantin J. Structural Machine Learning with Galois Lattice and Graphs// Proc. 15th International Conference on Machine Learning (ICML'98)/ Ed. by J. Shav-lik. — San Fransisco, С A: Morgan Kaufmann, 1998. — P. 305—313.

18. Гэри M., Джонсон Д. Вычислительные машины и труднорешаемые задачи.— М.: Мир, 1982.

19. Mitchell Т. Machine Learning. — The McGraw-Hill Companies, 1997.

20. Кузнецов С. О. Модели и методы автоматического обучения // Итоги науки и техники. Сер. Вычислительные науки. — 1991. — Т. 7. — С. 89—137.

21. Hutchinson A. Algorithmic Learning. — Oxford: Claredon Press, 1994.

22. King R. D., Srinivasan A., Dehaspe L. WARMR: A Data Mining tool for chemical data // J. Computer-Aided Molecular Design.— 2001.— Vol. 15, No. 2. — P. 173-181.

23. Kramer S. Structural Regression Trees // Proc. 13th National Conference on Artificial . Intelligence (AAAI'96). — Cambridge; Menlo Park: AAAI Press : MIT Press, 1996. —1. P. 812-819.

24. Финн В. К. Правдоподобные рассуждения в интеллектуальных системах типа ДСМ//Итоги науки и техники. Сер. Информатика.— 1991.— Т. 15.— С. 54—101.

25. Blinova V. G., Dobrynin D. A., Finn V. К., Kuznetsov S. О., Pankratova E. S. Toxicology analysis by means of the JSM-method//Bioinformatics.— 2003.— Vol. 19.— P. 1201-1207.

26. Pasquier N., Bastide Y., Taouil R., Lakhal L. Efficient Mining of Association Rules Using Closed Itemset Lattices //J. Inf. Systems. — 1999. — Vol. 24, No. 1. — P. 25-46.

27. Avidon V. V., Pomerantsev A. B. Structure-activity relationship oriented languages for chemical structure representation // J. Chem. Inf. Comput. Sci. — 1982. — Vol. 22, No. 4.— P. 207-214.

28. Kuznetsov S. O., Obiedkov S. A. Comparing performance of algorithms for generating concept lattices // J. of Experimental and Theoretical Artificial Intelligence. — 2002. — Vol. 14, No. 2-3. — P. 189-216.

29. Кузнецов С. О., Финн В. К. О модели обучения и классификации, основанной на операции сходства // Обозрение прикладной и промышленной математики. — 1996. — Т. 3, № 1.— С. 66-90.

30. Anshakov О. М., Finn V. К., Skvortsov D. P. On axiomatization of many-valued logics associated with the formalization of plausible reasonings // Stud. Log. — 1989. — Vol. 25, No. 4. — P. 23-47.

31. Mill J. S. A System of Logic, Ratiocinative and Inductive: Being a Connected View of the Principles of Evidence, and Methods of Scientific Integration. — London: J.W. Parker, 1843.

32. Michalski R., Stepp R. Machine Learning: An Artifical Intelligence Approach / Ed. by J. C. R.S.Michalski, T. Mitchell. — San Mateo, CA: Morgan Kaufmann, 1983.

33. Fisher D. Iterative optimization and simplification of hierarchical clusterings // J. Artificial Intelligence Research. — 1996. — Vol. 4. — P. 147-179.

34. Cohen W. W. Fast Effective Rule Induction // Proc. 12th International Conference on Machine Learning (ICML'95).— San Fransisco, CA: Morgan Kaufmann, 1995.— P. 115-123.

35. Furnkranz J., Widmer G. Incremental Reduced Error Pruning// Proc. 11th International Conference on Machine Learning (ICML'94).— San Fransisco, CA: Morgan Kaufmann, 1994.

36. Witten I. H., Frank E. Data Mining: Practical Machine Learning Tools with Java Implementations. — San Fransisco, CA: Morgan Kaufmann, 2000.

37. Quinlan J. R. Induction on Decision Trees //Machine Learning.— 1986.— Vol. 1, No. 1.— P. 81-106.

38. Quinlan J. R. C4.5: Programs for Machine Learning. — San Fransisco, CA: Morgan Kaufmann, 1993.

39. Quilllian M. R. Semantic Memory // Semantic Information Processing/ Ed. by M. Min-sky. — Cambridge, MA: MIT Press, 1968. — P. 227-270.

40. Sowa J. F. Conceptual Structures — Information Processing in Mind and Machine. — Reading, MA: Addison-Wesley, 1984.

41. Luks E. M. Isomorphism of graphs of bounded valence can be tested in polynomial time//J. Сотр. Syst. Sci. — 1982. — Vol. 25. — P. 42-65.

42. Hopcroft J. E., Wong J. K. Linear time algorithm for isomorphism of planar graphs (preliminary report)// Proc. of the 6th annual ACM symposium on Theory of computing. — New York, NY: ACM Press, 1974. — P. 172-184.

43. Bron C., Kerbosch J. Finding all cliques of an undirected graph // Communications of the ACM. — 1974.

44. Raymond J. W. Heuristics for similarity searching of chemical graphs using a maximum common edge subgraph algorithm // J. Chem. Inf. Comput. Sci. — 2002. — Vol. 42, No. 2.— P. 305-316.

45. McKay B. D. Practical Graph Isomorphism // Congressus Numerantium.— 1981.— Vol. 30. — P. 45-87.

46. Ullmann J. R. An algorithm for subgraph isomorphism // J. Association for Computing Machinery. — 1976. — Vol. 23, No. 1. — P. 31-42.

47. Kuramochi M., Karypis G. An efficient algorithm for discovering frequent subgraphs: Tech. Rep. 02-026. — Minneapolis, MN: University of Minnesota, 2002.

48. Inokuchi A., Washio Т., Nishimura K., Motoda H. A fast algorithm for mining frequent connected subgraphs: Research Report RT0448. — Tokyo: IBM Research, Tokyo Research Labaratoiy and Osaka University, 2002.

49. Кузнецов С. О., Самохин М. В., Харчевникова Н. В. Прогнозирование контрпродуктивных свойств химических соединений на основе узорных структур: сравнительный анализ подходов. Часть 1 // НТИ, Сер. 2. — 2006. — № 1. — С. 1-8.

50. Cook D. J., Holder L. В. Graph-Based Data Mining // IEEE Intelligent Systems. — 2000. — Vol. 15, No. 2. — P. 32-41.

51. Cameron-Jones R. M., Quinlan J. R. Efficient top-down induction of logic programs // SIGART Bulletin. — 1994. — Vol. 5, No. 1. — P. 33-42.

52. Muggleton S. Inverse Entailment and Progol // New Generation Computing.— 1995. — Vol. 13. — P. 245-286.

53. Provost E, Fawcett T. Robust classification for imprecise environments // Machine Learning. — 2001. — Vol. 42. — P. 203-231.

54. Braun J., Gugisch R., Kerber A., Laue R., Meringer M., Rucker C. MOLGEN-CID -A Canonizer for Molecules and Graphs Accessible through the Internet // J. Chem. Inf. Comput. Sci. — 2004. — Vol. 44, No. 2. — P. 542-548.

55. Nagle J. F. On ordering and identifying undirected linear graphs // J. Mathematical Physics. — 1966. — Vol. 7. — P. 1588-1592.

56. Арлазаров В. JI., Зуев И. В., Усков А. В., Фараджев И. А. Алгоритм приведения конечного неориентированного графа к каноническому виду // Журнал Вычислительной Математики и Математической Физики. — 1974. — Т. 14, № 4. — С. 734—747.

57. Randic М. On the recognition of identical graphs representing molecular topology // J. Chem. Phys. — 1974. — Vol. 1974. — P. 3920-3928.

58. Randic M. On canonical numbering of atoms in a molecule and graph isomorphism // J. Chem. Inf. Сотр. Sci. — 1977. — Vol. 17, No. 3. — P. 171-180.

59. Randic M., Brissey G. M., Wilkins C. L. Computer perception of topological symmetry via canonical numbering of atoms // J. Chem. Inf. Comput. Sci.— 1981. — Vol. 21, No. 1. — P. 52-59.

60. Hendrickson J. В., Toczko A. G. Unique numbering and cataloging of molecular structures//J. Chem. Inf. Comput. Sci. — 1983. — Vol. 23, No. 4. — P. 171-177.

61. Kvasnicka V., Pospichal J. Canonical indexing and constructive enumeration of molecular graphs //J. Chem. Inf. Comput. Sci. — 1990. — Vol. 30, No. 2. — P. 99-105.

62. Kvasnicka V., Pospichal J. An improved method on constructive enumeration of graphs//J. of Mathematical Chemistry. — 1992. — Vol. 9, No. 2. — P. 181-196.

63. Lukovits I. Isomer generation: Syntactic rules for detection of isomorphism // J. Chem. Inf. Comput. Sci. — 1999. — Vol. 39, No. 3. — P. 563-568.

64. Lukovits I. Isomer generation: Symantic rules for detection of isomorphism // J. Chem. Inf. Comput. Sci. — 1999. — Vol. 40, No. 2. — P. 361-366.

65. Morgan H. L. The generation of a unique machine description for chemical structures-a technique developed at chemical abstracts service // J. Chem. Doc. — 1965. — Vol. 5, No. 2.—P. 107-113.

66. Weininger D. SMILES, a chemical language and information system. 1. introduction to methodology and encoding rules // J. Chem. Inf. Comput. Sci. — 1988. — Vol. 28, No. 1.— P. 31-36.

67. Weininger D., Weininger A., Weininger J. L. SMILES. 2. algorithm for generation of unique SMILES notation // J. Chem. Inf. Comput. Sci. — 1989. — Vol. 29, No. 2. — P. 97-101.

68. Paton K. An algorithm for finding a fundamental set of cycles of a graph // Communications of the ACM. — 1969. — Vol. 12. — P. 514-518.

69. Mateti P., Deo N. On algorithms for enumerating all circuits of a graph // SIAM J. on Computing. — 1975. — Vol. 5. — P. 90-101.

70. Read R. C., Taijan R. E. Bounds on backtrack algorithms for listing cycles, paths and spanning trees// Networks. — 1975. — Vol. 5. — P. 90-101.

71. Syslo A. A. An efficient cycle vector space algorithm for listing all cycles of planar graph// SIAM J. on Computing. — 1981. — Vol. 10. — P. 797-808.

72. Deo N., Prabhu G. M., KrishnamoorthyM. S. Algorithms for generating fundamental cycles in a graph // ACM Transanctions on Mathematical Software. — 1982. — Vol. 8. — P. 26-42.

73. Horton J. D. A polynomial-time algorithm to find the shortest cycle basis of a graph // SIAM J. on Computing. — 1987. — Vol. 16, No. 2. — P. 358-366.

74. Dijkstra E. W. A note on two problems in connection with graphs // Numerische Math-ematik.— 1959.— Vol. 1. — P. 269-271.

75. Tierman J. An efficient search algorithm to find the elementary circuits of a graph // Communications of the ACM. — 1970. — Vol. 13. — P. 722-726.

76. Vismara P. Union of all the minimum cycle bases of a graph // Electronical J. of Combinatorics.— 1997.— Vol. 4, No. 1.— P. 73-87. Режим доступа: http://www.combinatorics.org.

77. Plotkin M. Mathematical basis of ring-finding algorithms in CIDS // J. Chem. Doc. — 1971.—Vol. 11.—P. 60-63.

78. Степанец Г. Ф. Базисные системы вектор-циклов с экстремальными свойствами в графах // Успехи математических наук АН СССР.— 1964.— Т. 19, № 2.— С. 171-175.

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

80. Filimonov D. A., Poroikov V. V. PASS: Computerized prediction of biological activity spectra for chemical substances // Bioactive Compound Design: Posibilities for Industrial Use. — Oxford: BIOS Scientific Publishers, 1996. — P. 47-56.

81. Filimonov D., Poroikov V., Borodina Y., Gloriozova T. Chemical similarity assessment through multilevel neighborhoods of atoms: Definition and comparison with the other descriptors //J. Chem. Inf. Comput. Sci. — 1999. — Vol. 39, No. 4. — P. 666-670.

82. Poroikov V. V., Filimonov D. A. PASS: Prediction of Biological Activity Spectra for Substances // Predictive Toxicology / Ed. by C. Helma. — N.Y.: Taylor & Frensis, 2005. — P. 459-478.

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

84. Лейбов А. Е. Некоторые способы реализации операции сходства для химически ориентированных экспертных систем типа ДСМ // НТИ, Сер. 2. — 1996. — № 5—6. — С. 37-44.

85. Забежайло М. И., Ивашко В. Г., Кузнецов С. О., Михеенкова М. А., Хазанов-ский К. П., Аншаков О. М. Алгоритмические и программные средства ДСМ-метода автоматического порождения гипотез // НТИ, Сер. 2. — 1987. — № 10. — С. 1—13.

86. Матвеев А. А. Алгоритм построения метаболической сети // НТИ, Сер. 2. — 2002. — №6.—С. 35-45.

87. Добрынин Д. А. Алгоритмы поиска фрагментов в молекулярных графах для автоматического кодирования химических структур в интеллектуальных системах для конструирования лекарств // НТИ, Сер. 2. — 2002. — № 6. — С. 51-57.

88. Кузнецов С. О., Самохин М. В., Харчевникова Н. В. Прогнозирование контрпродуктивных свойств химических соединений на основе узорных структур: сравнительный анализ подходов. Часть 2 // НТИ, Сер. 2. — 2006. — № 2. — С. 1-10.

89. Блинова В. Г., Добрынин Д. А., Жолдакова 3. И., Харчевникова Н. В. Изучение соотношений структура-токсичность спиртов с использованием ДСМ-метода // НТИ, Сер. 2. — 2001. — № 10. — С. 13-18.

90. Guilian W., Naibin В. Structure-activity relationships for rat and mouse LD50 of miscellaneous alcohols// Chemosphere. — 1998. — Vol. 35, No. 7. — P. 1475-1483.

91. Franke R., Grushka A., Benigni R. Prediction of rodent carcinogenecity of aromatic amins: a quantitative structure activity relationships model // Carcinogenesis.— 2001. — Vol. 22. — P. 1561-1571.

92. Korzekwa К. R., Jones J. R, Gillette J. R. Theoretical studies on cytochrome p-450 mediated hydroxylation: a predictive model for hydrogen atom abstractions // J. American Chemical Society. — 1990. — Vol. 112. — P. 7042-7070.

93. Yin H., Anders M., Korsekwa K-, Higgins L. A., Thummel К- E. Predicting safer chemicals: Predicting the rates of metabolism of halogenated alkanes // Proc. National Academy of Sciences of the USA.— 1995. — Vol.92. — P. 11076-11080.

94. Woo Y.-T., Lai D., McLain J. L., et al. Use of mechanism-based structure-activity relationships analysis in carcinogenic ranking for drinking water desinfection by-products // Environ. Health Perspect. — 2002. — No. 1. — P. 75-87.

95. The Carcinogenic Potency Database (CPDB), University of California, Berkley, USA. Режим доступа: http://potency.berkeley.edu/cpdb.html.

96. ГН 2.1.5.1315-03. Предельно допустимые концентрации (ПДК) химических веществ в воде водных объектов хозяйственно-питьевого и культурно-бытового водопользования. — 2003.

97. Канцерогенные вещества. Справочник. Материалы международного агентства по изучению рака / Под ред. А. Ф. Карамашевой. — Медицина, 1987.

98. Dipple A. Polynuclear Aromatic Carcinogens // Chemical Carcinogens / Ed. by С. E. Searle.— ACS Monograph No. 172. Washington, DC: Amer. Chem. Soc., 1976.— P. 245-314.

99. Yan L.-S. Study of carcinogenic mechanism of polycyclic aromatic hydrocarbons-extended bay region theory and its quantitative model // Carcinogenesis. — 1985. — No. 1. —

100. Badger G. M. The Chemical Basis of Carcinogenic Activity. — 1962.

101. Jerina D. M., Lehr R. E. Microsomes and Drug Oxidation / Ed. by V. Ullrich. — Oxford: Pergamon Press, 1977. — P. 709-720.

102. Lowe J. P., Silverman B. D. MO theory of ease of formation of carbocations derived from nonalternant polycyclic aromatic hydrocarbons // J. American Chemical Society.— 1984. — Vol. 106, No. 20. — P. 5955-5958.

103. Дьячков П. H. Квантовохимические расчеты в изучении механизма действия и токсичности чужеродных веществ // Итоги науки и техники. Сер. Токсикология. — 1990. — Т. 16.— С. 280.

104. Flesher J. W., Horn J., Lehner A. F. Molecular modeling of carcinogenic potential in polycyclic hydrocarbons // J. Molecular Structure (Theochem). — 1996. — Vol. 362, No. 1. — P. 29-49.

105. N-гликозиды производных индоло2,3-а.карбазола / А. А. Бахмедова, Л. Д. Гараева, О. В. Горюнова, Т. Д. Миникер, И. Л. Плихтяк, Л. В. Эктова, Т. П. Иванова и др. // Биоорганическая химия. — 1997. — Т. 23, № 8. — С. 667-674.

106. Мельник С. Я. Экспериментальная онкология на рубеже веков // Синтез и изучение гликозидов, производных бисиндола и родственных индоло2,3-а.карбазолов / Под ред. М. И. Давыдова, А. Ю. Барышникова. — М., 2003. — С. 281-293.

107. Апрышко Г. Н. Информационная система по противоопухолевым агентам // Российский биотерапевтический журнал. — 2002. — № 2. — С. 7—10.