Содержание к диссертации
Введение
Глава 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
- Вероятностные модели
- Перекрытия слов в мотиве. Граф перекрытий
- Алгоритм SufPref для СММ
- Сравнение программы SufPref с программой AhoPro
Введение к работе
Актуальность темы. Одним из важных направлений биоинформатики является распознавание функционально-значимых участков биологических последовательностей. Как правило, такие участки отличаются повышенным содержанием определенных слов. Набор слов, характерных для класса функционально-значимых участков называется мотивом; место положения слова из мотива в биологической последовательности называется вхождением (или сайтом вхождения) мотива; набор сайтов, расположенных на анализируемом участке биологической последовательности, называется кластером вхождений (или кластером сайтов) мотива. Таким образом, задачу распознавания функционально-значимых участков можно решать путем поиска участков с повышенным содержанием слов из соответствующего мотива.
При таком подходе для решения задачи распознавания необходимо:
1) уметь оценивать достоверность (функциональную значимость) найденного кластера вхождений мотива и 2) определять характерную для мотива последовательность мономеров.
В биологических последовательностях кластеры вхождений определенного мотива могут появляться не только в результате естественного отбора, но и случайно. В качестве меры достоверности кластера вхождений мотива в биологической последовательности часто используется вероятность {Р-значение) появления такого кластера в случайной последовательности соответствующей длины при подходящей вероятностной модели. Чем меньше вероятность обнаружить в случайной последовательности кластер, в котором количество вхождений мотива превышает заданный порог, тем больше оснований считать, что наличие такого кластера обусловлено его биологической значимостью.
Говоря более формально, Р-значением кластера из Го вхождений мотива, расположенного на участке длины щ относительно заданной вероятностной модели, называется вероятность обнаружить в случайной последовательности длины т кластер, содержащий не менее г0 вхождений мотива. Таким образом, встает вопрос о разработке эффективного метода вычисления /"-значения, что и является основной задачей данного исследования.
Проблема оценки достоверности предсказанных функционально-значимых вхождений мотива возникает в различных областях биоинформатики. Среди ученых, внесших значительный вклад в решение этой проблемы, О. Берг, Д. Гильберт, В. Ю. Макеев, А. А. Миронов, Г. Нюэль, М. Ренье, П. фон Хиппель и ряд других. Примером области, где необходима оценка достоверности кластеров сайтов, является идентификация потенциальных кластеров сайтов связывания белков - факторов регуляции транскрипции (ССФРТ), т. е. участков ДНК, которые взаимодействуют с факторами транскрипции. Здесь мотив - это набор до-
пустимых сайтов связывания данного фактора транскрипции. Во многих существующих программах распознавания кластеров ССФРТ отбор значимых результатов производится на основе вычисленного /"-значения. Сказанное выше определяет актуальность выбранной темы.
В представленной работе рассматриваются только мотивы, в которых все слова имеют одну и ту же длину, которая называется длиной мотива. Именно такими являются, например, мотивы, описывающие ССФРТ. Размером мотива называется количество слов в мотиве.
Цели и задачи исследования. Целью проведенного исследования является разработка эффективного метода точного вычисления вероятности (/"-значения) обнаружения в случайной последовательности длины По не менее Го вхождений заданного мотива для различных вероятностных моделей генерирования последовательностей.
Исходя из поставленной цели, были сформулированы следующие задачи.
Исследовать комбинаторные свойства графов перекрытий слов, в частности, - зависимость количества перекрытий слов, входящих в мотив от размера и длины мотива.
Разработать алгоритмы для нахождения точного f-значения кластера из Го вхождений мотива, расположенного на участке длины щ, относительно трех видов вероятностных моделей: моделей Бернулли, Марковских моделей данного порядка и скрытых Марковских моделей (СММ).
Реализовать разработанные алгоритмы в виде компьютерных программ.
Исследовать целесообразность применения классификационных затравок для поиска локальных сходств в аминокислотных последовательностях, что в свою очередь позволяет строить мотивы, описывающие функционально-значимые участки последовательностей. Разработать методику построения классификационных алфавитов.
Применить разработанные программы для анализа реальных аминокислотных последовательностей.
Методы исследования. В работе использованы методы теории алгоритмов, теории вероятностей, математической статистики, теоретической молекулярной биологии и биоинформатики.
Достоверность результатов. Достоверность результатов обеспечивается адекватностью используемых методов теории алгоритмов, теории вероятностей, математической статистики и биоинформатики, верификацией математических моделей, а также сравнением аналитических результатов с результатами математического моделирования.
Научная новизна. Получена оценка для среднего количества перекрытий слов, входящих в случайный мотив при равномерном распределении вероятностей мотивов. Доказано, что среднее количество перекрытий линейно зависит от размера мотива и не зависит от его длины.
Для вычисления /"-значений был разработан алгоритм SufPref в трех модификациях, соответствующих трем видам вероятностных моделей: моделям Бернулли, Марковским моделям произвольного порядка и скрытым Марковским моделям (СММ). В алгоритме SufPref впервые были использованы графы перекрытий слов, что обеспечило его преимущество в быстродействии по сравнению с ранее разработанными алгоритмами.
Личный вклад автора. Автору принадлежат все описанные в диссертации оригинальные теоремы, алгоритмы и программы.
Автору принадлежит разработка, анализ и реализация алгоритма SufPref для точного вычисления /"-значения вхождений мотивов, см. [3], [8], а также проведение компьютерных экспериментов для сравнения SufPref с другими алгоритмами. Автором была доказана теорема о среднем числе перекрытий [7] (см. раздел 2.3) и ряд утверждений, приведенных в диссертации. В работе [2] автору принадлежит вычисление статистической значимости шаблонов неупорядоченных участков в белках. В работах, описанных в публикациях [1], [4], [5], [6], автору принадлежат алгоритмы для построения классификационных алфавитов. Автор реализовал разработанные алгоритмы в программе и построил соответствующие классификационные алфавиты и одиночные классификационные затравки над этими алфавитами.
Теоретическая и практическая значимость. Теоретическая значимость работы состоит в исследовании комбинаторных объектов, связанных с наборами слов, - графов перекрытий слов и затравок. Доказано, что среднее количество перекрытий слов в мотивах данного размера и данной длины при равномерном распределении вероятностей на множестве мотивов линейно зависит от размера мотивов и не зависит от их длины. Разработан алгоритм SufPref, который вычисляет вероятность обнаружения в случайной последовательности длины щ не менее Го вхождений заданного мотива. Распределение вероятностей для последовательностей длины По может задаваться с помощью модели Бернулли, Марковской модели произвольного порядка или СММ. Разработана методика построения классификационных алфавитов.
Практическая значимость работы состоит в программной реализации разработанных алгоритмов. Программа и исходные коды доступны через интернет по адресу: . Реализация предложенного метода используется при создании опытного образца программного комплекса «СИМВОЛ», разрабатываемого в рамках государственного контракта № 07.514.11.4004. Результаты исследования использовались при выполнении работ по темам «Сравнительный анализ структур белков и нуклеиновых кислот» (номер государственной регистрации 01.2.00409635), «Математические методы анализа белков и нуклеиновых кислот: связь между последовательностями, структурой и функцией» (номер государственной регистрации 01.2.00952309), а также
при выполнении проекта РФФИ 09-04-01053-а «Достоверность и полнота результатов при компьютерном анализе последовательностей биополимеров». Построенные классификационные алфавиты были использованы Л. Ноэ в программе YASS (). Эта программа успешно применяется для выравнивания аминокислотных последовательностей.
Апробация результатов. Материалы диссертации докладывались на международных и всероссийских конференциях, в том числе: на международной конференции по биоинформатике регуляции и структуры генома (BGRS, Новосибирск, 2008), на Московских международных конференциях по вычислительной молекулярной биологии (МССМВ, Москва, 2007, 2009, 2011), международной конференции "The 2nd International Conference BIRD-ALBIO" (Австрия, 2008).
Публикации. По материалам диссертации опубликовано 8 печатных работ общим объемом 100 страниц. Из них три статьи в реферируемых научных изданиях (общий объем - 76 страниц), в том числе две статьи -в изданиях, входящих в список ВАК (общий объем - 48 страниц), а также пять тезисов докладов и препринтов (общий объем - 24 страницы).
Основные положения, выносимые на защиту.
Разработанный алгоритм SufPref корректно вычисляет вероятность (^-значение) появления не менее Го вхождений мотива Н, слова в котором имеют одинаковую длину т, в случайной последовательности длины щ\ распределение вероятностей на множестве случайных последовательностей может задаваться с помощью моделей Бернулли, Марковских моделей произвольного порядка и скрытых Марковских моделей.
Размер используемой памяти и время работы алгоритма SufPref описываются следующими формулами (ниже А - используемый алфавит, OV{H) - множество перекрытий слов в мотиве Н):
- для моделей Бернулли:
память: O(r0xmx\OV(H)\+mx\H\); время: O(n0xr0x(\OV(H)\+\H\));
- для Марковских моделей порядка К:
память: O(r0xKx\A\K+1+r0xmx\OV(H)\+mx\H\); время: O(n0xr0x(Kx \A\K+1+\OV(H)\+\H\));
- для СММ:
память: O(\Q\2x(\OV(H)\+\H\)+\Q\xr0xmx\OV(H)\+mx\H\);
время: 0(\Q\2xn0xrox(\OV(H)\+\H\)). Полученные оценки показали, что SufPref превосходит по характеристикам большинство существующих алгоритмов.
Среднее количество перекрытий слов в мотивах данного размера и данной длины при равномерном распределении вероятностей на множестве мотивов линейно зависит от размера мотивов и не зависит от их длины.
Разработанная методика построения классификационных алфави-
тов позволяет получать классификационные затравки, которые не уступают лучшим из ранее известных видов затравок по чувствительности и избирательности.
Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения и списка литературы (130 наименований). Полный объем диссертации составляет 128 страниц, количество рисунков - 20, количество таблиц - 20.
Вероятностные модели
Существует множество способов задания мотива. Самый простой способ - перечислить все содержащиеся в мотиве слова. Приведем другие широко распространенные способы.
Одним из них является задание мотива с помощью матрицы позиционных весов (МПВ, профиль) и порога. Такие матрицы были введены и применены в молекулярной биологии Грибсковым, Эйзенбергом и их соавторами [16-18]. Пусть дана матрица позиционных весов М = { {aJ)}aeAM m . Строки М соответствуют буквам из алфавита А, столбцы - позициям слов из мотива. Пусть дано слово х = аь ... ат длины т. Тогда вес слова х будет равен Мотив, заданный МПВ и порогом состоит из всех слов в А длины т, веса которых больше этого порога.
Говоря неформально, элемент w(a, і) показывает частоту появления символа а є А в /-ом столбце множественного выравнивания последовательностей, которое соответствует матрице М. Часто значения в МПВ преобразуются в логарифмы относительных различий. Пусть р(а, і) - частота появления символа а в столбце і множественного выравнивания, а р{а) - частота появления а во всех выравниваемых последовательностях. Тогда
Другие способы задания элементов матрицы позиционных весов рассматривались в работах [6, 8, 19-21]. В таблицах 1.1.1 и 1.1.2 даны матрицы позиционных весов МПВ8 и МПВ 12 (в транспонированном виде), описывающие два регуляторных сайта Drosophila: «en» длины 8 и «dref» длины 12 [128]. Эти матрицы использовались при выполнении компьютерных экспериментов, описанных в разделах 2.3, 3.5 и 4.2 настоящей диссертации.
Еще одним распространенным способом представления мотива является сигнатура. Часто также в биологической литературе используется термин консенсус. Рассмотрим пример задания мотива нуклеотидных последовательностей с помощью сигнатуры A[CT]N{A}. Такое задание означает, что мотив состоит из слов длины 4, в первой позиции которых стоит нуклеотид А, во второй - С или Т, в третьей - любой нуклеотид, и в четвертой - любой нуклеотид, кроме А. Сигнатура может быть представлена в виде слова в алфавите, буквы которого соответствуют подмножествам алфавита последовательностей. Например, для обозначений множеств нуклеотидов была разработана номенклатура IUPAC [22].
Также отметим способ представления мотива с помощью пары (/?, d), где каждое слово в мотиве может быть получено из слова h (шаблона) применением не более чем d операций с использованием некоторой группы операторов. Такими операторами могут быть замены, делеции, симметричные отражения мотива, переходы на комплементарную цепь и т.д. В таких случаях говорят, что в мотив входят все слова, для которых редакционное расстояние для данной группы операторов не превышает d. Таблица 1.1.1.
В биологических последовательностях кластеры вхождений мотива могут быть не только биологически значимыми, но и появляться случайно. Отсюда встает проблема оценки достоверности (статистической значимости) кластеров. Анализ реальных биологических последовательностей показывает, что функционально-значимые вхождения мотивов появляются в биологических последовательностях чаще или реже, чем это ожидается [1, 23], то есть являются перепредставленными или недопредставленными. Поэтому в качестве меры достоверности (биологической значимости) кластера вхождений мотива часто используется Р-значение [1, 56].
В статистике Р-значение - это вероятность наблюдать некоторое событие при условии выполнения нулевой гипотезы. Решение о принятии или отклонении нулевой гипотезы принимается при сравнении Р-значения с выбранным уровнем значимости. Применительно к указанной задаче, Р-значение - вероятность Р(Н, п, г) обнаружить не менее г вхождений мотива Н в случайной последовательности длины п в рамках некоторой вероятностной модели. Если считать, что вхождения мотива имеют нормальное распределение N(pi, а), то для оценки достоверности вхождений можно также использовать Z-значение,
Пусть дан алфавит А={щ, ...,ащ}. Ниже будут представлены три вида вероятностных моделей, задающих распределения вероятностей букв из А в случайных последовательностях: модели Бер ну лл и, Марковские модели заданного порядка и СММ.
Пусть р(а) - вероятность встретить букву а є А в некоторой позиции случайной последовательности при условии, что данное событие не зависит ни от позиции, ни от предшествующих букв последовательности. Вероятности удовлетворяют условию 2 р{а) -1. Относительно моделей Бернулли вероят аєА ность РгоЬв(м?) слова w равна произведению вероятностей букв w. Такая модель используется во многих работах по биоинформатике. Например, в работах [52, 56, 120, 121].
При Марковской модели порядка К вероятность появления буквы в некоторой позиции зависит от К предыдущих позиций. При задании Марковской модели порядка К необходимо определить: 1. Для всех слов q = а\...аке А и букв а є А условные вероятностиp(a\q) встретить букву а в некоторой позиции случайной последовательности при условии, что в К предыдущих позициях стояли буквы а\, ..-,ак соответственно. 2. Начальное распределение вероятностей S(q) для всех слов q є А . Относительно данной модели вероятность слова w=w1w2...w„e А" равна п VrobM{w) = S{wv..wK)- Y[p(wi\wi-K-wi-\) і=К+1 Модель Бернулли может быть описана Марковской моделью нулевого порядка. Примерами использования Марковских моделей заданного порядка могут служить работы [25, 35, 37, 42-44 ].
Перекрытия слов в мотиве. Граф перекрытий
Пусть даны две последовательности s, t и их выравнивание V = (S,T). Вес выравнивания W{V) можно найти как суммарный вес сопоставлений где W(S[i],T[i]) - вес сопоставления символов S[i] и T[i], I - длина последовательностей S и Т. В простейшем случае, при выравнивании нуклеотидных последовательностей вес совпадений полагают равным единице, а несовпадений - нулю. Для определений весов сопоставления аминокислот используют матрицы замен.
Элементами матриц замен являются веса сопоставлений символов некоторого алфавита. Для аминокислот матрицы замен, как правило, вычисляются по частотам замен символов в среднем по банку структурных выравниваний белковых семейств. В основе этих матриц косвенно лежат физико-химические свойства аминокислот. Очевидно, что такая матрица зависит от анализируемого банка и от метода оценки частот замен. На сегодняшний день существует несколько семейств матриц замен аминокислот, наиболее известные из них: РАМ [81], BLOSUM [82], GONNET [83]. Матрицы в этих семействах получены, исходя из частот замен аминокислот в гомологичных фрагментах эволюционно близких белков, различные матрицы в серии различаются степенью близости использованных фрагментов.
Рассмотрим несколько подходов к определению штрафов за пропуски, т.е. весов сопоставлений символов вида (х, _). В одном из широко используемых подходов [84], за все пропуски назначают постоянный штраф -а, где а -константа. Однако с точки зрения эволюционных событий, наличие пропусков длиной в несколько символов (множественные пропуски) соответствует единичному событию, причем длинные пропуски для родственных последовательностей менее вероятны, чем короткие. Также используют аффинную схему штрафов [85, 86] a(d) = A + B-d , где d - длина множественного пропуска, А - штраф за начало пропуска, а В -штраф за продолжение пропуска. Существует два основных вида методов выравнивания биологических последовательностей: методы динамического программирования и фильтра ционные методы. Среди методов динамического программирования наиболее популярными являются: алгоритм Нидельмана-Вунша [88] для глобальных выравниваний и алгоритм Смита-Уотермана [89] для локальных выравнива ний. Данные алгоритмы имеют вычислительные сложности 0(п т), где пит - длины последовательностей. Среди фильтрационных алгоритмов можно вы делить: FASTA[90, 91], BLAST [92, 93], PatternHunter [94, 95], Owen [96, 97, 98], YASS [99]. Ниже дадим описание метода Смита-Уотермана и общую схему работы фильтрационных методов.
Пусть даны две последовательности s = sls2...sm и t = txt2 ...tn над конечным алфавитом А. Целью метода Смита-Уотермана является нахождение фрагментов х и у последовательностей s и t, имеющих максимальный вес глобального выравнивания среди всех пар фрагментов s и t. Пусть Score(i,j) -максимальный вес выравнивания среди всех фрагментов префиксов s[l, /] и t[l,j] последовательностей s и t, i= 1,..., m,j = 1,..., п. Базовые условия таковы: Score(i,0) = ScoreiO, j) = 0; Общее рекуррентное соотношение имеет следующий вид: о ,Score{i-\,j-\) + W{s\i],t[j]) Score(i,j) = max\ . (1.4.1) Score(i -1, j) + W{s[i], _) Score{i,j-\) + W{_,t[j})
Вычисления происходят методом динамического программирования. Для всех пар (i,j) алгоритм находит Score(i,j). Если Score(i,j) Ф 0, то алгоритм для пары (/,_/) сохраняет ссылку на предшествующую пару, доставляющую максимум в соотношении (1.4.1). Таким образом, будет найдена пара (i ,j ), для которой Score{i ,j ) максимально. Далее, идя по сохраненным ссылкам от пары Q J \ алгоритм находит локальное выравнивание максимального веса.
При поиске сходств методами динамического программирования используется матрица сходств, строки которой соответствуют буквам одной последовательности, а столбцы - буквам другой последовательности.
В работе [129], по-видимому, впервые была применена техника фильтрации области поиска с помощью затравок, которая в дальнейшем получила широкое распространение. Эта техника основана на том, что поиск точных совпадений заданной длины в последовательностях длины тип может быть выполнен за время 0(m+n+R), где R - количество найденных совпадений. В задачах биоинформатики этот алгоритм был впервые применен в работе [130] для поиска совпадений длины 1. Новация работы [129] состояла в предложении искать совпадения произвольной длины s. При s log(m+n) получается (в среднем) линейное время поиска. При этом совпадения меньшей длины могут встретиться даже в случайных последовательностях длин типи, поэтому, как правило, не представляют интереса. Описанный подход был развит в работе Р.Вилбура и Д.Липмана [90]; в этой работе были сформулированы две алгоритмические идеи, позднее получившие широкое распространение. Одна из них - выделение т.н. «значимых полос» - областей матрицы сходства, содержащих аномально большое количество «затравочных» сходств и дальнейшее построение выравнивания только внутри выделенных областей. Вторая -строить выравнивание не как точный путь в матрице сходства, а как цепь, составленную из локальных сходств.
Алгоритм SufPref для СММ
Пусть дан алфавит А = {ah аг,..., ащ} и вероятности букв алфавита / («;), где / = 1,..., \А\. При) Доказательство следует из соотношений (2.4.2) - (2.4.9) и свойств моделей Бернулли.
Пусть задана СММ G = Q, данной вероятностной модели вероятность слова х будем обозначать через РгоЬв{х). Вероятность слова равна произведению вероятностей букв этого слова. Пусть w є V(H)\H - внутренняя вершина графа перекрытий и /г є Я - лист графа перекрытий. Утверждение 2.5.1. Пусть п т. Тогда 1) если и т, то: Рг оЬв (В(п, г)) = Рг obB (R(n, г, Я)) = Рг obB {Е{пь г, Я)) = 0 ; 2) если п = т, то: a) если г = 1, то: ProbB(R(mXh )) = robB(E(mXh )) = robB(h ); Рг obB (B(m,V ) = Pr obB (R(mX Щ) = Pr obB (E(mX Щ) = Pr obB (Я); b) если г 1, то: Pr obB (B(m, r)) = Рг o6B (Л(ш, г, Я)) = Pr oZ B (E(m, r, H)) = 0. Доказательство очевидно. Утверждение 2.5.2. Пусть п т. Тогда ?robB(B{n,r)) = VxobB(R(k,r,H)). (2.5.1) к=т Доказательство. Исходя из формулы (2.5.1) и из свойств данной вероятностной модели, получаем Pr obB (В(п,г)) = Рг оЪв (В(п -1, г)) Рг оЪв (А) + Pr o6g (R(n, г, #)) = = Рг о6д (В(п -1, г)) + Pr obB (R(n, г,Н)). Тогда Pr obB (В(п, г)) - Рг оЪв (В(п -1, г)) = Pr ов (R(n, г, Я)). Отсюда, получаем формулу (2.5.1). Утверждение 2.5.3. Пусть п т. Тогда 1) Pr obB (R(n, г, /г )) = Pr obB (Е(п, г, /г )) - Рг оЪв (Е(п, г + 1, /г )); (2.5.2) 2) если г = 1, то ?robB(E(nXh )) = robB(h ); (2.5.3) если г 1, то п-т Pr obB (Е(п, г, /г )) - Pr obB (R(k, г -1, Я)) Pr оЪв (/г ) + + Pr obB (D(n - len(Back(h )), г-I, lpred{h ))) Pr obB (Back(h )); (2.5.4) 3) если lpred(w) = є, то Pr obB (D(n,r, w)) = Pr obB (R(n,r,H{w))); (2.5.5) иначе, Pr obB (D(n, r, w)) = Pr obB (D(n — len(Back(w)), r, lpred{wj) Pr obB (Back(w)) + + robB(R(n,r,H(w))); (2.5.6) 4) ( \ ( \ РгоЬв(Я(п,г,Н(х))) + J vobB(R(n,r,h )) А єЯ , w=rpred(h ) xeOV(H),w=rpred(x) ?robB(R(n,r,H(w))) = (2.5.7Q0, я, 6 (задан конечно-автоматный генератор вероятностей). Ниже q будет обозначает произвольное состояние из Q. Понятия вероятности ProbG(S), конечной вероятности Pr obG(S,q) и условной конечной вероятности ProbG(q\S,q) множества S были введены в разделе 1.2. Вероятность VrobG(S)может быть найдена путем суммирования конечных вероятностей FrobG(S,q), т.е. VxobG{S) = J?vobG{S,q). Пусть д є Q, а є А, х є А и Мс А . Введем обозначения: - Start(a, q) = {q є Q\ %{д ,a,q) 0}; - Start{x, q) = {q є Q\ ProbG(q ,a,q) 0}; - Start(M, q) = [J Start(x, q). xeM Ниже выписаны рекуррентные соотношения для вычисления вероятностей текстовых множеств, введенных в разделе 2.4. Марковские модели порядка рассматриваются как частный случай СММ. Утверждение 2.5.4. Пусть х, t є А . Тогда robG(t-x,q) = VrobG(t,q )- PTobG(q ,x,q). (2.5.8) Q eQ Доказательство следует из свойств СММ. Утверждение 2.5.5. Для п т справедливы следующие выражения: 1) если п т, то: VrobG(B(n,r),q) = VvobG{R(n,r,H),q) = vobG(E(n,r,H),q) = 0 ; 2) если п = т, то: a) если г = 1,то: РгobG(R(m,l,h ),q) = VrobG(E(m,l,h ),q) = robG(h ,q); Рг obG (B(m,l), q) = Pr obG (R(m,l, Я), q) = Pr obG (E(m,\, H), q) = Pr obG (Я, q) ; b) еслиг 1,то: ProbG(B(m,r),q) = Pr obG(R(m,r,H),q) = robG(E(m,r,H),q) = 0 . Доказательство очевидно. Утверждение 2.5.6. Пусть п т. Тогда l)?robG(B(n,r),q)=yZ?robG(B(n-l,r),q )-7r(q\q) + TobG(R(n,r,H),q); (2.5.9) 2) VrobG(R(n,r,h ),q) = robG(E(n,r,h ),q)-VrobG(E(n,r + \,h ),q); (2.5.10) 3) если г = 1, то: ?robG(E(nXh ),q)= T(n-m,qy?robG{q\h ,q), (2.5.11) q eStart(h ,q) Tj\Qt{k,q) = S(q0)-IIk[q0,q], т.е. r(k,q) = robG(Ak,q); IJ- матрица вероятно стей переходов между состояниями; иначе, ?robG(E(n,r,h ),q) = YobG(F{n,r,h ),q) + YrobG(C(n,r,h \q); (2.5.12) 4) если г 1, то: ?robG(F(n,r,h ),q)= ProbG(B(n-m,r-l),q )-?vobG(q\h ,q); q e Start (A , q) (2.5.13) 5) если r 1 и lpred(w) Ф є, то: Ргобе(С(и,г,/г ),д) = ]Г Pro6G(Z)(« -len(Back(h )),r -1,Ipredih )) ) Pr o6G($ , BackQi ),q); ?feStart(Baci(A ),?) (2.5.14) иначе, ProbG(C(n,r,h ),q) = 0; 6) если г 1 и lpred(w) ф г, то: Pr obG (D(n, г, w), q) = Pr o6G (Л(«, r, #(w)), g) + + Pr oZ G (Z)(rc -len(Back(wJ), r,lpred(w)),q ) Pr o6G(q\ Backiyv), q) ; (2.5.15) иначе, Pr obG (D(n, r, w), q) = Pr obG (R(n, r, H{w)), q); 7) ?robG(R(n,r,H(w)),q) / robcXR(n,r,H(x)),q) xeOV(H),w=rpred(x) \ + (2.5.16) FvobG(R(n,r,h ),q) Л єЯ , w=rpred(h ) Доказательство следует из соотношений (2.4.1) - (2.4.9) и формулы (2.5.8).
Пусть задана СММ G = Q, QQ, Ж, S . В некоторых случаях, особенно для Марковских моделей, для большей части состояний вероятности текстовых множеств равны нулю. Ниже будет показано, что множество состояний, для которых вероятности текстовых множеств отличны от нуля для некоторых п и г, может быть вычислено на предварительном шаге алгоритма. Для многих моделей СММ, особенно для Марковских моделей, это значительно сокращает время работы алгоритма.
Сравнение программы SufPref с программой AhoPro
Алгоритм SufPref для точного вычисления Р-значения кластера вхождений мотива был реализован в программе на языке C++, работающей под Unix и Windows. Программа и подробная документация к ней доступны на сайте http://server2.lpm.org.ru/bio/online/sf. Созданы следующие версии программы: 1) веб-версия; 2) версия, запускаемая с командной строки; 3) реализация в виде Python-модуля. Первый вариант предназначен для использования программы через веб-сайт. Второй - для использования программы из командной строки. Реализация программы в виде Python-модуля может быть использована в качестве компоненты более сложных программ и для написания скриптов.
Входными параметрами программы являются: - алфавите; - вероятностное распределение букв в случайных последовательностях; - длина щ случайной последовательности; - мотив Н; - минимальное количество г0 вхождений мотива Н.
На выходе программа выдает найденное /"-значение. Все версии программы поддерживают работу с вероятностными моделями Бернулли, Марковскими моделями порядка К, где К т, и СММ. Важно отметить, что большинство аналогичных программ реализовано лишь для моделей Бернулли или Марковских моделей первого порядка. Мотивы могут быть заданы следующими способами: - списком слов; - матрицей МПВ и порогом; - - шаблоном и количеством допустимых замен; - сигнатурой (словом над алфавитом, буквы которого являются подмно жествами А).
Программа поддерживает работу со всеми символами кодировки Unicode. Это позволяет применять программу не только для анализа биологических последовательностей, но и для обработки произвольных языков. 4.2. Сравнение программы SufPref с программой AhoPro
Было проведено сравнение программы SufPref с программой AhoPro [56] (см. раздел 1.3.4), поддерживающей работу с моделями Бернулли и Марковскими моделями 1-го порядка. Программа AhoPro была выбрана для сравнения по двум причинам: во-первых, соответствующий ей алгоритм AhoPro имеет лучшие оценки времени работы и размера используемой памяти среди подобных алгоритмов; во-вторых данная программа эффективно применяется при решении задач биоинформатики. Отметим, что для большинства опубликованных алгоритмов для вычисления точного Р-значения не существует доступной программной реализации.
Для сравнения программ было вычислено Р-значение для следующих наборов тестовых данных: 1) алфавит - {А, С, G, Т}; 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 0,3 0,3 0,2 0,2 0,3 0,3 0,2 0,2 Отметим, что данная модель подобна вышеуказанной модели Бернулли, поэтому Р-значения для обоих моделей совпадают. Так же отметим, что выбор вероятностей не влияет на скорость работы программы и размер используемой памяти. 3) длина случайной последовательности - 1000; 4) минимальное количество вхождений - 10; 5) два вида мотивов: (а) случайные мотивы длины 8 и 12 (мотивы имеют равномерное распределение); (Ь) мотивы длины 8 и 12, заданные матрицами позиционных весов МПВ8 и МПВ12 (см. таблицы 1.1.1 и 1.1.2) и различными порогами.
Результаты экспериментов представлены в таблицах 4.2.1 - 4.2.12. Сравнение программ AhoPro и SufPref показало: - для одинаковых наборов данных вычисленные с помощью обоих программ Р-значения совпадают вплоть до 14 знака после запятой; из этого можно сделать вывод, что программа SufPref корректно вычисляет Р-значения; - для модели Бернулли SufPref работает в 4-20 раз быстрее AhoPro и использует в 1-3 раза меньше памяти; - для Марковской модели SufPref работает в 2-5 раз быстрее AhoPro, но проигрывает по размеру используемой памяти не более чем на 20%.
Из экспериментов видно, что чем меньше отношение количества слов в мотиве к количеству всех слов такой же длины, тем больше выигрыш программы SufPref по времени.
В таблицах дана следующая информация: - информация о мотиве (# - количество слов в мотиве; \OV(H)\ - количество перекрытий слов в мотиве; \Н \ - количество классов эквивалентности; \QC\ - количество состояний в автомате Ахо-Корасик для Н (структура, используемая в алгоритме AhoPro)); - Р-значение (одинаковое для обоих моделей); - время работы (в секундах) и размеры используемой памяти (в мегабайтах) при работе обоих программ; - ТВ и ТМ - отношения времени работы AhoPro ко времени работы SufPref для модели Бернулли и Марковской модели соответственно; - SB и SM - отношения размера памяти, используемой при работе AhoPro, к размеру памяти, используемой при работе SufPref, для модели Бернулли и Марковской модели соответственно.
