Бесплатный автореферат и диссертация по биологии на тему

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

ВАК РФ 03.01.09, Математическая биология, биоинформатика

Автореферат диссертации по теме "Оценка достоверности кластеров функционально-значимых фрагментов биологических последовательностей"

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

Фурлетова Евгения Игоревна

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

03.01.09 Математическая биология, биоинформатика

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

Москва-2012

1 5 мдр 2012

005013868

005013868

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте математических проблем биологии РАН

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

Михаил Абрамович Рой гберг

Официальные оппоненты: Всеволод Юрьевич Макеев

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

Федеральное государственное бюджетное

учреждение науки

Институт общей генетики

им. Н. И. Вавилова РАН,

заведующий лабораторией

Иван Владимирович Кулаковский, кандидат физико-математических наук, Федеральное государственное бюджетное учреждение науки Институт молекулярной биологии им. В. А. Энгельгардта РАН, научный сотрудник

Ведущая организация: Федеральное государственное бюджетное

учреждение науки Институт теоретической и экспериментальной биофизики Российской академии наук

Защита состоится « Оз_» апреле_2012 г. в jSiOO ч. на заседании диссертационного совета Д 002.077.04 на базе Федерального государственного бюджетного учреждения науки Института проблем передачи информации РАН им. A.A. Харкевича по адресу 127994, Москва, ГСП-4, Большой Каретный переулок, д. 19, стр.1.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Института проблем передачи информации им. A.A. Харкевича РАН.

Автореферат разослан « Ос2 » М<хрГо>__2012 г.

Ученый секретарь диссертационного совета Д 002.077.04

доктор биологических наук, профессор Р°жкова

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

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

При таком подходе для решения задачи распознавания необходимо:

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

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

Говоря более формально, Р-значением кластера из г0 вхождений мотива, расположенного на участке длины щ относительно заданной вероятностной модели, называется вероятность обнаружить в случайной последовательности длины п0 кластер, содержащий не менее г0 вхождений мотива. Таким образом, встает вопрос о разработке эффективного метода вычисления ./'-значения, что и является основной задачей данного исследования.

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

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

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

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

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

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

2. Разработать алгоритмы для нахождения точного /'-значения кластера из п вхождений мотива, расположенною на участке длины ио, относительно трех видов вероятностных моделей: моделей Бернулли, Марковских моделей данного порядка и скрытых Марковских моделей (СММ).

3. Реализовать разработанные алгоритмы в виде компьютерных программ.

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

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

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

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

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

Для вычисления /^-значений был разработан алгоритм SufPref в трех модификациях, соответствующих трем видам вероятностных моделей: моделям Бернулли, Марковским моделям произвольного порядка и скрытым Марковским моделям (СММ). В алгоритме 8и№геГ впервые были использованы графы перекрытий слов, что обеспечило его преимущество в быстродействии по сравнению с ранее разработанными алгоритмами.

Личный вклад автора. Автору принадлежат все описанные в диссертации оригинальные теоремы, алгоритмы и программы.

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

Теоретическая и практическая значимость. Теоретическая значимость работы состоит в исследовании комбинаторных объектов, связанных с наборами слов, - графов перекрытий слов и затравок. Доказано, что среднее количество перекрытий слов в мотивах данного размера и данной длины при равномерном распределении вероятностей на множестве мотивов линейно зависит от размера мотивов и не зависит от их длины. Разработан алгоритм 8и№ге£ который вычисляет вероятность обнаружения в случайной последовательности длины па не менее п> вхождений заданного мотива. Распределение вероятностей для последовательностей длины Но может задаваться с помощью модели Бернулли, Марковской модели произвольного порядка или СММ. Разработана методика построения классификационных алфавитов.

Практическая значимость работы состоит в программной реализации разработанных алгоритмов. Программа и исходные коды доступны через интернет по адресу: http://server2.lpm.org.ru/bio/online/sf. Реализация предложенного метода используется при создании опытного образца программного комплекса «СИМВОЛ», разрабатываемого в рамках государственного контракта № 07.514.11.4004. Результаты исследования использовались при выполнении работ по темам «Сравнительный анализ структур белков и нуклеиновых кислот» (номер государственной регистрации 01.2.00409635), «Математические методы анализа белков и нуклеиновых кислот: связь между последовательностями, структурой и функцией» (номер государственной регистрации 01.2.00952309), а также

