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

Размещено на http://www.allbest.ru/

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

МАТЕМАТИЧЕСКИЕ МОДЕЛИ И АЛГОРИТМЫ В ИССЛЕДОВАНИЯХ СВЯЗИ МЕЖДУ СТРУКТУРОЙ И СВОЙСТВАМИ ОРГАНИЧЕСКИХ СОЕДИНЕНИЙ

Скворцова Мария Ивановна

05.13.18 - математическое моделирование,

численные методы и комплексы программ

Москва - 2007

Работа выполнена в Московской государственной академии тонкой химической технологии (МИТХТ) им. М. В. Ломоносова

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ:

доктор физико-математических наук, профессор Сапоженко А.А.

доктор физико-математических наук, профессор Чернозатонский Л.А.

доктор химических наук, профессор Гюльмалиев А.М.

ВЕДУЩАЯ ОРГАНИЗАЦИЯ:

Институт математического моделирования РАН

Защита состоится «___» ______________2007 г. в «___» час. на заседании диссертационного совета Д 501.001.43 при Московском государственном университете им. М.В. Ломоносова по адресу: 119992, г. Москва, ГСП-2, Ленинские горы, МГУ, факультет вычислительной математики и кибернетики, ауд. 685.

С диссертацией можно ознакомиться в библиотеке факультета вычислительной математики и кибернетики МГУ им. М.В.Ломоносова.

Автореферат разослан «____» __________2007 г.

Ученый секретарь

диссертационного совета, Захаров Е. В.

доктор физико-математических наук

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

АКТУАЛЬНОСТЬ ТЕМЫ. Проблема моделирования связи между структурой и свойствами органических соединений является одной из важнейших математических задач современной теоретической химии. Найденные закономерности позволяют, минуя эксперимент, прогнозировать свойства новых химических соединений непосредственно по их структуре и могут быть использованы для планирования целенаправленного поиска соединений с заданными свойствами.

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

Приведем краткую характеристику наиболее распространенного современного подхода к моделированию связи «структура-свойство». Имеется выборка соединений с известными численными значениями некоторого свойства этих соединений. Структура соединений описывается при помощи набора молекулярных параметров x₁,…,x_n , в качестве которых используются топологические, электронные, геометрические характеристики молекул или значения каких-либо физико-химических свойств. Как правило, математическая модель связи «структура-свойство» в рамках этого подхода имеет вид уравнения, связывающего численные значения исследуемого свойства y и молекулярных параметров x₁,…,x_n при помощи некоторой функции f:

y=f(x₁,…,x_n). (1)

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

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

Важное место в вышеуказанных исследованиях занимают способы количественного описания структуры молекул, т.е. выбор параметров х₁,…,х_n. От этого выбора значительно зависит эффективность модели. Параметры х₁,…,х_n могут быть как экспериментальными, так и расчетными. Использование расчетных параметров в моделях связи «структура-свойство» более предпочтительно, т. к. они могут быть вычислены даже для гипотетических структур. Для получения этих параметров в качестве основы используется классическая структурная формула молекулы, которую можно рассматривать как меченый граф. По структурной формуле могут быть построены другие меченые графы. Вершины таких графов, называемых молекулярными, обычно соответствуют атомам (или фрагментам), а ребра - химическим связям молекулы. Метки вершин кодируют атомы различной химической природы, а метки ребер - связи разного типа. Метки типа буквенных символов характеризуют атомы и связи качественно, а числовые метки (веса) - количественно. Веса вершин и ребер могут быть взяты как из литературы (например, заряды ядер или ковалентные радиусы атомов), так и рассчитаны при помощи специальных стандартных программ, позволяющих определить электронные и геометрические характеристики молекул (например, могут быть найдены потенциалы ионизации, межатомные расстояния или рассчитаны заряды на атомах). На рис.1 в качестве примера приведена структурная формула 1,3-дихлорфенола и соответствующий ей меченый граф, в котором вершины соответствуют атомам углерода, а их метки A, B, C кодируют атомы углерода, в зависимости от присоединенных к ним фрагментов H, Cl или OH.

Рис.1.

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

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

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

ЦЕЛИ РАБОТЫ. При моделировании связи «структура-свойство» вышеописанным методом возникают следующие проблемы:

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

