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

? Определение 2 базиса инвариантов графов.

Назовем набор инвариантов {g_i} (i=1,2,...) меченых графов некоторого множества {G_i} (i=1,2,...; G_i1?G_i2 , i1?i2) базисным, если: 1) для любых графов G_i1 и G_i2 и (i1?i2) из этого множества вектора g(G_i1)=(g₁(G_i1),g₂(G_i1),…) и g(G_i2)=(g₁(G_i2),g₂(G_i2),…) различны; 2) любой инвариант f(G) графов любого конечного подмножества графов исходного множества {G_i} (i=1,2,...) может быть представлен в виде некоторой функции h от g₁, g₂,…, т.е. f(G)=h(g₁(G),g₂(G),…), причем h не зависит от G, а зависит от инварианта f и выбранного подмножества графов.

Отметим, что в определении 2, в отличие от определения 1, не требуется, чтобы: а) рассматриваемое множество графов было бы конечным; б) любой инвариант графа представлялся бы в виде линейной функции от базисных инвариантов; в) любой инвариант однозначно выражался бы через базисные инварианты.

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

Для построения первого набора инвариантов рассматриваются все графы F_k с k?1 вершинами, состоящие из объединения нескольких несвязных компонент, каждая из которых является либо цепью, либо циклом, или циклом, к некоторым вершинам которого присоединено еще по одной вершине. В случае k=1 граф F₁ состоит из одной вершины. Все такие графы для одного фиксированного k нумеруются произвольным образом и обозначаются через F_k,m (m=1,2,...). На рис. 2 приведены все такие графы при k=5. Пусть x_k,m - инвариант, равный числу вхождения в некоторый граф G подграфа F_k,m.

Второй набор инвариантов строится на основе первого следующим образом. Нумеруются все вхождения F_k,m в граф G и j-ое вхождение обозначается через F_k,m,j . Каждому F_k,m,j сопоставляется число

где суммирование проводится по всем компонентам связности F_k,m,j, n_i - число вершин в i - ой компоненте, v_р (р=1,2,…) - степени вершин F_k,m,j в G. Инвариант _k,m определяется так:

.

Для исследования наборов инвариантов {x_k,m} и {_k,m} на базисность в смысле определения 2 использованы разные методы исследования: 1) строгое математическое доказательство соответствующих утверждений для графов определенных классов; 2) выявление на основе некоторых теоретических результатов тех наборов графов, для которых могут нарушаться условия базисности; нахождение таких графов в разных классах графах с последующей непосредственной проверкой соответствующих утверждений для них; 3) проведение компьютерно-статистического эксперимента, в ходе которого случайным образом генерируются различные выборки графов и для них проверяется выдвигаемая гипотеза.

Рис. 2. Все графы F_k,m при k=5.

ТЕОРЕМА 1.10. Набор инвариантов x_k,m является базисным (в смысле определения 2) для множества графов {G_i} (i=1,2,..,), состоящего из графов типа F_k,m.

Аналогичные результаты получены и для набора {_k,m}.

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

На основании результатов проведенных комбинированных исследований наборы инвариантов {x_k,m } и {_k,m} были названы базисными (в смысле определения 2).

Метод построения моделей связи «структура-свойство» и его тестирование.

Предложен общий алгоритмизированный метод №2 построения моделей связи «структура-свойство», основанный на введенных выше инвариантах {_k,m}. Согласно этому методу, для данной выборки молекулярных графов строятся все возможные инварианты {_k,m}, а также их квадраты и попарные произведения, и затем из этого набора параметров отбирается небольшое число параметров, дающих удовлетворительную линейную модель.

Проведено тестирование предложенного метода на основе баз данных по углеводородам различных классов с различными свойствами. Рассматривались: (1-4) температура кипения, критическая температура, молярная рефракция, молярный объем алканов; (5) температура кипения циклосодержащих углеводородов; (6) полная -электронной энергия бензоидных углеводородов. Полученные модели обладают достаточно высокой точностью.

? Определение 3 базиса инвариантов графов.

Назовем семейство инвариантов {Z₁(₁), Z₂(₂),…} произвольного набора графов {G_i}, зависящих от параметров ₁, ₂,…, базисным, если для любого инварианта f любой выборки графов {G₁,…,G_N} найдется N инвариантов Z_j1(₁),…, Z_jN(_N) из этого множества, и N чисел ₁',…, _N', таких, что рассматриваемый инвариант f однозначно представляется в виде линейной комбинации Z₁(₁'),…,Z_N(_N'):