при выполнении проекта РФФИ 09-04-01053-а «Достоверность и полнота результатов при компьютерном анализе последовательностей биополимеров». Построенные классификационные алфавиты были использованы Л. Ноэ в программе YASS (http://bioinfo.lifl.fr/yass/). Эта программа успешно применяется для выравнивания аминокислотных последовательностей.

Апробация результатов. Материалы диссертации докладывались на международных и всероссийских конференциях, в том числе: на международной конференции по биоинформатике регуляции и структуры генома (BGRS, Новосибирск, 2008), на Московских международных конференциях по вычислительной молекулярной биологии (МССМВ, Москва, 2007, 2009,2011), международной конференции "The 2nd International Conference BIRD-ALBIO" (Австрия, 2008).

Публикации. По материалам диссертации опубликовано 8 печатных работ общим объемом 100 страниц. Из них три статьи в реферируемых научных изданиях (общий объем - 76 страниц), в том числе две статьи -в изданиях, входящих в список ВАК (общий объем - 48 страниц), а также пять тезисов докладов и препринтов (общий объем - 24 страницы).

Основные положения, выносимые на защиту.

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

2. Размер используемой памяти и время работы алгоритма SufPref описываются следующими формулами (ниже А - используемый алфавит, ()V(fí) - множество перекрытий слов в мотиве Н):

- для моделей Бернулли:

память: O(r0хт*\0V(H)\+mх |Я|); время: 0(n„ xru х(|0 V{H)\+\H\))-

- для Марковских моделей порядка К:

память: (){r0* |к+'+г0*тx\OV(H)\+mх|Я|); время: О(п0 *r0 *(Кх \А\Kn+\OV{H)\+\H\))-

- для СММ:

память: ГД|0|2х(|<9К(Я)|+|Я[)4-|()| хг„хтх\(ЩН)\+тх\Н\)-время: 0{\Q\2 хИо xr0 x(\OV(H)\+\H\)). Полученные оценки показали, что SufPref превосходит по характеристикам большинство существующих алгоритмов.

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

4. Разработанная методика построения классификационных алфави-

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

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения и списка литературы (130 наименований). Полный объем диссертации составляет 128 страниц, количество рисунков - 20, количество таблиц - 20.

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

Введение

Во введении дана общая характеристика работы.

Глава 1. Обзор литературы

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

Глава 2. Теоретическая основа алгоритма 8иЯ>геГ

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

Пусть даны: алфавит А ={аь ..., а^}; мотив Н = {к\, ..., /?,}, слова в котором имеют одинаковую длину т; вероятностное распределение на множестве слов заданной длины в алфавите А.

Целью работы является вычисление вероятности (Р-значения) встретить мотив Я по крайней мере г0 раз в случайной последовательности длины по. Будем предполагать, что т > от и г» > 1. В данной работе рассматриваются три вида вероятностных моделей: модели Бернулли, Марковские модели порядка К, где К<т, и скрытые Марковские модели.

2.2. Перекрытия слов в мотиве. Граф перекрытий

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

Определение 1. Слово будем называть перекрытием в мотиве Н, если существуют слова 1ь, Иг £ Н такие, что н' является префиксом 1ь и суффиксом й2. Множество всех перекрытий для Я будем обозначать через ОУ(Н).

Определение 2. Пусть и> 6 ()У(Н) и Я. Определим левого и правого предшественника 1рге<1(XV) и грге<1(м?) слова Н' следующим образом: 1р>-е^(\\>) = тах{и £ ()У(Н) | и является префиксом IV}; гргсс](м.') = шах{м е ОУ(Н) | и является суффиксом и>].

Определение 3. Два слова из мотива Я называются эквивалентными, если их левые и правые предшественники совпадают. Множество всех классов эквивалентности для мотива Я будем обозначать через Я*. Пусть Л* е Я* и ¡1 6 Л*. Тогда, по определению,

//)га/(/г*) = 1ргес1(1г); гргес/(И*) = гргес1(И).

Определение 4. Левым деревом перекрытий LOGu называется дерево LOG» = <V(H), £шо(Я)> где V{H) = OV{H) U Я* и

Vs,t(=V{H): (л,/)е£loo(#)<=> j=Ipred(/).

Аналогично, правым деревом перекрытий ROGh называется дерево ROGn = <V(H), EROg(H)>, где

\/s,ieV{H): (s,t)&EWo{H)<^s=rpred(t).

Графом перекрытий OVGu будем называть объединение левого и правого деревьев перекрытий.

Для Марковских моделей определения деревьев перекрытий отличаются от приведенных выше техническими деталями (см. раздел 2.2 диссертации). В автореферате эти детали не рассматриваются.

2.3. Среднее число перекрытий

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

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

Теорема 1. Пусть \А\>2 и т> 2. Тогда среднее количество overlap avg(s, т) перекрытий в мотивах размера от и длины s не превосходит с,у, где _

И+1 I 14" Ml— 1

Отметим, что если = 2, то с ~ 3,47; если \А\ = 4, то с ~ 1,73 и если \А\ = 20, то с = 1,11.

Гипотеза о линейной зависимости среднего числа перекрытий слов overlap_avg(s, т) от размера мотива s и отсутствии зависимости этого числа от длины слов т в мотиве была с помощью компьютерных экспериментов проверена для случая, когда вероятности отдельных слов в мотиве описываются неравномерным распределением Бернулли, а вероятность мотива - это произведение вероятностей входящих в него слов. В экспериментах рассматривался 4-буквенный алфавит, проверялись значения т от 8 до 50 с шагом 4 и значения s от 100 до 1000 с шагом 100, а также два распределения Бернулли - равномерное и неравномерное (с вероятностями {0,1; 0,2; 0,3; 0,4}). Эксперименты показали, что в обоих случаях overlap_avg(s, т) ~ s. Результаты экспериментов для неравномерного распределения представлены на рисунках 1 и 2, для равномерного распределения результаты аналогичны.

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

слов в мотивах, заданных с помощью этих матриц, равны соответственно т = 8 и т ~ 12. Значения порогов выбиралось так, чтобы размеры мотивов были примерно от 100 до 1000 слов. Показано, что отношение количества перекрытий к количеству слов в мотивах меняется от 0,04 до 0,09 для матрицы длины 8 и от 0,06 до 0,12 для матрицы длины 12.

Распределение вероятностей {0,1; 0,2; 0,3; 0,4}

1200 -1000 800 600 400 200 0

-s= 100 -s = 5()0 -s = 1000

12 16 20 24 длина слов в мотивах (т)

50

Рис. 1. Зависимость среднего числа перекрытий overlap avg{m,s) от параметров т и s, где т = 8, 12, 16, 20, 24 и s = 100, 500, 1000.

Распределение вероятностей {0,1; 0,2; 0,3; 0,4}

1200

1000

CD

> сз 800

1 1 600

w 400

о

200

0

# ^

rfP dSP ^

^ ^ Q3' & f ср

количество слов в мотивах (s)

Рис. 2. Зависимость среднего числа перекрытий overlap avg(s,m) от количества слов s в наборах при данной длине слов т - 10, где л = 100 • /, / = 1,...,10.

2.4. Текстовые множества

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

И(п, г) = {'Г £ А"| Т содержит не менее г вхождений мотива Н].

Очевидно, Р-зиачение кластера из г0 вхождений мотива Я, расположенного на участке длины п0, равно вероятности РгоЬ(В(по, пО). Приведем ряд определений и обозначений, которые используются в диссертации и связаны с перекрытиями слов.

Пусть х,и' е OV{H) U Я, х - префикс w; h* £ Я* .Тогда:

- 1еп(х) - длина х;

- Н(х) - подмножество слов из Я, заканчивающихся на х\

- OverlapPrefix(w) = {х £ ОК(Я)| л: является префиксом w}.

Если х - префикс w, то Васк(х, w) - такой суффикс слова w, что w - х-Васк(х, w). По определению:

Back(w}=Back(Ipred (w),w); Back(/;*) = (J Back(h).

Алгоритм SufPref для вычисления вероятностей множеств В(п, г) использует ряд текстовых множеств, которые определены ниже. Пусть Л G Я и w G OV(H). Тогда

R(n,r,h)={T&A"\'I' заканчивается на h&

& Т содержит ровно г вхождений Я};

E[n,r,h)={TsA"\T заканчивается на h &

& 'Г содержит не менее г вхождений Н};

D[n,r,w}= U R(n-len(Back{x,w)),r,H(x))-Back(x,w},

x&M-rLipPrcjhiw)

D(n,r,e)=0.

Соответственно, для класса эквивалентности /г*£ Я*

г,/;*)=£ R[n,r,h)\£'(;;,г,E{n,r,h).

Для указанных текстовых множеств доказаны следующие соотношения.

1. В[п ,r)=B[n-\,r)-AuR[n,r,H) (1)

2. R[n, r,h*)=E{n, r,h*)\E{n, r+\,h*) (2) 3. Если r> 1, то

E{n ,r, h*)=B(n-m,r- l)-h*UD{n~lcn{Back{h*}) ,r Jpred (h*)} Back(h*) (3) если r= 1, то

E{n,l,h*)=A"'"-h* (4)

4. D{n,r,w)=D{n-kn(Back{w)),r,lpred{w)}Back{w)liR(n,r,H(w)), (5)

5. R(n,r,H{w))-( (J R(n,r,H(x)))u( (J R{n,r,h*)). (6)

■veoc [hi hsll*,

w-rpred[ x) w-rpmHh* I

2.5. Вероятности текстовых множеств

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

множества В(п, г) и модели Бернулли получаем следующую формулу

п

РтЬ{В{п,г))=РгоЬ{В{п-\,г})-РгоЬ(Л)+РгоЬ{1{(п,г,Н))=^ Prob{R{k,r,H)).

к - т

Глава 3. Алгоритм SufPref для вычисления Р-зпачения участка, содержащего кластер вхождении мотива

Разделы 3.1-3.3. Общее описание алгоритма SufPref

В разделах 3.1-3.3 дано описание вариантов алгоритма SufPref, ориентированных соответственно на вероятностные модели Бернулли, СММ и Марковские модели. Различия между вариантами носят технический характер. Для краткости ниже описана только общая основа всех вариантов алгоритма SufPref. Во всех случаях основными структурами данных являются деревья пререкрытий LOGn и ROGn-

Целью алгоритма SufPref является нахождение вероятности Prob(B(na, Го)). Алгоритм SufPref в цикле по п = т + 1,..., и0 и, для каждого значения п, в цикле по г = 1,..., Га вычисляет следующие вероятности:

- Prob(B(n - то, г)), если п > 2т;

- Prob(R(n, г, //*)) для всех h* £ Н*\

- Prob(R(n, г, //(»•))) для всех н- е OV(H).

Для вычисления Prob{B(n - т, г)) используется соотношение (1). Вычисления Prob(R(n, г, h *)) выполняются путем обхода левого дерева перекрытий LOGn от корня к листьям. Сначала каждой из внутренних вершин w G OV(H) вычисляются вероятности Prob(D{n \Back(w)\, г, iv)) согласно (5). При этом используются значения аналогичных вероятностей, вычисленные для ранее просмотренных вершин. Далее, для листьев Л*еЯ* дерева LOGn алгоритм вычисляет Prob(E(n, г, h*)) (r= 1,..., ra + 1), используя вероятности

Prob(D(n -1 Back(w)|, г, и>)) и формулы (3) и (4); а затем -/Voft(7i(«,/", /г*)) согласно (2). Наконец, используя обход ROGn от листьев к корню алгоритм вычисляет вероятности Prob(R(n, г, H(w))) для всех w е OV(H) согласно (6).

Отметим, что Prob(R(n, г, Я(е))) = Prob(R(n, г, Н)).

На заключительном этапе алгоритм SufPref находит вероятности Prob(B(n0- т + \, Го)), ..., Prob(B(tio, г0)), используя формулу (1) и ранее вычисленные вероятности.

3.4. Предварительные построения

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

3.5. Анализ сложности алгоритма SufPref

В этом разделе дан теоретический анализ сложности алгоритма SufPref.

Теорема 2. Время работы алгоритма составляет:

- O(ni>xr0x(\OV(H)\+\H\)) для вероятностей модели Бернулли;

- 0(\Qf хяо xft> х(|(Ж(//)|+|Я|)) - для СММ;

- 0{паХГох(Кх\А\ки+\ОУ(Н)\+\Н\)) -для Марковской модели порядка

Размер используемой алгоритмом памяти составляет

- O(r0y-mx\OV(H)\+m*\H\) для вероятностной модели Бернулли;

- 0{Ш *(\OV{H)\m)+\Q\ т *\ОШУ+т*\Н\) - для СММ;

- O{r<iXK*\A\Kn+r0xmx\OV(H)\+m*\H\) - для Марковской модели порядка К.

Глава 4. Программная реализация алгоритма SufPref и ее апробация

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

Алгоритм SufPref для точного вычисления /-"-значения был реализован в программе на языке С++, работающей под Unix и Windows. Программа и подробная документация к ней доступны на сайте http://server2.lpm.org.ru/bio/online/sf. Созданы следующие версии программы: 1) Веб-версия; 2) версия, запускаемая с командной строки; 3) реализация в виде Руйоп-модуля.

Входными параметрами программы являются: 1) алфавиту}; 2) вероятностное распределение случайных последовательностей; 3) длина щ случайной последовательности; 4) мотив Н\ 5) минимальное количество г0 вхождений мотива. На выходе программа выдает найденное /'-значение. Все версии программы поддерживают работу с вероятностными моделями Бернулли, Марковскими моделями произвольных порядков и СММ.

4.2. Сравнение программы SufPref с программой AhoPro

В разделе 4.2. приведены результаты сравнения программы SufPref с программой AhoPro1, поддерживающей работу с моделями Бернулли и Марковскими моделями 1-го порядка. Программа AhoPro была выбрана для сравнения по двум причинам: во-первых, соответствующий ей алгоритм AhoPro имеет лучшие оценки времени работы и размера используемой памяти среди подобных алгоритмов; во-вторых данная программа эффективно применяется при решении задач биоинформатики. Для сравнения программ было вычислено /'-значение для следующих наборов тестовых данных:

1) алфавит-{А, С, G, Т};

2) вероятностное распределение на последовательностях задано следующими моделями:

- моделью Бернулли с вероятностями букв алфавита {0,3; 0,3; 0,2; 0,2};

1 Boeva V., ct al. Exact p-value calculation for heterotypic dusters of regulatory motifs and its application in computational annotation of cisregulatory modules. // Algorithms for molecular biology. 2007. Vol. 2, N. 13.1'. 25. lIpoipaM.ua AhoPro ;tocTymia no a/tpecy http://favorov.imb.ac.rn/ahokocc/.

- Марковской моделью первого порядка, условные вероятности которой заданы матрицей

0,3 0,3 0,2 0,2' 0,3 0,3 0,2 0,2 0,3 0,3 0,2 0,2 0,3 0,3 0,2 0,2

3) длина случайной последовательности «о : 1000;

4) минимальное количество «хождений п, ----- 10;

5) мотивы двух видов: (а) 10 и 11 случайных мотивов длины 8 и 12 соответственно (буквы имеют равномерное распределение); (б) 9 и 11 мотивов длины 8 и 12 соответственно, заданных матрицами позиционных весов и различными порогами.

Результаты сравнения показали: 1) для модели Бернулли ЗиГРгеГ работает в 4-20 раз быстрее АЬоРго и использует в среднем в полтора раза меньше памяти; 2) для Марковской модели БиП^геГ работает в 2-5 раз быстрее АЬоРго, но проигрывает по размеру используемой памяти не более чем на 20%.

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

Программа 5и£РгеГ была использована при нахождении статистической значимости шаблонов неупорядоченных участков в белках, то есть участков, пространственная структура которых не поддается определению методами кристаллографии. О. В. Галзитской и М. Ю. Лобановым была построена библиотека из 109 шаблонов, которые описывают неупорядоченные участки. Каждый шаблон - это слово в аминокислотном алфавите длиной от 6 до 50. Мотив, соответствующий шаблону, содержит все слова той же длины, которые отличаются от шаблона не более, чем в 20% позиций и удовлетворяют некоторым дополнительным условиям. Для каждого такого мотива А было подсчитано количество к(К) последовательностей белков, содержащих этот мотив, а также соответствующее 7-значение

ш,) т-ы-рм

где ДА, п) - вероятность (/-'-значение) хотя бы один раз обнаружить А в случайной последовательности длины п (я полагалось равным 260 -средней длине белка в базе данных); к(Н) - число последовательностей в базе данных, содержащих не менее одного вхождения А; Ы= 28727 - количество уникальных (не гомологичных друг другу по аминокислотной последовательности) белков в базе данных.

Для шаблонов, длина которых равна 15 и меньше, для вычисления ДА, п) использовалась разработанная программа Б^геЕ Отметим, что количество слов в множестве Н экспоненциально растет с увеличением длины шаблона И, поэтому точное вычисление /•'-значения для длинных

шаблонов становится невозможным. Поэтому для шаблонов, длина которых равна 16 и больше, использовалась оценка данной вероятности сверху G(h, п) > P(h, п), где G(h, п) = (п — т+ 1 )-Prob{Ii).

Предполагалось, что шаблон h является статистически значимым, если Z(h, п) больше, чем определенный ¿/-квантиль. Были рассмотрены 99-квантиль и 95-квантиль, значения которых равны 2,33 и 1,65 соответственно. Оказалось, что для 102 и 106 из 109 шаблонов Z-значение больше, чем 2,33 и 1,65 соответственно. Также оказалось, что 89 из 109 шаблонов имеют Z-значение больше 5, то есть являются перепредставленными в белках.

Глава 5. Построение классификационных затравок для нахождения локальных сходств аминокислотных последовательностей

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

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

5.1. Классификационные затравки. Основные определения

Пусть дан алфавит аминокислот А. Обозначим через Я = {<х, v>j х, v £ А} множество пар аминокислот.

Определение 5. Алфавит В называется классификационным, если:

- каждой букве а алфавита В соответствуют подмножество П(а) множества Я, разным буквам соответствуют разные подмножества;

- В содержит букву # такую, что Я(#) = {<х, х>\х £ А}, т.е. # означает совпадение символов, сопоставленных при выравнивании;

- множества, соответствующие буквам из алфавита В симметричны,

т. е. для любых аминокислот*,у е А и буквы а £ В выполняется: <х, у> е П(а) » <!', л> £ П(а).

Классификационной затравкой (одиночной) называется слово в алфавите В. Пусть з,, л2 £ А". Будем говорить, что выравнивание (.<ь л-2) образует затравочное сходство относительно к = о.\...а„, если <л-1[г], е /7(«,) для всех г'= 1,..., п. Будем говорить, что локальное сходство допускается затравкой ж, если оно содержит затравочное сходство относительно ж.

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

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

Пусть для каждой аминокислоты х £ А задана вероятность Ь(х) ее появления в аминокислотных последовательностях. Базовой вероятностью Ь(х, у) пары аминокислот <х, у> е П называется вероятность Ь(х, у) = Ь(х)-Ь(у). Кроме того, для каждой пары аминокислот <х,у>€П задана голевая вероятность ^{х, у). Говоря неформально, /(х, у) - это вероятность встретить сопоставление (х, у) в выравнивании сходных участков. Целевой вероятностью выравнивания слов называется произве-

дение

¿=1

Для классификационной буквы а £ В и классификационной затравки ж = «1.. .«„ определим: базовые вероятности:

/;(«)= X ФЖзО;М*)=ПМ<ч);

целевые вероятности:

/(«)= £ /(*,>■);/Ы=П/К)-

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

5.2. Классификационные алфавиты

В диссертации предложены три вида классификационных алфавитов: пороговый алфавит, иерархический транзитивный алфавит (ИТА) и неиерархический транзитивный алфавит (HTA).

Пороговый алфавит

Для каждой пары аминокислотр е П рассмотрим отношение

h{p) flp),b(p).

