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

Российская Академия Наук Сибирское Отделение Институт Систем Информатики

УДК 004.42,004.6, 004.8, 510.52, 519.233, 519.254, 519.6

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

ВАЛ ЕЕ В Тагир Фаридович

АЛГОРИТМЫ И ПРОГРАММНЫЙ ИНСТРУМЕНТАРИЙ ДЛЯ ИССЛЕДОВАНИЯ ПРОЦЕССОВ ГЕННОЙ РЕГУЛЯЦИИ

Специальность 05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

Новосибирск 2006

Работа выполнена в Институте систем информатики имени А.П. Ершова СО РАН

Научные руководители: Мурзин Федор Александрович,

кандидат физико — математических наук.

К ель Александр Эдуардович, кандидат биологических наук.

Официальные оппоненты: Воробьев Юрий Николаевич,

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

Молородов Юрий Иванович, кандидат физико-математических наук.

Ведущая организация: Институт математики

имени С.Л. Соболева СО РАН

Защита состоится 15декабря 2006 г.в 15 н 00 мин на заседании диссертационного совета К003.032.01 в Институте систем информатики имени А. П. Ершова Сибирского отделения РАН ло адресу:

630090, г. Новосибирск, пр. Акад. Лаврентьева, 6.

С диссертацией можно ознакомиться в читальном зале библиотеки ИСИ СО РАН (пр. ак. Лаврентьева, 6)

Автореферат разослан 8 ноября 2006 г. Ученый секретарь

диссертационного совета К003.032.01, к.ф,—м.н.

Мурзин Ф.А.

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

Актуальность проблемы

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

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

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

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

Цель работы

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

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

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

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

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

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

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

Методы исследования

Для решения поставленной задачи нами использовались различные алгоритмы и математические методы. Было выбрано представление регуляторной системы, как процессора, который принимает в качестве входного потока данных последовательность нуклеотидов промотора, а на выходе выдаёт числовое значение экспрессии. В итоге задача была сведена к определению внутренней структуры этого процессора для известных наборов входных и выходных данных. В качестве основы для внутренней структуры процессора использовалась нечёткая логика. Для оптимизации комплекса был выбран генетический алгоритм. В качестве целевой функции применяются различные компоненты такие, как: линейная регрессия, оптимизация ошибок перепредсказания и недопредсказання, критерий нормальности, Ьтест Стьюдента и др. Для оценки качества результата использовались также дополнительные статистические методы такие, как метод складного ножа. Для моделирования промотора при тестировании на искусственных данных использовались цепи Маркова. Для описания текстовой записи получаемых комплексов использовался формализм Бэкуса-Наура.

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

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

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

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

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

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

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

В результате работы созданы программные продукты СМ_А, Explain и Cissearch. Все они предназначены для обработки экспериментов, связанных с изучением генной регуляции, и могут использоваться для проектирования лекарств и лечения трудноизлечимых болезней. Изучение генной регуляции наиболее актуально для анализа работы иммунной системы, процессов апоп-тоза (естественной смерти клеток), что непосредственно связано с исследованием таких заболеваний как рак и СПИД и поиском путей их лечения. Исследования изменений в организме, происходящих из-за генетических заболеваний, также облегчаются с использованием разработанных программных систем.

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

ских компаний (например, Serono Group); научных институтов и центров (например, Германского центра изучения рака, DKFZ); компании, занимающейся выпуском биологических баз данных BIOBASE GmbH.

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

Результаты работы докладывались на международных научных конференциях, включая Ia Intl. Conf. on Natural Computations (ICNC'05) в г, Чанша, Китай; German Conf. on Bioin format tes (GCB'05) в г. Гамбург, Германия; 3rd Annual RECOMB Satellite Workshop on Regulatory Genomics в г. Сингапур, Сингапур; 3rd Intl. Conf. "Genomics, Proteomics, Bio informatics and Nanotech-nologies for Medicine" в г. Новосибирск и др. Работа была представлена на рабочем семинаре «Наукоемкое программное обеспечение» конференции памяти академика А. П. Ершова «Перспективы систем информатики», на различных встречах, семинарах. Система Explain демонстрировалась на пленарных докладах международных конференции, на встречах с представителями свыше десятка биотехнологических и фармацевтических компаний.

Автором опубликовано 23 печатные работы, из них по теме диссертации -16 работ.

Структура и объем работы

Диссертационная работа состоит из введения, четырёх глав, заключения и списка литературы. Объем диссертации — 163 стр. Список литературы содержит 81 наименование. Рабата включает 26 рисунков и графиков, полученных в результате расчётов на ЭВМ, в том числе с использованием разработанного программного обеспечения.

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

Во введении описано современное положение в области производства лекарств и обоснована необходимость изучения генной регуляции. После этого вкратце описан программный инструментарий, разработанный в рамках работы (программы СМА, Ex Plain и CisSearch), приведена структура диссертации и описан используемый в тексте язык описания алгоритмов. Также отмечены возможные применения разработок в других областях: изучение новых вычислительных технологий; построение алгоритмов и программ, а также создание биокомпьютеров.

Первая глава посвящена первичному анализу регуляции генов; описанные в ней методы не учитывают взаимодействия транскрипционных факторов между собой. В разделе 1.1. введён ряд определений, которые требуются в дальнейшем. Нуклеотидом мы называем элемент алфавита Ö' = {A,C,G,T,N}, последовательностью нуклеотидов — слово в этом алфавите и>€ £>'*, а подцепочкой — тройку (w,s,d), задающую последователь-

ность и', стрэнд (принадлежность к одной из двух цепочек ДНК) 5 и положение начала подцепочки на геноме <1, характеризующееся в свою очередь названием гена и смещением подцепочки относительно старта транскрипции (позиции в гене, откуда начинается считывание РНК). Отметим, что регуля-торные области, которые мы в основном изучаем, это промоторы, они расположены выше старта транскрипции (то есть смещение подцепочки отрицательно).

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

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

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

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

