автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Математические модели и алгоритмы в исследованиях связи между структурой и свойствами органических соединений

На правах рукописи

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

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

05 13.18 - математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

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

ии^иЬ4881

Москва-2007

003064881

Работа выполнена

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

им М В Ломоносова

(МИТХТ)

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

доктор физико-математических наук, профессор Сапоженко А А доктор физико-математических наук, профессор Чернозатонский Л А доктор химических наук, профессор Гюльмалиев А М

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

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

22

Защита состоится «3 »ОКТЯБРЯ 2007 г в «fi » час на заседании диссертационного совета Д 501 001 43 при Московском государственном университете им M В Ломоносова по адресу 119992, г Москва, ГСП-2, Ленинские горы, МГУ, факультет вычислительной математики и кибернетики, ауд 685

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

Автореферат разослан « i>cefrt#£'PJ} 2007 г

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

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

ЗахаровЕ В

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

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

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

Приведем краткую характеристику наиболее распространенного современного подхода к моделированию связи «структура-свойство» Имеется выборка соединений с известными численными значениями некоторого свойства этих соединений Структура соединений описывается при помощи набора молекулярных параметров X], ,х„ , в качестве которых используются топологические, электронные, геометрические характеристики молекул или значения каких-либо физико-химических свойств Как правило, математическая модель связи «структура-свойство» в рамках этого подхода имеет вид уравнения, связывающего численные значения исследуемого свойства у и молекулярных параметров х,, ,х„ при помощи некоторой функции/

У=№, ,х„) (1)

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

Модели связи «структура-свойство» могут иметь и другую форму, отличную от уравнения (1) Например, используются модели, определяемые заданием некоторой количественной меры молекулярного подобия пары соединений и 52,

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

Важное место в вышеуказанных исследованиях занимают способы количественного описания структуры молекул, т е выбор параметров X/, ,х„ От этого выбора значительно зависит эффективность модели Параметры X], ,х„ могут быть как экспериментальными, так и расчетными Использование расчетных параметров в моделях связи «струкгура-

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

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

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

Н

С1

Рис 1

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

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

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

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

2) Выбор функции f (или меры молекулярного подобия ф и инвариантов XI, ,х„ для описания структуры молекул в конкретной задаче Отметим, что число инвариантов графов бесконечно даже для одного, фиксированного способа взвешивания графа Как правило, большинство инвариантов, используемых в теоретической химии, получают при помощи формальных математических операций с графами, поэтому им трудно дать достаточно ясную физико-химическую или структурную интерпретацию Заранее не известно, от каких именно структурных особенностей зависит данное свойство, и каким образом Поэтому никаких четких правил выбора молекулярных параметров х1: ,х„ и аппроксимирующей функции/(или меры <1) для построения модели не существует,

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

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

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

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

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

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

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

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

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

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

3 НАУЧНАЯ НОВИЗНА И ПРАКТИЧЕСКАЯ ЗНАЧИМОСТЬ РАБОТЫ

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

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

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

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

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

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

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

определенную структурную интерпретацию Проведено тестирование предложенных методов

6) Предложены модели связи «структура-свойство» нового типа, которые отражают широко распространенный в химии постулат «близкие структуры имеют близкие свойства», позволяющие в ряде случаев оценивать свойство соединения на основе его сходства с другим соединением, для которого значение изучаемого свойства известно Эти модели имеют следующий вид \у,-у}'"с1(0„0^, где у„ у) - значения свойств г ого и ./-ого соединений, представленных графами б, и б,, а <1(0„О^ - некоторая симметричная функция двух аргументов в, и б,, значения которой количественно характеризуют степень подобия О, и О, Предложен метод оптимального подбора меры <1(0¡,0) в этом соотношении, а также способ оценки свойств соединений на основе такой модели Проведено тестирование метода, а также его сравнение с двумя другими методами, использующими другие меры подобия Это сравнение показывает, что предложенный в работе метод дает более точный результат, чем остальные методы

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

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

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

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

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

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

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

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

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

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

4. ЛИЧНЫЙ ВКЛАД АВТОРА Постановки задач, рассматриваемых в Главах 1-5, методы их решения, а также алгоритмы на графах из §6 2, §6 4 Главы 6 разработаны автором Алгоритм из §6 3 Главы 6 разработан совместно с д х н Трачом С С Теоретические результаты (определения, теоремы 1 1-1 12, 5 1-5 3) получены лично автором Тестирование предложенных методов и алгоритмов в ряде случаев выполнено автором самостоятельно, а в ряде - совместно с соавторами публикаций по теме диссертации Проведение компьютерно-статистических экспериментов по проверке гипотез о свойствах графов, описанных в §13-15, выполнено совместно с Федяевым КС В разработке компьютерных программ участвовали Баскин И И, Словохотова О Л, Федяев К С, Пасюков А В , Дозор И Н, Трач С С, Гальперн Е Г

5. АПРОБАЦИЯ РАБОТЫ Основные результаты диссертации были представлены на следующих конференциях и симпозиумах Всесоюзной конференции «Использование вычислительных машин в химических исследованиях и спектроскопии молекул» (Рига, 1986), Всесоюзной школе-семинаре по автоматизации химических исследований (Тбилиси,

1988), Межреспубликанской научно-практической конференции «Синтез, фармакология и клинические аспекты новых психотропных и сердечно-сосудистых средств» (Волгоград,

1989),VIII - ой Всесоюзной конференции «Использование вычислительных машин в

спектроскопии молекул и химических исследованиях» (Новосибирск, 1989), Межвузовских конференциях «Молекулярные графы в химических исследованиях» (Одесса, 1987, Калинин, 1990), 1-ой Всесоюзной конференции по теоретической органической химии (ВАТОХ) (Волгоград,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 Findmg and Optimization, (France, Lausanne, 1996), International Conference on Inverse and 111- Posed Problems (IIPP-96), (Russia, Moscow, 1996), International Symposium CACR - 96, (Russia, Moscow, 1996), IV-om Российском научном конгрессе «Человек и лекарство» (Москва, 1997), 1-ой, П-ой, Ш-ей, 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-om Международном симпозиуме «Компьютерное обеспечение химических исследований», (Москва, 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 foi Quantitative Structure-Activity Relationships and Molecular Design»), INTAS-00-03-63 («Virtual Computational Chemistry Laboratoiy - CCLAB»), РФФИ - №95-03-09696a («Разработка новых нейросетевых методов исследования связи между структурой и свойствами органических соединений Компьютерное конструирование и синтез соединений с заданными свойствами»), РФФИ -№ 98-03-32955а («Разработка новых методов компьютерного дизайна органических соединений с заданными свойствами на основе искусственных нейросетей Конструирование и синтез перспективных структур»), РФФИ- №96-03-33003а («Математические модели, алгоритмы и программы решения задач дизайна органических реакций»)

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

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

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

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

ГЛАВА 1 Методы построения моделей связи «структура-свойство» на основе базисных инвариантов и базисных подграфов молекулярных графов. Постановки химических задан и их теоретико-графовые формулировки. Рассматривается следующая общая проблема моделирования связи «структура-свойство» по заданной выборке органических соединений {3,} (г=1, ,к), представленных классическими структурными формулами с известными численными значениями некоторого свойства {у,}, построить уравнение вида у=/(3), связывающее значения изучаемого свойства у и структуры 5 данных соединений при помощи некоторой функции / Основная цель построения модели - оценить значения свойств у, других соединений Л'„ не включенных в исходную выборку Следовательно, на этапе применения модели возникает задача определения ее области применимости, т е выделения такого подмножества структур в некотором заданном множестве {8,} (1=к+1, свойства которых могут быть рассчитаны при помощи уравнения у=/(3) с заданной допустимой погрешностью е>0

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

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

- задача построения уравнения типа у=/(8) равносильна задаче восстановления аналитического вида некоторого инварианта графа О по набору его значений у,=/(0^ (1=1, ,к) на исходной выборке графов (возможно, с заданной погрешностью к),

- задача определения области применимости построенной модели равносильна определению условий на граф в из некоторого множества {(},} (г=к+1, ,К~), при которых значения инварианта у=/(0) на этом графе однозначно определяются по его значениям на заданных графах {О,} (1=1, ,к) (возможно, с заданной погрешностью в)

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

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

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

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

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

• Определение 1 базиса инвариантов граАоа Набор инвариантов {&} (¡=1, ,М) графов множества {О,} (1=1, назовем базисным, если любой инвариант /(О) графов этого множества однозначно представляется в виде линейной функции от них, т е м

1=1

где а] (¡=1, ,М) - некоторые константы, не зависящие от О, а зависящие только от/

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

ТЕОРЕМА 11 (необходимые и достаточные условия на набор инвариантов, при которых они образуют базис) Набор инвариантов {$,} 0=1, ,М) образует базис множества инвариантов графов {О,} (1=1, ,Ы) в смысле определения 1 тогда и только тогда, когда М=Ы и (кИЗ гдеВ=(Ьу) - матрица с элементами 1^=1, Д

ТЕОРЕМА 12 (описание множества всех базисов инвариантов) Пусть {%,} 0=1, М) - некоторый базис инвариантов графов множества {О,} (1=1, ,Ы) в смысле определения 1, А - произвольная невырожденная квадратная матрица размера .¿V Построим набор инвариантов {к} (¡=1, ,Ы) по формуле

(2)

гдeg=(gJ, ^м), к-ф,, ,кщ) - вектора -столбцы Тогда

1) Инварианты (И^ (¡=1, ,Щ также являются базисом инвариантов графов в смысле определения 1, 2) Любые два базиса к и g связаны между собой при помощи формулы (2) с некоторой невырожденной матрицей

ТЕОРЕМА 13 (о существовании базиса инвариантов, равных числам вхождения в граф определенных подграфов) Рассмотрим множество графов {С},} (1=1, Тогда инварианты равные числам вхождения подграфа Н,=0] (¡=1, ,Ы) в граф в, образуют базис инвариантов графов заданного множества

ТЕОРЕМА 14 (о существовании базиса инвариантов, часть которых постоянна на выделенном подмножестве графов) Пусть в множестве графов {О,} (1=1, ,Ы) выделено подмножество /<3,} (1=1, ,к, к<№) Тогда существует базис {/р} (р=1 ,К) инвариантов графов множества {О,} (1=1, ,Ы), такой, что его М-к+1 элемент постоянен на подмножестве /Су (г=1, ,к) При этом М-к+1 - максимальное число базисных инвариантов, обладающих вышеуказанным свойством

ТЕОРЕМА 1,5 (характеристическое свойство графов выделенного подмножества графов) Пусть в множестве графов {О,} (¡=1, ,М) выделено подмножества {(},} (¿=1, ,к,

к<М), а {/„} (р=1, ,N-/(+1) - базис инвариантов, постоянных на подмножестве графов {О^ (1=1, ,к), т е /р(0)=ср, где ср - некоторые константы, зависящие только от индекса р (р=1, ,Ы-к+1) (см теорему 1 4) Тогда не существует графа О, (г=к+1, ,Ы), такого, что /р(0,)=срф=1,

ТЕОРЕМА 16 (Об общем виде произвольного инварианта на выделенном подмножестве графов) Пусть в множестве графов {О,} (1=1, ,Ы) выделено подмножество {О)} (1=1, ,к, к<№), а инварианты §"р} (р=Ы-к+2, и константы ср (р=1, ,Ы-к+1) те же, что и в теоремах 1 4 и 1 5 Тогда на любом графе 0=0, (1-1, ,к) инвариант/представляется в виде

n

/(О) =а0+'£,а!/р(О), (ао^орс^сопй), (3)

р=№к+2 р-\1

причем коэффициенты а=(ао,ац^2, ,ап) однозначно определяются по значениям /(О)) (1=1, ,к)

ТЕОРЕМА 1 7 (необходимое и достаточное условие для восстановления значения инварианта графа по набору значений этого инварианта для других графов) Пусть в множестве графов {О,} (1=1, ,Ы) выделено подмножество {С1} (1=1, ,к, к<М) Значение инварианта/(О,) для графа (г=1, ,к) определяется по уравнению (3) тогда и только

тогда, когда инвариант/и граф О удовлетворяют условию

К-к+1

Шр(0)=Оо (4)

р=1

Следствие из теоремы 1 7

Из теоремы 1 7 следует, что для проверки возможности вычисления /(в) (в^З,, 1=1, ,к) по/¿Сг^ (1=1, ,к) необходимо знать значения ар (р=1, ,Ы-к+1) (значения^^ и а0-известны) Однако их невозможно определить по исходным данным Следовательно, без дополнительных предположений относительно инварианта / и графа Д в прит!ипе невозможно решить вышеуказанный вопрос Однако можно указать следующие достаточные условия на/и в, при которых выполнено условие (4) Предположим, что инвариант/такой, что ар=--0 при некоторых значениях р (1<р <М-к+1) (причем хотя бы для одного значения р\ а граф й из множества {в,} 0=к+1, ,Ы) такой, что ^(й)=ср для остальных значений р, 1<р<№-к+1 Легко видеть, что в этом случае выполнено условие (4)

Поставим следующий вопрос можно ли вообще не накладывать вышеуказанные ограничения на инвариант / а ввести ограничения только на граф С? Предположим, что /р(0)=ср для любого р, 1<р<М-к+1 Однако, как было доказано ранее, такого графа в вообще не существует, и эти ограничения становятся бессмысленными

ТЕОРЕМА 1 8 (обобщение теоремы 1 7) Предположим, что задана допустимая точность е>0 расчета значения инварианта/^, 0=0, (1=1, ,Ы) и для графов О-О, (1=1, ,к) получено приближенное уравнение вида

/(0)=Щ%(0)+ао' (5)

реЯ1