2) Выбор функции f (или меры молекулярного подобия d) и инвариантов х₁,…,х_n для описания структуры молекул в конкретной задаче. Отметим, что число инвариантов графов бесконечно даже для одного, фиксированного способа взвешивания графа. Как правило, большинство инвариантов, используемых в теоретической химии, получают при помощи формальных математических операций с графами, поэтому им трудно дать достаточно ясную физико-химическую или структурную интерпретацию. Заранее не известно, от каких именно структурных особенностей зависит данное свойство, и каким образом. Поэтому никаких четких правил выбора молекулярных параметров x₁,…,x_n и аппроксимирующей функции f (или меры d) для построения модели не существует;

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

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

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

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

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

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

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

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

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

НАУЧНАЯ НОВИЗНА И ПРАКТИЧЕСКАЯ ЗНАЧИМОСТЬ РАБОТЫ Диссертационная работа посвящена разработке и обоснованию математических методов решения основных задач, возникающих при моделировании связи «структура-свойство» органических соединений: построения моделей, определения их областей применимости, конструирования химических соединений с заданными свойствами на основе построенных уравнений. В качестве исходных данных для такого моделирования используются базы данных по структурам и свойствам химических соединений. Обработка этих данных позволяет выявить скрытые закономерности между структурой и свойствами органических соединений. В качестве математических моделей химических соединений используются произвольно меченые графы. В диссертации:

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

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

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

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

5) Разработаны алгоритмизированные методы решения различных обратных задач в исследованиях связи «структура-свойство». Эти методы позволяют провести исчерпывающую генерацию химических структур определенного класса, имеющих заданное значение y₀ рассматриваемого свойства (или заданный интервал (y₁, y₂) значений свойства), на основе предварительно построенной модели вида y=f(x₁,...,x_N), связывающей значения рассматриваемого свойства у и некоторые инварианты молекулярных графов x₁,...,x_N. Рассмотрены базовые корреляционные уравнения, содержащие различные инварианты, широко используемые при моделировании связи «структура-свойство» и допускающие определенную структурную интерпретацию. Проведено тестирование предложенных методов.

6) Предложены модели связи «структура-свойство» нового типа, которые отражают широко распространенный в химии постулат «близкие структуры имеют близкие свойства», позволяющие в ряде случаев оценивать свойство соединения на основе его сходства с другим соединением, для которого значение изучаемого свойства известно. Эти модели имеют следующий вид: y_i-y_j=d(G_i,G_j), где y_i, y_j - значения свойств i-ого и j-ого соединений, представленных графами G_i и G_j, а d(G_i,G_j) - некоторая симметричная функция двух аргументов G_i и G_j, значения которой количественно характеризуют степень подобия G_i и G_j. Предложен метод оптимального подбора меры d(G_i,G_j) в этом соотношении, а также способ оценки свойств соединений на основе такой модели. Проведено тестирование метода, а также его сравнение с двумя другими методами, использующими другие меры подобия. Это сравнение показывает, что предложенный в работе метод дает более точный результат, чем остальные методы.

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

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

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

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

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

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

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

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

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

Полученные результаты могут быть включены в спецкурсы по математическому моделированию в химии, медицинской химии, теории графов, прикладной математике. Ряд приведеных в работе результатов был использован автором при чтении спецкурса по дисциплине «Теория графов» в МИТХТ им. М. В. Ломоносова.

ЛИЧНЫЙ ВКЛАД АВТОРА. Постановки задач, рассматриваемых в Главах 1-5, методы их решения, а также алгоритмы на графах из §6.2, §6.4 Главы 6 разработаны автором. Алгоритм из §6.3 Главы 6 разработан совместно с д.х.н. Трачом С. С. Теоретические результаты (определения, теоремы 1.1-1.12, 5.1-5.3) получены лично автором. Тестирование предложенных методов и алгоритмов в ряде случаев выполнено автором самостоятельно, а в ряде - совместно с соавторами публикаций по теме диссертации. Проведение компьютерно-статистических экспериментов по проверке гипотез о свойствах графов, описанных в §1.3-1.5, выполнено совместно с Федяевым К.С. В разработке компьютерных программ участвовали: Баскин И.И., Словохотова О.Л., Федяев К.С., Пасюков А.В., Дозор И.Н., Трач С.С., Гальперн Е.Г.

