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

Московский государственный университет имени М.В. Ломоносова Механико-математический факультет

Деветьяров Дмитрий Александрович

ИСПОЛЬЗОВАНИЕ НЕЧЕТКОЙ ЛОГИКИ ПРИ ОПИСАНИИ МОЛЕКУЛ В ЗАДАЧЕ «СТРУКТУРА-СВОЙСТВО»

05.13.17 - теоретические основы информатики

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

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

Москва-2010

004600930

004600930

Работа выполнена на кафедре вычислительной математики Механико-математического факультета Московского государственного университета имени М.В.Ломоносова.

Научный руководитель: доктор физико-математических наук

Кумсков Михаил Иванович

Официальные оппоненты: доктор физико-математических наук,

профессор Персиянцев Игорь Георгиевич

кандидат физико-математических наук, старший научный сотрудник Афонин Сергей Александрович

Ведущая организация: Вычислительный центр

имени А. А. Дородницына РАН

Защита состоится 28 апреля 2010 г. в 16 час. 45 мин. на заседании диссертационного совета Д.501.002.16 при Московском государственном университете имени М.В. Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д.1, Московский государственный университет имени М.В. Ломоносова, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан 27 марта 2010 года

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

диссертационного совета Д.501.002.16 при МГУ доктор физико-математических наук

А.А. Корнев

Общая характеристика работы

Актуальность

Задача поиска количественных корреляций «структура-свойство»1 (Quantitative Structure-Activity Relationship, QSAR-задача), то есть задача предсказания физико-химической или биологической активности вещества исходя из его структуры, является ключевой проблемой математической химии. Математические модели «структура-свойство» широко используются на практике, как для предсказания активности веществ, так и для поиска новых соединений с заданными химико-биологическими свойствами. Данные модели позволяют значительно сохфатить расходы и время, необходимое для исследований, при синтезе новых соединений с заданными свойствами.

Особенно широкое развитие методы QSAR получили в последние 10-15 лет в связи с тем, что появились возможности для компьютерного хранения больших объемов данных о структуре всевозможных молекул и их активности, а также в связи с тем, что сильно повысилась производительность вычислительных систем, являющаяся критичной для ряда методов решения задачи QSAR.

В настоящее время разработано несколько разных подходов к решению QSAR-задачи. Как правило, QSAR-задача разбивается на две подзадачи:

1) преобразование информации о молекулярной структуре в вектора численных признаков (дескрипторов);

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

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

1 Karelson M. Molecular Descriptors in QSAK/QSPR. Wiley-iaterscienee, 2000 f < '

2 Розенблит А. Б., Голендср В. Е. Логихо-комбинаторные методы в конструировании лекарств.— Рига: Зинатне, 1984,—352 с.

Разработанный в работе метод развивает данное направление, однако направлен на избавление от ряда недостатков, которыми обладают классические структурные дескрипторы:

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

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

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

Кроме того, сформулированы следующие требования к разработанному методу:

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

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

Цель работы

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

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

2. Разработать алгоритм формирования алфавита нечетких структурных ЗО-дескрипторов.

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

4. Оценить вычислительную сложность разработанных алгоритмов.

5. Реализовать разработанные алгоритмы, провести вычислительные эксперименты.

Научная новизна

1. Предложен новый метод представления информации о структуре молекулярных графов семействами четких и нечетких структурных ЗО-дескрипторов.

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

3. Подтверждена практическая значимость подхода в серии вычислительных экспериментов по прогнозированию биологической активности органических соединений.

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

Практическая значимость

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

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

Апробация работы

Материалы диссертации докладывались и обсуждались на 8-ой международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» ("Pattern Recognition and Image Analysis: New Information Technologies", PRIA-8-2007), Международной научной конференции «Компьютерные науки и информационные технологии» (2009 г.), 14-ой Всероссийской конференции «Математические методы распознавания образов» ММРО-2009 (2009 г.), Молодежной конференции «Молекулярный дизайн и синтез веществ с заданной физиологической активностью» (химический факультет МГУ им. М,В. Ломоносова, 2006 г.). Полученные результаты также неоднократно обсуждались на научных семинарах Механико-математического факультета МГУ им. М.В. Ломоносова и Института Органической Химии им. Н.Д.Зелинского РАН.

Публикации по теме диссертации

По материалам диссертации опубликовано 12 научных работ [1-12]. Из них - четыре работы [4, 10, 11, 12] представлены в журналах из перечня ведущих научных журналов и изданий, рекомендованных ВАК РФ.

Структура и объем диссертации

Работа состоит из введения, 3 глав, заключения, списка литературы и приложения. Общий объем диссертации 110 страниц без приложения. Список литературы содержит 93 наименования.

Краткое содержание работы

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

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

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

молекул - молекулярными графами3, молекулярными поверхностями4, наборами особых точек.

Определение (задача «структура-свойство»). Пусть задано обучающее множество молекул ¿5 = (.М„у,), / = 1, в котором каждая молекула М, задана одним из описанных выше способов и отнесена к некоторому классу активности Ак,к = 1,...,К, который можно описать меткой ^,1 = 1,или имеет некоторое значение свойства. Пусть также задан ^ - некоторый класс функций. Необходимо:

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

2. (Этап анализа) Выбрать функцию /е .Р, получающую в качестве аргумента вектор дескрипторов молекулы и наилучшим образом относящую молекулу к одному из К классов активности или предсказывают значение свойства у,, / = 1,...,Яв смысле некоторого функционала качества <р{/).

В разделе 12 проводится обзор существующих методов представления информации о молекуле на этапе описания задачи «структура-свойство», а также перечисляются их недостатки. Рассмотрены методы на основе описания молекул топологическими дескрипторами (теоретико-графовыми индексами)5, а также структурными дескрипторами6, характеризующими наличие, количество, и взаимное расположение в молекуле определенных структурных фрагментов (атомов, связей и т.д.). Описаны методы решения задачи ЗО-С^АК7 путем вложения молекул в трехмерное пространство с регулярной сеткой.

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

1 Rouvray D.H. (Ed.) Computational Chemical Graph Theoiy. /Nova Publ., New York, 1989

* Lee, В., Richards F.M. The interpretation of protein structures: Estimation of static accessibility. Journal of Molecular

Biology, vol. 55,1971, pp.379-400

' Randic M. On Characterization of Molecular Branching. Journal of the American Chemical Society, 1975, vo.97,

pp.6609-6615

Carhart R et al. Atom Pairs as Molecular Features in Structure-Activity Studies: Definition and Applications. J. Chem. Inf. Comput. Sci.; 1985; 25(2) pp 64-73

7 Lowis D. R. HQSAR. A New, Highly Predictive QSAR Technique. Tripos Technical Notes; Oct 1997; VoL 1, No. 5 ' Ивахненко А.Г„ Зайченко Ю.П., Димитров В.Д. Принятие решений ва основе самоорганизации. М.: Сов.

