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

§ 2.2. Описание алгоритма конструирования инвариантов графа.113.

§ 2.3. Основные топологические индексы как результат реализации алгоритма генерации инвариантов графа.124.

§ 2.4. Метод построения корреляций «структура-свойство» на основе алгоритма генерации инвариантов графов и результаты его тестирования.128.

§ 2.5. Основные результаты и выводы.137.

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

§ 3.1.

Введение

140.

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

§ 3.3. Определение области применимости модели связи «структура — свойство во» на основе базисных инвариантов. 144.

§ 3.4. Основные результаты и выводы. 149.

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

§ 4.1.

Введение

154.

§ 4.2. Обратная задача для индекса Рандича. 155.

§ 4.3. Обратная задача для «каппа"-индексов Кира. 168.

§ 4.4. Обратная задача для информационных топологических индексов.175.

§ 4.5. Обратная задача для индекса Хосойя.179.

§ 4.6. Основные результаты и выводы.192.

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

§ 5.1.

Введение

196.

§ 5.2. Общая аналитическая формула для произвольной меры подобия молекулярных графов и следствия из нее.196.

§ 5.3. Метод прогнозирования свойств соединений, основанный на оптимальном подборе меры молекулярного подобия.201.

§ 5.4. Построение оптимальной меры подобия молекулярных графов при прогнозировании свойств соединений по методу «ближайшего соседа».207.

§ 5.5. Формализация постулата «близкие структуры имеют близкие свойства» и его анализ.210.

§ 5.6. Основные результаты и выводы.212.

ГЛАВА 6. Алгоритмы на графах, используемые для их кодирования, идентификации и исследования структурных особенностей.217.

§ 6.1.

Введение

217.

§ 6.2. Алгоритм поиска канонической нумерации вершин графа и его группы автоморфизмов, основанный на спектральной теории графов.217.

§ 6.3. Алгоритм установления изоморфизма графов и поиска его группы симметрии.224.

§ 6.4. Алгоритм нахождения в графе заданных подграфов.226.

§ 6.5. Основные результаты и выводы.234.

ВЫВОДЫ. 236.

СПИСОК ЦИТИРОВАННОЙ ЛИТЕРАТУРЫ. 241.

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ.253.

ПРИЛОЖЕНИЕ.261.

1. Общая характеристика области исследованийи ее современного состояния.

• Постановка основной задачи и ее актуальность. Проблема математического моделирования связи между структурой и различными свойствами органических соединений является одной из важнейших задач современной теоретической химии [1−10,11]. Эту область исследований обычно называют QSAR/QSPR (Quantitative Structure-Activity/Property Relationships Studies), или QSPR, если под «свойством» химических соединений подразумевают любое их свойство — физико-химическое, биологическую активность или какой-либо расчетный молекулярный параметр.

Основная цель построения моделей связи «структура-свойство» -прогнозирование свойств соединений, для которых отсутствуют экспериментальные данные. Найденные закономерности имеют большое значение для целенаправленного синтеза соединений с заданными свойствами, так как позволяют, в конечном итоге, предсказывать структуру искомых соединений и прогнозировать их свойства. Следует отметить, что к настоящему времени синтезировано огромное количество химических соединений (согласно работе [12], около 20 млн.), которые интенсивно вовлекаются в сферу практического использования. Однако экспериментальное определение различных свойств этих веществ (физико-химических, разных видов биологической активности) часто связано со значительными трудностями, возникающими, например, при получении достаточного количества вещества, его очисткой, возможной нестойкостью, токсичностью и т. д., да и не всегда возможно. Кроме того, такие исследования требуют значительных финансовых и временных затрат. В работе [13] приводятся следующие данные: для отбора одного вещества с заданным свойством нужно испытать в среднем 3−10 тыс. соединений — таков КПД обращении созданного вещества в вещество, используемое на практикев 1991;1992 г. г. из каждых 50−60 тыс. вновь синтезированных веществ внедрялось в практику лишь одно. В связи с этим разработка любых теоретических методов расчета свойств веществ по их структуре, минуя эксперимент, является актуальной задачей. Отметим также, что выявленные закономерности могут быть полезны и при разработке новых теорий о связи свойств веществ с их строением, а также при изучении механизмов действия биологически активных веществ.

• Статистический подход к построению моделей в QSAR/QAPR-исследованиях. Одним из наиболее распространенных подходов к поиску количественных соотношений типа «структура-свойство» является так называемый статистический подход, суть которого заключается в следующем. Имеется выборка соединений с известными численными значениями некоторого свойства (физико-химического или биологической активности). Структура рассматриваемых соединений описывается при помощи набора молекулярных параметров xi,., x", в качестве которых могут быть использованы топологические, электронные, геометрические характеристики молекул или значения их каких-либо физико-химических свойств. Как правило, математическая модель связи «структура-свойство» в рамках этого подхода имеет вид уравнения, связывающего исследуемое свойство у и параметры х],., хп при помощи некоторой функции/: у=/(хи., хг). (1).

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