АПРОБАЦИЯ РАБОТЫ. Основные результаты диссертации были представлены на следующих конференциях и симпозиумах: Всесоюзной конференции «Использование вычислительных машин в химических исследованиях и спектроскопии молекул» (Рига, 1986); Всесоюзной школе-семинаре по автоматизации химических исследований (Тбилиси, 1988); Межреспубликанской научно-практической конференции «Синтез, фармакология и клинические аспекты новых психотропных и сердечно-сосудистых средств» (Волгоград, 1989);VIII - ой Всесоюзной конференции «Использование вычислительных машин в спектроскопии молекул и химических исследованиях» (Новосибирск, 1989); Межвузовских конференциях «Молекулярные графы в химических исследованиях» (Одесса, 1987; Калинин,1990); I-ой Всесоюзной конференции по теоретической органической химии (ВАТОХ) (Волгоград,1991); Symposium “QSAR and Molecular Modeling: Concepts, Computational Tools and Biological Applications” (Spain, Barcelona, 1995); 11-th European Symposium on Quantitative Structure - Activity Relationships: Computer-Assisted Lead Finding and Optimization, (France, Lausanne, 1996); International Conference on Inverse and Ill- Posed Problems (IIPP-96), (Russia, Moscow, 1996); International Symposium CACR - 96, (Russia, Moscow, 1996); IV-ом Российском научном конгрессе «Человек и лекарство» (Москва, 1997); I-ой, II-ой, III-ей, IV-ой Всероссийских конференциях «Молекулярное моделирование» (Москва, 1998г, 2001 г., 2003 г., 2005); Ninth International Workshop on Quantitative Structure-Activity Relationships in Environmental Sciences, (Bulgaria, Bourgas, 2000); International School-Seminar on Computer Automatization and Information, (Russia, Moscow, 2000); II-ом Международном симпозиуме «Компьютерное обеспечение химических исследований», (Москва, 2001); Memorial International Symposium “Modern Trends in Organometallic and Catalitic Chemistry. Mark Vol'pin (1923-1996)” (Russia, Moscow, 2003); Fourth Indo-US Workshop on Mathematical Chemistry (With Application to Drug Discovery, Environmental Toxicology, Chemoinformatics and Bioinformatics), (Pune, Maharashtra, India, 2005); 11-ой Международной конференции «Математические модели физических процессов» (Россия, Таганрог, 2005); XIX Международной научной конференции «Математические методы в технике и технологиях» (Россия, Воронеж, 2006).

Научные исследования по теме диссертации были поддержаны следующими грантами: INTAS-93-32-33 («Development of New Technique for Quantitative Structure-Activity Relationships and Molecular Design»); INTAS-00-03-63 («Virtual Computational Chemistry Laboratory - CCLAB»); РФФИ - №95-03-09696а («Разработка новых нейросетевых методов исследования связи между структурой и свойствами органических соединений. Компьютерное конструирование и синтез соединений с заданными свойствами»); РФФИ - № 98-03-32955а («Разработка новых методов компьютерного дизайна органических соединений с заданными свойствами на основе искусственных нейросетей. Конструирование и синтез перспективных структур»); РФФИ- №96-03-33003а («Математические модели, алгоритмы и программы решения задач дизайна органических реакций»).

ПУБЛИКАЦИИ. По теме диссертации опубликовано 73 работы, среди которых 35 статей в журналах и сборниках (в том числе 24 статьи в журналах, рекомендованных ВАК), 34 тезиса докладов на конференциях, 2 главы в монографиях, 2 учебно-методических пособия.

СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИИ. Диссертация состоит из введения, шести глав, выводов, списка цитированной литературы (210 наименований), списка публикаций автора по теме диссертации (73 наименования) и Приложения. Работа изложена на 272 стр., содержит 35 таблиц, 49 рисунков. Каждая глава посвящена отдельной тематике, рассматриваемой в рамках общей задачи исследования связи «структура-свойство», и имеет логическую завершенность. В Главе 1 разработан ряд детерминированных методов построе-ния моделей связи «структура-свойство» на основе базисных инвариантов и базисных подграфов молекулярных графов. В Главе 2 описана система автоматической генерации инвариантов графов для моделирования связи «структура-свойство», использующая элементы случайного выбора. В Главе 3 рассматриваются различные методы определения областей применимости моделей связи «структура-свойство». Глава 4 посвящена алгоритмам решения обратных задач в исследованиях связи «структура-свойство» на основе различных базовых моделей связи «структура-свойство». В Главе 5 предложены модели, связывающие степень близости свойств и степень сходства химических соединений, отражающие постулат «близкие структуры имеют близкие свойства». Глава 6 посвящена описанию ряда алгоритмов на графах, используемых для их кодирования, идентификации и исследования структурных особенностей. Приложение содержит краткие описания некоторых из компьютерных программ, использованных для тестирования разработанных методов. инвариант базисный граф молекулярный

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Рассматривается следующая общая проблема моделирования связи «структура-свойство»: по заданной выборке органических соединений {S_i} (i=1,...,k), представленных классическими структурными формулами с известными численными значениями некоторого свойства {y_i}, построить уравнение вида y=f(S), связывающее значения изучаемого свойства y и структуры S данных соединений при помощи некоторой функции f. Основная цель построения модели - оценить значения свойств y_i других соединений S_i, не включенных в исходную выборку. Следовательно, на этапе применения модели возникает задача определения ее области применимости, т. е. выделения такого подмножества структур в некотором заданном множестве {S_i} (i=k+1,…,N), свойства которых могут быть рассчитаны при помощи уравнения y=f(S) с заданной допустимой погрешностью 0.