Радио,1976

Во второй главе диссертации приведена постановка задачи данной работы, описаны разработанные методы и алгоритмы решения поставленной задачи

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

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

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

Далее, приведены разработанные методы и алгоритмы описания молекулярных поверхностей.

Пусть задано обучающее множество вида (М„у,), i=l,...,N, где каждая молекула представлена набором выбранных по предварительно заданному алгоритму особых точек М, = {Р/}^, для каждой точки Р/ заданы ее координаты (x/._y/,z/) и вектор физико-химических свойств (p/J,...,p/'I')e RL.

Положим р'Ып = min pjJ, р'^ = max pjJ, d^ - максимум по всей выборке всех '•У

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

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

В случае четких дескрипторов для каждого I, \<1<L, отрезок [p^.p^J разбивается на п, подотрезков - классов значений свойств. В зависимости от принадлежности значения каждого свойства классам значений, каждой особой точке Р' присваивается метка "/,...iL", такая что значение свойства p/J принадлежит отрезку значений Символьное кодирование меток порождает алфавит дескрипторов первого уровня AD1 = {At, Л2, ..., Ai},Aj < А2 < ...< А/ -множество всех полученных символьных меток. Положим, что дескриптору Л,

б

соответствуют те и только химические функциональные группы б, которые состоят ровно из одной особой точки иб = {Л/}.

На отрезке [0, с^] вводятся Р интервалов расстояний. По индукции по уровню дескрипторов формируются алфавиты дескрипторов высших уровней АО2, АО1, ... (для пар, троек особых точек и т.д.). Пусть уже построены алфавиты АО2, АО3,..., АО" и необходимо построить алфавит дескрипторов (п + 1)-ого уровня А1?л' и задать соответствие между сформированными дескрипторами и химическими функциональными группами. К каждому из дескрипторов в АО" добавляется новая особая точка А,АеАО, которая лексикографически не меньше, чем метка любой особой точки дескриптора из АО"\ алфавит дескрипторов следующего уровня определяется как ЛЯ"+1 = {(АЛ,с)|£еЖ)\ АеАО, АкВ ЧВ&О, с = 1,..,/>).

Теперь, для того чтобы определить соответствие между химической функциональной группой в и произвольным дескриптором £> = (Дл,с)е АО"*1, необходимо проверить, можно ли разбить б на 2 такие группы (7/ и (состоящие из и и 1 особых точек соответственно), что фрагменту <?/ соответствует дескриптор О и б; = {А}. Если такое разбиение возможно, вычисляется расстояние р(А, между б) и = {А} (в качестве расстояния рассматривается наименьшее, наибольшее или среднее из всех расстояний между А и каждой из особых точек С). Химическая функциональная группа С соответствует дескриптору О тогда и только тогда, когда расстояние р(А, принадлежит интервалу разбиения с.

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

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

Вышеизложенный метод модифицирован в разделе 23 с помощью аппарата нечеткой логики в метод описания нечеткими структурными ЗБ-дескрипторами.

В подразделе 23.1 даны общие понятия аппарата нечеткой логики9: даны определения нечеткого множества, функций принадлежности, операций над нечеткими множествами и систем логического вывода. Кратко описаны

9 ХайсЬ Ь.А. Рилу Шопшйюп еш<1 Сопйо!, 1965, рр. 338-353

существующие методы решения задачи «структура-свойство» с использованием методов нечеткой логики. Рассмотрены подходы к описанию молекул структурными дескрипторами с введением нечетких множеств и функций принадлежности на множестве расстояний; подходы, основанные на использовании систем нечеткого логического вывода Мамдани10 и Такаги-Сугено11. Указаны недостатки таких подходов, в частности, невозможность сформулировать до решения задачи «структура-свойство» правила логического вывода экспертно и ограниченная применимость нечеткого логического вывода в силу большого числа дескрипторов.

В подразделе 2.3.2 вводятся понятия нечетких классов особых точек и расстояний.

Для каждого свойства /, \<1<Ь, необходимо выбрать некоторое число п, нечетких классов и п, функций принадлежности Я,',...,^,^':^,/)^]-»^,!], задающие нечеткие множества Д'В результате, для каждой особой точки Р с вектором свойств {р\...,р1)еЯ.1 в ¿-мерном параллелепипеде

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

различным нечетким классам особых точек по каждому из физико-химических свойств.

Аналогично вводятся нечеткие классы расстояний: на отрезке [О,*^} определяются б нечетких множеств Д,...,£)е, заданных функциями принадлежности :ЦО,¿^щах] —>■ [0,13- Введенные нечеткие множества

определяют степени принадлежности у,(с/).....уе(</) произвольного расстояния

(I е [0, й^ ] к () нечетким классам расстояний.

На основе введенных нечетких классов особых точек и расстояний, разработан метод построения алфавита нечетких структурных ЗБ-дескрипторов, изложенный в разделе 2.3.3.

При формировании всевозможных декартовых произведений вида А^, где 1< г, ^«р.,.,1 </'у < пр...,\<11 < п1, функция принадлежности

точки Р=(р1,...,р1')е Л1" к нечеткому множеству такого вида записывается в

ь

виде = ц\{р1)-...■. Множество построенных нечетких

множеств обозначим через А

10 Mamdani E.H. Application of fuzzy algorithms for control of a simple dynamic plant Proceedings of IEEE, vol.121, pp.1585-1588,1974

Takagi T,, Sugeao M. Fuzzy identification of systems and its applications to modelling and control, IEEE Transactions on Systems, man, and Cybernetics, vol.15, pp. 116-132, 1985

Далее, для каждой особой точки, определяется степень ее принадлежности к каждому нечеткому множеству /"/„..д , 15 5 л,, и производится суммирование данных степеней принадлежности для каждого нечеткого множества. Таким образом, алфавит дескрипторов первого уровня АО1 сформирован перечислением символьных строк вида "щ—Ь", 1 < <, соответствующих нечетким множествам . Для каждого дескриптора такого вида его значение для молекулы М с особыми точками Р1,—,Рп определяется как

(о

1-1

Алфавит дескрипторов АО2 для пар особых точек строится следующим образом. Рассмотрим декартово произведение вида А^х АххВ. Его элементами являются нечеткие множества - декартовы произведения нечетких множеств вида

И х Л2 * -х 4 > (4х 4х -х < > А (2)

для всевозможных наборов Чтобы избежать

повторения, рассмотрены только элементы, в которых (г,,^,...,^) < 2 >--,Л) (лексикографический порядок). Таким образом, получен набор из

21^4(1^4+1)

—1-^-!-нечетких множеств вида (2).

Для произвольной пары особых точек (Р:,Р2), находящихся на расстоянии р(Р1,Р2) друг от друга, ее степень принадлежности к множеству вида (2) записывается в виде

Я,л* {р2)^{р{Р,А)) О)

Алфавит дескрипторов второго уровня АО2 формируется перечислением всевозможных символьных строк вида "г,^...;^',^...^^", где сохраняется лексикографическое упорядочивание и 1 ^ ^ ^ б • Для

каждого дескриптора такого вида его значение для молекулы М с особыми точками Р1,...,Р„ определяется как сумма степеней принадлежности всех структурных 2-фрагментов молекулы соответствующему нечеткому множеству, т.е.:

^Скь-Ш-лП=(4)

/,т-1

Аналогично, можно построить алфавит АО1, рассмотрев декартовы произведения вида А'х А1хВх Л'х О и в них элементы, для которых сохраняется лексикографический порядок. В результате, формируется набор из

агш\+\)Ао1<\щ-\)

—-1-1-1-1- нечетких множеств с функциями принадлежности

6

вида

ЯМ) = Мр^МЪЪШЪК Р2).^з)) (5)