_N

f=?с_iZ_ji(_i').

ⁱ⁼¹

Далее введено семейство инвариантов {_k,m()=_k,m/n (k,m?1); _0,0()=n}, где n - число вершин графа G, =(k,m)0 - произвольный параметр, который для каждой пары (k,m) может принимать любые значения. Это семейство инвариантов является обобщением рассмотренного ранее набора инвариантов {_k,m }.

Проведено исследование семейства инвариантов {_k,m()} на базисность в смысле определения 3. Для этой цели использованы два различных метода: 1) строгое математическое доказательство выдвигаемой гипотезы для определенных классов графов; 2) проверка гипотезы в ходе компьютерно-статистического эксперимента.

ТЕОРЕМА 1.11. Инварианты {_k,m()} являются базисными в смысле определения 3 для любого множества графов {G_i}, i=1,...,N, удовлетворяющего одному из следующих условий: а) все графы данного множества имеют различное число вершин n₁, n₂,..., n_N; б) каждый граф из данного множества является графом типа F_k,m при некоторых (k,m).

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

Метод построения моделей связи «структура-свойство» и его тестирование.

Разработан общий алгоритмизированный метод №3 построения моделей связи «структура-свойство». Метод заключается в следующем: 1) задается конечный набор М значений параметра : ₁=0, ₂,…,_М с фиксированным значением шага h и заданным максимальным значением _М; 2) строятся инварианты {_k,m()} для всех фрагментах F_k,m, которые присутствуют в заданном множестве структур, при всех выбранных значениях параметра ; 3) из этого множества инвариантов отбираются наилучшие для построения линейной модели. Если полученный результат является неудовлетворительным (по каким-либо критериям), то процедура повторяется для других значений _М или h.

Проведено тестирование предложенного метода. Для этой цели было использовано несколько баз данных по физико-химическим свойствам углеводородов различных классов и значениям некоторых широко известных топологических индексов. Рассматривались следующие свойства: 1) температура кипения; 2) критическая температура; 3) молярная рефракция; 4) теплота образования; 5) теплота сгорания; 6) критическое давление; 7) молярный объем; 8) теплота испарения; 9) поверхностное натяжение; 10) плотность; 11) энтальпия образования; 12) температура плавления; 13) энергия Гиббса; 14) удельная теплоемкость; 15) показатель преломления. В качестве топологических индексов были взяты индексы Винера, Хосойя, молекулярной связности, индексы молекулярной формы Кира, полная -электронная энергия. Рассмотренные базы разбивались на обучающую и контрольную выборки так, чтобы число структур в последней составляло примерно 10% от общего числа структур базы. По обучающей выборке строилось уравнение связи «структура - свойство»; затем оно использовалось для расчета свойств соединений контрольной выборки. Было построено 27 моделей, для каждой из которых определялись коэффициент корреляции и среднеквадратичное отклонение как для обучающей выборки, так и для контрольной. В этих примерах были использованы значения h=0.1, _М =3, 4, 5, 6.

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

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

Идея поиска таких подграфов основана на следующих известных результатах спектральной теории графов: 1) собственные числа взвешенного графа с n вершинами однозначно определяются по набору его подграфов на k=1,2,...,n вершинах, состоящих из объединения изолированных вершин, ребер и циклов; 2) граф однозначно определяется по набору его собственных чисел и соответствующих линейно независимых собственных векторов; однако в общем случае граф не определяется однозначно по набору собственных чисел. В связи с этим возникает следующая задача: найти подграфы, определяющие однозначно и собственные вектора графа. Отметим, что вышеуказанная проблема для собственных векторов более сложная, чем для собственных чисел, так как: 1) собственные вектора зависят от собственных чисел; 2) в общем случае может быть несколько линейно-независимых собственных векторов, соответствующих одному и тому же собственному числу; 3) компоненты собственных векторов зависят от нумерации вершин графа.

В этом разделе Главы 1 дано решение вышеуказанной проблемы: выведены формулы, связывающие собственные вектора графа и его некоторые подграфы. Полученные результаты сформулированы в виде теоремы 1.12. На их основе выделен объединенный набор подграфов, который используется для определения как собственных чисел, так и собственных векторов графа. Эти подграфы названы базисными.

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