Важное место в исследованиях связи «структура-свойство» занимают способы количественного описания структуры молекул, т. е. выбор параметров Х],., ХП. От этого выбора значительно зависит успех в построении и применении модели. Эти параметры могут быть как экспериментальными, так и расчетными. Для получения расчетных параметров в качестве основы используется классическая структурная молекулы, которую можно рассматривать как меченый граф. По ней тем или иным способом могут быть построены другие меченые (или взвешенные) графы, называемые молекулярными. Вершины таких графов обычно соответствуют атомам (или фрагментам), а ребра — химическим связям молекулы. Метки вершин кодируют атомы различной химической природы, а метки ребер — связи разного типа. Каждой молекулярной структуре могут быть сопоставлены различные инварианты л-?,., х" соответствующих молекулярных графов. Использование инвариантов графов в этих задачах имеет ряд преимуществ, т.к. они вычисляются непосредственно из структурной формулы и могут быть найдены даже для гипотетических молекул. Выбирая специальным образом веса вершин и ребер молекулярного графа, можно в той или иной степени учесть особенности топологического, электронного и пространственного строения молекулы. Эти веса могут быть взяты как из справочников (например, заряды ядер атомов или ковалентные радиусы атомов), так и рассчитаны при помощи специальных стандартных программ, позволяющих определить электронные и геометрические характеристики молекул (например, могут быть определены межатомные расстояния в трехмерной модели молекулы или квантово-химическими методами рассчитаны заряды на атомах). Инварианты графов, для построения которых использовалась лишь информация о топологии молекулы и, возможно, справочные данные о количественных характеристиках атомов и связях разного типа, в теоретической химии обычно называют топологическими индексами. Инварианты графов, связанных с пространственными моделями молекул, обычно называют геометрическими дескрипторами. Если же для вычисления весов графа использовались квантово-химические методы, то соответствующие инварианты называют квантово-химическими параметрами. Отметим, что при построении молекулярного графа возможна и комбинация вышеуказанных подходов.

Очевидно, что результаты моделирования связи «структура-свойство», основанные на моделях типа уравнения (1), существенно зависят от выбранных молекулярных параметров, а также вида аппроксимирующей функции. Рассмотрим основные типы параметров, используемых в С^РЛ-моделях, а также их достоинства и недостатки [1,4,5,10,11,14,15]. а) Физико-химические параметры. В обзоре [15] приведен обширный список таких параметров. В их число входит логарифм коэффициента распределения, параметр липофильности, параметры тонкослойной хроматографии, парахор, мольный объем, растворимость в воде, молекулярный вес, поверхностное натяжение, молекулярная рефракция, физико-химические константы заместителей, характеризующие их электронное и пространственное строение, и т. д. Отметим, что такие параметры используются, как правило, для моделирования только биологической активности веществ. Наиболее распространенным из них является 1о§ Р — логарифм коэффициента распределения вещества в системе октанол/вода. В качестве недостатка физико-химических параметров следует отметить их экспериментальный характер, что не позволяет использовать модели, содержащие такие параметры, для расчета свойств соединений, для которых не известны соответствующие данные. б) Квантово-химические параметры. В обзоре [16] (содержащем 249 ссылок), посвященном применению квантово-химических параметров в (^АН-исследованиях, приведено 55 таких параметров. В их числе такие, как индекс свободной валентности, энергия наивысшей занятой орбитали (НЗМО) и энергия низшей свободной молекулярной орбитали (НСМО), дипольный момент, потенциал ионизации, сродство к электрону, энергия резонанса и др. Применению квантово-химических методов при прогнозировании токсичности веществ посвящен также обзор [8] (содержит 236 ссылок). Достоинством таких параметров является возможность их физико-химической интерпретации, а также расчетный характер. Однако, как указано в [15], не ясно, каким из квантово-химических параметров следует отдавать предпочтение при построении моделей. В обзоре [11] отмечено, что получаемая в результате квантово-химических расчетов информация не всегда достаточно надежна и точна. В работе [16] указана также проблема вычисления квантово-химических параметров для конформационно-гибких молекул. В работе [17] предложен подход для прогнозирования биологической активности конформационно-гибких соединений, основанный на методе интервального анализа и использующий квантово-химические параметры. в) Геометрические параметры. Эти параметры рассчитываются из трехмерной модели молекулы, полученной путем минимизации энергии структуры (например, методами молекулярной механики). Геометрические параметры характеризуют размер и форму молекулы. Наиболее распространенные из них — ван-дер-ваальсов объем молекулы и собственные числа тензора инерции. Для построения тензора инерции, представляющего собой матрицу размера 3×3, используются атомные массы и пространственные координаты ядер атомов [1]. В работе [18] рассматривается матрица, диагональные элементы которой равны атомным массам, а внедиагональные межатомным расстояниям. В качестве геометрических параметров предложено использовать собственные числа этой матрицы и ряд простейших функций от них.

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

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

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

Топологические параметры можно условно разделить на две группы. К первой группой относятся инварианты, равные числам вхождения в структуру определенных структурных фрагментов. Такие параметры являются чрезвычайно распространенными при моделировании связи «структура-свойство». Применению фрагментов в С^АК/С^РИ посвящен обзор [6]. Наиболее распространенными из них являются атом-центрированные фрагменты, представляющие из себя окрестность к-ого порядка некоторого центрального атома. При этом учитывают химический символ атома и распределение типов связей. Однако каждому атому могут быть сопоставлены, наряду с химическим символом и его некоторые физико-химические параметры, а также метки, характеризующие вхождение атома в какой-либо специальный фрагмент (например, в цикл). Такая классификация атомов рассмотрена, например, в работе [19]. Другой распространенный тип фрагментов — это цепочки определенной длины, соединяющие пары атомов. В серии работ [7, 12, 13, 20] такие фрагменты использованы для учета невалентных взаимодействий атомов при моделировании связи «структура-свойство». При построении таких цепочек можно учитывать типы концевых атомов (при разных способах классификации атомов), а также длину соответствующей цепочки, как, например, в работе [21], где такие фрагменты названы «атомными парами». В качестве достоинства таких параметров укажем их вычислительный характер, возможность структурной интерпретации, а также очень широкие возможности выбора фрагментов.