Модель представляет собой весовую матрицу 4х£, где Ь — длина сайта; каждой позиции внутри сайта для нуклеотидов А, С, О, Т соответствует вероятность появления данного нуклеотида в данной позиции сайта с некоторой перенормировкой. Имея весовую матрицу, для любой последовательности длины £ можно вычислить степень соответствия (вес) между последовательностью и моделью; в случае, если вес превышает некоторый порог, последовательность можно считать предсказанным сайтом, соответствующим данной матрице.

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

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

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

Вторая глава посвящена построению модели комплекса с учётом различной информации из предметной области, а также методам её оптимизации. В разделе 2.1. описана общая постановка задачи, решаемой программой СМ А. Вводится понятие модели, как параметризованной функции RS:Sl —> [0,1], где S¡ — множество предсказанных сайтов для некоторого промотора. Модель задаёт набор правил и определяет, насколько данный промотор (а точнее — список сайтов, предсказанных на нём) соответствует этим правилам. Приводится пример простейшей модели с одним параметром;

Здесь параметр X— имя матрицы. Такой модели соответствуют промоторы, на которых присутствует как минимум один сайт матрицы X, Комплексом мы называем модель с подставленными параметрами. К примеру, в данной модели заменив X на имя конкретной матрицы, мы получим комплекс. Далее говорится о степени соответствия комплекса некоторым экспериментальным данным. Для каждого промотора i определено значение экспрессии и принадлежность категории с, (обычно категорий две — 'Yes* и 'No'). Степень соответствия определяется с помощью целевой функции Z.

В разделах 2.2. и 2.5. описаны различные виды моделей, объединённые в классы. Класс моделей представляет комплекс в ещё более общем виде и имеет ряд параметров, задание которых превращает класс в конкретную модель. Задание параметров класса выполняется пользователем. В работе рас-

RSX

1, если Э сайт матрицы X в SI О, иначе

смотрены три класса, реализованные в программе СМА от простого к сложному: оконный, булев и обобщённый.

В оконном классе параметрами класса является количество матриц в модели N и размер окна I (в нуклеотидах). Параметрами модели являются идентификаторы N матриц Х1,Хг,...,Хь/ и соответствующие им пороги С,,С2,...,С№. Значением комплекса является делённое на N максимальное количество предсказанных сайтов различных матриц из набора расположенных в окне ширины /, причём таких, что их вес превышает соответствующий порог. Рассматриваются детали реализации подсчёта такого комплекса и вопросы оптимизации. Модель оконного класса учитывает то что для работы комплекса необходимо, чтобы сайты связывания были распо* ложены близко друг к другу.

Модель булева класса представляет собой булеву формулу вида

Модель принимает значения 0 или 1 в зависимости от истинности этого выражения. Здесь Е^ — предикат, принимающий истинное значение, если на

данном промоторе есть сайт матрицы Ху с порогом выше, чем С#. Модель

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

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

Модель представляется в виде набора подкомплексов, объединяемых таким же выражением, как и в булевом классе, однако здесь уже Е^ — нечёткая логическая величина, характеризующая соответствие промотора одному из подкомплексов. Подкомплекс содержит набор матриц и композиционных элементов. Для каждой матрицы в качестве параметров модели определен идентификатор X, порог С и параметр V, показывающий, сколько сайтов данной матрицы учитывается.

Для каждого композиционного элемента определены две матрицы Х1г Хг; соответствующие им пороги С,,С3, диапазон допустимых расстояний между сайтами этих матриц с/^, , допустимая взаимная ориентация сай-

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

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

Особый интерес представляют мутация и кроссовер для обобщённого класса моделей. Генетические операции основаны не на побитовом изменении комплексов, а учитывают их внутреннюю структуру, В процессе мутации с некоторой вероятностью происходит одио из нескольких событий: добавление или удаление матрицы, композиционного элемента или подкомплекса; объединение двух матриц в композиционный элемент; распад композиционного элемента на две матрицы; рекомбинация матрицы и композиционного элемента; изменение одного из параметров матрицы или композиционного элемента (порога, v, ориентации или расстояний d^^d^).

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

Целевая функция Z описана в разделах 2.3, и 2,6, Она состоит из ряда компонент, которые характеризуют: соответствие профиля вычисленных значений комплексов RS экспериментальным значениям экспрессии (Z„); степень различия значений RS для промоторов категорий 'Yes* и 'No' по критерию Стьюдента (Zr); количество ошибок перепредсказания и недо-предсказания (Z£); соответствие распределения значений RS для категории 'Yes' нормальному (Zv); степень сложности комплекса (ZP). В качестве значения ZR используется величина R2 отклонения зависимости между RS и от линейной:

«S/Í-(Sa)1

Здесь д = ) , з и — общее число промоторов. Значение ZT вы-

числяется по двухвыборочному t-тесту Стьюдента с разными дисперсиями. При вычислении ZE находится значение RS*, разделяющее полученные RS таким образом, что количество промоторов из 'No', для которых RS <RS', сложенное с количеством промоторов из *Yes*, для которых RS й RS', максимально возможно. После нормализации эта сумма и используется в качестве ZE. Подсчёт ZN основан на статистике, введённой д'Лгостиио, которая

учитывает соответствие скоса —^—— Руа) и эксцесса

а ПГа

—У1(р1 ~~ PrJ] значениям, характерным для нормального распределения "fe

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

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

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

и

