Содержание к диссертации
Введение
Глава 1. Задача «структура-свойство» и существующие методы ее решения ... 13
1.1 Общая постановка задачи «структура-свойство» 13
1.1.1 Описание обучающего множества 14
1.1.2 Постановка задачи 17
1.2 Существующие методы описания молекул 20
1.2.1 Параметрическое описание молекул топологическими дескрипторами 21
1.2.2 Параметрическое описание молекул структурными дескрипторами 23
1.2.3 3D-QSAR анализ трехмерных молекул 25
1.3 Методы построения прогнозирующей функции 28
Выводы 30
Глава 2. Метод представления информации о структуре молекул четкими и нечеткими дескрипторами 31
2.1 Постановка задачи в работе 32
2.2 Метод описания молекулярной структуры четкими структурными 3D-дескрипторами 36
2.3 Применение аппарата нечеткой логики при формировании структурных 3D-дескрипторов 41
2.3.1 Нечеткая логика и существующие методы решения задачи «структура-свойство» с помощью нечеткой логики 41
2.3.2 Нечеткие классы особых точек и расстояний 45
2.3.3 Алфавит нечетких структурных 3D-дескрипторов и вычисление их значений 47
2.4 Оптимизация описания нечеткими дескрипторами как демонстрация преимущества нечетких дескрипторов 52
2.4.1 Общая схема алгоритма оптимизации 52
2.4.2 Формирование начального алфавита дескрипторов 53
2.4.3 Оптимизация алфавита дескрипторов с использованием нейронной сети 54
2.5 Алгоритм решения задачи «структура-свойство» с помощью нечетких дескрипторов 57
2.5.1 Эволюционный отбор 58
2.5.2 Описание алгоритма 60
2.6 Оценка вычислительной сложности 64
Выводы 69
Глава 3. Экспериментальные результаты 71
3.1 Программная реализация алгоритма 71
3.1.1 Построение молекулярной поверхности, особых точек 71
3.1.2 Формирование матрицы «молекула-признак» и поиск классифицирующей функции в среде MATLAB 76
3.2 Использованные методы построения классифицирующей функции 77
3.3 Описание результатов 84
3.3.1 Обработка выборки бициклических бисмочевин 85
3.3.2 Обработка выборки гликозидов 95
Выводы 106
Заключение 108
Приложение.
Литература 117
- Существующие методы описания молекул
- Применение аппарата нечеткой логики при формировании структурных 3D-дескрипторов
- Алгоритм решения задачи «структура-свойство» с помощью нечетких дескрипторов
- Использованные методы построения классифицирующей функции
Введение к работе
Актуальность
Задача поиска количественных корреляций «структура-свойство» (Quantitative Structure-Activity Relationship, QSAR-задача), то есть задача предсказания физико-химической или биологической активности вещества исходя из его структуры, является ключевой проблемой математической химии. Математические модели «структура-свойство» широко используются на практике, как для предсказания активности веществ, так и для поиска новых соединений с заданными химико-биологическими свойствами. Данные модели позволяют значительно сократить расходы и время, необходимое для исследований, при синтезе новых соединений с заданными свойствами.
Особенно широкое развитие методы QSAR получили в последние 10-15 лет в связи с тем, что появились возможности для компьютерного хранения больших объемов данных о структуре всевозможных молекул и их активности, а также в связи с тем, что сильно повысилась производительность вычислительных систем, являющаяся критичной для ряда методов решения задачи QSAR.
В настоящее время разработано несколько разных подходов к решению QSAR-задачи. Как правило, QSAR-задача разбивается на две подзадачи:
1) преобразование информации о молекулярной структуре в вектора
численных признаков (дескрипторов);
2) анализ полученных данных (построение предсказывающей модели для
биологической активности - функции в векторном пространстве признаков).
Предсказывающая модель строится с использованием стандартных методов
машинного обучения (линейные и нелинейные регрессии, нейронные сети
и т.д.).
За последние несколько десятилетий разработано большое число методов решения QSAR-задачи, при этом методы различаются, главным образом, методом описания молекул в векторном пространстве признаками (дескрипторами). Классический подход был предложен Розенблитом и Голендером, которые использовали понятие «фармакофор» — набор структурных признаков в молекуле, которые отвечают за биологическую активность молекулы. Данный метод выделяет группы или цепочки атомов в структуре молекулы и находит функциональную зависимость между наличием тех или иных групп или цепочек и биологической активностью.
Karelson М. Molecular Descriptors in QSAR/QSPR. Wiley-interscience, 2000 2 Розенблит А. Б., Голендер В. Е. Логико-комбинаторные методы в конструировании лекарств.— Рига: Зинатне, 1984.—352 с.
Разработанный в работе метод развивает данное направление, однако направлен на избавление от ряда недостатков, которыми обладают классические структурные дескрипторы:
1. Проблема автоматического поиска оптимального описания молекул.
При описании дескрипторами параметры описания, как правило, выбираются
оператором исходя из априорной информации об обучающем множестве или из
других соображений. В частности, описание молекулы структурными
дескрипторами существенно зависит от выбора параметров описания -
интервалов расстояний. При этом, затруднена возможная оптимизация выбора
такого разбиения, так как значения дескрипторов не связаны непрерывно с
выбором параметров - точек разбиений. Данная проблема называется
проблемой дискретизации расстояний. Необходимость вмешательства
оператора в описание молекул снижает прогностичную силу и скорость работы
моделей «структура-свойство». Таким образом, является актуальной задача
автоматического поиска оптимального описания молекул.
2. Невозможность учитывать подвижность пространственной
структуры молекулы. При моделировании биологической активности задача
«структура-свойство» осложняется тем, что молекулы могут незначительно
менять конформацию (пространственную укладку). В результате, при
изменении конформапии даже несущественное изменение взаимного
расположения атомов может привести к значительному изменению значений
дескрипторов и прогнозирующая функция может работать ошибочно.
Следовательно, актуальной является разработка методов представления
информации о структуре молекул, нечувствительных к небольшим сдвигам
атомов относительно положения равновесия.
Таким образом, актуальной является разработка нового метода представления информации о структуре молекулы, который не обладает вышеописанными недостатками. Данный метод предлагается разработать с помощью использования аппарата нечеткой логики при определении так называемых «нечетких» дескрипторов.
Кроме того, сформулированы следующие требования к разработанному методу:
1. Метод должен позволять содержательную интерпретацию
дескрипторов, используемых в моделях, отражающих функциональную
зависимость между структурой и свойством. Некоторые современные методы
(например, топологические индексы) не обладают данным свойством.
2. Помимо нахождения структурных признаков, отвечающих за
биологическую активность, метод должен также осуществлять проверку
гипотезы о локальной значимости того или иного физико-химического свойства
(например, электростатического заряда, липофильности, способности
принимать/отдавать электрон).
Цель работы
Разработка метода представления информации о пространственных структурах молекул, основанного на нечетких структурных дескрипторах, в задаче обнаружения функциональной зависимости «структура-свойство». Для достижения этой цели сформулированы и решаются следующие задачи:
Разработать метод представления информации о пространственных конфигурациях молекул с помощью нечетких структурных ЗО-дескрипторов.
Разработать алгоритм формирования алфавита нечетких структурных ЗО-дескрипторов.
Разработать алгоритм оптимизации нечеткого описания молекул с целью поиска локально лучшей модели в некотором классе предсказывающих функций.
Оценить вычислительную сложность разработанных алгоритмов.
Реализовать разработанные алгоритмы, провести вычислительные эксперименты.
Научная новизна
Предложен новый метод представления информации о структуре молекулярных графов семействами четких и нечетких структурных 3D-дескрипторов.
В рамках предложенного метода разработан алгоритм описания молекул в задаче «структура-свойство» и проведена оценка вычислительной сложности алгоритма.
3. Подтверждена практическая значимость подхода в серии
вычислительных экспериментов по прогнозированию биологической
активности органических соединений.
Обоснованность и достоверность научных положений и полученных результатов обеспечивается обоснованной с точки зрения химии и биологии постановкой задачи и результатами тестирования использованных методов.
Практическая значимость
Разработанные алгоритмы решения QSAR-задачи могут быть использованы для решения прикладных задач предсказания физико-химической или биологической активности веществ по их структуре. Это позволяет отказаться от дорогостоящих и длительных исследований внеэкспериментальным скринингом на больших наборах химических соединений. Архитектура программного комплекса, созданного в рамках выполнения диссертационной работы, может служить основой для
автоматической системы предсказания активности соединений. Предложенный эволюционный алгоритм построения дескрипторов может быть использован для повышения вычислительной эффективности подобной системы.
Апробация работы
Материалы диссертации докладывались и обсуждались на 8-ой международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» ("Pattern Recognition and Image Analysis: New Information Technologies", PRIA-8-2007), Международной научной конференции «Компьютерные науки и информационные технологии» (2009 г.), 14-ой Всероссийской конференции «Математические методы распознавания образов» ММРО-2009 (2009 г.), Молодежной конференции «Молекулярный дизайн и синтез веществ с заданной физиологической активностью» (химический факультет МГУ им. М,В. Ломоносова, 2006 г.). Полученные результаты также обсуждались на научных семинарах механико-математического факультета МГУ им. М.В. Ломоносова и Института Органической Химии им. Н.Д.Зелинского РАН.
Публикации по теме диссертации
По материалам диссертации опубликовано 12 научных работ [1-12]. Из них - три работы [10, 11, 12] представлены в журналах из перечня ведущих научных журналов и изданий, рекомендованных ВАК РФ.
Структура и объем диссертации
Существующие методы описания молекул
Как правило, при решении задачи «структура-свойство» прогнозирующая функция / ищется одним из стандартных методов машинного обучения (линейные и нелинейные регрессии, нейронные сети и т. д.). Поэтому ключевой в задаче «структура-свойство» является задача выбора представления информации о структуре молекулы (т.е., набора признаков-дескрипторов).
Подходы к описанию молекул можно разделить на несколько больших групп: описание топологическими дескрипторами, основанными на свойствах молекулярного графа (теоретико-графовыми индексами); описание дескрипторами, соответствующими базовым геометрическим свойствам молекул (таким, как площадь поверхности, объем, диаметр и т.д.); описание структурными дескрипторами, характеризующими наличие, количество, и взаимное расположение в молекуле определенных структурных фрагментов; описание дескрипторами, характеризующими локальные физико-химические свойства молекулы в трехмерном пространстве, заполненном некоторой регулярной сеткой.
Опишем основные подходы к представлению молекул набором дескрипторов. К топологическим дескрипторам можно отнести дескрипторы, основанные либо на свойствах молекулярного графа молекулы (теоретико-графовые индексы) и дескрипторы, описывающие общую топологию молекулы (т.е., ее форму, размер и т.д.). В QSAR-задаче теоретико-графовые индексы были впервые использованы Рандичем [42] в задаче моделирования температуры кипения ациклических насыщенных углеводородов (алканов). Впоследствии, полученные результаты были развиты и обобщены в [1818, 74].
Дескрипторы, описывающие общую топологию молекулы, как правило, строятся на основе ван-дер-ваальсовой или молекулярной поверхности молекулы. Например, в [3636] в качестве дескриптора предложено использовать объем, ограниченный ван-дер-ваальсовой поверхностью, а в [26] -площадь молекулярной поверхности.
Приведем ряд примеров топологических дескрипторов. Пример 5 (индекс Винера [52]). Пусть G = {V,E} — молекулярный граф с п вершинами (атомами) и D{G) = {dlJ) — его матрица расстояний, так что d — длина кратчайшего пути между z-ой иу-ой вершинами в графе G. Определим 1 " индекс Винера как W(G) = — ]Г dy . В [5252] показано, что индекс Винера сильно коррелирует с температурой кипения алканов. Пример 6 (индекс связности Рандича [42]). Пусть G = {V,E] — молекулярный граф с п вершинами (атомами) и dt — степень /-ой вершины в графе G. Определим индекс Рандича как x(G) = , , где суммирование проводится по всем ребрам графа G, а индексы і и j относятся к номерам атомов, соединенных данным ребром. В [18] показано, что индекс Рандича может быть использован для предсказания ряда физико-химических свойств соединений.
Пример 7. В качестве дескриптора молекулы с графом G можно использовать площадь ее молекулярной поверхности Mr(G) [26, 46].
В настоящее время разработано и используется более 1000 различных топологических дескрипторов. Регрессионный анализ на основе топологических дескрипторов дает относительно неплохие результаты при моделировании физико-химических свойств «простых» молекул (углеводородов и полимеров) [2]. Благодаря своей простоте, топологические дескрипторы могут быть вычислены с минимальными затратами времени.
В то же время, топологические дескрипторы практически не применяются в прогнозировании биологической активности, поскольку не учитывают трехмерную структуру исследуемых молекул. Большинство разработанных топологических дескрипторов используют лишь информацию о молекулярном графе, игнорируя его укладку в пространстве.
В частности, топологические дескрипторы неприменимы в случае анализа гибких молекул, которые могут принимать несколько различных пространственных конфигураций. Поскольку молекулярные графы одной молекулы для всех таких конфигураций будут одинаковы, то для них будут совпадать и топологические дескрипторы; в то же время, активность молекулы в различных конфигурациях может отличаться, что делает построение предсказывающей модели на основе топологических дескрипторов невозможным.
Еще одним важным недостатком является сложность содержательной интерпретации модели, основанной на значениях топологических дескрипторов.
Структурные дескрипторы характеризуют наличие или отсутствие определенных структурных фрагментов (химических функциональных групп) в молекуле. Использование данного класса дескрипторов основано на понятии «фармакофор», что есть набор структурных признаков в молекуле, которые отвечают за биологическую активность молекулы. Данное понятие было развито и использовано в [72].
Метод выделяет структурные фрагменты в структуре молекулы и находит функциональную зависимость между наличием тех или иных групп или цепочек и биологической активностью. В качестве таких фрагментов могут выступать отдельные атомы, группы атомов и цепочки атомов, соединенных связями. После выделения фрагментов каждому фрагменту сопоставляется структурный дескриптор, значение которого соответствует числу повторений фрагмента в молекуле [68, 62].
Структурные дескрипторы были впервые использованы в [7]. В работе рассматривались структурные фрагменты - пары атомов, отстоящих друг от друга на определенное расстояние. Таким образом, структурный фрагмент записывался строкой (V.,V.,d), где VnV. - метки атомов, ad- длина минимального пути между атомами. Значением соответствующего дескриптора было число повторений фрагмента вида (,.,.,d) в молекуле.
Применение аппарата нечеткой логики при формировании структурных 3D-дескрипторов
Сначала введем ряд базовых понятий, необходимых для описания молекул в терминах нечеткой логики. Большая часть определений приведена из [54]. Определение 9. Пусть X — множество произвольной природы. Нечетким множеством А на множестве X, А с X, назовем множество пар А = {(х,/лА (х)) х є X}, где jiA : X — [О,1] назовем функцией принадлежности нечеткого множества А. При этом значение juA(x) называется степенью принадлежности элемента х к нечеткому множеству А. Если juA(x) = l, то говорят, что элемент х полностью принадлежит к А, а если 0 juA(x) l, то элемент х принадлежит А частично. Чем выше степень принадлежности элемента, тем в большей степени элемент соответствует («принадлежит») нечеткому множеству. Пример 8. Функцию принадлежности вида называют гауссовской, а соответствующее ей нечеткое множество -гауссовским. При этом число а называют центром такого нечеткого множества, а а - его стандартным отклонением. Пример функции принадлежности приведен на рисунке 6. для некоторых a b c d называют трапециевидной функцией, а соответствующее ей нечеткое множество - трапециевидным. Пример функции принадлежности приведен на рисунке 7. Определение 10. Пересечением нечетких множеств сХи BcZ назовем нечеткое множество АслВ с функцией принадлежности /лАпВ(х) = тт(/лА(х),/лв(х)) для каждого хеХ. Аналогично, объединением нечетких множеств А и В назовем нечеткое множество АиВс функцией принадлежности /iAuB (х) = max( iA (х), juB (х)). Определение 11. Дополнением нечеткого множества А Х назовем нечеткое множество А с функцией принадлежности (х) = 1 - /лА{х). Определение 12. Декартовым произведением нечетких множеств А с X и 5с7 назовем нечеткое множество Ах В такое, что для каждого х є X и у є Y. Пример 10. (операции над нечеткими множествами) Определение 13. Нечетким правилом логического вывода будем называть утверждение вида «ЕСЛИ х]єА] И х2еА2 И ... И хпєАп ТО уєВ», где Д,/ = 1,...,« - нечеткие множества, построенные на различных множествах произвольной природы и В - нечеткое множество на R. Такое утверждение задает соотношение между степенями принадлежности элементов х1,х2,...,хп к множествам АІ,А ,...УАІ и принадлежностью элемента у к некоторому нечеткому множеству В. На основе нечетких правил логического вывода разработаны системы нечеткого логического вывода Мамдани [32] и Такаги-Сугено [51].
Подобные алгоритмы логического вывода используются, в частности, в задачах классификации: после того, как рассматриваемые объекты представлены векторами признаков (x15...,xn), эти признаки могут быть сделаны нечеткими. После этого, используются правила логического вывода, задаваемые экспертно или сгенерированные другим способом с тем, чтобы приблизить значение целевого значения у на обучающем множестве. Такой подход к решению задачи классификации называют нечеткой классификацией. Описанные выше понятия нечеткой логики и нечеткой классификации нашли ряд применений при решении QSAR-задач. В основном, разрабатывались два подхода к применению нечеткой логики: использование нечетких функций принадлежности на этапе описания молекул и использование стандартных методов нечеткой классификации (таких, как системы логического вывода Мамдани, Такаги-Сугено, нейронные сети с фуззификацией [28], ANFIS (Adaptive Network - based Fuzzy Inference System) [43, 44,45]. Использование нечеткой логики на этапе описания относительно редко используется при решении QSAR-задач.
В качестве примера такого «нечеткого» описания можно привести гистограммы распределения расстояний между парами атомов, введенные в [47]. На основе сравнения гистограмм различных молекул была построена некоторая мера близости между молекулами, которая впоследствии была использована при внеэкспериментальном скрининге химических соединений. Как правило, нечеткая логика используется в QSAR-задаче точно так же, как и в других задачах классификации: после построения «четких» векторов дескрипторов к ним применяется одна из стандартных систем логического вывода [28,30]. При этом критическим для успешного применения такой системы является вопрос выбора правил нечеткого логического вывода. Экспертное задание таких правил обычно невозможно, а их генерация и оптимизация является очень сложной вычислительной задачей в силу большого числа дескрипторов в описании молекул.
В целом, использование нечетких методов классификации не приводит к существенному улучшению качества классифицирующей функции, хотя и обеспечивает ее несколько более прозрачную интерпретацию. Кроме этого, такое применение аппарата нечеткой логики не решает проблемы обработки «гибких» трехмерных молекул, так как первоначальное описание вектором дескрипторов не учитывает гибкость. В целом, вопрос нечеткого описания молекул недостаточно проработан в настоящее время. В частности, при использовании аппарата нечеткой логики в QSAR-моделях важным является вопрос выбора функций принадлежности (структурного фрагмента к классу фрагментов, соединений к классу активности и т.п.). В связи с этим возникает проблема оптимизации такого выбора. Далее в данном разделе описан метод, использующий аппарат нечеткой логики на этапе описания молекул с тем, чтобы корректно учесть взаимное расположение в трехмерном пространстве ключевых структурных фрагментов молекулы и построить по возможности легко интерпретируемую модель «структура-свойство». С этой целью вводятся нечеткие классы особых точек и расстояний, из которых затем формируются нечеткие дескрипторы, характеризующие число повторений определенных «нечетких» структурных фрагментов в молекуле.
Алгоритм решения задачи «структура-свойство» с помощью нечетких дескрипторов
На основе предложенной методики описания молекулярного графа с помощью нечетких дескрипторов, предложен алгоритм формирования алфавита дескрипторов. Особенности данного алгоритма позволяют нам добиться следующего: устранить эффект «комбинаторного взрыва» - ситуации, когда при обработке дескрипторов высших уровней формируется огромное число дескрипторов, что приводит к огромным вычислительным затратам при вычислении значений дескрипторов, а также делает вычислительно неэффективным применение многих методов классификации и регрессии; обеспечить распространенность задействованных дескрипторов; оптимизировать тип используемых функций принадлежности по угловому коэффициенту.
В первом подразделе приведено описание одной из особенностей алгоритма — эволюционного построения дескрипторов. Эволюционное построение позволяет сократить число дескрипторов, и как следствие, уменьшить вычислительную сложность алгоритма на этапе анализа. Подробные оценки приведены в разделе 2.6.
Существует два варианта построения дескрипторов высоких уровней: построение алфавита дескрипторов на основе всех дескрипторов предыдущего уровня, либо только на основе тех из них, что наиболее информативны для данного свойства. В данном разделе приведено описание второго варианта, называемого эволюционным отбором.
Информативная значимость признаков определяется после проведения этапа анализа матрицы и построения прогнозирующей модели следующим образом. Матрица «молекула-признак» строится на основе дескрипторов предыдущего уровня AD". Для каждой молекулы и каждого структурного дескриптора (что отвечает заданной строке и заданному столбцу матрицы признаков) перечисляются все химические функциональные группы молекулярного графа, состоящие из п особых точек, соответствующих данному дескриптору, и, значение дескриптора определяется как количество соответствующих фрагментов.
В результате, формируется матрица «молекула-признак» на основе дескрипторов алфавита АІУ, к которой применяется определенный алгоритм выявления функциональной зависимости. Множество дескрипторов DczAD", задействованных в построенной линейной прогнозирующей модели, назовем инфомативно значимыми. И далее, алфавит дескрипторов ADn+x формируется уже на основе множества D a ADn. Добавим к каждому из дескрипторов в D новую особую точку А, А є AD и положим Теперь, для того, чтобы определить соответствие между химической функциональной группой G и произвольным дескриптором D = (D,A,c)eADn+l, необходимо проверить, можно ли разбить G на 2 такие группы G] и G2 (состоящие из п и 1 особых точек соответственно), что фрагменту G] соответствует дескриптор D и G2 = {А}. Если такое разбиение возможно, вычислим расстояние d(A, Gj) между Gi и G2 = {А} (под расстоянием здесь понимается наименьшее, наибольшее или среднее из всех расстояний между А и каждой из особых точек G). Наконец, химическая функциональная группа G соответствует дескриптору D тогда и только тогда, когда расстояние d(A, Gj) принадлежит интервалу разбиения с. Ниже приведено детальное описание алгоритма построения дескрипторов, 2-ого, 3-его и 4-ого уровней. 1. Формирование алфавита дескрипторов 2-ого порядка (соответствующих парам особых точек) Сначала, из всевозможных пар меток особых точек осуществляется отбор пар, которые присутствуют в доле соединений выборки, не менее чем S, 0 S 1. Назовем данные пары распространенными. Далее вычисляются точки разбиения интервала расстояний. Были реализованы три варианта: A) Отрезок расстояний [0,с/тах] разбивается на равные отрезки. Б) Рассматривается множество всех расстояний между особыми точками. Для данного множества вычисляются квантили для \/к, ..., (к-\)/к, где к — количество интервалов разбиения. Данные квантили в дальнейшем служат точками разбиения интервала. B) Для каждой распространенной пары меток особых точек рассматривается множество расстояний между особыми точек данных меток по всей выборке. Для данного множества аналогично вычисляются квантили для \/к ..., {к-\)/к, которые в дальнейшем служат точками разбиения интервала. Таким образом, получено разбиение интервала расстояний для каждой распространенной пары меток особых точек.
Помимо точек разбиения, у каждой функции принадлежности есть еще параметры, которые можно варьировать — угловой коэффициент функций принадлежности, отражающий их «крутизну». Для каждой распространенной пары меток особых точек, осуществляется перебор всевозможных вариантов углового коэффициента функций принадлежности из заранее заданного набора значений. Для каждого углового коэффициента, вычисляется значение дескрипторов, основанных на информативных парах меток особых точек и функциях принадлежности. Рассматривая совокупность наборов дескрипторов, отвечающих разным угловым коэффициентам, в качестве признакового пространства, запускается МГУА таким образом, что в конечной модели не могут использоваться функции принадлежности с разными угловыми коэффициентами для одного и того же подинтервала расстояний между определенными типами особых точек.
В случае когда метод классификации/регрессии содержит автоматический отбор признаков (то есть конечная модель опирается на значения сокращенного набора дескрипторов), из полученного набора дескрипторов отберем те, которые задействованы в методе классификации/регрессии. Например, в случае использования МГУА отберем дескрипторы, задействованные в нескольких моделях с лучшим показателем прогноза. Назовем полученный сокращенный набор дескрипторов информативными дескрипторами 2-ого порядка.
Отобранные дескрипторы могут использовать разные угловые коэффициенты функций принадлежности для расстояний между разными особыми точками. Набор угловых коэффициентов, определяющих данные функции принадлежности, определяет набор нечетких дескрипторов с лучшим показателем качества. 2. Эволюционное построение алфавита дескрипторов 3-его порядка
Построение алфавита дескрипторов 3-его порядка имеет те же особенности, что и построение дескрипторов 2-ого порядка. Однако с целью уменьшения размерности признакового пространства, формирование дескрипторов 3-его порядка происходит только на основе информативных дескрипторов 2-ого порядка.
Для каждой пары меток особых точек (ТГТ2) и интервала расстояния между ними D\, образующих один из информативных дескрипторов 2-ого порядка, проводится перебор метки третьей особой точки Тз. Назовем распространенной тройку меток особых точек {Ті, Тг, Т3} с интервалом расстояний D\, если соответствующие структурные фрагменты (т.е. наборы особых точек А, В, С такие, что АеТг, ВеТ2, СєТ3, dist( 4,В)єDl)
Использованные методы построения классифицирующей функции
Полученные матрицы «молекула-признак» обработаны различными методами машинного обучения и для каждого метода проведено сравнение качества предсказаний для четких и нечетких дескрипторов. Все методы применены в режиме скользящего контроля (leave-one-out cross validation), так как размер выборки не позволяет разделение на тренировочное и тестовое множества.
Таким образом, качество прогноза вычислялось как i v. Реализованы следующие методы:
Были реализованы деревья решений с применением метода группового учета аргументов (МГУА) [16]. В качестве опорных функций использовались линейные комбинации дескрипторов. К данным предварительно применена следующая нормализация (стандартизация) с целью устранения влияния абсолютного значения признаков: z,,=- -, где х — исходная матрица признаков, zi} - нормализованная матрица признаков, х\ - среднее значения j-ого столбца, ст. — среднеквадратичное отклонение у -ого столбца.
Предварительно для получения деревьев решения, был применен иерархический агломеративный метод кластерного анализа с евклидовой метрикой на отобранном множестве дескрипторов и центроидальным методом объединения кластеров. Множество дескрипторов для определения метрики кластерного анализа было отобрано с помощью МГУА, примененного ко всей выборке. На каждом этапе селекции МГУА происходило отсеивание сильно коррелирующих и близких к нулю признаков. Применение подобного алгоритма к задаче «структура-свойство» изложено в [24] и [66].
В итоге, реализован алгоритм, состоящий из следующих шагов (подробная схема алгоритма изложена на рисунке 17): 1) нормирование столбцов матрицы и результирующего вектора, сохранение коэффициентов нормирования; 2) первоначальная фильтрация столбцов матрицы на близкие к константным и сильно коррелирующие между собой столбцы; 3) запуск МГУА на полной выборке с фильтрацией прогнозирующих моделей на близкие к константным и коррелирующие между собой на каждом шаге селекции, а также с функционалом качества, адаптированным к логическому формату прогнозируемого вектора; последующее удаление из матрицы неинформативных столбцов; 4) запуск иерархического кластерного анализа на получившейся матрице; 5) на каждом кластере отдельный запуск МГУА с последующим удалением неинформативных для данного кластера столбцов; 6) для каждого кластера вычисление коэффициентов классифицирующей функции и номеров информативных столбцов (в том числе с учетом первоначального нормирования столбцов); 7) запуск скользящего контроля (основанного на линейной регрессии) и вычисление качества линейной модели с помощью функционала качества, адаптированного к логическому формату прогнозируемого вектора. Таким образом, конечная прогнозирующая модель имеет следующий вид (рисунок 18): 2) если на этапе 1 объект был отнесен к тому или иному кластеру, применяется линейная модель, соответствующая данному кластеру: 3) если на этапе 1 объект не отнесен ни к одному кластеру, то он считается выбросом и происходит отказ от прогноза активности. 2. МГУА на конъюнкциях / дизъюнкциях. Действительные значения дескрипторов преобразованы в бинарные данные. Полученное множество разбито на кластеры агломеративным методом кластерного анализа. К бинарным матрицам «молекула - признак» для каждого кластера применен МГУА, использующий в качестве опорных функций конъюнкции ряда дескрипторов и отдельно от них дизъюнкции ряда дескрипторов. Когда добавление очередного дескриптора не дает улучшения прогноза, алгоритм МГУА останавливается.