Проведено тестирование предложенного метода на основе баз данных по биологической активности разнообразных классов соединений, а также его сравнение с другими методами моделирования связи «структура-свойство» на используемых данных. Рассматривались: 1) галоидпроизводные метана и этана с известными значениями их наркотической активности lnAD₅₀ (AD₅₀ - концентрация вещества, вызывающая анестезию у половины подопытных животных); 2) нитробензолы и нитротолуолы с известными значениями мутагенной активности ln (на Salmonella typhimurium, - количество ревертантов на наномоль); 3) хлорзамещенные анилины с известными значениями токсичности logEC₅₀^-1, где EC₅₀ - концентрация вещества, вызывающая уменьшение интенсивности люминесценции в 2 раза у морских бактерий Photobacterium phosphoreum. Построенные модели обладают достаточно высокой точностью, что свидетельствует об эффективности предложенного метода.

Таким образом, в Главе 1 разработаны и обоснованы четыре новых метода построения моделей связи «структура-свойство» в терминах инвариантов молекулярных графов. Методы носят общий характер, применимы к произвольным свойствам и произвольным выборкам химических соединений. Два из них позволяют учесть метки соответствующих молекулярных графов, которые могут быть произвольными символами; два других используют представления структур в виде простых графов. Методы строго детерминированы и допускают компьютерную реализацию. Проведено тестирование предложенных подходов для моделирования связи «структура-свойство» для разнообразных свойств (физико-химических, биологической активности), вычисляемых молекулярных параметров и классов соединений, показавшее их широкую практическую применимость и эффективность. Кроме того, получен ряд новых теоретических результатов в области теории графов, являющихся основой для разработки соответствующих алгоритмов.

ГЛАВА 2. Система автоматической генерации инвариантов графов для моделирования связи «структура-свойство»

Постановка задачи: разработать алгоритм конструирования инвариантов графов: 1) моделирующий действия человека, строящего инварианты для использования их в корреляциях «структура-свойство»; 2) в котором выбор элементарных шагов в процессе конструирования инвариантов происходит случайным образом; 3) позволяющий генерировать как известные, так и новые инварианты графов. Цель разработки такой системы - получать произвольное количество разнообразных инвариантов графов для построения на их основе моделей связи «структура-свойство».

Целесообразность создания вышеуказанной системы обусловлена тем, что не всегда удается построить достаточно хорошие корреляции «структура-свойство», используя для этих целей даже достаточно большие наборы вполне определенных параметров, построенных «вручную». Это связано с тем, что: а) инвариантов графов в принципе существует бесконечно много, и использование какого-либо одного и того же конечного, фиксированного набора инвариантов для всех случаев не всегда приводит к требуемому результату; б) как правило, в процессе построения конкретной модели обнаруживаются корреляции между различными инвариантами. Последнее можно объяснить, в частности, тем, что при конструировании инвариантов «вручную» часто происходит применение одних и тех же приемов построения и действий «по аналогии».

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

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

Далее в качестве примера на рис.3 приведена блок-схема 1-ого этапа. В качестве входных данных на этом этапе используется матрица смежности (или весов) A₀=(a_ij) графа. Результатом работы алгоритма на этом этапе является База Матриц (БМ) введенного графа, полученных из А₀ по разным правилам. Матрица А₀ также заносится в БМ. На 1-ом этапе задаются Списки 1-5, содержащие варианты преобразования А₀. Например, в Списке 1 приведены варианты начальных весов вершин графа, в Списке 2 - варианты начальных весов пар вершин; Списки 3 и 4 содержат варианты преобразований весов вершин или весов пар вершин. Так как некоторые варианты в Списках 1-5 предполагают использование каких-либо функций или определенных подграфов, то также вводятся дополнительные Списки 6-9 (перечни функций f одной переменной, симметричных функций F многих переменных, симметричных функций g двух векторных аргументов; перечень специальных подграфов).

Исследование возможностей системы генерации инвариантов графов. Показано, что основные, известные из литературы инварианты молекулярных графов (называемые в теоретической химии топологическими индексами) могут быть получены в рамках разработанной схемы. Рассмотрено 42 топологических индекса различного типа, причем некоторые из них в действительности представляют собой целые семейства инвариантов. Примерами таких являются индексы связности порядка h1, для вычисления которых рассматриваются все цепи фиксированной длины h1 в графе, или информационные индексы порядка k1, где k - номер координационной сферы атома.

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