В разделе 3.2. описано три метода для анализа результатов. Первый метод — это так называемый мультизапуск: возможность запустить генетический алгоритм с одинаковыми параметрами несколько раз и сравнить результаты, а также оценить надёжность. Для сравнения результатов используется функция схожести 5(с,,са), которая позволяет сравнить два комплекса с, и с2 одной и той же модели. Она симметрична и принимает значения в диапазоне [0,1], причём 5{с,,с2) = 1 о с, = с2. Тогда если в п запусках получились оптимальные комплексы с,,с2,...,с„, то надёжность будет выражаться, как

В разделе описывается вид функции схожести для комплексов различных классов и доказывается, что введённые функции удовлетворяют заявленным свойствам. Затем приведён пример использования мультизапуска для определения оптимальных параметров запуска генетического алгоритма: при недостаточном размере популяции и количестве поколений получается низкая надёжность. Также мультизапуск может быть полезен для уточнения параметров класса: в приведённом примере использована модель оконного класса с N = 3, и результаты позволяют предположить, что с модель с N = 4 даст более высокое значение целевой функции.

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

После этого для оставшихся промоторов Р'= Р\С снова ищется наилучший комплекс и т. д., пока в кластера не войдёт как минимум 90% промоторов. Найденные комплексы и кластера выводятся пользователю.

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

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

целевой функции Zk принимала максимально возможное значение. Полученные коэффициенты отражают важность матриц.

В четвёртой главе описаны некоторые летали программной реализации СМА и ExPlain, а также приведены результаты тестирования-СМА на искусственных н экспериментальных данных. Программа СМА реализована в виде кроссплатформенного приложения командной строки на С++ (около 0.5 МБ кода). Результаты тестирования на искусственно сгенерированных промоторах, в которые были внедрены сайты определённых факторов и композиционных элементов, показали, что СМА успешно находит внедрённые факторы. Результаты тестирования на двух экспериментальных наборах данных, для которых правильный результат частично известен, показали, что комплекс, находимый СМА, хорошо согласуется с известными данными.

Система Explain представляет собой кросс платформенное веб-приложение на языке программирования Perl (около 1.0 МБ кода). Это — оболочка, которая объединяет в себе различные виды анализа регуляторных процессов на основании экспериментальных данных. В частности, в ней включена возможность запуска СМА. Обрабатывать данные в Explain значительно удобнее, так как данные, полученные из эксперимента, можно непосредственно загрузить в ExPlain, используя идентификаторы генов из любых популярных баз данных. ExPlain он преобразует их, найдёт промоторы, соответствующие генам, и извлечёт соответствующие им последовательности из базы TRANSPRO, после чего запустит СМА и представит результаты в удобном виде с использованием средств разметки HTML. Кроме того, ExPlain предоставляет широкие возможности для предварительной фильтрации данных, конструирования профайлов и комплексной обработки данных различными методами.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

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

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

• Реализована программа СМА, представляющая собой инструмент для гибкого анализа регуляторной модели на основании данных по экспрессии генов в различных экспериментах. Проведено тестирование программы

на искусственных и экспериментальных данных; результаты тестирования подтвердили согласие предсказываемых СМА регуляторных комплексов с экспериментальными данными.

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

О ЛИЧНОМ ВКЛАДЕ АВТОРА

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

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

Программная реализация СМА (не включая использованную библиотеку GRESA) выполнена автором приблизительно на 80-85%, в частности продумана общая структура приложения; полностью реализованы булев и обобщённый класс моделей, средства проверки результата; значительно переработана и оптимизирована целевая функция и оконный комплекс; написан изначально цикл генетического алгоритма (который впоследствии менялся другими разработчиками); реализованы классы для обработки параметров, вывода результата и отображения графической информации.

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

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

м

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

1. Waleev, Т., Shtokalo, D., Konovalova, Т., Voss, N., Cheremushkin, В.,

Stegmaier, P., Kel-Margoulis, O., Win gender, E., Kel, A. Composite Module Analyst: identification of transcription factor binding site combinations using genetic algorithm. // Nucleic Acids Research. — 2006. — Vol. 34(Web Server issue).

— P. 541-545.

2. Cheremushkin, E4 Konovalova, Т., Valeev, Т., Kel, A.

Methods for search of gene regulatory elements binding sites. // Analytical Tools for DNA: Genes and Genomes: Nuts & Bolts. — DNA Press, 2005. — P. 185— 214.

3. Kel, A., Konovalova, Т., Waleev, Т., Cheremushkin, E., Kel-Margoulis, O., Wlngender, E. Composite Module Analyst: a fitness-based tool for identification of transcription factor binding site combinations. If В ioin forma tics. — 2006. — Vol. 22(10). —P. 1190-1197.

