Оценка достоверности кластеров функционально-значимых фрагментов биологических последовательностей
На правах рукописи
Фурлетова Евгения Игоревна
Оценка достоверности кластеров функционально-значимых
фрагментов биологических последовательностей
03.01.09 Математическая биология, биоинформатика
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата физико-математических наук
Москва – 2012
Работа выполнена в Федеральном государственном бюджетном учре ждении науки Институте математических проблем биологии РАН
Научный руководитель: доктор физико-математических наук Михаил Абрамович Ройтберг
Официальные оппоненты: Всеволод Юрьевич Макеев доктор физико-математических наук, Федеральное государственное бюджетное учреждение науки Институт общей генетики им. Н.И. Вавилова РАН, заведующий лабораторией Иван Владимирович Кулаковский кандидат физико-математических наук, Федеральное государственное бюджетное учреждение науки Институт молекулярной биологии им. В.А. Энгельгардта РАН, научный сотрудник
Ведущая организация: Федеральное государственное бюджетное учреждение науки Институт теоретической и экспериментальной биофизики Российской академии наук
Защита состоится «» 2012 г. в ч. на засе дании диссертационного совета Д 002.077.04 на базе Федерального госу дарственного бюджетного учреждения науки Института проблем передачи информации РАН им. А.А. Харкевича по адресу 127994, Москва, ГСП-4, Большой Каретный переулок, д.19, стр.1.
С диссертацией можно ознакомиться в библиотеке Федерального госу дарственного бюджетного учреждения науки Института проблем пере дачи информации им. А.А. Харкевича РАН.
Автореферат разослан «»2012 г.
Ученый секретарь диссертационного совета Д 002.077. доктор биологических наук, профессор Г.И. Рожкова
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Одним из важных направлений биоинформа тики является распознавание функционально-значимых участков биоло гических последовательностей. Как правило, такие участки отличаются повышенным содержанием определенных слов. Набор слов, характер ных для класса функционально-значимых участков называется моти вом;
место положения слова из мотива в биологической последователь ности называется вхождением (или сайтом вхождения) мотива;
набор сайтов, расположенных на анализируемом участке биологической после довательности, называется кластером вхождений (или кластером сайтов) мотива. Таким образом, задачу распознавания функциональ но-значимых участков можно решать путем поиска участков с повышен ным содержанием слов из соответствующего мотива.
При таком подходе для решения задачи распознавания необходимо:
1) уметь оценивать достоверность (функциональную значимость) найденного кластера вхождений мотива и 2) определять характерную для мотива последовательность мономеров.
В биологических последовательностях кластеры вхождений опреде ленного мотива могут появляться не только в результате естественного отбора, но и случайно. В качестве меры достоверности кластера вхожде ний мотива в биологической последовательности часто используется ве роятность (P-значение) появления такого кластера в случайной последо вательности соответствующей длины при подходящей вероятностной модели. Чем меньше вероятность обнаружить в случайной последова тельности кластер, в котором количество вхождений мотива превышает заданный порог, тем больше оснований считать, что наличие такого кла стера обусловлено его биологической значимостью.
Говоря более формально, P-значением кластера из r0 вхождений мотива, расположенного на участке длины n0 относительно заданной ве роятностной модели, называется вероятность обнаружить в случайной последовательности длины n0 кластер, содержащий не менее r0 вхожде ний мотива. Таким образом, встает вопрос о разработке эффективного метода вычисления P-значения, что и является основной задачей данно го исследования.
Проблема оценки достоверности предсказанных функционально-зна чимых вхождений мотива возникает в различных областях биоинформа тики. Среди ученых, внесших значительный вклад в решение этой проблемы, О. Берг, Д. Гильберт, В. Ю. Макеев, А. А. Миронов, Г. Нюэль, М. Ренье, П. фон Хиппель и ряд других. Примером области, где необходима оценка достоверности кластеров сайтов, является иден тификация потенциальных кластеров сайтов связывания белков – факто ров регуляции транскрипции (ССФРТ), т. е. участков ДНК, которые вза имодействуют с факторами транскрипции. Здесь мотив – это набор до пустимых сайтов связывания данного фактора транскрипции. Во многих существующих программах распознавания кластеров ССФРТ отбор зна чимых результатов производится на основе вычисленного P-значения.
Сказанное выше определяет актуальность выбранной темы.
В представленной работе рассматриваются только мотивы, в которых все слова имеют одну и ту же длину, которая называется длиной мотива. Именно такими являются, например, мотивы, описывающие ССФРТ. Размером мотива называется количество слов в мотиве.
Цели и задачи исследования. Целью проведенного исследования является разработка эффективного метода точного вычисления вероят ности (P-значения) обнаружения в случайной последовательности дли ны n0 не менее r0 вхождений заданного мотива для различных вероят ностных моделей генерирования последовательностей.
Исходя из поставленной цели, были сформулированы следующие задачи.
1. Исследовать комбинаторные свойства графов перекрытий слов, в частности, – зависимость количества перекрытий слов, входящих в мотив от размера и длины мотива.
2. Разработать алгоритмы для нахождения точного P-значения кла стера из r0 вхождений мотива, расположенного на участке длины n0, отно сительно трех видов вероятностных моделей: моделей Бернулли, Мар ковских моделей данного порядка и скрытых Марковских моделей (СММ).
3. Реализовать разработанные алгоритмы в виде компьютерных программ.
4. Исследовать целесообразность применения классификационных затравок для поиска локальных сходств в аминокислотных последова тельностях, что в свою очередь позволяет строить мотивы, описываю щие функционально-значимые участки последовательностей. Разрабо тать методику построения классификационных алфавитов.
5. Применить разработанные программы для анализа реальных ами нокислотных последовательностей.
Методы исследования. В работе использованы методы теории алго ритмов, теории вероятностей, математической статистики, теоретиче ской молекулярной биологии и биоинформатики.
Достоверность результатов. Достоверность результатов обеспечи вается адекватностью используемых методов теории алгоритмов, теории вероятностей, математической статистики и биоинформатики, верифика цией математических моделей, а также сравнением аналитических ре зультатов с результатами математического моделирования.
Научная новизна. Получена оценка для среднего количества пере крытий слов, входящих в случайный мотив при равномерном распреде лении вероятностей мотивов. Доказано, что среднее количество пере крытий линейно зависит от размера мотива и не зависит от его длины.
Для вычисления P-значений был разработан алгоритм SufPref в трех модификациях, соответствующих трем видам вероятностных моделей:
моделям Бернулли, Марковским моделям произвольного порядка и скрытым Марковским моделям (СММ). В алгоритме SufPref впервые были использованы графы перекрытий слов, что обеспечило его преиму щество в быстродействии по сравнению с ранее разработанными алго ритмами.
Личный вклад автора. Автору принадлежат все описанные в дис сертации оригинальные теоремы, алгоритмы и программы.
Автору принадлежит разработка, анализ и реализация алгоритма SufPref для точного вычисления P-значения вхождений мотивов, см. [3], [8], а также проведение компьютерных экспериментов для срав нения SufPref с другими алгоритмами. Автором была доказана теорема о среднем числе перекрытий [7] (см. раздел 2.3) и ряд утверждений, при веденных в диссертации. В работе [2] автору принадлежит вычисление статистической значимости шаблонов неупорядоченных участков в бел ках. В работах, описанных в публикациях [1], [4], [5], [6], автору принад лежат алгоритмы для построения классификационных алфавитов. Автор реализовал разработанные алгоритмы в программе и построил соответ ствующие классификационные алфавиты и одиночные классификацион ные затравки над этими алфавитами.
Теоретическая и практическая значимость. Теоретическая значи мость работы состоит в исследовании комбинаторных объектов, связан ных с наборами слов, – графов перекрытий слов и затравок. Доказано, что среднее количество перекрытий слов в мотивах данного размера и данной длины при равномерном распределении вероятностей на множе стве мотивов линейно зависит от размера мотивов и не зависит от их длины. Разработан алгоритм SufPref, который вычисляет вероятность обнаружения в случайной последовательности длины n0 не менее r0 вхо ждений заданного мотива. Распределение вероятностей для последова тельностей длины n0 может задаваться с помощью модели Бернулли, Марковской модели произвольного порядка или СММ. Разработана ме тодика построения классификационных алфавитов.
Практическая значимость работы состоит в программной реализации разработанных алгоритмов. Программа и исходные коды доступны че рез интернет по адресу: 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), на Московских международных кон ференциях по вычислительной молекулярной биологии (MCCMB, Моск ва, 2007, 2009, 2011), международной конференции "The 2nd International Conference BIRD-ALBIO" (Австрия, 2008).
Публикации. По материалам диссертации опубликовано 8 печатных работ общим объемом 100 страниц. Из них три статьи в реферируемых научных изданиях (общий объем – 76 страниц), в том числе две статьи – в изданиях, входящих в список ВАК (общий объем – 48 страниц), а так же пять тезисов докладов и препринтов (общий объем – 24 страницы).
Основные положения, выносимые на защиту.
1. Разработанный алгоритм SufPref корректно вычисляет вероятность (P-значение) появления не менее r0 вхождений мотива H, слова в котором имеют одинаковую длину m, в случайной последовательности длины n0;
распределение вероятностей на множестве случайных последовательно стей может задаваться с помощью моделей Бернулли, Марковских моде лей произвольного порядка и скрытых Марковских моделей.
2. Размер используемой памяти и время работы алгоритма SufPref описываются следующими формулами (ниже A – используемый алфа вит, OV(H) – множество перекрытий слов в мотиве H):
- для моделей Бернулли:
память: O(r0m|OV(H)|+m|H|);
время: O(n0r0(|OV(H)|+|H|));
- для Марковских моделей порядка K:
память: O(r0K|A|K+1+r0m|OV(H)|+m|H|);
время: O(n0r0(K|A|K+1+|OV(H)|+|H|));
- для СММ:
память: O(|Q|2(|OV(H)|+|H|)+|Q|r0m|OV(H)|+m|H|);
время: O(|Q|2n0r0(|OV(H)|+|H|)).
Полученные оценки показали, что SufPref превосходит по характеристи кам большинство существующих алгоритмов.
3. Среднее количество перекрытий слов в мотивах данного размера и данной длины при равномерном распределении вероятностей на множе стве мотивов линейно зависит от размера мотивов и не зависит от их длины.
4. Разработанная методика построения классификационных алфави тов позволяет получать классификационные затравки, которые не усту пают лучшим из ранее известных видов затравок по чувствительности и избирательности.
Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения и списка литературы (130 наименований). Полный объем диссертации составляет 128 страниц, количество рисунков – 20, количество таблиц – 20.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Введение Во введении дана общая характеристика работы.
Глава 1. Обзор литературы Глава 1 посвящена обзору литературы, отмечена связь проанализи рованных работ с предметом исследования диссертации. В этой главе также приведены основные определения и обозначения.
Глава 2. Теоретическая основа алгоритма SufPref 2.1. Постановка задачи Пусть даны: алфавит A ={a1, …, a|A|};
мотив H = {h1, …, hs}, слова в котором имеют одинаковую длину m;
вероятностное распределение на множестве слов заданной длины в алфавите A.
Целью работы является вычисление вероятности (P-значения) встре тить мотив H по крайней мере r0 раз в случайной последовательности дли ны n0. Будем предполагать, что n0 m и r0 1. В данной работе рассматри ваются три вида вероятностных моделей: модели Бернулли, Марковские модели порядка K, где K m, и скрытые Марковские модели.
2.2. Перекрытия слов в мотиве. Граф перекрытий В данном разделе вводятся понятия, относящиеся к структуре моти ва. В частности, определяются левое и правое деревья перекрытий – основные структуры, используемые при работе алгоритма.
Определение 1. Слово w будем называть перекрытием в мотиве Н, если существуют слова h1, h2 H такие, что w является префиксом h1 и суффиксом h2. Множество всех перекрытий для Н будем обозначать че рез OV(H).
Определение 2. Пусть w OV(H) H. Определим левого и правого предшественника lpred(w) и rpred(w) слова w следующим образом:
lpred(w) = max{u OV(H) | u является префиксом w};
rpred(w) = max{u OV(H) | u является суффиксом w}.
Определение 3. Два слова из мотива H называются эквивалентными, если их левые и правые предшественники совпадают. Множество всех классов эквивалентности для мотива H будем обозначать через H*.
Пусть h* H* и h h*. Тогда, по определению, lpred(h*) = lpred(h);
rpred(h*) = rpred(h).
Определение 4. Левым деревом перекрытий LOGH называется дере во LOGH = V(H), ELOG(H), где V(H) = OV(H) H* и s, t V (H ): (s,t)E LOG (H ) s=lpred (t).
Аналогично, правым деревом перекрытий ROGH называется дерево ROGH = V(H), EROG(H), где s, t V (H ): (s,t )E ROG ( H ) s=rpred (t ).
Графом перекрытий OVGH будем называть объединение левого и правого деревьев перекрытий.
Для Марковских моделей определения деревьев перекрытий отлича ются от приведенных выше техническими деталями (см. раздел 2.2 дис сертации). В автореферате эти детали не рассматриваются.
2.3. Среднее число перекрытий Время работы алгоритма SufPref пропорционально количеству пере крытий слов в мотиве. Поэтому была исследована зависимость числа перекрытий слов в мотиве от количества слов s и длины слов m в этом мотиве. Были рассмотрены две постановки задачи.
Во-первых, было исследовано среднее количество перекрытий для случая, когда все мотивы, размера s (то есть, содержащие s слов) и дли ны m равновероятны.
Теорема 1. Пусть |A| 2 и m 2. Тогда среднее количество overlap_avg(s, m) перекрытий в мотивах размера m и длины s не превосходит cs, где Am A+ c=.
A1 Am Отметим, что если |A| = 2, то с 3,47;
если |A| = 4, то с 1,73 и если |A| = 20, то с 1,11.
Гипотеза о линейной зависимости среднего числа перекрытий слов overlap_avg(s, m) от размера мотива s и отсутствии зависимости этого чис ла от длины слов m в мотиве была с помощью компьютерных эксперимен тов проверена для случая, когда вероятности отдельных слов в мотиве описываются неравномерным распределением Бернулли, а вероятность мотива – это произведение вероятностей входящих в него слов. В экспе риментах рассматривался 4-буквенный алфавит, проверялись значения m от 8 до 50 с шагом 4 и значения s от 100 до 1000 с шагом 100, а также два распределения Бернулли – равномерное и неравномерное (с вероятностя ми {0,1;
0,2;
0,3;
0,4}). Эксперименты показали, что в обоих случаях overlap_avg(s, m) s. Результаты экспериментов для неравномерного рас пределения представлены на рисунках 1 и 2, для равномерного распреде ления результаты аналогичны.
Во-вторых, было подсчитано количество перекрытий для мотивов, ко торые задаются с помощью двух матриц позиционных весов (МПВ), опи сывающих регуляторные сайты Drosophila, и различных порогов. Длины слов в мотивах, заданных с помощью этих матриц, равны соответственно m = 8 и m = 12. Значения порогов выбиралось так, чтобы размеры мотивов были примерно от 100 до 1000 слов. Показано, что отношение количества перекрытий к количеству слов в мотивах меняется от 0,04 до 0,09 для мат рицы длины 8 и от 0,06 до 0,12 для матрицы длины 12.
Распределение вероятностей {0,1;
0,2;
0,3;
0,4} overlap_avg 600 s = 400 s = s = 8 12 16 20 24 длина слов в мотивах (m) Рис. 1. Зависимость среднего числа перекрытий overlap_avg(m,s) от параметров m и s, где m = 8, 12, 16, 20, 24 и s = 100, 500, 1000.
Распределение вероятностей {0,1;
0,2;
0,3;
0,4} overlap_avg количество слов в мотивах (s) Рис. 2. Зависимость среднего числа перекрытий overlap_avg(s,m) от количества слов s в наборах при данной длине слов m = 10, где s = 100 i, i = 1,…,10.
2.4. Текстовые множества Для краткости символьные последовательности, в которых рассмат риваются вхождения мотивов ниже называются текстами.
Пусть даны натуральные числа n и r. Определим множество:
B(n, r) = {T An| T содержит не менее r вхождений мотива H}.
Очевидно, P-значение кластера из r0 вхождений мотива H, располо женного на участке длины n0, равно вероятности Prob(B(n0, r0)). Приве дем ряд определений и обозначений, которые используются в диссерта ции и связаны с перекрытиями слов.
Пусть x,w OV(H) H, x – префикс w;
h* H*.Тогда:
- len(x) – длина x;
- H(х) – подмножество слов из H, заканчивающихся на x;
- OverlapPrefix(w) = {х OV(H)| х является префиксом w}.
Если x – префикс w, то Back(x, w) – такой суффикс слова w, что w = xBack(x, w). По определению:
Back (h).
Back (w)=Back (lpred (w),w);
Back (h *)= hh* Алгоритм SufPref для вычисления вероятностей множеств B(n, r) ис пользует ряд текстовых множеств, которые определены ниже. Пусть h H и w OV(H). Тогда n R(n,r,h)={T A T заканчивается на h& &T; содержит ровно r вхождений H };
n E(n,r,h)={T A T заканчивается на h & & T содержит не менее r вхождений H };
D(n,r,w)= R(nlen( Back( x,w)),r,H( x)) Back( x,w);
(w) xOverlapPrefix( w) D(n,r,)=.
Соответственно, для класса эквивалентности h* H* R( n,r,h*)= R(n,r,h);
E (n,r,h*)= E (n,r,h).
hh* hh* Для указанных текстовых множеств доказаны следующие соотно шения.
1. B(n,r )= B(n1, r )A R( n, r, H ) (1) 2. R(n,r,h *)=E (n,r,h *) E( n, r+1, h *) (2) 3. Если r 1, то Back(h*) (3) E(n,r,h*)=B(nm,r1)h*D(nlen( Back(h*)),r,lpred (h*)) если r = 1, то nm (4) E(n,1,h*)=A h* 4. D(n,r,w)=D(nlen( Back(w)),r,lpred(w)) Back(w)R(n,r,H (w)), w (5) 5. R(n,r,H(w))=( (6) R(n,r,H( x)))( R(n,r,h*)).
xOV ( H ), hH*, w=rpred(h*) w=rpred( x) 2.5. Вероятности текстовых множеств В разделе 2.5 приведены формулы вычисления вероятностей описан ных выше множеств для различных вероятностных моделей. Вывод фор мул непосредственно следует из свойств используемых моделей и того, что все объединения в формулах (1)–(6) – дизъюнктные. Например, для множества B(n, r) и модели Бернулли получаем следующую формулу n Prob( B(n,r))=Prob(B(n1,r ))Prob( A)+Prob( R(n,r,H ))= Prob( R(k,r,H )).
k=m Глава 3. Алгоритм SufPref для вычисления P-значения участка, содержащего кластер вхождений мотива Разделы 3.1–3.3. Общее описание алгоритма SufPref В разделах 3.1– 3.3 дано описание вариантов алгоритма SufPref, ори ентированных соответственно на вероятностные модели Бернулли, СММ и Марковские модели. Различия между вариантами носят техниче ский характер. Для краткости ниже описана только общая основа всех вариантов алгоритма SufPref. Во всех случаях основными структурами данных являются деревья пререкрытий LOGH и ROGH.
Целью алгоритма SufPref является нахождение вероятности Prob(B(n0, r0)). Алгоритм SufPref в цикле по n = m + 1,..., n0 и, для каждо го значения n, в цикле по r = 1,..., r0 вычисляет следующие вероятности:
- Prob(B(n - m, r)), если n 2m;
- Prob(R(n, r, h*)) для всех h* H*;
- Prob(R(n, r, H(w))) для всех w OV(H).
Для вычисления Prob(B(n - m, r)) используется соотношение (1). Вы числения Prob(R(n, r, h*)) выполняются путем обхода левого дерева перекрытий LOGH от корня к листьям. Сначала каждой из внутренних вершин w OV(H) вычисляются вероятности Prob(D(n |Back(w)|, r, w)) согласно (5). При этом используются значения аналогичных вероятно стей, вычисленные для ранее просмотренных вершин. Далее, для ли стьев h* H* дерева LOGH алгоритм вычисляет Prob(E(n, r, h*)) (r = 1,..., r0 + 1), используя вероятности Prob(D(n | Back(w)|, r, w)) и формулы (3) и (4);
а затем – Prob(R(n, r, h*)) согласно (2). Наконец, используя обход ROGH от ли стьев к корню алгоритм вычисляет вероятности Prob(R(n, r, H(w))) для всех w OV(H) согласно (6).
Отметим, что Prob(R(n, r, H())) = Prob(R(n, r, H)).
На заключительном этапе алгоритм SufPref находит вероятности Prob(B(n0 m+1, r0)), …, Prob(B(n0, r0)), используя формулу (1) и ранее вычисленные вероятности.
3.4. Предварительные построения В этом разделе описаны алгоритмы построения графов перекрытий и инициализации структур данных, выполняемые на предварительном эта пе работы SufPref.
3.5. Анализ сложности алгоритма SufPref В этом разделе дан теоретический анализ сложности алгоритма SufPref.
Теорема 2. Время работы алгоритма составляет:
- O(n0r0(|OV(H)|+|H|)) для вероятностой модели Бернулли;
- O(|Q|2n0r0(|OV(H)|+|H|)) – для СММ;
- O(n0r0(K|A|K+1+|OV(H)|+|H|)) – для Марковской модели порядка K.
Размер используемой алгоритмом памяти составляет - O(r0m|OV(H)|+m|H|) для вероятностной модели Бернулли;
- O(|Q|2(|OV(H)|+|H|)+|Q|r0m|OV(H)| +m|H|) – для СММ;
- O(r0K|A|K+1+r0m|OV(H)|+m|H|) – для Марковской модели порядка K.
Глава 4. Программная реализация алгоритма SufPref и ее апробация 4.1. Программная реализация алгоритма SufPref Алгоритм SufPref для точного вычисления P-значения был реализо ван в программе на языке C++, работающей под Unix и Windows. Про грамма и подробная документация к ней доступны на сайте http://server2.lpm.org.ru/bio/online/sf. Созданы следующие версии про граммы: 1) Веб-версия;
2) версия, запускаемая с командной строки;
3) реализация в виде Python-модуля.
Входными параметрами программы являются: 1) алфавит A;
2) вероят ностное распределение случайных последовательностей;
3) длина n0 слу чайной последовательности;
4) мотив H;
5) минимальное количество r вхождений мотива. На выходе программа выдает найденное P-значение.
Все версии программы поддерживают работу с вероятностными моделями Бернулли, Марковскими моделями произвольных порядков и СММ.
4.2. Сравнение программы SufPref с программой AhoPro В разделе 4.2. приведены результаты сравнения программы SufPref с программой AhoPro1, поддерживающей работу с моделями Бернулли и Марковскими моделями 1-го порядка. Программа AhoPro была выбрана для сравнения по двум причинам: во-первых, соответствующий ей алго ритм AhoPro имеет лучшие оценки времени работы и размера использу емой памяти среди подобных алгоритмов;
во-вторых данная программа эффективно применяется при решении задач биоинформатики. Для срав нения программ было вычислено P-значение для следующих наборов те стовых данных:
1) алфавит – {A, C, G, T};
2) вероятностное распределение на последовательностях задано сле дующими моделями:
- моделью Бернулли с вероятностями букв алфавита {0,3;
0,3;
0,2;
0,2};
Boeva V., et al. Exact p-value calculation for heterotypic clusters of regulatory motifs and its application in computational annotation of cisregulatory modules. // Algorithms for molecular biology. 2007. Vol. 2, N. 13. P. 25. Программа AhoPro доступна по адресу http://favorov.imb.ac.ru/ahokocc/.
- Марковской моделью первого порядка, условные вероятности которой заданы матрицей 0,3 0,3 0,2 0, ( ) 0,3 0,3 0,2 0, ;
0,3 0,3 0,2 0, 0,3 0,3 0,2 0, 3) длина случайной последовательности n0 = 1000;
4) минимальное количество вхождений r0 = 10;
5) мотивы двух видов: (а) 10 и 11 случайных мотивов длины 8 и соответственно (буквы имеют равномерное распределение);
(б) 9 и мотивов длины 8 и 12 соответственно, заданных матрицами позицион ных весов и различными порогами.
Результаты сравнения показали: 1) для модели Бернулли SufPref ра ботает в 4–20 раз быстрее AhoPro и использует в среднем в полтора раза меньше памяти;
2) для Марковской модели SufPref работает в 2–5 раз быстрее AhoPro, но проигрывает по размеру используемой памяти не бо лее чем на 20%.
4.3. Оценка статистической значимости шаблонов неупорядоченных участков в белках Программа SufPref была использована при нахождении статистиче ской значимости шаблонов неупорядоченных участков в белках, то есть участков, пространственная структура которых не поддается определе нию методами кристаллографии. О. В. Галзитской и М. Ю. Лобановым была построена библиотека из 109 шаблонов, которые описывают неу порядоченные участки. Каждый шаблон – это слово в аминокислотном алфавите длиной от 6 до 50. Мотив, соответствующий шаблону, содер жит все слова той же длины, которые отличаются от шаблона не более, чем в 20% позиций и удовлетворяют некоторым дополнительным усло виям. Для каждого такого мотива h было подсчитано количество k(h) по следовательностей белков, содержащих этот мотив, а также соответству ющее Z-значение k (h) NP (h,n) Z (h,n)=, NP (h,n)(1P (h,n)) где P(h, n) – вероятность (P-значение) хотя бы один раз обнаружить h в случайной последовательности длины n (n полагалось равным 260 – средней длине белка в базе данных);
k(h) – число последовательностей в базе данных, содержащих не менее одного вхождения h;
N = 28727 – ко личество уникальных (не гомологичных друг другу по аминокислотной последовательности) белков в базе данных.
Для шаблонов, длина которых равна 15 и меньше, для вычисления P(h, n) использовалась разработанная программа SufPref. Отметим, что количество слов в множестве H экспоненциально растет с увеличением длины шаблона h, поэтому точное вычисление P-значения для длинных шаблонов становится невозможным. Поэтому для шаблонов, длина ко торых равна 16 и больше, использовалась оценка данной вероятности сверху G(h, n) P(h, n), где G(h, n) = (n – m + 1)Prob(H).
Предполагалось, что шаблон h является статистически значимым, если Z(h, n) больше, чем определенный q-квантиль. Были рассмотрены 99-квантиль и 95-квантиль, значения которых равны 2,33 и 1,65 соответ ственно. Оказалось, что для 102 и 106 из 109 шаблонов Z-значение больше, чем 2,33 и 1,65 соответственно. Также оказалось, что 89 из шаблонов имеют Z-значение больше 5, то есть являются перепредстав ленными в белках.
Глава 5. Построение классификационных затравок для нахо ждения локальных сходств аминокислотных последовательностей Глава 5 посвящена поиску локальных сходств - одному из важных ме тодов построения мотивов. Обнаружив ряд сходных между собой фраг ментов в одном геноме или в нескольких геномах, можно по ним по строить мотив, который затем будет использоваться для поиска участков генома, содержащих избыточное количество вхождений таких мотивов.
Для решения задачи поиска локальных сходств, как правило, приме няются фильтрационные методы: сначала находят короткие гомологич ные фрагменты последовательностей (якоря или затравочные сходства).
Затем якоря расширяют до выравниваний более длинных фрагментов путем анализа окрестностей якорей. Образец для поиска затравочных сходств называется затравкой. Фильтрационные методы работают до статочно быстро, однако ценой за это может быть понижение чувстви тельности (доли найденных сходств). Поэтому встает вопрос о таком вы боре затравки, чтобы алгоритм работал быстро и при этом имел доста точно высокую чувствительность. Для нуклеотидных последовательно стей в этом направлении были получены хорошие результаты. Для ами нокислотных последовательностей единственным удовлетворительным решением этой проблемы стало использование векторных затравок. В данной главе исследована возможность использования для анализа ами нокислотных последовательностей классификационных затравок, ранее использовавшихся только при работе с нуклеотидными последователь ностями.
5.1. Классификационные затравки. Основные определения Пусть дан алфавит аминокислот A. Обозначим через П = {x, y| x, y A} множество пар аминокислот.
Определение 5. Алфавит B называется классификационным, если:
- каждой букве алфавита B соответствуют подмножество П() множества П, разным буквам соответствуют разные подмножества;
- B содержит букву # такую, что П(#) = {x, x|x A}, т.е. # означа ет совпадение символов, сопоставленных при выравнивании;
- множества, соответствующие буквам из алфавита B симметричны, т. е. для любых аминокислот x, y A и буквы B выполняется:
x, y П() y, x П().
Классификационной затравкой (одиночной) называется слово в ал фавите B. Пусть s1, s2 An. Будем говорить, что выравнивание (s1, s2) об разует затравочное сходство относительно = 1…n, если s1[i], s2[i] П(i) для всех i = 1,..., n. Будем говорить, что локальное сходство допускается затравкой, если оно содержит затравочное сходство относительно.
Множественной затравкой называется группа одиночных затравок.
Локальное сходство допускается множественной затравкой, если оно до пускается какой либо входящей в нее одиночной затравкой.
Затравка может быть охарактеризована двумя параметрами: чув ствительностью и избирательностью. Говоря неформально, чувстви тельность (относительно заданного множества целевых сходств) – веро ятность того, что случайное выравнивание из заданного множества целе вых выравниваний допускается затравкой;
избирательность – вероят ность в рамках выбранной вероятностной модели того, что независимые случайные последовательности не образуют затравочное сходство. При ведем формальные определения.
Пусть для каждой аминокислоты x A задана вероятность b(x) ее по явления в аминокислотных последовательностях. Базовой вероятностью b(x, у) пары аминокислот x, y П называется вероятность b(x, у) = b(x)b(y). Кроме того, для каждой пары аминокислот x, y П задана целевая вероятность f(x, y). Говоря неформально, f(x, y) – это веро ятность встретить сопоставление (x, y) в выравнивании сходных участков.
Целевой вероятностью выравнивания слов s1, s2 An называется произве дение n f (s 1, s 2)= f ( s1 [k ], s 2 [k ]).
k = Для классификационной буквы B и классификационной затравки = 1…n определим:
базовые вероятности:
n b( x )b ( y );
b()= b(k );
b()= k = x, y П () целевые вероятности:
n f ( x, y);
f ()= f ( k ).
f ()= k = x, y П () Избирательностью затравки называется величина 1 – b(). Чув ствительностью затравки относительно заданного множества целе вых сходств называется сумма целевых вероятностей тех сходств, кото рые допускаются затравкой.
5.2. Классификационные алфавиты В диссертации предложены три вида классификационных алфави тов: пороговый алфавит, иерархический транзитивный алфавит (ИТА) и неиерархический транзитивный алфавит (НТА).
Пороговый алфавит Для каждой пары аминокислот p П рассмотрим отношение h(p) = f(p)/b(p).
Упорядочим все пары аминокислот по возрастанию h(p). Пусть дан набор порогов T = {t1, …, ts}. Каждому порогу t сопоставим классифика ционную букву (t), которой соответствует множество пар аминокислот П((t)) = {p П| f(p)/b(p) t}.
Такие буквы будем называть пороговыми. Пороговым алфавитом будем называть совокупность букв B(T) = {(t) | t T}.
Пороговые буквы являются вложенными, то есть для любых двух порогов t1, t2 T, где t1 t2, выполняется:
П((t1)) П((t2)).
Транзитивные алфавиты Классификационную букву будем называть транзитивной, если и только если x, y, y, z П() x, z П().
Соответственно, классификационную затравку будем называть транзитивной, если она составлена из транзитивных букв. Транзитивная затравка задает отношение эквивалентности на аминокислотных по следовательностях той же длины. Мотивацией к построению транзитив ных алфавитов является уменьшение количества списков хэш-таблицы, к которым приходится обращаться при поиске локальных сходств.
В работе рассматриваются два вида транзитивных алфавитов: иерар хический и неиерархический. Иерархическим называется алфавит, в ко тором буквы вложены друг в друга. Соответственно, в неиерархическом алфавите буквы не обязательно являются вложенными.
5.3. Классификационные затравки Эффективность построенных алфавитов была продемонстрирована путем построения на их основе затравок, вычисления чувствительности и избирательности этих затравок и сравнения характеристик построен ных затравок с аналогичными характеристиками затравок других типов.
Автором диссертации с помощью программы Iedera2 были построе ны одиночные классификационные затравки длины 3–5, избирательно сти которых принадлежат промежутку [0,988;
1]. Также с помощью Iedera были вычислены чувствительности этих затравок, и среди затра вок было отобрано Парето-множество, т. е. множество, в котором не су Kucherov G., et. al. A unifying framework for seed sensitivity and its application to subset seeds. // Journal of Bioinformatics 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, (соответствует затравке BLASTp с порогом 13) и при длине целевых выравниваний 32 чувствительность затравки BLASTp составляет 0,81925, а чувствительность лучшей из пороговых затравок – 0,869064.
- Множественные транзитивные затравки сравнимы с затравкой BLASTp при относительно невысоких значениях избирательности (ниже 0,997) и немного превосходят ее при более высоких значениях избирательности. При этом преимущество транзитивных затравок растет с ростом избирательности и длины целевых выравниваний.
Заключение В диссертации представлены следующие основные результаты.
1. Разработан алгоритм SufPref для вычисления вероятности (P-зна чения) появления не менее r0 вхождений заданного мотива в случайной последовательности длины n0. Распределение вероятностей на множе Noe L., et. al. On subset seeds for protein alignment. // IEEE/ACM Trans. Comput. Biol. Bioinformatics.
2009. Vol. 6, N. 3. P. 483–494.
Brejov B., et. al. Vector seeds: An extension to spaced seeds. // Journal of Computer and System Sciences.
2005. Vol. 70, N. 3. P. 364–380;
Brown D. Optimizing multiple seed for protein homology search. // IEEE/ACM Transactions on Computational Biology and Bioinformatics. 2005. Vol. 2, N. 1. P. 29–38.
стве случайных последовательностей может задаваться с помощью мо делей Бернулли, Марковских моделей порядка K, где K m, и скрытых Марковских моделей.
2. Получены оценки сложности работы алгоритма для указанных ви дов вероятностных моделей.
3. С помощью компьютерных экспериментов было показано, что среднее число перекрытий overlap_avg(s, m) в случайных мотивах, слова в которых порождены в рамках моделей Бернулли, пропорционально ко личеству слов s в мотивах и не зависит от длины m этих слов. Для моти вов, слова в которых имеют равномерное распределение, была доказана теорема о том, что overlap_avg(s, m) сs, где c – константа, зависящая от размера алфавита;
c 4. Из этого следует, что скорость работы алго ритма в среднем не зависит от длины слов в мотиве.
4. Алгоритм SufPref реализован в виде кросс-платформенного про граммного комплекса.
5. Проведено сравнение реализации алгоритма SufPref с реализацией алгоритма AhoPro для модели Бернулли и Марковской модели первого порядка. Для модели Бернулли SufPref работает в 4–20 раз быстрее AhoPro и использует в среднем в полтора раза меньше памяти. Для Мар ковской модели SufPref работает в 2–5 раз быстрее AhoPro, но проигры вает по размеру используемой памяти не более чем на 20%.
6. Вычислены P-значения и статистические значимости вхождений мотивов неупорядоченных участков в белках.
7. Построены классификационные алфавиты для анализа аминокис лотных последовательностей: (1) пороговый алфавит, (2) иерархический транзитивный алфавит;
(3) неиерархический транзитивный алфавит. За травки над этими алфавитами не уступают по чувствительности и изби рательности лучшим из ранее известных видов затравок.
РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ 1. Roytberg М. A., Gambin A., Noe L., Lasota S., 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 O. 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., No L., Roytberg M. A., Tsitovich I. I.
Statistical approach to the design of subset seeds for protein alignment. // Pro ceedings of the International Moscow Conference on computational molecu lar biology. July 2007. P. 94.
5. Furletova E. I., Kucherov G., No L., Roytberg M. A., Tsitovich I. I.
Transitive subset seeds for protein alignment. // Proceedings of the 6th Inter national Conference on Bioinformatics of Genome Regulation and Structure (BGRS). July 2008, Novosibirsk (Russia). P. 77.
6. Roytberg М. 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–478.
7. Regnier M., Furletova E. I., Roytberg M. A. An average number of suf fix-prefixes. // Proceedings of the International Moscow Conference on com putational molecular biology. 2009. P. 313–314.
8. Regnier M., Furletova E. I., Roytberg M. A., Yakovlev V. V. An al gorithm for exact probability of pattern occurrences calculation. // Proceed ings of the International Moscow Conference on computational molecular biology. 2011. P. 320.