Пусть математической моделью химического соединения S является произвольно меченый граф G, вершины и ребра которого соответствуют атомам и связям молекулы, а метки вершин и ребер кодируют атомы и связи различной химической природы. Метки могут быть как числами, так и произвольными символами. Способ выбора меток и их интерпретация для дальнейших исследований не важны. Если отождествить структуру S с соответствующим молекулярным графом G, то свойство y (функцию от структуры) можно рассматривать как инвариант графа y=f(G) (т.е. число, определяемое по графу, значение которого не зависит от способа нумерации его вершин).

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

- задача построения уравнения типа y=f(S) равносильна задаче восстановления аналитического вида некоторого инварианта y=f(G) графа G по набору его значений y_i=f(G_i) (i=1,…,k) на исходной выборке графов (возможно, с заданной погрешностью );

- задача определения области применимости построенной модели равносильна определению условий на граф G из некоторого множества {G_i} (i=k+1,…,N), при которых значения инварианта y=f(G) на этом графе однозначно определяются по его значениям на заданных графах {G_i} (i=1,…,k) (возможно, с заданной погрешностью ).

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

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

1) Первая стратеия: поиск базисных инвариантов графов.

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

? Определение 1 базиса инвариантов графов. Набор инвариантов {g_j} (j=1,…,M) графов множества {G_i} (i=1,…,N) назовем базисным, если любой инвариант f(G) графов этого множества однозначно представляется в виде линейной функции от них, т.е.:

_M

f(G)=?a_jg_j(G), (G€{G_i},j=1,…,N),

^j=1

где a_j (j=1,…,M) - некоторые константы, не зависящие от G, а зависящие только от f.

Сформулированы и доказаны теоремы о свойствах базиса в смысле определения 1.

ТЕОРЕМА 1.1 (необходимые и достаточные условия на набор инвариантов, при которых они образуют базис). Набор инвариантов {g_j} (j=1,…,M) образует базис множества инвариантов графов {G_i} (i=1,…,N) в смысле определения 1 тогда и только тогда, когда M=N и detB?0, где B=(b_ij) - матрица с элементами b_ij=g_j(G_i), i, j=1,…,N.

ТЕОРЕМА 1.2 (описание множества всех базисов инвариантов). Пусть {g_j} (j=1,…,N) - некоторый базис инвариантов графов множества {G_i} (i=1,…,N) в смысле определения 1, A - произвольная невырожденная квадратная матрица размера N. Построим набор инвариантов {h_j} (j=1,…,N) по формуле:

h=Ag , (2)

где g=(g₁,…,g_N), h=(h₁,…,h_N) - вектора - столбцы. Тогда:

1) Инварианты {h_j} (j=1,…,N) также являются базисом инвариантов графов в смысле определения 1; 2) Любые два базиса h и g связаны между собой при помощи формулы (2) с некоторой невырожденной матрицей А.

ТЕОРЕМА 1.3 (о существовании базиса инвариантов, равных числам вхождения в граф определенных подграфов). Рассмотрим множество графов {G_i} (i=1,…,N). Тогда инварианты g_j(G), равные числам вхождения подграфа H_j=G_j (j=1,…,N) в граф G, образуют базис инвариантов графов заданного множества.

