Содержание к диссертации
Введение
Глава 1. Интеллектуальный анализ данных и проблема прогнозирования путей биотрансформации
1.1 Прогнозирование путей биотрансформации 13
1.1.1 Основные понятия и задачи предметной области 13
1.1.2 Модель активности реакционных центров 16
1.2 Существующие решения 19
1.3 Об интеллектуальном анализе данных 24
1.4 Средства интеллектуального анализа данных 30
1.5 ДСМ-метод как средство интеллектуального анализа данных 38
1.5.1 ДСМ-рассуждения 38
1.5.2 Представление данных и знаний в виде открытой эмпирической теории для применения ДСМ-рассуждений 42
1.6 Выводы 43
Глава 2. Архитектура интеллектуальной системы типа ДСМ для решения задач прогнозирования биотрансформаций
2.1 Общая архитектура ИнтС-ДСМ 47
2.2 Интегрированная среда поддержки исследователя, анализирующего данные о путях биотрансформаций 48
2.2.1 Редактор метаболических сетей 52
2.2.2 Редактор химических соединений 53
2.2.3 Компонент генерации отчетов о проведенных экспериментах 54
2.2.4 Компоненты 2D- и 3D- визуализации структур химических соединений 55
2.2.5 Модуль биотрансформационного преобразования 55
2.2.6 Модуль, реализующий стратегию построения метаболической сети 56
2.2.7 Модуль настройки ДСМ-решателя на предметную область 57
2.2.8 Модуль поддержки эксперимента 57
2.2.9 Модуль взаимодействия с ДСМ-решателем 58
2.2.10 Подсистема связи с Базой Данных / Базой Знаний 58
2.3 Принцип работы системы 59
2.4 Выводы 61
Глава 3. Алгоритмические и программные средства
3.1 Алгоритм шага трансформации 64
3.2 Алгоритм поиска подграфа в графе 64
3.2.1 Основные этапы работы программы, реализующей алгоритм поиска подграфа в графе 68
3.2.2 Принцип работы алгоритма 74
3.2.3 Поиск всех вложений подграфа G" в граф G 81
3.2.4 Пример нахождения вложения подграфа G' в граф G 83
3.3 Алгоритм замены подграфа G" на подграф G" в графе G 92
3.3.1 Представление трансформации в системе 92
3.3.2 Принцип работы алгоритма 95
3.4. Алгоритм построения метаболической сети 98
3.5 Программная реализация 99
3.5.1. Редактор метаболических сетей 99
3.5.2 Модуль биотрансформационного преобразования 101
3.5.3 Модуль настройки ДСМ-решателя на предметную область... 104
3.5.4 Компонент для работы с файлами формата MDL MOL 105
3.5.5 Компонент 20-отображения структур химических соединений 106
3.6 Выводы 106
Глава 4. Интеллектуальная система анализа данных о результирующем эффекте от введения в организм двух химических соединений
4.1 О результирующем эффекте от введения в организм двух химических соединений 108
4.2 Использование ДСМ-метода для прогноза результирующего эффекта воздействия на организм нескольких веществ 109
4.3 Архитектура ИнтС-ДСМ для решения задачи прогноза результирующего эффекта от введения в организм двух химических соединений 111
4.4 Принцип работы системы 113
4.5. Программная реализация 115
4.5.1 БД SYNERGISM 116
4.5.2 Модуль настройки ДСМ-решателя на предметную область... 118
4.5.2Программный комплекс SYNERGEXP 119
4.6 Выводы 124
Глава 5. Экспериментальное подтверждение адекватности предложенного подхода к решению задач прогнозирования путей биотрансформаций и результирующего эффекта от введения в организм двух химических соединений: компьютерные эксперименты
5.1 Порождение необходимых и достаточных условий прохождения биотрансформационных преобразований 125
5.2 Прогноз результирующего эффекта от введения в организм двух химических соединений 134
5.3 Выводы 135
Заключение 137
Основные результаты работы 139
Список публикаций 140
Апробация работы 141
Литература 142
- Средства интеллектуального анализа данных
- Интегрированная среда поддержки исследователя, анализирующего данные о путях биотрансформаций
- Основные этапы работы программы, реализующей алгоритм поиска подграфа в графе
- Использование ДСМ-метода для прогноза результирующего эффекта воздействия на организм нескольких веществ
Введение к работе
В связи с техногенным характером современной цивилизации (в частности, в связи с применением химических веществ как в быту, так и в сфере производства) в окружающую человека среду попадает все большее число биологически активных соединений. Также большое их количество синтезируется в лабораториях, занимающимися исследованиями в области биохимии. Определение опасности этих веществ для организма человека или, наоборот, возможности их применения в качестве лекарственных средств требует решения задачи прогнозирования путей биотрансформации этих веществ.
Прогноз путей биотрансформации особенно важен при исследовании антипродуктивных свойств (канцерогенности, мутагенности, токсичности) веществ, так как зачастую именно в процессе биотрансформации вводимые в организм нейтральные вещества приобретают эти свойства (непрямые канцерогены, непрямые мутагены) [1-4]. Также важно рассматривать результирующий эффект воздействия на организм нескольких веществ, так как возможно попадание в организм одновременно или последовательно двух или более химических веществ [5]. Это особенно необходимо при моделировании ситуации введения нескольких лекарственных препаратов.
Средства интеллектуального анализа данных
Интеллектуальный анализ данных (ИАД), основанный на Data Mining, является мультидисциплинарной областью, возникшей и развивающейся на базе достижений прикладной статистики, распознавания образов, методов искусственного интеллекта, теории баз данных и др. Отсюда обилие методов и алгоритмов, реализованных в различных действующих системах ИАД. Многие из таких систем интегрируют в себе сразу несколько подходов. Тем не менее, как правило, в каждой системе имеется какой-то ключевой компонент, на который делается главная ставка. Приведем краткий обзор основных классов систем ИАД [27]: 1) Системы, использующие статистические методы. В таких системах основное внимание уделяется классическим методикам -корреляционному, регрессионному, факторному анализу и др. Недостатком систем этого класса считают требование к специальной подготовке пользователя, «тяжеловесность» и высокую стоимость. Есть еще более серьезный принципиальный недостаток статистических пакетов, ограничивающий их применение в Data Mining. Большинство методов, входящих в состав пакетов опираются на статистическую парадигму, в которой главными фигурантами служат усредненные характеристики выборки. А эти характеристики при исследовании реальных сложных жизненных феноменов часто являются фиктивными величинами. В качестве примеров наиболее мощных и распространенных статистических пакетов можно назвать SAS (компания SAS Institute), SPSS (SPSS), STATGRAPICS, STATISTICA, STADIA и др. 2) Системы, использующие технологию нейронных сетей. Это большой класс систем, архитектура которых пытается имитировать построение нервной ткани из нейронов. В одной из наиболее рас пространенных архитектур, многослойном перцептроне с обратным распространением ошибки, эмулируется работа нейронов в составе иерархической сети, где каждый нейрон более высокого уровня соединен своими входами с выходами нейронов нижележащего слоя. На нейроны самого нижнего слоя подаются значения входных параметров, на основе которых нужно принимать какие-то решения, прогнозировать развитие ситуации и т. д. Эти значения рассматриваются как сигналы, передающиеся в вышележащий слой, ослабляясь или усиливаясь в зависимости от числовых значений (весов), приписываемых межнейронным связям.
В результате на выходе нейрона самого верхнего слоя вырабатывается некоторое значение, которое рассматривается как ответ, реакция всей сети на введенные значения входных параметров. Для того чтобы сеть можно было применять в дальнейшем, ее прежде надо "натренировать" на полученных ранее данных, для которых известны и значения входных параметров, и правильные ответы на них. Эта тренировка состоит в подборе весов межнейронных связей, обеспечивающих наибольшую близость ответов сети к известным правильным ответам. Основным недостатком нейросетевой парадигмы является необходимость иметь очень большой объем обучающей выборки. Другой существенный недостаток заключается в том, что даже натренированная нейронная сеть представляет собой черный ящик. Знания, зафиксированные как веса нескольких сотен межнейронных связей, совершенно не поддаются анализу и интерпретации человеком. К тому же подобные системы достаточно дороги. Примеры нейросетевых систем — BrainMaker (CSS), NeuroShell (Ward Systems Group), OWL (HyperLogic). 3) Системы рассуждений на основе аналогичных случаев. Идея систем case based reasoning - CBR - заключается в следующем. Для того чтобы сделать прогноз на будущее или выбрать правильное решение, эти системы находят в прошлом близкие аналоги наличной ситуации и выбирают тот же ответ, который был для них правильным. Поэтому этот метод еще называют методом "ближайшего соседа" (nearest neighbour). Системы CBR показывают очень хорошие результаты в самых разнообразных задачах. Главным их минусом считают то, что они вообще не создают каких-либо моделей или правил, обобщающих предыдущий опыт, — в выборе решения они основываются на всем массиве доступных исторических данных, поэтому невозможно сказать, на основе каких конкретно факторов CBR системы строят свои ответы. Другой минус заключается в произволе, который допускают системы CBR при выборе меры "близости". От этой меры самым решительным образом зависит объем множества прецедентов, которые нужно хранить в памяти для достижения удовлетворительной классификации или прогноза. Примеры систем, использующих CBR, — KATE tools (Acknosoft), Pattern Recognition Workbench (Unica). 4) Системы, использующие деревья решений. Деревья решений являются одним из наиболее популярных подходов к решению задач ИАД. Они создают иерархическую структуру классифицирующих правил типа «если...то...» (ifhen). Популярность данного подхода связана с наглядностью и понятностью. Но очень остро для деревьев решений стоит проблема значимости. Дело в том, что отдельным узлам на каждом новом построенном уровне дерева соответствует все меньшее и меньшее число записей данных — дерево дробит данные на большое количество частных случаев. Чем больше этих частных случаев, чем меньше обучающих примеров попадает в каждый такой частный случай, тем менее уверенной становится их классификация. Если построенное дерево слишком "кустистое" — состоит из неоправданно большого числа мелких веточек — оно не будет давать статистически обоснованных ответов. Как показывает практика, в большинстве систем, использующих деревья решений, эта проблема не находит удовлетворительного решения. Кроме того, общеизвестно, что деревья решений дают полезные результаты только в случае независимых признаков. В противном случае они лишь создают иллюзию логического вывода. Довольно много систем используют этот метод. Самыми распространенными являются See5/C5.0 (RuleQuest), Clementine (Integral Solutions), SIPINA (University of Lyon), IDIS (Information Discovery).
Интегрированная среда поддержки исследователя, анализирующего данные о путях биотрансформаций
Для решения задач прогнозирования путей биотрансформаций была разработана новая (ориентированная на решение задач именно в этой области) интегрированная среда поддержки исследователя, состоящая из следующих подсистем: Подсистема ввода и отображения данных - компоненты этой подсистемы обеспечивают интерфейс с пользователем, отвечают за ввод, вывод и визуализацию данных о метаболических сетях (МС) и химических структурах. В эту подсистему входят: - редактор метаболических сетей - редактор химических соединений - компонент генерации отчетов о проведенных экспериментах - компоненты 2D- и 3D- визуализации структур химических соединений Подсистема автоматического построения МС - компоненты этой подсистемы отвечают за анализ структур как исходного вещества, так и его метаболитов, а также за построение для исходного вещества его метаболической сети. В компонентах этой подсистемы реализованы алгоритмы поиска реакционных центров в структуре и трансформации структуры («применения реакции»). Сюда же входят компоненты, отвечающие за стратегию порождения сети. Эта подсистема тесно связана с внешними фильтрами, которые помогают принять решение о порождении того или иного метаболита на основе определенной информации (о структуре исходного вещества и предполагаемого метаболита, о типе реакции и т. п.). В эту подсистему входят: - компонент, преобразующий информацию о структуре химического соединения из формата MDL MOL [40] во внутреннее представление и обратно; - компонент, реализующий алгоритм поиска подграфа в графе для нахождения вхождений заданной подструктуры в структуру некоторого химического соединения; - компонент, осуществляющий замену одной подструктуры на другую в структуре химического соединения; - модуль, реализующий через взаимодействие с этими компонентами «шаг» биотрансформационного преобразования; - модуль, реализующий стратегию построения метаболической сети с использованием предыдущего модуля.
Подсистема связи с ДСМ-решателем - главным «фильтром» при построении МС, задача которого предсказать для некоторого исход ного вещества появление/отсутствие предполагаемого метаболита на основе знаний и данных о других (подобных) веществах. Эту под систему составляют: - модуль настройки ДСМ-решателя на предметную область; - модуль поддержки эксперимента, отвечающий за формирование выборок, кодирование данных и их подготовку к запуску ДСМ-решателя, а также интерпретацию полученных результатов; - модуль взаимодействия с ДСМ-решателем, отвечающий за «загрузку» в решатель данных и получение от него гипотез и результатов их применения.
Подсистема связи с Базой Данных / Базой Знаний отвечает за взаимодействие с БД / БЗ. В БД содержится информация о структу рах веществ и их МС, в БЗ содержится информация о реакциях, пра вила порождения МС и порожденные и нефальсифицированные (±) гипотезы, полученные в результате работы ДСМ-решателя. Все это активно используется модулем автоматического построения МС. Распределение функций интегрированной среды поддержки исследователя по подсистемам показано на рис 2.2. Архитектура ИнтС-ДСМ для решения задач прогнозирования биотрансформации представлена на рис. 2.3. На рисунке указаны компоненты и связи между ними. Рассмотрим их более подробно. Разработанный графический редактор предоставляет возможность ввода метаболических сетей на основе экспериментально полученных данных. Редактор также служит средством отображения и редактирования автоматически построенных МС. Ввод необходим для пополнения БД новыми фактами, потенциально содержащими в себе новые знания. Именно на основе этих фактов строится прогноз путей биотрансформации исследуемых веществ.
Основные этапы работы программы, реализующей алгоритм поиска подграфа в графе
На первом этапе работы программы структуры из формата MDL MOL транслируются во внутренне представление с сохранением всей информации о типах атомов и связей. В программе каждая структура представлена в виде двух списков: списка атомов и списка связей. В памяти компьютера и атомы и связи представлены как отдельные объекты, содержащие лишь указатели друг на друга. Такая организация объектов позволяет реализовать множественные ассоциативные связи между объектами, а также позволяет легче ими манипулировать, так как в процессе работы алгоритма часто приходится переходить от одного объекта к другому, ассоциированному с ним.
На этапе предварительной обработки собирается информация о количестве и типах атомов и связей в G" и G. Эта информация помогает: - сразу прекратить попытки вложения, в случае если вложение невозможно, - оптимизировать процесс поиска вариантов вложения. Эта информация помогает выявить невозможность вложения в следующих случаях: 1. Общее число атомов и/или связей в G" больше чем число атомов и/или связей в G, т.е. в случае, когда Na(G") Na(G) или Nb(Gx) Nb(G), где Na(G") - число всех атомов в G\ Na(G) - число всех атомов в G, Nb(G ) - число всех связей в G Nb(G) - число всех связей в G. 2. Число атомов и/или связей определенного типа в G" больше чем число атомов и/или связей подобного типа в G, например, в случае, когда NH(G ) NH(G), где NH(G") - число атомов водорода (Н) в G\ NH(G) - число атомов водорода (Н) в G 3.
Число атомов и/или связей переменного типа в G" больше чем число атомов и/или связей подходящего им типа в G, например, в случае, когда NSBDB(G ) (NSB(G) - NSB(G,))4-(NDB(G) - NDBCG )), где NSBDB(G ) - число связей в G" , которые могут вкладываться как в одинарные (SB) так и в двойные (DB) связи в G, (NSB(G) -NSB(G )) - число свободных одинарных связей в G, которые останутся при вложении всех одинарных связей из G" в соответствующие им одинарные связи из G, (NDB(G) - NDB(G")) - то же самое, но для двойных связей, (NSB(G) - NSB + D G) -NDB(G")) - соответственно сумма всех оставшихся (после вложения в G всех связей фиксированного типа из G") связей, куда могут быть вложены связи переменного (одинарного/двойного) типа. NB: Связи/атомы переменного типа используются при поиске подструктур с условием, например, когда надо найти фрагмент G , одна (или несколько) из связей которого в структуре G может быть либо двойной, либо тройной, и/или когда один (или несколько) из атомов G не фиксирован, а принадлежит какому-нибудь множеству (например, галогенам).
Использование ДСМ-метода для прогноза результирующего эффекта воздействия на организм нескольких веществ
ИнтС-ДСМ основаны на инструментальных средствах, которые могут быть применены для решения задач в тех областях науки, где знания слабо формализованы, данные хорошо структурированы, а в БД содержатся как положительные, так и отрицательные примеры изучаемых эффектов. Задача прогноза результирующего эффекта воздействия на организм нескольких веществ как раз является такой задачей, т.е. сводится к классу задач, решаемых ДСМ-методом. Чтобы применить ДСМ-метод для прогноза результирующего эффекта при введении двух веществ (соответствующими способами введения) в конкретный организм животного, необходимо определение понятия объекта, его свойств и отношения сходства объектов. Требуемые определения и КАТ результирующего эффекта от введения в организм двух химических соединений предложены в диссертационной работе Панкратовой Е.С. [30]. Свойствами являются эффект суммирования (Add), синергизма (Syn или Synnp - синергизм, вызванный промоцией) и антагонизма (Ant). Для конкретного объекта наличие одного из свойств означает отсутствие других. Отсюда следует, что отрицательные примеры, с которыми работает ДСМ-метод, содержатся в той же БД. Это отражено в соответствующих аксиомах предметной области, содержащихся в КАТ: Во всех случаях, кроме усиления, вызванного промоцией Synnp (частный случай Syn), порядок воздействия веществ на организм не играет роли, поэтому в объектах-кортежах химические вещества можно поменять местами, что отражено в следующей аксиоме предметной области:
Приведенные определения и аксиомы использовались при разработке ИнтС-ДСМ для решения задачи прогноза результирующего эффекта от введения в организм двух химических соединений. Разработанная ИнтС-ДСМ состоит из 2 блоков (подобно ИнтС-ДСМ для прогноза путей биотрансформаций): - универсального ДСМ-решателя, который используется системой для индуктивного обучения; - интегрированной среды поддержки исследователя. Интегрированная среда поддержки исследователя включает в себя следующие подсистемы: Подсистема ввода и отображения данных - компоненты этой подсистемы обеспечивают интерфейс с пользователем, отвечают за ввод данных о химических соединениях, о проявляемых ими эф фектах и за визуализацию результатов проведенных экспериментов. В эту подсистему входят: - редактор химических соединений; - компонент генерации отчетов о проведенных экспериментах; - компоненты 2D- и 3D- визуализации структур химических соединений. Подсистема связи с ДСМ-решателем, которая включает в себя: - модуль настройки ДСМ-решателя на предметную область, содержащий определения типов и структур объектов, для которых задается отношение вложения и операции сходства, разности и пересечения, входящие в решающие предикаты ДСМ-метода; - модуль поддержки эксперимента, отвечающий за формирование выборок, кодирование данных и их подготовку к запуску ДСМ-решателя, а также интерпретацию полученных результатов; - модуль взаимодействия с ДСМ-решателем, отвечающий за «загрузку» в решатель данных и получение от него гипотез и результатов их применения.
