Алгоритмы сравнительного анализа первичных структур биополимеров

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

Бесплатный автореферат и диссертация по биологии на тему
Алгоритмы сравнительного анализа первичных структур биополимеров
ВАК РФ 03.00.28, Биоинформатика

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

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

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

Алгоритмы сравнительного анализа первичных структур биополимеров

03.00.28 Биоинформатика

АВТОРЕФЕРАТ

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

1 9 Ш 2ССЗ

Москва - 2009

003483941

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

Официальные оппоненты: доктор биологических наук,

профессор В.В. Поройков

доктор физико-математических наук О.В. Галзитская

доктор физико-математических наук A.M. Райгородский

Ведущая организация: Учреждение Российской академии

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

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

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

Автореферат разослан «_»_2009г.

Ученый секретарь диссертационного совета Д 002^077.02 „„ре„„огает„„у„рофес„р ^Р—Г*

Общая характеристика работы

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

Практически одновременно с накоплением данных о биологических последовательностях (в 60-х - 70-х годах XX века) происходило развитие прикладной теории алгоритмов - разработка базовых алгоритмов анализа символьных последовательностей и связанных с ними алгоритмов сортировки и алгоритмов на графах. Начиная с 70-х годов XX века аппарат прикладной теории алгоритмов начал применяться для анализа (прежде всего - сравнения) биологических последовательностей. При этом достаточно быстро стало понятно, что постановки задач должны максимально учитывать специфику предметной области, а собственно алгоритмы поиска (построения) искомых объектов должны дополняться исследованием статистической значимости полученного результата и/или его соответствия эталонным (экспериментально подтвержденным) результатам — для тех случаев, когда эти результаты известны.

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

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

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

Основные понятия выравнивания биологических последовательностей были сформированы в конце 70-х - начале 80-х годов XX века в работах Нндл-мана, Вунша, Смита, Уотермана, Селлерса, Санкоффа, Эриксона, Туманяна и др. В частности, были предложены основанные на методе динамического программирования алгоритмы, которые строят оптимальное выравнивание последовательностей для различных классов весовых функций. Алгоритм для линейных штрафов имеет время работы 0(ш»п); алгоритмы построения оптимального выравнивания для выпуклых весов делеций и для произвольных весов делецнй имеют временную сложность соответственно 0(m«n«(m+n)) и 0(т2»п2) (т и п -длины последовательностей)-. Однако оставался открытым вопрос - существует ли класс весовых функций, более широкий, чем линейные функции, допускающий построение оптимального выравнивания за время 0(т«п)? Кроме того, указанные алгоритмы имеют два существенных недостатка с точки зрения биологических приложений. Во-первых, оптимальное выравнивание аминокислотных последовательностей белков в ряде важных случаев по внутренним причинам не может воспроизвести выравнивание этих белков, согласованное с их пространственной структурой. Во-вторых, не разработана теория выбора значении параметров штрафов за делеции. Как правило, выбор параметров осуществлялся эмпирически. Это определяет важность поиска путей инкорпорирования содержательной биологической информации, как при собственно выравнивании, так и при подборе параметров штрафов.

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

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

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

Построение выравниваний и поиск локальных сходств связаны с оценкой достоверности полученных результатов. Это может быть сделано двумя способами. Если доступна обучающая выборка, в которой наряду со сравниваемыми объектами есть и результат сравнения, то качество алгоритма можно проверить на этой выборке. В противном (и более распространенном) случае стандартным способом проверки достоверности полученного результата является вычисление вероятности «случайного» возникновения такого события (Р-\'а1ие). В терминах вычисления Р-\'а1ие может быть переформулирована и упоминавшаяся выше задача о вычислении чувствительности затравок. По-видимому, впервые в задачах биоинформатики понятие Р-\-а1ие было введено в работах Карлина и Альтшуля, где было показано, что распределение веса наилучшего безделеционного локального сходства двух независимых случайных последовательностей асимптотически описывается распределением экстремальных значений.

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

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

Задачи исследования.

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

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

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

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

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

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

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

Основными из этих алгоритмов являются:

1) алгоритм построения оптимального выравнивания нуклеотидных последовательностей при штрафах за делеции, задаваемых кусочно-линейными функциями;

2) алгоритм построения множества Парето-оптимальных выравниваний относительно векторной весовой функции;

3) алгоритм выравнивания аминокислотных последовательностей белков с учетом их вторичной структуры

4) алгоритм предсказания внутренних циклов во вторичной структуре РНК;

5) алгоритм выравнивания вторичных структур РНК при заданной втор!гчной структуре;

6) алгоритм выравнивания геномов;

7) алгоритм вычисления чувствительности затравок для поиска локальных сходств;

8) алгоритм опенки значимости кластеров регуляторных сайтов

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

Апробация результатов. Материалы диссертации докладывались на международных и всероссийских конференциях и семинарах, в том числе: Московском семинаре по компьютерной генетике; отчетных конференциях программы «Геном человека»; II Съезде биофизиков России (Москва, 1999), симпозиуме «The Informatics of Protein Classification» (Университет Ратгерс, США, 2000), III, IV,V,VI международных конференциях по биоинформатике и регуляции структуры генома (Новосибирск, 2002, 2004, 2006, 2008), I, II и III Московских международных конференциях по вычислительной биологии (2003, 2005, 2007), международной конференции Combinatorial Pattern Matching-2004 (Стамбул, Турция), международной конференции Workshop on Algorithms in Bioinformatica (Пальма де Майорка, Испания, 2005), международной конференции «Implementation and Application of Automata» (Прага, Чехия, 2007), международном симпозиуме NETTAB (Варенна, Италия, 2008).

С использованием материалов диссертации автором сделаны доклады в NCBI USA (2000), Georgia Tech (2005), INRIA (2003, 2007), на семинарах в Институте белка РАН, Московском физико-техническом институте, факультете биоинженерии и биоинформатики МГУ и ряде других учреждений.

Публикации. Основные материалы диссертации изложены в 37 статьях в реферируемых научных изданиях (из них 33 в соавторстве).

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

Содержание работы

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

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

Напомним основные понятия. Выравнивание символьных последовательностей и н v - это тройка <и, v, S>, где S ={<ii,ji >, ...<i„,j„ >} - набор пар пози-

ций в словах и и v соответственно, таких, что 1 <i¡< ...< г„ < |г/(; 1 <j¡< ...< j„ < |v¡. Имеется в виду, что 4-я познш!я слова и сопоставлена с/;:-й позицией слова v fit = 1, ..., я), а непустые фрагменты вида u[h+l, h+r^J и v[jk+l, j^i-1] удалены (здесь £ = 0, ..., п; i0-jo = 0; Пары позиций > назы-

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

В разделе 2.1 введено понятие кусочно-линейных функций штрафов (весовых функций) за удаление фрагмента и представлен соответствующий алгоритм построения оптимального выравнивания. Предложенный класс функций является наиболее широким из известных классов весовых функций, для которых построен квадратичный алгоритм построения оптимального выравнивания (под квадратичным алгоритмом понимается алгоритм со временем работы, пропорциональным длинам сравниваемых последовательностей). Класс весовых функций, рассмотренный в разделе 2.2, наоборот, - простейший класс, при котором задача построения оптимального выравнивания двух последовательностей не сводится к хорошо изученной задаче построения максимальной общей подпоследовательности (Longest Common Subsequence, LCS). Для указанного класса функций предложен адаптивный алгоритм построения оптимального выравнивания. Хотя оценка времени алгоритма в худшем случае является квадратичной, время работы алгоритма для близких последовательностей почти линейно. В частности, если для последовательностей v¡ и \>2 длины m существует оптимальное выравнивание, содержащее t несовпадений и s удаленных символов, то время работы предлагаемого алгоритма составляет 0((í+s)m).

Рассмотрим подробнее каждый из упомянутых алгоритмов.

Говоря неформально, кусочно-линейная система весовых функций - это система, которая обладает следующими свойствами:

1) штрафы за удаления фрагментов на концах последовательностей могут быть произвольными;

2) штраф за удаление фрагмента может зависеть от граничных позиций удаляемого фрагмента;

3) зависимость штрафа от длины фрагмента может задаваться произвольной кусочно-линейной функцией;

4) штрафы за удаления фрагментов в каждой из сравниваемых последовательностей могут задаваться по-своему;

5) вес сопоставления символов u[i] и v[¡] задается произвольной функцией t](i,j, и, v).

Вес выравнивания последовательностей определяется как разность S - Д где S - сумма весов сопоставлений букв, D — сумма штрафов за удаление фрагментов.

Идея алгоритма построения оптимального выравнивания символьных последовательностей (слов) Vj и v2 при заданной кусочно-линейной системе весовых функций состоит в следующем. Последовательно (в цикле по г, а внутри него - в цикле по j) вычисляются т.н. оптимальные {i,j)-выравнивания A[i, j] и их веса P[i, j]; здесь (/, /)-выравнивание слов и и v - это такое выравниваний пре-