Используя предложенную схему, которая является, по сути, алгоритмом генерации алгоритмов генерации инвариантов, можно строить автоматически сколь угодно много инвариантов разного типа при помощи компьютера.

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

Проведено тестирование предлагаемого подхода для построения корреляций «структура-свойство» для физико-химических свойств и биологической активности органических соединений различных классов. Рассматривались: 1)-5) энтальпия образования, температура кипения, критическая температура, критическое давление, 3D-индекс Винера ³W алканов С₂-С₈; 6)-7) ингибирование микросомального пара-гидроксилирования анилина цитохромом Р₄₅₀ (степень ингибирования характеризуется величиной pIC₅₀,=-lgIC₅₀ , где IC₅₀ - концентрация вещества, приводящая к 50% ингибированию гидроксилирования анилина), а также температура кипения t_кип. алифатических спиртов; 8), 9) параметр гидрофобности logP (P - коэффициент распределения соединения между водой и н-октанолом), а также токсичность, характеризуемая величиной logEC₅₀^-1 (EC₅₀ - концентрация вещества, вызывающая 50% уменьшение биолюминисценции морских бактерий Photobacterium phosphoreum в течение 30 мин.) хлорзамещенных фенолов. Полученные результаты свидетельствуют об эффективности предложенного подхода.

Рис.3. Блок-схема 1-ого этапа алгоритма генерации инвариантов графа.

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

ГЛАВА 3. Методы определения областей применимости моделей связи «структура-свойство»

Постановка задачи: определить область применимости (ОП) построенной модели связи «структура-свойство», т. е. то множество химических соединений, свойства которых могут быть рассчитаны по соответствующему уравнению с заданной погрешностью . Эта задача возникает на этапе прогнозирования свойств соединений при помощи построенной модели. Очевидно, что использование любой математической модели без учета ее ОП может дать неверный результат.

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

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

В данной главе описаны два общих, конструктивных метода априорного определения ТОП уравнений связи «структура-свойство» при заданной погрешности расчета свойств . Приведены обоснования предложенных методов, а также результаты их тестирования.

Вероятностный метод определения ОП. Предложен вероятностный подход к определению области применимости линейной модели связи «структура-свойство» следующего вида:

y=a₁x₁+...+a_mx_m ,

в которой параметры a₁,...,a_m определяются по исходной выборке k соединений методом наименьших квадратов, а x₁,…,x_m - любые молекулярные параметры. Пусть y_расч - величина свойства, рассчитанная по вышеприведенному уравнению, у - экспериментальное значение свойства, М - множество, структуры которого требуется разделить на два класса: принадлежащие и не принадлежащие ТОП соответствующего уравнения. Согласно определению, РОП вышеприведенного уравнения состоит из тех соединений, для которых y-y_расч. Так как невозможно учесть все факторы, влияющие на заданное свойство, его экспериментальное значение у можно рассматривать как случайную величину. Следовательно, выполнение условия y-y_расч представляет собой случайное событие, и можно рассмотреть его вероятность P(y-y_расч). Будем считать, что ТОП состоит из тех соединений, для которых P(y-y_расч)_кр, где _кр - некоторое пороговое (критическое) значение этой вероятности. Основная идея предложенного метода заключается в определении порога _кр по заданному значению , и дальнейшей оценке вероятности P(y-y_расч) для тестируемого соединения. Подход базируется на ряде гипотез, в частности, на предположении о том, что некоторые случайные величины, связанные с изучаемым свойством, распределены по нормальному закону. Критерий принадлежности некоторого соединения ТОП построенной модели заключается в выполнении для тестируемого соединения некоторого числового неравенства. Для его проверки необходимо знание значений параметров x₁,…,x_m для тестируемого соединения и для соединений исходной выборки, значений свойств соединений исходной выборки, чисел _кр и , а также значения t(_кр, k-m)- квантили уровня _кр распределения Стьюдента с k-m степенями свободы.