Упорядочим все пары аминокислот по возрастанию h(p). Пусть дан набор порогов Т= {/i,..., Ц. Каждому порогу t сопоставим классификационную букву a(t), которой соответствует множество пар аминокислот

mm {р £ n\ f{]))/h(p) > i\.

Такие буквы будем называть пороговыми. Пороговым алфавитом будем называть совокупность букв

B(T)={a(t)\te1}.

Пороговые буквы являются вложенными, то есть для любых двух порогов t\, Ii £ Т, где U > t2, выполняется:

Л(«(/,)) s Я(«(/:)).

'Грапзипшвпые алфавиты

Классификационную букву а будем называть транзитивной, если и только если

<*,.}'>, <>', -> е Л (а) => <х, "> 6 П(а).

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

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

5.3. Классификационные затравки

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

Автором диссертации с помощью программы Iedera2 были построены одиночные классификационные затравки длины 3-5, избирательности которых принадлежат промежутку [0,988; 1]. Также с помощью Iedera были вычислены чувствительности этих затравок, и среди затравок было отобрано Парето-множество, т. е. множество, в котором не су-

2 Kueherov G., ct. al. A unifying framework for seed .sensitivity and its application to subset seeds. // Journal of Bioinfomiatics and Computational Biology. 2006. Vol. 4, N. 2. P. 553-570.

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

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