Вторая группа топологических параметров — это так называемые топологические индексы (ТИ) [ 4,5, 10,14, 22−32]. Обычно ТИ вычисляют по структурной формуле молекулы, не учитывая при этом типы атомов и связей. Можно рассматривать ТИ как инварианты простых молекулярных графов, соответствующих структурной формуле. В качестве примеров ТИ, наиболее популярных в С^АЯ/С^РЛ — исследованиях, укажем индекс Рандича: у, — и Vу — степени вершин / и суммирование проводится по всем ребрам (Ц) молекулярного графа) — индекс Винера IV: йц — расстояние между вершинами / и суммирование проводится по всем парам вершин (7,/), К/.) — индекс Хосойя 2: ш к=0 где рк — число подграфов, состоящих из к несмежных ребер граф, р0 = 1, пчисло вершин графа.

Однако имеются и обобщения ТИ, при построении которых учитывают типы атомов и связей. Для этого вершинам и ребрам простых молекулярных графов приписывают некоторые числовые веса, характеризующие атомы и связи (обычно взятые из справочников), превращая тем самым простые графы во взвешенные. Следует отметить, что ТИ существует бесконечно много (например, любая функция от уже построенных ТИ — также ТИ). В обзоре [10], наряду с перечнем известных ТИ, их классификацией и указанием областей применения, указан также ряд общих способов построения новых ТИ. В качестве достоинств этих параметров отметим простоту и быстроту их вычисления (в отличие от квантово-химических параметров) и неэмпирический характер (в отличие от физико-химических параметров). Кроме того, выбирая специальным образом веса вершин и ребер графа, можно в определенной степени учесть особенности электронного и пространственного строения молекулы [10, 22−32]. Обычно эти веса берут из справочников (например, ковалентный радиус атома, заряд ядра атома и т. д.), так что для их определения не требуется проведения квантово-химических расчетов или определения геометрии молекулы.

Важным этапом при моделировании связи «структура-свойство» является выбор аппроксимирующей функции / Обычно используют линейную или квадратичную функцию с подбором параметров методом наименьших квадратов. В обзоре [15] указано, что литературные данные по корреляциям «структура-свойство» показывают, что порядок таких функций, как правило, не выше второго. Однако бывают и исключения из этого правила. Например, в работе [33] рассматривается линейная функция от некоторых степеней ряда ТИ, причем подбираются как степени (которые могут быть как положительными, так и отрицательными дробными числами), так и коэффициенты в линейной функции.

В качестве метода построения моделей связи «структура-свойство» можно указать также и метод искусственных нейросетей. Применение этого метода в химии обсуждается в обзоре [34]. Обзор результатов по применению нейросетевого подхода в корреляциях «структура-свойство» приведен также в [35]. В работе [36] описан программный комплекс реализующий вышеуказанный метод для исследования зависимостей «структура-свойство». В этом методе подбирается некоторая нелинейная функция/ для задания которой требуется относительно много подгоночных параметров. Следует отметить, что метод стандартного регрессионного анализа является более распространенным, чем нейросетевой метод.

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

Предпринимались попытки построить модели на основе некоторых физико-химических соображений и разумных рассуждений, которые позволили бы выбрать молекулярные параметры и вид функции / Одним из таких подходов является метод Ханша, применимый к гомологическим рядам соединений, детально описанный и проанализированный в монографии [1] и обзорах [3,11]. Полученное в результате различных гипотез уравнение Ханша имеет следующий вид: oglZC =ао+а]7Г+а2л?+а3а+а4Ек, (С — исходная концентрация вещества, л — параметр гидрофобности, аэлектронная константа заместителя, Е3 — стерический параметр Тафта, а0-а4 некоторые константы). В работе [3] отмечаются недостатки этого метода: он подходит только для узких серий соединенийиспользует экспериментальные характеристики, что исключает его применение для соединений с отсутствующими даннымиэкспериментальные данные на практике часто согласуются с другими формами уравнения, так что говорить о строгой теоретической обоснованности метода не имеет смысла.