где 5/ -некоторое подмножество множества 8={М-к+2, ,А/ и

определено по формуле (3) Обозначим $>2={1, ,Ы-к+1} Значение /(О) для графа Ст=Ст, (1=к+1, ,Щ) вычисляется с точностью е по уравнению (5) (те //(О)-/'(й) /<е) тогда и только тогда, когда

1ща)(ар-а1')+ЩО)ар+Щ>(а)ага0'!<е. р р р

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

Сформулируем достаточные условия, при которых/^ определяется по уравнению (5) Как и в случае теоремы 1 7, предположим, что / и О таковы, что при ре8г либо ар=0, тбо /р(С)=ср

Тогда Еа/р=ао, рев2

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

1ЩО)(ар-ар')^ЩО)ар+а1Гао' (7)

81 в«!

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

ТЕОРЕМА 1 9 (аналог теоремы 1 8) Предположим, что задана допустимая точность е>0 расчета значения инварианта /(О), С=0, (1=1, ,Ы) и для графов Ст=С, (1=1, ,к) получено точное уравнение (3), а из него - приближенное уравнение путем замены некоторых инвариантов^ (р=Н-к+2, ,Ы) на их средние значения

Ър=(1/к)1?г№

1=1

на подмножестве графов в, (1=1, ,к) Обозначим 8={М-к+2, 8г={1, ,Ы-к+1}, Л -множество номеров базисных инвариантов, оставшихся в приближенном уравнении Таким образом, приближенное уравнение будет иметь следующий вид

Г(0^£а/р(0)+Ао (А0=а0+1арЪр), (8)

причем //(О,)-/'(О^ /<£ (¡=1, ,к) Значение /(О) для графа ОфОг (г=1, ,к) вычисляется с точностью е по уравнению (8) (т е !/(0)гГ(О) /<«•) тогда и только тогда, когда

(9)

реЯЧ] Р€$2

Следствие из теоремы 1 9

Сформулируем достаточные условия, при которых /((У) определяется по уравнению (8) Как и в случае следствия из теоремы 1 7, предположим, что/и О таковы, что приреЗг либо ар=0, либо /р(0)=ср Тогда 1а^р=ао,

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

1£(Ьр-ГР(0))ар1<е. (10)

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

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

1) Из теорем 11-13 следует, что для любой выборки химических структур и любого свойства всегда можно построить бесконечно много точных линейных моделей связи

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

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

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

4) Теорема 17 связана с возможностью экстраполяции найденной зависимости «структура-свойство» на новые соединения В ней даны необходимые и достаточные условия на исходную выборку соединений, на новое соединение, для которого осуществляется прогноз, на исследуемое свойство, при которых это возможно Из этих условий, в частности следует, что а) на основе исходных данных в принципе невозможно определить, принадлежит ли данный граф области применимости построенной модели, б) можно предложить достаточные условия на свойство и граф, при которых эта задача разрешима свойство не должно зависеть от некоторых структурных особенностей (что можно только предполагать и нельзя получить из исходных данных), а граф должен обладать определенным сходством с графами исходной выборки, в) чем меньше структурных факторов влияет на рассматриваемое свойство, тем меньше ограничений требуется на новые структуры и тем шире область применимости построенной модели Теоремы 18, 19 обобщают теорему 17 на случай, когда вычисление значений рассматриваемого свойства допускается с определенной погрешностью е, а для вычислений используется приближенное уравнение Таким образом, теоремы 14-19, могут служить основой для разработки новых, математически обоснованных методов определения областей применимости моделей связи «структура-свойство»

Метод построения моделей связи «структура-свойство» и его тестирование. На основании полученных теоретических результатов предложен общий алгоритмизированный метод №1 построения приближенной модели связи «структура-свойство» по набору N

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

Проведено тестирование предложенного метода на основе баз данных по разнообразным свойствам и классам соединений Рассматривались 1)-3) алканы с известными значениями температуры кипения tKU„, критической температуры tm, критического давления Ркр , 4) сульфиды с известными значениям температуры кипения ?,„„ , 5) спирты с известными значениями параметра y^-logX, где X - растворимость соединения в воде, 6) амины с известными значениями температуры кипения tm„ , 7) эфиры с известными значениями токсичного действия (на мышей) y~lgC (С - концентрация вещества, вызывающая заданный биологический эффект) Для оценки качества модели в соответствии с принятыми критериями использовались коэффициент корреляции Я и среднеквадратичное отклонение s для регрессии, построенной для расчетных и экспериментальных значений свойства как для обучающей, так и для контрольной выборки соединений, рассматривались также коэффициент корреляции Rev и среднеквадратичное отклонение Scv для регрессии, полученной в процедуре «скользящего контроля» ("cross-validation") в случае отсутствия контрольной выборки Построенные модели обладают достаточно высокой точностью и имеют хорошую прогностическую способность, что свидетельствует об эффективности предложенного метода

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

Назовем набор инвариантов {g,} (i "l,2, ) меченых графов некоторого множества {GJ (i—1,2, , ОифО,2, 11фг2) базисным, если 1) для любых графов G,j и G,2 и (г1фг2) из этого множества вектора g(Ga)=(gi(G,0,gi(Gu), ) и g(Ga)=(g,(Gl2),g2(Gl2), ) различны, 2) любой инвариант f(G) графов любого конечного подмножества графов исходного множества {G,} (i=l,2, ) может быть представлен в виде некоторой функции h от gh g2, , те f(G)=h(gi(G),g2(G), ), причем h не зависит от G, а зависит от инварианта/и выбранного подмножества графов

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

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

Для построения первого набора инвариантов рассматриваются все графы Ft с к>1 вершинами, состоящие из объединения нескольких несвязных компонент, каждая из

которых является либо цепью, либо циклом, или циклом, к некоторым вершинам которого присоединено еще по одной вершине В случае к=1 граф Fj состоит из одной вершины Все такие графы для одного фиксированного к нумеруются произвольным образом и обозначаются через (т=1,2, ) На рис 2 приведены все такие графы при к=5 Пусть хк:Ш - инвариант, равный числу вхождения в некоторый граф G подграфа F^m

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

Мк m J ~ , / >

VV1V2 V»,

где суммирование проводится по всем компонентам связности и, - число вершин в г -ой компоненте, vp (р=1,2, ) - степени вершин F^j в G Инвариант щт определяется так

j

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

Рис 2 Все графы при к=5

ТЕОРЕМА 1 10. Набор инвариантов является базисным (в смысле определения 2) для множества графов {О,} (1=1,2, ,), состоящего из графов типаТ^« Аналогичные результаты получены и для набора {<Рк.т}

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

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

Метод построения моделей связи «структура-свойство» и его тестирование Предложен общий алгоритмизированный метод Ж«2 построения моделей связи «структура-свойство», основанный на введенных выше инвариантах {щ,т} Согласно этому

методу, для данной выборки молекулярных графов строятся все возможные инварианты {<Рк,т}, а также их квадраты и попарные произведения, и затем из этого набора параметров отбирается небольшое число параметров, дающих удовлетворительную линейную модель

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

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

Назовем семейство инвариантов {Zi(aj), Z2(aa), } произвольного набора графов {GJ, зависящих от параметров alt а2, , базисным, если для любого инварианта f любой выборки графов {Gi, ,Gn} найдется TV инвариантов Zji(ccj), , ZjN(aц) из этого множества, и N чисел №, ая\ таких, что рассматриваемый инвариант / однозначно представляется в виде линейной комбинации Zt(at'), ,Zx(a?/')

n

f=YfiiZJi(al') ¡=i

Далее введено семейство инвариантов {щт(а)=<рк^па (к,т>1), y/0i0(a)=na}, где и -число вершин графа G, о=а(к,т)>0 - произвольный параметр, который для каждой пары (к,т) может принимать любые значения Это семейство инвариантов является обобщением рассмотренного ранее набора инвариантов }

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

ТЕОРЕМА 111 Инварианты {щм(а)} являются базисными в смысле определения 5 для любого множества графов {G,}, i=l, ,N, удовлетворяющего одному из следующих условий а) все графы данного множества имеют различное число вершин пь п2, , nN, б) каждый граф из данного множества является графом типа Fu,m при некоторых (к,т)

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

Метод построения моделей связи «структура-свойство» и его тестирование Разработан общий алгоритмизированный метод ЖеЗ построения моделей связи «структура-свойство» Метод заключается в следующем 1) задается конечный набор М значений параметра a. at=0, а2, ,ам с фиксированным значением шага h и заданным максимальным значением ом, 2) строятся инварианты (щш(а)} для всех фрагментах которые присутствуют в заданном множестве структур, при всех выбранных значениях параметра а, 3) из этого множества инвариантов отбираются наилучшие для построения линейной модели Если полученный результат является неудовлетворительным (по каким-либо критериям), то процедура повторяется для других значений а^или h

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

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

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

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

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

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

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

Проведено тестирование предложенного метода на основе баз данных по биологической активности разнообразных классов соединений, а также его сравнение с

другими методами моделирования связи «структура-свойство» на используемых данных Рассматривались 1) галоидпроизводные метана и этана с известными значениями их наркотической активности InADw (AI)50 - концентрация вещества, вызывающая анестезию у половины подопытных животных), 2) нитробензолы и нитротолуолы с известными значениями мутагенной активности ln/.i (на Salmonella typhirmmum, ц - количество ревертантов на наномоль), 3) хлорзамещенные анилины с известными значениями токсичности logECsoгде ЕС ¡о - концентрация вещества, вызывающая уменьшение интенсивности люминесценции в 2 раза у морских бактерий Photobacterium phosphoreum Построенные модели обладают достаточно высокой точностью, что свидетельствует об эффективности предложенного метода

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Проведено тестирование предлагаемого подхода для построения корреляций «структура-свойство» для физико-химических свойств и биологической активности органических соединений различных классов Рассматривались 1)-5) энтальпия образования, температура кипения, критическая температура, критическое давление, 30-индекс Винера ъ\¥

алканов С2-С8, б)-7) ингибирование микросомального пара-гидроксилирования анилина цигохромом Р450 (степень ингибирования характеризуется величиной р1С50~-/^1Сю , где 1С50 - концентрация вещества, приводящая к 50% ингибированию гидроксилирования анилина), а также температура кипения ¡т„ алифатических спиртов, 8), 9) параметр гидрофобности 1о%Р (Р - коэффициент распределения соединения между водой и н-октанолом), а также токсичность, характеризуемая величиной 1о%ЕС-м' (ЕС ¡а ~ концентрация вещества, вызывающая 50% уменьшение биолюминисценции морских бактерий РЬо1оЪас1егшт рИоврИогеит в течение 30 мин) хлорзамещенных фенолов Полученные результаты свидетельствуют об эффективности предложенного подхода

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

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

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

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

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

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

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

у=а]Х1+ +ал,

в которой параметры аь ,аи определяются по исходной выборке к соединений методом наименьших квадратов, а хи ,хт - любые молекулярные параметры Пусть Ур^ч - величина свойства, рассчитанная по вышеприведенному уравнению, у - экспериментальное значение свойства, М — множество, структуры которого требуется разделить на два класса принадлежащие и не принадлежащие ТОП соответствующего уравнения Согласно определению, РОЛ вышеприведенного уравнения состоит из тех соединений, для которых А'-Урасч!^ Так как невозможно учесть все факторы, влияющие на заданное свойство, его экспериментальное значение у можно рассматривать как случайную величину Следовательно, выполнение условия ¿у-урас,/<ё представляет собой случайное событие, и можно рассмотреть его вероятность Р(/у-урасч!<е) Будем считать, что ТОП состоит из тех соединений, для которых Р(/у-урасч1<к) >а,:р, где ОгР - некоторое пороговое (критическое) значение этой вероятности Основная идея предложенного метода заключается в определении порога а,:р по заданному значению с, и дальнейшей оценке вероятности Рф-Урасч/^е) Для тестируемого соединения Подход базируется на ряде гипотез, в частности, на предположении о том, что некоторые случайные величины, связанные с изучаемым свойством, распределены по нормальному закону Критерий принадлежности некоторого соединения ТОП построенной модели заключается в выполнении для тестируемого соединения некоторого числового неравенства Для его проверки необходимо знание значений параметров хь ,хт для тестируемого соединения и для соединений исходной выборки, значений свойств соединений исходной выборки, чисел а^, и е, а также значения ЦсЦф, к'Щ)- квантили уровня а^ распределения Стьюдента с к-т степенями свободы

Проведено тестирование предложенного метода При этом проверялись степень совпадения ТОП и ТОП, степень сокращения доли ошибочных предсказаний и доля «пропущенных» соединений при использовании ТОП В качестве множества М рассматривалось множество всех алканов С2-С8 (39 соединений) с известными значениями температуры кипения Обучающая выборка состояла из к=12 соединений этого класса По этим данным было построено линейное уравнение связи «структура-свойство», содержащее такие параметры как Ьг(%+1), где х ~ индекс Рандича, и п - число атомов углерода в молекуле Рассматривался ряд значений е (0<е^5(°С)), и для этих значений определялось качество предложенного метода Проведенные исследования показали, что описанный выше метод позволяет в 94-97% случаев отбросить соединения, не принадлежащие РОЛ, и в 8085% случаев верно определить, принадлежит ли РОП данное соединение Если проводить прогнозирование свойств всех соединений исходного множества, не выделяя ТОП, то доля верных предсказаний составляет 90%, если прогнозирование проводить только внутри ТОП, то доля верных предсказаний - 97%, доля «пропущенных» соединений -13%

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

Метод определения ОП на основе базисных инвариантов Предложен метод определения ТОП модели связи «структура-свойство» специального вида на основе

базисных инвариантов (в смысле определения 1), рассмотренных в Главе 1, и ряда соответствующих теоретических результатов