ТЕОРЕМА 1.4 (о существовании базиса инвариантов, часть которых постоянна на выделенном подмножестве графов). Пусть в множестве графов {G_i} (i=1,…,N) выделено подмножество {G_i} (i=1,…,k; k?N). Тогда существует базис {f_p} (p=1,…,N) инвариантов графов множества {G_i} (i=1,…,N), такой, что его N-k+1 элемент постоянен на подмножестве {G_i} (i=1,…,k). При этом N-k+1 - максимальное число базисных инвариантов, обладающих вышеуказанным свойством.

ТЕОРЕМА 1.5 (характеристическое свойство графов выделенного подмножества графов). Пусть в множестве графов {G_i} (i=1,…,N) выделено подмножество {G_i} (i=1,…,k; k?N), а {f_p} (p=1,…,N-k+1) - базис инвариантов, постоянных на подмножестве графов {G_i} (i=1,…,k), т. е. f_p(G_i)=c_p, где c_p - некоторые константы, зависящие только от индекса p (p=1,…,N-k+1) (см. теорему 1.4). Тогда не существует графа G_i (i=k+1,…,N), такого, что f_p(G_i)=c_p (p=1,…,N-k+1).

ТЕОРЕМА 1.6 (Об общем виде произвольного инварианта на выделенном подмножестве графов). Пусть в множестве графов {G_i} (i=1,…,N) выделено подмножество {G_i} (i=1,…,k; k?N), а инварианты {f_p} (p=N-k+2,…,N) и константы c_p (p=1,…,N-k+1) те же, что и в теоремах 1.4 и 1.5. Тогда на любом графе G=G_i (i=1,...,k) инвариант f представляется в виде:

_{N N-k+1}

f(G)=a₀+?a_pf_p(G) , (a₀=?a_pc_p=const), (3)

^{p=N-k+2 p=1}

причем коэффициенты a=(a₀,a_N-k+2,...,a_N) однозначно определяются по значениям f(G_i) (i=1,...,k).

ТЕОРЕМА 1.7.(необходимое и достаточное условие для восстановления значения инварианта графа по набору значений этого инварианта для других графов). Пусть в множестве графов {G_i} (i=1,…,N) выделено подмножество {G_i} (i=1,…,k; k?N). Значение инварианта f(G) для графа GG_i (i=1,...,k) определяется по уравнению (3) тогда и только тогда, когда инвариант f и граф G удовлетворяют условию:

_N-k+1

?a_pf_p(G)=a₀ . (4)

^p=1

Следствие из теоремы 1.7.

Из теоремы 1.7 следует, что для проверки возможности вычисления f(G) (GG_i, i=1,...,k) по f(G_i) (i=1,...,k) необходимо знать значения a_p (p=1,...,N-k+1) (значения f_p(G) и a₀ - известны). Однако их невозможно определить по исходным данным. Следовательно, без дополнительных предположений относительно инварианта f и графа G в принципе невозможно решить вышеуказанный вопрос. Однако можно указать следующие достаточные условия на f и G, при которых выполнено условие (4). Предположим, что инвариант f такой, что a_p=0 при некоторых значениях p (1?p ?N-k+1) (причем хотя бы для одного значения p), а граф G из множества {G_i} (i=k+1,…,N) такой, что f_p(G)=c_p для остальных значений p, 1?p?N-k+1. Легко видеть, что в этом случае выполнено условие (4).

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

ТЕОРЕМА 1.8 (обобщение теоремы 1.7). Предположим, что задана допустимая точность 0 расчета значения инварианта f(G), G=G_i (i=1,…,N) и для графов G=G_i (i=1,…,k) получено приближенное уравнение вида

f'(G)=a_p'f_p(G)+a₀' , (5)

^{p S1}

где S1 -некоторое подмножество множества S={N-k+2,…,N} и f(G)-f'(G)?, а f(G) определено по формуле (3). Обозначим S2={1,…,N-k+1}. Значение f(G) для графа G=G_i (i=k+1,...,N)) вычисляется с точностью по уравнению (5) (т.е. f(G)-f'(G)?) тогда и только тогда, когда