В качестве другого известного подхода построения моделей связи «структура-свойство» укажем TLSER (Theoretical Linear Solvation Energy Relationship) — метод, описанный в [16,37]. Этот метод в основном применяется для анализа свойств веществ, связанных с взаимодействием вещества с растворителем (водой). Соответствующая модель, основанная на пяти квантово-химических параметрах и одном геометрическом, имеет вид: logl/C=ao-sraiV+a27[*+a3?a+a4?b+a5q++a6q~, где V — ван-дер-ваальсов объем молекулы, л* - поляризуемость молекулы, еа=.

Ецомо воды ~~E[jjjo вещества Sb ЕщМО воды Е HOMO вещества> qнаибольший положительный заряд на атоме водорода, q' - наибольший отрицательный атомный заряд в молекуле, а0-а^ - некоторые константы. В работе [16] отмечено, что при использовании этих параметров предполагается, что растворитель не меняет существенно геометрическую и электронную структуру молекулы, однако, это не всегда так. Имеется много примеров успешного использования этого метода [16]. Однако есть и примеры того, что применение этого метода не позволяет получить достаточно хорошую корреляцию [37].

Таким образом, общих, обоснованных правил выбора молекулярных параметров и аппроксимирующей функции при построении моделей в QSAR/QSPR — исследованиях нет. Традиционный подход к построению моделей связи «структура-свойство» типа уравнения (1) заключается в следующем. Сначала выбирается некоторое множество молекулярных параметров (топологических, квантово-химических, геометрических и др.), обычно известных из литературы [4,5,10,38,39], и составляется комплекс компьютерных программ для их вычисления. Примерами являются известные из литературы программные комплексы POLLY [40], CODES SA [41], STAR [42], EMMA [43]. Далее создается база данных, содержащая соединения с известными значениями изучаемого свойства. Для структур этой базы вычисляют значения выбранных параметров. Как правило, между многими параметрами существуют сильные корреляции. Выявляя такие корреляции, часть параметров отбрасывают. В качестве функции / обычно используется линейная или квадратичная функции. Далее из оставшегося набора параметров стандартным методом (например, методом пошаговой линейной регрессии или каким либо другим) отбирается относительно небольшое число параметров, дающих наилучший результат с точки зрения определенного критерия. В качестве таких критериев могут быть использованы ограничения на коэффициент корреляции R, среднеквадратичное или максимальное отклонение а, и т. д. Например, в работе [44] рассматривается 90 параметров (топологических индексов), в [45] - 81, в [46] - 165, причем в последних двух случаях — топологические, электронные и геометрические параметры.

Изложенный выше подход имеет очевидные ограничения, поскольку заранее неизвестно, какие параметры нужны в данной конкретной задаче даже при заданной функции / Возможно, что для эффективного решения рассматриваемой задачи, определяемой выборкой соединений и свойством, нужны совсем другие параметры, не попавшие в число запрограммированных. Так, например, в работе [46] сообщается о результатах построения линейной регрессионной модели для 127 соединений на основе 165 параметров: наилучший возможный результат, причем недостаточно хороший, был достигнут на 5 параметрах, а добавление других параметров не приводило к существенному улучшению модели.

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

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

Первоначально модели связи «структура-свойство» рассматривались лишь для относительно небольших, однородных баз данных структурно родственных соединений. Эти соединения имели один общий фрагмент и несколько заместителей в разных положениях. В этом случае ОП моделей определялась естественным образом: она состояла из всех структур такого типа [48,49]. Затем рассматривались базы данных, состоящие из нескольких классов такого типа. Для таких баз строились корреляционные уравнения, содержащие так называемые индикаторные переменные, соответствующие имеющимся классам соединений. Эти переменные принимают значения 0 или 1, в зависимости от того, принадлежит ли данное соединение определенному классу (или в зависимости от наличия в структуре определенного фрагмента). В этом случае ОП построенных моделей определялась аналогично предыдущему случаю. Рассматривается также разбиение исходной базы на части, соответствующие имеющимся классам соединений, и проведение независимых исследований для каждого класса [50,51]. Если же имеется разнородная база данных, которую нельзя разбить на четко определенные химические классы соединений, то такие методы определения ОП не могут быть применены. Как правило, в этом случае ОП задается перечислением ряда структурных фрагментов, которые обязаны присутствовать или отсутствовать во всех структурах из ОП [52−56]. ОП можно определить, задавая и ограничения на числа вхождения в структуры определенных фрагментов, выявленные на основе анализа исходной выборки [57,58]. При этом выбор фрагментов носит субъективный характер и часто связан с гипотезами о влиянии тех или иных структурных особенностей на данное свойство. Ограничения на ОП можно сделать более жесткими, если наряду со структурными критериями, ввести критерии близости каких-либо физико-химических свойств соединений из исходной выборки и ОП (например, молекулярного веса, абсорбции, растворимостью в воде и т. д. [59]). Однако такие данные не всегда известны для рассматриваемой выборки соединений. Перечисленные выше критерии обеспечивают определенное сходство структур исходной выборки и структур из ОП. Отметим, что во всех этих подходах не учитывается никаким образом сама модель, хотя речь идет именно об ее ОП.

Обсуждая способы определения ОП, основанные на структурном сходстве соединений, следует подчеркнуть, что даже очевидное сходство структур соединений не гарантирует того, что очень «похожая» структура принадлежит ОП. В качестве примера приведем следующий факт, содержащийся в обзоре [60], посвященном истории возникновения С^АЯ. В 1869 г. Ричардсон обнаружил, что наркотический эффект в гомологических рядах спиртов жирного ряда увеличивается пропорционально увеличению количества атомов углерода в их молекулах. В многочисленных экспериментах других ученых справедливость правила Ричардсона была показана для различных гомологических рядов и при воздействии на самые различные живые объекты. Однако в 1876 г. было найдено ограничение этого правила: оказалось, оно справедливо только до определенного члена гомологического ряда.

В [61] предложен другой подход к определению ОП, учитывающий в определенной степени и саму модель. Рассматриваются погрешности расчета свойств соединений исходной выборки по построенной модели, и разбиваются на 2 класса — «хорошие» и «плохие». Для этого подбирается пороговое значение А0, такое, что примерно для 70−80% соединений исходной выборки А1<�Д0 для «хороших» соединений, а Д->Ао для остальных, «плохих» соединений. Далее разрабатывается какое-либо классификационное правило, которое на основе сходства нового соединения и соединений этих двух классов позволяет отнести его в один из вышеуказанных классов. Если соединение отнесено к «хорошему» классу, то считается, что оно принадлежит ОП, если к «плохому» — то нет. Для векторного описания структур в этом подходе используются параметры, вошедшие в построенное уравнение. Однако в этом методе нет достаточных обоснований выбора порога Д0. Кроме того, согласно идеологии этого подхода, 20−30% соединений («плохих») исходной выборки считаются не принадлежащими ОП этой модели. Фактически, роль допустимой погрешности 8 играет число А0, которое здесь не задается a 'priori, а подбирается определенным способом. Однако представляется целесообразным строить и исследовать модели, которые дают «хороший» прогноз по крайней мере на всей обучающей выборке соединений. Отметим, что ни в одной из перечисленных выше работ, посвященных определению ОП, не учитывается допустимая погрешность б, которая должна быть задана изначально, хотя очевидно, что ОП существенно зависит от е. Только в одной работе [59] отмечается необходимость учета погрешности в этих задачах, однако никаких способов ее учесть при этом не предлагается.

Проблема определения ОП тесно связана с проблемой оценки прогнозирующей способности модели. Для этих целей используется тестовая выборка соединений с известными значениями рассматриваемого свойства. Для соединений этой выборки при помощи построенной модели рассчитываются значения свойства, которые затем сравниваются с экспериментальными значениями. Качество прогноза затем оценивается, например, по коэффициенту корреляции и среднеквадратичному отклонению для регрессии, построенной по экспериментальным и расчетным данным. Для получения тестовой и обучающей выборки структур всю исходную базу данных делят каким-либо способом на 2 части (обычно — случайным образом, хотя для этой цели могут быть использованы и специальные алгоритмы [62]): например, в [63] базу делят пополам, в [61] - обучающая выборка составляет 80% базывозможны и другие пропорции при делении базы на 2 части. Следует отметить, что во многих работах выбор обучающей и тестовой выборки просто декларируется, без мотивированных объяснений.

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

Подчеркнем, что сделать обобщенных выводов из полученных результатов вышеописанных тестов нельзя. Можно только лишь сказать, какие из тестируемых соединений принадлежат ОП построенной модели, а какиенет (если, конечно, при этом известно, какой прогноз считается хорошим). Если модель плохо прогнозирует свойства каких-либо нескольких соединений, то нельзя сказать, что она «плохая» или сам метод моделирования «плох»: возможно, эти соединения просто не принадлежат ОП этой модели. Как справедливо отмечается в [61], знание результатов прогноза на тестовой выборке не позволяет нам судить о том, каков будет прогноз на новой выборке соединений, свойства которых нам не известны. Однако именно последняя выборка и представляет практический интерес. В связи с этим разработка методов определения ОП моделей связи «структура-свойство», позволяющих сократить долю «плохих» прогнозов, является очень важной задачей [61]. Отметим, что если некоторое соединение теоретически не принадлежит ОП данной модели, то следует отказаться от прогноза его свойства по этой модели, и пытаться построить для него другую, более подходящую. Следует подчеркнуть и такой факт: выделение из всей базы данных обучающей выборки и построение модели только по ней приводит к искусственному уменьшению объема анализируемой информации и к потере какой-либо информации о связи «структура-свойство». Анализируя работы в области (^РИ/С^АИ — анализа, можно обнаружить, что в подавляющем большинстве работ, посвященных построению вышеуказанных моделей, тестовая выборка отсутствует. Вероятно, авторы этих работ являются сторонниками вышеуказанной точки зрения.

• Обратная задача в ОЗАШОБРЯ — исследованиях. В исследованиях связи «структура-свойство» может быть сформулирована так называемая обратная задача (03), заключающаяся в исчерпывающей генерации химических структур определенного класса, обладающих заданной величиной (или интервалом изменения) свойства у0, на основе предварительно построенной модели связи «структура-свойство» вида (1). В качестве параметров х],., х^ для описания структуры молекул при решении 03, как правило, рассматриваются инварианты соответствующих молекулярных графов. Это вполне естественно, так как они непосредственно связаны со структурой графов, в отличие, например, от эмпирических молекулярных параметров. В этом случае 03 сводится к исчерпывающей генерации молекулярных графов по заданному значению их инварианта вида /(3С],., хн).

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

Отметим также, что задачи восстановления графа по значению одного его инварианта в математической литературе по теории графов практически ранее не рассматривались. Это связано с тем, что: 1) в математике обычно представляют особый интерес лишь те инварианты, которые определяют граф однозначно- 2) задача поиска графов с заданным значением какого-либо инварианта теоретически может быть решена переборным путем на основе конструирования всех графов с заданным числом вершин и ребер и вычисления значений заданного инварианта на каждом из них. Однако количество химических графов даже для определенного класса соединений с ростом числа вершин астрономически растет (например, число структурных изомеров алканов СпН2&bdquo-+2 при п=20 равно 366 319, а при п=30 — 4 111 846 763). Очевидно, что с точки зрения химии не важно, одно или много решений будет иметь поставленная задача. С другой стороны, с практической точки зрения важно получить обозримое множество структур за разумное время. Актуальность данной задачи в области поиска соединений с заданными свойствами, а также отсутствие подходящих алгоритмов привели к развитию целого направления в математической химии, связанного с реконструкцией молекулярных графов по их инвариантам.