фиксов и[1, i], v[J,j], в котором сопоставлены позиции u[i] и vjj]. Одновременно вычисляется выравнивание M[i,j] - оптимальное выравнивание слов и и v, в котором последнее сопоставление позиций (х, у) удовлетворяет условиям x<i; у <j. Выравнивание М[\а\, \v\] будет искомым. Для вычисления веса P[i,j] и соответствующего ему выравнивания A fi, j] алгоритм поддерживает ki • к2 рекурсивно вычисляемых величин mfs, 1], где - количество интервалов линейности у функции штрафов за удаление фрагментов внутри слова v, При вычислении веса ГЦ, il величина mfs, t] хранит (в приведенной форме, см. подробнее п.2.1.5 диссертации) максимальный вес среди весов таких (х, vj-выравниваний, что длина /-х-1 попадает в л-й интервал линейности слова и, а длина j-y-l — в /-й интервал линейности слова v. При этом каждая из величии mfs, t] для очередной пары (г, j) перевычисляется за конечное время, что и обеспечивает указанное время работы алгоритма 0(k1'lc2'\vi\'\v2\). Память, нужная алгоритму, оценивается формулой (см. раздел 2.1.10 диссертации)

S<(cï+c2-sl +l\ -к\ )-m1+ci - ml,

где Ci, ...,с4 - константы. Однако большая часть этой памяти нужна лишь при восстановлении оптимального выравнивания как пути в специальном дереве (дереве опорных склеек). Поэтому для потребной оперативной памяти получаем оценку 0(к1 чп2).

В разделе 2.2 вес выравнивания G последовательностей \1 и v2 длины соответственно m¡п m2 задается формулой

W(G) = р - f'r-d'( mrp-r) - d'( m2-p-r) где p - количество совпадений в выравнивании; г - количество несовпадений; тгр-г - количество символов, удаленных в первой последовательности; тгр-г -количество символов, удаленных во второй последовательности; / d - весовые коэффициенты. Таким образом, система весовых функций описывается двумя коэффициентами/и d.

Базовыми понятиями алгоритма, описанного в разделе 2.2, являются понятие опорного множества и специального веса начального выравнивания. Начальным выравниванием слов Vj и v2 называется выравнивание префиксов VjfO, xj и v2[0, х2]. Начальное выравнивание G = < vrfO, xj, v2[0, xj, Q> слов v; и v2 называется граничным, еслиХ/ = |г')| илих2 = | v^(.

Определение 2.2.2. Множество .S'начальных выравниваний слов и называется опорным множеством, если в S найдется выравнивание, которое является префиксом некоторого оптимального выравнивания слов v; и v2.

Например, множество Sg, состоящее из единственного начального выравнивания Л g = < V;[0], VjfO], {(0,0)}>, является опорным.

Определение 2.2.1. Пусть G = < Ту [0, xj, v2 [0, х>], Q> - начальное выравнивание слов V/ и v2 длин т} и т2. Специальным весом выравнивания G называется величина

SP(G) = P(G)+ с• min(mi-Xi, т2-х2) - d'\(mrxi)-f m2-x2) |.

Начальное выравнивание G называется максимальным в множестве S, если в S нет выравнивания, которое имеет специальный вес больше, чем SP(G). Опорное множество S называется терминальным, если некоторое граничное выравнивание является максимальным в нем.

Специальный вес выравнивания обладает следующими свойствами.

1. Пусть G - выравнивание слов v1 и v2 и начальное выравнивание В является префиксом выравнивания G. Тогда

P(G)<SP(B).

2. Пусть S - опорное множество для слов \'i и v2; Be S - граничное начальное выравнивание, которое является максимальным в S. Тогда выравнивание В' слов V; и v2, имеющее тот же набор сопоставлений, что и выравнивание В - оптимальное выравнивание слов vj и v2.

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

Построение терминального опорного множества и соответствующего граничного максимального выравнивания выполняется с помощью построения т.н. канонической последовательности опорных множеств fSJ. Множество S0 состоит из одного выравнивания <\'j[0,0], v2[0,0], {(0,0)} >. Пусть опорное множество S, построено. Если S, - терминальное множество, то процесс построения канонической последовательности закончен. В противном случае выбирается некоторое начальное выравнивание S, {лидер множества S,) и это выравнивание заменяется таким набором продолжений D(Lj), что любое оптимальное выравнивание, продолжающее выравнивание L„ является продолжением одного из выравниваний множества D(L:). Это гарантирует то, что полученное множество S,,; будет опорным. Далее из построенного множества, возможно, удаляются некоторые избыточные выравнивания, т.е. такие выравнивания, удаление которых оставляет множество Si+i опорным. Таким образом,

S^ciiSi-fLJjvDfLJ.

Центральная идея алгоритма в том, что в качестве лидера выбирается максимальное выравнивание текущего опорного множества. Это позволяет избежать рассмотрения «неперспективных» начальных выравниваний и обеспечивает экономию времени при сравнении близких последовательностей.

Время работы алгоритма Time и потребная память Space описываются соотношениями Space = 0(К+ |v;| + \v2\), где К - длина канонической последовательности; Time = 0(Klog(\Vi\ + \v2\). При этом для величины К имеет место следующая оценка. Пусть для слов v; и \>2 длин соответственно т1 и т2 существует оптимальное выравнивание, содержащее t несовпадений и s удаленных символов. Тогда

К <(2t +.у + 2.5'\т,- т2\) •min(mi, ту).

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

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

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

Определение 2.3.1. Пусть к >2 - целое число. Векторная весовая функция - это функция, сопоставляющая каждому выравниванию А ¿-мерный вектор í VI), называемый (векторным) весом выравнивания А.

Примером векторного веса является вес

F(A) = (NumMatch{A), -NumDel(A)), где k = 2; NumMateh(A) и NwnDel(A) - это соответственно число совпадении и число удаленных символов в выравнивании А. Компоненты векторного веса (в данном случае NumMatch(A) и -NumDei(A)) называются элементарными весовыми функциями. Другими примерами элементарных весовых функций являются:

-NutnGap{A) - количество удаленных сегментов последовательностей («делеций», "gaps");

WeightMatch(A) - суммарный вес сопоставлений символов относительно выбранной матрицы замен;

-MisMatch(Á) - количество несовпадений (соответствует использованию единичной матрицы замен);

Определение 2.3.4. Пусть S¡ и ¿и- последовательности; V— векторная весовая функция. Выравнивание А последовательностей S¡ и S¡ называется Паре-то-оптимальным относительно весовой функции V, если V(A) является Парето-оптимальным вектором в множестве векторных весов всех возможных выравниваний последовательностей S¡ и S2.

Важность множества Парето-оптпмальных выравниваний определяется следующим наблюдением. Пусть V(A) = < V¡(A), .... Vk(A) > - векторная весовая функция; g(x¡, ...,х!г) - функция к переменных, монотонно неубывающая по каждому из аргументов, tp(A) = g(V¡(A), .... Vk(A)) - скалярная весовая функция и В -оптимальное выравнивание некоторых последовательностей относительно функции <р. Тогда В - оптимальное выравнивание этих последовательностей относительно вектор-функции V. В частности, если В - оптимальное выравнивание некоторых последовательностей относительно линейной комбинации функций V;(A), ..., Vt(A) с положительными коэффициентами, то В - оптимальное выравнивание этих последовательностей относительно вектор-функции V(A).

В разделе 2.3 представлен алгоритм построения множества всех Парето-оптимальных выравниваний данных последовательностей S¡ и S2 относительно данной весовой функции V(A). Этот алгоритм является алгоритмом динамического программирования н основан на соотношении дистрибутивности между операцией сложения векторов и операцией взятия Парето-подмножества объединения двух Парето-оптимальных множеств. Более точно, пусть с - число, множества 7 T¡, Т? с Rk, причем Т T¡, Т? - Парето-оптимальные множества; через РагеГо(Т) обозначается Парето-подмножество множества Т;. Рассмотрим следующие операции:

с ® Т = Pareío({< xi+c, ..., хк +с>\ < х,, ..., хк > е Tf), Т, © Т2 = Рагею(Т, vTJ.

Тогда

с ®(Г, © = (с ®Т,) © (с ®Г,).

Доказательство непосредственно следует из определения операций © и ® и определения Парето-множества.

Для последовательностей длины от, и тг время работы такого алгоритма оценивается как 0(с(тт-^'ПЦ'тт), где коэффициент с(ти т2) зависит от выбранной весовой функции и определяется временем выполнения операций ®и © для этой функции. В некоторых случаях приведенная оценка может быть улучшена. В частности, оценку времени для случая упомянутой выше весовой функции VD(A) = (NumMalch{A), -NwnDe!(A)) дается следующей леммой:

Утверждение 2.3.4. Пусть S\ и S2 - последовательности; пх длины равны соответственно п и т. Пусть р - длина наибольшей общей подпоследовательности Si и S2', d = m + n- 2р н /• = min (р, if).

Алгоритм Pareto_Aljgn_Del_Dmax строит множество Парето-оптимальных весов н Парето-оптимальных выравниваний для последовательностей и S2 относительно весовой функции VD(A) = (Match(A), -NumDel{A)) за время 0(min(«, 2d>mv?«log(>)).

Такая же оценка нерпа и для весов ой функции VG(A) = (Match(A), -NumGap(A)).

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

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

Предлагаемый подход основан на следующем наблюдении. Рассмотрим две последовательности к и v и фиксируем некоторую весовую матрицу замен. Для произвольного целого g, через S(g) обозначим наибольший суммарный вес сопоставлений среди выравниваний, содержащих не более g удаленных фрагментов. Через D(g) обозначим «производную» S(g)\

D(g) = S(g+l)-S(g).

Значения S(g) могут быть найдены путем построения Парето-оптимальных выравниваний относительно векторной весовой функции

WG(A) = (WeightMatch(A), -NumGap(A))

Допустим, что удалением некоторого количества фрагментов из последовательностей и и v можно получить достаточно похожие последовательности равной длины; эти фрагменты назовем «правильными». Удаление «правильного» фрагмента восстанавливает соответствие между (обычно, протяженными) гомологичными фрагментами исходных последовательностей и, тем самым, ведет к существенному увеличению веса S(g) (значение D(gj велико). Когда все

«правильные» фрагменты удалены, новые удаления уже не мотивированы биологически и, следовательно, не могут привести к существенному увеличению S(g) (значение D(g) мало/ Наибольшее значение параметра g, при котором значение D(g) велико, назовем критическим значением, а соответствующее ему выравнивание - критическим выравниванием. Мы полагаем, что критическое выравнивание наиболее (среди других Парето-оптимаяьных выравниваний) соответствует биологически корректному выравниванию данных последовательностей. Это приводит к следующему методу выравнивания последовательностей.

1. Построить множество Парето-оптимальных выравниваний относительно векторной весовой функции !VG(A) = (WeightMatch(A), -NumGap(A)).

2. Определить критическое значение количества удаленных фрагментов g п взять критическое выравнивание в качестве результата.

Успешность применения этого метода зависит от алгоритма, который определяет порог, отделяющий «малые» и «большие» значения D(g). Компьютерные эксперименты показали, что для нуклеотидных последовательностей со степенью сходства не менее 30% и для аминокислотных последовательностей со степенью сходства не менее 20% выбор такого порога возможен. Получена верхняя оценка для величины D„ «малых» значений D(gj:

Д.г 5 log(L)/log(l/(l -/>)) -1, (2.4.1)

где L - средняя длина последовательностей, р - доля совпадающих букв. Эта оценка хорошо согласуется с данными компьютерных экспериментов при р > 0.4 (см. таблицу 2.4.S). Величина ошибки увеличивается с убываниемр и возрастанием L.

Таблица 2.4.8.

Оценки значений величины Д.,

L Р

0.3 0.4 0.5 0.6 0.7 0.8 0.9

200 FORM 13.8 9.4 6.6 4.8 3.4 2.3 1.3

ЕХР 10.0 8.0 6.0 4.0 3.0 2.0 1.0

300 FORM 15.0 10.2 7.2 5.2 3.7 2.5 1.5

ЕХР 10.0 8.0 6.0 5.0 3.0 2.0 1.0

700 FORM 17.3 11.8 8.5 6.1 4.4 3.1 1.8

ЕХР 11.0 9.0 7.0 5.0 3.0 3.0 1.0

1000 FORM 18.3 12.5 9.0 6.6 4.7 3.3 2.0

ЕХР 11.0 9.0 7.0 6.0 4.0 3.0 2.0

Верхняя граница для величины Д,. вычисленная по формуле (2.4.1), строки FORM, п максимальные значения величины Дг. полученные в ходе компьютерных экспериментов (см. п.2.4.2 диссертации, строки ЕХР. Данные приведены для различных длин L и уровней сходства р.

В свою очередь, ожидаемое значение М величины D(g) при удалении «правильного» фрагмента (что соответствует «докритической» области значений D(g)} зависит не только от L и р, но н от других характеристик сравниваемых последовательностей, Такими характеристиками являются: длина <1 удаляемого фрагмента, длина D каждого из гомологичных фрагментов, которые оказались сопоставленными правильно в результате удаления; доля совпадений р0 при сопостав-

лении негомологичных (случайных) фрагментов последовательностей. Для среднего значения М имеем формулу:

М - 1){р-ро) -pd.

Если указанное значение будет менее Д.,, то удаление таких «правильных» фрагментов не может быть диагностировано на фоне статистического шума. Это показывает статистические пределы применимости алгоритмических методов восстановления биологически корректных выравниваний. Другие ограничения возможностей алгоритмических методов рассмотрены в главе 3.

Таким образом, в главе 2 рассмотрена общая задача построения оптимального выравнивания символьных последовательностей, в частности, - проблема выбора штрафов за удаление фрагментов. В главе 3 рассматривается более специальная задача - выравнивание биологических последовательностей. Центральная тема этой главы - учет пространственной структуры сравниваемых молекул при сравнении их первичных структур (последовательностей). Имея это ввиду, мы ограничиваемся рассмотрением наиболее распространенного в современной биоинформатике класса весовых функций удаления фрагментов - аффинными функциями. Это позволяет существенно упростить изложение, хотя приведенные в разделах 3.2 и 3.3 алгоритмы могут быть обобщены на случай рассмотренных в главе 1 кусочно-линейных функций. В разделе 3.4. представлен оригинальный алгоритм предсказания вторичной структуры РНК.

Раздел 3.1 посвящен изучению связи между биологически корректными выравниваниями аминокислотных последовательностей и выравниваниями, полученными с помощью алгоритма Смита-Уотермана (571) - наиболее распространенного в настоящее время алгоритма построения оптимального выравнивания последовательностей. В качестве «биологически корректных» (эталонных) выравниваний использованы выравнивания, основанные на наложении пространственных структур белков. Адекватность такого подхода обоснована существенно большей консервативностью пространственной структуры белков по сравнению с их первичной структурой. В качестве источника эталонных выравниваний использовалась база данных BaliBase [http://www-igbmc.u-strasbg.fr/BioInfo/BAliBASE/]. Большая часть сравниваемых пар последовательностей (всего 583 пары) имела процент совпадений %ID от 15% до 40%.

Исследована зависимость степени сходства между алгоритмическими и структурными выравниваниями от степени сходства между сравниваемыми последовательностями и выявлены причины расхождений между этими выравниваниями. В качестве количественной оценки качества алгоритмически полученных выравниваний использовались две взаимодополняющих меры: (1) Точность выравнивания (обозначение: Ali_Acc) равна отношению количества одинаковых сопоставлений (/) в обоих выравниваниях к общему количеству сопоставлений в эталонном выравнивании (G): Ali_Acc = I/G*100 %. (2) Достоверность вырав-шбашля_(обозначение: Ali Confl, равна отношению количества одинаковых сопоставлений в обоих выравниваниях (I) к общему количеству сопоставлений в алгоритмически построенном выравнивании (A): Ali_Conf = I/A* 100 %. Неформально говоря, точность АН Асс показывает, какую долю эталонного выразни-

вания удалось восстановить, а достоверность АИ_Соп/— насколько можно доверять построенному выравниванию.

Как видно из рис. 3.1.2, алгоритм может строить выравнивания, хорошо совпадающие с эталонными, только при уровне сходства сравниваемых белков более 30-40%. Этот диапазон уровня гомологии (Ю > 30%) примерно совпадает с известным порогом %Ю, выше, которого можно достоверно восстановить структурное выравнивание, зная только последовательности [%56, %58-60]

Рис. 3.1.2. Зависимость точности восстановления эталонных выравниваний методом 5\У от уровня сходства (%Ш) сравниваемых белков. Каждая точка соответствует паре эталонных белков. Х-координата точки равна %Ю пары, а Г-равный координата - значению точности. Зависимость для достоверности практически такая же

При уровне гомологии меньше 10% метод Б\У не может восстановить правильное выравнивание даже частично. Для диапазона уровня гомологии от 10% до 30% выравнивания Смита-Уотермана показывают очень широкий разброс точности и достоверности. Для разных пар последовательностей с одинаковым уровнем сходства построенные 8\У-выравнивания могут иметь очень различные значения точности и достоверности. Это означает, что в этом диапазоне %Ю качество алгоритмических выравниваний определяется не только уровнем сходства сравниваемых белков, но и «внутренними свойствами» их эталонных выравниваний. Эти «внутренние» свойства удобно формулировать в терминах т.н. «островов».

Определение 3.1.1. Островом в выравнивании А = <и, V, {?> называется непродолжаемая последовательность сопоставлений, не разделенных удалениями фрагментов. Весом острова называется сумма весов входящих в остров сопоставлений. Выравнивание можно представить как цепочку островов, разделенных делещими.

Эталонные выравнивания и 5\У-выравнивания имеют существенно различную структуру островов с точки зрения веса островов (см. рис. 3.1.5). Неожиданно много эталонных островов имеют очень низкий или даже отрицательный вес, в то время как алгоритмические выравнивания совсем не содержат островов малого веса. Стоит отметить, что суммарная длина таких «слабых» островов в эталонных выравниваннях достаточно велика (см. рис. 3.1.5 б)

Эталонные острова веса меньше 5 составляют 32% от всех островов и покрывают 20% всей длины эталонных выравниваний. Только 5% островов такого малого веса были восстановлены алгоритмом. Для выравниваний из серой зоны (10 < %Ю < 30) картина еше более критическая - восстановлено всего 2.5% островов веса меньше 5. Эти «слабые» острова обычно не имеют шансов быть восстановленными любым алгоритмом, использующим данную матрицу замен.

(а)

9000 8000 л 7000

| 6000 к 5000 х 4000 3 3000

I. 2000 1000 0

(б)

о о о о о о

ООО о ю о

Рисунок 3.1.5. (а) Гистограмма распределения количества островов в эталонных выравниваниях (белый) и выравниваниях БЧ' (черный) по весу острова, (б) Суммарная длина островов, имеющих вес в пределах диапазонов. Эталонные острова - белый, - черный

%Ю<10%

10% <%Ю<30%

450-,

та з: г 400 -1 350

с: С£ 300 1

К 250 '

(О 200 |

о. та 150 '

г 100 1

и 50|»

0-НЧ

7000

6000

5000

4000-

3000

2000 -

1000 I

0- 4

Мл ^ЯЮ

3500 3000 2600 2000 1500

%Ю>30%

вес острова

Рисунок 3.1.6. Более детальное представление данных рис. 3.1.5а. Гистограммы суммарных длин островов с весом в пределах указанных по оси X диапазонов отдельно для каждой их 3-х областей %/О.Данные по эталонным островам показаны белым, 5%' - черным

С увеличением степени сходства сравниваемых белков (см. рис. 3.1.6) различие в весе эталонных и построенных островов уменьшается. Однако даже для высокого уровня сходства белков (Ю > 30%) встречаются эталонные острова отрицательного веса.

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

пространственных структур, если идентичность последовательностей ниже 30%. В разделе 3.2 представлен подход, который позволяет существенно повысить как точность, так и достоверность алгоритмических выравниваний первичных структур белков. Идея подхода состоит в явном учете сведений о вторичной структуре сравниваемых белков, при этом примерно с равным успехом может использоваться как экспериментально полученная вторичная структура, так и теоретически предсказанная. Таким образом, метод применим и для выравнивания белков с неизвестной пространственной структурой. Наша работа не была первой работой в этом направлении, однако мы впервые исследовали влияние учета сведений о вторичной структуре белков на точность и достоверность получаемых выравниваний и получили лучшее по сравнению с предшественниками качество выравнивашш.

Представленный в разделе 3.2 алгоритм STRUSWER является модификацией алгоритма Смита-Уотермана. Отличие состоит в том, что при сопоставлении i-ro аминокислотного остатка одной последовательности и j-ro остатка другой к весу сопоставления добавляется бонус. Этот равен произведению коэффициента SBON, определяющего вклад вторичной структуры в вес сопоставления, на величину сходства элементов вторичной структуры.

Как указывалось выше, предложенный метод может использоваться как с экспериментально полученными, так и с теоретически предсказанными вторичными структурами. Для предсказания вторичной структуры использовалась программа PSIPRED [Bryson К, McGuffm LJ, Marsden RL, Ward JJ, Sodhi JS. & Jones DT. Protein structure prédiction servers at University College London. Nucl. Acids Res. 2005. Vol. 33 (Web Server issue): W36-38] в двух режимах: совместного предсказания структуры для группы гомологичных белков ("full version") и предсказание структуры только по аминокислотной последовательности ("single version"). При этом точность предсказания для использованного набора белков составила соответственно 82% и 65%, что согласуется с результатами, приведенными на сервере EVA (http://cubic.bioc.columbia.edu/eva/).

Для каждой из этих версий использовалось два способа представления предсказанной вторичной структуры. В первом случае («тип_структуры»), каж-долгу остатку аминокислотной последовательности приписывается определенный символ вторичной структуры (Н - спираль; Е — бета-структура; L - петля). Во втором («вероятность_структуры»), каждому остатку приписываются вероятности принадлежности остатка к каждому из трех типов вторичной структуры, которые также рассчитываются программой PSIPRED.

При тестировании качество выравниваний, полученных методом STRUSWER с различными способами разметки вторичной структуры (см. выше) сравнивалось с качеством выравниваний, полученных методом SW, а также методом WFMFL, представленный в работе [Wallqvist A, Fukunishi Y, Murphy L.R., Fadel A, Levy R.M. Iterative sequence/secondary structure search for protein homologs: comparison with amino acid sequence alignments and application to fold récognition in genome databases. Bioinformatics. 2000. V. 16. P. 988-1002]

В качестве эталонных выравнивашш, как и в разделе 3.1, использовались выравниванм из базы BaliBase (см. выше); корпус эталонных парных выравниваний был разделен на обучающий и тестовый наборы. Источником данных об

экспериментально определенных вторичных структурах белков служила база данных DSSP [Kabsch W, Sander С. Dictionary of protein secondary structure: pattern recognition of hydrogen-bonded and geometrical features. Biopolymers. 1983. V. 22, P. 2577-2637].

Таблица 3.2.2.

Точность (Acc) и достоверность (Conf) различных методов выравнивания

Метод SBON GOP GEP Асс Conf ID < 30%

Асс 0.353 Conf 0.429

SW не исп. 7 1 0.525 0.585

а) предсказание вторичной структуры по последовательности

STRUSWER SIN S 2 10 1 0.578 0.622 0.428 0.482

STRUSWER SIN % 7 8 2 0.602 0.618 0.461 0.477

WFMFL SIN не исп. 13 1 0.399 0.488 0.263 0.346

б) предсказание вторичном структуры с привлечением данных о гомологичных белках

STRUSWER PSI S 8 9 1 0.659 0.683 0.546 0.573

STRUSWER PSI % 17 6 2 0.683 0.695 0.579 0.589

WFMFL PSI не исп. 16 1 0.631 0.672 0.503 0.560

в) экспериментально известная структура

STRUSWER EXP 8 ' 10 1 0.677 0.700 0.577 0.601

WFMFL EXP не исп. 15 1 0.638 0.698 0.527 0.602

Параметры (SBON, GOP, GEP) были подобраны на обучающей Еыборке для получения максимальной точности (Асс) каждым из методов. Представлены данные как для всей тестовой выборки (288 пар белков) так и для «серой зоны» (белки с гомологнчностью ниже 30%, 182 пары). Для методов STRUSWER и WFMFL указаны способы разметки вторичной структуры: Ехр - экспериментально полученная структура; PSI - предсказание структуры по гомологии ("full version" PSIPRED); SIN. Суффиксы _S и _% указывают способ представления предсказаний: «тяп_структуры» (_S) или «вероятность_структуры» (_%)■ Метод WFMFL не приспособлен для использования предсказаний, представленных вероятностями структур

Результаты тестирования представлены в таблице 3.2.2. Параметры каждого из методов, были предварительно подобраны на обучающей выборке выравниваний. Отметим, что параметр SBON имеет смысл только для метода STRUSWER, а параметры аффинных штрафов за удаление (GOP, gap opening penalty, и GEP, gap elongation penalty) используются всеми методами. Значения параметров в таблице 3.2.2 были получены путем максимизации средней точности выравниваний по обучающей выборке. Результаты тестирования с параметрами, полученными при оптимизации достоверности, носят сходный характер.

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

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

Таким образом, в качестве основного метода предсказания вторичной структуры следует рассматривать метод, делающий предсказание вторичной структуры по отдельной аминокислотной последовательности, в данной работе -программой PSIPREDsingle. Обладая меньшей, чем полный вариант PSIPREDfull, точностью предсказаний, он, тем не менее, имеет ряд преимуществ. Первое преимущество состоит в том, что программа PSIPREDsingle не основана на поиске гомологов, и поэтому STRUSWER в соответствующих режимах (STRUSWER_SIN_S и STRUSWER_SIN_%) можно использовать в случаях, когда произвести поиск гомологов по тем или иным причинам невозможно. Второе преимущество вытекает из первого, и заключается в существенно меньших затратах времени, необходимого для предсказания вторичной структуры. Подобный факт может оказаться решающим в больших вычислительных проектах. Выравнивания, сделанные алгоритмом STRUSWER_SIN, с использованием вторичной структуры, предсказанной по аминокислотной последовательности, превосходят по качеству аналогичные выравнивания, полученные алгоритмом SW и алгоритмом WFMFL_SIN, как по точности, так и по достоверности. Все указанные соотношения остаются верными, если мы ограничимся только слабогомологичными парами белков. При этом относительный выигрыш от использования вторичной структуры существенно возрастает.

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

Определение 3.3.3. РНК-дерево - это такое корневое упорядоченное дерево, что

(1) листья помечены буквами РНК-алфавита {А, С, G, U};

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

РНК-лесом F = <Т], ..., Т„ > называется упорядоченное множество РНК-деревьев.

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

Представленный в разделе 3.3 алгоритм строит оптимальное выравнивание РНК-лесов при аффинных штрафах за удаление фрагментов РНК. Уточним постановку задачи.

Пусть <$1, /';>, Р2> - РНК-структуры без псевдоузлов, здесь - последовательность, Р, ~ множество спариваний (/'=7, 2); О - выравнивание & и Будем говорить что в выравнивании б спаривание (х1у у^) £ Р1 сопоставлено спариванию (х2, у2) в Р2, если х: сопоставлено х2 и у, сопоставлено».

Весовая система для выравнивания структур РНК - это пятерка <Л/, g, <3, Ь, с>, где М - весовая матрица замен; - это коэффициенты аффинной весовой функции удалений фрагментов; Ъ — бонус за сопоставление спариваний, с -штраф за каждое спаривание, не участвующее в сопоставлениях.

Пусть задана весовая система <М, g, с!, Ъ, с>; <ЯЬ ¡'¡> и <Я2, Р2> структуры и А - их выравнивание с набором сопоставленных позиций (склеек) {<рь дк> ) к = 1,..., N1. Пусть т - общее число удаленных фрагментов в А; I - суммарная длина этих фрагментов, к - количество спариваний в апс! Р2\ которые не сопоставлены в А другим спариваниям: / = (|Р} | + \Р2 |-к)/2 - количество сопоставлений спариваний. Тогда структурным весом выравнивания А называется величина

8соге(А) = -ЪЫ) -g■m -с!1 + Ы- с к. (3.3.1)

Это определение соответствует определению веса глобального выравнивания последовательностей с аффинными весовыми функциями удаления фрагментов, к которому добавлены бонусы и штрафы за правильное (неправильное) сопоставление спариваний.

Представленный алгоритм сводит задачу построения оптимального выравнивания последовательностей РНК с известными вторичными структурами при заданной весовой системе <М, g, (I, Ь, с> к обобщению задачи выравнивания лесов на случай РНК-лесов. Специфика РНК-лесов заключается (1) в различной интерпретации листьев и внутренних вершин (нуклеотиды и спаривания), в частности, в понятии главных сыновей и (2) в использовании аффинной функции штрафов за удаление символов.

Определение 3.3.4. Выравниванием РНК-лесов и Р2 называется такое множество А £ 1'еПех(Р¡)х \гег1ех(Рг), что для каждой пары (у^и^), (у2,м'2) е А выполнено:

1) 1'1 = 12 тогда и только тогда, когда и'! = н'г (иными словами, А - взаимно однозначное соответствие .между подмножествами ¥ег!ех(Р¡) и УеНех(Р2)).

2) вершина V] предшествует вершине \'2 в смысле левого обхода леса тогда и только тогда, когда вершина предшествуете вершине и'2 в смысле левого обхода леса Р2.

3) если (у, м>) е А, то либо обе вершины V и к' - листья, либо обе они -внутренние вершины;

4) Пусть (у, М') е \'епех(Р1)х УеПех(Р2): 1 и — главные сыновья вершины v; м>1 и м¡2 - главные сыновья вершины №. В этих условиях (v, \у) еА тогда и только тогда, когда (уьм:]), (у^у^ е А.

Первые два условия традицноины для выравнивания упорядоченных лесов общего вида. Условия (3) и (4) отражают специфику РНК-лесов. Определение веса выравнивания РНК-лесов очевидным образом следует из (3.3.1).

Алгоритм построения оптимального выравнивания РНК-лесов - это алгоритм динамического программирования, использующий парадигму «левый-правый», предложенную в работе Клейна [Klein P.N.. Computing the edit-distance between unrooted ordered trees // Proceedings of the 6th European Symposium on Al-gorithms(ESA). 1998. P. 91-102]. В указанной работе вес удаления фрагмента пропорционален его длине, что соответствует посимвольным удалениям. Для того, чтобы использовать аффинные штрафы за удаления фрагментов, для каждого промежуточного РНК-леса вычисляются значения дополнительных (по сравнению с алгоритмом Клейна) характеристик.

Определение 3.3.13. Пусть L, R с {1, 2} и А - выравнивание лесов F, и F2. Пусть ki(A) (соответственно, kg(A) ) - количество таких индексов ie L (соответственно, je К) , что лес F, пуст или при выравнивания А в лесе F, не удален самый левой (соответственно, правый) лист. Делеционным весом WD(A, L, R) выравнивания А при ограничениях L, R называется величина

WD(A, L, R) = W(A) - (kL+ kR)-g,

где W(A) - вес А относительно выбранной весовой системы <М, g, d, Ъ, с>; g -штраф за удаление фрагмента, аналогичный gap opening penalty алгоритма Сми-та-Уотермана.

Определение 3.3.14. Пусть <Fi ,F2> - пара лесов, L, R с {1, 2}. Через Best(FI ,F:, L, R) обозначается наибольшее возможное значение делеционного веса WD(A, L, R) для выравниваний А лесов Fj и F2.

Очевидно,

WD(A, 0, 0J = W(A) н Best(Fj ,F2, 0, 0j - это вес оптимального выравнивания лесов F; и F,.

Сложность работы алгоритма естественно выражается через количество промежуточных пар лесов К, обработанных в ходе работы алгоритма. Потребная память есть О(К), а время - 0(Klog(K)). Аналогично алгоритму Клейна, можно показать, что К = 0(т2п lg (п)), где т St - длины сравниваемых последовательностей. Таким образом, получаем для памяти оценку 0(т2п log (п)), а для времени работы - оценку 0(т2п log2 (п)).

В разделе 3.4 представлен алгоритм вычисления энергии внутренних петель в структурах РНК в рамках модели Цукера-Тернера-Мэтьюза (Nearest Neighbour Model, NNM) - общепринятой в настоящее время модели строения РНК. Такой алгоритм является необходимой частью общего алгоритма поиска оптимальной (т.е. имеющей минимальную свободную энергию) структуры для данной последовательности РНК в рамках NNM. Как было показано в предыдущих разделах главы 3, использование сведений о вторичной структуре, в том числе - теоретических предсказаний структуры, важно для сравнения биологических последовательностей.

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

соответственно валентные и водородные связи. Петли делятся на типы в зависимости от количества входящих в них водородных связей и длин спаренпь/х участков (см. определения в п. 3.4.2.2 диссертации).

Фиксируем последовательность РНК длины L и множество U, состоящее из M спариваний позиций этой последовательности; спаривания из U будут называться допустимыми. Множество 110IVв = {(х, В) eU} называется В-й строкой.

Определение 3.4.2. Пусть Р çz U- структура, (А, В), (р, q) е Р. Спаривания (А, В), (р, q) образуют внутреннюю петлю (internal loop), если А <р < q < В и ни один из нуклеотидов х, где А <х <р или q <х < В, не участвует в спариваниях структуры Р. Спаривание (А, В) называется замыкающим спариванием петли; спаривание (р, q) - внутренним спариванием петли; фрагменты [А+1, р-1] и [q+/, В-13 - крыльями петли.

Определение 3.4.4. Будем говорить, что спаривание (А, В) - замыкающее спаривание (closing pairing) в структуре Р, если Р не содержит пар (х, у), где х < А или у> В.

Алгоритм, который предсказывает вторичную структуру РНК в рамках модели NNM, просматривает все допустимые спаривания строка за строкой в порядке возрастания номеров строк В е [1, £]. При этом, для каждого спаривания (А, В) g ROW в вычисляется оптимальная структура каждого типа t е {0, 1, 2, 3}, тип структуры определяется типом петли, к которой принадлежит замыкающее спаривание структуры. Далее просмотром этих «частных» оптимальных структур вычисляется структура, имеющая наименьшую энергию AG(A, В) среди всех структур, не имеющих спаренных нуклеотидов вне сегмента [А, В].

Энергия структуры, в которой замыкающая склейка (А, В) принадлежит внутренней петле, образованной склейками (А, В) и (х, у), задается формулой

AGïnW„ml_Laop(A, В; X, }>) =

=fLen(dA+dB) +fDlJ){dA~dB)+AG(x,y) =

=Ы(В-А) - (y-x+2)) +М(В+А) - (У+Х)) + AG(x, y). (3.4.1) Здесь fim(t) — фиксированная выпуклая функция, она хорошо аппроксимируется логарифмической функцией. Функция определяется соотношениями:

fixffO) = basejevel, если |/| > width,

fajr (0 = (basejevel / width)*\t\, если |/| < width. (3.4.2)

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

AG]nternal_Loop(A, В) =

= min{AGIn,mK,LLoop(A, В; х, у) \(х, у) £ U & А<х<у<В} = = mm{fle„({B-A) - iy-x+2)) +fDiff((B+A) - 0**)) + AG(x, y)|

\(x, y) e U & A<x<y<B}. (3.4.3 )

Говоря неформально, AG/,tKr„aijJJ0!, описывает увеличение (т.е. ухудшение - структура с большей энергией менее стабильна) энергии структуры РНК в связи с образованием внутренней петли. Это увеличение зависит от длин dA и dB крыльев петли и представляется в виде суммы двух слагаемых. Одно из слагае-

мых (fie„(i')) зависит от суммарной длины крыльев, другое ifoiffO)) - от асимметрии петли, т.е. величины | dA - dB |. Если асимметрия мала, то fo^ (t) растет линейно; для значений асимметрии, превышающих порог width, значение fDiß- (t) постоянно. Такой своеобразный вид функции Ж7;„,гг„0/_£00;/Л, В; х, у) и представляет основную трудность при анализе внутренних петель.

В первых алгоритмах построения оптимальной вторичной структуры минимум в (3.4.3) находился прямым перебором, что приводило к общему времени анализа внутренних петель 0(L4); позднее был предложен алгоритм [Lyngs0 et al. Fast evaluation of internal loops in RNA secondary structure prediction //Bioinformatics. 1999. V. 15. P. 440-445] со сложностью 0(LS). Представленный в разделе 3.4 алгоритм AFOLD использует технику динамического программирования для разреженных матриц (sparse dynamic programming, см. [Eppstein et al. Sparse Dynamic Programming II: Convex and Concave Cost Functions J. ACM. 1992. V. 39, P. 546-567]) и имеет временную сложность 0(M*log'(i)), где L - длина последовательности, М - количество теоретически допустимых спариваний. Т.к. М < L2, эта оценка существенно улучшает оценку 0(L3) лучшего из ранее предложенных алгоритмов. Отметим, что использованная алгоритмическая техника близка к технике выравнивания последовательностей и может быть использована при построении выравниваний геномов.

В заключение разбора раздела 3.4 сделаем два замечания. Во-первых, в отличие от предлагавшихся ранее подходов, в оценку времени нашего алгоритма явно входит число М допустимых склеек. Благодаря этому алгоритм хорошо сочетается с различными (как экспериментальными, так и теоретическими) способами предварительного отбора (фильтрации) допустимых склеек. Во-вторых, для некоторых классов относительно небольших молекул РНК известно, что их структуры не содержат ветвящихся петель. Для таких молекул наш подход позволяет построить оптимальную структуру за время 0(M*log'{L)).

Рассмотренные в главах 2 и 3 алгоритмы оптимального выравнивания имеют квадратичную временную сложность — их время работы (в худшем случае) пропорционально произведению длин последовательностей. Такое время слишком велико для многих бноинформатических приложений, в частности, -для сравнения синтенных фрагментов геномов (длина — 107 нуклеотидов. Глава 4 посвящена выравниванию последовательностей, не связанному с оптимизацией весовой функции, и возникающим в этой связи алгоритмическим задачам. В разделе 4.1 представлен иерархический алгоритм геномного выравнивания OWEN, основанный на построении систем коллинеарных локальных сходств. Разделы 4.2 и 4.3 посвящены поиску локальных сходств с помощью т.н. затравок - наиболее распространенному и быстродействующему из известных методов построения локальных сходств. В разделе 4.2 дано определение затравки в наиболее общем виде и рассмотрен простейший класс «неклассических» затравок -разреженные затравки, предложенные в [Ма, В., Tromp, J, and Li, M. Pattern-Hunter: Faster and More Sensitive Homology Search // Bioinformatics. 2002. V. 18. P. 440-445, 2002]. Для этого класса указан вид оптимальной оптимальной затравки среди затравок с одной несущественной позицией. Раздел 4.3 посвящен введенному нами (совместно с Г.Кучеровым и Л. Ноэ) классу затравок - классификационным затравкам, и некоторым алгоритмическим проблемам, связанным

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

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

Сходство синтенных участков геномов «средне близких» организмов (человек - мышь, C.Elegance - C.Briggsae н т.п.) существенно неоднородно и распадается на локальные сходства. Как правило, эти сходства являются статистически достоверными, т.е. имеют достаточно низкое значение /'-значения (Р-уа!ие) для заданных длин последовательностей и распределения вероятностей. Большинство статистически достоверных сходств коллинеарны, т.е. проекции на оба сравниваемых генома расположены в одинаковом порядке. Это объясняется тем, что основные эволюционные события (замена нуклеотида, удаление/вставка фрагмента) не нарушают коллинеарности. Возможные нарушения коллинеарности (конфликты между сходствами, см. рис. 4.1.1), связаны с более редкими эволюционными событиями.

Есть три основных источника нарушения коллинеарности локальных сходств или микроколлинеарности (термин «микроколлинеарность» используется, чтобы отличить коллинеарность локальных сходств, как кодирующих, так и некодирующих, от макроколлинеарности - коллинеарности генов в синтенных участков геномов). Этими источниками являются (1) локальная конвергентная эволюция, (2) консервативный повтор, присущий обоим геномам, но по-разному расположенный в них; (3) локальные перестановки в геноме.

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

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

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

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

2. Описанный выше принцип применяется как при сравнении последовательностей в целом, так и при сравнении их ортологичных фрагментов («фрак-тальность»). Благодаря этому, после того, как выделена цепь локальных сходств, значимых на уровне последовательностей в целом, алгоритм может пополнить эту цепь менее сильными сходствами, расположенными в коллинеарных участках между уже выделенными сходствами. Эти «дополнительные» сходства не являлись значимыми при сравнении исходных последовательностей длиной, скажем, 107, но становятся значимыми при сравнении коллинеарных фрагментов длиной, скажем 101. Иными словами, более «сильные» локальные сходства поддерживают коллинеарные с ними более слабые сходства.

а) Ь) с)

о.

Последовательность U

Рис. 4.1.1. Матрица сходств (dot-matrix), на которой показаны различные вида конфликтов между локальными сходствами. а) Неустранимый конфликт: сходные фрагменты на разных последовательностях расположены в разном порядке. Ь) Неустранимый конфликт: проекции сходств на последовательность U существенно перекрываются. с) Есть незначительное перекрытие проекций сходств на последовательность V В этом случае конфликт может быть разрешен путем обрезания концов сходств

/ t

Mus musculiis

Рис. 4.1.2. Сравнение синтенных участков последовательностей мыши (AF139987) и человека (AF045555). Наиболее сильное сходство H - это ортологичное сходство, представляющее экзон 10 локусе Rfc2 (нуклеотиды 104514-104583 по последовательности мыши). Каждое из коллинеарных между собой сходств А¡, Л2 и Аз не является ортологичным. Однако их общий вес выше, чем вес сходства H

Цепь локальных сходств, построенную исходя из сформулированных выше принципов, будем называть остовной (backbone) цепью. Мы полагаем (см. аргументацию выше), что она близка к «эволюционно правильной» цепи, содержащей все ортологичные локальные сходства. В отличие от выравнивания белков (см. разделы 3.1, 3.2), при выравнивании геномов мы вынуждены полагаться

только на индивидуальную статистическую значимость локальных сходств. Описанный подход реализован в алгоритме OWEN, который опнсан в разделе

Формальное определение остовной цепи основано на понятии р-достоверности (ре [0,1] - порог значимости).

Определение 4.1.1. Р-значением сходства Н между последовательностями 11 и V называется вероятность того, что независимые случайные последовательности длин | И\, | У\ имеют локальное сходства веса не менее Нсоге(Н).

Определение 4.1.3. Пусть Р - цепь локальных сходств в последовательностях и, V и Н - элемент К Сходство Н р-достоверно в Р, если его Р-значение относительно фрагментов ¡7, V, ограниченных ближайшими к Н элементами цепи Р, имеющими больший, чем Н, вес, не превышает порога р (см. рис. 4.1.3).

Цепь локальных сходств Р в последовательностях 1!, V называется р-достоверной, если каждое, входящее в Р сходство /»-достоверно в Р.

Остовная цепь для II, V с уровнем значимости р - это максимальная р-достоверная цепь для и, V (уточнение понятия максимальности см. определение 4.1.6 в диссертации).

Построение/>-остовной цепи для последовательностей II, ['выполняется

иерархически. Сначала строятся все сходства, /"-достоверные на уровне последовательностей II, V в целом и для этого множества сходств строится максимальная цепь Затем эта процедура рекурсивно применяется к промежуткам между соседними сходствами уже построенной подцепи искомой остовной цепи. Такой иерархический подход позволяет избежать затратного по времени анализа относительно слабых локальных сходств по последовательности в целом, что и определяет эффективность алгоритма.

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

4.1.

Рис. 4.1.3. Иллюстрация понятия р-достоверности сходства относительно цепи. Пусть цепь Р = !'А,, Я, А, А.) и $соге(Н) < 5соге(А2) < 8соге(А}) < 8соге(А]). Тогда (1) ^ = {А,, Ау А.), РА2 = (АГ А^ РА3 = {А,}, и РА} пусто; (2) А2 р-достоверно в Р, если в выделенном прямоугольнике

U[End(Aj,U)+l, Beg(A3.U)-l] X V[End(A 1,V)+1, Beg(a3,V)-l], ограниченном сходствами A[ and As: (3) Aj p-достоверно в F, если оно р-достоверно относительно последовательностей U and V в целом.

Пхлекетгелыюсп. LT

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

Время работы описанного алгоритма оценивается величиной 0(2) + OfNlogN) + TimesaLoc где Z - количество сходств в остовной цепи, N - общее количество локальных сходств, рассмотренных в ходе работы алгоритма, TimegetLoc - общее время построения локальных сходств. При обычно используемых малых значения параметрар (р <0.01) значение N = к Т, где ¿мало.

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

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

Практически все используемые в настоящее время алгоритмы поиска локальных сходств основаны на фильтрации пространства поиска с помощью предварительного выделения т.н. затравочных сходств. Приведенные ниже определения обобщают определения из работ [Ma, В., Tromp, J, and Li, M. Pattern-Hunter: Faster and More Sensitive Homology Search. // Bioinformatics. 2002. V. 18. P. 440-445], [Brown D. Optimizing multiple seeds for protein homology search. //IEEE Transactions on Computational Biology and Bioinformatics. 2005. Vol. 2 , P. 29-38.] и др.

Определение 4.2.1. Затравкой [seed] будем называть произвольное множество локальных выравниваний (=сходств), эти выравнивания называются затравочными выравниваниями. Затравка Z допускает выравнивание G = <v, w, Е>, если существует затравочное выравнивание z0e Z такое, что z0 - подвырав-нивание выравнивания G.

Простейший пример затравки - это множество точных совпадений заданной длины т. В этом случае затравка состоит из выравниваний вида <и, и, So>, где и — слово длины m, S0— тривиальное выравнивание слова с самим собой.

Пусть Jt - затравка. Назовем слова w ', iv ' ' я-эквивалентными, если

W({v, M")ejtO(v, if")e4

Очевидно, множество С(ж, i;) всех слов образующих с данным словом v затравочное сходство в смысле затравки ~ , есть объединение классов к-

эквивалентности. На этом наблюденни основан стандартный способ поиска затравочных сходств для данных последовательностей v, и'.. Он состоит из двух этапов.

1. Индексирование. Для каждого класса ^-эквивалентными 2 строится список всех вхождений элементов этого класса в последовательность V (т.н. индексный список).

2. Поиск. Просматриваем последовательность и' слева направо. Чтобы найти все фрагменты последовательности v, образующие затравочное сходство с очередным фрагментом Щх, х+с1], достаточно просмотреть индексные списки для всех классов я -эквивалентности 2 таких, что 2с:С(к, \\'[х, х+ф.

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

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

Этап 1. Поиск затравок (см. выше).

Этап 2. Поиск в окрестности затравок локальных сходств, представляющих интерес с точки зрения поставленной биологической задачи.

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

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

Вычисление избирательности затравки определяется вероятностью того, что фрагменты независимых случайных последовательностей, которые начинаются в заданных позициях, образуют затравочное сходство. Например, для рассмотренной выше затравки «точное совпадение длины >г» и бернуллиевских случайных последовательностей изб1грательность равна р". В то же время вычисление чувствительности затравки представляет определенную сложность. Вычисление чувствительности затравки означает вычисление вероятности (в рамках заданной вероятностной модели) того, что случайное выравнивание из заданного множества целевых выравнивании содержит подвыравнивание, принадлежащее затравке. Алгоритмы вычисления чувствительности затравок рассмотрены в разделе 5.2 главы 5.

Упомянутые выше точные совпадения были первым использовавшимся классом затравок, однако в последние годы был предложен ряд новых классов. Два таких класса рассмотрены в главе 4.

Первый из этих классов (см. раздел 4.2) - это разреженные затравки (spaced seeds) - первый класс затравок, отличный от «классических» идущих подряд п совпадений; этот класс был предложен в начале 2000-х годов (см. [Burkhardt S. and Karkkainen J. Better Filtering with Gapped q-Grams // Fundamenta Informaticae. 2003. Vol. 56, N. 1-2. P. 51-70], [Ma, В., Tromp, J, and Li, M. Pattern-Hunter: Faster and More Sensitive Homology Search // Bioinformatics. 2002. V. 18. P. 440-445]. Неформально говоря, разреженная затравка, как и классическая затравка, требует наличия нескольких совпадений, но расположенных не подряд, а по описанной в затравке схеме. Более формально разреженные затравки описываются следующими определениями.

Определение 4.2.3. Разреженным термом Е называется список положительных целых чисел {p¡, ....pj таких, что p¡< ...<p¿ и p¡=l. Размером терма Е называется величина span(E) =pj; весом терма Е называется число weight(E) = d. Отметим, что вес разреженной затравки напрямую связан с ее избирательностью.

Терм Е ={p¡, ...,Pdj часто для наглядности представляют словом íE длины pä в двухбуквенном алфавите {#, -} таким, что 1E[i] = '#' & {pi, ...,p¡¡•}■ Символ называют джокером.

Определение 4.2.5. Пусть G = безделеционное выравнивание слов v и w; Е ={p¡, ■ ■■,Pdi - разреженный терм. Выравнивание G соответствует терму Е, если

1)\v\=\w\-pd;

2) Vj е{1, ...d}(v[k+pj+iJ = w[k+pj+IJ).

Разреженная затравка, задаваемая термом Е - это множество всех выравниваний, соответствующих терму Е.

Т.к. разреженные затравки трактуют выравнивания только с точки зрения совпадений-несовпадений, то при работе с разреженными затравками выравнивания обычно перекодируются в двухбуквенный алфавит с буквами 1 (совпадение) и 0 (несовпадение).

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

Определение 4.2.9. Выравнивание g€{l, Of называется (т, к)-выравниванием, если в нем есть ровно к нулей и т-к единиц. Затравка Е решает (т, к)-проблему, если она допускает все (т, ^-выравнивания.

Определение 4.2.11. Пусть Q - затравка и к - допустимое количество несовпадений. к-критическая длина для Q - это минимальная длина т, при которой Q решает (т, Ä^-проблему. Затравка Q называется k-оптималъной в некотором классе затравок, если она имеет минимальную к-критическую длину в этом классе.

Утверждение 4.2.2. Рассмотрим класс затравок веса не менее d с одним джокером, к - натуральное число. Тогда к-аттшачъной затравкой будет затравка ^-'-tf, где

r= [d/2], если к=1, г = [ d/3], если к> 1, где [х] - ближайшее целое к числу х и [п+1/2] = п.

Этот результат был обобщен на случай затравок с несколькими джокерами в [Farach-Colton, М., Landau, G.M., Sahinalp, S.C., Tsur, D: Optimal spaced seeds for faster approximate string matching // J. Comput. Syst. Sei. 2007. V. 73. P. 1035-1044].

Пример 4.2.1. Затравка #4-#2 - оптимальная в смысле приведенного выше определения среди затравок веса 6 с одним джокером. Это, в частности, означает, что она решает (т, 2) - проблему для всех т > 16 и это - наилучшая оценка в рассматриваемом классе. Аналогично, эта затравка решает (т, 3) - проблему для всех т > 20 и это - наилучшая оценка в рассматриваемом классе и т.д.

Естественным обобщением разреженных затравок являются классификационные затравки, представленные в разделе 4.3.

Пусть ж - затравка. Слова равной длины w' и w" называются л-эквнвалентными, если для любого слова v той же длины безделеционные выравнивания (v, w') и (v, w") либо одновременно являются затравочными сходствами для к (см. определение 4.2.1), либо одновременно не являются. Через С (ж, v) обозначим множество всех слов w, образующих с данным словом v затравочное сходство в смысле затравки я. Очевидно, множество С.(ж, v) есть объединение классов jt-эквивалентности.

Для произвольной разреженной затравки Е каждый класс С(Е, v) состоит ровно из одного класса ¿'-эквивалентности (говорят, что разреженные затравки допускают однозначное индексирование), что упрощает поиск соответствующих затравочных сходств. Возможность однозначного индексирования для разреженных затравок связана с тем, что эти затравки различают только два вида отношений между символами - совпадение и несовпадение. В [Brejova В., Brown, D., Vinar Т. Vector seeds: an extension to spaced seeds allows substantial improvements in sensitivity and specificity // Proceedings of the 3rd International Workshop in Algorithms in Bioinformatics / Eds. Benson, G., Page, R. Lecture Notes in Computer Science. Vol. 812. Springer. 2003] была предложена более гибкая и общая модель затравок - векторные затравки, в которых критерий соответствия между затравкой и выравниванием базируется на интегральной характеристике - сумме вкладов разных позиций. Платой за эту общность является то, что для векторной затравки R класс C(R, v) может состоять из десятков классов /¿-эквивалентности, что усложняет как поиск, так и индекагрование.

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

Фиксируем алфавит последовательностей П. Пусть М = {(а, а)\а е 11} — множество всех пар-совпадений.

Определение. 4.2.12. Классификационный алфавит В - это алфавит, каждая буква Ье В которого соответствует непустому подмножеству П„ сПх П, причем

1) ЬЪе В (М с:Пъ ) (любая классификационная буква допускает совпадение);

2) В В есть буква #, для которой /7* = М (# требует только совпадений, она ниже называется единичной буквой).

Очевидно, алфавит разреженных затравок {#, -} - классификационный, причем джокеру соответствует множество ПхП.

Определение. 4.3.1. Классификационная затравка - это слово в некотором классификационном алфавите В. Затравка я = Ь]...Ьт е5™ допускает фрагмент выравнивания а/...а„, &{ПхП)'", если У/'е {1, ..., т} ai е Ь,. Размером $рап(ж) затравки ж называется ее длина т, #-весом - количество $Иагр(ж) букв '#' среди Ьь

■ ■■, ь,„

Определение. 4.3.2. Назовем буквы х, у еПх П эквивалентными относительно алфавита Л (В-эквивалентными), если (хе Л4 уе Пь).

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

Пример 4.3.1. Рассмотрим выравнивания нукпеотидных последовательностей, т.е. выравнивания над алфавитом последовательностей {А, С, С, Т]. Тран-зицией называется одна из четырех пар {(А, Т), (Т, А), (С, (?), (О, С) }. Трансверсией называется любое несовпадение, отличное от транзиции. Известно, что среди замен в нуклеотидных выравниваниях частота транзиций существенно выше, чем частота трансверсий. В качестве алфавита затравок возьмем алфавит В = { #, -/; элементы В представляют соответственно только совпадение (#), совпадение или транзицию (@), любое сопоставление (-). Очевидно, порожденный алфавитом В алфавит выравниваний А включает три множества: (1) совпадения (символ: 1)\ (2) транзиции (символ.' /г); (3) трансверсии, т.е. несовпадения, отличные от транзиций (символ:0).

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

Пусть В - алфавит классификационных затравок. Будем считать, что каждой букве с е В сопоставлена вероятность Р(с). Это можно сделать, например, так. Рассмотрим алфавит последовательностей П, связанный с алфавитом В. Пусть на П задано распределение вероятностей Д- П -> [0,1], где

I хедР(х) = 1.

Это распределение индуцирует распределение вероятностей на множестве пар ПхП по правилу Р(х, у) = Р(х) ¡¡(у). Так как буквы классификационного алфавита соответствуют подмножествам в ПхП, то, тем самым, зная распределение Д каждому классификационному символу с можно приписать вероятность р(с). Отметим, что, вообще говоря,

ЪсеВР(с)

Определение 4.3.3. Пусть В - алфавит классификационных затравок и каждой букве с е В сопоставлена вероятность [¡(с) е [0, 1]. Пусть # - единичный символ алфавита В, т.е. символ, соответствующий множеству совпадений М = {(х, х)\х е П}. Весом произвольного символа с е В называется величина

№ег81?/(с) = -^ф(с))По%ф(Щ). Весом weight(■к) классификационной затравки к называется сумма весов входящих в нее букв.

Пример 4.3.2 (продолжение примера 4.3.1). Пусть на алфавите {А, С, О, Т} задано равномерное распределение вероятностей. Тогда weight(^i) = 1; weight((a}) - 'А; weight(-) - 0. Вес н'е/^Л/ук) затравки п = равен 2.5.

В п.4.3.4 диссертации показано (см. таблицы 4.3.3, 4.3.4), что при фиксированном весе, а следовательно, при фиксированной нзб1грательности, классификационные затравки из рассмотренных выше примеров 4.3.1, 4.3.2 имеют более высокую чувствительность, чем разреженные затравки. В обеих таблицах множество целевых выравниваний - это множество всех безделеционных выравниваний длины 64. В таблице 4.3.1 распределение вероятностей на этом множестве - это бернуллиевское распределение, в таблице 4.3.4 - марковское распределение порядка 3. Параметры этих распределений получены из анализа парных геномных выравниваний для 40 бактериальных геномов. Ниже приведена таблица 4.3.3, данные таблицы 4.3.4 аналогичны.

Таблица 4.3.3.

Оптимальные затравки в классах разреженных затравок и классификационных затра-

вок

Вес Разреженные затравки Чувствительность Классификационные затравки, два @ Чувствительность

9 ##-##-#-#-### 0.4183 0.4443

10 ##-##-##-#-### 0.2876 0.3077

11 ###-#-#-###-### 0.1906 0.2056

12 ###-#-##-#-##-### 0.1375 0.1481

Оптимальные затравки в классах разреженных затравок и классификационных чатравок в алфавите {#, -} (см. пример 4.2.2) с не более, чем двумя символами @ для различных весов (от 9 до 12). Целевые выравнивания имеют длину 64. Распределение вероятностей - бернуллиевское, все символы равновероятны.

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

Утверждение 4.3.3. Пусть ж = bl...bm е//" - классификационная затравка длины m, w - количество символов # в ж и Sx = < A, Q, qo, Qf, It'> - классификационный автомат затравки ж. Тогда количество состояний автомата SR не превосходит (w+l)'2'"~w.

Эта оценка не улучшаема, что показывает следующее

Утверждение 4.3.4. Пусть А = {#, -} и л = #-г# (между символами # расположено г джокеров). Тогда классификационный автомат ,VT неприводим, т.е.

(i) любое состояние S- достижимо из начального состояния q0;

(ii) никакие два состояния не эквивалентны.

В силу определения 4.2.1, классификационный автомат затравки я эквивалентен автомату Ахо-Кораснк для множества слов Л'4, соответствующих затравке п. Для двухбуквенного алфавита выравниваний, соответствующего разреженным затравкам, оценка утверждения 4.3.3 совпадает с оценкой количества состояний автомата Ахо-Корасик из работы [Aho, A.V.; Corasick, M.J. Efficient String Matching. // Communications of the ACM. 1975. V. 18. P. 333-340.], которая дается формулой (\v+l)'a'"~M', где a - размер алфавита выравниваний. Таким образом, утверждение 4.3.3 дает верхнюю оценку для числа состояний приведенного автомата, соответствующего автомату Ахо-Корасик для множества слов

Мж.

Таблица 4.3.1 представляет данные о среднем количестве состояний классификационного автомата соответственно для разреженных и классификационных затравок из примера 4.3.1. Для каждого веса и' было подсчитано среднее количество состояний у автомата Ахо-Корасика (столбцы «Ахо-Корасик») и классификационного автомата, описанного в разделе 4.2.4 (столбцы «Кпассиф. автомат»), В каждом случае показывалось как среднее количество состояний (столбцы «Разм.»), так н отношение этого среднего к среднему количеству состояний для соответствующего минимального автомата (столбцы «Опт»). Среднее количество состояний дли минимального автомата (это число одинаково для обеих конструкций, т.к. соответствующие автоматы эквивалентны) приведено в столбце «Разм. мин. авт.». Отметим, что классификационный автомат компактнее автомата Ахо-Корасик не только для 3-буквенного алфавита В (см. выше), но и для двухбуквенного алфавита R. При данном весе для регулярных затравок среднее подсчитано по всем затравкам веса w и длины не более w+8; для затравок примера 4.3.1 - по всем затравкам веса w, длины не более w+5 и содержащим не более двух символов @.

В главах 2-4 представлены алгоритмы построения парного выравнивания биологических последовательностей, ориентированные на широкий спектр постановок задач. Большинство из этих алгоритмов основано на методе динамического программирования. Как известно (см. [Finkelstein, A.V. and Roytberg, М.А. Computation of biopolymers: a general approach to different problems. // BioSystems. 1993. Vol. 30, P.l-19.]), динамическое программирование, наряду с построением оптимальных объектов, позволяет решать, в определенном смысле, двойственную задачу. Это задача вычисления т.н. обобщенных статистических сумм, которые характеризуют множество допустимых объектов в целом. Более формально, речь идет о следующей задаче.

Таблица 4.3.1.

Классификационные автоматы и автоматы Ахо-Корасик.

Вес Разреженные затравки {#, -} Классификационные затравки {#, -1

Ахо-Корасик Классиф. автомат Размер мин. авт. Ахо-Корасик Классиф. автомат Размер МИН. авт

Разм. Отн. Разм. Охн. Разм. Отн. Раш. Отн.

9 345.9 3.1 146.3 1.3 113.2 1900.7 16.0 167.6 1.4 119.0

10 380.9 3.2 155.1 1.3 120.6 2104.0 16.5 177.9 1.4 127.5

11 415.4 3.3 163.8 1.3 127.6 2306.3 17.0 188.1 1.4 136.0

12 449.5 3.3 172.4 1.3 134.9 2507.9 17.4 198.1 1.4 144.0

13 483.3 3.4 180.9 1.3 141.8 2709.0 17.8 208.1 1.4 152.3

Дан конечный ациклический ориентированный граф С,для простоты будем считать, что у графа О один источник А и один сток 2. Полным путем в графе О называется путь из источника в сток. Ребра графа помечены элементами множества Л, на котором определены две ассоциативные операции - «сложение» (обозначается Ф ) и «умножение» (обозначается ® ), обладающие следующими свойствами:

1) нейтральные элементы 0 и 1:

Ысе М (О Ф х) =--х; Ьке М (1 ®х) = х;

2) коммутативность сложения:

Ыс, уе М (у ®х = х ®у);

3) дистрибутивность:

¥х, у, М ( (х ®у) ®г = (х®2) © {у®г)) ;

Весом пути называется «произведение» (относительно операции ®) весов входящих в него ребер, взятых в порядке следования от источника к стоку.

Обобщенной статистической суммой (ОСС) графа С называется «сумма» (относительно операции ©) весов всех его полных путей.

Если операции Фи®- это обычные операции сложения и умножения, а веса ребер - это вероятности переходов, то ОСС графа О это суммарная вероятность полных путей из источника С этого графа.

Значение обобщенной статистической суммы может быть вычислено за время 0(Ес1^е((})), где Е<1^с(0) - количество ребер в графе С.

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

вычислению обобщенной статистической суммы. Этот подход применен к вычислению чувствительностей затравок (см. главу 4 и раздел 5.2) и вероятностей обнаружения сигналов в последовательностях (раздел 5.3).

Фиксируем алфавит А и длину последовательностей т. Пусть задано множество последовательностей 5' с А'" и распределение вероятностей р на множестве А'". В разделе 5.1 вычисление вероятности Рр($) сведено к вычислению обобщенной статистической суммы для некоторого графа. Этот граф строится на основе конечного детерминированного автомата (КДА), распознающего язык 5 и конечно-автоматного генератора вероятностей, задающего распределение р.

Множество А"', вероятность которого требуется найти - конечное, и, следовательно, допускается конечным детерминированным автоматом К с не более, чем т^ состояниями. Специальные случаи построения такого автомата К, распознающего множество 5 рассматриваются ниже. «Конечно-автоматность» распределения р является достаточным условием применимости предлагаемого подхода, она эквивалентна существованию НММ, описывающей распределение Р-

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

Определение 5.1.1. Пусть А - алфавит. Конечно-автоматный генератор вероятностей над алфавитом А - это четверка 0= <0, д°, А, р >, где <2 - множество состояний; д"- начальное состояние; А - алфавит, р: () х А х () -> [0, 1] - функция генерации вероятностей такая, что

е (^хч.е<3аеАр(цу а, д') = 1.

Переходом в Б называется тройка е =<д,а,д'> такая, что [>(д, а, д') >0. Буква а называется меткой перехода и обозначается 1аЬе1(е). Состояния д и д' называются соответственно начальным и конечным состоянием перехода и обозначаются соответственно 51аг1(е), еп^(е). Меткой пути Р = (е1, ..., е;[) в О называется слово ЫЪеЦе]) ...1аЪе1(е„).

Генератор С называется детерминированным, если для любой пары д £ 2, а (=А есть не более одного перехода вида <д,а,д'>.

Путь Р называется инициальным, если его начальное состояние - это состояние генератора в. Вероятностью р(Р) пути Р = (&}, ..., е„) называется произведение р(Р) = П,-Ллр(е,). Вероятностью слова и' относительно генератора О называется величина Рв(м), равная сумме вероятностей всех инициальных путей с меткой ж Вероятностью конечного набора слов (языка) Ь с: А * называется сумма Р0(Ц вероятностей всех слов IV с7 £. Очевидно, для любого п выполнено

Ра(А") = 1.

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

ного символа зависит от к предшествующих символов. Такое распределение может быть описано детерминированным генератором с не более, чем \А\к состояниями; эти состояния соответствуют словам длины менее к в алфавите А

Пусть даны К'ДА К = <Qa q°K, Q'\-, А, <рК>, - распознающий язык S и конечно-автоматный генератор G= <Qa, q"G, А р0 >, задающий распределение вероятностей р на А"'. Вычисление вероятности У'аО-) сводится к вычислению ОСС для графа т.н. вероятностного распознающего автомата (BP-автомата), который строится как декартово произведение К л G. Говоря неформально, BP-автомат -это недетерминированный конечно-автоматный генератор вероятностей, в котором выделено подмножество допускающих состояний.

Определение 5.1.6. Пусть К = <QK, qK°, (f к • А, (р > - детерминированный конечный автомат без выхода; G-- <Qi„ q°G, А, р> • конечно-автоматный генератор вероятностей над алфавитом А. BP-автомат W = KxG - это пятерка \¥= =<(?»-, cfw, (fw, Л,, р„> где СЛг = QkxQg ; q°w = q\xq°G ;

{{<k, g>e = QKxQc I ke (fK};

Pwi<k, g>, a, <k\ g>) =p(g, a, g'), если <p(k,. a) = k';

ßu-(<k, g>, a, <k', g'>) = 0 - в противном случае.

Все Описанные ниже алгоритмы и оценки их сложности основываются на следующих утверждениях, которые следуют из определения 5.1.6.

1. Значение вероятности PG(L) равно значению обобщенной статистической суммы для графа BP-автомата W.

2. Автомат IVимеет \Qa\'\Qi:\ состояний и для каждой пары, состоящей из состояния q автомата W и символа а е А есть не более \Qo\ исходящих из q ребер.

Для некоторых важных частных случаев оценки п.2 могут быть существенно улучшены, что приводит к различным оценкам сложности алгоритмов при различных допущениях. Некоторые из этих оценок приведены ниже.

Утверждение 5.1.4. Рассмотрим алфавит А и конечное множество L с А"'. Пусть К = <Qz, q'K, (f к, A, ip¿> - КДА, распознающий множество L и G= <Ос„ q°c, A, pG> - конечно-автоматный генератор, задающий распределение вероятностей р на Ат. Тогда вероятность I\,(L) множества L относительно распределения pG может быть найдена за время 0(\Qo\2 '\Qt¿\'\A\) с использованием памяти 0(\Qg\'\Qk\)- Если генератор G детерминированный, то для времени работы алгоритма верна оценка 6Y1£?gI*Ií?a-|*M(/

Следствие 1. Пусть распределение вероятностей на множестве А"' - бер-нуллиевское. Тогда для времени и памяти вычисления вероятности PG(L) верны оценки TimeBcr„< 0(\Q¿'\A\) и SpaceBen< 0(\QK\)

Следствие 2. Пусть распределение вероятностей на множестве А'" - это Марковское распределение порядка г. Тогда для времени и памяти вычисления вероятности PG(L) верны оценки Time\íarllm,< 0(\Qk\'\A'*'\) и Брасемшко^ 0(]Qx\-\ArD

Утверждение 5.1.6. Рассмотрим алфавит Л и конечное множество L С А"'. Пусть В = <QB, q°B, (Ув, А, (рв> - автомат, распознающий множество L' такое, что L'd Ат = L и G= <Qg, я"с,' A, pG> - конечно-автоматный генератор, задающий распределение вероятностей р на А"'. Тогда вероятность Pp(L) множества L

относительно распределения р может быть найдена за время с использованием памяти В случае детермини-

рованного генератора (/ время работы равно 0((\()в\,\()с\'\А\'т).

Следствие 1. Пусть распределение вероятностей на множестве Ат - Бер-нуллиевское. Тогда для времени и памяти вычисления вероятности Ра(Ц верны оценки ТтсВегп< 0($)в\'\А\-т) и ЗрасеВгт< 0^в$

Следствие 2. Пусть распределение вероятностей на множестве А'" - это Марковское распределение порядка г. Тогда для времени и памяти вычисления вероятности Ра(Ц верны оценки ТппеК1агкт< О^ОвМА^'^т) и Ярасемагколб:

0№в\Мг\)

Утверждение 5.1.8. Рассмотрим алфавит А и конечное множество Ь сАт. Пусть А/ - конечное множество слов, множество 1.это множество

Ь' = /и' е А | у\} содержит подслово из М} и при этом выполнено Ь = А"' пЬ'.

Пусть далее, В = <()в, (У'в, А, <рв> - автомат Ахо-Корасик для множества М, распознающий множество Ь' и р ~ распределение вероятностей на А'", задаваемое марковской моделью порядка г. Тогда вероятность Рр(Ь) множества относительно распределения р может быть найдена за время О((\0в\+\А'])'\А\чп) с использованием памяти 0((\()В\+\АГ[)).

В разделе 5.2 результаты предыдущего раздела применены для вычисления чувствительности данной затравки, т.е. вероятности (в рамках заданной вероятностной модели) того, что случайное выравнивание из заданного множества целевых выравниваний допускается затравкой. Все выравнивания в этом разделе считаются безделеционнымн и представляются словами в некотором алфавите А. В качестве множества целевых выравниваний рассматривается множество А'" всех выравниваний длины т. На А'" задано распределение вероятности р, отражающее вероятности замен в интересующем исследователя классе выравниваний. Как и в разделе 5.1, будем считать, что распределение вероятности р задано конечно-автоматным генератором вероятностей 0= <()а Ц о. А, р >. Фиксируем затравку ж.

Определение 5.2.1 Через 8(ж) а А обозначается множество всех выравниваний, допускаемых затравкой ж. Автоматом затравки ж называется детерминированный конечный автомат без выхода, распознающий множество Я(тг). Через Б(ж, т) сАт обозначается множество всех выравниваний, допускаемых затравкой ж

Будем считать, что вместе с затравкой ж задан и ее автомат В(ж) = <<2в, дв°, Огв , А, (рГ1>. Такой автомат для всех известных классов затравок может быть построен на основе автомата Ахо-Корасик, специальная конструкция автомата для классификационных затравок представлена в п.4.3.4. Из результатов раздела 5.1 вытекают следующие утверждения.

Утверждение 5.2.1.Пусть А - алфавит выравниваний, 6= <()с, А, ра> -конечно-автоматный генератор, задающий распределение вероятностей р на А"'; л - затравка и В (л) = <(2в, <]в, (/в, А, <рв> - автомат затравки ж. Тогда чувствительность <5"еш(п, т) затравки тг относительно множества выравниваний А'" может быть найдена методом динамического программирования за время

О(\0а\2Л0в\'т'\А\) с использованием памяти О(]0оМ£?я1Л Если автомат В(л) -детерминированный, то время работы равно О($2с\'\0.в\'т'\А$.

Следствие 1. Пусть распределение вероятностей на множестве А"' - бер-нуллиевское. Тогда для времени и памяти вычисления чувствительности $спх(к, т) верны оценки ТтеБег„< 0(]дв\-т >\А\) и 8расеВеп< 0^в\чп)

Следствие 2. Пусть распределение вероятностей на множестве Ат - это Марковское распределение вероятностей р порядка г. Тогда для времени и памяти вычисления вероятности 1\,(1.) верны оценки Т1те,[!агкт< 0(]0в\'т '\А''''[) и Ярасшл^ОАОвЫ >\АГ\)

Утверждение 5.2.3.Пусть ж - затравка в алфавите последовательностей П, А - алфавит выравнивают, согласованный с затравкой я и автомат В(п) = <()в, Чв , ОРв, А, (рв> является автоматом Ахо-Корасик. Пусть далее на множестве Ат задано Марковское распределение вероятностей р порядка г. Тогда чувствительность 8ет(к, т, р) затравки я относительно множества выравниваний А"' и распределения р может быть найдена методом динамического программирования за время 0(($)в\+\Аг$'\А\чп) с использованием памяти 0(($)В\ + \АГ$).

В разделе 5.3 приведен еще один пример приложения техники, описанной в разделе 5.1, - вычисление значимости найденного кластера регуляторных сайтов. Факторы регуляции транскрипции (ФРТ) связываются с фрагментами ДНК, содержащими специфичную для данного фактора последовательность нуклеоти-дов. Как правило, все последовательности, с которыми может связываться данный ФРТ имеют одну и туже длину. Множество таких последовательностей называется мотивом связывания ФРТ. В геноме область связывания ФРТ расположена перед регулируемым геном и называется цис-регуляторным модулем (ЦРМ). В последние годы было показано, что регуляция транскрипции с помощью ФРТ носит кумулятивный характер: в регуляции может участвовать несколько ФРТ, причем для каждого из них может быть несколько потенциальных мест связывания (вхождений соответствующих мотивов). Существующие программы распознавания ЦРМ основаны на поиске фрагментов генома, в котором перепредствлены соответствующие мотивы. Для практического использования этих программ необходимы средства оценки значимости полученных результатов. Формально задача может быть поставлена следующим образом.

Фиксируем алфавит ДНК Д={а, с, /}. Как и в разделе 5.2, будем считать, что на А"' (здесь да - длина предполагаемого ЦРМ) есть распределение вероятностей р, которое задается конечно-автоматным генератором (т= Я°с„ А, р а >. В частности, это распределение может быть Бернуллиевским или Марковским некоторого порядка г > 0.

Определение 5.3.1. Мотив длины / - это множество слов М с:Д'.

Определение 5.3.2. Пусть М - мотив длины I, О е Д" - последовательность ДНК длины т; т > I. Вхождение мотива М в последовательность И - это фрагмент В[х, х+и1] такой, что В[х, х+1-1] е М.

Пусть 1)[х], х) м1-1] - вхождение мотива А// и В[х2, х2+12-1] - вхождение мотива М2. Эти вхождения пересекаются, если пересекаются отрезки [хь А";+/г 1] иО[х2,х2Чг1].

Определение 5.3.2. Пусть дан набор М ~ < АЛ , ..., Л/, >, состоящий из 5 мотивов М, длины <, (г=1, ..., ь) и вектор к = < , ..., к5 >, состоящий из нату-

ральных чисел /с, (¡~1, ..., Пусть О е Д' - последовательность ДНК длины т. Набор мотивов М имеет к -вхождение в последовательность Д если для каждого/с {1.....р, О есть не менее к, (возможно, пересекающихся) вхождений мотива М.1.

Введем следующие обозначения:

Р(М, к) - множество всех последовательностей из Д, для которых существует к -вхождение набора М;

Р(М, к, т) - множество всех последовательностей из Д", для которых существует к -вхождение набора М;

В качестве меры достоверности потенциального ЦРМ длины т, содержащего А-, вхождений мотива М( (¡=1, •••, з) при заданном распределении вероятностей р на Д" используется величина Рр(Р(М, к, т)), где М = < М], ..., > и к = < к1, ..., к>. С помощью техники, описанной в п. 5.1, вычисление этой вероятности можно свести к вычислению обобщенной статистической суммы и, следовательно, найти искомую вероятность алгоритмом, основанным на методе динамического программирования.

Приведенные ниже утверждения дают оценки сложности этого алгоритма для различных вариантов задания распределения вероятностей р. Во всех этих оценках в качестве параметра фигурирует количество состояний автомата Ахо-Корасика С для множества М0 = А//<_/...<_/ М,. В цитированной выше работе Ахо и Корасик показано, что

т <цм), (5.з.1)

где Ь(М) — суммарная длина всех слов из множества М0. В приведенных ниже утверждениях фигурирует величина |0с|, а не более естественная величина поскольку, как показано в разделе 4.3, оценка (5.3.1) недостаточно точна.

Утверждение 5.3.3. Пусть М = < М), ..., Мй > - набор мотивов в алфавите А; к =- < к;, ..., к5 > - вектор с натуральными компонентами, С = <()с, Ц°с> & с, А, (рс> - автомат Ахо-Корасик для множества М0 = М/и... иМа и Сг= <()с, А, Ра> - конечно-автоматный генератор, задающий распределение вероятностей р на Л .

Тогда вероятность Рр(Р(М, к, т)) множества Р(М, к, т) относительно распределения р может быть найдена методом динамического программирования за время 0(($)с\'к1 «... •к!,т'^о\г,\А$ с использованием памяти 0(10с№ *■■- 'к; '\QoU- Если генератор О - детерминированный, то оценка времени может быть понижена до 0(($)с\,к1«... 'кх'т^с\'\А$

Следствие. Пусть распределение вероятностей на множестве А'" - Бернул-лиевское. Тогда для времени и памяти вычисления вероятности Рр(Р(М, к, т)) верны оценки ТппеВег„<0(^с\'к1«... 'к,'т'\А\) и$расеВет<0(\(>с\'к1«... -к,).

Утверждение 5.3.5. Пусть М = < , .... М, > - набор мотивов в алфавите А; к == < к] , ..., к„ > - вектор с натуральными компонентами, С = <()с, <Ц°с, с, А, <рс> - автомат Ахо-Корасик для множества М0 = А/) и... и М- яр — распределение вероятностей на Ат, задаваемое марковской моделью порядка г.

Тогда вероятность РР(Р(М, к, т)) множества Р(М, к, т) относительно распределения р может быть найдена методом динамического программирования за время 0( (\QcVki «... 'к;+ \А\Г) *т*\А\) с использованием памяти 0(](2с№ *•■-

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

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

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

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

4. Предложен алгоритм предсказания внутренних петель при построении оптимальной вторичной структуры РНК с временной сложностью 0(P*Iog2/?)> где Р - количество потенциальных спариваний нуклеотидов, п — длина последовательности РНК. Предложен алгоритм построения оптимального выравнивания последовательностей РНК с заданной вторичной структурой относительно аффинных штрафов за делеции с временной сложностью 0{m"nlo¿(п)), где m, п -длины сравниваемых последовательностей.

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

Основные результаты диссертации опубликованы в работах:

1. Roytberg M. A. A Search for Common Patterns in many Sequences // Comput. Appl. Biosci. 1992. Vol. 8, N 1. P. 57 - 64.

2. Roytberg M.A. Fast algorithm for optimal aligning of symbol sequences // In: Mathematical methods of the analysis of biopolymer sequences. AMS, Providence. 1992. P. 103-117.

3. Beridze T., Tsirekidze N., Roytberg M.A. On the tertiary structure of satellite DNA //Biochimie. 1992. Vol.74, N.l.P. 187-194.

4. Roytberg M.A. Similarity Search in Biological Sequences. // Modelling and Computer Methods in Molecular Biology and Genetics / Eds. V.A.Ratner and N.A. Kolchanov. NY: Nova Science Publishers, Inc. 1992. P. 81-86.

5. Gelfand M.S., Roytberg M.A. Prediction of the exon-intron structure by a dynamic programming approach // Biotechnology Software. 1992. P. 13-18.

6. Finkelstein, A.V. and Roytberg, M.A. Computation of biopolymers: a general approach to different problems // BioSystems. 1993. Vol.30. P.1-19.

7. Gelfand M.S., Podolsky L.I., Astakliova T.V. and Roytberg M.A. Prediction of the exon-intron structure and multicriterial optimization. //Bioinformatics and Genome Research / Eds. H.A.Lim, C.R.Cantor. Singapore: World Scientific Publ. Co. 1995. P. 173-183.

8. Gelfand M.S., Roytberg M.A. A dynamic programming algorithm for prediction of the exon-intron structure // BioSystems. 1993. Vol.30, P.173-182.

9. Nazipova N.N., Shabalina S.A., Ogurtsov A.Yu., Kondrashov A.S., Roytberg M.A., Buryakov G.V., Vernoslov S.E. SAMSON: a software package for the biopolymer primary structure analyses // Comput. Appl. Biosci. 1995. Vol. 11. P. 423-426.

10. Gelfand M.S., Podolsky L.I., Astakhova T.V., Roytberg M.A. Recognition of genes in human DNA sequences // Journal of Computational Biology. 1996. Vol. 3, N. 2. P. 223-234.

11. Ройтберг M.A., Астахова T.B., Гельфанд M.C. Алгоритм высокоспецифичного распознавания белок-кодирующих областей в последовательностях высших эукариот // Молекулярная биология. 1997. Т. 31, № 1.С. 25-31.

12.M.A.Roytberg, T.V.Astahova, M.S.Gelfand. Combinatorial approaches to gene recognition // Computers and Chemistry. 1998). Vol. 1, P. 229-236.

13.Sze S.H, Roytberg M.A., Gelfand M.S., Mironov A.A., Astakhova T.V., Pevzner P.A. Algorithms and software for support of gene identification experiments//Bioinformatics. 1998. Vol.1, N. 14. P. 14-19.

14. Mironov A.A., Roytberg M.A. Pevzner P.A., Gelfand M.S. Performance guarantee gene predictions via spliced alignment //Genomics. 1998. Vol. 51, P. 332339.

15.Ройтберг M.A., Симеоненков M.H., Таболина О.Ю. Парето-оптимальные выравнивания символьных последовательностей //Биофизика. 1998. Т. 44, №4. С, 581-594.

16. Mironov A A, Koonin EV, Roytberg MA, Gelfand MS. Computer analysis of transcription regulatory patterns in completely sequenced bacterial genomes //Nucleic Acids Res. 1999. Vol.15, N.27. P. 2981-2989.

17.Ramensky V.E., Makeev V.Ju., Roytberg M.A., Tumanyan V.G. DNA segmentation through the Bayesian approach //J Comput Biol. 2000. Vol.7, N.l-2. P. 215-231.

18.Ramensky V.E., Makeev V.Y., Roytberg M.A., Tumanyan V.G. Segmentation of long genomic sequences into domains with homogeneous composition with BASIO software//Bioinformatics. 2001. Vol.17, N.l 1. P. 1065-1066.

19.Kister A.E, Roytberg M.A, Chothia C., Gelfand I.M. The sequence determinants of cadherin molecules // Protein Science. 2001. Vol. 10. P. 1801-1810.

20. Roytberg, M.A., Ogurtsov A.Y., Shabalina S.A., Kondrashov A.S. A hierarchical approach to aligning collinear regions of genomes // Bioinformatics. 2002. Vol. 18. P.1673-1680.

21.0gurtsov A.Y., Roytberg M.A., Shabalina S.A. and Kondrashov A.S. OWEN: aligning long collinear regions of genomes // Bioinformatics. 2002. Vol. 18. P. 1703-1704.

22.Sunyaev S.R., Bogopolsky G.A., Oleynikova N.V., Vlasov P.K., Finkelstein A.V., Roytberg M.A. 2004. From analysis of protein structural alignments toward a novel approach to align protein sequences // Proteins. 2004. Vol. 54, P.569-582.

23.М.А.Ройтберг. Сравнительный анализ первичных структур нуклеиновых кислот и белков //Молекулярная биология. 2004. Т. 38, № 1. С. 92-103.

24.Kucherov, G., Noe, L. Roytberg, M. Multi-seed lossless filtration. // IEEE/ACM Transactions on Computational Biology and Bioinformatics. 2005. Vol.2, N. 1, P. 51-61.

25.Kucherov G., No'e L., and Roytberg M. 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

26.Astakhova T.V., Petrova S.V. , Tsitovich I.I., Roytberg M.A. Recognition of coding regions in genome alignment // Bioinformatics of Genome Regulation and Structure II. / Eds. N.Kolchanov and R. Hofestaedt. NY: Springer Sci-ence+Business Media. 2006. P. 3-10.

27.Ogurtsov, A.Yu, Shabalina, S.A., Kondrashov, A.S., Roytberg M.A. Analysis of internal loops within the RNA secondary structure in almost quadratic time // Bioinformatics. 2006, Vol. 22, No. 11, P. 1317-1324

28. Литвинов И.И., Лобанов М.Ю., MirpoHoe А.А., Финкелыптейн A.B., Ройт-берг M.A. Информация о вторичной структуре белка улучшает качество выравнивания // Молекулярная биология. 2006. Т. 40, № 3. С. 533-540.

29.Backofen R, Chen S, Hermelin D, Landau GM, Roytberg MA, Weimann O, Zhang K. Locality and gaps in RNA comparison // J Comput Biol. 2007. Vol. 14. N8. P.1074-1087.

30.Asthana S., Roytberg M., Stamatoyannopoulos J., Sunyaev S. Analysis of sequence conservation at nucleotide resolution // PLoS Comput Biol. 2007. V. 3, N 12. P. 254.

31.Boeva V, Clement J, Regnier M, Roytberg MA, Makeev VJ. Exact p-value calculation for heterotypic clusters of regulatory motifs and its application in computational annotation of cis-regulatory modules // Algorithms Mol Biol. 2007. Vol. 2. P.13-27

32.Polyanovsky V.O., Roytberg M.A., Tumanyan V.G. Reconstruction of genuine pair-wise sequence alignment // J. Comput. Biol. 2008. V. 15. N 4. P. 379-391.

33.Поляновский, В.О., Ройтберг, М.А., Туманян, В.Г. Новый подход к оценке достоверности выявления вставок-делеций в парном выравнивании // Биофизика. 2008. Т. 53, №4. С.533-537.

34. Корзннов О.М., Астахова Т.В., Власов П.К., Ройтберг М.А Статистический анализ участков ДНК в окрестности сайтов сплайсинга // Молекулярная биология. 2008. Т. 42. Лг» 1: С. 150-162

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

36.Regnier, M., Kirakosyan, Z., Furletova E. and Roytberg, M. A Word Counting Graph // London Algorithmics 2008: Theory and Practice. / Eds. Chan, J., Daykin, J.W. and Rahman M.S. London: College Publications. 2009. P. 10-43.

37.Ройтберг M.A. Вычисление вероятностей семейств биологических последовательностей // Биофизика. 2009. Т.54. № 5. С. 718-724

Подписано в печать 7 сентября 2009 г.

Формат 60x90/16

Объём 2,7 п.л.

Тираж 100 экз.

Заказ №211009251

Оттиражировано на ризографе в ООО «УнпверПринт» ИНН/КПП 7728572912X772801001

Адрес: 119333, г. Москва, Университетский проспект, д. 6, кор

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

http://www.univerprint.ru

Содержание диссертации, доктора физико-математических наук, Ройтберг, Михаил Абрамович

Введение.

1. Общая характеристика работы.

2. Основные понятия и краткий обзор результатов.

3. Структура работы.

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

1.1. Выравнивание символьных последовательностей.

1.2. Использование специфики биологических последовательностей.

1.3. Выравнивание геномов и построение затравок.

1.4. Динамическое программирование.

Глава 2. Алгоритмы выравнивания символьных последовательностей.Т.

2.0. Введение.

2.1. Глобальное выравнивание при кусочно-линейных штрафах за делеции.

2.2. Глобальное выравнивание при штрафах за делеции, пропорциональных длине делеции.

2.3. Векторные веса сопоставления символов и Парето-опти-мальные выравнивания.

2.4. Построение биологически-корректного выравнивания без явного задания штрафов за делеции.

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

3.0. Введение.

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

3.2. Выравнивания аминокислотных последовательностей с учетом вторичной структуры.

3.3. Выравнивание последовательностей РНК с заданной вторичной структурой.

3.4. Предсказание вторичной структуры РНК.

Глава 4. Алгоритмы парного выравнивания, основанные на выделении локальных сходств.

4.0. Введение.

4.1. Иерархическое выравнивание геномов.

4.2. Алгоритмические задачи, связанные с построением затравок для поиска локальных сходств.

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

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

5.0. Введение.

5.1. Общий метод вычисления вероятностей семейств символьных последовательностей.

5.2. Вычисление чувствительности затравок.

5.3. Вероятность обнаружения мотивов в случайных последовательностях.

Введение Диссертация по биологии, на тему "Алгоритмы сравнительного анализа первичных структур биополимеров"

1. Общая характеристика работы

1.1. Тема исследования.

Последовательности (первичные структуры) нуклеиновых кислот и белков - наиболее массовый и наиболее доступный в настоящее время вид молекулярно-биологических экспериментальных данных. Эти данные начали накапливаться со второй половины 70-х годов. За последние 30 лет масштабы получения новых последовательностей нуклеотидных кислот (секвенирования) выросли почти в миллиард раз. В настоящее время расшифровано около 900 полных геномов прокариотических организмов и около 100 геномов эукариот, включая геномы человека, мыши, шимпанзе и некоторых других млекопитающих.

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

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

Практически одновременно с накоплением данных о биологических последовательностях (особенно интенсивно в 60-х годах XX века) происходило развитие прикладной теории алгоритмов - разработка базовых алгоритмов анализа символьных последовательностей и связанных с ними алгоритмов сортировки и алгоритмов на графах. Движущими силами этого развития была, с одной стороны, разработка новых моделей вычислений (конечные автоматы и их варианты с различными видами памяти, в частности, - автоматы Мура, Мили, автоматы с магазинной памятью и др., см. обзор в [152]), а, с другой стороны, появление компьютеров и, следовательно, реальная потребность в обработке значительных (по тем временам) объемов данных. Итоги этого периода были подведены в монографиях Д. Кнута [178,179,180], А. Ахо, Дж. Хопкрофта и Дж. Ульмана [24]. Подробный анализ тенденций и результатов развития прикладной теории алгоритмов в указанный период дан в монографии В. А. Успенского и А. Л. Семенова [18].

С конца 70-х годов XX века аппарат прикладной теории алгоритмов начал применяться для анализа (прежде всего - сравнения) биологических последовательностей. При этом в начале применялись те же алгоритмы, что и для других приложений, например, распознавания речи и поиска сбоев при хранении файлов. Характерно название первого сборника, содержащего работы по биоалгоритмике - «Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison» [283].

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

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

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

В ходе исследования были решены следующие задачи:

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

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

3. Разработаны специализированные методы анализа нуклеотидных последовательностей (сравнение геномов, сравнение последовательностей РНК с известной вторичной структурой); разработан новый метод предсказания вторичной структуры РНК.

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

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

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

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

Основными из этих алгоритмов являются:

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

2) алгоритм построения множества Парето-оптимальных выравниваний относительно векторной весовой функции сопоставлений;

3) алгоритм выравнивания аминокислотных последовательностей белков с учетом их вторичной структуры

4) алгоритм предсказания внутренних циклов во вторичной структуре РНК;

5) алгоритм выравнивания вторичных структур РНК при заданной вторичной структуре;

6) алгоритм выравнивания геномов;

7) алгоритм вычисления чувствительности затравок для поиска локальных сходств;

8) алгоритм построения затравок для поиска локальных сходств в нуклеиновых и аминокислотных последовательностях.

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

1.4. Апробация работы и публикации

Материалы диссертации докладывались на международных и всероссийских конференциях и семинарах, в том числе: Московском семинаре по компьютерной генетике; отчетных конференциях программы «Геном человека»; II Съезде биофизиков России (Москва, 1999), симпозиуме «The Informatics of Protein Classification» (Университет Ратгерс, США, 2000), III, IV,V,VI международных конференциях по биоинформатике регуляции и структуры генома (Новосибирск, 2002, 2004, 2006, 2008), I, II и III Московских международных конференциях по вычислительной биологии (2003, 2005, 2007), международной конференции Combinatorial Pattern Matching-2004

Стамбул, Турция), международной конференции Workshop on Algorithms in Bioinformatics (Пальма де Майорка, Испания, 2005), международной конференции «Implementation and Application of Automata» (Прага, Чехия, 2007),международном симпозиуме NETT AB (Варенна, Италия, 2008).

По материалам диссертации опубликовано 37 статей в реферируемых научных журналах (из них 33 в соавторстве), а также более 50 тезисов докладов и препринтов.

Заключение Диссертация по теме "Биоинформатика", Ройтберг, Михаил Абрамович

3.2.5. Выводы.

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

ЗАКЛЮЧЕНИЕ. ♦

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

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

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

-у

0(т п^(п)).

4. Предложен алгоритм предсказания внутренних петель при построении оптимальной вторичной структуры РНК с временной сложностью 0{Р*\о£п), где Р - количество потенциальных спариваний нуклеотидов, п -длина последовательности РНК. Предложен алгоритм построения оптимального выравнивания последовательностей РНК с заданной вторичной структурой относительно аффинных штрафов за делеции с временной сложностью 0(тгп1о£*(п)), где т, п- длины сравниваемых последовательностей.

Библиография Диссертация по биологии, доктора физико-математических наук, Ройтберг, Михаил Абрамович, Пущино

1. Арлазаров B.JL, Диниц Е.А., Кронрод М.А., Фараджев И.А. Об экономном построении транзитивного замыкания ориентированного графа. //Докл. АН СССР. 1970. Т.134, №3. С.477-478.

2. Астахова Т. В., Олейникова Н.В., Ройтберг М А. Глава 6. Сравнительный анализинформационных биополимеров. //Компьютеры и суперкомпьютеры в биологии. Под.ред.В.Д.Лахно и М.Н.Устинина. Москва-Ижевск. 2002. С. 433-455.

3. Гельфанд М.С. Геномы и эволюция. // Вестник РАН. 2009 Т. 79. С. 411-418

4. Кобзарь А. И. Прикладная математическая статистика. Справочник для инженерови научных работников.// М.: Физматлит, 2006. —С. 816 .

5. Корзинов О. М., Астахова Т. В., Власов П. К., Ройтберг М. А. Статистическийанализ участков ДНК в окрестности сайтов сплайсинга. //Молекулярная биология. 2008. Т.42, №1, С.150-162.

6. Ландау, Л. Д., Лифшиц, Е. М. Статистическая физика. Часть 1. — Издание 3-е, дополненное. //М.: Наука, 1976. С.584 («Теоретическая физика», том V).

7. Левенштейн В. И. Двоичные коды с исправлением выпадений, вставок и замещений символов. //Доклады Академий Наук СССР. 1965. Т. 163, №4. С. 845848.

8. Литвинов И.И., Лобанов М.Ю., Миронов A.A., Финкельштейн A.B., Ройтберг М.А. Информация о вторичной структуре белка улучшает качество выравнивания. //Молекулярная биология. 2006. Т. 40, №3. С. 533-540.

9. Поляновский, В.О., Ройтберг, М.А., Туманян, В.Г. Новый подход к оценке достоверности выявления вставок-делеций в парном выравнивании. // Биофизика. 2008. Т. 53, №4. С.533-537.

10. Птицын А.Б. Финкельштейн A.B. Связь вторичной структуры глобулярных белков с их первичной структурой. // Биофизика. 1970. Т. 15, С. 757-767.

11. Ройтберг М.А. Алгоритм определения гомологии первичных структур. // Пущино, НЦБИ. 1984. 24 С. (препринт).

12. Ройтберг М.А. Еще один подход к задаче выравйивания последовательностей: больше сходств, меньше делеций и никаких весовых коэффициентов. // В: Труды конференции "Геном человека - 93" (Черноголовка, 10-12 марта 1993г.). 1993. С. 135

13. Ройтберг М.А. Сравнительный анализ первичных структур нуклеиновых кислот и белков. // Молекулярная биология. 2004. Т.38 №1, стр. 92-103,

14. Ройтберг М.А. Вычисление вероятностей семейств биологических последовательностей. // Биофизика. 2009. Т.54. № 5. С. 718-724

15. Ройтберг М.А., Астахова Т.В., Гельфанд М.С. Алгоритм высокоспецифичного распознавания белок-кодирующих областей в последовательностях высших эукариот. //Молекулярная биология. 1997. Т. 31, № 1. С. 25-31.

16. Ройтберг М.А., Симеоненков М.Н:, Таболина О.Ю. Парето-оптимальные выравнивания символьных последовательностей. //Биофизика. 1998. Т. 44, №4. С. 581-594.

17. Трахтенброт Б.А., Барздинь Я.М. Конечные автоматы. Поведение и синтез. //М., Наука. 1970. С.400.

18. Успенский В.А., Семенов A.JI. Теория алгоритмов: основные открытия и приложения. //М.Наука. 1987. С.288 .

19. Харари Ф. Теория графов.// М. УРСС. 2003.С. 300 .

20. Abagyan R.A, Batalov S. Do aligned sequences share the same fold? //J. Mol. Biol.1997. Vol. 273, P. 355-368.

21. Aerts S., Loo P.V., Thijs G, Moreau Y, Moor BD. Computational detection of cis -regulatory modules.// Bioinformatics. 2003. Vol.19, P.I5-I14. doi: 10.1093/bioinformatics/btg 1052.

22. Aho, A. V., Corasick, M. J. Efficient string matching: An aid to bibliographic search. //Communications of the ACM. 1975. Vol. 18, P.6.

23. Aho, A.V., Hirschberg, D.S., Ullman, J.D. Bounds on the Complexity of the Longest Common Subsequence Problem. //Journal of ACM. 1976. Vol. 23, N.l. P. 1-12.

24. Aho A., Hopcroft J., Ulman J. The design and analysis of computer algorithms // Addison-Wesley, Reading , MA., USA. 1974. P. 470.

25. Alexandrov N.N., Luethy R. Alignment algorithm for homology modeling and threading. //Protein Sci. 1998. Vol. 7, P. 254-258.

26. Altschul S.F. Amino acid substitution matrices from an information theoretic perspective. //Journal of molecular biology.1991. Vol.219, N.3. P. 555-65. PMID 2051488.

27. Altschul S.F. Generalized affine gap costs for protein sequence alignment. //Proteins.1998. Vol. 32, P. 88-96.

28. Altschul S.F., Bundschuh R., Olsen R., Hwa T. The estimation of statistical parameters for local alignment score distributions. //Nucleic Acids Res. 2001. Vol. 15, N.29. P. 351-361.

29. Altschul S.F., Gish W., Miller W., Myers E., Lipman D.J. Basic local alignment search tool. //J Mol Biol 1990. Vol.215, P.403-410.

30. Altschul S.F, Gish W. Local alignment statistics. // R.F. Doolittle, ed. Methods in Enzimology. Computer methods in macromolecular sequence analysis. Academic Press. 1996. Vol. 266. P. 460 480.

31. Altschul S., Madden Т., Schaffer A., Zhang J., Zhang Z., Miller W., Lipman D. Gapped BLAST and PSI-BLAST: A New Generation of Protein Database Search Programs. //Nucleic Acids Research. 1997. Vol. 25, N. 17. P. 3389-3402.

32. An Y., Friesner R.A. A novel fold recognition method using composite predicted secondary structures. //Proteins. 2002. Vol. 48, P.352-366.

33. Apostolico A., Giancarlo R. Seqeunce Alignment in Molecular Biology. // Journal of Computational Biology. 1998. Vol.5, N. 2 P. 173-196 .

34. Apostolico A., Guerra C. The longest common subsequence problem revisited. // Algorithmica. 1987. Vol.2, P. 315-316.

35. Arratia R., Waterman M. // Advances in Mathematics. 1985. Vol. 55, P. 13.

36. Arslan A.N., Egecioglu O., Pevzner P.A. A new approach to sequence comparison: normalized sequence alignment. //Bioinformatics. 2001. Vol. 17, P. 327-337.

37. Assis R., Kondrashov A. S. Rapid repetitive element-mediated expansion of piRNA clusters in mammalian evolution. // PNAS. 2009. Vol.l06, N.l7. P. 7079 7082.

38. Astakhova T.V., Petrova S.V. , Tsitovich I.I., Roytberg M.A. Recognition of coding regions in genome alignment. // Bioinformatics of Genome Regulation and Structure II. (Eds. N.Kolchanov and R. Hofestaedt) Springer Science+Business Med. 2006. P.3-10.

39. Asthana S., Roytberg M., Stamatoyannopoulos J., Sunyaev S. Analysis of sequence conservation at nucleotide resolution. // PLoS Comput Biol. 2007. Vol.3, N.12 :e254. Epub 2007 Nov 14.

40. Aurora R., Rose G.D. Seeking an ancient enzyme in Methanococcus jannaschii using ORF, a program based on predicted secondary structure comparisons. //Proc. Natl. Acad. Sei. USA. 1998. Vol.95, P. 2818-2823.

41. Backofen R., Chen S., Hermelin D., Landau G.M., Roytberg M.A., Weimann O., Zhang K. Locality and gaps in RNA comparison. // J Comput Biol. 2007. Vol. 14, N 8. P.1074-87.

42. Backofen R., Hermelin D., Landau G.M., Weimann O. Normalized similarity of RNA sequences. //In Proceedings of the 12th symposium on String Processing and Information Retrieval. 2005. P. 360-369.

43. Backofen R., Hermelin D., Landau G.M., Weimann O. Local alignment of RNA sequences with arbitrary scoring schemes. // Proceedings of the 17th annual symposium on Combinatorial Pattern Matching (CPM). 2006. P.211.

44. Backofen R., Will S. Local sequence-structure motifs in RNA. //Journal of Bioinformatics and Computational Biology (JBCB). 2004. Vol. 2, N.4. P.681-698.

45. Bafna V., Muthukrishnan S., Ravi R. Comparing similarity between rna strings. // Proceedings of the 6th Annual Symposium on Combinatorial Pattern Matching, LNCS 937. 1995. P. 1-16.

46. Bahr A., Thompson J., Thierry J., Poch O. BAliBASE (Benchmark Alignment dataBASE): enhancements for repeats, transmembrane sequences and circular permutations. //Nucleic Acids Research. 2001. Vol. 29, N. 1. P. 323-326.

47. Bailey T., Noble W. Searching for statistically significant regulatory modules. //Bioinformatics. 2003. Vol.19, P.II 16-1125. doi: 10.1093ftioinformatics/btgl054.

48. Barton, G. J., Sternberg, M. J. E., Evaluation and Improvements in the Automatic Alignment of Protein Sequences. // Prot. Eng., 1987. V.l, P. 89-94

49. Bateman A, Birney E. Searching databases to find protein domain organization. //Adv. Protein Chem. 2000. Vol.54. P. 137-157.

50. Bellman R. On the theory of dynamic programming, //Proc. Nat. Acad. Sei. U.S.A. 1952. Vol.38, P. 716-719.

51. Ben-Tabou de-Leon, S, Davidson E.H. Gene regulation: gene control network in development. //Annual Review of Biophysics and Biomolecular Structure Vol. 36, P.191-212

52. Beridze T., Tsirekidze N., Roytberg M.A. On the tertiary structure of satellite DNA. //Biochimie. 1992. Vol.74, N.l. P. 187-194.

53. Berman H.M, Westbrook J., Feng Z., Gilliland G., Bhat T.N., Weissig H., Shindyalov

54. N., Bourne P.E. The Protein Data Bank. // Nucleic Acids Res. 2000. Vol.28, N.l. P.235-42.

55. Bille P. A survey on tree edit distance and related problems. // Theoretical Computer Science. 2005. V. 337 , P. 217 239

56. Blanchette M., Sinha S. Separating real motifs from their artifacts. //Bioinformatics. 2001. Vol.17, P. 30-8.

57. Blin G., Touzet H. How to Compare Arc-Annotated Sequences: The Alignment Hierarchy. // String Processing and Information Retrieval. Springer Berlin / Heidelberg. 2006. LNCS V.4209/2006. P. 291-303.

58. Bordo A. and Argos P. Suggestions for "safe" residue substitutions in site-directed mutagenesis. // J. Mol. Biol. 1991. Vol. 244, P. 86-99.

59. Bork P., Koonin E.V. Predicting functions from protein sequences— where are the bottlenecks?//Nat. Genet. 1998. Vol.18, P.313-318.

60. Bourque G., Pevzner P. Genome-Scale Evolution: Reconstructing Gene Orders in the Ancestral Species // Genome Research. 2002. Vol. 12, P. 12:26-36.

61. Brejova B., Brown D., Vinar T. Optimal spaced seeds for homologous coding regions. //Journal of Bioinformatics and Computational Biology. 2004. Vol. 1, P. 595-610.

62. Brenner S.A, Cohen M.A, Gonnet G.H. Amino acid substitution during functionally constrained divergent evolution of protein sequences. //Protein Eng. 1994. Vol.7, P.1323-1332.

63. Brink M., Verbeet M., de Boer H. 1 Formation of the central pseudo- knot in 16S rRNA is essential for initiation of translation. // EMBO J. 1993. Vol.12, P.3987-3996.

64. Brown C.T., Rust A.G., Clarke P.J., Pan Z., Schilstra M.J., De Buysscher T., Griffin G., Wold B.J., Cameron R.A., Davidson E.H., Bolouri H. New computational approaches for analysis of cis-regulatory networks. //Dev Biol. 2002. Vol.246,P.

65. Brown D. Optimizing multiple seeds for protein homology search. //IEEE Transactions on Computational Biology and Bioinformatics. 2005. Vol. 2 , P. 29 38.

66. Brudno M, Malde S, Poliakov A, Do CB, Couronne O, Dubchak I, Batzoglou S. Glocal alignment: finding rearrangements during alignment. // Bioinformatics. 2003. Vol.19, N. IP. P. 54-62.

67. Buhler J. Provably Sensitive Indexing Strategies for Biosequence Similarity Search. //Proc. Sixth Ann. Int'l Conf. Computational Molecular Biology (RECOMB '02). 2002. P. 90-99.

68. Buhler J., Keich U., Sun Y. Designing Seeds for Similarity Search in Genomic DNA. // Proc. Seventh Ann. Int'l Conf. Computational Molecular Biology (RECOMB '03). 2003. P. 67-75.

69. Bulyk M.L. DNA microarray technologies for measuring protein-DNA interactions. //Curr Opin Biotechnol. 2006. Vol. 17, P.422-30. doi: 0.1016/j.copbio.2006.06.015.

70. Burkhardt S., Karkkaincn J. One-Gapped q-Gram Filters for Levenshtein Distance. // Proc. 13th Symp. Combinatorial Pattern Matching (CPM '02). 2002. Vol 2373, P. 225234.

71. Burkhardt S., Karkkainen J., Better Filtering with Gapped q-Grams. // Fundamenta Informaticae. 2003. Vol. 56, N. 1-2. P. 51-70, preliminary version in Combinatorial Pattern Matching 2001.

72. Byers T.M., Waterman M.S. Determining all optimal and nearoptimal solutions when solving shortest path problems by dynamic programming. //Oper Res. 1984. Vol.32, P.1381-1384.

73. Califano A., Rigoutsos I. Flash: A Fast Look-Up Algorithm for String Homology. //Proc. First Int'l Conf. Intelligent Systems for Molecular Biology. 1993. P. 56-64.

74. Carroll H„ Beckstead W., O'Connor T., Ebbert M„ Clement M., Snell Q., McClellan D. DNA reference alignment benchmarks based on tertiary structure of encoded proteins. //Bioinformatics. 2007. Vol23, P.2648-2649.

75. Cartwright. R.A.Logarithmic gap costs decrease alignment accuracy. BMC Bioinformatics 2006, 7:527

76. Chen S.-J. RNA Folding: Conformational Statistics, Folding Kinetics, and Ion Electrostatics. // Annu Rev Biophys. 2008. Vol. 37. P. 197-214.

77. Chen S., Wang Z., Zhang K. Pattern matching and local alignment for RNA structures. // Proceedings of the international confcrence on Mathematics and Engineering Techniques in Medicine and Biological Sciences (METMBS). 2002. P. 55-61.

78. Chen, W., Sung, W.K. On half gapped seed. //Genome Informatics. 2003. Vol. 14, P. 176-185.

79. Choi K.P., Zeng F., Zhang L. Good Spaced Seeds For Homology Search. //Bioinformatics. 2004. Vol. 20, P. 1053-1059.

80. Choi K., Zhang L. Sensitivity analysis and efficient method for identifying optimal spaced seeds. //Journal of computer and System Sciences. 2004. Vol. 68, P. 22—40.

81. Chou P.Y., Fasman G.D. Conformational parameters for amino acids in helical, betasheet, and random coil regions calculated from proteins. //Biochemistry. 1974. Vol.13,P.211-222.

82. Clyde D.E, Corado M.S, Wu X., Pare A., Papatsenko D,, Small S. A self-organizing system of repressor gradients establishes segmental complexity in Drosophila. //Nature. 2003. Vol.426, P.849-53. doi: 10.1038/nature02189.

83. Cocke J., Schwartz J.T. Programming languages apd their compilers: Preliminary notes. Technical report, Courant Institute of Mathematical Sciences, New York University. 1970.

84. Crochemore M., Rytter W. Jewels in Stringology. World Scientific Publishing, Hong Kong. 2002.

85. Crochemore M., Stefanov V. Waiting time and complexity for matching patterns with automata. //Information Processing Letters. 2003. Vol.87, N.3. P. 119-125.

86. Csuros M. Performing Local Similarity Searches with Variable Length Seed. // Proc. 15th Ann. Combinatorial Pattern Matching Symp. (CPM). 2004. P. 373-387.

87. Csuros M., Ma B. Rapid homology search with neighbor seeds. // Algorithmica. 2007. Vol. 48, N. 2, P. 187-202.

88. Cuff J.A., Barton G.J. Evaluation and improvement of multiple sequence methods for protein secondary structure prediction. //Proteins. 1999. Vol.34, P.508-519.

89. Currey K.M., Sasha D., Shapiro B.A., Wang J., Zhang K. An algorithm for finding the largest approximately common substructure of two trees. // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1998. Vol. 20, N.8. P.889-895.

90. Darling, A.C., Mau, B., Blattner, F.R., Nicole T. Perna: Mauve: Multiple Alignment of Conserved Genomic Sequence With Rearrangements//.Genome Res. 2004. V.14. N 7. P. 1394-1403

91. Das M.K., Dai H-K. A survey of DNA motif finding algorithms. // BMC Bioinformatics. 2007. Vol.8, N.52. P.247.

92. David R., Korenberg M.J, Hunter I.W. 3D-ID threading methods for protein fold recognition. //Pharmacogenomics. 2000. Vol.1, P. 445-455.

93. Dayhoff M. O., Schwartz R. M., Orcutt B. C. A model of evolutionary change in proteins. //Atlas of Protein Sequence and Structure. 1978. Vol. 5, N.3. P. 345-352.

94. Demaine E.D., Mozes S. Rossman B., Weimann O. An 0(n3)-time algorithm for tree edit distance. //Technical Report arXiv:cs.DS/0604037, Cornell University. 2006.

95. Di Franccsco V., Gamier J., Munson P.J. Protein topology recognition from secondary structure sequences: application of the Hidden Markov Models to the alpha class ' proteins.// J. Mol. Biol. 1997. Vol. 267, P.446^63.

96. Di Francesco V., Geetha V., Gamier J., Munson P.J. Fold recognition using predicted secondary structure sequences and Hidden Markov Models of protein folds.// Proteins. 1997. Vol.1, P.123-128.

97. Dijkstra E. W. A note on two problems in connexion with graphs. // Numerische Mathematik. 1959.Vol 1, P. 269-271.

98. Do C.B., Foo C.S., Batzoglou S. A max-margin model for efficient simultaneous alignment and folding of RNA sequences. // Bioinformatics. 2008. Vol. 24, N. 13. P. i68-76.

99. Domingues, F.S., Lackner, P., Andreeva, A., Sippl M.J. Structure-based evaluation of sequence comparison and fold recognition alignment accuracy. // J. Mol. Biol. 2000.Vol. 297, P.1003-1013.

100. Doolittle, R.F. Similar amino acid sequences: chance or common ancestry? //Science. 1981. Vol.214, P.149-159.

101. Doolittle W.F. The nature of the universal ancestor arid the evolution of the proteome. //Curr. Opin. Struc. Biol. 2000. Vol.10, P.355-358.

102. Dowell R.D., Eddy S.R. Efficient pairwise RNA structure prediction and alignment using sequence alignment constraints. // BMC Bioinformatics. 2006. Vol. 7, P.400.

103. Dulucq S., Tichi L. : RNA secondary structure comparison: exact analysis of the Zhang-Shasha tree edit algorithm. // Theor. Comput. Sci.2003. Vol. 306, P. 471-484

104. Dumas J.P., Ninio J. Efficient algorithms for folding and comparing nucleic acid sequences //Nucleic Acids Res. 1982. V. 10. P. 197-206.

105. Durbin R., Eddy D., Krogh A., Mitchison G. Pairvvise alignment. Biological sequence analyses. Probabilistic models of proteins and nucleic acids. //CambridgeUniversity Press, Cambridge, UK. 1998. P. 12-45.

106. Eckardt N.A. Everything in its place: Conservation of gene order among distantly related plant species. //Plant Cell. 2001. Vol.13, P. 723-725.

107. Eddy S.R. Where did the BLOSUM62 alignment score matrix come from?. //Nature biotechnology. 2004. Vol. 22, N.8. P. 1035-1036.

108. Edgar R. C. MUSCLE: multiple sequence alignment with high accuracy and high throughput. //Nucleic Acids Research. 2004. Vol. 32, N. 5. P. 1792-1797.

109. Edgar R.C. MUSCLE: A Multiple Sequence Alignment Method with Reduced Time and Space Complexity. //BMC Bioinformatics. 2004. Vol. 5, N.l. P.l 13.

110. Edgar R.C, Batzoglou S. Multiple Sequence Alignment. //Current Opinion in Structural Biology. 2006. Vol. 16, P.368-373.

111. Eppstein, D., Galil Z., Giancarlo R., Italiano G Sparse dynamic programming I: linear cost functions. //J. ACM. 1992. Vol. 39, P. 513 522

112. Eppstein, D., Galil Z., Giancarlo R., Italiano G. Sparse dynamic programming II: convex and concave cost functions //J. ACM. 1992. Vol. 39, P. 546 567

113. EVA server: http://cubic.bioc.columbia.edu/eva/

114. Farach-Colton M., Landau G., Sahinalp S.C., Tsur D. Optimal spaced seeds for faster approximate string matching. //J. Comput. Syst. Sci. 2007. Vol. 73, N.7. P. 1035-1044 .

115. Fernandez-Baca. D., Srinivasam S. Constructing tile minimization diagram of a two-parameter problem. //Operat. Res. Letters. 1991. Vol. 10, P.87-93.

116. Finkelstein, A.V. Roytberg, M.A. Computation of biopolymers: a general approach to different problems. // BioSystems. (spec, volume "Computer genetics". P.A.Pevzner, M.S.Gelfand, eds.). 1993. Vol.30, P. 1-19.

117. Fischel-Ghodsian F., Mathiowitz G., Smith T.F. Alignment of protein sequences using secondary structure: a modified dynamic programming method. //Protein Eng. 1990. Vol. 3, P.577-581.

118. Fischer D., Eisenberg D. Protein fold recognition using sequence-derived predictions. //Protein Sci. 1996. Vol.5, P. 947-955.

119. Fitch W. M., Smith T.F. Optimal sequence alignments. // Proc. Natl. Acad. Sci. USA. 1983. Vol. 80, P. 1382-1386.

120. Furletova E., Kucherov G., Noe L., Roytberg M., Tsitovich I. Transitive subset seeds for protein alignment. // Proseedings of The Sixth International Conference on Bioinformatics of Genome Regulation and Structure (BGRS'2008). 2008. P.77.

121. Gardner P.P, Wilm A., Washietl S. A benchmark of multiple sequence alignment programs upon structural RNAs. //Nucleic Acids Res. 2005. Vol. 33, P.2433-2439.

122. Gamier J., Osguthorpe D.-J., Robson B. Analysis of the accuracy and implications of simple methods for predicting the secondary structure of globular proteins. // J. Mol. Biol. 1978. Vol. 120, P. 97-120.

123. Gelfand M.S., Koonin E.V. Avoidance of Palindromic Words in Bacterial and Archaeal Genomes: a Close Connection with Restriction Enzymess. //Nucleic Acids Research. 1997. Vol.25, N.12. P.2430-2439.

124. Gelfand M., Koonin E., Mironov A. Prediction of Transcription Regulatory Sites in Archaea by a Comparative Genome Approach. //Nucleic Acids Research. 2000. Vol. 28, P. 695-705.

125. Gelfand M.S., Podolsky L.I., Astakhova T.V., Roytberg M.A. Recognition of genes in human DNA sequences. // Journal of Computational Biology. 1996. Vol.3, N.2. P.223-234.

126. Gelfand M.S., Roytberg M.A. Prediction of the exon-intron structure by a dynamic programming approach. // Biotechnology Software. 1992. P. 13-18.

127. Gerstein M, Levitt M. A structural census of the current population of protein sequences. ProcNatl Acad Sci USA. 1997 Oct 28;94(22):11911-11916.

128. Giegerich R., Hochsmann M., Kurtz S., Toller T. Local similarity in RNA secondary structures. //In Proceedings of Computational Systems Bioinformatics (CSB). 2003. P. 159-168.

129. Goad W.B, Kanehisa M.I. Pattern recognition in nucleic acid sequences. I. A general method for finding local homologies and symmetries.// Nucleic Acids Res. 1982 . Vol.11. N. 10. P. 247-263.

130. Gonnet G.H, Cohen M.A, Benner S.A. Exhaustive matching of the entire protein sequence database. //Science. 1992. Vol. 256, N.5062. P.1443-1445.

131. Gotoh O. An improved algorithm for matching biological sequences. // J. Mol. Biol. 1982. Vol.162, P.705-708.

132. Gukov, I.M., Astahova, T.V., Roytberg, M.A., Tsitovich I.I. One Shift" Alignments of Biological Sequences and their Statistics. // Proceedings of Moscow Conference on Computational Molecular Biology (MCCMB'05, Moscow, July 18-21, 2005. P. 136.

133. Gusfeld D. Algorithms on Strings, Trees, and Sequences. //Computer Science and Computational Biology. Press Syndicate of the University of Cambridge. 1997.

134. Gusfield D., Balasubramian K., Naor K. //Proc. 3rd Ann. ACM-SIAM Discrete Algorithms. 1992. P. 432^139.

135. Halfon MS, Michelson AM. Exploring genetic regulatory networks in metazoan development: methods and models. //Physiol Genomics. 2002. Vol.10 P. 131-43.

136. Hannenhalli S., Pevzner P.A. Transforming cabbage into turnip: Polynomial algorithm for sorting signed permutations by reversals. //Journal of the ACM. 1999. Vol. 46, P. 1-27.

137. Henikoff S., Henikoff J.G. Amino acid substitution matrices from protein blocks // Proc. Natl. Acad. Sci. USA. 1992. Vol. 89, P. 10915-10919.

138. Henikoff S., Henikoff J.G. Amino acid substitution matrices. // Adv. Protein Chem. 2000. Vol.54, P.73-97.

139. Hirschberg D.S. A linear space algorithm for computing maximal common subsequence // CACM. 1975. Vol. 18, N. 6. P.341-343.

140. Hirschberg D.S. Algorithms for the Longest Common Subsequence Problem. // Journal of the ACM . 1977. Vol. 24 , N.4. P. 664 675.

141. Hofacker, I.L., et al. Fast folding and comparison of RNA secondary structures. //Monatsh. Chemie. 1994. Vol. 125 , P.167-188.

142. Hofacker I.L., et al. Conserved RNA secondary structures in viral genomes: a survey. //Bioinformatics. 2004. Vol. 20, P. 1495-1499.

143. Hopcroft J.E., Ullman J.D. Formal languages and their relation to automata. Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA 1969. P. 262.

144. Hu YJ, Sandmeyer S, McLaughlin C, Kibler D. Combinatorial motif analysis and hypothesis generation on a genomic scalc. //Bioinformatics. 2000. Vol.16, P.222—232.

145. Hunt J.W., Szymanski T.G. A fast algorithm for computing longest common subsequences, //Comm. Assoc. Comput. 1977. Vol. 20, P.350-353.

146. Hwa T., Lassig M. Similarity Detection and Localization. //Phys. Rev. Lett. 1996. Vol. 76, P. 2591-2594:

147. Ilie L., Ilie S. Long spaced seeds for finding similarities between biological sequences. // Proceedings of the 2nd International Conference on Bioinformatics & Computational Biology (BIOCOMP). 2007. P. 3-8.

148. Iliopoulos C.S., Kubica M., Rahman M.S., Walen T. Algorithms for Computing the Longest Parameterized Common Subsequence // Combinatorial Pattern Matching. LNCS. 2007. Vol. 4580. P. 265-273.

149. Izing, E. Beitrag zut Theorie des Ferromagnetizmus. //Zeitschr. Phys.1925. Vol. 31, P.253-258.

150. Jaeger, J. A., et al. Improved predictions of secondary structures for RNA. //Proc. Natl Acad. Sci. USA. 1989. Vol. 20, P.7706-7710.

151. Jareborg N., Birney E., Durbin R. Comparative analysis of noncoding regions of 77 orthologous mouse and human gene pairs. // Genome Res. 1999. Vol.9, P. 815-824.

152. Jones D. Protein secondary structure prediction based on position-specific scoring matrices. // J. Mol. Biol. 1999. Vol. 292, P. 195-202.

153. Jones D.T., Taylor W.R., Thornton J.M. A new approach to protein fold recognition. //Nature. 1992. Vol. 358, P.86-89.

154. Jun S., Desplan C. Cooperative interactions between paired domain and homeodomain. //Development. 1996. Vol.122, P.2639-50.

155. Kabsch W., Sander C. Dictionary of protein secondary structure: pattern recognition of hydrogenbonded and geometrical features. //Biopolymers. 1983. Vol.22, P.2577-2637.

156. Kanehisa M. Use of statistical criteria for screening potential homologies in nucleic acid sequences. //Nucleic Acids Res. 1984. Vol.12. P. 203-213.

157. Karlin S., Altschul S.F. Methods for assessing the statistical significance of molecular sequence features by using general scoring schemes. // Proc. Natl. Acad. Sci. USA. 1990. Vol. 87, P.2264-2268.

158. Kasami T. An efficient recognition and syntax-analysis algorithm for context-free languages. //Scientific report AFCRL-65-758, Air Force Cambridge Research Lab, Bedford, MA. 1965.

159. Kato M, Hata N, Baneijee N, Futcher B, Zhang MQ. Identifying combinatorial regulation of transcription factors and binding motifs.// Genome Biol. 2004. 5:R56. doi: 10.1186/gb-2004-5-8-r56. Epub 2004 Jul 28.

160. Katoh K, Kuma K, Toh H, Miyata T: MAFFT version 5: Improvement in Accuracy of Multiple Sequence Alignment. // Nucleic Acids Research 2005, Vol. 3. P. 511-518.

161. Keich U., Li M., Ma B., Tromp J. On spaced seeds for similarity search. // Discrete Applied Mathematics. 2004. Vol. 138, No. 3. P. 253-263.

162. Kent, W.J.: BLAT-the BLAST-likc alignment tool.// Genome Research. 2002. Vol. 12, P. 656-664.

163. Kent W.J. Zahler A.M. Conservation, regulation, synteny, and introns in large-scale C.briggsae C.elegans genomic alignment. //Genome Res. 2000. Vol. 10, P. Ill5-1125.

164. Kister A.E, Roytberg M.A, Chothia C., Gelfand I.M. The sequence determinants of cadherin molecules. // Protein Science. 2001. Vol.10, P^ 1801-1810.

165. Kleene, S.C., Representation of events in nerve nets and finite automata. // Shannon, C.E., McCarthy, J. (Eds.), Automata Studies, Princeton University Press. 1956. P. 3-41.

166. Klein P.N. Computing the edit-distance between unrooted ordered trees. // Proceedings of the 6th European Symposium on Algorithms (ESA). 1998. P. 91-102.

167. Klingenhoff A, Freeh K, Werner T. Regulatory modules shared within gene classes as well as across gene classes can be detected by the same in silico approach. // Silico Biol. 2002. Vol.2, P. 17-26.

168. Knut D.E. Art of Computer Programming: Fundamental Algorithms. //Addison-Wesley, Reading, MA, USA. 1968. Vol. 1, P. 658.

169. Knut D.E. Art of Computer Programming: Seminumerical Algorithms. // Addison-Wesley, Reading, MA, USA. 1969. Vol. 2. P. 638.

170. Knut D.E. Art of Computer Programming: Sorting and Searching. // Addison-Wesley, Reading, MA, USA. 1973. Vol. 3, P. 736.

171. Korn L.J., Queen C.L., Wegman M.N. Computer analysis of nucleic acid regulatory sequences. // Proc Natl Acad Sci USA. 1977. Vol.74, N.10. P.4401^405.

172. Kramers, H.A., Wannier, G.H. Statistics of the one-dimensional ferromagnet.// Phys. Rev. 1941. Vol. 60, P.252-276.

173. Kruskal J.B. An Overview of Sequence Comparison: Time Warps. String Edit and Macromoleculas. // SIAM Rev. 1983. Vol.25, N. 26. P.201-238.

174. Kschischo M., Lassig M. Finite-temperature Sequence Alignment. // Pacific Symposium on Biocomputing. 2000. Vol. 5, P.621-632.

175. Kucherov G., Noe L., Ponty Y. Estimating seed sensitivity on homogeneous alignments. // Proceedings of the IEEE 4th Symposium on Bioinformatics and Bioengineering, IEEE Computer Society Press. 2004. P. 387-394.

176. Kucherov G., Noe L. Roytberg, M. Multi-seed lossless filtration. // IEEE/ACM Transactions on Computational Biology and Bioinformatics. 2005. Vol. 2, No. 1, 51-61.

177. Kucherov G., Noe L., Roytberg M. 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, preliminary version in WABI2005.

178. Kucherov G., Noe L., Roytberg M. Subset seed automaton. // Implementation and Application of Automata. Lecture Notes in Computer Science. Springer. BerlinHeidelberg. 2007. Vol. 4783, P. 180-191

179. Kung, H.T., Luccio, F., Preparata F.P.On Finding the Maxima of a Set of Vectors // J. ACM. 1975. Vol. 22, P. 469-476.

180. Latchman D. S. Eukaryotic Transcription Factors. //Elsevier Academic Press, New York, 4-th edition. 2004. P. 360.

181. Lee T.I., Young R.A. Transcription of eukaryotic protein-coding genes. //Annu. Rev. Genet. 2000. Vol.34, P. 77-137.

182. Lesk A.M. Introduction to protein architecture. //Oxford, N.Y.: Oxford Univ. press. 2001. P.360.

183. Lesk, A. M., M. Levitt, C. Chothia. Alignment of the Amino Acid Sequences of Distantly Related Proteins Using Variable Gap Penalties. //Protein Engineering. 1986. Vol.1, P.77-78

184. Li H., Rhodius V., Gross C., Siggia E.D. Identification of the binding sites of regulatory proteins in bacterial genomes. //Proc Natl Acad Sci USA. 2002. Vol.99, P.l 1772-7. doi: 10.1073/pnas.l 12341999. Epub 2002 Aug 14.

185. Li M., Ma B., Kisman D., Tromp J. PatternHunter II: Highly Sensitive and Fast Homology Search. J. Bioinformatics and Computational Biology. 2004. Vol. 2, N. 3. P. 417-440.

186. Li W.H. Molecular evolution. //Sunderland: Sinauer Associates. 1997. P.443.

187. Liaw G.J, Lengyel J.A. Control of tailless expression by bicoid, dorsal and synergistically interacting terminal system regulatory elements. //Mech Dev. 1993. Vol.40, P.47-61. doi: 10.1016/0925-4773(93)90087-E.

188. Lifanov A., Makeev V., Nazina A., Papatsenko D. Uniform clusters in Drosophila. //Genome Res. 2003. Vol.13, P.579-588. doi: 10.1101/gr.668403

189. Lim V.I. Algorithms for prediction of alpha-helical and beta-structural regions in globular proteins.// J. Mol. Biol. 1974. Vol. 88, P. 857-872.

190. Lipman D.J, Pearson W.R. Rapid and sensitive protein similarity searches. //Science. 1985. Vol.227, P.1435-1441.

191. Lothaire. Applied Combinatorics on Words. //Cambridge University Press, Reading, Mass. 2005.

192. Luthy R., McLachlan A.D., Eisenberg D. Secondary structure-based profiles: use of structure-conserving scoring tables in searching protein sequence databases for structural similarities. //Proteins. 1991. Vol.10, P.229-239.

193. Lyngso R.B., et al. Fast evaluation of internal loops in RNA secondary structure prediction. // Bioinformatics. 1999 Vol.15, P. 440^145.

194. Ma B., Li W, Zhang K. . Amino Acid Classification and Hash Seeds for Homology Search. // In: Lecture Notes in Computer Science. 2009. Vol. 5462. P. 44-51.

195. Ma B., Tromp J., Li M., PatternHunter: Faster and More Sensitive Homology Search. // Bioinformatics. 2002. Vol. 18, N. 3. P. 440-445.

196. Ma B., Zhang K. The similarity metric and the distance metric.// In Proceedings of the 6th Atlantic Symposium on Computational Biology and Genome Informatics. 2005. P. 1239-1242.

197. Maclsaac K.D., Fraenkel E. Practical strategies for discovering regulatory DNA sequence motifs. //PloS ComputBiol. 2006;2:e36. doi: 10.1371/journal.pcbi.0020036.

198. Mak D., Gelfand Y., Benson G. Indel seeds for homology search. // Bioinformatics. 2006. Vol. 22, N. 14. P. 341-349.

199. Makeev V., Lifanov A., Nazina A., Papatsenko D. Distance preferences in distribution of binding motifs and hierarchical levels in organization of transcription regulatory information. //Nucleic Acids Res. 2003.VoL31, P.6016-26. doi: 10.1093.

200. Markstein M., Markstein P., Markstein V., Levine M. Genome-wide Analysis of Clustered Dorsal Binding Sites Identifies Putative Target Genes in the Drosophila Embryo. //PNAS. 2002. Vol.99, P.763-768. doi: 10.1073/pnas.012591199.

201. Markstein M., Zinzen R., Markstein P., Yee K.P., Erives A., Stathopoulos A., Levine M. A regulatory code for neurogenic gene expression in the Drosophila embryo. //Development. 2004. Vol.131, P.2387-94. doi: 10.1242/dev.01124.

202. Marsden, R. L., McGuffin, L. J., Jones, D. T. Rapid protein domain assignment from amino acid sequence using predicted secondary structure. // Protein Sci.2002.Vol. 11, P.2814-2824.

203. Masek W.J. Paterson M.S. A Faster Algorithm for Computing String Edit Distances. //J. of Computer and Systems Sciences. 1980. Vol.20, N.l. 18-31.

204. Mathews D.H., et al. Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure. //J. Mol. Biol . 1999. Vol. 288, P. 911-940.

205. Mayr G., Domingues F.S., Lackner P. Comparative Analysis of Protein Structure Alignments. // BMC Structural Biology. 2007. Vol.7, P.50.

206. McCaskill, J.S. The equilibrium partition function and base pair binding probabilities for RNA secondary structure. // Biopolymers. 1990. Vol. 29, P.l 105-1119.

207. McNaughton R., Yamada H. Regular expressions and state graphs for automata. // IRE Transactions orTElectronic Computer 1960. Vol.9, N.l. P. 39^17.

208. Miller W. Comparison of genomic DNA sequences: solved and unsolved problems. //Bioinformatics. 2001. Vol.17, P. 391-397.

209. Miller W., Myers E.W. Sequence comparison with concave weighting functions. //Bulletin of Mathematical Biology. 1988. Vol.50, P. 97-120.

210. Mironov A.A., Koonin E.V., Roytberg M.A., Gelfand M.S. Computer analysis of transcription regulatory patterns in completely sequenced bacterial genomes. //Nucleic Acids Res. 1999. Vol.15, N.27. P. 2981-9.

211. Mironov A.A., Roytberg M.A. Pevzner P.A., Gelfand M.S. Performance guarantee gene predictions via spliced alignment. //Genomics. 1998, Vol. 51, P. 332-339.

212. Moore P.B. Structural motifs in RNA. //Annual review of biochemistry. 1999. Vol. 68, P.287-300.

213. Mott R. Maximum-likelihood estimation of the statistical distribution of Smith-Waterman local sequence similarity scores. //Bull. Math. Biol. 1992. Vol. 54. P.59-75.

214. Mott R. Accurate formula for p-values of gapped local sequence and profile alignments. //J. Mol Biol. 2000. Vol.300, P. 649-659.

215. Mount D.W. Bioinformatics. Sequence and genome analysis. //Cold Spring Harbor Laboratory Press,U.S. 2001. P. 564.

216. Myers E.W. An 0(N D) difference algorithm and its variations. // Algorithmica. 1986. Vol. 1,P. 251-266.

217. Myers E.W, Miller W. Optimal alignments in linear space.// Comput Appl Biosci. 1988a. Vol.4, N. LP. 11-7.

218. Myers E.W., Miller W. Chaining multiple-alignment fragments in sub-quadratic time. // Proceedings of the.sixth annual ACM-SIAM symposium on Discrete algorithms. San Francisco, SA. 1995. P. 38 47.

219. Naor D., Brutlag D. On near optimal a;ignmentsin biological sequences. // J. Comp.Biol. 1994. Vol.1, P. 349-366.

220. Navarro G,. Raffinot M. Flexible Pattern Matching in Strings //Practical On-Line Search Algorithms for Texts and Biological Sequences. Cambridge Univ. Press. 2002.

221. Nazipova N.N., Shabalina S.A., Ogurtsov A.Yu., Kondrashov A.S., Roytberg M.A., Buryakov G.V., Vernoslov S.E. SAMSON: a software package for the biopolymer primary structure analyses. //Comput. Appl. Biosci. 1995. Vol. 11, N. 4. P.423-426.

222. Needleman S.B., Wunsch C.D. A general method applicable to the search for similarities in the amino acid sequence of two proteins. // J.Mol. Biol. 1970. Vol.48, P.443-453.

223. Nicodeme P. Regexpcount, a symbolic package for counting problems on regular expressions and words. //Fundamenta Informaticae. 2003. Vol. 56, P. 71-88.

224. Nicodeme P., Salvy B., Flajolet P. Motif Statistics. //Theoretical Computer Science. 2002. Vol. 287, P. 593-618.

225. Noe L., Kucherov G. Improved Hit Criteria for DNA Local Alignment. // BMC Bioinformatics. 2004. Vol. 5, N. 149. Oct. 2004.

226. Noe L. and Kucherov G. YASS: enhancing the sensitivity of DNA similarity search. //Nucleic Acid Research, 2005. Vol. 33, P. 540-543.

227. Notredame C., Higgins D.G., Heringa J. T-Coffee: a novel method for fast and accurate multiple sequence alignment. //J Mol Biol. 2000. Vol. 302, P.205-217.

228. Nozaki Y., Bellgard M. Statistical evaluation and comparison of a pairwise alignment algorithm that a priori assigns the number of gaps rather than employing gap penalties //BIOINFORMATICS . 2005. Vol.21, N.8. P. 1421-1428.

229. Nussinov R., Jacobson, A.B. Fast algorithm for predicting the secondary structure of single-stranded RNA. // Proc. Natl Acad. Sci. USA. 1980. Vol. 77, P. 6309-6313.

230. Ogurtsov A.Y., Raytberg M.A., Shabalina S.A., Kondrashov A.S. OWEN: aligning long collinear regions of genomes. //Bioinformatics. 2002 . Vol. 18, P. 1703-1704.

231. Ogurtsov, A.Yu, Shabalina, S.A., Kondrashov, A.S., Roytberg M.A. Analysis of internal loops within the RNA secondary structure in almost quadratic time. // Bioinformatics. 2006, Vol. 22, No. 11, P. 1317-1324

232. Papatsenko D, Makeev V, Lifanov A, Regnier M, Nazina A, Desplan C. Extraction of Functional Binding Sites from Unique Regulatory Regions: The Drosophila Early Developmental Enhancers.// Genome Research. 2002. Vol. 12, P.470-481.

233. Papatsenko D. ClusterDraw web server: a tool to identify and visualize clusters of binding motifs for transcription factors. //Bioinformatics. 2007. Vol.23, P. 1032-1034. doi: 10.1093/bioinformatics/btm047.

234. Pareto V. Manual of political economy. New York: A.M. Kelley. 1972. 516 p.

235. Pascarella S., Milpetz F., Argos P. A databank (3D-ali) collecting related protein sequences and structures. // Protein Eng. 1996. Vol. 9, P.249-251.

236. Pearson W.R. Empirical statistical estimates for sequence similarity searches.// J.MoI.Biol. 1998. Vol.276, P. 71-84.

237. Pearson W.R. Rapid and Sensitive Sequence Comparison with FASTP and FASTA. // Methods Enzymol. 1990. Vol. 183. P. 63-98.

238. Pearson W.R., Lipman D.J. Improved tools for biological sequence comparison. //Proc Natl Acad Sci USA. 1988. Vol. 85, N.8. P. 2444-8.

239. Pearson W.R. Comparison of methods for searching protein sequence databases. //Protein Sci. 1995. Vol.4, N.6. P.l 145-60.

240. Pearson W.R. Flexible sequence similarity searching with the FASTA3 program package. //Methods Mol Biol. 2000. Vol. 132, P.l85-219.

241. Pearson W.R. Uva FASTA Downloads: http://fasta.bioch.virginia.edu/fastawww2/fastadown.shtmI

242. Pevzner P., Waterman M. "Multiple Filtration and Approximate Pattern Matching. Algorithmica. 1995. Vol. 13, P. 135-154.

243. Pirovano W., Feenstra K.A., Heringa J. The meaning of alignment: lessons from structural diversity. // BMC Bioinformatics 2008,V. 9 P. 556 doi:10.1186/1471-2105-9-556

244. Polyanovsky V., Roytberg M.A., Tumanyan V.G. Reconstruction of genuine pair-wise sequence alignment. //Comput Biol. 2008. Vol.15, N. 4. P. 379-91.

245. Ptitsyn O.B., Finkelstein A.V. Theory of protein secondary structure and algorithm of its prediction. //Biopolymers. 1983 . Vol. 22, P. 15-25.

246. Ramensky VE, Makeev VJu, Roytberg MA, Tumanyan VG. DNA segmentation through the Bayesian approach. //J Comput Biol. 2000.Vol.7, N.l-2. P. 215-31.

247. Ramensky V.E., Makeev V.Y., Roytberg M.A., Tumanyan Y.G. Segmentation of long genomic sequences into domains with homogeneous composition with BASIO software. // Bioinformatics. 2001. Vol. 17, N. 11. P. 1065-1066.

248. Regnier, M., Kirakosyan, Z., Furletova E., Roytberg, M. A Word Counting Graph.// In. London Algorithmics 2009. Theory and Practice (Chan, J., Daykin, J.W. and Rahman M.S., eds). 2009. P. 10-43.

249. Resch A. M. , L. Carmel L. Marino-Ramirez A. Y.'Ogurtsov S. A. Shabalina I. B. Rogozin E. V. Koonin. Widespread Positive Selection in Synonymous Sites of Mammalian. //Genes Mol. Biol. Evol. 2007. Vol. 24, N.8. P. 1821 1831.

250. Rice D., Eisenberg-D. A 3D-ID substitution matrix for protein fold recognition that includes predicted secondary structure of the sequence. //J Mol. Biol. 1997. Vol. 267, P.1026—1038.

251. Rice,P. Longden,I, Bleasby,A. EMBOSS: The European Molecular Biology Open Software Suite Trends in Genetics 2000. Vol.16, N 6. P. 276-277

252. Rochkind M.J. The Source Code Control System. // IEEE Transactions on Software Engineering. 1975. Vol.1, N. 4. P. 364-370.

253. Rost B., Schneider R., Sander C. Protein fold recognition by prediction-based threading. //J. Mol. Biol. 1997.Vol. 270, P.471-480.

254. Roytberg M.A. (a) Fast algorithm for optimal aligning of symbol sequences. // Mathematical methods of the analysis of biopolymer sequences. AMS, Providence. 1992. P.103-117.

255. Roytberg M.A. (b) A Search for Common Patterns in many Sequences. // CABIOS. 1992. Vol.8, N.l. P. 57-64.

256. Roytberg M.A. Similarity Search in Biological Sequences. // In:"Modelling and Computer Methods in Molecular Biology and Genetics" (eds. V.A.Ratner and N.A. Kolchanov). Nova Science Publishers, Inc., NY .1992, P. 81-86.

257. Roytberg M.A. Pareto-optimal alignments of symbol sequences. // Preprint, ONTI NTsBI, Pushchino. 1994.

258. Roytberg M.A., Astahova T.V., Gelfand M.S. Combinatorial approaches to gene recognition. // Computers and Chemistry. 1998. Vol.1. N.21. P. 229-236.

259. Roytberg M., Gambin A., Noe L., Lasota S., Furletova E., Szczurek E., Kucherov G. On subset seeds for protein alignment. // Transactions on Computational Biology and Bioinformatics. 2009. Vol. 6, N. 3. P. 483-494.

260. Roytberg, M.A., Ogurtsov A.Y., Shabalina S.A., Kondrashov A.S. A hierarchical approach to aligning collinear regions of genomes. Bioinformatics. 2002. Vol. 18, P.1673-1680.

261. Russell D., Out H., Sayood K. Grammar-based distance in progressive multiple sequence alignment // BMC Bioinformatics. 2008. V. 9. P. 306 doi: 10.1186/1471-21059-30

262. Russell R.B., Barton G.J. Structural features can be unconserved in proteins with similar folds. An analysis of side-chain to side-chain contacts secondary structure and accessibility.//J. Mol. Biol. 1994. Vol.244, P.332-350.

263. Russell R.B., Copley R.R., Barton G.J. Protein fold recognition by mapping predicted secondary structures. //J. Mol. Biol. 1996. Vol. 259, P.349-365.

264. Sanchez R, Sali A. Comparative protein structure modeling. Introduction and practical examples with modeller. //Methods Mol Biol. 2000. Vol.143, P.97-129.

265. Sander C., Schneider R. Database of homology-derived protein structures and the structural meaning of sequence alignment. //Proteins. 1991. Vol. 9, P.56-68.

266. Sankoff D. Simultaneous Solution of the RNA Folding, Alignment, and Protosequence Problems. // SIAM J Appl Math. 1985. Vol, 45, P.810-825.

267. Sankoff D., Kruskal J.B. (eds) Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison. // Reading, MA: Addison-Wesley. 1983. P.426

268. Schwartz S., Kent J., Smit A., Zhang Z., Baertsch R., R. Hardison R., Haussler D., Miller W. Human—Mouse Alignments with BLASTZ. // Genome Research. 2003. Vol. 13, P. 103-107.

269. Schwartz S., Zhang Z., Frazer K.A., Smit A., Riemer C., Bouck J., Gibbs R., Hardison R., Miller W. PipMaker A Web server for aligning two genomic DNA sequences. //Genome Res. 2000. Vol.10, P.577-586.

270. Sellers P.H. On the Theory and Computation of Evolutionary Distance, SIAM // J. Appl. Math. 1974. Vol. 26, P. 787-793.

271. Sellers, P. H. (1979), Pattern recognition in genetic sequences. //Proc. Natl. Acad. Sci. USA. 1979. Vol. 76, P. 3041.

272. Sellers P.H. The theory and computation of evolutionary distances: pattern recognition.// J.of Algorithms. 1980. Vol.1, P.359-373.

273. Shabalina S.A., Kondrashov A.S. Pattern of selective constraint in C.elegans and C.briggsae genomes. //Genet. Res. 1999. Vol. 74, P. 23-30.

274. Shabalina S.A., Ogurtsov A.Y., Kondrashov V.A., Kondrashov A.S. (2001) Selective constraint in intergenic regions of human and mouse genomes. //Trends in Genet. 2001. Vol.17, P.373-376.

275. Sheridan R.P., Dixon J.S., Venkataraghavan R., Kuntz I.D., Scott K.P. Amino acid composition and hydrophobicity patterns of protein domains correlate with their structures. //Biopolymers. 1985. Vol. 24, P.1995-2023.

276. Shi, J., Blundell, T. L., Mizuguchi, K. FUGUE: sequence-structure homology recognition using environment-specific substitution tables and structure-dependent gap penalties.// J. Mol. Biol. 2001. Vol.310, P.243-257.

277. Smith T. F. , Waterman M. S.,Fitch W. M. Comparative biosequence metrics. // J. Mol. Evol. 1981. Vol. 18, P. 38-46

278. Smith T.F., Waterman M.S. Identification of common molecular subsequences. //J. Mol. Biol. 1981. Vol.147, P.195-197.

279. Sosinsky A., Bonin C., Mann R., Honig B. Target Explorer: an automated tool for the identification of new target genes for a specified set of transcription factors. //Nucleic Acids Research. 2003. Vol.31, P.3589-3592. doi:10.1093/nar/gkg5.

280. Stephen G.A. String Searching Algorithms. // WORLD SCIENTIFIC PUBLISHING COMPANY. Singapore. 1994. P.256.

281. Sun Y., Buhler J. Designing Multiple Simultaneous Seeds for DNA Similarity Search.// Proc. Eighth Ann. Int'l Conf. Research in Computational Molecular Biology (RECOMB 2004). 2004. P 76-84.

282. Sunyaev S.R., Bogopolsky G.A., Oleynikova N.V., Vlasov P.K., Finkelstein A.V., Roytberg M.A. From analysis of protein structural alignments toward a novel approach to align protein sequences. // Proteins. 2004. Vol. 54, P.569-582.

283. Sze S.H, Roytberg M.A. , Gelfand M.S., Mironov A.A., Astakhova T.V., Pevzner P.A. Algorithms and software for support of gene identification experiments. //Bioinformatics. 1998. Vol.1, N. 14. P. 14-19.

284. Szymanski M, Barciszewska MZ, Erdmann VA, Barciszewski J: 5S Ribosomal RNA Database. //Nucleic Acids Res. 2002. Vol. 30, P. 176-178.

285. Thompson J.D, Koehl P., Ripp R., Poch O. BAliBASE 3.0: latest developments of the multiple sequence alignment benchmark. //Proteins. 2005. Vol.61, N.l. P.127-36

286. Tinoco,I.Jr., Uhlenbeck,O.C., and Levine,M.D. Estimation of secondary structure in ribonucleic acids. //Nature. 1971. V. 230. P. 3362-3367

287. Tinoco I. Jr, et al. Improved estimation of secondary structure in ribonucleic acids. // Nat. New Biol. 1973. Vol. 246, P.40-41.

288. Touzet H. Tree edit distance with gaps.// Information Processing Letters. 2003. Vol.85, N.3. P. 123-129.

289. Ukkonen E. Algorithms for approximate string matching. // Information and Control. 1985. Vol.64, P.100-118.

290. Ulam S. M. Some Ideas and Prospects in Biomathcmatics. // Annu Rev Biophys Bioeng. 1972. Vol.1, P.277-92.

291. Venkatesh B., GilliganP., Brenner S. Fugu: a compact vertebrate reference genome. //FEBS Lett. 2000. Vol. 476, P.3-7.

292. Vingron M, Argos P. Determination of reliable regions in protein sequence alignments. //Protein Engineering. 1990. Vol. 3, N.7. P.565-569.

293. Vingron M. Near-optimal sequence alignment // Current Opinion in Structural Biology Volume 6, Issue 3, June 1996, Pages 346-352

294. Vingron M., Waterman M.S. Sequence alignment and penalty choice: Review of concepts, case studies and implications // Journal of Molecular Biology. 1994. Vol.235, N. 1. P. 1-12

295. Vogt, G.,.Etzold, T., Argos P. An assessment of amino acid exchange matrices in aligning protein sequences: the twilight zone revisited. //J. Mol. Biol. 1995. Vol.249, P.816-831.

296. Wagner A. Genes regulated cooperatively by one or more transcription factors and their identification in whole eukaryotic genomes. //Bioinformatics. 1999. Vol.15, P.776-784. doi: 10.1093/bioinformatics/15.10.776.

297. Wagner R.A., Fischer M.J. The String-to-String Correction Problem. // Journal of ACM. 1974. Vol. 21, N. l.P. 168-173.

298. Wallqvist A., Fukunishi Y., Murphy L.R., Fadel A., Levy R.M. Iterative sequence/secondary structure search for protein homologs: comparison with amino acid sequence alignments and application to fold recognition in genome databases.//Bioi.

299. Waterman M.S. Sequence alignments in the neighborhood of the optimum with general application to dynamic programming. // PNAS. 1983. Vol. 80, P.10 31233124.

300. Waterman M.S. Efficient sequence alignment algorithm. // J.Theor.Biol. 1984. Vol.108,333-337.

301. Waterman M.S.(ed.) Mathematical methods for DNA sequences. // CRC Press, Boca Raton, FL. 1989. 293 p.

302. Waterman M.S. Introduction to Computational Biology. // London: Chapman and Hall Press. 1995.

303. Waterman M.S., Eggert M., Lander E. Parametric sequence comparisons. // Proc.Nat. Acad. Sci. USA. 1992. Vol. 89, P. 6090-6093

304. Waterman, M. S., Smith, T.F., Beyer, W.A. Some Biological Sequence Metrics // Advances in mathematics. 1976. Vol.20, P.367 387.

305. Waterman M. S., Smith T. F. RNA secondary structure: a complete mathematical analysis. // Mathematical Biosciences. 1978. Vol. 42, P. 257-266.

306. Wilbur W.Y., Lipman D.J. Rapid similarity searches of nucleic acid and protein data banks. // PNAS USA. 1983. Vol.80, P.726-730.

307. Wilm A, Mainz I, Steger G. An enhanced RNA alignment benchmark for sequence alignment programs. // Algorithms Mol Biol. 2006. Vol 24, P. 1:19.

308. Wolf Y.I., Rogozin I.B., Kondrashov A.S., Koonin E.V. Genome alignment, evolution of prokaryotic genome organization, and prediction of gene function using genomic context. //Genome Research. 2001. Vol.11, P. 356-372.

309. Wuchty S., Fontana W., Flofacker I.L., Schuster P. Complete suboptimal folding of RNA and the stability of secondary structures. // Biopolymers 1999. Vol. 49, P. 145165.

310. Xu J. Brown D., Li M., Ma B. Optimizing Multiple Spaced Seeds for Homology Search. //Proc. 15th Symp. Combinatorial Pattern Matching. 2004. P. 47-58.

311. Yang I.I-L, Wang S.H., Chen Y.H., Huang P.H., Ye L., Huang X., Chao K.M. Efficient methods for generating optimal single and multiple spaced seeds. // Proceedings of the 4th IEEE Symposium on Bioinformatics and Bioengineering. 2004. P. 411

312. Younger D. Recognition and parsing of context-free languages in time n3. // Information and Control. 1967. Vol. 10, N.2. P. 189-208.

313. Zafar N., Mazumder R., Seto D. Comparisons of gene colinearity in genomes using Gene0rder2.0. //Trends. Biochem. Sci. 2001. Vol. 26, P.514-516.

314. Zhang J, Jiang B, Li M, Tromp J, Zhang X, Zhang M. Computing exact P-values for DNA motifs. //Bioinformatics. 2007. Vol.23, P.531-537. doi: 10.1093/bioinformatics/btl662.

315. Zhang K., Shasha D. Simple fast algorithms for the editing distance between trees and related problems. //SIAM Journal on Computing. 1989. Vol. 18, N.6. P.1245-1262.

316. Zhang Z., Berman P., Miller W. Alignments without low-scoring regions. //J. Comput. Biol. 1998. Vol.5, P. 197-210.

317. Zhang Z., Raghavachari B„ Hardison R.C., Miller W. Chaining multiple-alignment blocks. //J. Comput. Biol. 1994. Vol. 1, P.217-226.

318. Zhang Z., Scheffer A., , Miller W., Madden T.,Lipman D., Koonin E., Altschul S. Protein sequence similarity searches using patterns as seeds // Nucleic Acids Research, 1998, Vol. 26, No. 17. P. 3986-3990

319. Zhu Z, Shendure J, Church GM. Discovering, functional transcription-factor combinations in the human cell cycle.// Genome Res. 2005. Vol.15, P.848-55. doi: 0.1101/gr.3394405.

320. Zuker M. On finding all suboptimal foldings of an RNA molecule. //Science. 1989. 244,48-52.

321. Zuker M. Suboptimal sequence alignment in molecular biology. Alignment with error analysis.//J Mol Biol. 1991 Vol.221, N.2. P.403-20.

322. Zuker M. Mfold web server for nucleic acid folding and hybridization prediction. //Nucleic Acids Res. 2003. Vol.31, P.3406-3415.

323. Zuker M., Sankoff D. RNA secondary structures and their prediction. //Bull. Math. Biol. 1984. Vol.46, P. 591-621.

324. Zuker M., Stiegler P. Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information. //Nucleic Acids. Res. 1981. Vol. 9, P. 133148.

325. Zvelebil, M., Baum, J.O. Understanding bioinformatics. London. Garland Science. 2007. P. 800

Информация о работе

Ройтберг, Михаил Абрамович
доктора физико-математических наук
Пущино, 2009
ВАК 03.00.28

Диссертация

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

Автореферат

Похожие работы