4. Konovalova, Т., Valeev, Т., Cheremushkin, E., Kel, A. Composite Module Analyst: Tool for Prediction of DNA Transcription Regulation. Testing on Simulated Data. It Proc. of the First Internationa] Conference on Natural Computations (ICNC'05), Changsha, China, Aug. 27-29, 2005. — Advances in Natural Computation, part 2 (LNCS 3611). — Springer, 2005. — P. 1202-1205.

5. Kel, A., Konovalova, Т., Valeev, Т., Cheremushkin, E., КеГ-Margoulis, O., Wingender, E. Composite Module Analyst: A Fitness-Based Tool for Prediction of Transcription Regulation. // Proc. of the German Conference on Bioinformatics (GCB'05), Hamburg, Germany, Oct. 5-7, 2005. — Lecture Notes in Informatics.

— 2005. — Vol. P—71. — P, 63-76.

6. Cheremushkin, E-, Konovalova, Т., Valeev, Т., Shtokalo, D., Taraskina, A.

CisSearch: Software Package For Complex Analysis Of Gene Regulatory Se-

quences. // Proc. of the 3"1 Annual RECOMB Satellite Workshop on Regulatory Genomics, Singapore, Jul. 17-18,2006.—: Singapore, 2006. — P. 100-108.

7. Cheremushkln, E., Konovalova, Т., Valeev, Т., Shtokalo, D., Tarasklna, Л.

Software Package for Complex Analysis of Gene Regulatory. // Proc. of the 3rd International Conference "Genomics, Proteomics, Bio informatics and Nanotechnolo-gies for Medicine", Novosibirsk, Jul. 12-16, 2006. — P. 97.

8. Валеев Т. Ф. Сравнительный анализ методов поиска регул яторных модулей в последовательностях ДНК, использующих данные микргаррэев. // Методы и инструменты конструирования и оптимизации программ. — Новосибирск, 2005. — С. 21-28.

9. Валеев Т. Ф. Генетический алгоритм как альтернатива для решения некоторых NP-полиых задач. // Тез. докл. конференции-конкурса «Технологии Microsoft в информатике и программировании», Новосибирск, 22-24 февраля 2005. — С. 112-113.

10. Коновалова Т. Г., Валеев Т. Ф., Черёмушкин Е. С. Поиск композиционных промоторных модулей, регулирующих экспрессию генов эукариот. // Тез. докл. конференции-конкурса «Технологии Microsoft в информатике и программировании», Новосибирск, 22—24 февраля 2005. — С. 121-122.

11. Черёмушкнн Е. С., Коновалова Т. Г., Валеев Т. Ф. Разработка пакета программ по анализу регуляторных областей ДНК. // Тез. докл. конференции-конкурса «Технологии Microsoft в информатике и программировании», Новосибирск, 22-24 февраля 2005. — С, 142-J43.

12. Голосов К. В., Валеев Т. Ф., Коновалова Т. Г. и др. Интегральная система анализа генетической информации ExPlain. // Тез. докл. конференции-конкурса «Технологии Microsoft в теории и практике программирования», Новосибирск, 22-24 февраля 2006. — С. 171-172.

13. Тараскина Л. С., Коновалова Т. Г., Вал ее в Т. Ф.» Штокало Д. Н., Черёмушкин Е. С. Графическое представление результатов анализа в пакете программ по поиску регуляторных фрагментов в ДНК, Н Тез. докл. конференции-конкурса «Технологии Microsoft в теории и практике программирования», Новосибирск, 22—24 февраля 2006. — С. 223-225.

14. Тараскина А. С., Коновалова Т. Г., Валеев Т. Ф., Штокало Д. Н., Черёмушкнн Е. С. Пакет программ CisSearch по поиску регуляторных фрагментов в ДНК. // Тез. докл. XIII Международной научной конференции «Ломоносов», Москва, 12-15 апреля 2006. — Т. IV. — С. 48-49.

15. Черёмушкнн £. С., Валеев Т. Ф, Коновалова Т. Г., Штокало Д. Н-, Голосов К. В., К ель А. Э. Explain: программная система по анализу микрочипов и поиску ключевых молекул. II Тез. докл. Шестой международной конференции «Перспективы систем информатики», рабочий семинар «Наукоёмкое программное обеспечение», Новосибирск, 28-29 июня 2006. — С. 106-110,

16. Черёмушкнн Е. С., Коновалова Т. Г., Валеев Т. Ф., Штокало Д. Н., Тараскина А. С. Пакет программ CisSearch для анализа регуляторных последовательностей ДНК. // Тез. докл. Шестой международной конференции «Перспективы систем информатики», рабочий семинар «Наукоёмкое программное обеспечение», Новосибирск, 28-29 июня 2006. — С. J1J-114.

В алее в Т. Ф.

АЛГОРИТМЫ И ПРОГРАММНЫЙ ИНСТРУМЕНТАРИЙ ДЛЯ МОДЕЛИРОВАНИЯ ПРОЦЕССОВ ГЕННОЙ РЕГУЛЯЦИИ

Автореферат

Подписано в печать Объем 1,1 уч.-изд. л.

Формат бумаги 60 х 90 1/16_Тираж 100 экз.

Отпечатано в ЗАО РИЦ «Прайс-курьер»

630090, г. Новосибирск, пр. Ак. Лаврентьева, 6, тел. 330-72-02

Заказ № ЗЩ

Введение.

Глава 1. Первичный анализ регуляции генов.

1.1. Основные понятия и определения.

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

1.3. Обработка экспериментальных данных и предсказание регулирующих факторов

Глава 2. Модель регуляторного комплекса.

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

2.2. Построение модели.

2.2.1. Конструирование и анализ алгоритма оконного класса моделей.

2.2.2. Конструирование булева класса моделей.

2.3. Целевая функция.

2.4. Поиск оптимального комплекса.

2.4.1. Выбор эффективного алгоритма поиска.

2.4.2. Операторы создания и мутации.

2.4.3. Оператор кроссовера.

2.5. Обобщённый класс моделей: унификация знаний о сайтах и факторах.

2.5.1. Общая структура.

2.5.2. Подкомплекс: семантика и структура.

2.5.3. Вес обобщенного комплекса.

2.5.4. Эффективная программная реализация математической модели обобщенного комплекса.

2.5.5. Операторы создания, мутации и кроссовера в обобщённом классе.

2.6. Обобщённая целевая функция.

2.6.1. Компоненты целевой функции.

2.6.2. Ограничения обобщённой целевой функции.

Глава 3. Взаимодействие с пользователем и оценка качества.

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

3.2. Методы оценки качества результата.

3.2.1. Мультизапуск: проверка устойчивости поведения генетического алгоритма.

3.2.2. Запуск с кластеризацией.

3.2.3. Запуск с расщеплением выборки: достоверность результата и переобучение

3.3. Значимость компонентов подкомплекса.

Глава 4. Реализация и тестирование.

4.1. Реализация СМА.

4.2. Тестирование СМА.

4.2.1. Тестирование на искусственных данных.

4.2.2. Тестирование на экспериментальных данных.

4.3. Система ExPlain.

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

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

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

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

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

Хотелось бы также отметить потенциальную важность исследования генной регуляции не только для генетики, но и для изучения новых вычислительных технологий и принципов построения алгоритмов и программ. Рассматривая представление ДНК как блока данных, а транскрипционных факторов — как программы, обрабатывающей эти данные, и изучая механизмы их взаимодействия, можно получить новые эффективные методы построения программ или решения некоторого класса задач. Напомним, что, исследуя устройство и функционирование генетического кода, учёные уже описали семейство эволюционных алгоритмов (включая генетический алгоритм), базирующихся на тех же принципах. Также можно упомянуть, что в 1994 году благодаря работе Эдлмана [3] появился метод решения NP-полных задач с помощью фрагментов ДНК и так называемые биокомпьютеры [4]. Изучение законов генной регуляции, возможно, позволит в будущем развить эту область и увеличить возможности биокомпьютеров1.

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

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

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

1 Мнение о потенциальной пользе нашей работы для биокомпьютерных исследований высказал Danny van Noort (PhD, ранее старший научный сотрудник кафедры биомолекулярной обработки информации Института Фраунгофера, Германия, ныне профессор Национального Университета Сеула, читает курс лекций по биокомпьютерным вычислениям) на конференции ICNC'05 в Китае. Уже сейчас проводятся эксперименты по использованию генной регуляции в биокомпьютерах.

• Реализацию способа оптимизации (подбора параметров) этой модели для достижения наибольшего соответствия модели экспериментальным данным.

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

• Создание программного инструментария, который выполняет процесс оптимизации и представляет подробные результаты, а также позволяет гибко управлять видом модели и процессом её оптимизации и оценить качество результата.

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

В результате проведённой работы разработано два программных средства — СМА и ExPlain. СМА [66,68,69,70,75] представляет собой неинтерактивное приложение, основанное на библиотеке GRESA [5] и управляемое множеством параметров командной строки. Большая часть проектирования, разработки и отладки СМА выполнена автором данной работы, но в создании этого продукта принимали участие и другие разработчики. ExPlain [77,80] — это мощная интерактивная система анализа генной регуляции в целом, которая, в частности, является оболочкой для СМА, хотя удобный запуск СМА и визуальное представление результатов этого запуска — лишь малая доля функциональности этой системы. Она сопряжена с различными базами данных, выпускаемыми BIOBASE GmbH, и призвана сделать обработку данных по генной регуляции более эффективной. ExPlain разрабатывается автором этой работы в составе интернациональной группы, в которой около 10 человек.

Существуют некоторые конкурирующие с СМА разработки, такие как TOUCAN [6,7] и TeLIS [10]. В работе [73] мы проводили сравнение их функциональности с СМА, но с тех пор проект СМА ушёл далеко вперёд, хотя некоторые полезные особенности конкурентов до сих пор не имеют аналогов в СМА (например, разбиение весовых матриц на классы с возможностью исключения из регуляторного комплекса матриц из одного класса). С другой стороны, СМА содержит много уникальных особенностей, таких как предсказание композиционных элементов, комплекса, состоящего из нескольких подкомплексов, учёт нескольких сайтов одной матрицы и многое другое.

Система ExPlain на мировом рынке аналогов не имеет. Хотя для большинства отдельных компонентов системы существуют подобные конкурирующие разработки, до сих пор никто не пытался интегрировать их в цельную систему.

Некоторые идеи, методы и алгоритмы, описанные в работе, нашли также применение в программном комплексе CisSearch [71,72,76,78,79,81], представляющем собой интерактивное графическое приложение под Windows, которое облегчает обработку разнообразных экспериментальных данных, связанных с генной регуляцией. Впрочем, мы практически не будем говорить об этом продукте.

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

Разработанные программные средства успешно использовались различными специалистами для обработки данных по генной регуляции включая представителей международных биотехнологических и фармацевтических компаний (например, Serono Group); научных институтов и центров (например, Германского центра изучения рака, DKFZ); компании, занимающейся выпуском биологических баз данных BIOBASE GmbH.

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

Результаты работы докладывались на международных научных конференциях, включая 1st Intl. Conf. on Natural Computations (ICNC'05) в г. Чанша, Китай; German Conf. on Bioinformatics (GCB'05) в г. Гамбург, Германия; 3rd Annual RECOMB Satellite Workshop on Regulatory Genomics в г. Сингапур, Сингапур; 3rd Intl. Conf. "Genomics, Proteomics, Bioinformatics and Nanotech-nologies for Medicine" в г. Новосибирск и др. Работа была представлена на рабочем семинаре «Наукоёмкое программное обеспечение» конференции памяти академика А. П. Ершова «Перспективы систем информатики», на различных встречах, семинарах. Система ExPlain демонстрировалась на пленарных докладах международных конференций, на встречах с представителями свыше десятка биотехнологических и фармацевтических компаний.

Структура и объем работы

Диссертационная работа состоит из введения, четырёх.глав, заключения и списка литературы. Объем диссертации — 163 стр. Список литературы содержит 81 наименование. Работа включает 26 рисунков и графиков, полученных в результате расчётов на ЭВМ, в том числе с использованием разработанного программного обеспечения.

Основные результаты

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

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

• Реализована программа СМА, представляющая собой инструмент для гибкого анализа регуляторной модели на основании данных по экспрессии генов в различных экспериментах. Проведённое тестирование показало, что разработанные инструменты работоспособны, а получаемый результат находит экспериментальное подтверждение.

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

Заключение

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

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

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

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

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

СМА, другие выдвинули разработчики. Практически любой этап работы СМА может быть так или иначе усовершенствован. Опишем некоторые варианты улучшений.

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

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

В-третьих, необходимо выработать критерии надёжности результата СМА, к примеру, критерий p-value (вероятность того, что данный результат мог получиться на случайном наборе входных данных). Это очень важно, так как иногда результат, выдаваемый СМА, может быть абсолютно ненадёжен по ряду причин: недостаточное число поколений в генетическом алгоритме, ненадёжные значения экспрессий во входных данных ввиду плохо поставленного эксперимента и т. д. Подобный критерий позволит пользователю определить подобные проблемы на раннем этапе анализа и принять меры к их устранению.

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

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

Выше перечислены только некоторые идеи дальнейшего развития СМА. В действительности их высказано гораздо больше, не говоря о бесчисленных пожеланиях к улушению системы ExPlain (модульность системы со специфицированным интерфейсом, возможность внедрения плагинов, управляемая скриптами поточная обработка больших объёмов данных и многое другое).

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

• Формализована структура булева класс моделей и выполнена большая часть работы по формализации структуры обобщённого класса;

• Выдвинута идея использования функции сходства, сконструирована сама функция; выдвинута и реализована идея её использования для оценки надёжности;

• Оптимизировано вычисление комплекса оконного класса и создан алгоритм оптимального вычисления комплекса обобщённого класса;

• Реализованы оригинальные события в операторе мутации: синтез, распад и рекомбинация композиционных элементов (при тестировании на искусственных данных добавление этих операторов уменьшило на порядок время затрачиваемое на поиск внедрённого комплекса);

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

• Проведено исследование критериев нормальности; выбран критерий, обес-печивающий приемлемое качество при высокой скорости вычисления;

• Придуман алгоритм, определяющий RScut и вычисляющий ZE за линейное время;

• Исследована применимость различных вариантов формул нечёткой логики и выбрана наиболее подходящая.

Реализация программного кода СМА выполнена автором на 80-85%. Создана общая структура приложения и разбивка на пакеты, реализованы вспомогательные классы ввода-вывода. Автором полностью реализованы булев и обобщённый класс моделей, оптимизирован и доработан оконный класс, значительно переработана целевая функция, реализованы различные виды запусков и многое другое.

Что касается системы ExPlain, тут разделить вклад разработчиков значительно сложнее: одни и те же фрагменты кода неоднократно переписывались несколькими разработчиками, и уже трудно установить, кто внёс больший вклад. Точно можно сказать, что автор привёл общий интерфейс к текущему виду, ввёл концепцию процессов, проработал часть структуры базы данных, которая касается хранения информации о различных генетических объектах (генах, мРНК, промоторах и т. д.) и связях между ними, проработал разделение на модули. Автором реализовано, переработано, исправлено и отлажено множество отдельных функций, предложены различные идеи. Общий вклад в разработку системы автор оценивает примерно в 25%.

Тестирование на искусственных данных выполнено автором полностью, включая написание генератора искусственных последовательностей. Из трёх экспериментов, описанных в разделе «Тестирование на экспериментальных данных», автором полностью выполнен первый, во втором и третьем автор не участвовал.

Общий объём программного кода СМА, генератора искусственных последовательностей и программы graphout на С++ составляет около 500 Кб (не включая тесты и библиотеку GRESA). Объём программного кода ExPlain на Perl превышает 1 Мб (не включая файлы данных, конфигурационные файлы, двоичные исполняемые модули, графические элементы интерфейса и документацию).

Автором опубликованы 23 печатные работы, из них 16 по теме диссертации.

1. Интегральная платформа «От гена до прототипа лекарства» in silico и in vitro / Иванов А. С., Веселовский А. В., Дубанов А. В., Скворцов В. С., Арчаков А. И. // Российский химический журнал. — 2006. — Том L. — №2. —С. 18-35.

2. Lohse, М. J. The future of pharmacology. Trends Pharmacol // Science. — 1998. —Vol. 19. —P. 198-200.

3. Adleman, L. M. Molecular Computation Of Solutions To Combinatorial Problems//Science. — 1994. — Vol. 266(11). —P. 1021-1024.

4. Amos, M. Theoretical and Experimental DNA Computation / Amos, M. — Springer, 2005. — 173 p.

5. Computational detection of cis-regulatory modules / Aerts S., Van Loo P., Thijs G., Moreau Y., De Moor, B. // Bioinformatics. — 2003. — Vol. 19, Suppl 2. —P. ii5-iil4.

6. TOUCAN: Deciphering the Cis-Regulatory Logic of Coregulated Genes / Aerts, S., Thijs, G., Coessens, В., Staes, M., Moreau Y., De Moor, B. // Nucleic Acids Research. — 2003. — Vol. 31, N 6. — P. 1753-1764.

7. A genetic algorithm for the detection of new cis-regulatoiy modules in sets of coregulated genes / Aerts S., Van Loo P., Moreau Y., De Moor, B. // Bioinformatics. — 2004. — Vol. 20(12). — P. 1974-1976.

8. TOUCAN 2: the all-inclusive open source workbench for regulatory sequence analysis / Aerts S., Van Loo P., Aerts, S., Mayer, H., De Martin, R.,

9. Moreau, Y., De Moor B. // Nucleic Acids Research. — 2005. — Vol 33(Web Server issue). — P. 393-396.

10. Expression-based monitoring of transcription factor activity: The TELiS database / Cole, S., Yan, W., Galic, Z., Arevalo, J., Zack, J. A. // Bioinformatics. — 2005. — Vol. 21(6). — P. 803-810.

11. Transcription factor interactions: selectors of positive or negative regulation from a single DNA element / Diamond, M. I., Miner, J. N., Yoshinaga, S. K., Yamamoto K. R. // Science. — 1990. — Vol. 249. — P. 1266-1272.

12. COMPEL: a database on composite regulatory elements providing combinatorial transcriptional regulation / Kel-Margoulis, О. V., Romashchenko, A. G., Kolchanov, N. A., Wingender, E., Kel, A. E. // Nucleic Acids Research. — 2000. —Vol. 28(1). —P. 311-315.

13. TRANSFAC and its module TRANSCompel: transcriptional gene regulation in eukaryotes / Matys, V., Kel-Margoulis, О. V., Fricke, E. et. al. // Nucleic Acids Research. — 2006. — Vol. 34(Database issue). — P. 108-110.

14. Davidson, E. H. Genomic Regulatory Systems: Development and Evolution / Davidson, E. H. — Academic Press, 2001. — 261 p.

15. Yuh, C.-H. Genomic Cis-Regulatory Logic: Experimental and Computational Analysis of a Sea Urchin Gene / Yuh, C.-H., Bolouri, H., Davidson, E. H. // Science. — 1998. — Vol. 279. — No. 5358. — P. 1896-1902.

16. Single Nucleotide Polymorphisms: Methods and Protocols / Edited by Kwok, P.-Y. — AACC Press, 2002. — 269 p.

17. MATRIX SEARCH 1.0: a computer program that scans DNA sequences for transcriptional elements using a database of weight matrices / Chen, Q. K., Hertz, G. Z., Stormo, G. D. // Bioinformatics. — 1995. — Vol. 11(5). — P. 563-566.

18. Schneider T. Information content of binding sites on nucleotide sequences / Schneider, Т., Stormo, G. D., Gold, L. // Journal of Molecular Biology. — 1986. —Vol. 188. — P. 415-431.

19. Horton P. An assessment of neural network and statistical approaches for prediction of E.coli promoter sites / Horton P., Kanehisa M. // Nucleic Acids Research. — 1992. — Vol. 20. — P. 4331-4338.

20. MATCH: A tool for searching transcription factor binding sites in DNA sequences / Kel, A. E., Gossling, E., Reuter, I., Cheremushkin, E., Kel-Margoulis, О. V., Wingender, E. // Nucleic Acids Research. — 2003. — Vol. 31(13). — P. 3576-3579.

21. Колмогоров A. H. Теория информации и теория алгоритмов / Колмогоров А. Н. — М.: Наука, 1987. — 304 с.

22. TRANSFAC: transcriptional regulation, from patterns to profiles / Matys, V., Fricke, E., Geffers, R. et al. // Nucleic Acids Research. — 2003. — Vol. 31(1). — P. 374-378.

23. Light-generated oligonucleotide arrays for rapid DNA sequence analysis / Pease, A. C., Solas, D., Sullivan, E. J., Cronin, M. Т., Holmes, C. P., Fodor, S. P. // Proc. of the National Academy of Sciences. — 1994. — Vol. 91(11).— P. 5022-5026.

24. Serial analysis of gene expression / Velculescu, V. E., Zhang, L., Vogelstein, В., Kinzler, K. W. // Science. — 1995. — 270(5235). — P. 484-487.

25. Expression monitoring by hybridization to high-density oligonucleotide arrays / Lockhart, D. J., Dong, H., Byrne, M. C., Follettie, M. Т., Gallo, M. V., Chee,

26. M. S., Mittmann, M., Wang, С., Kobayashi, M., Horton, H., Brown, E. L. // Nature Biotechnology. — 1996. —Vol. 14(13). —P. 1675-1680.

27. Naur, P. Revised Report on the Algorithmic Language ALGOL 60 // Communications of the ACM. — 1960. — Vol. 3. — No. 5. — P. 299-314.

28. Marcotty ML The World of Programming Languages / Marcotty M., Ledgard, H. — Berlin: Springer-Verlag, 1986. — С 41-й с. и ниже.

29. Land А. Н. An automatic method of solving discrete programming problems / Land, A. H., Doig, A. G. // Econometrica. — 1960. — Vol. 28. — P. 497-520.

30. Корбут А. А. Дискретное программирование / Корбут А. А., Финкель-штейн Ю. Ю. — М.: Наука, 1969. — 368 с.

31. Алгоритмы: построение и анализ / Кормен Т. X., Лейзерсон Ч. И., Ривест, P. JL, Штайн, К. — Издательство «Вильяме», 2005. — 1296 с.

32. Holland J. Н. Adaptation in Natural and Artificial Systems / Holland J. H. — The University of Michigan Press, 1975. — 211 p.

33. Michalewicz, Z. Genetic Algorithms + Data Structures = Evolution Programs / Michalewicz, Z. — Springer-Verlag, 1996. — 387 p.

34. The Practical Handbook of Genetic Algorithms / Edited by Chambers, L. — Chapman & Hall, 2001. — 535 p.

35. Mitchell, M. An Introduction to Genetic Algorithms / Mitchell, M. — MIT Press, 1999. — 158 p.

36. Zadeh L. A. Fuzzy algorithms // Information and Control. — 1968. — P. 94102.

37. Cignoli R. Algebraic Foundations of Many-Valued Reasoning / Cignoli R., D'Ottaviano, I. M., Mundici, D. — Springer, 1999. — 248 p.

38. Kanji G. K. 100 Statistical Tests. — London, Sage, 1999. — 224 p.

39. Hartigan, J. Clustering algorithms / Hartigan, J. — New York, Wiley, 1975.366 p.

40. Shapiro, S. S. An analysis of variance test for normality (complete samples) / Shapiro, S. S„ Wilk, M. B. // Biometrika. — 1965. — Vol. 52. — P. 591-611.

41. Epps, T. W. A test for normality based on the empirical characteristic function / Epps, T. W., Pulley, L. B. // Biometrika. — 1983. — Vol. 70 — P. 723-726.

42. ГОСТ P ИСО 5479-2002. Статистические методы. Проверка отклонения распределения вероятностей от нормального распределения. — М.: Изд-во стандартов. 2002. — 30 с.

43. Орлов А. И. Прикладная статистика / Орлов А. И. — М.: Издательство «Экзамен», 2004. — 656 с.

44. Большее JI. Н. Таблицы математической статистики / Большев JI. Н., Смирнов Н. В. —М.: Наука, 1983. —416 с.

45. D'Agostino, R. В. Transformation to normality of the null distribution of gi // Biometrika. — 1970. — Vol. 57. — P. 679-681.

46. D'Agostino, R. B. Tests for departures from normality. Empirical results for the distribution of and b2 / D'Agostino, R. В., Pearson, E. // Biometrika.1973. — Vol. 60. — P. 613-622.

47. D'Agostino, R. B. Goodness-of-fit Techniques / D'Agostino, R. В., Stephens, M. A. — New York, 1986. — 576 p.

48. Akaike, H. A New Look at the Statistical Model Identification // I.E.E.E. Transactions on Automatic Control. — 1974. — Vol. AC 19. — P. 716-723.

49. Akaike, H. Canonical Analysis of Time Series and the Use of an Information Criterion // System Identification: Advances and Case Studies. — New York, Academic Press, 1976. — P. 52-107.

50. Hannan, E. J. The Estimation of the Order of an ARMA Process // Annals of Statistics. — 1980. — No. 8. — P. 1071-1081.

51. Hannan, E. J. The Determination of the Order of an Autoregression / Hannan, E. J., Quinn, B. G. // Journal of the Royal Statistical Society. — 1979. — Vol. B—41. — P. 190-195.

52. Schwarz, G. Estimating the Dimension of a Model // Annals of Statistics. — 1978. —No. 6. —P. 461464.

53. Efron, B. Nonparametric estimates of standard error: The jackknife, the bootstrap and other methods // Biometrika. — 1981. — No. 68. — P. 589-599.

54. Колесов Ю. Моделирование систем. Динамические и гибридные системы / Колесов Ю., Сениченков Ю. — БХВ-Петербург, 2006. — 224 с.

55. Biological sequence analysis / Durbin, R., Eddy, S. R., Krogh, A., Mitchson, G. — Cambridge University Press, 1998. — 356 p.

56. TRANSCompel: a database on composite regulatory elements in eukaryotic genes / Kel-Margoulis, O., Kel, A. E., Reuter, I., Deineko, I. V., Wingender, E. // Nucleic Acids Research. — 2002. — Vol. 30. — P. 332-334.

57. Recognition of NFATp/AP-1 composite elements within genes induced upon the activation of immune cells / Kel, A., Kel-Margoulis, O., Babenko, V., Wingender, E. // Journal of Molecular Biology. — 1999. — Vol. 288. — P. 353376.

58. Structure of the DNA-binding domains from NFAT, Fos and Jun bound specifically to DNA / Chen, L., Glover, J. N., Hogan, P. G., Rao, A., Harrison, S. C. // Nature. — 1998. — Vol. 392. — P. 42^18.

59. Identifying combinatorial regulation of transcription factors and binding motifs / Kato, M., Hata, N., Banerjee, N., Futcher, В., Zhang, M. // Genome Biology. — 2004. — Vol. 5(8):R56.

60. Molecular Cell Biology / Lodish, H., Scott, M. P., Matsudaira, P., Darnell, J., Zipursky, L., Kaiser, C., Berk, A., Krieger, M. — Freeman, 2003. — 973 p.

61. Cell Cycle Control / Edited by Hutchison, C., Glover, D. M. — 1995. — 320 p. Публикации по теме диссертации

62. Cheremushkin, E., Konovalova, Т., Valeev, Т., Kel, A.

63. Methods for search of gene regulatory elements binding sites. // Analytical

64. Tools for DNA: Genes and Genomes: Nuts & Bolts. — DNA Press, 2005. — P. 185-214.

65. Cheremushkin, E., Konovalova, Т., Valeev, Т., Shtokalo, D., Taraskina, A.

66. CisSearch: Software Package For Complex Analysis Of Gene Regulatory Sequences. // Proc. of the 3rd Annual RECOMB Satellite Workshop on Regulatory Genomics, Singapore, Jul. 17-18, 2006. — Singapore, 2006. — P. 100— 108.

67. Cheremushkin, E., Konovalova, Т., Valeev, Т., Shtokalo, D., Taraskina, A.

68. Software Package for Complex Analysis of Gene Regulatory. // Proc. of the 3rd International Conference "Genomics, Proteomics, Bioinformatics and Nanotechnologies for Medicine", Novosibirsk, Jul. 12-16, 2006. — P. 97.

69. Валеев Т. Ф. Сравнительный анализ методов поиска регуляторных модулей в последовательностях ДНК, использующих данные микроэррэев. //

70. Методы и инструменты конструирования и оптимизации программ. — Новосибирск, 2005. — С. 21-28.

71. Валеев Т. Ф. Генетический алгоритм как альтернатива для решения некоторых NP-полных задач. // Тез. докл. конференции-конкурса «Технологии Microsoft в информатике и программировании», Новосибирск, 22-24 февраля 2005. —С. 112-113.

72. Черёмушкин Е. С., Коновалова Т. Г., Валеев Т. Ф. Разработка пакета программ по анализу регуляторных областей ДНК. // Тез. докл. конференции-конкурса «Технологии Microsoft в информатике и программировании», Новосибирск, 22-24 февраля 2005. — С. 142-143.