Первой работой в этой области была работа [64], в которой излагалась методология решения 03 для наиболее популярных инвариантов простых графов (топологических индексов), используемых в корреляциях «структура-свойство» — индексов Винера и Рандича. При этом предполагалось, что соответствующие инварианты могут быть однозначно выражены через «у» из корреляционного уравнения, и заданному значению «у» соответствует некоторое значение рассматриваемого инварианта. Основная идея предлагаемого подхода заключалась в определении по заданной величине свойства всех возможных распределений степеней вершин у искомых простых графов, с последующей генерацией графов по этой информации по уже имеющимся алгоритмам. В статье [65], посвященной применению математики в химии, отмечается, что вышеуказанная работа [64] была пионерской в данной области и стимулировала развитие целого направления в математической химии, связанного с обратными задачами в проблеме связи «структура-свойство». В дальнейшем были разработаны алгоритмы решения 03 и для других инвариантов графов, в которых использовалась та же основная идея. Так, например, в [66] рассматривалась 03 для центрического индекса Балабана, в [67] - для валентно-взвешенного индекса Рандича, в [68−70] - для инвариантов, равных числам вхождения в простой граф цепочек длины 1, 2, 3. В работе [71] предлагается другой подход к решению 03 для индексов Рандича и Винера. Суть этого подхода заключается в том, что в разработанный авторами алгоритм генерации графов с заданным числом вершин и ребер «встраивается» процедура поиска графов с заданным значением соответствующего инварианта. При этом используются некоторые гипотезы о свойствах индексов Рандича и Винера, которые позволяют вести генерацию графов в определенном направлении. Однако, авторы [71] не смогли доказать выдвинутые гипотезы в общем виде, но проверили их справедливость для определенных графов. Таким образом, предложенный в [71] подход к решению 03 носит эмпирический характер. Обзор результатов по разработке методов решения 03, полученных к 1995 г., дан в работе [72]. Среди других подходов к поиску соединений с заданными свойствами на основе предварительно построенных уравнений связи «структура-свойство» отметим методы, основанные на стохастической генерации структур [73] или генерации структур на основе генетических алгоритмов [74]. Эти методы применимы к уравнениям произвольного вида и позволяют решить в определенной степени проблему «комбинаторного взрыва». Однако при таких подходах в общем случае не проводится исчерпывающая генерация структур, и всегда есть возможность пропустить какие-либо перспективные соединения.