Каждый дескриптор представляет собой символьную строку "^•••'¿ЛЛ-Л^^Л-^^г"» где сохраняется лексикографическое упорядочивание (i^,iг,...,iL)ZU\>j2>•^•>jL)í(kl>k2>■^■>kl) и 1< А,,Значение такого дескриптора для молекулы М с особыми точками Ри.~,Р„ равно сумме степеней принадлежности всех структурных 3-фрагментов молекулы соответствующему нечеткому множеству, т.е.:

Е ^¡м^пР.А) (6)

где р((Р„Рк),Рч) - расстояние от пары особых точек (Р,,Рт) доРц в смысле наименьшего, наибольшего или среднего из расстояний р(РпРч) и р(Р„,Рч) ■

Сходным образом можно усложнять описание далее, построив алфавиты АО*,...,АОр. Объединив построенные алфавиты, получим алфавит дескрипторов АО - АО1 и АО2 и... и АОр.

Доказана теорема о том, что алфавит четких дескрипторов является частным случаем алфавита нечетких дескрипторов.

Теорема. Для любого алфавита четких дескрипторов, порожденного разбиением отрезков [р^.р^на л, подотрезков и отрезка [0, на О подотрезков, существуют семейства нечетких функций принадлежности = и у,,...,^;^. :[0,с/,*,]->[0,1], такие что

алфавит и значения нечетких дескрипторов, порожденных функциями принадлежности ^¡,...,^,¡=1 совпадают с алфавитом и

значениями четких дескрипторов.

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

В подразделе 2.4.1 приводится общая схема алгоритма оптимизации описания:

1. Формируется начальный алфавит дескрипторов АО0, в котором функции принадлежности строятся на основе гипотез о пространственных структурах, отвечающих за исследуемую активность.

2. Строится матрица «молекула-признак» обучающего множества в текущем алфавите.

3. По построенной матрице «молекула-признак» выбирается наилучшая линейная предсказывающая модель / для свойства у в смысле функционала качества (рф.

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

5. Проводится обучение схемы с тем, чтобы максимизировать функционал качества классификации.

Общий вид рассматриваемой схемы приведен на рис. 1.

Рис.1. Схема функциональных элементов для оптимизации алфавита дескрипторов

В подразделе 2.4.2 приведен алгоритм формирования начального алфавита дескрипторов. В подразделе 2.4.3 доказана

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

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

А <9<р

первого слоя и каждый из параметров сдвигается на Аа=т] —, где т] -

да

коэффициент сдвига, выбираемый отдельно.

На втором проходе ищется оценка наименьших квадратов, получаемая вычислением у/ = (ХтХ)~1Хту, где Х- матрица «молекула-признак» размера ЛГхМ, построенная применением к молекуле функциональных элементов слоя 1, н;=(уу,,..., н>и), у - прогнозируемый вектор классов активности молекул обучающего множества.

Оценка наименьших квадратов может быть получена либо прямым вычислением, либо итерационно, в случае если велико число обусловленности матрицы ^Х)'1.

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

• Реализовано эволюционное построение дескрипторов: дескрипторы п-ого порядка формируются на основе наиболее информативных дескрипторов (л-1)-ого порядка.

• Осуществляется поиск разных функций принадлежности для расстояний между разными типами структурных фрагментов. В частности, происходит отдельное разбиение интервала расстояний для каждой пары меток ОТ / пары дескриптора (л-1)-ого порядка и метки ОТ.

• Рассматриваются только структурные фрагменты (пары и тройки ОТ), присутствующие не менее чем в определенной доле соединений.

• Осуществляется оптимизация функций принадлежности по угловому коэффициенту.

Особенности данного алгоритма позволяют добиться следующего:

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

• обеспечить распространенность задействованных дескрипторов;

• оптимизировать тип используемых функций принадлежности.