Проведено тестирование предложенного метода. При этом проверялись степень совпадения РОП и ТОП, степень сокращения доли ошибочных предсказаний и доля «пропущенных» соединений при использовании ТОП. В качестве множества М рассматривалось множество всех алканов С₂-С₈ (39 соединений) с известными значениями температуры кипения. Обучающая выборка состояла из k=12 соединений этого класса. По этим данным было построено линейное уравнение связи «структура-свойство», содержащее такие параметры как ln(+1), где - индекс Рандича, и n - число атомов углерода в молекуле. Рассматривался ряд значений (0<5(⁰С)), и для этих значений определялось качество предложенного метода. Проведенные исследования показали, что описанный выше метод позволяет в 94-97% случаев отбросить соединения, не принадлежащие РОП, и в 80-85% случаев верно определить, принадлежит ли РОП данное соединение. Если проводить прогнозирование свойств всех соединений исходного множества, не выделяя ТОП, то доля верных предсказаний составляет 90%; если прогнозирование проводить только внутри ТОП, то доля верных предсказаний - 97%; доля «пропущенных» соединений -13%.

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

Метод определения ОП на основе базисных инвариантов. Предложен метод определения ТОП модели связи «структура-свойство» специального вида на основе базисных инвариантов (в смысле определения 1), рассмотренных в Главе 1, и ряда соответствующих теоретических результатов.

Рассматриваемые модели связи «структура-свойство» строятся следующим образом. Пусть задано множество соединений, представленных графами {G_i} (i=1,...,N), и выборка соединений из них {G_i} (i=1,...,k) с известными значениям некоторого свойства {y_i} (i=1,...,k). Пусть {f_j} (j=1,...,N) - базис инвариантов графов исходного множества, такой, что N-k+1 его элементов с номерами k,...,N постоянны на графах {G_i} (i=1,...,k), т.е. f_p(G_i)=c_p , i=1,...,k. Предположим, что по исходным данным сначала построено точное уравнение связи «структура-свойство» следующего вида:

_k-1

y=a_pf_p(G)+ a₀.

^p=1

Пусть из него получено приближенное уравнение (с заданной погрешностью ) путем замены некоторых инвариантов f_p (например, с номерами p=m+1,...,k-1) на константы b_p, равные их средним на выборке значениям:

_{m k-1}

y=a_pf_p(G)+A₀ (A₀=a₀+a_pb_p).

^{p=1 p=m+1}

В Главе 1 были даны некоторые достаточные условия на рассматриваемое свойство и молекулярный граф G (т.е. химическую структуру), при которых значение свойства этой структуры определяется по вышеуказанному уравнению с точностью (см. Теорему 1.9 и следствие из нее). Первое из них - это независимость рассматриваемого свойства для соединений исходного множества от некоторых базисных инвариантов f_p с номерами p=k,...,N (что можно только предполагать и нельзя получить из исходных данных). Второе условие - это выполнение для графа G равенств вида f_p(G)=c_p для остальных номеров p=k,...,N. Третье условие - это выполнение следующего неравенства:

_k-1

a_p(f_p(G)-b_p).

^p=m+1

Из этих условий следует, что число L₁ ограничений типа равенств на структуры графов из ТОП связаны с числом L₂ гипотез о независимости свойства от некоторых базисных параметров так: L₁+L₂=N-k+1. Таким образом, чем меньше факторов влияет на величину данного свойства, тем меньше структурных ограничений надо вводить на графы из ТОП.

На основании этих теоретических результатов предложен следующий метод определения ТОП вышеприведенного уравнения: 1) выдвигается ряд гипотез о независимости рассматриваемого свойства от некоторых структурных параметров, задаваемых инвариантами f_p; 2) для анализируемого графа G проверяется ряд соответствующих ограничений типа равенств и одно ограничение типа неравенства, приведенные выше; если все эти условия выполняются, то граф G считается принадлежащим ТОП.

Проведено тестирование предложенного метода. Проверялись степень совпадения РОП и ТОП, степень сокращения доли ошибочных предсказаний и доля «пропущенных» соединений при использовании ТОП. Рассмотрено множество всех алканов С₂-С₇ (N=21), с известными значениями температуры кипения у. В качестве обучающей выборки использовано множество всех алканов С₂-С₅ (k=7), а =5(⁰С). Выдвигаемые гипотезы основаны на представлении о том, что температура кипения зависит, в основном, от размера и степени разветвленности молекул, а числа вхождения в граф некоторых специальных подграфов могут служить количественной мерой этих структурных особенностей. Проведенные исследования показали, что при классификации исходных соединений на «принадлежащие/не принадлежащие» РОП при помощи ТОП была сделана лишь одна ошибка, т.е. правильная классификация соединений была проведена в 95% случаев. Если проводить прогноз свойств всех соединений исходного множества, не выделяя ТОП, то доля верных прогнозов составляет 43%; если прогнозирование проводить внутри ТОП, то доля верных прогнозов - 100%; доля «пропущенных» соединений -5%.

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

