Содержание к диссертации
Введение
1 Основные определения 8
1.1 Теория решёток и Анализ Формальных Понятий 8
1.1.1 Частично упорядоченные множества и решётки 8
1.1.2 Анализ формальных понятий (АФП) 10
1.1.3 Узорные структуры и их проекции 13
1.1.3.1 Проекции узорных структур 16
1.2 Машинное обучение и анализ данных 17
1.2.1 Анализ Формальных Понятий и ДСМ-метод 20
1.2.1.1 Стратегия последовательного покрытия гипотезами в ДСМ-методе 24
1.2.2 Метод порождения правил с исключениями. RIPPER 26
1.2.3 Наивный метод Байеса (Naive Bayes) 27
1.2.4 Методы индуктивного порождения деревьев решений 29
2 Графы и их проекции 32
2.1 Общий взгляд 32
2.2 Графы и узорные структуры 35
2.3 Различные варианты проекций на графах 51
3 Алгоритмическая реализация приближенного описания узорных структур 59
3.1 Общий взгляд 59
3.2 Подробное описание 60
3.2.1 Порождение кандидатов 64
3.2.2 Алгоритмы для различных вариантов проекции 65
3.2.3 Использование алгоритма в ДСМ-методе 67
3.2.4 Оценка быстродействия 68
4 Машинные эксперименты и результаты 70
4.1 Эксперименты с химическими данными 73
4.1.1 Эксперименты на массиве РТС 73
4.1.2 Проекции графов "на ROC-диаграмме" (результаты для массива РТС) 74
4.1.3 Эксперименты по исследованию токсичности спиртов 81
4.1.4 Эксперименты по исследованию канцерогенности ариламинов . 82
4.1.5 Эксперименты по поиску достаточных условий прохождения биотрансформации химических соединений в организме 83
4.2 Анализ канцерогенности и токсичности в рамках модели "структура-актив
ность". Использование комбинированного подхода 83
4.2.1 Эксперименты по хронической токсичности и канцерогенности гало-гензамещённых алифатических углеводородов (ГАУ) 85
4.2.2 Результаты и обсуждение 88
4.3 Эксперименты на массивах ПАУ 92
4.3.1 Результаты и обсуждение 98
4.3.2 Эксперимент на массиве Theochem [119] 102
4.4 Прогнозирование биологической активности гликозидов 105
4.5 Эксперименты с графами жалоб 107
Заключение 111
Литература
- Анализ формальных понятий (АФП)
- Графы и узорные структуры
- Порождение кандидатов
- Эксперименты по поиску достаточных условий прохождения биотрансформации химических соединений в организме
Введение к работе
Объект исследования и актуальность темы. Актуальность работы определяется ростом интереса к проблематике приобретения знаний из данных, заданных помеченными графами, в области машинного обучения и разработки данных (в частности, для задач прогнозирования биологической активности химических соединений), а также необходимостью разработки эффективных процедур вычисления на графах (например, сходства множеств графов).
Решение аналитических задач, связанных с производством, довольно часто сопряжено с необходимостью проведения дорогих экспериментов и исследований. Например, при разработке лекарственных препаратов требуется проверка синтезированных соединений на лабораторных животных, подразумевающая проведение дорогостоящих и продолжительных опытов. Другой пример — анализ жалоб, предъявляемых компании покупателями (или получателями услуг), на качество предоставляемых товаров (или услуг). Основной проблемой в этой задаче является оценка обоснованности жалоб и дальнейшее принятие решения, для чего порой необходимо привлекать дополнительные кадровые ресурсы. Уменьшения затрат при решении подобных задач можно достичь с помощью разработки компьютерных программ, которые могут обучаться по прецедентам (такие программы называются системами машинного обучения).
В ряде работ последних лет в области машинного обучения и разработки данных (Machine Learning, Data Mining) внимание исследователей сосредоточено на проблеме обучения на данных, заданных помеченными графами (например, [1—7]).
При решении задач типа "структура-активность" (Structure-Activity Relationship, см., например, [8]) структуры соединений часто представляются различными дескриптор-ными языками (например, язык ФКСП — фрагментарный код суперпозиции подструктур [9]), имеющих простую, с вычислительной точки зрения, реализацию теоретико-множественных операций и отношений над объектами.
В тоже время недостаточная гибкость дескрипторных языков для адекватного описания взаимосвязей различных подграфов молекулярных графов в ряде задач (например, задача прогнозирования путей биотрансформации химических соединений в организ- ме [10]) определяет необходимость использования более точных способов описания исходных молекул (например, с помощью помеченных графов). При этом область применения такого рода подхода к представлению и анализу данных не ограничивается только химическими приложениями, и подход может быть использован в произвольных задачах анализа данных, в которых исходные данные являются помеченными графами.
В связи с вышеизложенным, целью диссертационной работы является разработка методов приближенного представления помеченных графов — проекций, реализация эффективных алгоритмов вычисления проекций графов, интеграция процедур вычисления проекций на графах с различными методами машинного обучения, а также расширение решателя ДСМ-метода автоматического порождения гипотез добавлением подсистемы, реализующей операции сходства на проекциях.
В соответствии с целью исследования были поставлены следующие задачи:
Разработать математический аппарат приближенного представления различных классов помеченных графов;
Исследовать особенности приближенного представления помеченных графов;
Разработать на основе метода алгоритмы и программные модули построения проекций;
Провести анализ особенностей разработанного подхода на большом экспериментальном материале.
Следующие особенности работы определяют её научную новизну:
Разработка эффективного, гибкого и компактного приближенного представления помеченных графов (проекций).
Разработка алгоритмических и программных средств вычисления проекций.
Сочетание математических и программных средств построения решёток и средств обработки данных, представленных помеченными графами.
Научная и практическая ценность. В настоящей работе разработан математический аппарат проекций для различных классов помеченных графов. Предложены и алгоритмически и программно реализованы вычислительные процедуры построения приближенного описания помеченных графов (проекций). Проведены эксперименты, подтвержда- ющие адекватность предложенных методов задачам качественного анализа данных, в частности, в анализе биологических активностей химических соединений из различных химических рядов и анализе жалоб. Получены новые результаты в исследованиях биологической активности химических соединений различных рядов, правильно прогнозированы биологические активности соединений, которые не удалось исследовать с помощью применения дескрипторных языков описания (таких как ФКСП-кодов). Положения, выносимые на защиту:
Метод приближенного представления помеченных графов;
Эффективность разработанных алгоритмических и программных средств построения приближенного описания помеченных графов;
Практическая значимость метода в машинном обучение и обработке данных
Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях:
8-й национальной конференции по искусственному интеллекту (КИИ'2002), Коломна, 2002;
6-й международной конференции "Информационное общество, интеллектуальная обработка информации, информационные технологии" (НТИ-2002), Москва, 2002;
12-й международной конференции по понятийным структурам (12th International Conference on Conceptual Structures (ICCS'04)), Huntsville, AL, USA, 2004;
9-й национальной конференции по искусственному интеллекту (КИИ'2004), Тверь, 2004;
13-й международной конференции по понятийным структурам (13th International Conferenece on Conceptual Structures (ICCS'05)), Kassel, Germany, 2005;
15-й международной конференции по индуктивному логическому программированию (15th International Conferenece on Inductive Logic Programming (ILP'05)), Bonn, Germany, 2005;
12-й Всероссийской конференции "Математические методы распознавания образов" (ММРО-12), Звенигород, 2005;
1 -ой международной конференции "Системный анализ и информационные технологии" (САИТ-2005), Переславль-Залесский, 2005;
9. Научно-технической конференции студентов, аспирантов и молодых специалистов "Информационные технологии в бизнесе" (диплом "Лучший доклад"), Москва, ГУ-ВШЭ, 2006;
10. XIII Российском национальном конгрессе "Человек и лекарство" (3 место в конкурсе работ молодых учёных на симпозиуме "Бионинформатика и компьютерное конструирование лекарств"), Москва, 2006
Диссертация состоит из введения, четырёх глав, заключения и списка литературы.
Во введении раскрывается актуальность темы диссертации, формулируются проблемы исследования, определяется цель работы, описываются методы исследования, излагаются основные научные результаты, обосновывается теоретическая и практическая значимость работы, даётся её общая характеристика.
В Главе 1 введены основные определения теории решёток, кратко описан язык анализа формальных понятий. Рассмотрены некоторые аспекты машинного обучения в целом и отдельных методов машинного обучения (в том числе основанных на теоретико-решёточных конструкциях), необходимые для изложения результатов применения предлагаемого подхода приближенного описания помеченных графов. Под анализом данных мы понимаем, главным образом, обнаружение в данных всевозможных зависимостей, обладающих той или иной степенью правдоподобия, и использование этих зависимостей для восстановления полноты данных (в случае их изначальной неполноты), классификации новых данных и т.п. Далее кратко описаны основные идеи ДСМ-метода автоматического порождения гипотез.
В Главе 2 — "Графы и их проекции" приводится сравнение различных подходов описания данных, представленных помеченными графами. Также в этой главе вводятся необходимые определени из теории графов и формулируется предлагаемый подход приближенного описания помеченных графов.
Анализ формальных понятий (АФП)
Анализ формальных понятий (АФП)
Определение 1.11. Формальный контекст К есть тройка {G, М, I), где G — множество, называемое множеством объектов, М — множество, называемое множеством признаков, I C.G х М — отношение.
Отношение I интерпретируется следующим образом: для g є G, т є М имеет место glm, если объекту обладает признаком т.
Для формального контекста К = (G, М, I) и произвольных AQGHBCM определена пара отображений: А := {т є М glm для Bcexg є А}, В := {g є G glm для всех т є В}, которые задают соответствие Галуа между частично упорядоченными множествами (2е, С) и (2м, С) (см. Раздел 1.1.1), а оператор ()" является оператором замыкания на G О М — дизъюнктном объединении G и М, т.е. для произвольного А С G или А С М имеют место следующие соотношения [11]: 1. АСА"(экстенсивность), 2. А"" = А" (идемпотентность), 3. если Л С С, то А" с С" (изотонность). Множество Л называется замкнутым, если Л" = Л [11].
Определение 1.12. Формальное понятие формального контекста К = (G,M,I) есть пара (А, В), где Л с G, В С М, А = В и В = А. Множество Л называется объёмом, а В — содержанием понятия (Л, В).
Очевидно, что объем и содержание произвольного формального понятия являются замкнутыми множествами.
Множество формальных понятий контекста К, которое мы будем обозначать посредством Ш(С,ЛЇ,7), частично упорядочено по вложению объёмов: формальное понятие X = (А, В) является менее общим (более частным), чем понятие Y = (C,D), (А, В) (С,D), если ЛСС, что эквивалентно D С В (Y — обобщение X).
В работе [11] было показано, что подмножества произвольного множества, замкнутые относительно заданной на нем операции замыкания, образуют полную решётку, а в работах [12,14] было показано, что множество всех понятий формального контекста К образует полную решётку.
Определение 1.13. Множество понятий контекста Ш(С,Л1,7) образуют решётку ШР,М,1) := (S(G,M,/),A,V), где (ЛЬВ,) Л (А2,В2) = (Ах П Л2,(Ах П Л2) ). и (ЛЬВ,) V (Лг, Вг) = ((В\ ПДгУ. By ПВ2). Такие решётки называют решётками понятий или решётками Галуа [12].
Любая полная решётка изоморфна решётке понятий некоторого формального контекста [12]. В качестве объектов этого контекста нужно выбрать Л-неразложимые элементы, а в качестве признаков — V-неразложимые элементы исходной решётки. Тогда объект g в контексте будет обладать признаком т, если элемент решётки, соответствующий g, находится "под" элементом, соответствующим т.
Определение 1.14. Строчно- (столбцево-)редуцированным называется такой формальный контекст, в котором всякое объектное (признаковое) понятие является V-нераз-ложимым (Л-неразложимым). Редуцированным называется формальный контекст, являющийся одновременно строчно- и столбцево-редуцированным.
Определение 1.15. Пусть А,В С М формального контекста B(G,MJ), тогда выражение Л —» В называется импликацией (на множествах признаков), если А с В (или В С А"), т.е. все объекты из G, обладающие множеством признаков А, обладают также множеством признаков В.
Аналогичным образом определяются импликации на множествах объектов. Наличие импликации А — Вв контексте К соответствует тому, что в диаграмме решётки Ш(К) формальное понятие (А , А") находится ниже формального понятия (В1, В"). Импликации формального контекста удовлетворяют аксиомам Армстронга [12] для произвольных X, У, Z: 1. Х- Х; 2. ECXKX-4YTOXUZ- Y; 3. EamX YnYUZ- WToX\JZ- W. Помимо определённых выше однозначных (one-valued) формальных контекстов в анализе формальных понятий изучаются многозначные (many-valued) контексты:
Определение 1.16. Многозначный формальный контекст есть четвёрка (G,M, W,J), где G,M,W — множества (объектов, признаков и значений признаков, соответственно), а / — тернарное отношение/ QGxMxW, задающее значение w признака т, причём:
(g, т, w) є / и {g, т, v) є / влечёт w = v
Многозначные признаки могут рассматриваться как отображения G — W, таким образом можно обозначать m(g) = w вместо (g,m,w) є /.
Процедура сведения многозначных контекстов к однозначным называется шкалированием (scaling). Для шкалирования каждый признак многозначного контекста представляется формальным контекстом, называемым шкалой.
Определение 1.17. Шкала для признака т многозначного контекста (G, М, W, J) есть (однозначный) контекст Sm := (Gm,Mm,Im) такой, что m(G) С Gm. Объекты в шкале называются значениями шкалы, а признаки — признаками шкалы.
Определение 1.18. Пусть задан многозначный контекст {G,M, W,J) и шкалы Sm, т є М, тогда производным контекстом будем называть контекст (G,N,J), где множество признаков ./V := итемМт (Мт := {т} х М) и отношение gJ(m,n) :-ФФ- (m(g) = wn wlmn).
В нашей работе будет использоваться один из вариантов шкалирования — порядковое шкалирование. Порядковая шкала Оя := (я, я, ) используется для признаков, значения которых упорядочены относительно некоторого порядка , а обладание объектом некоторым значением признака влечёт обладание всеми меньшими значениями признака. Возможные виды шкалирования рассмотрены в [12].
Графы и узорные структуры
Теперь рассмотрим частный случай узорной структуры, возникающий при представлении объектов помеченными графами. Для дальнейшего изложения метода и реализующих его алгоритмов нам понадобятся следующие определения.
Определение 2.1. Помеченный граф Г есть пятёрка вида ((V, /), (Е, Ь), С), где V — множество вершин, ЕС V х V — множество рёбер, I: V — С — функция, сопоставляющая метки вершинам, b: Е — С — функция, сопоставляющая метки рёбрам.
Определение 2.2. Помеченные графы Гі = ((И, /і), (Е\, Ь\), С) и Г2 = ((. /2), (Яг, fa), С) изоморфны (Гі = Гг), если существует взаимнооднозначное отображение : V — И такое, что оно 1) сохраняет ребра: (v, w) є Еч « ( /?(о), (ш)) Є ь 2) учитывает равенство на метках: h((p(v)) = h(v).
Рассмотрим следующую полурешётку (G, П) на множествах графов с метками вершин и рёбер из некоторого множества . Для определения полурешётки на графах дадим сначала определение частичного порядка на графах. Считаем, что изоморфные графы неразличимыми или, что то же самое, что частичный порядок задан на классах эквивалент-ностях, состоящих из изоморфных графов. В простейшем случае порядок задаётся отношением изоморфизма подграфу: Гг Гі, если Гг изоморфен подграфу Гі. В общем случае, когда задан порядок на метках из С, порядок на графах должен учитывать ещё и его.
В нашей работе мы рассматриваем только связные подграфы. Отсутствие в определении условия связности подграфов, приводит к рассмотрению более сложной с вычис лительнои точки зрения модели, так как в этом случае, например, каждый связный подграф может быть изоморфен связной компоненте большого числа несвязных графов.
Определение 2.3. Для пары графов Гі := ((Fb l{), (Eh &i), С) и Г2 := ((V2, /2), (E2t b2), С) из G будем говорить, что Гі доминирует над Г2 или Г2 Гі (или Г2 является подграфом Гі), если существует взаимнооднозначное отображение р : V2 — V\ такое, что оно 1) сохраняет ребра: (v,w) є Е2 = ( / ( ). vC )) Є ь 2) учитывает порядок на метках: Ш Цф)).
Очевидно, что, если Гі Г2 и Г2 Гь то Гі и Г2 изоморфны. Отношение есть частичный порядок, если графы рассматриваются с точностью до изоморфизма.
Пример 2.1. Пусть порядок на множестве меток вершин задан следующим образом С = {С, NH2, СНз, ОН, х}, тогда имеем
Операция П — идемпотентна, коммутативна и ассоциативна. С помощью этой операции можно определить узорную структуру, положительные и отрицательные гипотезы.
Узором в таком случае будет замкнутое множество графов, т.е. множество графов X, обладающее свойством X = Х.
Пример 2.4. Рассмотрим ДСМ-гипотезы для массива данных, где положительные примеры описаны графами Гі,..,Г4, а отрицательные — графами Г5 и Ге. В данном случае {Гі} П {Гг} П {Г3} и {Г2} П {Г3} П {Г4} являются минимальными положительными гипотезами, в то время как {Гі} П {Г2} П {Гз} П {Г4} не является положительной гипотезой (мы можем не использовать скобок в силу ассоциативности операции П). Положительные примеры:
Понятие замкнутого множества графов тесно связано с понятием замкнутого графа [6], используемого для вычисления ассоциативных правил на парах графов. Замкнутые графы определяются в работе [6] (в терминах, так называемого, "countinginference") следующим образом: для массива данных D (содержащего данные в форме помеченных графов), поддержка графа g или support(g) есть множество (или размер множества) графов в D, у которых есть подграф, изоморфный графу g.
Граф g является замкнутым, если все надграфы / графа g имеют другую поддержку. Подчеркнём, что в данном определении речь идёт о замкнутом графе, а не замкнутом множестве графов. Как уже говорилось выше, замкнутые множества графов образуют нижнюю полурешётку по отношению к оператору П, а всякая конечная нижняя полурешётка может быть пополнена до решётки введением единичного (максимального) элемента. На замкнутых графах такая операция не может быть определена. В общем случае, в частично упорядоченном множестве замкнутых графов нельзя однозначно определить инфинумы и супремумы двух замкнутых графов. Тем не менее, существует тесная связь между понятием замкнутого графа и понятием замкнутого множества графов.
Предложение 2.1. Пусть массив данных задан узорной структурой (, (Дп), 5). Тогда
1. Для любого замкнутого графа g существует замкнутое множество графов G такое, что g є G.
2. Для замкнутого множества графов G любой граф g є G есть замкнутый граф.
Доказательство. 1. Рассмотрим замкнутое множество графов G = {g}. Поскольку G состоит из всех максимальных общих подграфов графов, у которых есть подграф, изоморфный g, множество G содержит в качестве элемента либо g, либо его надграф /. В первом случае имеет место свойство 1. Во втором случае, произвольный граф из G, у которого есть подграф, изоморфный g, должен также содержать подграф, изоморфный /, и таким образом, / имеет такую же поддержку, что и g, что противоречит замкнутости g. Таким образом, G = {g} есть замкнутое множество графов, удовлетворяющее свойству 1.
2. Рассмотрим замкнутое множество графов G и произвольный граф g Є G. Если g не замкнутый, то для него существует надграф /, имеющий ту же поддержку, что и g, а, следовательно, ту же поддержку что все элементы множества G. Поскольку G есть множество всех максимальных общих подграфов графов, описывающих примеры из множества G (т.е., с той же поддержкой), то должно иметь место / є G. Это противоречит тому фак ту, что g є G, так как замкнутое множество графов не может содержать одновременно некоторый граф и его надграф (иначе замыкание такого множества не совпадало бы с ним самим).
Так как проверка отношения на помеченных графах является NP-полной задачей [19], то и вычисление гипотез в узорных структурах, основанных на помеченных графах может быть очень трудоёмким. В [16] были определены операторы проекций, используемые для приближенного описания множеств графов.
Порождение кандидатов
Одним из основных шагов алгоритма построения проекции графа Г является процедура порождения кандидатов. Очевидной трудностью, которая возникает при разработке алгоритма поуровнего построения всех подмножеств некоторого множества, является большое число проверок изоморфизма графов и графа подграфу. В связи с этим существенную роль играет применение различных дополнительных условий, позволяющих избежать избыточного порождения кандидатов и огромного числа проверок изоморфизма графов.
На этом шаге порождается множество кандидатов размера т + 1 по заданному множеству кандидатов размера т графа Г. Подграф Л размера т + 1 порождается путём добавления вершин и рёбер из графа Г \ Л к подграфу Л размера т.
Простым, но эффективным, средством избежать построения одних и тех же подграфов несколько раз при порождении кандидатов является использование порядка, заданного на множестве вершин графа. Пусть произвольный порядок, заданный на множестве вершин Vr графа Г. Обозначим через s единственную вершину подграфа candidate из множества candidates, полученного применением процедуры getOneVertexSubgraphs. Процедура extendGraph (см. Алгоритм 3.2.3) расширяет подграф candidate только с помощью тех вершин, которые предшествуют вершине s относительно порядка . Таким образом, процедура getlncidentEdges в Алгоритме 3.2.3 возвращает только те инцидентные вершине v ребра (у, w), для которых верно v, w s. В нашей реализации на множестве вер шин был задан линейный порядок, соответствующий последовательности вершин на входе алгоритма.
Описанное выше условие позволяет порождать подграфы без повторов, поэтому остаётся единственный шаг алгоритма, на котором необходимо использовать точный поиск изоморфизма — добавление порождённого подграфа в множество projection. Как уже было сказано выше, использование различных инвариантов графа позволяет эффективно проверить неизоморфность пары графов, а значит существенно сократить число точных проверок на изоморфизм.
Алгоритм 3.2.3 является реализацией (Z, -проекции (см. Определения 2.11, 2.14 в Разделе 2.3). В тоже время существуют задачи, в которых целесообразно использовать другие варианты проекций, поэтому, следуя определениям проекций, приведённых в Разделе 2.3 были разработаны алгоритмы, реализующие другие типы проекций. Так, например, программная реализация -циклической проекции графов приведена в Алгоритме 3.2.4.
Для вычисления циклической проекции необходимо найти в графе все элементарные циклы. Поскольку минимальный циклический базис может быть не единственным для: данного графа, ищется объединение всех минимальных циклических базисов в графе (см. выше, Раздел 1). Для поиска минимальных циклов была использована идея алгоритма (процедура calcUnionMCB{T)\ предложенная в работе [85].
Реализация варианта алгоритма поиска множества релевантных циклов и применение релевантных циклов для построения циклической -проекции графа представлено в Алгоритме 3.2.4.
Процедура extendCGraph (см. Алгоритм 3.2.4) расширяет подграф candidate є candidates графа Г, добавляя элементарный цикл С из множества 7г \ candidate, который содержит хотя бы одно общее с подграфом candidate ребро (Бе є Ее — є є Ecan(ndate) На множестве вершин графа Г задан линейный порядок, соответствующий последовательности вершин на входе алгоритма. Каждому подграфу candidate Є candidates сопоставляется битовая строка, содержащая номера вершин из множества candidate- Поскольку рассматриваются только связные индуцированные подграфы, то битовая строка номеров вершин однозначно определяет подграф. При добавлении подграфа в множество candidates процедура isValidCandidate(extCandidate, candidates) проверяет соответствующую расширению подграфа candidate битовую строку относительно множества
битовых строк подграфов candidates, за счёт чего происходит быстрый отсев "полных дублей" (т.е. подграфов с одинаковыми битовыми строками номеров вершин).
Ещё один алгоритм реализует вариант проекции из Определения 2.16. Этот алгоритм объединяет в себе Алгоритмы 3.2.3 и 3.2.4. Сначала алгоритм вычисляет элементарные циклы, как на первом шаге Алгоритма 3.2.4. На подграфе Л графа Г, множество рёбер которого Е\ — Ег \ (JceTj( c) (на древесной части графа Г) выполняется процедура getOneVertexSubgraph. Затем алгоритм достраивает подграфы из множества candidates, начиная с одновершинных подграфов и подграфов, состоящих из одного элементарного цикла, как в Алгоритме 3.2.3.
Эксперименты по поиску достаточных условий прохождения биотрансформации химических соединений в организме
Изучение свойств химических соединений в рамках модели "структура-активность" с применением ДСМ-метода показало, что схема, основанная на чисто структурном описании молекул, далеко не всегда даёт правильный ответ на вопрос, будет ли анализируемое соединение обладать заданными биологическими свойствами.
Существует ряд задач, в которых структурная формула не определяет однозначно проявление изучаемых свойств, как, например, в задаче прогнозирования токсичности, и, в частности, канцерогенное химических соединений.
Токсичность многих соединений определяется их биоактивацией под действием ферментных систем организма, токсический эффект в этом случае вызывается взаимодействием не исходных соединений, а их метаболитов с макромолекулами. Определение наи 84 более активного метаболита из всех возможных для данного соединения может быть осуществлено с использованием методов квантовой химии. Можно предположить, что уровень токсического эффекта в ряду структурно родственных химических соединений должен зависеть от параметра, характеризующего реакционную способность конечных метаболитов. Совместное использование для прогнозирования биологической активности ДСМ-метода и числовых параметров — физических характеристик, в частности, характеристик реакций образования метаболитов и их реакционной способности, позволяет учитывать возможность различных процессов биотрансформации и взаимодействия с организмом, в частности, процессов детоксикации.
В работах [105,106] комбинированный подход, в котором ДСМ-рассуждения проводятся на гибридных объектах, состоящих из структурной части, описанной с помощью ФКСП [102], и числовых параметров, был применён для прогноза канцерогенной активности полициклических ароматических углеводородов (ПАУ) [105] и галогенсодержащих алифатических углеводородов [ 106].
Эти соединения являются непрямыми канцерогенами, т.е. их канцерогенная активность определяется биоактивацией в организме. Для непрямых канцерогенов расчёт числовых параметров, характеризующих уровень канцерогенности, должен состоять из следующих этапов: выделение для данного соединения возможных метаболитов; выделения наиболее канцерогенного (устойчивого) метаболита, и приписывания его уровня активности исходному веществу.
Вопрос, таким образом, сводится к поиску параметров, наиболее адекватно отражающих уровень канцерогенности метаболитов. Для класса ПАУ таким параметром должна быть разность энергии образования катионов и диолэпоксидов (подробнее см. в [105]).
Энергия в данной работе определяется на основе расчёта энергии по методу Хюк-келя, применимого только для 7г-систем. В этом методе полная энергия молекулы аппроксимируется полной 7г-электронной энергией (Е7г). В простейшем случае (альтернантные ПАУ без гетероатомов и заместителей) Еп может быть вычислена, как удвоенная сумма отрицательных собственных значений симметрической матрицы смежности молекулярного графа молекулы.
Многие соединения ряда галогенированных алканов также проявляют канцерогенную активность. Одним из путей биотрансформации этих соединений в организме явля ется окислительное дегалогенирование под действием цитохрома Р-450. Согласно модели [107, 108] ключевой стадией этого процесса является отрыв атома водорода от углерода с образованием радикала (скорость реакции образования радикалов характеризуется параметром Еакт, по которому определяется структура образующегося метаболита). Затем происходит рекомбинация с радикалом ОН и дегидрогалогенирование с образованием карбонильных соединений (реакционная способность метаболита характеризуется параметром Енсмо). В ходе эксперимента по прогнозу канцерогенности галогенированных алканов использовались два числовых параметра — Еакт и Енсмо» которые рассчитывались средствами программы МОРАС 6.0 с использованием полуэмпирического квантово-химического метода AMI.
Целью наших экспериментов была проверка возможностей описанного в работе метода в сравнение с результатами, полученными с применением других методов. Для проведения экспериментов программный модуль, реализующий подход, описанный в Разделе 2, был интегрирован в систему интеллектуального анализа данных QuDA [97].