В разделе 2.6 приведена оценка сложности предложенного алгоритма. Обозначим через Т число меток (типов) ОТ; £)* - число нечетких множеств, заданных на интервале значений расстояния между структурным фрагментом к-ого уровня (ОТ, парой или тройкой ОТ) и ОТ; (3 - количество наиболее информативных дескрипторов, на основе которых формируются дескрипторы следующего уровня (в случае применения МГУА в качестве классифицирующей функции, равно глубине МГУА, умноженной на рассматриваемое число лучших моделей). ¿'04шк, ^*гас, - количество

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

построении, соответственно; , Еки!у1 - аналогичные показатели для

этапа построения классифицирующей модели с МГУА как алгоритмом построения модели. Справедлива

Теорема. Имеют место следующие оценки:

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

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

В разделе 3.1 описана программная реализация алгоритма. Раздел 3.1.1 детально приводит этапы расчета пространственной структуры и электростатического заряда молекулярных графов, построения триангулированных молекулярных поверхностей, нахождения и маркировки особых точек. Реализация этапов формирования матрицы «молекула-признак» и поиска классифицирующей функции в среде МАТЬАВ приведена в разделе 3.1.2.

В разделе 32 описаны использованные методы построения классифицирующей функции:

• МГУА на кластерах;

• МГУА, использующий в качестве опорных функций конъюнкции и дизъюнкции ряда дескрипторов [10];

• АЛИБ12 на главных компонентах13;

• МГУА с использованием метода ближайших соседей (МГУА-к№Ч) [9].

12 J.-S. Roger Jang, С.-Т. Sun and Е. Mizutani, "Neuro-Fuzzy and Soft Computing: a computational approach to learning and machine intelligence," 1996, to be published by Prentice-Hall

13 Харман Г. Современный факторный анализ: Пер. с англ., - М.: Статистика, 1972,486с

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

• выборка гликозидов, протестированная на противоопухолевую активность;

• выборка соединений бициклической мочевины, протестированных на общую токсичность и транквилизирующую активность.

Проведено сравнение результатов при применении четких дескрипторов, а также при различных модификациях алгоритма с использованием нечетких дескрипторов. Результаты численных экспериментов подтвердили эффективность и перспективность методов и алгоритмов, разработанных на основе аппарата нечеткой логики: при обработке определенными методами машинного обучения (например, МГУА-кИИ для выборки бициклических бисмочевин и АЛИВ на главных компонентах для выборки гликозидов) наблюдалось заметное улучшение качества прогноза при переходе от четкого описания молекулярной структуры к нечеткому. При использовании остальных методов машинного обучения четкие и нечеткие дескрипторы приводят к сопоставимым результатам.

В частности, на выборке бициклической мочевины среднее качество прогноза методом МГУА-ШЫ улучшается при продвижении от более четких функций принадлежности к более нечетким: 78.0% для четких функций принадлежности, 82.6% для нечетких трапециевидных, 86.3% для нечетких треугольных. При этом максимальное значение качества прогноза 96.9% также достигается при использовании треугольных функций принадлежности

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

В приложении приведено описание обработанных выборок химических соединений.

Основные результаты диссертации, выносимые на защиту

1. Разработаны методы представления информации о пространственных конфигурациях молекул и молекулярных поверхностях с помощью четких и нечетких структурных ЗО-дескрипторов.

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

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

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

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

Благодарность

Автор выражает глубокую признательность своему научному руководителю д.ф.-м,н. Кумскову Михаилу Ивановичу на постановку задач, постоянное внимание к работе и многочисленные плодотворные обсуждения. Автор также выражает благодарность заведующему кафедрой вычислительной математики д.ф.-м.н. профессору Кобелькову Георгий Михайловичу и всем сотрудникам кафедры за творческую атмосферу и поддержку, а также д.х.н. Кравченко Ангелине Николаевне (Институт органической химии имени Н.Д. Зелинского РАН) и к.б.н. Апрышко Галине Николаевне (Российский онкологический научный центр имени H.H. Блохина) за предоставление выборок бицикпических мочевин и гликозидов.

Список опубликованных работ по теме диссертации

Основные результаты диссертации содержатся в следующих статьях:

1) I.V. Svitanko, D.A. Devetyarov, D.E. Tcheboukov, M. S. Dolmat, A.M. Zakharov, S.S. Grigoryeva, V.T. Chichua, L.A. Ponomareva, M.I. Kumskov. QSAR Modeling on the Basis of 3D Descriptors Representing the Electrostatic Molecular Surface (Ambergris Fragrances) // Mendeleev Communications. - 2007. - Vol.17, No. 2. -P. 90-91. (Автору диссертации принадлежит реализация алгоритма и проведение численных экспериментов)

2) D.A. Devetyarov, A.M. Zaharov, M.I. Kumskov, L.A. Ponomareva. Fuzzy logic application for construction of 3D descriptors of molecules in QSAR problem. // Proceeding of the 8th International Conference "Pattern Recognition and Image

Analysis: New Information Technologies" (PRIA-8-2007) - 2007. - Vol.2. - P.249-252. (Автору диссертации принадлежат разработанный алгоритм и результаты вычислительных экспериментов)

3) S.S. Grigoreva, M.I. Kumskov, А.М. Zaharov, D.A. Devetyarov, L.A. Ponomareva, I.V. Svitanko. Search of 3D structure representation of flexible molecules adequate to the given biological activity // Proceeding of the 8th International Conference "Pattern Recognition and Image Analysis: New Information Technologies" (PRIA-8-2007)-2007.- Vol.2. - P.262-265. (Автору диссертации принадлежат реализация алгоритма и проведение численных экспериментов)

4) Григорьева С.С., Чичуа В.Т., Деветьяров Д.А., Кумсков М.И. Выбор оптимального описания структуры молекулы в задаче структура-свойство для заданной биологической активности // Вестник Московского Университета. Серия 2. Химия. - 2007. - Т. 48, N 5. - С. 305-307. (Автору диссертации принадлежат реализация алгоритма и проведение численных экспериментов)

5) Деветьяров Д.А., Григорьева С.С., Пермяков Е.А., Кумсков М.И., Пономарева JI.A., Свитанько И.В. Решение задачи «структура-свойство» для молекул с множеством пространственных конформаций // Система прогнозирования свойств химических соединений: Алгоритмы и модели. Сборник научных работ. - М.: МАКС Пресс, 2008. - С. 3-9. (Автору диссертации принадлежат алгоритмы 1 и 2 и результаты экспериментов по выборке зеленого запаха)

6) Григорьева С.С., Деветьяров Д.А., Свитанько И,В., Пермяков Е.А., Апрьппко Г.Н., Кумсков М.И. Поиск представлений 3D структур гибких молекул в задаче прогнозирования биологической активности // Система прогнозирования свойств химических соединений: Алгоритмы и модели. Сборник научных работ. - М.: МАКС Пресс, 2008. - С. 10-36. (Автору диссертации принадлежат разработанные метод и алгоритмы описания гибких молекул)

7) Захаров А.М., Деветьяров Д.А., Кумсков М.И. Решение задачи «структура-активность» с использованием нечетких функций близости (kernel-функций) // Система прогнозирования свойств химических соединений: Алгоритмы и модели. Сборник научных работ. - М.: МАКС Пресс, 2008. - С. 37-50. (Автору диссертации принадлежат разработанный алгоритм (раздел 4) и доказательство теоремы 1)

8) Деветьяров Д.А., Кумсков М.И., Апрышко Г.Н., Носеевич Ф.М., Прохоров Е.И., Перевозников A.B., Пермяков Е.А. Сравнительный анализ применения нечетких дескрипторов при решении задачи «структура-свойство» // Доклады

14-ой Всероссийской конференции «Математические методы распознавания образов» ММРО-2009. - М: МАКС Пресс. - 2009. - С. 511-514. (Автору диссертации принадлежит метод и алгоритм формирования дескрипторов, экспериментальные результаты на этапе описания, а также экспериментальные результаты на этапе анализа методом МГУА)

9) Носеевич Ф.М., Деветьяров Д.А., Кумсков М.И., Апрышко Г.Н., Пермяков Е.А. Двоичный метод группового учета аргументов в задаче «структура-свойство» // Доклады 14-ой Всероссийской конференции «Математические методы распознавания образов» ММРО-2009. - М: МАКС Пресс. - 2009. - С. 575-578. (Автору диссертации принадлежит метод и алгоритм формирования дескрипторов, экспериментальные результаты на этапе описания)

10) Деветьяров Д.А. Нечеткие дескрипторы молекул в задаче «Структура-свойство» И Информационные технологии. - 2010. - №3.

11) Деветьяров Д.А., Кумсков М.И. Использование нейронных сетей в задаче «структура-свойство» с использованием нечеткого описания пространственных структур молекул // Нейрокомпьютеры: разработка, применение. - № 3. - С. 14-19. (Автору диссертации принадлежат метод создания искусственных нейронных сетей на основе кусочно-линейных моделей «Структура-свойство» и экспериментальные результаты)