ГЛАВА 4. Обратные задачи в исследованиях связи «структура-свойство»: теоретико - графовый подход

Постановка задачи. Обратная задача (ОЗ) в исследованиях связи «структура-свойство» - это задача исчерпывающей генерации химических структур определенного класса, имеющих заданное значение y₀ рассматриваемого свойства (или заданный интервал (y₁, y₂) значений свойства), на основе предварительно построенной базовой модели связи «структура-свойство» следующего вида:

y=f(x₁,...,x_N),

где y - значение рассматриваемого свойства, x₁,...,x_N - какие-либо молекулярные параметры, f - некоторая функция. Если в качестве параметров x₁,...,x_N использованы инварианты соответствующих молекулярных графов, то ОЗ сводится к исчерпывающей генерации молекулярных графов по заданному значению их инварианта, задаваемому выражением вида f(x₁,...,x_N).

Метод ОЗ важен для целенаправленного поиска соединений с заданными свойствами. По сравнению с традиционным подходом к поиску таких соединений, когда при помощи базовой модели «структура-свойство» последовательно тестируется определенный набор соединений и затем из него отбираются подходящие соединения, метод ОЗ имеет явное преимущество: он позволяет дать исчерпывающее (с математической точки зрения) решение поставленной задачи. Такая особенность этого метода позволяет выявить структуры новых соединений (возможно, еще не синтезированных), которые, согласно прогнозу, должны обладать требуемым свойством.

В Главе 4 описаны алгоритмы решения ОЗ для некоторых наиболее популярных инвариантов графов, используемых в теоретической химии при построении корреляций «структура-свойство» и ставших в определенном смысле «классическими». Проведено тестирование предложенных алгоритмов.

Типы рассмотренных базовых моделей связи «структура-свойство».

Рассматриваются модели связи «структура-свойство» следующих видов:

1) а) Уравнение содержит только один молекулярный параметр ч, называемый

индексом Рандича:

ч=У(v_i v_j)^-1/2

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

2) Уравнение содержит индекс Винера W и рассматривается для ациклических молекулярных графов:

W=?_i<jd_ij

(d_ij - расстояние между вершинами i и j, суммирование проводится по всем парам вершин (i,j), i<j.).

3) Уравнение содержит «каппа»-индексы Кира ⁱк (i=0, 1, 2, 3), предложенные для количественной характеристики различных особенностей «формы» молекулы, представленной простым графом. Эти молекулярные параметры определяются в терминах числа вершин графа n и числа путей ⁱP длины i (i=1, 2, 3) в графе по следующим формулам:

¹к=n(n-1)²/¹P²,²к=(n-1)(n-2)²/²P²,

³к=(n-3)(n-2)²/³P² (для четного n>3);³к=(n-1)(n-3)²/³P² (для нечетного n>3).

Индекс ⁰к определяется по формуле: ⁰к=-nУ(n_i/n)log₂(n_i/n), где n_i - число топологически эквивалентных вершин в i - ом классе эквивалентности. Разбиение вершин на классы происходит по каким-либо их топологическим характеристикам, причем самое «мелкое» разбиение соответствует орбитам группы симметрии графа.

4) Уравнение содержит индексы ⁱк (i=0,1,2,3), а также их обобщения ⁱк_б (i=1,2,3), разработанные для учета гетероатомов и кратных связей в молекуле. Они вычисляются аналогично ⁱк (i=1,2,3), но в вышеприведенных формулах вместо n используется величина n+б, а вместо ⁱP - величина ⁱP+б при некотором параметре б, вычисляемом по взвешенному графу. Для вычисления б атомы молекулы классифицируют по химическим символам атомов и распределениям типов связей; для атома каждого типа определенным способом вычисляют параметр б_j, зависящий от ковалентного радиуса атома, затем б вычисляют по формуле б=Уб_j.

3) Уравнение содержит информационные топологические индексы разных типов, но одного порядка k.

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