f_p(G)(a_p-a_p')+f_p(G)a_p+fp(G)a_p-a₀'?. (6)

^{pS1 pS\S1 pS2}

Следствие из теоремы 1.8.

Сформулируем достаточные условия, при которых f(G) определяется по уравнению (5). Как и в случае теоремы 1.7, предположим, что f и G таковы, что при pS2 либо a_p=0, либо f_p(G)=c_p.

Тогда a_pf_p=a₀ ,

^pS2

а условие (6) примет вид:

f_p(G)(a_p-a_p')+f_p(G)a_p+a₀-a₀'?. (7)

^{S1 S\S1}

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

ТЕОРЕМА 1.9 (аналог теоремы 1.8). Предположим, что задана допустимая точность 0 расчета значения инварианта f(G), G=G_i (i=1,…,N) и для графов G=G_i (i=1,…,k) получено точное уравнение (3), а из него - приближенное уравнение путем замены некоторых инвариантов f_p (p=N-k+2,...,N) на их средние значения

_k

b_p=(1/k)f_p(G_i)

ⁱ⁼¹

на подмножестве графов G_i (i=1,...,k). Обозначим: S={N-k+2,...,N}, S2={1,...,N-k+1}, S1 - множество номеров базисных инвариантов, оставшихся в приближенном уравнении. Таким образом, приближенное уравнение будет иметь следующий вид:

f'(G)=a_pf_p(G)+А₀ (A₀=a₀+a_pb_p) , (8)

^{p S1 pS\S1}

причем f(G_i)-f'(G_i)? (i=1,...,k). Значение f(G) для графа G?G_i (i=1,..,k) вычисляется с точностью по уравнению (8) (т.е. f(G)-f'(G)?) тогда и только тогда, когда

(b_p-f_p(G))a_p+(c_p-f_p(G))a_p? . (9)

^{pS\S1 pS2}

Следствие из теоремы 1.9.

Сформулируем достаточные условия, при которых f(G) определяется по уравнению (8). Как и в случае следствия из теоремы 1.7, предположим, что f и G таковы, что при pS2 либо a_p=0, либо f_p(G)=c_p. Тогда a_pf_p=a₀ ,

а условие (9) примет вид

(b_p-f_p(G))a_p?. (10)

^S\S1

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

Методологические выводы из ТЕОРЕМ 1.1-1.9 и их интерпретация:

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

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

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

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

Метод построения моделей связи «структура-свойство» и его тестирование. На основании полученных теоретических результатов предложен общий алгоритмизированный метод №1 построения приближенной модели связи «структура-свойство» по набору N молекулярных графов. Метод заключается в следующем: для описания структуры графов рассматриваются N инвариантов, равных числам вхождения в произвольный граф графов этой выборки, а затем из них отбирается относительно небольшое число параметров, дающих модель удовлетворительной точности. Метод универсален: он позволяет построить точную модель связи «структура-свойство» для любой выборки химических соединений, представленных любыми мечеными графами и любого свойства химических соединений (физико-химического, биологической активности) или какого-либо вычисляемого молекулярного параметра. Таким образом, метод основан на определенном, строго детерминированном и теоретически обоснованном способе выбора инвариантов графов и аппроксимирующей функции в модели связи «структура-свойство». Число параметров, исключаемых из точной модели для получения приближенной модели заданной точности 0, зависит от состава выборки, рассматриваемого свойства, числа , а также от способа представления химических соединений молекулярными графами. Метод может быть модифицирован следующим образом: наряду с вышеуказанными подграфами рассматриваются также подграфы самого «маленького» по числу вершин графа, и наилучший набор параметров отбирается из соответствующего объединенного набора.

Проведено тестирование предложенного метода на основе баз данных по разнообразным свойствам и классам соединений. Рассматривались: 1)-3) алканы с известными значениями температуры кипения t_кип., критической температуры t_кр., критического давления P_кр.; 4) сульфиды с известными значениям температуры кипения t_кип..; 5) спирты c известными значениями параметра y=-logX, где Х - растворимость соединения в воде; 6) амины с известными значениями температуры кипения t_кип.; 7) эфиры с известными значениями токсичного действия (на мышей) y=-lgC (C - концентрация вещества, вызывающая заданный биологический эффект). Для оценки качества модели в соответствии с принятыми критериями использовались коэффициент корреляции R и среднеквадратичное отклонение s для регрессии, построенной для расчетных и экспериментальных значений свойства как для обучающей, так и для контрольной выборки соединений; рассматривались также коэффициент корреляции Rcv и среднеквадратичное отклонение scv для регрессии, полученной в процедуре «скользящего контроля» (“cross-validation”) в случае отсутствия контрольной выборки. Построенные модели обладают достаточно высокой точностью и имеют хорошую прогностическую способность, что свидетельствует об эффективности предложенного метода.

...