• Построение моделей связи «структура-свойство» на основе концепции молекулярного подобия. Модели связи «структура-свойство» могут иметь и другую форму, отличную от уравнения (1). Например, широко используются модели, основанные на концепции молекулярного подобия (КМП), суть которой отражена в постулате «подобные структуры имеют подобные свойства». Эти модели определяются заданием некоторой количественной меры молекулярного подобия с{(Х (1)гХ (2)), где с1 — симметричная функция двух векторных аргументов Л®- =(х/'., хп (')) (1=1,2), образованных какими-либо молекулярными параметрами, соответствующими паре соединений 5/ и ?2 • В отличие от случая уравнения (1), функция с1 задается а’рпоп [9,19,75−86,87]. Предполагается, что имеется база данных по структурам и свойствам соединений. Первоначально выбирается некоторый способ математического описания структуры молекул (например, в виде молекулярных графов и связанных с ними векторами, множествами, последовательностями, матрицами и т. д.). Затем вводится некоторая количественная мера подобия двух структур и $>2, с1(81,82)>0, являющаяся скалярной функцией двух аргументов 5/ и 5<2. Обычно функция с1 является метрикой. Вид функции с1 зависит от выбранного способа описания структуры молекул, и по сути, с! является мерой сходства соответствующих математических объектов. Для прогнозирования свойств соединений в рамках этого подхода используются свои специфические методы, в той или иной форме основанные на постулате «близкие структуры имеют близкие свойства». Суть этих подходов заключается в следующем: для исследуемого соединения при помощи выбранной меры определяется соединение, «ближайшее» к нему в заданной базе данныхсчитается, что значения свойств исследуемого соединения и близкого к нему примерно одинаковы. В более общем случае для расчета свойства уо какого-либо соединения используется так называемый «метод к ближайших соседей», согласно которому у0 есть среднее арифметическое численных значений свойств к соединений, ближайших к данному по мере с1 [19,88−91]. Число к подбирается эмпирическим способом.

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

Приведем примеры мер подобия для случая, когда химические структуры Si представлены молекулярными графами G, (i=l, 2) [87].

1) Пусть для графов Gj и G2 построены вектора x (1)=(x/I),., xJI) j и x (2)-(xi (2),., xn (2)), компоненты которых — какие-либо инварианты графов. В этом случае в литературе рассматривались следующие меры подобия: р — любое целое число- (метрика пространства L") — m (k)=(l/n)lxi (k k=l, 2 (коэффициент корреляции) — d3(x (1)^2)) =[Zx!ux!2)] / [Ц (х!!))2+Цх!2))2−1х!их!2)] (коэффициент Танимото) — d^^^x^-x^logt^/x!2) — d5(x (1)^c (2)) =[Zmin (x!'), x.

2) Пусть графам G и G2 поставлены в соответствие конечные множества Di и ?>2, соответственносимвол |D| означает число элементов в множестве D. Для этого случая были введены следующие меры: d9(Di, Dd=Di+D2−2DiCD2- d, o (D, D2)=D1nD2/(D1-D2) — dn (D1,D2)=D] D2 + D2DI I.

3) Пусть MACS (G], G2) — максимальный общий подграф графов Gj и Gf, |G| - суммарное число вершин и ребер графа G. В литературе рассматривались следующие меры подобия, основанные на максимальном общем подграфе: d12(GhG2)=G, + G2−2MACS (G!, G2)-, dв (G и G2)=I MA CS (GI, G2)2/(GI-G2).

4) Пусть графам G и G2 поставлены в соответствие последовательности Lj и Lf, LCS — наибольшая общая подпоследовательность в Lj и L2- Lдлина последовательности L. Тогда можно построить следующие меры подобия: d14(U, L2)=U + L2V2LCS (U, L2)\ di5(L1,L2)=LCS (L1,L2)2/(L1-L2) Однако меры сходства химических структур используются не только для прогнозирования свойств соединений описанным выше методом. Различные меры подобия используются также и при изучения связи структуры и биологической активности, задаваемой качественно (активны/неактивны), методами теории распознавания образов [1,88]. Такие подходы детально описаны в монографиях [1,2], а также в обзоре [3]. Программный комплекс PASS, предназначенный для прогнозирования с определенной вероятностью наличия или отсутствия биологической активности, описан в [63,92,93,94]. Однако мы рассматриваем лишь случаи количественных моделей связи «структура-свойство», и поэтому не будем детально описывать это направление в моделировании связи «структура-свойство».