12) Деветьяров Д.А. Эволюционное построение алфавита дескрипторов, сформированных на основе аппарата нечеткой логики, в задаче «структура-свойство» // Системы управления и информационные технологии. - 2010. -20Ю.-№ 1.1 (39).-С. 131-134.

Подписано в печать 25.0i.i0 Формат 60x90 1/16. Усл. печ. л. ¿2$ Тираж (00 экз. Заказ 19

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета МГУ имени М.В.Ломоносова

Введение.

Глава 1. Задача «структура-свойство» и существующие методы ее решения.

1.1 Общая постановка задачи «структура-свойство».

1.1.1 Описание обучающего множества.

1.1.2 Постановка задачи.

1.2 Существующие методы описания молекул.

1.2.1 Параметрическое описание молекул топологическими дескрипторами

1.2.2 Параметрическое описание молекул структурными дескрипторами

1.2.3 3D-QSAR анализ трехмерных молекул.

1.3 Методы построения прогнозирующей функции.

Выводы.

Глава 2. Метод представления информации о структуре молекул четкими и нечеткими дескрипторами.

2.1 Постановка задачи в работе.

2.2 Метод описания молекулярной структуры четкими структурными 3D-дескрипторами.

2.3 Применение аппарата нечеткой логики при формировании структурных 3D-дескрипторов.

2.3.1 Нечеткая логика и существующие методы решения задачи «структура-свойство» с помощью нечеткой логики.

2.3.2 Нечеткие классы особых точек и расстояний.

2.3.3 Алфавит нечетких структурных 3D-дескрипторов и вычисление их значений.

2.4 Оптимизация описания нечеткими дескрипторами как демонстрация преимущества нечетких дескрипторов.

2.4.1 Общая схема алгоритма оптимизации.

2.4.2 Формирование начального алфавита дескрипторов.

2.4.3 Оптимизация алфавита дескрипторов с использованием нейронной сети.

2.5 Алгоритм решения задачи «структура-свойство» с помощью нечетких дескрипторов.

2.5.1 Эволюционный отбор.

2.5.2 Описание алгоритма.

2.6 Оценка вычислительной сложности.

Выводы.

Глава 3. Экспериментальные результаты.

3.1 Программная реализация алгоритма.

3.1.1 Построение молекулярной поверхности, особых точек.

3.1.2 Формирование матрицы «молекула-признак» и поиск классифицирующей функции в среде MATLAB.

3.2 Использованные методы построения классифицирующей функции.

3.3 Описание результатов.

3.3.1 Обработка выборки бициклических бисмочевин.

3.3.2 Обработка выборки гликозидов.

Выводы.

Задача поиска функциональной зависимости «Сруктура-свойство» (Quantitative Structure-Activity Relationship, QSAR-задача) [170шибка! Источник ссылки не найден., 2], то есть задача предсказания физико-химической или биологической активности вещества исходя из его структуры, является ключевой проблемой математической химии. Математические модели «структура-свойство» широко используются на практике, как для предсказания активности веществ, так и для поиска новых соединений с заданными химико-биологическими свойствами. Данные модели позволяют значительно сократить расходы и время, необходимое для исследований, при синтезе новых соединений с заданными свойствами.

Особенно широкое развитие методы QSAR получили в последние 10-15 лет в связи с тем, что появились возможности для компьютерного хранения больших объемов данных о структуре всевозможных молекул и их активности, а также в связи с тем, что сильно повысилась производительность вычислительных систем, являющаяся критичной для ряда методов решения задачи QSAR.

В настоящее время разработано несколько разных подходов к решению QSAR-задачи. Как правило, QSAR-задача разбивается на две подзадачи:

1) преобразование информации о молекулярной структуре в вектора численных признаков (дескрипторов);

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

За последние несколько десятилетий разработано большое число методов решения QSAR-задачи, при этом методы различаются, главным образом, методом описания молекул в векторном пространстве признаками дескрипторами). Классический метод был предложен Розенблитом и Голендером [72], которые использовали понятие «фармакофор» - набор структурных признаков в молекуле, которые отвечают за биологическую активность молекулы. Данный метод выделяет группы или цепочки атомов в структуре молекулы и находит функциональную зависимость между наличием тех или иных групп или цепочек и биологической активностью.

Метод, разработанный в этой работе, развивает данное направление, однако ориентирован на избавление от ряда недостатков, которыми обладают классические методы описания:

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

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

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

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

Кроме того, мы выдвигаем следующие требования к разрабатываемому методу:

1. Метод должен позволять содержательную интерпретацию дескрипторов, используемых в моделях, отражающих функциональную зависимость между структурой и свойством. Некоторые современные методы (например, топологические индексы [7373,69]) не обладают данным свойством.

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

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

В соответствии с целью были поставлены и решены следующие задачи:

1. Разработка метода представления информации о пространственных конфигурациях молекул с помощью нечетких структурных 3D-дескрипторов.

2. Разработка алгоритма формирования алфавита нечетких структурных 3D-дескрипторов.

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

4. Оценка вычислительной сложности разработанных алгоритмов.

5. Реализация разработанных алгоритмов, проведение вычислительных экспериментов.

Научная новизна работы состоит в следующем:

1. Предложен новый метод представления информации о структуре молекулярных графов семействами четких и нечетких структурных 3D-дескрипторов.

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

3. Подтверждена практическая значимость подхода в серии вычислительных экспериментов по прогнозированию биологической активности органических соединений.

Научные результаты, выносимые на защиту, состоят в следующем:

1. Разработаны методы представления информации о пространственных конфигурациях молекул и молекулярных поверхностях с помощью четких и нечетких структурных ЗО-дескрипторов.

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

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

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

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