IC_k=-У n_i/n_ilog₂n_i/n_i (Information Content), SIC_k=IC_k/log₂n (Structural Information Content),

CIC_k=log₂n (Complement Information Content), BIC_k=IC_k/log₂q (Boundary Information Content),

TIC_k=n·IC_k (Total Information Content), (q - общее число связей в молекуле).

Аналогичные инварианты можно построить и для произвольно меченого графа.

4) Уравнение содержит индекс Хосойя Z, а также такие параметры как общее число вершин графа n и числа n_i вершин графа степени i=1, 2, 3, 4. Инвариант Z определяется по формуле:

,

где - число подграфов, состоящих из k несмежных ребер граф, , n - число вершин графа. Отметим, что для ациклических графов индекс Хосойя равен сумме модулей коэффициентов характеристического полинома графа. Рассматриваются простые графы, степени вершин которых не превосходят четырех. Кроме того, предполагается, что индекс Z может быть выражен однозначно из вышеуказанного уравнения.

Алгоритмы решения обратных задач и их тестирование. Приведены алгоритмы решения ОЗ для вышеуказанных корреляционных уравнений. Проведено их тестирование для конструирования химических соединений с заданными интервалами значений определенных свойств. Для этой цели предварительно были построены разнообразные модели связи «структура-свойство» вышеописанного вида.

Рассматривались: (1) температура кипения алканов; (2) температура кипения циклосодержащих углеводородов; (3) токсичность простых эфиров; (4) теплота парообразования алканов; (5) растворимость спиртов в воде; (6) параметр гидрофобности logP, где P - коэффициент распределения соединения в системе октанол-вода для кислородсодержащих соединений (кетонов, ненасыщенных и насыщенных спиртов, карбоновых кислот); (7) температура кипения аминов; (8) температура кипения сульфидов. Во всех рассмотренных случаях имеется хорошее соответствие между экспериментальными данными и результатами компьютерной генерации соединений с заданными свойствами.

Рассмотрим следующий пример решения ОЗ. По базе данных, содержащих предельные спирты (N=50) с известными значениями физико-химического свойства: -logX ( - растворимость спиртов в воде (в мольных долях)), построено уравнение вида:

-logX=-0.8+1.186lnZ (R=0.976, s=0.21).

Поставим задачу: найти все соединения этого класса, для которых 2.6?-logX?3.0. Построено 20 структур, изображенных на рис. 4. Для соединений №№ 1-11 значения свойства известны. При этом для 9 структур экспериментальные значения свойства действительно лежат в заданном интервале; для 2 структур - незначительно выходят за пределы интервала (для №3 - 2.542; для №8 - 2.588). Для соединений №№ 12-20 экспериментальные значения рассматриваемого свойства неизвестны.

Таким образом, в Главе 4 рассматривается ряд алгоритмов решения ОЗ в исследованиях связи «структура-свойство» на основе предварительно построенных базовых моделей, содержащих различные инварианты графов (топологические индексы). Рассмотренные топологические индексы находят широкое применение в корреляциях «структура-свойство» и допускают определенную структурную интерпретацию (например, как количественная мера ветвления, компактности, симметрии, «формы», неоднородности молекулы и т. д.). Базовые корреляционные уравнения могут содержать как один, так и несколько различных инвариантов. Уравнения, содержащие какие-либо другие инварианты, не рассматриваемые в данной главе, в ряде случаев можно свести к уравнениям, содержащим уже рассмотренные инварианты, используя корреляционные соотношения между различными инвариантами. Применение алгоритмов и их эффективность продемонстрированы на конкретных примерах.

ГЛАВА 5. Построение моделей связи «структура-свойство» и прогнозирование свойств химических соединений на основе концепции молекулярного подобия

Постановка задачи. В Главе 5 рассматривается один из широко распространенных подходов к построению моделей связи «структура-свойство», основанный на постулате «близкие структуры имеют близкие свойства». Для реализации этого метода необходимо: 1) иметь базу данных, содержащую структуры соединений {S} и значения их свойств; 2) выбрать способ математического описания структуры молекул, при котором структуре S соответствует объект М; 3) на множестве выбранных математических объектов {M} задать количественную меру подобия этих объектов: d(M₁,M₂)?0.