Используя полученные в диссертационной работе классификационные алфавиты, Л. Ноэ в работе3 построил множественные классификационные затравки. Построенные затравки сравнивались с затравкой BLASTp с порогами 10-13 и множественной векторной затравкой4 с порогами 13-16. При сравнении были получены следующие результаты:

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

-Множественные пороговые затравки превосходят затравку BLASTp по чувствительности примерно на 5% при примерно равных избирательностях. Например при избирательности 0,999355 (соответствует затравке BLASTp с порогом 13) и при длине целевых выравниваний 32 чувствительность затравки BLASTp составляет 0,81925, а чувствительность лучшей из пороговых затравок - 0,869064.

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

Заключение

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

1. Разработан алгоритм SufPref для вычисления вероятности (/-"-значения) появления не менее г0 вхождений заданного мотива в случайной последовательности длины «о. Распределение вероятностей на множе-

3 Noc L., el. al. On subset seeds for protein alignment. // 1ЕШЛСМ Trans. Comput. Biol. lSioinf'ormalics. 2009. Vol. 6, N. 3.1'. 4H3-494.

4 Brejová В., et. al. Vector seeds: An extension lo spaced seeds. // Journal of Computer and System Sciences. 2005. Vol.70, N. 3. I'. 364-380; Brown 1). Optimizing multiple seed for protein homology search. // ШЕК/ЛСМ Transactions on Computational Biology and Bioinformatics. 2005. Vol. 2, N. 1. P. 29-38.

стве случайных последовательностей может задаваться с помощью моделей Бернулли, Марковских моделей порядка К, где К<т, и скрытых Марковских моделей.

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

3. С помощью компьютерных экспериментов было показано, что среднее число перекрытий overlap _avg(s, т) в случайных мотивах, слова в которых порождены в рамках моделей Бернулли, пропорционально количеству слов s в мотивах и не зависит от длины т этих слов. Для мотивов, слова в которых имеют равномерное распределение, была доказана теорема о том, что overlap avg(s, т) < c-s, где с - константа, зависящая от размера алфавита; с < 4. Из этого следует, что скорость работы алгоритма в среднем не зависит от длины слов в мотиве.

4. Алгоритм SufPref реализован в виде кросс-платформенного программного комплекса.

5. Проведено сравнение реализации алгоритма SufPref с реализацией алгоритма AhoPro для модели Бернулли и Марковской модели первого порядка. Для модели Бернулли SufPref работает в 4-20 раз быстрее AhoPro и использует в среднем в полтора раза меньше памяти. Для Марковской модели SufPref работает в 2-5 раз быстрее AhoPro, но проигрывает по размеру используемой памяти не более чем на 20%.

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

7. Построены классификационные алфавиты для анализа аминокислотных последовательностей: (1) пороговый алфавит, (2) иерархический транзитивный алфавит; (3) неиерархический транзитивный алфавит. Затравки над этими алфавитами не уступают по чувствительности и избирательности лучшим из ранее известных видов затравок.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1. Roytberg М. A., Gambin A., Noe L., LasotaS., Furletova E. I., Szczurek E., Kucherov G. On subset seeds for protein alignment. // IEEE/ACM Transactions on Computational Biology and Bioinformatics. 2009. Vol. 6, N. 3. P. 483-494.

2. Lobanov M. Y., Furletova E. I., Bogatyreva N. C., Roytberg M. A., Galzitskaya О. V. Library of disordered patterns in 3D protein structures. PLoS Computational Biology. 2010. Vol. 6, N. 10. P. 1-10.

3. Regnier M., Kirakosian Z., Furletova E. I., Roytberg M.A. A word counting gpaph. // London algorithmics 2008: theory and practice. 2009. P. 10-43.

4. Furletova E. I., Kucherov G., Noe L., Roytberg M. A., Tsitovich 1.1. Statistical approach to the design of subset seeds for protein alignment. // Proceedings of the International Moscow Conference on computational molecular biology. July 2007. P. 94.

5. Furletova E. [., Kucherov G., Noe L., Roytberg M. A., Tsitovich 1.1. Transitive subset seeds for protein alignment. // Proceedings of the 6th International Conference on Bioinformatics of Genome Regulation and Structure (BGRS). July 2008, Novosibirsk (Russia). P. 77.

6. Roytberg M. A., Gambin A., Noe L., Lasota S., Furletova E. I., Szczurek E., Kucherov G. Efficient seeding techniques for protein similarity search. // Proceedings of the 2nd International Conference BIRD-ALBIO. 2008. P. 466^78.

7. Regnier M., Furletova E. I., Roytberg M. A. An average number of suffix-prefixes. // Proceedings of the International Moscow Conference on computational molecular biology. 2009. P. 313-314.

8. Regnier M., Furletova E. I., Roytberg M. A., Yakovlev V. V. An algorithm for exact probability of pattern occurrences calculation. // Proceedings of the International Moscow Conference on computational molecular biology. 201 l.P. 320.

Подписано в печать 01 марта 2012 г.

Формат 60x90/16

Объём 1,00 п. л.

Тираж 100 экз.

Заказ №020312421

Оттиражировано на ризографе в ООО «УниверПринт»

ИНН/КПП 7728572912\772801001

Адрес: г. Москва, улица Ивана Бабушкина, д. 19/1.

Тел. 740-76-47,989-15-83.

http://www.univerprint.ru

Текст научной работыДиссертация по биологии, кандидата физико-математических наук, Фурлетова, Евгения Игоревна, Москва

61 12-1/700

РОССИЙСКАЯ АКАДЕМИЯ НАУК Федеральное государственное бюджетное учреждение науки Институт математических проблем биологии РАН

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

Фурлетова Евгения Игоревна

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

03.01.09 - Математическая биология, биоинформатика

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

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

Ройтберг М. А.

Москва 2012

ОГЛАВЛЕНИЕ

Введение........................................................................................3

Глава 1. Обзор литературы............................................................10

1.1. Мотивы биологических последовательностей и их вхождения......10

1.2. Вероятностные модели.......................................................13

1.3. Методы вычисления Р-значения кластера вхождений мотива.......16

1.4. Сходства биологических последовательностей..........................23

1.5. Затравки..........................................................................28

Глава 2. Теоретическая основа алгоритма SufPref..............................32

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

2.2. Перекрытия слов в мотиве. Граф перекрытий...........................32

2.3. Среднее число перекрытий....................................................37

2.4. Текстовые множества.............................................................46

2.5. Вероятности текстовых множеств............................................49

Глава 3. Алгоритм SufPref для вычисления /^значения участка, содержащего кластер вхождений мотива................................................................57

3.1. Алгоритм SufPref для моделей Бернулли.....................................57

3.2. Алгоритм SufPref для СММ....................................................62

3.3. Алгоритм SufPref для Марковских моделей.............................66

3.4. Предварительные построения...............................................69

3.5. Анализ сложности алгоритма SufPref.....................................73

Глава 4. Программная реализация алгоритма SufPref и ее апробация ....83

4.1. Программная реализация алгоритма SufPref..............................83

4.2.Сравнение программы SufPref с программой AhoPro..................84

4.3. Оценка статистической значимости шаблонов неупорядоченных участков в белках........................................................................................93

Глава 5. Построение классификационных затравок для нахождения локальных сходств аминокислотных последовательностей......................97

5.1. Классификационные затравки. Основные определения...............97

5.2. Классификационные алфавиты............................................100

5.3. Классификационные затравки.............................................111

Заключение.................................................................................117

Литература............................................................................................................119

ВВЕДЕНИЕ

Актуальность темы исследования

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

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

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

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

встает вопрос о разработке эффективного метода вычисления Р-значения, что и является основной задачей данного исследования.

Проблема оценки достоверности предсказанных функционально-значимых вхождений мотива возникает в различных областях биоинформатики. Среди ученых, внесших значительный вклад в решение этой проблемы, О. Берг, Д. Гильберт, В.Ю. Макеев, A.A. Миронов, Г. Нюэль, М. Ренье, П. фон Хиппель и ряд других. Примером области, где необходима оценка достоверности кластеров сайтов, является идентификации потенциальных кластеров сайтов связывания белков - факторов регуляции транскрипции (ССФРТ), т.е. участков ДНК, которые взаимодействуют с факторами транскрипции. Здесь мотив - это набор допустимых сайтов связывания данного фактора транскрипции. Во многих существующих программах распознавания кластеров ССФРТ отбор значимых результатов производится на основе вычисленного Р-значения. Сказанное выше определяет актуальность выбранной темы.

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

Для решения задачи поиска локальных сходств, как правило, применяются фильтрационные методы. В частности, именно так работают программы для поиска локальных сходств, такие как BLAST [92], Owen [96], YASS [99]. Эти методы основаны на предварительной фильтрации пространства поиска. Сначала находят короткие гомологичные фрагменты последовательностей (якоря или затравочные сходства). Затем якоря расширяют до выравниваний более длинных фрагментов путем анализа окрестностей якорей. Образец для поиска затравочных сходств называется затравкой. Фильтрационные методы

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

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

Цели и задачи исследования

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

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

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

2. Разработать алгоритмы для нахождения точного Р-значения кластера из г вхождений мотива, расположенного на участке длины п, относительно трех видов вероятностных моделей: моделей Бернулли, Марковских моделей данного порядка и скрытых Марковских моделей (СММ).

3. Реализовать разработанные алгоритмы в виде компьютерных программ.

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

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

Научная новизна и теоретическая ценность работы

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

Для вычисления Р-значений был разработан и алгоритм 8и№геГ в трех модификациях, соответствующих трем видам вероятностных моделей: моделям Бернулли, Марковским моделям произвольного порядка и скрытым Марковским моделям (СММ). В разработанном алгоритме впервые был использован граф перекрытий слов, что обеспечило его преимущество в быстродействии по сравнению с ранее разработанными алгоритмами. В отличие от большинства аналогичных алгоритмов, время работы 8и£РгеГ в среднем не зависит от длины мотива и размера алфавита.

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

Практическое значение работы

Практическое значение работы состоит в программной реализации разработанных алгоритмов. В частности, алгоритм 8и1Рге1? реализован в виде кросс-платформенного программного комплекса. Программа и исходные коды доступны через интернет по адресу: http://server2.lpm.org.ru/bio/online/sf. Реализация предложенного метода используется при создании опытного образца программного комплекса "СИМВОЛ", разрабатываемого в рамках государственного контракта №07.514.11.4004. Результаты исследования использовались

при выполнении работ по темам «Сравнительный анализ структур белков и нуклеиновых кислот» (номер государственной регистрации 01.2.00409635), «Математические методы анализа белков и нуклеиновых кислот: связь между последовательностями, структурой и функцией» (номер государственной регистрации 01.2.00952309), а также при выполнении проекта РФФИ 09-04-01053-а «Достоверность и полнота результатов при компьютерном анализе последовательностей биополимеров».

Построенные классификационные алфавиты были использованы Л. Ноэ в программе УАБЗ (ЬЦр^ютГо.НА.йУуазз/). Эта программа успешно применяется для выравнивания аминокислотных последовательностей.

Основные положения, выносимые на защиту

1. Разработанный алгоритм 8и£РгеГ корректно вычисляет вероятность (Р-значение) появления не менее г вхождений мотива Н, слова в котором имеют одинаковую длину т, в случайной последовательности длины п; распределение вероятностей на множестве случайных последовательностей может задаваться с помощью моделей Бернулли, Марковских моделей произвольного порядка и скрытых Марковских моделей.

2. Размер используемой памяти и время работы алгоритма 8и1РгеГ описываются следующими формулами (ниже А - используемый алфавит, 0¥(Н) -множество перекрытий слов в мотиве Н):

- для моделей Бернулли:

память: 0(гхтх\0У(Н)\+тх\Н\); время: 0{пуг*(\0У(Н)\+\Н\))\

- для Марковских моделей порядка К:

память: 0(г*Кх\А\к+1+гхтх\ОУ(Н)\+тх|Я|); время: 0(пхгх(Кх\А\к+1+\0Г(Щ+\Н\));

-для СММ:

память: 0(|£|2 *(|0К(Я)|+|Я|)+|£| *г хт х\ОГ(Н)\+т х|Я]); время: 0(\д\2хпхгх(\ОУ(Н)\+\Н])). Полученные оценки показали, что SufPref превосходит по характеристикам большинство существующих алгоритмов.

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

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

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

Диссертация состоит из введения, пяти глав, заключения и списка литературы (130 наименований). Полный объем диссертации составляет 128 страниц, количество рисунков - 20, количество таблиц - 20.

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

В главе 2 даны основные определения и изложена теоретическая основа алгоритма 8и1РгеГ для вычисления Р-значения кластера вхождений мотива. В разделе 2.1 дана постановка задачи. В разделе 2.2 введены понятия, относящиеся к мотивам, дано определение графа перекрытий слов - основной структуры, используемой при работе алгоритма. Раздел 2.3 посвящен исследованию зависимости числа перекрытий от количества слов и длины слов в мотивах. В разделе 2.4 определены текстовые множества, связанные с вычислением Р-значения кластера вхождений мотива, и выведены связывающие их соотношения. В разделе 2.5 выведены формулы для вычисления вероятностей этих текстовых множеств.

Глава 3 посвящена программной реализации алгоритма 8и1РгеГ. В разделах 3.1 - 3.3 дано описание вариантов алгоритма 8и:11Рге1?, ориентированных соответственно на вероятностные модели Бернулли, СММ и Марковские модели. Различия между вариантами носят технический характер. Во всех случаях основной структурой при вычислениях является граф перекрытий. В разделе 3.4 описаны алгоритмы построения графа перекрытий и инициализации структур данных, выполняемые на предварительном этапе работы

ВиАРге^ В разделе 3.5 дан теоретический анализ сложности работы алгоритма 8и£Рге£ Также в этом разделе описаны результаты сравнения коэффициентов в оценках времени работы и размеров используемой памяти при работе алгоритма ЗиЯ3^ и алгоритма 8ра11 [54].

Глава 4 посвящена программной реализации алгоритма 8и£РгеГ и ее апробации. В разделе 4.1 обсуждаются технические детали программы 8и1РгеГ. В разделе 4.2 приведены результаты сравнения программы 8иАРгеГ и программы А1юРго [56]. В 4.3 обсуждается использование 8иИ>геГ при нахождении статистической значимости шаблонов неупорядоченных участков в белках, то есть участков, пространственная структура которых не поддается определению методами кристаллографии. Также в этом разделе описан быстрый метод, позволяющий оценить Р-значение вхождений шаблонов.

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

ГЛАВА 1. Обзор литературы

1.1. Мотивы биологических последовательностей и их вхождения

1.1.1. Мотивы биологических последовательностей

В биоинформатике мотивом называется набор фрагментов (слов), характерных для функционально-значимых участков определенного вида. Место положения слова из мотива в биологической последовательности называется вхождением (или сайтом вхождения) мотива. Набор сайтов, расположенных на определенном участке биологической последовательности, называется кластером вхождений (или кластером сайтов) мотива. В настоящей диссертации мотивом будем называть заданный список слов в некотором алфавите А. Для нуклеотидных последовательностей А = {А, С, G, Т} и для аминокислотных последовательностей

А = {А, С, D, Е, F, G, H, I, К, L, M, N, Р, Q, R, S, Т, V, W, Y}.

В качестве примеров мотивов можно привести участки связывания белков - факторов рег