Материалы диссертации докладывались и обсуждались на 8-ой международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» ("Pattern Recognition and Image Analysis: New Information Technologies, PRIA-8-2007), Международной научной конференции "Компьютерные науки и информационные технологии" (2009 г.), 14-ой Всероссийской конференции «Математические методы распознавания образов» ММРО-2009 (2009 г.), Молодежной конференции "Молекулярный дизайн и синтез веществ с заданной физиологической активностью" (химический факультет МГУ им. М,В. Ломоносова, 2006 г.). Полученные результаты также обсуждались на научных семинарах механико-математического факультета МГУ им. М.В. Ломоносова и Института Органической Химии им. Н.Д.Зелинского РАН. По материалам диссертации опубликовано 12 научных работ. Основные результаты диссертации содержатся в следующих статьях:

1. I.V. Svitanko, D.A. Devetyarov, D.E. Tcheboukov, M. S. Dolmat, A.M. Zakharov, S.S. Grigoryeva, V.T. Chichua, L.A. Ponomareva, M.I. Kumskov. QSAR Modeling on the Basis of 3D Descriptors Representing the Electrostatic Molecular Surface (Ambergris Fragrances) // Mendeleev Communications. - 2007. - Vol.17, No. 2. - P. 90-91.

2. D.A. Devetyarov, A.M. Zaharov, M.I. Kumskov, L.A. Ponomareva. Fuzzy logic application for construction of 3D descriptors of molecules in QSAR problem. // Proceeding of the 8th International Conference "Pattern Recognition and Image Analysis: New Information Technologies" (PRIA-8-2007) - 2007. - Vol.2. - P.249-252.

3. S.S. Grigoreva, M.I. Kumskov, A.M. Zaharov, D.A. Devetyarov, L.A. Ponomareva, I.V. Svitanko. Search of 3D structure representation of flexible molecules adequate to the given biological activity // Proceeding of the 8th International Conference "Pattern Recognition and Image Analysis: New Information Technologies" (PRIA-8-2007) - 2007. - Vol.2. - P.262-265.

4. Григорьева С.С., Чичуа В.Т., Деветьяров Д.А., Кумсков М.И. Выбор оптимального описания структуры молекулы в задаче структура-свойство для заданной биологической активности // Вестник Московского университета. Серия 2. Химия. - 2007. - Т. 48, N 5. - С. 305-307.

5. Деветьяров Д.А., Григорьева С.С., Пермяков Е.А., Кумсков М.И., Пономарева JI.A., Свитанько И.В. Решение задачи "структура-свойство" для молекул с множеством пространственных конформаций // Система прогнозирования свойств химических соединений: Алгоритмы и модели. Сборник научных работ. - М.: МАКС Пресс, 2008. - С. 3-9.

6. Григорьева С.С., Деветьяров Д.А., Свитанько И.В., Пермяков Е.А., Апрышко Г.Н., Кумсков М.И. Поиск представлений 3D структур гибких молекул в задаче прогнозирования биологической активности //

Система прогнозирования свойств химических соединений: Алгоритмы и модели. Сборник научных работ. - М.: МАКС Пресс, 2008. — С. 10-36.

7. Захаров A.M., Деветьяров Д.А., Кумсков М.И. Решение задачи «структура-активность» с использованием нечетких функций близости (kernel-функций) // Система прогнозирования свойств химических соединений: Алгоритмы и модели. Сборник научных работ. - М.: МАКС Пресс, 2008. - С. 37-50.

8. Деветьяров Д.А., Кумсков М.И., Апрышко Г.Н., Носеевич Ф.М., Прохоров Е.И., Перевозников А.В., Пермяков Е.А. Сравнительный анализ применения нечетких дескрипторов при решении задачи «структура-свойство» // Доклады 14-ой Всероссийской конференции «Математические методы распознавания образов» ММРО-2009. - М: МАКС Пресс. - 2009. - С. 511-514.

9. Носеевич Ф.М., Деветьяров Д.А., Кумсков М.И., Апрышко Г.Н., Пермяков Е.А. Двоичный метод группового учета аргументов в задаче «структура-свойство» // Доклады 14-ой Всероссийской конференции «Математические методы распознавания образов» ММРО-2009. — М: МАКС Пресс. - 2009. - С. 575-578.

10.Деветьяров Д.А. Нечеткие дескрипторы молекул в задаче «Структура-свойство» // Информационные технологии. - 2010. — №3. — С. 73-74.

11. Деветьяров Д.А., Кумсков М.И. Использование нейронных сетей в задаче «структура-свойство» с использованием нечеткого описания пространственных структур молекул // Нейрокомпьютеры: разработка, применение. - № 3. - С. 14-19.

12.Деветьяров Д.А. Эволюционное построение алфавита дескрипторов, сформированных на основе аппарата нечеткой логики, в задаче «структура-свойство» // Системы управления и информационные технологии. - 2010.-2010.-№ 1.1 (39).-С. 131-134.

Работа поддержана Российским Фондом Фундаментальных Исследований (РФФИ) по гранту №07-07-00282.

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

Выводы

Предложенный метод построения нечетких дескрипторов реализован и применен к выборкам соединений с различными биологическими свойствами. Проведено сравнение результатов с применением четких дескрипторов, а также при различных модификациях алгоритма с использованием нечетких дескрипторов. Результаты численных экспериментов подтвердили перспективность методики, разработанной на основе аппарата нечеткой логики: при обработке определенными методами машинного обучения (например, МГУА-fcNN для выборки бициклических бисмочевин и ANFIS на главных компонентах для выборки гликозидов) наблюдается заметное улучшение качества прогноза при переходе от четкого описания молекулярной структуры к нечеткому. При использовании остальных методов машинного обучения четкие и нечеткие дескрипторы приводят к сопоставимым результатам.

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

Заключение

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

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

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

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

Создана программная реализация разработанного алгоритма с использованием сред разработки MATLAB и Microsoft Visual Studio. Проведенные вычислительные эксперименты на выборках соединений с различными целевыми свойствами/активностями подтвердили перспективность нечетких дескрипторов: при обработке определенными методами машинного обучения наблюдается заметное улучшение качества прогноза при переходе от четкого описания молекулярной структуры к нечеткому; в остальных случаях четкие и нечеткие дескрипторы приводят к сопоставимым результатам.

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

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

Данную проблему можно решить двумя различными способами.

Прежде всего, можно ввести распределение вероятностей Р расстояния между каждой парой особых точек РУ,Р2 на отрезке [0,б?тах]. Такое распределение может быть как дискретным (в случае, если у молекулы существует несколько конформаций, которые она принимает с некоторой вероятностью), так и непрерывным. В любом случае, можно переписать формулу (11) в виде интеграла Лебега тзх

J ,.,iL)мл,.JL{Pi)vk(t)P(dt) . (31) о

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

Предложенный метод является достаточно трудоемким, поэтому предлагается другой способ обработки гибких молекул в случае, когда для каждого соединения представлен конечный набор его конформаций. Главное отличие подхода состоит в том, что при обработке семейства конформаций, вместо одиночных значений расстояний между структурным фрагментом (Рх,.,Рк) и особой точкой Р0 формируются семейства расстояний от структурного фрагмента до особой точки по всем конформациям соединения D = D((PX,., Рк ), Р0) = {dx,., dn }, где dt — расстояние между структурным фрагментом (Рх,.,Рк) и особой точки Р0 на г-ой конформации, п — число конформаций, а далее вместо полного вектора Д длина которого может достигать несколько тысяч, рассматривается только его описание, например, вектор {Dmin(D),Dmed(D),DmaK(D)}, где Dmin(D) = mmdl

Dmax (D) = max dt Dmed(D) - медиана или среднее арифметическое множества D. i