Рассматриваемые модели связи «структура-свойство» строятся следующим образом Пусть задано множество соединений, представленных графами {О,} (1=1, ,КТ), и выборка соединений из них {О,} (1=1, ,к) с известными значениям некоторого свойства {у,} (1=1, ,к) Пусть 0=1, ,ЛУ - базис инвариантов графов исходного множества, такой, что Ы-к+1 его элементов с номерами к, постоянны на графах {С}^ (1—1, ,к), те /р(в()=Ср , 1=1, ,к Предположим, что по исходным данным сначала построено точное уравнение связи «структура-свойство» следующего вида

ы

у=Щ/р(С)+ ао.

р=1

Пусть из него получено приближенное уравнение (с заданной погрешностью с) путем замены некоторых инвариантов /р (например, с номерами р=т+1, ,к-1) на константы Ър, равные их средним на выборке значениям

т к-1

у=1а1/р(0)+Ао (Ао=ао+2арЬр,)

Р=1 Р=т+1

В Главе 1 были даны некоторые достаточные условия на рассматриваемое свойство и молекулярный граф О (т е химическую структуру), при которых значение свойства этой структуры определяется по вышеуказанному уравнению с точностью в (см Теорему 1 9 и следствие из нее) Первое из них - это независимость рассматриваемого свойства для соединений исходного множества от некоторых базисных инвариантов / с номерами р=к, ,Ы (что можно только предполагать и нельзя получить из исходных данных) Второе условие - это выполнение для графа в равенств вида /р(0)=ср для остальных номеров р=к, ,Ы Третье условие - это выполнение следующего неравенства

Из этих условий следует, что число Ь/ ограничений типа равенств на структуры графов из ТОП связаны с числом 12 гипотез о независимости свойства от некоторых базисных параметров так Ь1\Ь2^,-к-\-1 Таким образом, чем меньше факторов влияет на величину данного свойства, тем меньше структурных ограничений надо вводить на графы из ТОП

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

Проведено тестирование предложенного метода Проверялись степень совпадения ЮП и ТОП, степень сокращения доли ошибочных предсказаний и доля «пропущенных» соединений при использовании ТОП Рассмотрено множество всех алканов С2-С7 (N=21), с известными значениями температуры кипения у В качестве обучающей выборки использовано множество всех алканов С2-С} (к=7'), а ь~5(}С.) Выдвигаемые гипотезы основаны на представлении о том, что температура кипения зависит, в основном, от размера и степени разветвленности молекул, а числа вхождения в граф некоторых специальных подграфов могут служить количественной мерой этих структурных особенностей Проведенные исследования показали, что при классификации исходных

соединений на «принадлежащие/не принадлежащие» РОП при помощи ТОП была сделана лишь одна ошибка, те правильная классификация соединений была проведена в 95% случаев Если проводить прогноз свойств всех соединений исходного множества, не выделяя ТОП, то доля верных прогнозов составляет 43%, если прогнозирование проводить внутри ТОП, то доля верных прогнозов - 100%, доля «пропущенных» соединений -5%

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

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

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

У=Дх1,

где у - значение рассматриваемого свойства, х1: ,хк - какие-либо молекулярные параметры, / - некоторая функция Если в качестве параметров х]: ,хм использованы инварианты соответствующих молекулярных графов, то ОЗ сводится к исчерпывающей генерации молекулярных графов по заданному значению их инварианта, задаваемому выражением вида

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

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

Типы рассмотренных базовых моделей связи «структура-свойство» Рассматриваются модели связи «структура-свойство» следующих видов 1) а) Уравнение содержит только один молекулярный параметр Х- называемый

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

X=Z(vtv/'/2

(v, и Vj - степени вершин г uj, суммирование проводится по всем ребрам (ij) молекулярного графам Предполагается, что х может бьпъ выражен однозначно из этого уравнения, рассматривается как случай произвольных графов так и случай молекулярных графов, соответствующих ката-конденсированным бензоидным углеводородам, б) корреляционное уравнение, наряду с индексом / содержит и ряд других целочисленных параметров, ограниченных на рассматриваемом классе графов

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

1Г=1хЛ

(4j - расстояние между вершинами г и j, суммирование проводится по всем парам вершин (ij), KJ )

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

1к=п(п-1)2/'Р2,2к= (п-1) (П-2//Р2, 3к=(п-3)(п-2)2/3Р2 (для четного п>3),3к=(п-1)(п-3)2/'Р2 (для нечетного п>3)

Индекс °к определяется по формуле °K=-n£(n/n)log2(n/n), где п, число топологически эквивалентных вершин в г - ом классе эквивалентности Разбиение вершин на классы происходит по каким-либо их топологическим характеристикам, причем самое «мелкое» разбиение соответствует орбитам группы симметрии графа

4) Уравнение содержит индексы 'к (г=0,1,2,3), а также их обобщения 'ка (1=1,2,3), разработанные для учета гетероатомов и кратных связей в молекуле Они вычисляются аналогично 'к (,1=1,2,3'), но в вышеприведенных формулах вместо п используется величина п+а, а вместо 'Р - величина 1Р+а при некотором параметре а, вычисляемом по взвешенному графу Для вычисления а атомы молекулы классифицируют по химическим символам атомов и распределениям типов связей, для атома каждого типа определенным способом вычисляют параметр а,, зависящий от ковалентного радиуса атома, затем а вычисляют по формуле a=Za.j.

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

Предположим, что химические соединения представлены в виде классических структурных формул, т е в виде вершинно - и реберно-меченых графов Пусть атомы в молекуле разбиты на классы эквивалентности по окрестностям ¿-ого порядка (к>0)

Информационными топологическими индексами, соответствующими такой классификации атомов, являются следующие инварианты

ICt=-l' n/njogrfi/rit (Information Content), SlC^lC^/log^n (Structural Information Content), CICt=log2n (Complement Information Content), BICk=ICt/log2q (Boundary Information Content), TlC]i=nlCt (TotalInformation Content), (q общее число связей в молекуле)

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

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

^ -

к=О

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

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

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

Рассмотрим следующий пример решения 03 По базе данных, содержащих предельные спирты {N=50) с известными значениями физико-химического свойства -к^Х (X - растворимость спиртов в воде (в мольных долях)), построено уравнение вида

-1о%Х=-0 8+1186Ы (Я=0 976, 6=0 21) Поставим задачу найти все соединения этого класса, для которых 2 6<-к^<3 0 Построено 20 структур, изображенных на рис 4 Для соединений №№ 1-11 значения свойства известны При этом для 9 структур экспериментальные значения свойства действительно лежат в заданном интервале, для 2 структур - незначительно выходят за пределы интервала (для №3 - 2 542, для №8 - 2 588) Для соединений №№ 12-20 экспериментальные значения рассматриваемого свойства неизвестны

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

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

1) иметь базу данных, содержащую структуры соединений ® и значения их свойств, 2) выбрать способ математического описания структуры молекул, при котором структуре 5 соответствует объект М, 3) на множестве выбранных математических объектов {М} задать количественную меру подобия этих объектов с1(М1,М2)>0

ОН

■ОН

он

он

он

10

он 7

он

11

он

12

13

ОН

14

^ОН

он

15

ОН

17

18

он

19

он

Рис 4

Для прогнозирования свойства у о соединения во в рамках этого подхода используются различные методы, суть которых заключается в следующем 1) для Бо следует найти соединение «ближайшее» к нему в базе данных (или несколько «ближайших») и положить у0=у (или уо равно среднему арифметическому свойств «ближайших» соединений) Метод такого типа целесообразно использовать, в частности, тогда, когда исходная база данных очень разнородна по своему составу, и не удается построить удовлетворительную модель вида у=/(3) Однако разбиение базы на части структурно-близких соединений приводит к малоинформативным выборкам небольшого размера

Следует отметить, что меры подобия, обычно используемые для прогнозирования свойств в рамках этого подхода, зависят лишь от структур сравниваемых соединений и не зависят ни от исходной выборки, ни от рассматриваемого свойства Имеются примеры,

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

Общая аналитическая Формула для произвольной меры подобия молекулярных графов Выведена общая аналитическая формула для произвольной симметричной меры подобия d(Gh Gij, заданной на произвольном множестве графов {GJ, i=l, ,N Доказана теорема, соласно которой существует единственная симметричная квадратная матрица М=(щ) (ij=l, ,N-1) такая, что мера c/fGfoG/J представляется в следующем виде

d(GhG^M(f^ (Ш

где fk=(fi(Gij, ,fbr-i(Gi,)), ft=(fi(Gi), ,/n-i (Gf)) - векгора-столбцы, компоненты которых - это значения некоторых базисных инвариантов исходного множества графов (в смысле определения 1, рассмотренного в Главе 1) на графах G* и G/, соответственно, Mfftrft) -произведение М и ft-fi, символ « » обозначает скалярное произведение соответствующих векторов

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

Метод построения моделей связи «структура - свойство», основанный на оптимальном подборе меры подобия Предложен метод построения моделей связи «структура-свойство» и прогнозирования свойств химических соединений, основанный на приведенных выше теоретических результатах Для разработки этого метода используется аппроксимация вышеуказанной точной формулы для меры подобия Предполагается, что структура соединений исходной выборки описана при помощи некоторых векторов X длины k<N-l, мера подобия d(G„ Gj задается формулой, аналогичной вышеуказанной формуле d(G„Gj) =M(X!!>Sfn) (Х^гХР), где матрицам с неопределенными элементами имеет порядок к. Элементы матрицы М подбираются так, чтобы \yi-y]\=d(Gl,G), ij=l, ,N, i>j В предлагаемом подходе мера подобия подбирается некоторым оптимальным образом по исходным данным Заключительный этап - прогнозирование свойства уо нового соединения Go - тоже изменен Вместо метода т «ближайших соседей» (где всегда остается вопрос о выборе числа т) предлагается другой подход, в котором для вычисления у0 используются все исходные данные Однако для прогнозирования свойств может быть использован и метод «ближайших соседей»

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

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

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

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

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

Для проведения теоретического исследования справедливости этого угвервдения рассмотрен общий случай, когда химические структуры представлены в виде некоторых математических объектов М, (i=l, ,N), и на множестве этих объектов задана некоторая симметричная функция d(M„Mj) - мера подобия этих объектов Предполагается, что сКМгМ^О тогда и только тогда, когда M,=Mj Пусть заданы числа у, ,N) - значения

некоторого свойства соответствующих соединений Естественно считать мерой близости свойств величину \угу} Предположим, что заранее указаны численные критерии подобия свойств и структур, т е такие числа ё>0 и о>0, что если d(M„Mj)<$, то структуры М„ Mj считаются «близкими», и если \yr-yj\<S, то значения свойств считаются «близкими» Очевидно, что число е задается исследователем и зависит от конкретной задачи, а варьируемыми характеристиками являются d(M„MJ и S Вышеуказанный постулат в этом случае можно сформулировать так если для любых структур М, -и Mj dlM^Mj)^, то \у,-у}¡<е Легко ввдеть, что это утверждение является аналогом определения равномерной непрерывности функции/^ одной переменной на заданном числовом промежутке X

Приведенная формулировка этого постулата позволяет провести теоретическое исследование его справедливости в общем виде Предполагается, что мера подобия такова, что d(Mi,Mj)=0 тогда и только тогда, когда hh—Mj. Доказано, что для любой выборки структур, представленных в виде некоторых математических объектов М, (i=l, -,N), любого свойства у, любой меры подобия d(G„Gj) верны следующие оценки

а d(M„Mj)<\yry№ d(MI:Mj), где а и Ь - константы, зависящие от меры, свойства, и выборки структур Этот результат сформулирован в виде теоремы

Из полученного результата сделан ряд выводов 1) Постулат будет всегда справедливым, если выбрать З=е/Ь, 2) Предположим, что для данной выборки не все значения свойств близки, т е найдется пара М, и М,, что \yryy, >£ Тогда, если д=тахс1(М1,М^, то постулат не будет справедлив на данной выборке, 3) Если выбрать в очень большим, то постулат будет справедлив при любых 6 и 4) Из полученных неравенств следует

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

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

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

Разработаны следующие алгоритмы на графах. 1) поиска канонической нумерации вершин взвешенного графа и его группы автоморфизмов, основанного на использовании ряда спектральных характеристик графа (даны примеры реализации алгоритма и некоторые результаты его тестирования на быстродействие при программной реализации), 2) установления изоморфизма графов О] и и поиска группы симметрии А иЮ графа б (приведены некоторые результаты тестирования алгоритма на быстродействие при его программной реализации), 3) поиска всех подграфов, изоморфных заданному подграфу, в произвольно взвешенном графе (прилагается акт о внедрении соответствующей компьютерной программы в ИОХФ им А Е Арбузова в исследования по планированию органического синтеза)

ф * *

ВЫВОДЫ

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

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

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

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

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