Для прогнозирования свойства y₀ соединения S₀ в рамках этого подхода используются различные методы, суть которых заключается в следующем: 1) для S₀ следует найти cоединение S, «ближайшее» к нему в базе данных (или несколько «ближайших») и положить y₀=y (или y₀ равно среднему арифметическому свойств «ближайших» соединений). Метод такого типа целесообразно использовать, в частности, тогда, когда исходная база данных очень разнородна по своему составу, и не удается построить удовлетворительную модель вида y=f(S). Однако разбиение базы на части структурно-близких соединений приводит к малоинформативным выборкам небольшого размера.

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

Рис.4.

Общая аналитическая формула для произвольной меры подобия молекулярных графов. Выведена общая аналитическая формула для произвольной симметричной меры подобия d(G_k,G_l), заданной на произвольном множестве графов {G_i}, i=1,...,N. Доказана теорема, соласно которой существует единственная симметричная квадратная матрица M=(m_ij) (i,j=1,...,N-1) такая, что мера d(G_k,G₁) представляется в следующем виде:

d(G_k,G_l)=M(f_k-f_l)·(f_k-f_l)

где f_k=(f₁(G_k),...,f_N-1(G_k)), f_l=(f₁(G_l),...,f_N-1 (G_l)) - вектора-столбцы, компоненты которых - это значения некоторых базисных инвариантов исходного множества графов (в смысле определения 1, рассмотренного в Главе 1) на графах G_k и G_l, соответственно, M(f_k-f_l) - произведение M и f_k-f_l, символ «·» обозначает скалярное произведение соответствующих векторов.

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

Метод построения моделей связи «структура - свойство», основанный на оптимальном подборе меры подобия.Предложен метод построения моделей связи «структура-свойство» и прогнозирования свойств химических соединений, основанный на приведенных выше теоретических результатах. Для разработки этого метода используется аппроксимация вышеуказанной точной формулы для меры подобия. Предполагается, что структура соединений исходной выборки описана при помощи некоторых векторов X длины k<N-1, мера подобия d(G_i,G_j) задается формулой, аналогичной вышеуказанной формуле: d(G_i,G_j)=M(X⁽ⁱ⁾-X^(j))·(X⁽ⁱ⁾-X^(j)), где матрица М с неопределенными элементами имеет порядок k. Элементы матрицы М подбираются так, чтобы |y_i-y_j|=d(G_i,G_j), i,j=1,...,N; i>j. В предлагаемом подходе мера подобия подбирается некоторым оптимальным образом по исходным данным. Заключительный этап - прогнозирование свойства y₀ нового соединения G₀ - тоже изменен. Вместо метода m «ближайших соседей» (где всегда остается вопрос о выборе числа m) предлагается другой подход, в котором для вычисления y₀ используются все исходные данные. Однако для прогнозирования свойств может быть использован и метод «ближайших соседей».

Проведено тестирование разработанного метода и его сравнение с другими аналогичными методами. Рассмотрена база данных, состоящая из 76 соединений различных химических классов (спирты, фенолы, кетоны, карбоновые кислоты, простые и сложные эфиры, амины, амиды, нитрилы, галогенпроизводные, гетероциклические соединения и.т.д.) с известными значениями параметра log P, где P - коэффициент распределения соединения между водой и н-октанолом. Качество построенной модели оценивалось по коэффициенту корреляции R и среднеквадратичному отклонению s, найденным для корреляции между расчетными и экспериментальными значениями свойства. Приведены результаты сравнения построенной модели и двух других моделей, полученных другими авторами для тех же данных, где для оценки степени подобия использовались две другие меры подобия. Из этих результатов следует, что предлагаемый метод дает наилучшую модель из этих трех.

Оптимальный подбор меры подобия при прогнозировании свойств по методу «ближайшего соседа». Рассмотрена задача построения оптимальной меры подобия молекулярных графов при прогнозировании свойств соединений по методу одного «ближайшего соседа». Предполагается, что задана некоторая выборка молекулярных графов {G_i} с известными значениями некоторого свойства y_i, причем все эти значения - различны.

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

Проведено тестирование предложенного метода и его сравнение с шестью аналогичными методами, использующими другие меры подобия, зависящие от различных особенностей молекулярного строения и не зависящие от исследуемого свойства. Рассмотрена база данных, содержащая структурные формулы нитрозаминов с известными значениями мутагенности y=lnм (на Salmonella typhimurium, м - число ревертантов на наномоль). Установлено, что предложенный метод дает более точный результат, чем остальные методы.