Далее, для каждого элемента вектора описания формируется элемент алфавита дескрипторов с тем изменением, что вместо расстояния между структурным фрагментом и точкой p{{Pv Рк), Р0) рассматривается один из элементов описания (например, Dmm (D{{PX ,.,Рк),Р0)), при этом к дескриптору добавляется атрибут, указывающий на тип элемента описания (например, «min»).

В частности, нечеткий фрагмент 2-ого уровня порождает в данном случае следующее множества пар {(<имя дескриптора>, <его значение>)}: D\A,B) = {(A +В + min+ Dx), vx (.Dmin (D(A, В)))}, {(A + B + mm+DQ), vg(Dmin(D(A,B)))j, {(A + B + med + Dx), vx(Dmei(D(A,B)))},. {(A + B + med + DQ), vQ(Dmed(D(A,B)))}, {(A + B + max + Dx), vx(Dmwi(D(A,Bm,., {(^ + 5 + max + De), vQ (Dmsx (D(A,B)J)}. где А, В - это метка особой точки, D^.,DQ - нечеткие множества расстояний, vl,.tvQ;vi :[0,<imax]->[0,1] - их функции принадлежности. Данное определение можно естественным образом распространить на фрагменты более высокого уровня.

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

1. Aoyama Т., Suzuki Y., 1.hikawa H. Neural networks applied to quantitative structure-activity relationship analysis // Journal of Medicinal Chemistry. 1990. Vol. 33. P. 2583-2590.

2. Balaban A.T. Applications of graph theory in chemistry // Journal of Chemical Information and Modeling. 1985. Vol. 25. P.334.

3. Bezdek J.C. Pattern Recognition with Fuzzy Objective Function Algorithms. Kluwer Academic Publishers. 1981.

4. Biltz H. // Liebigs Ann. Chem. 1908. P. 1387.

5. Boileau J., Wimmer E., Carail M., Gallo R. // Bulletin de la Societe Chimique de France. 1986. 3. P. 465-469.

6. Butler A.R., Leitch E. Mechanistic studies in the chemistry of urea. Part 4. Reactions of urea, 1-methylurea, and 1,3-dimethylurea with benzil in acid solution // Journal of Chemical Society. Perkin Transactions. 1980. 2. P. 103.

7. Carhart R et al. Atom pairs as molecular features in structure-activity studies: definition and applications // Journal of Chemical Information and Modeling. 1985. Vol. 25(2) . P. 64-73.

8. Cho S.J., Tropsha A. Cross-validated R2-guided region selection for comparative molecular field analysis: a simple method to achieve consistent results // Journal of Medicinal Chemistry. 1995. Vol. 38. P.1060-1066.

9. Connolly M.L. Molecular surface triangulation // Journal of Applied Crystallography. 1985. Vol. 18. P. 499-505.

10. O.Cramer R.D., III, Patterson D.E., Bunce J.D. Comparative molecular field analysis (CoMFA). 1. Effect of shape on binding of steroids to carrier proteins // Journal of the American Chemical Society. 1988. Vol.110(18) P. 5959-5967.

11. Fischer H.J., Ekeley J.B., Ronzio A.N. // Journal of the American Chemical Society. 1942. Vol. 64. P. 1434-1436.

12. Geladi P., Kowalski B.R. Partial least squares: a tutorial // Analytica Chimica Acta. 1986. Vol. 185. P. 1-15.

13. Grillon E., Gallo R., Pierrot M., Boileau J., Wimmer E. Tetrahedron Letters. 1988. Vol.29. P. 1015.

14. Hopfinger A.J., Wang S., Tokarski J.S., Jin В., Albuquerque M., Madhav P.J, Duraiswami C. Construction of 3D-QSAR models using the 4D-QSARanalysis formalism // Journal of the American Chemical Society. 1997. Vol.119. P. 10509-10524.

15. Ivahnenko A.G. and Muller J.-A. Present state and new problems of further GMDH development // Systems Analysis Modelling Simulation. 1995. Vol. 20. P. 3-16.

16. Karelson M. Molecular Descriptors in QSAR/QSPR. Wiley Interscience. 2000.

17. Kier L.B., Hall L.H. Molecular Connectivity in Chemistry and Drug Research. Academic Press: New York. 1976.

18. Kier L.B., Hall L.H. Molecular Connectivity in Structure-Activity Analysis. Wiley, London. 1986.

19. Kim К. H., Greco G., Novellino E. A Critical Review of Recent CoMFA Applications. 3D QSAR in Drug Design, Kubinyi, H.; Folkers, G.; Martin, Y. C. (Eds). Kluwer Academic Publishers, Great Britain. 1998. Vol. 3. P. 257.

20. Klebe G. Comparative molecular similarity indices: CoMSIA // 3D QSAR in Drug Design, H. Kubinyi et al. (eds). Kluwer Academic Publishers, Great Britain. 1998. Vol. 3. P. 87-104.

21. Klebe G., Abraham U., Mietzner T. // Journal of Medicinal Chemistry. 1994. Vol. 37. P. 4130-4146.

22. Kravchenko A.N., Lebedev O.V., Maksareva E.Yu., Vasilevsky S.V., Lyssenko K.A. New approach on the synthesis l,3-dimethyl-4,5-disubstituted imidazolidin-2-ones // Mendeleev Communications. 2008. Vol. 18. P. 45-47.

23. Kumskov M.I., Zyryanov I.L., Svitan'ko I.V. A new method for representing spatial electronic structures of molecules in the problem of structure-biological activity relationship // Pattern Recognition and Image Analysis. 1995. N. 3. P.477-484.

24. Labute P. A widely applicable set of molecular descriptors // Journal of Molecular Graphics and Modelling. 2000. Vol.18. P. 464-477.

25. Lee, В., Richards F.M. The interpretation of protein structures: estimation of static accessibility // Journal of Molecular Biology. 1971. Vol. 55. P.379^00.

26. Loukas Y. Adaptive neuro-fuzzy inference system: an instant and architecture-free predictor for improved QSAR studies // Journal of Medicinal Chemistry. 2001. Vol.44. P. 2772-2783.

27. Lowis D. R. HQSAR. A new, highly predictive QSAR technique // Tripos Technical Notes. 1997. Vol. 1. No. 5.

28. Maddalena D.J. Applications of soft computing in drug design // Expert Opinion on Therapeutic Patents. 1998. 8. P. 249-258.

29. Makeev G.M., Kumskov M.I., Svitan'ko I.V., Zyryanov I.L. Recognition of spatial molecular shapes of biologically active substances for classification of their properties // Pattern Recognition and Image Analysis. 1996. Vol.6. N.4. P.795-808.

30. Mamdani E.H. Application of fuzzy algorithms for control of a simple dynamic plant//Proceedings of IEEE. 1974. Vol.121. P.1585-1588.

31. Marshall G.R. // H. Kubinyi (Ed.), 3D QSAR in Drug Design: Theory, Methods and Applications. Escom, Leiden. 1993. P. 80-116.

32. Martin Y. Distance comparisons: a new strategy for examining three-dimensional structure-activity relationships in classical and three-dimensional QSAR in agrochemistry //ACS Symposium Series, C. Hansch & T. Fijita, eds. 1995. P. 318-329.

33. Martin Y.C., Kim K.-H., Liu C.T. Comparative molecular field analysis: CoMFA // Advances in Quantitative Structure-Property Relationships. 1996. 1. P. 1-52. JAI Press.

34. Moriguchi I., Kanada Y. Use of van der Waals volume in structure-activity studies // Chemical & Pharmaceutical Bulletin (Tokyo). 1977. Vol. 25. P. 925936.

35. Nematollahi J. and Ketcham R. Imidazoimidazoles. I. The reaction of ureas with glyoxal. Tetrahydroimidazo4,5-d.imidazole-2,5-diones // The Journal of Organic Chemistry. 1963. Vol. 28. P. 2378.

36. Norinder U. Single and domain mode variable selection in 3D QSAR applications //Journal of Chemometrics. 1996. Vol. 10. P. 95-105.

37. Ortiz A. R., Pisabarro M. Т., Gago F., Wade R. C. Prediction of drug binding affinities by comparative binding energy analysis // Journal of Medicinal Chemistry. 1995. Vol. 38. P. 2681-2691.

38. Pastor M., Cruciani G., McLay I., Pickett S., Clementi S. GRid-INdependent descriptors (GRIND): a novel class of alignment-independent three-dimensional molecular descriptors // Journal of Medicinal Chemistry. 2000. Vol. 43. No. 17. P. 3233-3243.

39. Piacenza G., Beguet C., Wimmer E., Gallo R., Giorgi M. Acta Crystallographica Section C. 1997. Vol. 53. C. 1459.

40. Randic M. On characterization of molecular branching // Journal of the American Chemical Society. 1975. Vol. 97. P. 6609-6615.

41. Roger Jang J.-S. ANFIS: adaptive-network-based fuzzy inference systems // IEEE Transactions on Systems, Man, and Cybernetics. 1993. Vol. 23 J.-S. N. 03. P. 665-685.

42. Roger Jang J.-S. and Sun C.-T. Neuro-fuzzy modeling and control // The Proceedings of the IEEE. 1995. Vol. 83. N. 3. P. 378-406.

43. Roger Jang J.-S., Sun C.-T., Mizutani E. Neuro-Fuzzy and Soft Computing: a Computational Approach to Learning and Machine Intelligence. Prentice-Hall. 1996.

44. Rouvray D.H. (Ed.) Computational Chemical Graph Theory. Nova Publishers, New York, 1989.

45. Sheridan R.P. et al. Chemical similarity using geometric atom pair descriptors // Journal of Chemical Information and Modeling. 1996. Vol. 36. P. 128-136.

46. So S.S., Richards W.G. Application of neural networks: quantitative structure-activity relationships of the derivatives of 2,4-Diamino-5-(substituted-benzyl) pyrimidines as DHFR inhibitors // Journal of Medicinal Chemistry. 1992. Vol. 35. P.3201-3207.

47. Stone M. Cross-validatory choice and assessment of statistical predictions // Journal of the Royal Statistical Society. 1974. Vol. 36. P. 111-147.

48. Takagi Т., Sugeno M. Fuzzy identification of systems and its applications to modelling and control // IEEE Transactions on Systems, Man, and Cybernetics. 1985. Vol.15. P.l 16-132.

49. Wiener H. Structural determination of paraffin boiling points // Journal of the American Chemical Society. 1947. Vol. 69. P. 17-20.

50. Wold S., Ruhe A., Wold H., Dunn W.J. The collinearity problem in linear regression: the partial least squares approach to generalized inverses // SIAM Journal on Scientific Computing. 1984. Vol.5. P.735-743.

51. Zadeh L.A. Fuzzy sets // Information and Control. 1965. P. 338-353.

52. Zheng W., Tropsha A. Novel variable selection quantitative structure-property relationship approach based on the k-nearest-neighbour principle // Journal of Chemical Information and Modeling. 2000. Vol.40. P. 185-194.

53. Айвазян C.A, Бухштабер B.M., Енюков И.С., Мешалкин Л.Д. Прикладная статистика: Классификация и снижение размерности. М.: Финансы и статистика. 1988.

54. Апрышко Г.Н. Биологическая информация в электронной базе данных по противоопухолевым веществам НИИ ЭДИТО РОНЦ РАМН // Вестник РОНЦ. 2007. № 2. С. 25-31.

55. Апрышко Г.Н. Информационная система РОНЦ им. Н.Н. Блохина РАМН по противоопухолевым агентам. Общий обзор // НТИ. Серия 2. 2007. № 1. С. 18-22.

56. Апрышко Г.Н., Решетникова В.В. Регистрационно-номенклатурный и химический модули электронной базы данных Информационной системы по противоопухолевым агентам // НТИ. Серия 2. 2007. №6. С. 24-31.

57. Кохов В. А. Метод количественного определения сходства графов на основе структурных спектров // Известия РАН, Техническая Кибернетика. 1994. №5. С. 143-159.

58. Кравченко А.Н., Газиева Г. А., Сигачев А.С., Максарева Е.Ю., Лысенко К.А., Махова Н.Н. Двухступенчатое а-уреидоалкилирование мочевин 4,5-дигидроксиимидазолидин-2-онами // Известия Академии Наук, Серия химическая. 2007. С. 140-145.

59. Кумсков М.И., Смоленский Е.А., Пономарева JI.A., Митюшев Д.Ф., Зефиров Н.С. Системы структурных дескрипторов для решения задач «структура-активность» // Доклады Академии Наук. 1994. 336. ПЛ. С.64

60. Магнусон В., Харрис Д., Бейсак С. Топологические индексы, основанные на симметрии окрестностей: химические и биохимические применения. Из сборника: Химические приложения топологии и теории графов: Пер с англ. / Под ред. Р.Кинга. М.: Мир. 1987. 560 с.

61. Машковский М.Д. Лекарственные средства // Новая волна. 2005. №1.

62. Петропавловский Г.А., Реакции целлюлозы с полифункциональными, соединениями // Журнал прикладной химии. 1969. Т. 42. С. 2072.

63. Розенблит А. Б., Голендер В. Е. Логико-комбинаторные методы в конструировании лекарств. Рига: Зинатне, 1984. 352 с.

64. Руврэ Д. Следует ли заниматься разработкой топологических индексов? из сборника: Химические приложения топологии и теории графов: Пер с англ. / Под ред. Р.Кинга. М.: Мир. 1987. 560 с.

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

66. Тулюпа Ф.М., Герасютина М.И., Каряка Л.Г., Мовчан В.В. Корд. Хим. 1979. С. 120-159.

67. Харман Г. Современный факторный анализ: Пер. с англ. М.: Статистика. 1972. 486 с.

68. Шараф М.А., Иламен Д.А., Ковальский Б.Р. Хемометрика: Пер. с англ. Ленинград: Химия. 1989. 269 с.66.1. С. 86.