6) Предложены модели связи «структура-свойство» нового типа, отражающие широко распространенный в химии постулат «близкие структуры имеют близкие свойства» Эти модели имеют следующий вцц \у,-у) =<1(0,, ОД где у„ yJ - численные значения свойств г-ого и 7-ого соединений, представ ленных графами в, и О,, а Ы(С„ О) - некоторая симметричная функция двух аргументов О, и О,, значения которой количественно характеризуют степень подобия О, и О, Предложен метод оптимального подбора меры подобия <1(0„О^ в этом соотношении, а также способ оценки свойств соединений на основе такой модели Проведено тестирование этого метода, а также его сравнение с двумя другими методами, использующими другие меры подобия

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

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

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

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

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

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

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

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

1 Зефиров Н С, Трач С С, Станкевич (Скворцова) М И Алгоритм установления изоморфизма молекулярных графов // Тезисы докладов Всесоюзной конференции «Использование вычислительных машин в химических исследованиях и спектроскопии молекул», Рига, 1986, с 190-192

2 Станкевич (Скворцова) М И, Баскин И И, Зефиров Н С Автоматизированный поиск структурных фрагментов Алгоритм и программа // Журнал структурной химии, 1987, т28, №6, с 136-137

3 Станкевич (Скворцова) М И, Баскин И И, Зефиров Н С Комбинаторные модели и алгоритмы в химии Поиск структурных фрагментов // Деп ВИНИТИ АН СССР 11 06 1986, № 4288-В86, 27 стр

4. Станкевич (Скворцова) М И, Станкевич И В , Зефиров Н С Топологические индексы в органической химии // Успехи химии, 1988, т 57, № 3, с 337-366

5. Девдариани Р О, Станкевич (Скворцова) М И, Палюлин В А, Зефиров Н С Оценка с помощью ЭВМ температур плавления для некоторых классов органических соединений // Тезисы докладов Всесоюзной школы-семинара по автоматизации химических исследований, Тбилиси, 1988, с 39

6. Баскин И И , Станкевич (Скворцова) М И , Девдариани Р О , Зефиров Н С Комплекс программ для нахождения корреляций «структура - свойство» на основе топологических индексов // Журнал структурной химии, 1989, т 30, X» 6, с 145-147

7 Гордеева Е В, Баскин И И , Девдариани Р О, Зефиров Н С , Станкевич (Скворцова) М И Методология решения обратной задачи в проблеме связи «структура-свойство» для случая топологических индексов // ДАН СССР, 1989, т 307, № 3, с 613-616

8. Станкевич (Скворцова) М И , Баскин И И, Зефиров Н С, Гордеева Е В , Палюлин В А, Девдариани Р О О проблеме восстановления химических структур по заданным значениям топологических индексов // Тезисы докладов межреспубликанской научно-практической конференции «Синтез, фармакология и клинические аспекты новых психотропных и сердечно-сосудистых средств», Волгоград, 1989, С 28

9. Зефиров Н С, Скворцова М И, Станкевич И В, Томилин О Б Об одном способе нумерации вершин молекулярных графов // Тезисы докладов VIII-ой Всесоюзной конференции «Использование вычислительных машин в спектроскопии молекул и химических исследованиях», Новосибирск, 1989, с 176-177

10 Скворцова М И, Баскин И И , Девдариани Р О, Палюлин В А, Зефиров НС О проблеме генерации структур органических соединений с заданными свойствами // Тезисы

докладов VIII-ой Всесоюзной конференции «Использование вычислительных машин в спектроскопии молекул и химических исследованиях», Новосибирск, 1989, с 250

11 Девдариани Р О, Палюлин В А, Скворцова М И, Баскин И И, Зефиров Н С Прогнозирование температур плавления ароматических соединений некоторых классов на основе использования взвешенных топологических индексов // Тезисы докладов VIII-ой Всесоюзной конференции «Использование вычислительных машин в спектроскопии молекул и химических исследованиях», Новосибирск, 1989, с 251

12 Зефиров Н С, Скворцова М И, Станкевич И В Генерация структур поликонденсированных бензоидных углеводородов по индексу Рандича // Тезисы докладов VIII-ой Всесоюзной конференции «Использование вычислительных машин в спектроскопии молекул и химических исследованиях», Новосибирск, 1989, с 252-253

13 Stankevitch (Skvortsova) М I, Tratch S S, Zefirov N S Combinatorial Models and Algonthms m Chemistry Search for Isomorphisms and Automorphisms of Molecular Graphs // J Comput Chem ,1988, v 9, N 4, p 303-314

14 Скворцова M И, Станкевич И В Зефиров Н С Топологические свойства ката-конденсированных бензоидных углеводородов индекс Рандича и его связь с химическим строением // Тезисы докладов Межвузовской конференции «Молекулярные графы в химических исследованиях», Калинин, 1990, с 84

15 Скворцова М И, Станкевич И В, Томилин О Б, Зефиров Н С Проекционные операторы и каноническая нумерация вершин молекулярных графов // Тезисы докладов Межвузовской конференции «Молекулярные графы в химических исследованиях», Калинин, 1990, с 85-86

16 Скворцова М И , Словохотова О JI, Палюлин В А, Зефиров Н С Решение обратной задачи в проблеме связи «структура-свойство» для топологических индексов, характеризующих молекулярную форму // Тезисы докладов 1-ой Всесоюзной конференции по теоретической органической химии (ВАТОХ), Волгоград, 1991, с 551

17 Станкевич И В , Скворцова М И Обобщенный индекс Рандича как функционал от я -электронной плотности // Тезисы докладов 1-ой Всесоюзной конференции по теоретической органической химии (ВАТОХ), Волгоград, 1991, с 97

18 Скворцова М И, Станкевич И В , Зефиров И С Генерация молекулярных структур поликонденсированных бензоидных углеводородов по индексу Рандича // Журнал структурной химии, 1992, т 33, № 3, с 99-104

19 Станкевич И В, Скворцова М И, Томилин О Б, Зефиров Н С Использование проекционных операторов для нумерации атомов и исследования свойств симметрии молекулярных структур // Журнал структурной химии, 1992, т 33, № 3, с 93-98

20 Скворцова М И, Баскин И И, Словохотова О JI, Палюлин В А, Зефиров Н С Обратная задача в QSAR/QSPR-анализе для случая топологических индексов, характеризующих молекулярную форму (индексов Кира) // ДАН, 1992, т 324, № 2, с 344-348

21. Станкевич И В , Скворцова М И, Зефиров Н С Топологические свойства сопряженных углеводородов обобщенный индекс Рандича как функционал от к-электронной плотности // ДАН, 1992, т 324, № 1, с 133-137

22 Skvortsova М I, Bastan I I, Slovokhotova О L, Palyuhn V А, Zefirov N S The Inverse Problem in QSAR/QSPR Studies for the Case of Topological Indices Characterizing Molecular Shape (Kier Indices) // J Chem Inform Comput Sei, 1993, v 33, N 4, p 630-634 23. Stankevich I V, Galpern E G, Chistyakov A L, Bastan I I Skvortsova M I, Zefirov N S , Tomilm О В Spectral Theory of Graphs in Chemistry 1 Projection Operators and Canonical Numeration of Graph Vertices// J Chem Inform Comput Sei 1994, v 34,N5,p 1105-1108

24. Скворцова М И, Баскин И И, Словохотова О JI, Зефиров Н С Методология построения общей модели связи «структура-свойство» на топологическом уровне // ДАН, 1994, т 336, N4, с 496-499

25 Баскин И И , Скворцова М И , Станкевич И В , Зефиров Н С О базисе инвариантов помеченных молекулярных графов // ДАН, 1994, т 339, N 3, с 346-350 26. Stankevich I V, Skvortsova М I, Kolmykov V А, Subbotm V F, Mnukhin V В Spectral Graph Theory in Chemistry // In Mathematical Methods in Contemporary Chemistry (Ed Kuchanov S I, Gordon and Breath Publishers, Amsterdam), 1996, p 101-141

27 Skvortsova M I, Baskm I I, Palyulin V A, Slovokhotova О L, Zefirov N S Structural Design Inverse Problems for Topological Indices m QSAR/QSPR Studies // In AIP Conference Proceedings 330, E С С С 1, Computational Chemistry, F E С S Conference, Nancy, France, May

1994, Eds F Bernardy, J-L Rivail, p 486-499

28 Baskin I I, Skvortsova M I, Stankevich I V, Zefirov N S On the Basis of Invariants of Labeled Molecular Graphs //J Chem Inform Comput Sci, 1995, v 35, N 3, p 527-531

29 Stankevich I V, Skvortsova M I, Zefirov N S On a Quantum-Chemical Interpretation of Molecular Connectivity Indices for Conjugated Hydrocarbons // J Mol Strut (THEOCHEM),

1995, v 342, p 173-179

30. Zefirov N S , Palyulin V A, Skvortsova M I, Baskin I I Inverse Problem m QSAR // In QSAR and Molecular Modeling Concepts, Computational Tools and Biological Applications, Barcelona, Prous Science Publishers, 1995 p 40

31 Скворцова M И, Баскин И И, Словохотова О JI, Палюлин В А, Зефиров Н С Обратная задача в проблеме связи «структура-свойство» для случая корреляционного уравнения, содержащего произвольные топологические дескрипторы // ДАН, 1996, т 346, N 4, с 497-500

32 Skvortsova М I, Stankevich I V, Baskin I I, Palyulin V A, Zefirov N S Analytical Description of a Set of Similarity Measures Defined on Molecular Graphs // In Proceedmgs of the 11th European Symposium on Quantitative Structure-Activity Relationships Computer-Assisted Lead Finding and Jptimization, Lausanne, September 1-6,1996, p 13 В

33 Skvortsova M I, Baskin I I, Slovokchotova О L, Palyulin V A, Zefirov N S Inverse Problems in Quantitative Structure-Property Relationships Studies Molecular Graph Reconstruction Using Graph Invariants // In Proceedings of International Conference on Inverse and Ill-Posed Problems (IIPP-96), September 9-14, 1996, Moscow, Russia, p 169

34 Baskin I I, Skvortsova M I, Stankevich I V, Zefirov N S The Basis of Invariants of Labeled Molecular Graphs and Its Applications to Molecular Properties Prediction // In Book of Abstracts International Symposium CACR-96, December 17-18, 1996, Moscow, Russia, p 39

35 Skvortsova M I, Baskm I I, Stankevich I V, Zefirov N S New Method for Constructing Linear "Structure-Property" Equations // In Book of Abstracts International Symposium CACR-96, December 17-18,1996, Moscow, Russia, p 60

36. Skvortsova M I, Baskm I I, Stankevich I V, Palyulin V A, Zefirov N S Molecular Similarity in Structure-Property Relationships Studies Analitical Description of the Complete Set of Graph Similanty Measures // In Book of Abstracts, International Symposium CACR-96, December 17-18, 1996, Moscow, Russia, p 67

37 Skvortsova MI, Baskm 11, Stankevich IV, Zefirov N S A New Approach to to the Problem of Defining Applicability Range of QSAR/QSPR Models // In Book of Abstracts International Symposium CACR-96, December 17-18, 1996, Moscow, Russia, p 67-68

38 Baskm I I, Skvortsova M I, Palyulin V A, Zefirov N S Quantitative Chemical Structure-Property/Activity Studies Using Artifical Neural Networks // Foundations of Computing and Decision Sciences 1997, v 22, N 2, p 107-116

39 Скворцова М И, Баскин И И, Станкевич И В , Зефиров Н С Об одном способе построения линейных уравнений связи «структура-свойство» // ДАН, 1996, т351, № 1, с 7880

40 Скворцова М И, Станкевич И В, Баскин И И, Палюлин В А, Зефиров Н С Аналитическое описание множества мер подобия молекулярных графов // ДАН, 1996, т 350, № б, с 786-788

41 Зефиров Н С, Палюлин В В, Молчанова М С, Скворцова М И, Баскин И И Структурная генерация и QSAR // Тезисы докладов IV - ого Российского научного конгресса «Человек и лекарство», Москва, 8-12 апреля 1997г , с 261

42 Скворцова М И, Словохотова О JI, Баскин И И, Палюлин В А, Зефиров Н С Обратная задача в проблеме связи «структура-свойство» для случая информационных топологических индексов // ДАН, 1997, т 357, № 1, с 72-74

43 Skvortsova М I, Baskin I I, Stankevich I V, Palyulm V A, Zefirov N S Molecular Similarity 1 Analitycal Description of Graph Similarity Measures // J Chem Inform Comput Sci 1998, v 38, N 5, p 785-790

44 Skvortsova M I, Baskin I I, Skvortsov L A, Palyulin V A, Zefirov N S , Stankevich I V Chemical Graphs and Their Basis Invariants//J Mol Struct (THEOHEM), 1999, v 466, p 211-217

45 Скворцова M И, Баскин И И, Станкевич И В, Палюлин В А, Зефиров Н С Новый метод прогнозирования свойств химических соединений на основе оптимизации меры молекулярного подобия//Тезисы докладов 1-ой Всероссийской конференции «Молекулярное моделирование», 14-16 апреля 1998г, (РАН, отделение общей и технической химии, Институт геохимии и аналитической химии им В И Вернадского, Москва, 1998), С 66

46. Скворцова М И, Баскин И И, Словохотова О JI, Палюлин В А, Зефиров Н С Обратная задача в проблеме связи «структура-свойство» для случая топологических индексов // Тезисы докладов 1-ой Всероссийской конференции «Молекулярное моделирование», 14-16 апреля 1998г, (РАН, отделение общей и технической химии, Институт геохимии и аналитической химии им В И Вернадского, Москва, 1998), С 67 47 Станкевич И В , Чистяков A JI, Скворцова М И Исследование структуры и свойств некоторых эндоэндральных кластеров и обобщение понятия молекулярной топологической формы // Известия РАН, сер химическая, 1999, № 3, с 436-440

48. Скворцова М И, Станкевич И В Теория графов в структурной химии Молекулярные графы Часта I - Изд-во МИТХТ - 1998 - 88 с

49 Artemenko N V, Baskin I I, Halberstam N M, Skvortsova M I, Palyulin V A, Zefirov N S Combmation of Substructural Approach and Neural Networks as a Universal Tool for Predicting Physico-Chemical Properties of Organic Compounds // In Book of Abstracts "QSAR 2000 Crosroads to the XXI Century Ninth International Workshop on Quantitative Structure-Activity Relationships in Environmental Sciences» September 16-20, 2000, Bourgas, Bulgaria, p 66-67

50 Скворцова M И , Федяев К С, Палюлин В А, Зефиров Н С О вероятностном подходе к определению области применимости уравнений связи «структура-свойство» // ДАН, 2000, т 375, № 1, с 46-49

51 Пасюков А В , Скворцова М И , Палюлин В А, Зефиров Н С Метод прогнозирования свойств химических соединений, основанный на оптимальном подборе меры молекулярного подобия // ДАН, 2000, т 374, № 6, с 786-789

52 Skvortsova М I, Fedyaev К S, Palyulin V А, Zefirov N S An Automatic Search for Chemical Structures with Given Properties Correlating Hosoya Index // In Book of Abstracts of International School-Seminar on Computer Automatization and Information, Moscow, 2000 (Russian Academy of Sciences, Moscow State University, Russian Research Center "Kurchatov Institute", MC RAS-MS "ELICS", ACS'2000), p 47-48

53 Skvortsova M I, Fedyaev К S , Palyuhn V A, Zefirov N S A Probability Technique for the Construction of the Applicability Range for "Structure-Property" Equation // In Book of Abstracts of International School-Seminar on Computer Automatization and Information, Moscow, 2000 (Russian Academy of Sciences, Moscow State University, Russian Research Center "Kurchatov Institute", MC RAS-MS "ELICS", ACS'2000), p 45-46

54 Скворцова M И, Федяев К С, Палюлин В А, Зефиров H С О вероятностном подходе к определению области применимости в QSAR // Тезисы докладов П-ой Всероссийской конференции «Молекулярное моделирование», 24-26 апреля 2001 г, Москва, 2001 (РАН, Отделение Общей и технической химии, Институт геохимии и аналитической химии им В И Вернадского, МГУ им M В Ломоносова), с 36

55 Скворцова M И, Федяев К С, Палюлин В А, Зефиров H С Обратная задача в проблеме связи «структура-свойство» для индекса Хосойя // Тезисы докладов П-ой Всероссийской конференции «Молекулярное моделирование», 24-26 апреля 2001 г , Москва, 2001 (РАН, Отделение Общей и технической химии, Институт геохимии и аналитической химии им В И Вернадского, МГУ им M В Ломоносова), с 99

56 Скворцова M И, Станкевич И В Теория графов в структурной химии Спектры графов и их применение в теории сопряженных молекул Часть II - Москва - МИТХТ им M В Ломоносова -2001 -64 с

57. Скворцова M И, Федяев К С, Баскин И И, Палюлин В А, Зефиров H С Структурно-вероятностный подход к определению области применимости линейной модели связи «структура-свойство» // Тезисы докладов II-ого международного симпозиума «Компьютерное обеспечение химических исследований» (Москва, 22-23 мая 2001 г ) и Ш-ей Всероссийской школы-конференции по квантовой и вычислительной химии им В А Фока (Великий Новгород, 21-25 мая 2001 г ), с 126

58. Скворцова M И, Федяев К С, Баскин И И, Палюлин В А, Зефиров H С Об одном способе кодирования химических структур в задачах построения математических моделей связи "структура-свойство" // Тезисы докладов II-ого международного симпозиума «Компьютерное обеспечение химических исследований» (Москва, 22-23 мая 2001 г ) и Ш-ей Всероссийской школы-конференции по квантовой и вычислительной химии им В А Фока (Великий Новгород, 21-25 мая 2001 г ), с 127

59 Скворцова M И, Федяев К С, Палюлин В А, Зефиров H С Обратная задача в проблеме связи «структура-свойство» для случая корреляционного уравнения, содержащего индекс Хосойя//ДАН, 2001, т 379, №2, с 209-213

60. Скворцова M И , Федяев К С , Баскин И И , Палюлин В А, Зефиров H С Новый способ кодирования химических структур на основе базисных фрагментов // ДАН, 2002, т 382, № 5, с 645-648

61 Скворцова M И, Федяев К С, Палюлин В А, Зефиров H С Обратная задача в проблеме связи «структура-свойство» для случая корреляционных уравнений, содержащих базисные топологические дескрипторы/ЛГезисы докладов Ш-ей Всероссийской конференции «Молекулярное моделирование», 15-17 апреля 2003 г (Москва, РАН, Отделение химии и наук о материалах, Ин-т геохимии и аналитической химии им В И Вернадского, МГУ им M В Ломоносова), с 110

62 Скворцова M И, Федяев К С, Палюлин В А, Зефиров H С Базисные топологические дескрипторы и их применение для построения корреляций «структура-свойство» // Тезисы докладов Ш-ей Всероссийской конференции «Молекулярное моделирование», 15-17 апреля 2003 г (Москва, РАН, Отделение химии и наук о материалах, Ин-т геохимии и аналитической химии им В И Вернадского, МГУ им M В Ломоносова), с 109

63. Skvortsova M I, Fedyaev К S , Palyulm V A, Zefirov N S Molecular Design of Chemical Compounds with Prescribed Properties from QSAR Models Containing the Hosoya Index // Internet Electron J Mol Des 2003, N 2, p 70-95, http //www biochempress com

64 Skvortsova M I, Fedyaev К S , Palyuhn V A, Zefirov N S Inverse Problem in Quantitatve Structure-Property Relationships Studies for Correlations Constructed by Basic Topological Molecular Descriptors // In Book of Abstracts "Modern Trends m Oiganometallic and Catalitic Chemistry Mark Vol'pm (1923-1996) Memorial International Symposium, Moscow, May 18-23, 2003", pi81

65 Скворцова M И, Федяев К С, Палюлин В А, Зефиров Н С Моделирование связи между структурой и свойствами углеводородов на основе базисных топологических дескрипторов // Известия АН (сер химическая), 2004, № 8, с 1527-1535

66 Скворцова М И, Станкевич И В О связи между собственными векторами взвешенных графов и их подграфами // Дискретная математика, 2004, т 16, вып 4, с 32-40

67 Скворцова М И , Палюлин В А, Зефиров Н С Компьютерный дизайн топологических индексов в органической химии // Тезисы докладов IV-ой Всероссийской конференции «Молекулярное моделирование", 12-15 апреля 2005 г, Москва (РАН - Отделение наук о Земле, ГЕОХИ им В И Вернадского, МГУ им М В Ломоносова), с 93

68 Скворцова М И, Палюлин В А, Зефиров Н С Построение моделей связи «структура-свойство» на основе концепции молекулярного подобия путем оптимального подбора меры подобия и молекулярных дескрипторов//Тезисы докладов IV-ой Всероссийской конференции «Молекулярное моделирование", 12-15 апреля 2005 г, Москва (РАН -Отделение наук о Земле, ГЕОХИ им В И Вернадского, МГУ им М В Ломоносова), с 94

69 Skvortsova М I, Stankevich I V Eigenvectors of Weighted Graphs Supplement to Sachs' Theorem //J Mol Struct (THEOCHEM), 2005, v 719, p 213-223

70 Palyulin V A, Skvortsova M I, Zotov A Yu, Zefirov N S Computed-Aided Design of Topological Indices // In Book of Abstracts Fourth Indo-US Workshop on Mathematical Chemistry (With Applications to Drug Discovery, Environmental Toxicology, Chemoinformatics and Bioinformatics), Yanuary 8-12, 2005, Pune, Maharashtra, India, p 16

71 Скворцова M И, Федяев К С, Палюлин В А, Зефиров Н С Теоретико-графовый подход к моделированию связи между строением и свойствами углеводородов // Сборник научных трудов 11-ой Международной конференции «Математические модели физических процессов», т 1 (29-30 июня 2005, Россия, Таганрог, ТГПИ) с 254-259

72 Скворцова М И, Станкевич И В Система искусственного интеллекта для конструирования инвариантов графов в органической химии // Сборник трудов XIX Международной научной конференции «Математические методы в технике и технологиях», т 6 (30 мая-2 июня 2006, Россия, Воронеж, ВГТА), с 62-64

73 Скворцова М И, Станкевич И В, Палюлин В А, Зефиров Н С Концепция молекулярного подобия и ее применение для прогнозирования свойств органических соединений // Успехи химии, 2006, т 75, № 11, 1074-1093

ВВЕДЕНИЕ.

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

§1.1. Введение.

§1.2. Базис инвариантов графов (определение 1), его свойства и применение для моделирования связи «структура-свойство» (метод № 1)

§1.3. Базис инвариантов графов (определение 2) и его свойства.

§1.4. Модификация базисных инвариантов, введенных в

§1.3, и их применение для моделирования связи «структура - свойство» (метод №2).

§1.5. Базис инвариантов графов (определение 3), его свойства и применение для моделирования связи «структура-свойство» (метод № 3).

§1.6. Базисные подграфы и их применение для моделирования связи «структура

- свойство» (метод №4).

§ 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] предложен подход для прогнозирования биологической активности конформационно-гибких соединений, основанный на методе интервального анализа и использующий квантово-химические параметры. в) Геометрические параметры. Эти параметры рассчитываются из трехмерной модели молекулы, полученной путем минимизации энергии структуры (например, методами молекулярной механики). Геометрические параметры характеризуют размер и форму молекулы. Наиболее распространенные из них - ван-дер-ваальсов объем молекулы и собственные числа тензора инерции. Для построения тензора инерции, представляющего собой матрицу размера 3x3, используются атомные массы и пространственные координаты ядер атомов [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[jj\jo вещества 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„+2 при п=20 равно 366319, а при п=30 - 4111846763). Очевидно, что с точки зрения химии не важно, одно или много решений будет иметь поставленная задача. С другой стороны, с практической точки зрения важно получить обозримое множество структур за разумное время. Актуальность данной задачи в области поиска соединений с заданными свойствами, а также отсутствие подходящих алгоритмов привели к развитию целого направления в математической химии, связанного с реконструкцией молекулярных графов по их инвариантам.

Первой работой в этой области была работа [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<l2))]/[I(Xi(1))2+I(Xi(2))2-Imin(Xi(1),Xi(2))]; ¿¿(¿'^х^^Рх^хРШЦх!0)2)1''2 (Цх!2) f),/2] (косинус угла между векторами); d7(x(,\x(2)) -[21тт(х11),х12))HIx^+Ix^]; d&(xm^2)M^nlX(xll)-xi2)fjl.

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

3) Пусть MACS(G],G2) - максимальный общий подграф графов Gj и Gf, |G| - суммарное число вершин и ребер графа G. В литературе рассматривались следующие меры подобия, основанные на максимальном общем подграфе: d12(GhG2)=\G,\ + \G2\-2\MACS(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\ + \L2V2\LCS(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„6у) -некоторая симметричная функция двух аргументов (графов) б, и бу, значения которой количественно характеризуют степень подобия двух структур б, и бу. Предложен метод оптимального подбора меры й^6/,бу) в этом соотношении по заданной выборке соединений, а также способ оценки свойств соединений на основе такой модели.

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

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

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

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

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

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

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

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

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

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

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