Отметим также, что имеются подходы, в которых для заданной выборки соединений строятся модели следующего вида: у]=1а4и+а0 < где у] - значение свойства /-ого соединения, аь а0 — постоянные, с1у — значение меры сходства /-ого и /-ого соединения [19].

Метод прогнозирования свойств соединений в рамках КМП на основе метода «ближайшего соседа» (или «к ближайших соседей») имеет следующие преимущества перед описанным выше статистическим подходом: 1) можно сравнивать структуры молекул как целостные объекты, не используя для их описания вектора, состоящие из отдельных молекулярных параметров- 2) если же такие вектора все же использованы, то их длины могут быть любыми- 3) не требуется подбирать аппроксимирующую функцию/ 4) для оценки свойства соединения нужно знать значение свойства лишь «близкого» к нему соединения, а не всех соединений выборки. Однако, при использовании метода, основанного на КМП, возникает и ряд проблем. Например, заранее неизвестно, какой способ математического описания структуры молекулы и вид меры подобия следует выбрать в конкретной задаче. Очевидно также, что результат прогноза существенно зависит от того, как составлена база данных, используемая при прогнозе свойств: возможно, действительно «близкого» соединения с «близким» свойством в ней просто нет. Отметим, что понятие «сходства» химических соединений в первую очередь понимается как визуальное сходство соответствующих структурных формул. Однако, в литературе, посвященной этой тематике, в качестве опровержения такого упрощенного понимания этого понятия, приводятся примеры пар соединений, обладающих: 1) значительным визуальным сходством, но имеющих существенно различные свойства (например, биологически активных и неактивных по отношению к определенному виду активности) — 2) имеющих одинаковые свойства, но совершенно различную структуру (см., например [19]). В связи с этим выбор адекватного способа математического описания молекулярной структуры, а также соответствующей меры подобия, при которых «подобные» структуры будут иметь «подобные» свойства, являются важными составляющими в прогнозировании свойств на основе КМП и определяют эффективность этого метода.

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

Эти задачи тесно связаны между собой. Так, например, один из способов однозначного кодирования графов связан с построением канонической нумерации вершин графа и использованием в качестве такого кода либо соответствующей матрицы, называемой канонической, либо ее представлением в виде одной строки или числа. Очевидно, что при наличии канонических представлений графов проблема их изоморфизма решается тривиальным образом. Задача поиска всех автоморфизмов графа (т.е. его группы симметрии) (7 с матрицей, А является частным случаем задачи нахождения всех изоморфизмов пары графов С] и с матрицами А1 и соответственно. Действительно, графы С] и с числом вершин п изоморфны тогда и только тогда, когда существует квадратная матрица X «-ого размера, соответствующая некоторой подстановке ж из симметрической группы Бп, такая, что А1Х-ХА2. Все такие матрицы X (или подстановки ж) дают все изоморфизмы графов С] и.

Очевидно, что в частном случае, когда (А=А]=А2 соответствующие подстановки дают группу симметрии графа & Отметим также, что алгоритм нахождения в графе (7- всех подграфов, изоморфных заданному графу бможно использовать для установления изоморфизма двух графов й] и С2 с одинаковым числом вершин.

Следует подчеркнуть, что все вышеуказанные задачи, в принципе, могут быть решены непосредственным перебором вариантов. Однако количество этих вариантов существенно растет при росте числа вершин графа. Поэтому такие процедуры на практике неприменимы, что ведет к необходимости разработки алгоритмов, использующих разные приемы для сокращения перебора. Имеется много работ, посвященных алгоритмам установления изоморфизма графов [1,2,95−103]. Многие из них ориентированы лишь на графы специального типанекоторые процедуры носят эвристический характер. Можно выделить три традиционных подхода к решению этой проблемы. В первом из них множество вершин графа разбивается на классы эквивалентности каким — либо способомзатем проверяются на изоморфизм те отображения множеств вершин, которые переводят в себя вершины каждого класса [100−103]. Для разбиения вершин на такие классы обычно используются какие-либо локальные вершинные инварианты графа (например, степень вершинычисло путей различной длины, начинающихся в данной вершине и т. д.). В другом подходе матрица графа преобразуется в каноническую форму, и полученные канонические матрицы сравниваются между собой [105−109]. Третий подход основан на поиске специального подмножества вершин в «произведении» графов, которое строится определенным образом из двух исходных графов. Наличие такого подмножества вершин показывает, что графы изоморфны [110−112]. Можно выделить также и еще один подход, основанный на поиске полного набора инвариантов графов (т.е. набора инвариантов, определяющих граф однозначно). Однако быстро вычислимого полного набора инвариантов графов пока не найдено. В разных алгоритмах используются некоторые неполные множества инвариантов, позволяющие сократить перебор [95−99]. В работах [108,113−115] приведены алгоритмы поиска группы симметрии графа. Работы [111,112,116.

125] посвящены задаче поиска заданных подграфов в графе. Предлагаемые алгоритмы, по сути своей, являются переборными. Для сокращения перебора используются те или иные необходимые условия изоморфизма, позволяющие в ряде случаев сократить перебор. Эффективность подобных алгоритмов обычно проверяется экспериментально, и результат зависит от вида графов. Отметим также, что для сравнения алгоритмов необходимо иметь соответствующие компьютерные программы, написанные на одном языке программирования, что не всегда реально. Довольно трудно теоретически оценить сложность алгоритмов в общем случае. Однако желательно, чтобы алгоритмы, применяемые на практике, обладали следующими свойствами: 1) универсальность (т.е. применимость его к произвольным графам с любыми метками вершин и ребер- 2) строгость, дающую гарантию правильного результата в любой ситуации- 3) приемлемое быстродействие при обработке больших баз данных или графов с большим числом вершин. Для практического использования описанных в литературе алгоритмов также важно, чтобы они были достаточно детально разработаны и не требовали дальнейших уточнений.