1. Стьюпер Э., Брюггер У., Джуре П. Машинный анализ связи химической структуры и биологической активности. М.:Мир, 1982, 235 с.

2. Розенблит А. Б., Голендер И. Е. Логико комбинаторные методы в конструировании лекарств. Рига, 3инатне,1983, 352 с.

3. Тюрина Л. А., Кадыров Ч. Ш., Симонов В. Д. Машинный поиск закономерностей строение биологическое действие химического соединения. Итого науки и техники, сер. Органическая химия, т.18,1989, 156 с.

4. Devillers J., Balaban А. Т. (Eds.). Topological Indices and Related Descriptors in QSAR and QSPR. Gordon and Breath Science Publishers, Amsterdam, 1999.

5. Todeschini R., Consonni V. Handbook of Molecular Descriptors. Willey-VCH, Weinheim, 2000.

6. Zefirov N. S., Palyulin V. A. Fragmental Approach in QSPR // J. Chem. Inform. Comput. Sei. 2002. - v. 42. - p. 1112-1122.

7. Виноградова M. Г., Папулов Ю, Г., Смоляков В. М. Количественные корреляции «структура-свойство» алканов. Аддитивные схемы расчета. (Учебное пособие). Тверь: Изд-во ТГУ, 1999. - 96 с .

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

9. Johnson M. A., Maggiora G. M. (Eds) Concepts and Applications of Molecular Similarity.- Wiley, New York, 1990.

10. Станкевич M. И., Станкевич И. В., Зефиров Н. С. Топологические индексы в органической химии // Успехи химии. 1988. - т. 57. - с.337-366.

11. Раевский O.A., Сапегин A.M. Возможности и перспективы конструирования биологически активных веществ//Успехи химии.-1988.-т.57.-№9.- с.1565-1585.

12. Виноградова М.Г. Расчетные методы исследования взаимосвязи «структура-свойство» в атом-атомном представлении // Автореферат дисс. на соискание ученой степени д.х.н.- Тверь.- ТГУ. 2004.

13. Папулов Ю.Г. Виноградова М.Г. Расчетные методы в атом-атомном представлении.-Тверь,- ТГУ.-2002.

14. Raevsky O.A. Molecular structure descriptors in the computer-aided design of biologically active compounds // Russ.Chem.Rev.-1999.- v.68.- p.505-524.

15. Нижний C.B., Эпштейн H.A. Количественные соотношения «химическая структура-биологическая активность» //Успехи химии. -1978. -т. 47. №4. с.739-772.

16. Karelson M., Lobanov V.S., Katritzky A.R. Quantum Chemical Descriptors in QSAR/QSPR Studies//Chem. Rev.- 1996.-v.96.- p.1027-1043.

17. Бурляева E.B. Информационно методологическое обеспечение поддержки принятия решений при прогнозировании активности конформационно-гибких органических соединений // Автореферат дисс. на соискание ученой степени д.т.н. - М.- МИТХТ.-2004.

18. Велик А.В. Теоретическая оценка взаимосвязи структура-свойства для ряда органических соединений // Автореферат дисс. на соискание ученой степени д.х.н.- Уфа. -1994.

19. Бородина Ю. В. Компьютерный анализ сходства фармакологических веществ с эндогенными биорегуляторами рецепторного действия и их синтетическими аналогами // Дисс. на соискание ученой степени к. б. н., НИИ Биомедицинской химии РАМН, Москва, 1998.

20. Смоляков В.М. Зависимость свойств органических веществ от строения их молекул: расчетно-теоретическое исследование// Автореферат дисс. на соискание ученой степени д.х.н.,-Тверь.-ТГУ.- 1995.

21. Carchart R.E., Smith D.H., Venkataraghavan R. Atoms Pairs as Molecular Features in Structure-Activity Studies: Definition and Applications// J. Chem.Inform. Comput.Sci.-1985.-v.25.-p.64-73.

22. Кинг P. (ред.). Химические приложения топологии и теории графов. М.: Мир, 1987.-560 с.

23. Папулов Ю. Г., Розенфельд В. Р., Кеменова Т. Г. Молекулярные графы (учебное пособие).- Тверь: Изд-во ТГУ, 1990. 88 с.

24. Зефиров Н. С., Кучанов С. И. (ред.). Применение теории графов в химии. -Новосибирск, Наука, 1988. 306 с.

25. Скворцова М. И., Станкевич И. В. Теория графов в структурной химии. Спектры графов и их применение в теории сопряженных молекул. Часть П.(Учебно-методическое пособие). Москва, Изд-во МИТХТ, 2001. - 64 с.

26. Скворцова М. И., Станкевич И. В. Теория графов в структурной химии. Молекулярные графы. Часть I. (Учебно-методическое пособие. Москва, Изд-во МИТХТ, 1998.-88 с.

27. Папулов Ю. Г., Чернова Т. И., Смоляков В. М., Поляков М. Н. Использование топологических индексов при построении корреляций «структура-свойство»//Журн. физ. химии. 1993. - т.67. - № 2. - с.203-209.

28. Смоленский Е. А. Применение теории графов к расчету структурно -аддитивных свойств углеводородов.// Журн. физ. химии. 1964. - т.38. - № 5. -с. 1288-1290.

29. Balaban A. T.(ed.). Chemical Applications of Graph Theory. Academic Press, London, 1976.

30. Trinajstic N.(ed.) Chemical Graph Theory, v.l, 2. CRC Press, Boca Raton, FL, 1983.

31. King R.B., Rouvray D. H. (ed.). Graph Theory and Topology in Chemistry (Studies in Physics and Theoretical Chemistry, v.51). Elsevier, Amsterdam, 1987.

32. Randic M. Chemical Graph Theory Facts and Fictions//Indian J. of Chemistry. -v. 42 a. -2003. - p.1207-1218.

33. Marinich J.A., Maguna F., Okulik N., Castro E.A. An Optimal Characterization of Structure by Means of Several Molecular Connectivity and Complexity Indices// Polish J.Chem.- 2002. -v.76. -p.589-600.

34. Zupan J., Gastaiger J. Neural Networks for Chemists. -VCH.- Weinhein.- 1993.

35. Гальберштам Н.М. Моделирование своймтв и реакционной способности органических соединений с использованием искусственных нейронных сетей // Автореферат дисс. на соискание ученой степени к.х.н. -Москва.- МГУ.-2001.

36. Баскин И.И., Гальберштам Н.М., Палюлин В.А., Зефиров Н.С. NASA WIN -программный комплекс для исследования зависимостей «структура-свойство» в химии // Материалы 7-ой Всероссийской конф. «Нейрокомпьютеры и их применение». -М.-2001, с.419-422.

37. Sixt S., Altschuh J., Bruggemann R. Quantitative structure-toxity relationships for 80 chlorinated compounds using quantum chemical descriptors// Chemosphere.-1995,- v. 30. No. 12.- p. 2397-2414.

38. Rouvray D. H., King R. B. (Eds.). Topology in Chemistry. Discrete Mathematics of Molecules. Horwood Publishing Ltd., 2002.

39. Basak S.C., Harriss D.K., Magnuson V.R. POLLY: Copyright of the University of Minnesotf,1988.

40. Katritzky A.R., Lobanov V., Karelson M. CODESSA (Comprehensive DEScriptors for Structural and Statistical Analysis); University of Florida, Gainesville, FL.

41. Баскин И.И., Станкевич М.И. Девдариани P.O., Зефиров Н.С. Комплекс программ для нахождения корреляций «структура-свойство» на основе топологических индексов// Журн. структурной химии. -1989.-т.30.-№6.-с.145-147.

42. Петелин Д. Е., Палюлин В.А., Зефиров Н. С. Топологические индексы для исследований в QSAR/QSPR, основанные на весах вершин молекулярных графов// ДАН. 1992. -т. 324. - №5. - с. 1019-1022.

43. Basak S.C., Magnuson V.R., Niemi G. I., Regal R.R., Veith G. D. Topological Indices: Their Nature, Mutual Relatedness, and Applications// Mathematical Modelling 1987. -v. 8. - p. 300-305.

44. Wessel M.D., Jurs P.C. Prediction of Normal Boiling Points of Hydrocarbons from Molecular Structure// J.Chem. Inf. Comput. Sci. 1995. -v. 35. -No. 1. - p. 6876.

45. Sutter J. M., Dixon S.L., Jurs P.C. Automated Description Selection for Quantitative Structure-Activity Relationships Using Generalized Simulated Anneling // J. Chem. Inform. Comput. Sci. 1995.- v.35. -No. 1.- p. 77-84.

46. Tratch S. S., Stankevich M. I., Zefirov N.S. Combinatorial Models and Algorithms in Chemistry. An Expanded Wiener Number a Novel Topological Index // J. Сотр. Chem.- 1990. - v. 11. - No. 7. p. 899-908.

47. Hansch C. A quantitative Approach to biochemical structure-activity relationships //Acct. Chem. Res.- 1969. v. 2. - p. 232-239.

48. Hansch C. On the structure of medicinal chemistry// J. Med. Chem. 1976. -v.19. p.1-6.

49. Hansch С. Structure activity relationships of chemical mutagens and carcinogens// Sci. Tot. Environ.-1991. - v. 109/110. -p. 17-29.

50. Kim K.H., Hansch C., Fukunagh I. Y., Steller E. E., Jow P.Y.C., Craig P. N., Page J. Quantitative structure-activity relationschips in l-aryl-2-(alkylamino) ethanol antimalarials// J. Med. Chem. 1979. -v. 22. -p. 366-371.

51. Klopman G. Artifical Intelligence approach to structure-activities studies. Computer automated Structure Evaluation of biological Activity of Organic Molecules// J. Am. Chem. Soc. 1984. -v. 106, -p. 7315-7321.

52. Klopman G. MULTICASE: 1. A Hierarchical Computer Automated Structure Evaluation Program// Quant. Struct.-Act. Relat.- 1992. -v. 11. -p. 176-184.

53. Enslein K., Craig P. N. Carcinogenesis: A predictive structure-activity model// J. Toxicol. Environ. Health. 1982. - v. 10. - p. 521-530.

54. Enslein K., Borgstedt H. H., Tomb M. E., Blake B. W., Hart H. B. A Structure-activity prediction Model of Carcinogenicity based on NCI/NTP assays and food Additives// Toxicol. Indust. Health. 1987. -v.3. - p. 267-287.

55. Enslein K., Gombar V. K., Blake B. W. Use of SAR in Computer Assisted Prediction of Carcinogenicity and Mutagenicity f Chemicals by the TOPCAT Program// Mutation Research. - 1994. -v. 305. - 47-61.

56. Skvortsova M.I., Baskin I.I., Slovokhotova O.L., Palyulin V.A., Zefirov N.S. Inverse Problem in QSAR/QSPR Studies for the Case of Topological Indices Characterizing Molecular Shape (Kier Indices)// J. Chem. Inform. Comput. Sci.-1993. v.33. p.630-634.

57. Dimitrov S., Dimitrova G., Pavlov Т., Dimitrova N., Patlewicz G., Niemela J., Mekenyan O. A Stepwise Approach for Defining the Applicability Domain of SAR and QSAR Models// J. Chem. Inform. Comput. Sci.- 2005. v. 45. - p.839-849.

58. Guha R., Jurs P. Determining the Validity of a QSAR Model A Classification Approach// J.Chem. Inform. Comput. Sci. - 2005. - v.45. -p.65-73.

59. Gramatica P., Pilutti P., Papa E. Validated QSAR Prediction of OH Tropospheric Degradation of VOCs: Splitting into Training/Test Sets and Consensus Modeling// J.Chem. Inform. Comput. Sci.- 2004. v.44. - p. 1794-1802.

60. Баскин И. И., Гордеева Е. В., Девдариани Р. О., Зефиров Н. С., Палюлин В. А., Станкевич М. И. Методология решения обратной задачи в проблеме связиструктура-свойство» для случая топологических индексов// ДАН АН СССР. -1989. т.307. - № 3. -с. 613-616.

61. Milne G. W. A. Mathematics as a Basis for Chemistry// J. Chem. Inform. Comput. Sci. 1977. -v. 37. -c. 639-644.

62. Зефиров H. С., Палюлин В. А., Радченко E. В. Генерация химических структур с заданными свойствами. Решение обратной задачи для центрического индекса Балабана// ДАН АН СССР. 1991. -т. 316. -с. 921-924.

63. Kier L. В., Hall L. H, Frazer J. W. Design of Molecules from Quantitative Structure-Activity Relationship Models. 1. Information Transfer between Path and Vertex Degree Counts// J. Chem. Inf. Comput. Sci.- 1993. v. 33. - p.143-147.

64. Kier L. В., Hall L. H., Frazer J. W. Design of Molecules from Quantitative Structure-Activity Relationship Models. 2. Derivation and Proof of Information Transfer Relating Equations// J. Chem. Inf. Comput. Sci. 1993. - v. 33. - p. 148152.

65. Hall L. H., Dailey R. S., Kier L. B. Design of Molecules from Quantitative Structure-Activity Relationship Models. 3. Role of Higher Order Path Counts // J. Chem. Inf. Comput. Sci. 1993. - v. 33.- p. 598-603.

66. Kvasnicka V., Pospichal J. Canonical Indexing and Constructive Enumeration of Molecular Graphs// J. Chem. Inform. Comput. Sci. 1990.- v. 30. -p. 99-105.

67. Faulon J.-L. Stochastic Generator of Chemical Structures. 2. Using Simulated Anneling to Search the Space of Constitutional Isomers // J. Chem. Inform. Comput. Sci.- 1996.-v.36. p. 731-740.

68. Venkatasubramanian V., Chan K., Caruthers J. Evolutionary Design of Molecules with Desired Properties Using the Genetic Algorithm // J. Chem. Inform. Comput, Sci.- 1995.-v.35.- p.188-195.

69. Rouvray D. H. Similarity Studies. l.The Necessity for Analogies in the Development of Science. // J. Chem. Inform. Comput. Sci.- 1994. v. 34. - p. 446 -452.

70. Carbo-Dorca R., Mezey P. G. (Eds.). Advances in Molecular Similarity, v.2. -JAI Press, London, 1998.

71. Carbo R. (Ed.). Molecular Similarity an Reactivity: From Chemical to Phenomenological Approaches. Kluver Academic Publishers, Dordrecht, Netherlands, 1995.

72. Dean P. M. (Ed.). Molecular Similarity in Drug Design.- Blackie Academic & Professional, London, 1995.

73. Johnson M. A. A Review and Examination of Mathematical Spaces Underlying Molecular Similarity Analysis. //J. Math. Chem.- 1989. v.3. -№2. -p.l 17-145.

74. Monev V. Introduction to Similarity Searching in Chemistry. // MATCH. -2004.-v. 51. p. 7-38.

75. Martin. J. C. Diverse Viewpoints on Computational Aspects of Molecular Diversity // J. Comb. Chem.-2001. v. 3. - № 3. - p. 231-250.

76. Nikolova N., Jaworska J. Approaches to Measure of Similarity a Review. // QSAR Combin Sci. - 2003. -v.22. -p. 1006-1026.

77. Randic M. In: Kuchanov S. I. (ed.). Mathematical Methods in Contemporary Chemistry. Gordon and Breath Publishers, Amsterdam, 1996. -p. 1-100.

78. Sen K. (Ed.). Molecular Similarity I and II. Topics Curr. Chem.-1973 (1995).?

79. Willett P. Similarity and Clustering in Chemical Information Systems. Research Studies Press, Letchworth, 1987.

80. Скворцова М.И., Станкевич И.В., Палюлин B.A., Зефиров Н.С. Концепция молекулярного подобия и ее использование для прогнозирования свойств химических соединений// Успехи химии.- 2006.-т.75.-№11.- с.1074-1093.

81. Джуре П., Айзенауэр Т. Распознавание образов в химии. Мир, Москва, 1977.

82. Basak S. С., Grunwald D. G. Estimation of lipophility from molecular structural similarity //New J. Chem. -1995. v. 19.-p. 231-237.

83. Basak S. C., Grunwald G. D. Molecular Similarity and Risk Assisment: Analog Selection and and Property Estimation Using Graph Invariants // SAR and QSAR in Environmental Research. 1994. - v.2.- p. 289-307.

84. Basak S. C., Bertelsen S., Grunwald G. D. Application of Graph Theoretical Parameters in Quatifying Molecular Similarity and Structure-Activity Relationships // J. Chem. Inform. Comput. Sci. 1994. - v.34. - p. 270-276.

85. Anzali S., Barnickel G., Cezanne В., Krug M., Filimonov D., Poroikov V. Discriminating between Drugs and Nondrugs by Prediction of Activity Spectra for Substances (PASS)// J. Med.Chem.- 2001.- v. 15. №4.- p.2432-2437.

86. Lagunin A., Stepanchikova A., Filimonov D., Poroikov V.PASS: prediction of activity spectra for biologically active substances// Bioinformatics.- 2000.- v. 16. -№8.- p.747-748.

87. Corneil D. G., Kirkpatrik D. G. A theoretical analysis of various heuristics for the graph isomorphism problem // SIAM J. Comput. 1980. - № 2. - v.9. -p. 281-297.

88. Read R. C., Corneil D. G. The graph isomorphism disease // J. Graph Theory. -1977,- v.l. -p. 339-363.

89. Gati G. Further annotated bibliography on the isomorphism disease // J. Graph Theory.- 1979. № 2. - v.3. - p. 95-109.

90. Земляченко В. H., Корнеенко Н. М., Тышкевич Р. И. Проблема изоморфизма графов. В: Записки Научного семинара ЛОМИ АН СССР. -1982.- тЛ 18. с. 83158.

91. Goldbogen C.G., Williams G. Н. A comparision of graph isomorphism algorithms. In: Algorithms and Complexity. New Directions and Recent Results, Proc. Symp. Carnegie-Mellon Univ., New York, 1976; New York, e.a.,1976.

92. Курейчик В. M., Королев А. Г. Применение алгоритма изоморфизма графов для контроля схем БИС// Кибернетика. 1977. - № 2. -с. 82-87.

93. Corneil D. G., Gotlieb С. С. An efficient algorithm for graph isomorphism// J. Assoc. Comput. Mach.-1970. № 1. - v. 17. -p. 51-64.

94. Goldberg M. К. Нефакториальный алгоритм распознавания изоморфизмов графа// Discrete Appl. Math. -1983. -v. 6. p. 229-236.

95. Раденски А. А. Алгоритм для нахождения всех изоморфизмов двух графов// Сердика. Бълг. Мат. Списания. 1975. - т.1. - №2.- с.167-177.

96. Tinhofer G. К определению автоморфизмов конечного графа// Computing, -1975. -v.15. №2. -р. 147-156. ?

97. Corneil D., Goldberg М. Нефакториальный алгоритм для канонической нумерации графа// J Algorithms. 1984. -v. 5. - p. 345-362.

98. Херндон У. Каноническая нумерация и система линейных обозначений химических графов. В кн.: Кинг Р. (ред.). Химические приложения топологии и теории графов.- М.:Мир,1987. -с. 266-277.

99. Скоробогатов В. А., Хворостов П. В. Методы и алгоритмы анализа симметрии графов// Вычислительные системы (Новосибирск). -1984. № 103. -с. 6-25.

100. McKay В. D. Нахождение автоморфизмов и канонических помечиваний графов// Lect. Notes in Math. 1978. - v. 686. - p. 223-230.

101. Арлазаров В. Л., Зуев И. И., У сков А. В., Фараджев И. А. Алгоритм приведения конечных неориентированных графов к каноническому виду// Ж. выч. матем. и мат. физ. 1974. - № 3.- с. 737-743.

102. Зыков А. А. Основы теории графов. М.: Наука, 1987.

103. Akinniya F.A.,Wong А.К.С. A new product graph based algorithm for subgraph isomorphism// Proc. CVPR'83: IEEEE Comput. Soc. Conf. Comput. Vision and Pattern Recogn. Washington, DC, 19-23 Jule, 1983. Silver Spring, Md, 1983. -p. 457-467.

104. Baron G. Bestimmung der Automorphismengruppe Spezieller Klassen von Graphen// Computing -1967. № 2. -p. 332-335.

105. Сенюкова А. Г. Об определении всех автоморфизмов неориентированных графов//Кибернетика. 1978. -№ 1.-е. 141-145.

106. Brown H. Molecular Structure Elucidation// SIAM J. Appl. Math. 1977.- v.32. -№ 3. -p.534-?

107. Stoubach R. E. Chemical Substructure Searching // J. Chem. Inform. Comput. Sci. 1985. - v.25. - № 3. - 271-177.

108. Курейчик В. M., Королев А. Г. Об одном методе изоморфного вложения графов. В сб.: Методы расчета и автоматиз. проектир. устройств микроэлектрон. ЦВМ. 1975, Киев. - р. 6-16.

109. Cheng J.K., Huang Т. S. A Subgraph Isomorphism Algorithm Using Resolution//PatternRecogn. 1981.- v. 13. - № 5.-p. 731-739.

110. Ullman J. R. An Algorithm for Subgraph Isomorphism // J.Assoc. Comput. Mach.- 1976.-v.2.-№l.-p. 31-42.

111. Боровиков A.A. Изоморфизм графов. В сб.: Искусственный интеллект: итоги и перспективы. М., 1974. - с. 83-88.

112. Chahraman D. Е., Wong А.К.С., Au Tung. Graph Monomorphism Algorithms// IEEE Trans. Syst. Man. And Cybern.-1980. -v. 10. № 4. - p.189-196.

113. Король H. E., Шкурба В. В. Задача идентификации подграфа и ее приложения. В сб.: Мат. методы исследов. и оптимиз. систем,- Киев, 1970, Вып.З.-с. 49-58.

114. Kasif S., Kitchen L., Rosenfeld A. A hough transform technique for subgraph isomorphism// Pattern Recogn. Lett. 1983. -v. 2. - №2. - p. 83-88.

115. Шейнаускас Р.И. Алгоритм для установления изоморфизма и изоморфного вхождения двух графов. В сб.: Вычислит, техн., т.З. Каунас, 1972. -с. 347-353.

116. Fridrich G., Ugi I. Substructure Searching and Structure Property Locating by Means of Substructure Generation// MATCH. 1979.- v. 6. -p. 201-211.

117. Моисеев H.H. Математические задачи системного анализа. М.: Наука, 1981.-488 с.

118. Мнухин В. Б. О базисе алгебры инвариантов графа. В сб.: Математический анализ и его приложения. Ростов-на-Дону, 1983. - с.55-60.

119. Randic М. Representation of Molecular Graphs by Basic Graphs // J. Chem. Inform. Comput. Sci. 1999. - v.32. - № 1. - p. 57-69.

120. Kier L. В., Hall L. H. Molecular Connectivity in Structure-Activity Analisis. -N.Y., Research Studies Press Ltd., John Wiley and Sons Inc., 1986. 262 p.

121. Kier L. В., Hall L. H. Molecular Connectivity in Chemistry and Drug Research. N. Y., Academic Press, 1976.

122. Kier L. B. Shape Index from Molecular Graphs // Quant. Struct.- Act. Relat. -1985.-v.4.-p. 109-116.

123. Kier L. B. Shape Indexes of Orders One and Three from Molecular Graphs // Quant. Struct.-Act. Relat. -1986. v. 5. p. 1-7.

124. Kier L. B. Inclusion of Symmetry as a Shape Attribute in Kappa Index Analysis// Quant. Struct.-Act. Relat. 1987.- v.6. - p. 8-12.

125. Kier L. B. Indexes of Molecular Shape from Chemical Graphs// Med. Res. Rev.-1987.- v. 7. p. 417-440.

126. Bonchev D. Informational Theoretic Indices for Characterization of Chemical Structures. Research Studies Press, N.Y. ,1983.

127. Магнусон В., Харрис Д., Бейсак С. Топологические индексы, основанные на симметрии окрестностей: химические и биохимические применения. В кн.: Кинг Р.(ред), Химические приложения топологии и теории графов. М., Мир, 1987.- с.206-221.

128. Wiener Н. Relation of the Physical Properties of the Isomeric Alkanes to Molecular Structure// J. Phys. Chem. 1948. - v. 52. p. 1082-1089.

129. Wiener H. Structural Determination of paraffin boiling Points // J. Am. Chem. Soc. 1947.- v.69. - №1. p. 17-20.

130. Needham D. E., Wei I. C, Seybold P. G. Modeling of the Physical Properties of the Alkanes//J. Am. Chem. Soc.- 1988,- v. 110. p. 4186-4194.

131. Zefirov N. S., Palyulin V. A. QSAR for Boiling Points of "Small" Sulfides. Are the "High-Quality Structure-Property-Activity Regressions" the Real High Quality QSAR Models?// J. Chem. Inf. Comput. Sci.- 2001. v.41. p. 1022-1027.

132. Sharma V., Goswami R., Madan A. K. Eccentric Connectivity Index: A Novel Highly Discriminating Topological Descriptor for Structure-Property and Structure-Activity Studies// J. Chem. Inform. Comput. Sci. 1997. - v. 37. p. 273-282.

133. Randic M., Sabljic A., Nicolic S., Trinajstic N. A Rational Selection of Graph-Theoretical Indices in the QSAR // Intern. J. Quant. Chem.: Quantum Biology Symposium.-1988. v. 15. p. 267-285.

134. Molchanova M. S., Shcherbukhin V. V., Zefirov N. S. Computer Generation of Molecular Structures by SMOG Program // J. Chem. Inf. Comput. Sci. 1996. -v. 36. p. 888-899.

135. Molchanova M. S., Zefirov N. S. Irredundant Generation of Isomeric Molecular Structures with some Known Fragments // J. Chem. Inform. Comput. Sci.-1998.-v. 38.- p. 8-22.

136. Цветкович Д., Дуб M., Захс X. Спектры графов. Теория и применение.-Киев, Наукова Думка, 1984.

137. Cvetkovic D., Doob М., Sachs Н. Spectra of Graphs. Theory and Application. -Academic Press, New York, 1980; 2nd revised: Barth, Heidelberg, 1995.

138. Sachs H. Beziehungen zwischen den in einem Graphen enthaltenen Kreisen und seinem charakteristischen Polynom // Publ. Math. (Debrecen). -1964.- v. 11, p. 119134.

139. Heilbronner E. Some comments on cospectral graphs // MATCH. 1979.- №5.-p. 105-113.

140. D'Amato S. S., Gimarc В. M., Trinajstic N. Isospectral and Subspectral Molecules // Croat. Chem. Acta. 1981. - v.54. -№1. - p. 1-52.

141. Knop J. V., Miiller W. R., Szimanski K., Trinajstic N., Kleiner A. F., Randic M. On irreducible endospectral graphs// J.Math.Phys. 1986. -v.27. - p. 2601-2612.

142. Плотников А. Д. Дискретная математика (Учебное пособие). М.,: Новое знание, 2005. - 288с.

143. Rucker G, Riicker С. On Topological Indices, Boiling Points and Cycloalkanes // J. Chem. Inf. Comput. Sci. 1999. - v. 39. p. 788-802.

144. Роберте Дж. Расчеты по методу молекулярных орбит. -М.: Изд-во иностр. лит., 1963.- 150 с.

145. Gakh A., Gakh E. G., Sumpter B. G., Noid D. W.Neural Network-Graph Theory Approach to the Prediction of the Physical Properties of Organic Compounds // J. Chem. Inf. Comput. Sci. 1994.- v. 34. p. 832-839.

146. Оболенцев P. Д. Физические константы углеводородов. M.: Гос. научно-тех. изд-во нефтяной и горно-топл. лит-ры, 1953.

147. Татевский В. М. Физико-химические свойства индивидуальных углеводородов. -М.: Гос. научно-тех. изд-во нефтяной и горно-топл. лит-ры, 1960.-412 с.

148. Татевский В. М. Химическое строение углеводородов и закономерности в их физико-химических свойствах. М.: Изд-во Моск. ун-та, 1953. - 320 с.

149. Randic М. Orthogonal Molecular Descriptors// New J. Chem.- 1991.- v. 15.- p. 517-525.

150. Domalski E. S., Hearing E. D. //J. Phys. Chem. Ref. Data. 1988. - v. 17. -p.1637-1645.

151. Trinajstic Nv The characteristic polinomial of a chemical graph// J. Math. Chem.- 1988.- v.2 . -p.197-215.

152. Gutman I. Impact of the Sachs Theorem on theoretical chemistry :a participant's testimony//MATCH. 2003.- v. 48.- p. 17-34.

153. Graovac A., Gutman I., Trinajstic N. Topological Approach to the Chemistry of Conjugated Molecules. Lecture Notes in Chemistry (v. 4). Springer, Berlin, 1977.

154. Ivanciuc O., Ivanciuc Т., Klein D. J., Seitz W.A., Balaban A.T. Wiener Index Extension by Counting even/odd Graph Distances // J. Chem. Inform. Comput. Sci. -2001. v.41. p. 536-549.

155. Klein D. J., Lukovits I., Gutman I. On the Definition of the Hyper-Wiener For Cycle-Containing Structure// J. Chem. Inform. Comput. Sci. 1995. -v.35. p. 50-52.

156. Plavsic D., Nicolic S., Trinajstic N., Mihalic Z. On the Harary Index for the Characterization of Chemical Graphs// J. Math. Chem. -1993. -v. 12. p. 235-250.

157. Gutman I., Linert W., Lukovits I., Tomovic Z. The Multiplicative Version of the Wiener Index// J. Chem. Inform. Comput. Sci. -2000. -v.40. -p.l 13-116.

158. Bonchev D.The Overall Wiener Index a New Tool for Characterization of Molecular Topology// J. Chem. Inform. Comput. Sci. - 2001.- v.41. p. 582-592.

159. Lukovits I., Razinger M. On Calculation of the Detour Index// J. Chem. Inform. Comput. Sci. 1997. - v. 37. -p. 283-286.

160. Randic M. Novel Shape Descriptors for Molecular Graphs// J. Chem. Inform. Comput. Sci.- 2001. v.41.-p. 607-613.

161. Gutman I., Riicker C., Riicker G. On Walks on Molecular Graphs// J. Chem. Inform. Comput. Sci.-2001.-v.41.-p.739-745.

162. Lukovits I. An All-path Version of the Wiener Index// J. Chem. Inform. Comput. Sci. 1988. - v. 38. - p. 125-129.

163. Yao, Yun-Yuan; Xu, Lu; Yang, Yi-Qui; Yuan Xiu-Shun. Study on Structure-Activity Relationships on Organic Compounds: Three New Topological Indices and Their Applications//J. Chem. Inform. Comput. Sci. 1993. - v.33. -p. 590-594.

164. Randic M. Graph Valence Shells as Molecular Descriptors// J. Chem. Inform. Comput. Sci. 2001.-v.41.-p. 627-630.

165. Shultz H. P. Topological Organic Chemistry. 1. Graph Theory and Topological Indices of Alkanes//J. Chem. Inform. Comput. Sci. 1989. - v. 29. - p. 227-228.

166. Khadicar P.V., Karmarkar S., Agrawal V. K. A Novel PI Index and Its Application to QSPR/QSAR Studies// J. Chem. Inform. Comput. Sci. 2001. - v.41. -p. 934-949.

167. Krenkel G., Castro E. A., Toropov A.A. Improved Molecular Descriptors to

168. Calculate Boiling Points Based on the Optimization of Correlation Weightts of Local

169. Graph Invariants //J. Mol. Struct (THEOCHEM). 2001.- v. 542. - p.107-113.1 f

170. Randic M., Pompe M. The Variable Connectivity Index % Versus the Traditional Molecular Descriptors: A Comparative Study of % Against Descriptors of CODESSA //J. Chem. Inform. Comput. Sci. -2001/ -v. 41. p. 631-638.

171. Демиденко Е.З. Линейная и нелинейная регрессия. М.: Финансы и статистика. 1981. - 102 с.

172. Степанов Н.Ф., Ерлыкина М.Е., Филиппов Г.Г. Методы линейной алгебры в физической химии. М.: Изд-во МГУ, 1976.

173. Чистяков В.П. Курс теории вероятностей. М.: Наука, 1987. - 240 с.

174. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. М.: Наука, 1968. - 720 с.

175. Lucic В., Lukovits I., Nikolic S., Trinajstic N. Distance-Related Indexes in the Quantitative Structure-Property Relationships Modeling// J. Chem. Inform. Comput. Sci.-2001.-v.41.-p. 527-535.

176. Randic M. On Characterization of Molecular Branching // J. Am. Chem. Soc. -1975.-v. 97.-p. 6609-6615.

177. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980.

178. Харари Ф. Теория графов. М.: Мир, 1973.

179. Молодцов С. Г., Пиоттух-Пелецкий В. Н. Построение всех неизоморфных химических графов из заданного набора структурных фрагментов// Алгоритмы анализа структурной информации (Вычисл. системы). 1984. - Вып. 103. - р. 51-58.

180. Molodtsov S. G. Generation of Molecular Graphs with a Given Set of Nonoverlapping Fragments// Commun. Math. Chem. (MATCH). -1994.- v. 30. p. 203-212.

181. Molodtsov S. G. Computer-Aided Generation of Molecular Graphs// Commun. Math. Chem. (MATCH). 1994. -v. 30. -p. 213-224.

182. Фараджев И. А. Генерация неизоморфных графов с заданным распределением степеней вершин // В: Алгоритмические исследования в комбинаторике. М., Наука, 1978. с. 11-19.

183. Masinter L. М., Sridharan N. S., Lederberg J., Smith D. H. Applications of Artifical Intelligence for Chemical Inference. 12. Exhaustive Generation of Cyclic and Acyclic Isomers // J. Am. Chem. Soc. 1974. -v. 96. -p. 7702-7714.

184. Bohanec S., Zupan J. Structure Generation of Constitutional Isomers from Structural Fragments// J. Chem. Inform. Comput. Sci. 1991. - v. 31. p. 531-540.

185. Zhu S.-Y., Zhang J.-P. Exhaustive Generation of Structural Isomers for a Given Empirical Formula a New Algorithm // J. Chem. Inform. Comput. Sci. - 1982. -v.22.-p. 38-44.

186. Липский В. Комбинаторика для программистов. М., Мир, 1988.

187. Мжельская Е. В., Скоробогатов В. А. Применение теории графов в химии полициклических бензоидных углеводородов. Новосибирск, (Препринт №35, Ин-т математики СО АН СССР), 1987. - 34 с.

188. Villemin D., Cherqaoui D., Mesbah A. // Predicting Carcinogenity of Polycyclic Aromatic Hydrocarbons from Back- Propagation Neural Networks // J. Chem. Inform. Comput. Sci. 1994. -v. 34. - p. 1288-1298.

189. Корнилов M. Ю., Замковой В.И. Расчет чисел изомеров и кодирование конденсированных полициклических систем: перечисление полибензолов //Теорет. и экспер. химия.- 1987. №1. - с. 54-61.

190. Contreras М. L., Valdivia R., Rozas R. Exhaustive Generation of Organic Isomers. 1. Acyclic Structures// J. Chem. Inform. Comput. Sci. 1992. -v. 32. - p. 323-330.

191. Cammarata A. Molecular Topology and Aqueous Solubility of Aliphatic Alcohols // J. Pharm. Sci. 1979. - v. 68. - p. 839-842.

192. Murray W. J., Hall L. H., Kier L. B. Molecular Connectiity III: Relation to partition Coefficients//J. Pharm. Sci. 1975. - v. 64.-p.1978-1981.

193. Carlson R., Prochazka M.P., Lundstedt T.V. Acta chem. scand.- 1988. v. B42. - №3. -p. 157-165.

194. Aldrich Chemical Company. Aldrich Catalog-Handbook of Fine Chemicals. -Milwaukee, WI, 1996-1997.

195. Gutman I., Shalabi A., Topological Properties of Benzenoid Systems. XXIX. On Hosoya's Topological Index// Z. Naturforsch. 1984. - v. 39a. - p.797-799.

196. Ivanciuc O., Design of Topological Indices. Part 18. Modeling the Physical Properties of Alkanes with Molecular Graph Descriptors Derived from the Hosoya Operator// Rev. Roum. Chim. 2001. - v. 46. - p. 129-141.

197. Nikolic S., Plavsic D., Trinajstic N. On the Z-counting Polynomial for Edge-weighted Graphs// J. Math. Chem. -1992.- v. 9. p. 381-387.

198. Plavsic D., Soskic M., Dakovic Z., Gutman I., Graovac A. Extension of the Z-matrix to cycle-counting and edge-weighted molecular graphs// J. Chem. Inf. Comput. Sci. 1997. -v. 37. -p. 529-534.

199. Hosoya H., Hosoi K., Gutman I., A topological index for the total л-electron energy. Proof of a generalized Huckel rule for an arbitrary network//Theor. Chim. Acta (Berlin). 1975. - v. 38. - p. 37-47.

200. Hosoya H., Murakami M. Topological index as applied to л-electronic systems. II. Topological bond order// Bull. Chem. Soc. Japan. 1975. -v. 48. -p. 3512-3517.

201. Hosoya H., Topological Index. A Newly Proposed Quantity Characterizing the Topological Nature of Structural Isomers of Saturated Hydrocarbons// Bull.Chem. Soc. Japan. -1971. v. 44. - p. 2332-2339.

202. Hosoya H., The Topological Index Z Before and After 1971 // Internet Electron. J. Mol. Des. 2002. -v. 1. -p. 428-442, http://www. biochempress. com.

203. Heilmann O. J., Lieb E. H. Theory of monomer-dimer systems // Commun. Math. Phys. 1972. -v. 25. - p. 190-232.

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

205. Станкевич (Скворцова) М. И., Баскин И. И., Зефиров Н.С. Автоматизированный поиск структурных фрагментов. Алгоритм и программа. Журнал структурной химии, 1987, т.28, № 6, с. 136-137.

206. Станкевич (Скворцова) М.И., Баскин И.И., Зефиров Н.С. Комбинаторные модели и алгоритмы в химии. Поиск структурных фрагментов. Деп. ВИНИТИ АН СССР 11.06 1986, № 4288-В86, 27 стр.

207. Станкевич (Скворцова) М.И., Станкевич И.В., Зефиров Н.С. Топологические индексы в органической химии. Успехи химии, 1988, т 57, № 3, с. 337-366.

208. Баскин И.И., Станкевич (Скворцова) М.И., Девдариани P.O., Зефиров Н.С. Комплекс программ для нахождения корреляций «структура свойство» на основе топологических индексов. Журнал структурной химии, 1989, т. 30, № 6, с.145-147.

209. Гордеева Е.В., Баскин И.И., Девдариани P.O., Зефиров Н.С., Станкевич (Скворцова) М.И. Методология решения обратной задачи в проблеме связи « структура-свойство» для случая топологических индексов. ДАН СССР, 1989, т. 307, №3, с. 613-616.

210. Stankevitch (Skvortsova) М. I., Tratch S. S., Zefirov N. S. Combinatorial Models and Algorithms in Chemistry. Search for Isomorphisms and Automorphisms of Molecular Graphs. J. Comput. Chem.,1988, v.9, N 4, p. 303-314.

211. Станкевич И. В., Скворцова М. И. Обобщенный индекс Рандича как функционал от тг электронной плотности. Тезисы докладов 1-ой Всесоюзной конференции по теоретической органической химии (ВАТОХ), Волгоград, 1991, с. 97.

212. Скворцова М. И., Станкевич И. В., Зефиров Н. С. Генерация молекулярных структур поликонденсированных бензоидных углеводородов по индексу Рандича. Журнал структурной химии, 1992, т. 33, № 3, с. 99-104.

213. Станкевич И. В., Скворцова М. И., Томилин О. Б., Зефиров Н. С. Использование проекционных операторов для нумерации атомов и исследования свойств симметрии молекулярных структур. Журнал структурной химии, 1992, т. 33, № 3, с. 93-98.

214. Скворцова М. И., Баскин И. И., Словохотова О. Л., Палюлин В. А., Зефиров Н. С. Обратная задача в QSAR/QSPR-анализе для случая топологических индексов, характеризующих молекулярную форму (индексов Кира). ДАН, 1992, т. 324, № 2, с. 344-348.

215. Станкевич И. В., Скворцова М. И., Зефиров Н.С. Топологические свойства сопряженных углеводородов: обобщенный индекс Рандича как функционал от тг- электронной плотности. Доклады Академии Наук, 1992, т.324, № 1, с.133-137.

216. Skvortsova М. I., Baskin 1.1., Slovokhotova О. L., Palyulin V. A., Zefirov N. S. The Inverse Problem in QSAR/QSPR Studies for the Case of Topological Indices

217. Characterizing Molecular Shape (Kier Indices). J. Chem. Inform.Comput.Sci., 1993, v.33,N4, p. 630-634.

218. Скворцова M. И., Баскин И. И., Словохотова О. JI., Зефиров Н. С. Методология построения общей модели связи «структура-свойство» на топологическом уровне. Доклады Академии Наук, 1994, т. 336, N 4, с. 496-499.

219. Баскин И. И., Скворцова М. И., Станкевич И. В., Зефиров Н. С. О базисе инвариантов помеченных молекулярных графов. Доклады Академии Наук, 1994, т. 339, N3, с. 346-350.

220. Stankevich I. V., Skvortsova М. I., Kolmykov V. A., Subbotin V. F., Mnukhin V. В. Spectral Graph Theory in Chemistry. In: Mathematical Methods in Contemporary Chemistry. (Ed. Kuchanov S. I.; Gordon and Breath Publishers, Amsterdam), 1996, p. 101-141.

221. Baskin 1.1., Skvortsova M. I., Stankevich I. V., Zefirov N. S. On the Basis of Invariants of Labeled Molecular Graphs. J. Chem. Inform. Comput. Sci., 1995, v. 35, N. 3, p. 527-531.

222. Stankevich I. V., Skvortsova M. I., Zefirov N. S. On a Quantum-Chemical Interpretation of Molecular Connectivity Indices for Conjugated Hydrocarbons. J. Mol. Strut. (THEOCHEM), 1995, v. 342, p. 173-179.

223. Zefirov N. S., Palyulin V. A., Skvortsova M. I., Baskin 1.1. Inverse Problem in QSAR. In: QSAR and Molecular Modeling: Concepts, Computational Tools and Biological Applications; Barcelona, Prous Science Publishers, 1995. p. 40.

224. Skvortsova M. I., Baskin I. I., Stankevich I. V., Zefirov N. S. New Method for Constructing Linear "Structure-Property" Equations. In: Book of Abstracts. International Symposium CACR-96; December 17-18; 1996, Moscow, Russia; p. 60.

225. Skvortsova M.I., Baskin I.I., Stankevich I.V., Zefirov N. S. A New Approach to to the Problem of Defining Applicability Range of QSAR/QSPR Models. In: Book of Abstracts. International Symposium CACR-96; December 17-18; 1996, Moscow, Russia; p. 67-68.

226. Baskin I. I., Skvortsova M. I., Palyulin V. A., Zefirov N. S. Quantitative Chemical Structure-Property/Activity Studies Using Artifical Neural Networks. Foundations of Computing and Decision Sciences. 1997, v. 22, N 2, p.107-116.

227. Скворцова M. И., Баскин И. И., Станкевич И. В., Зефиров Н. С. Об одном способе построения линейных уравнений связи «структура-свойство». Доклады Академии Наук, 1996, т.351, № 1, с. 78-80.

228. Скворцова М. И., Станкевич И. В., Баскин И.И., Палюлин В. А., Зефиров Н. С. Аналитическое описание множества мер подобия молекулярных графов. Доклады Академии Наук, 1996, т.350, № 6, с. 786-788.

229. Зефиров Н. С., Палюлин В. В., Молчанова М. С., Скворцова М. И., Баскин И. И. Структурная генерация и QSAR. Тезисы докладов IV ого Российского научного конгресса «Человек и лекарство»; Москва, 8-12 апреля 1997г.; с. 261.

230. Скворцова М. И., Словохотова О. JL, Баскин И. И., Палюлин В. А., Зефиров Н. С. Обратная задача в проблеме связи «структура-свойство» для случая информационных топологических индексов. Доклады Академии Наук, 1997, т. 357, № 1, с. 72-74.

231. Skvortsova M. I., Baskin I. I., Stankevich I. V., Palyulin V. A., Zefirov N. S. Molecular Similarity. 1. Analitycal Description of Graph Similarity Measures. J. Chem. Inform. Comput. Sci. 1998, v.38, N 5, p. 785-790.

232. Skvortsova M. I., Baskin I. I., Skvortsov L. A., Palyulin V. A., Zefirov N. S., Stankevich I. V. Chemical Graphs and Their Basis Invariants. J. Mol. Struct. (THEOHEM), 1999, v. 466, p. 211-217.

233. Станкевич И. В., Чистяков А. Л., Скворцова М. И. Исследование структуры и свойств некоторых эндоэндральных кластеров и обобщение понятия молекулярной топологической формы. Известия РАН, сер. химическая, 1999, № 3, с. 436-440.

234. Скворцова М. И., Станкевич И. В. Теория графов в структурной химии. Молекулярные графы. Часть I. (Учебно-методическое пособие; Изд-во МИТХТ), 1998, 88 с.

235. Скворцова M. И., Федяев К. С., Палюлин В. А., Зефиров Н. С. О вероятностном подходе к определению области применимости уравнений связи «структура-свойство». Доклады Академии Наук, 2000, т. 375, № 1, с. 46-49.

236. Пасюков А. В., Скворцова М. И., Палюлин В. А., Зефиров Н. С. Метод прогнозирования свойств химических соединений, основанный на оптимальном подборе меры молекулярного подобия. Доклады Академии Наук, 2000, т. 374, № 6, с.786-789.

237. Скворцова М. И., Станкевич И. В. Теория графов в структурной химии. Спектры графов и их применение в теории сопряженных молекул. Часть П.(Учебно-методическое пособие), Москва, МИТХТ им. М. В. Ломоносова, 2001, 64 с.

238. Скворцова М. И., Федяев К. С., Палюлин В. А., Зефиров Н. С. Обратная задача в проблеме связи «структура-свойство» для случая корреляционного уравнения, содержащего индекс Хосойя. Доклады Академии Наук, 2001, т. 379, №2, с. 209-213.

239. Скворцова М. И., Федяев К. С., Баскин И.И., Палюлин В. А., Зефиров Н.С. Новый способ кодирования химических структур на основе базисных фрагментов. Доклады Академии Наук, 2002, т. 382, № 5, с. 645-648.

240. Скворцова M. И., Федяев К. С., Палюлин В. А., Зефиров Н. С. Моделирование связи между структурой и свойствами углеводородов на основе базисных топологических дескрипторов. Известия АН (сер. химическая), 2004, №8, с. 1527-1535.

241. Скворцова М. И., Станкевич И. В. О связи между собственными векторами взвешенных графов и их подграфами. Дискретная математика, 2004, т. 16, вып. 4, с. 32-40.

242. Skvortsova М. I., Stankevich I. V. Eigenvectors of Weighted Graphs: Supplement to Sachs' Theorem. J. Mol. Struct. (THEOCHEM), 2005, v.719, p. 213-223.

243. Скворцова М. И., Станкевич И. В., Палюлин В. А., Зефиров Н. С. Концепция молекулярного подобия и ее применение для прогнозирования свойств органических соединений// Успехи химии.- 2006.-т.75.-№11.- с. 1074-1093.