• Выводы. Таким образом, в последние десятилетия опубликовано большое число работ, посвященных моделированию связи «структура-свойство» на основе представления молекул в виде графов и описания их структуры в терминах инвариантов графов. В подавляющем большинстве случаев для описания молекулярной структуры рассматриваются разнообразные топологические индексы, что связано с относительной простотой и быстротой их вычисления, а также с практически неограниченными возможностями варьировать как способ взвешивания графа, так и способ вычисления самого инварианта. На втором месте по степени распространенности — квантово-химические дескрипторы, а на третьемгеометрические параметры. Эту область исследований, возникшую на стыке нескольких научных дисциплин, иногда рассматривают как часть математической химии, компьютерной химии или химической информатики. Многочисленные работы, посвященные этой тематике, публикуются в таких международных журналах, как Journal of Chemical Information and Computer Science, Journal of Computational Chemistry, Journal of Mathematical Chemistry, Computers and Chemistry и. т. д. Постоянно проводятся международные конференции по этой тематике. Интенсивное развитие данного направления связано, прежде всего, с широким внедрением ЭВМ в химические исследования, созданием баз данных по структурам и свойствам соединений, а также доступностью вычислительной техники для химиков. Все это делает возможным проводить статистическую обработку накопленной информации с целью выявления различных скрытых закономерностей. Наличие многочисленных примеров успешного применения вышеуказанного подхода для моделирования связи «структура-свойство» как для физико-химических свойств, так и для разных видов биологической активности, показывающих эффективность применяемого метода, также способствует развитию данного направления. Кроме того, определенным стимулом исследований в этой области является их финансовая поддержка многочисленными организациями, интересующимися поиском и синтезом новых веществ с заранее заданными свойствами, в том числе и определенными видами биологической активности.

Однако, при моделировании связи «структура-свойство» в рамках статистического подхода, основанного на использовании инвариантов молекулярных графов, возникает ряд следующих существенных проблем:

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

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

Г* ^ или меры с!) не существует. В связи с эти/возникает проблема оптимального ' выбора относительно небольшого числа инвариантов для описания структуры молекул в каждой конкретной задаче, а также выбора функций /или <Л;

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

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

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

— отсутствие обоснованных критериев для выбора конкретных инвариантов графов и аппроксимирующей функции;

— отсутствие теоретического обоснования того, что химические соединения, на которые экстраполируется зависимость вида (1), принадлежат области применимости модели (1);

— недостаточная разработка методов решения обратных задач;

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

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

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

2. Цели диссертационной работы.

Цели работы связаны с перечисленными выше проблемами. Они таковы:

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

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

3) Разработать обоснованные подходы для описания областей применимости теоретико-графовых моделей вида (1). Провести тестирование предложенных методов.

4) Разработать алгоритмы решения обратных задач в проблеме связи «структура-свойство» на основе уравнений (1) различных видов. Провести тестирование этих алгоритмов.

5) Разработать методы построения моделей связи «структура-свойство» и прогнозирования свойств химических соединений на основе концепции молекулярного подобия. Провести тестирование предложенных методов.

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

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

3. Структура и основные результаты диссертационной работы.

Диссертационная работа состоит из введения, шести глав, выводов, списка цитированной литературы, списка публикаций по теме диссертации и приложения. Работа содержит 35 таблиц, 49 рисунков и занимает объем в 276 стр. Каждая глава посвящена отдельной тематике, рассматриваемой в рамках общей задачи исследования связи «структура-свойство» и имеет логическую завершенность. Главы логически связаны между собой и отражают практически все основные этапы в рамках (^АМ^РИ-исследований. Так, Глава 1 и Глава 2 посвящены проблеме построения моделей вида (1), связывающих строение и свойства органических соединений. Однако, основная цель построения таких.

ВЫВОДЫ.

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

В диссертационной работе:

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

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

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

4) Проведено исследование задачи определения области применимости модели связи «структура-свойство» для заданной допустимой погрешности расчета свойств соединений е>0, а также предложен ряд методов ее решения.

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

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

5) Разработаны алгоритмизированные методы решения различных обратных задач в исследованиях связи «структура-свойство». Эти методы позволяют провести исчерпывающую генерацию химических структур определенного класса, имеющих заданное значение у0 рассматриваемого свойства (или заданный интервал (у, у2) изменения значений свойства), на основе предварительно построенной модели вида у=/(х!,., хд), связывающей значения рассматриваемого свойства и некоторые инварианты молекулярных графов Х],., Хм. Рассмотрены базовые корреляционные уравнения, содержащие различные инварианты, широко используемые при моделировании связи «структура-свойство» и допускающие определенную структурную интерпретацию. Проведено тестирование предложенных методов.

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

6) Предложены модели связи «структура-свойство» нового типа, которые отражают широко распространенный в химии постулат «близкие структуры имеют близкие свойства», позволяющие в ряде случаев оценивать свойство соединения на основе его сходства с другим соединением, для которого значение изучаемого свойства известно. Эти модели имеют следующий вид: у~ урДОьО^, где уу у) — значения свойств пары соединений 6- и бу, а ¿-/(6&bdquo-6у) -некоторая симметричная функция двух аргументов (графов) б, и бу, значения которой количественно характеризуют степень подобия двух структур б, и бу. Предложен метод оптимального подбора меры й⁶/, бу) в этом соотношении по заданной выборке соединений, а также способ оценки свойств соединений на основе такой модели.

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

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

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

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

ИВГ", реализующей алгоритм изоморфного вложения графов, в исследования по планированию органического синтеза.

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

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

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

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

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

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