WWW.LIT.I-DOCX.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - различные публикации
 

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

^ a п Р а в а х рукописи

IIIII11 It II11IIIIIIIIII II III

llllllllllllllllllllllllllll сЛ^/Z—

003483Э4 1

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

Алгоритмы сравнительного анализа

первичных структур биополимеров

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

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

\ Э КОЯ 2ССЗ

Москва - 2009

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

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

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

Ученый секретарь диссертационного совета Д 002,077.02 доктор биологических наук, профессор СА*=П • У^ Рожкова Г.И .

Общая характеристика работы Актуальность темы. Последовательности (первичные структуры) нук­ леиновых кислот и белков - наиболее массовый и наиболее доступный в на­ стоящее время вид молекулярно-биологаческих экспериментальных данных .

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

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

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

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





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

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

Основные понятия выравнивания биологических последовательностей были сформированы в конце 70-х - начале 80-х годов XX века в работах Нидлмана, Вунша, Смита, Уотермана, Селлерса, Санкоффа, Эриксона, Туманяна и др .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация результатов. Материалы диссертации докладывались на ме­ ждународных и всероссийских конференциях и семинарах, в том числе: Москов­ ском семинаре по компьютерной генетике; отчетных конференциях программы «Геном человека»; II Съезде биофизиков России (Москва, 1999), симпозиуме «The Informatics of Protein Classification» (Университет Ратгерс, США, 2000), III, І,,І международных конференциях по биоинформатике и регуляции струк­ туры генома (Новосибирск, 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, S, где S ={ii,ji,...i„,j„ } - набор пар позиций в словах и и соответственно, таких, что 1 h... і„ \и\; 1 ji —jn |vj. Имеется в виду, что 4-я позиция слова а сопоставлена cjn-ii позицией слова (к = 1,..., гі), а непустые фрагменты вида u[h+l, it+i-1] и v[jk+l,jk+rlj удалены (здесь к ~ 0,.... п; i0 -jo = 0; і„+і-\и]+1; j„+]=]v\+l). Пары позиций is,Js назы­ ваются склейками. Вес Р(А) выравнивания А определяется как функция (обычно

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

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

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

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

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

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

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

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

5) вес сопоставления символов up] и р] задается произвольной функ­ цией ц(і, j, и, ) .

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

Идея алгоритма построения оптимального выравнивания символьных по­ следовательностей (слов) Vj и 2 при заданной кусочно-линейной системе весо­ вых функций состоит в следующем. Последовательно (в цикле по г, а внутри не­ го - в цикле noj) вычисляются т.н. оптимальные (і, 7')-выравнивання А[і, j] и их веса Рр, j]; здесь (/, /)-выравнивание слов и и - это такое выравниваний префиксов и/7, ij, vfj.jj, в котором сопоставлены позиции ufij и vfj]. Одновременно вычисляется выравнивание Mfi, j] - оптимальное выравнивание слов а и в ко­, тором последнее сопоставление позиций (х, у) удовлетворяет условиям хі; у j .

Выравнивание М[\и\, \\] будет искомым. Для вычисления веса Pfi.j] и соответ­ ствующего ему выравнивания Afi, j] алгоритм поддерживает к] • к2 рекурсивно вычисляемых величин mfs, 1], где kf. - количество интервалов линейности у функции штрафов за удаление фрагментов внутри слова При вычислении веса, Pfi, j] величина mfs, 1] хранит (в приведенной фор.ме, см. подробнее п.2.1.5 дис­ сертации) максимальный вес среди весов таких (х, vj-выравниваний, что длина іх-1 попадает в л-й интервал линейности слова и, а длина j-y-J - в /-й интервал линейности слова. При этом каждая из величин mfs, t] для очередной пары (г, j) перевычисляется за конечное время, что и обеспечивает указанное время работы алгоритма 0(кі'к2'\1\'\2\). Память, нужная алгоритму, оценивается формулой (см. раздел 2.1.10 диссертации) S(ct+c2-s\+c, -к] )-mi+ci -ml, где Ci,...,с4 - константы. Однако большая часть этой памяти нужна лишь при восстановлении оптимального выравнивания как пути в специальном дереве (дереве опорных склеек). Поэтому для потребной оперативной памяти получаем оценку 0(к1 •т2) .

В разделе 2.2 вес выравнивания G последовательностей Vj и 2 длины со­ ответственно /Я/ и т2 задается формулой W(G) = р - / - d'( m,-p-r) - d'( m2-p-r) где р - количество совпадений в выравнивании; г - количество несовпадений;

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

Базовыми понятиями алгоритма, описанного в разделе 2.2, являются поня­ тие опорного множества и специального веса начального выравнивания. На­ чальным выравниванием слов Vj и 2 называется выравнивание префиксов VjfO, х,] и 2[0, х2]. Начальное выравнивание G =,[0, xj, v2f0, xj, Q слов, и 2 называется граничным, еслиХ/ = \vt\ илих 2 = \v2\ .

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

Например, множество Sg, состоящее из единственного начального вырав­ нивания А0 = VjfOJ, VjfO], {(0,0)}, является опорным .

Определение 2.2.1. Пусть G = Vj [0, xj, v2 f0, xj, Q - начальное вы­ равнивание слов \'і н 2 длин т} и т2. Специальным весом выравнивания G назы­ вается величина SP(G) = P(G)+ счпіп(пі]-Хі, m2-x2) -d'\(mrxi)-f ni2-x2) | .

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

Опорное множество S называется терминальным, если некоторое граничное вы­ равнивание является максимальным в нем .

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

1. Пусть G - выравнивание слов V/ н 2 и начальное выравнивание В явля­ ется префиксом выравнивания G. Тогда P(G)SP(B) .

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

- оптимальное выравнивание слов vj и 2 .

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

Построение терминального опорного множества и соответствующего гра­ ничного максимального выравнивания выполняется с помощью построения т.н .

канонической последовательности опорных множеств fSJ. Множество S0 состо­ ит из одного выравнивания \і(0,0], 2[0,0], {(0,0)}. Пусть опорное множество Si построено. Если S, - терминальное множество, то процесс построения канони­ ческой последовательности закончен. В противном случае выбирается некоторое начальное выравнивание i, e St (лидер множества Si) и это выравнивание заменя­ ется таким набором продолжений D(Lj), что любое оптимальное выравнивание, продолжающее выравнивание L,, является продолжением одного из выравнива­ ний множества D(L). Это гарантирует то, что полученное множество Si+i будет опорным. Далее из построенного множества, возможно, удаляются некоторые избыточные выравнивания, т.е. такие выравнивания, удаление которых оставля­ ет множество Sl+i опорным. Таким образом, Центральная идея алгоритма в том, что в качестве лидера выбирается мак­ симальное выравнивание текущего опорного множества. Это позволяет избе­ жать рассмотрения «неперспективных» начальных выравниваний и обеспечива­ ет экономию времени при сравнении близких последовательностей .

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

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

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

Определение 2.3.1. Пусть к 2 - целое число. Векторная весовая функция

- это функция, сопоставляющая каждому выравниванию А ^-мерный вектор (А), называемый (векторным) весом выравнивания А .

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

Другими примерами элементарных весовых функций являются:

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

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

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

Определение 2.3.4. Пусть S\ и $ — последовательности; V— векторная ве­ совая функция. Выравнивание А последовательностей 5] и 5? называется Парето-оптимальным относительно весовой функции V, если (А) является Паретооптнмальным вектором в множестве векторных весов всех возможных выравни­ ваний последовательностей St и S2 .

Важность множества Парето-оптпмальных выравниваний определяется следующим наблюдением. Пусть (А) = VrfA),.... Vk(A) - векторная весовая функция; g(xt,...,х,,) - функция к переменных, монотонно неубывающая по каж­ дому из аргументов, ір(А) -•=• gfVjfA),..., Vk(A)) - скалярная весовая функция и В --оптимальное выравнивание некоторых последовательностей относительно функции р. Тогда В - оптимальное выравнивание этих последовательностей от­ носительно вектор-функции V. В частности, если В - оптимальное выравнивание некоторых последовательностей относительно линейной комбинации функций ;(А),..., Vt(A) с положительными коэффициентами, то В - оптимальное вырав­ нивание этих последовательностей относительно вектор-функцші (А) .

В разделе 2.3 представлен алгоритм построения множества всех Паретооптимальных выравниваний данных последовательностей S-. и Si относительно данной весовой функции (А). Этот алгоритм является алгоритмом динамиче­ ского программирования н основан на соотношении дистрибутивности между операцией сложения векторов и операцией взятия Парето-подмножества объе­ динения двух Парето-оптпмальных множеств.

Более точно, пусть с - число, множества 7 Г/, Т? cR, причем Т Tj, Т:

- Парето-оптимальные множества; че­ рез Pareto(T) обозначается Парето-подмножество множества 7/. Рассмотрим следующие операции:

с ® Т = Pareto({ х,+с,..., хк +с\ х,,..., хк е Tfj, Т, © Т2 = Рагею(І) KJTJ .

Тогда с ® ( Г, Т2) - (с ® Т,) ® (с ® Т,) .

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

Для последовательностей длины гп\ и тг время работы такого алгоритма оценивается как 0(с(пц, ШгУпц'гпг), где коэффициент с(т\, т2) зависит от вы­ бранной весовой функции и определяется временем выполнения операций ®и © для этой функции. В некоторых случаях приведенная оценка может быть улучшена.

В частности, оценку времени для случая упомянутой выше весовой функции 1)(Л) = (NwnMuich{A), -NwnDe!(A)) дается следующей леммой:

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

Алгоритм Pareto_Align_Del_Dmax строит множество Парето-оптимальных весов и Парето-оптимальных выравниваний для последовательностей S\ и S2 от­ носительно весовой функции VD(A) = (Match(A), -NumDel(A)) за время 0(шіп(я, 2d)wn'log(r)) .

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

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

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

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

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

Через D(g) обозначим «производную» S(g):

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

Значения S(g) могут быть найдены путем построения Парето-оптимальных вы­ равниваний относительно векторной весовой функции WG(A) = (WeightMatch(A\ -NumGap(A)) Допустим, что удалением некоторого количества фрагментов из последо­ вательностей и и можно получить достаточно похожие последовательности равной длины; эти фрагменты назовем «правильными». Удаление «правильно­ го» фрагмента восстанавливает соответствие между (обычно, протяженными) гомологичными фрагментами исходных последовательностей и, тем самым, ве­ дет к существенному увеличению веса S(g) (значение D(g) велико). Когда все «правильные» фрагменты удалены, новые удаления уже не мотивированы био­ логически и, следовательно, не могут привести к существенному увеличению S(g) (значение D(g) мало/ Наибольшее значение параметра g, прн котором зна­ чение D(g) велико, назовем критическим значением, а соответствующее ему вы­ равнивание - критическим выравниванием.. Мы полагаем, что критическое вы­ равнивание наиболее (среди других Парето-оптимальных выравниваний) соот­ ветствует биологически корректному выравниванию данных последовательно­ стей. Это приводит к следующему методу выравнивания последовательностей .

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

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

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

Получена верхняя оценка для величины D„ «малых» значений D(g):

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

–  –  –

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

Для среднего значения М имеем формулу:

M = D(p-p0)-pd .

Если указанное значение будет менее Д.,, то удаление таких «правильных»

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

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

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

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

Исследована зависимость степени сходства между алгоритмическими и структурными выравниваниями от степени сходства между сравниваемыми по­ следовательностями и выявлены причины расхождений между этими выравни­ ваниями. В качестве количественной оценки качества алгоритмически получен­ ных выравниваний использовались две взаимодополняющих меры: (1) Точность выравнивания (обозначение: АІі_Асс) равна отношению количества одинаковых сопоставлений (/) в обоих выравниваниях к общему количеству сопоставлений в эталонном выравнивании (G): АІі_Асс = I/G* 100 %. {2) Достоверность выравШбои«.я_(обозначение: AliConjl, равна отношению количества одинаковых со­ поставлений в обоих выравниваниях (7) к общему количеству сопоставлений в алгоритмически построенном выравнивании (A): Ali_Conf = І/А*100 %. Нефор­ мально говоря, точность АН Асе показывает, какую долю эталонного выравнивания удалось восстановить, а достоверность Ali_C,onf— насколько можно дове­ рять построенному выравниванию .

Как видно из рис. 3.1.2, алгоритм SW может строить выравнивания, хоро­ шо совпадающие с эталонными, только при уровне сходства сравниваемых бел­ ков более 30-40%. Этот диапазон уровня гомологии (ID 30%) примерно совпа­ дает с известным порогом %Ю, выше, которого можно достоверно восстано­ вить структурное выравнивание, зная только последовательности [%56, %58-60] •3% J&* Рнс. 3.1.2. Зависимость точности восстановления эталонных выравниваний методом SW от уровня сходства (%Ш) сравниваемых белков. Каждая точка соответствует паре эталонных белков. Х-координата точки равна %Ю пары, а /"-равный координата - значению точности .

Зависимость для достоверности практически такая же При уровне гомологии меньше 10% метод SW не может восстановить правильное выравнивание даже частично. Для диапазона уровня гомологии от 10% до 30% выравнивания Смнта-Уотермана показывают очень широкий раз­ брос точности и достоверности .

Для разных пар последовательностей с одинако­ вым уровнем сходства построенные SW-выравнивания могут иметь очень раз­ личные значения точности и достоверности. Это означает, что в этом диапазоне %Ю качество алгоритмических выравниваний определяется не только уровнем сходства сравниваемых белков, но и «внутренними свойствами» их эталонных выравниваний. Эти «внутренние» свойства удобно формулировать в терминах т.н. «островов» .

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

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

–  –  –

Рисунок 3.1 .

5. (а) Гистограмма распределения количества островов в эталонных выравнивани­ ях (белый) и выравниваниях SW (черный) по весу острова, (б) Суммарная длина островов .

имеющих вес в пределах диапазонов. Эталонные острова - белый, SW - черный

–  –  –

Рисунок 3.1 .

6. Более детальное представление данных рис. 3.1.5а. Гистограммы суммарных длин островов с весом в пределах указанных по оси X диапазонов отдельно для каждой их 3-х областей %Д).Данные по эталонным островам показаны белым, SW - черным С увеличением степени сходства сравниваемых белков (см. рис. 3.1.6) раз­ личие в весе эталонных и построенных островов уменьшается. Однако даже для высокого уровня сходства белков (2D 30%) встречаются эталонные острова от­ рицательного веса .

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

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

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

Как указывалось выше, предложенный метод может использоваться как с экспериментально полученными, так и с теоретически предсказанными вторич­ ными структурами. Для предсказания вторичной структуры использовалась про­ грамма PSIPRED [Bryson К, McGuffm LJ, Marsden RL, Ward JJ, Sodhi JS. & Jones DT. Protein structure prediction 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.coluinbia.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 rec­ ognition in genome databases. Bioinformatics. 2000. V. 16. P. 988-1002] В качестве эталонных выравнивашш, как и в разделе 3.1, использовались выравниваши из базы BaliBase (см. выше); корпус эталонных парных выравни­ ваний был разделен на обучающий и тестовый наборы. Источником данных об экспериментально определенных вторичных структурах белков служила база данных DSSP [Kabsch W, Sander С. Dictionary of protein secondary structure: pat­ tern recognition of hydrogen-bonded and geometrical features. Biopolymers. 1983. V .

22, P. 2577-2637] .

–  –  –

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

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

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

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

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

(2) каждая внутренняя вершина имеет по меньшей мере двух сыновей;

причем самый левый и самый правый из этих сыновей - листья, они называются главными сыновьями .

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

Говоря неформально, каждая внутренняя вершина соответствует «спари­ ванию» (т.е. образованию водородной связи, pairing) своих главных сыновей .

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

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

Пусть Si, Pj, S2, Р2 - РНК-структуры без псевдоузлов, здесь S,- - по­ следовательность, Pt - множество спариваний (/'=7, 2); G - выравнивание Si и S2 .

Будем говорить что в выравнивании G спаривание (xh yt) e Pi сопоставлено спариванию (х2, у2) € Р2, если X; сопоставлено х2 иуі сопоставлено^ .

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

Пусть задана весовая система М, g, d, b, c; Sh Рг и S2, P2 струк­ туры и А - их выравнивание с набором сопоставленных позиций (склеек) (Ph qk I к = 1,..., N). Пусть т - общее число удаленных фрагментов в А; I - сум­ марная длина этих фрагментов, к - количество спариваний в Р} and P2\ которые не сопоставлены в А другим спариваниям: / = {\Р} \ + \Р2 \-к)/2 - количество со­ поставлений спариваний. Тогда структурным весом выравнивания А называется величина Score(A) = I.t.^-MiSdPk], S2[q,J) -gm-dl + bt- с к. (3.3.1) Это определение соответствует определению веса глобального выравни­ вания последовательностей с аффинными весовыми функциями удаления фраг­ ментов, к которому добавлены бонусы и штрафы за правильное (неправильное) сопоставление спариваний .

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

Определение 3.3.4. Выравниванием РНК-лесов F ; и F2 называется такое множество А с VertexfFJx Vertex(F2), что для каждой пары (Vi,\vi), (v2,\v2) e A выполнено.' 1) 'і = г тогда и только тогда, когда it'i = w2 (иными словами, А - взаимно однозначное соответствие.между подмножествами Vertex(Fj) н Vertex(F2)) .

2) вершина l'j предшествует вершине 2 в смысле левого обхода леса Fi тогда и только тогда, когда вершина W| предшествует вершпне і2 в смысле ле­ вого обхода леса F2 .

3) если (у, л) € А, то либо обе вершины и w - листья, лпбо обе они внутренние вершины;

4) Пусть (у, w) e VertexfFJx Verlex(Fi): v ; и - главные сыновья верши­ ^ ны ; Wj и w2 - главные сыновья вершины №. В этих условиях (v, w) eA тогда и только тогда, когда (VJ.WJ), (v^ivj) • А .

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

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

Определение 3.3.13. Пусть L, R с {1, 2} и А - выравнивание лесов F, и F2 .

Пусть кі(А) (соответственно, кц(А) ) - количество таких индексов іе L (соответ­ ственно, /е К), что лес 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(Fj,F2, L, R) обозначается наибольшее возможное значение делеционного веса WD(A, L, R) для выравниваний А лесов F] и F2 .

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

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

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

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

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

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

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

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

Энергия структуры, в которой замыкающая склейка (А, В) принадлежит внутренней петле, образованной склейками (А, В) и (х, у), задается формулой AGfi,tental_Loip(A, В; X, }) = =fun(dA+dB) +fDlJI{ciA~dB)+AG(x,y) = =Ы(В-А) - (у-х+2)) +/DI/(B+A) - (у+х)) + AG(x, у). (3.4.1) Здесь fun(t) — фиксированная выпуклая функция, она хорошо аппрокси­ мируется логарифмической функцией.

Функция foyfi) определяется соотноше­ ниями:

fDiffOJ = basejevel, если |/| width, fDiff (t) = (basejevel I widlh)*\t\, если |/| width. (3.4.2) Таким образом, энергия оптимальной структуры среди структур с замы­ кающей склейкой (А, В) при условии, что эта склейка принадлежит внутренней петле, задается формулой AGi„iermi_Loop(A, В) = = min{AGi„,mK,LLoop(A, В; х, у) \(х, у) е U & АхуВ} = = min{fle„({B-A) - {у-х+2)) +fm((B+A) - ()*х)) +AG(x, y)\ \(х, у) е U & АхуВ}. (3.4.3 ) Говоря неформально, AGimermi_L.oop описывает увеличение (т.е. ухудшение

- структура с большей энергией менее стабильна) энергии структуры РНК в свя­ зи с образованием внутренней петли. Это увеличение зависит от длин dA и dB крыльев петли и представляется в виде суммы двух слагаемых. Одно из слагаемых (fim(t)) зависит от суммарной длины крыльев, другое {fDiff (I)) - от асиммет­ рии петли, т.е. величины | dA - dB |. Если асимметрия мала, то_/Ь# (0 растет ли­ нейно; для значений асимметрии, превышающих порог width, значение fDig- (t) постоянно. Такой своеобразный вид функции AGimer„ai_Lo0p(A, В; х, у) и представ­ ляет основную трудность при анализе внутренних петель .

В первых алгоритмах построения оптимальной вторичной структуры ми­ нимум в (3.4.3) находился прямым перебором, что приводило к общему времени анализа внутренних петель 0(L ) ; позднее был предложен алгоритм [Lyngso et а\. Fast evaluation of internal loops in RNA secondary structure prediction //Bioinformatics. 1999. V. 15. P. 440-445] со сложностью 0(L3). Представленный в разделе 3.4 алгоритм AFOLD использует технику динамического программиро­ вания для разреженных матриц (sparse dynamic programming, см. [Eppstein et a] .

Sparse Dynamic Programming II: Convex and Concave Cost Functions J. ACM. 1992 .

V. 39, P. 546-567]) и имеет временную сложность 0(M*log'(Z)), где L - длина последовательности, М - количество теоретически допустимых спариваний. Т.к .

Л/ L2, эта оценка существенно улучшает оценку 0(L?) лучшего из ранее пред­ ложенных алгоритмов. Отметим, что использованная алгоритмическая техника близка к технике выравнивания последовательностей и может быть использова­ на при построении выравниваний геномов .

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

Рассмотренные в главах 2 и 3 алгоритмы оптимального выравнивания имеют квадратичную временную сложность — их время работы (в худшем слу­ чае) пропорционально произведению длин последовательностей. Такое время слишком велико для многих бноинформатических приложений, в частности, для сравнения сннтенных фрагментов геномов (длина ~ 10 нуклеотидов. Глава 4 посвящена выравниванию последовательностей, не связанному с оптимизацией весовой функции, и возникающим в этой связи алгоритмическим задачам. В раз­ деле 4.1 представлен иерархический алгоритм геномного выравнивания OWEN, основанный на построении систем коллинеарных локальных сходств. Разделы

4.2 и 4.3 посвящены поиску локальных сходств с помощью т.н. затравок - наи­ более распространенно^ и быстродействующему из известных методов по­ строения локальных сходств. В разделе 4.2 дано определение затравки в наибо­ лее общем виде и рассмотрен простейший класс «неклассических» затравок разреженные затравки, предложенные в [Ма, В., Tromp, J, and Li, M. PatternHunter: Faster and More Sensitive Homology Search // Bioinformatics. 2002. V. 18 .

P. 440-445, 2002]. Для этого класса указан вид оптимальной оптимальной за­ травки среди затравок с одной несущественной позицией. Раздел 4.3 посвящен введенному нами (совместно с Г.Кучеровым и Л. Ноэ) классу затравок - класси­ фикационным затравкам, и некоторым алгоритмическим проблемам, связанным с вычислением чувствительности затравок этого класса. Задача вычисления чув­ ствительности произвольных затравок рассмотрена в разделе 5.2 главы 5 .

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

подробнее п.3.1) .

Сходство синтенных участков геномов «средне близких» организмов (че­ ловек - мышь, С.Elegance - C.Briggsae и т.п.) существенно неоднородно и рас­ падается на локальные сходства. Как правило, эти сходства являются статисти­ чески достоверными, т.е. имеют достаточно низкое значение Р-значения (Раіие) для заданных длин последовательностей и распределения вероятностей .

Большинство статистически достоверных сходств коллинеарны, т.е. проекции на оба сравниваемых генома расположены в одинаковом порядке. Это объясняется тем, что основные эволюционные события (замена нуклеотнда, удаление/вставка фрагмента) не нарушают коллинеарности. Возможные нарушения коллинеарно­ сти (конфликты между сходствами, см. рис. 4.1.1), связаны с более редкими эволюционными событиями .

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

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

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

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

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

–  –  –

• А:

Аі / Последовательность U Mus musculus Рис. 4.1.1. Матрица сходств (dot- Рис. 4.1.2. Сравнение синтенных matrix), на которой показаны различные участков последовательностей мыши вида конфликтов между локальными сход­ (AF139987) и человека (AF045555). Наибо­ ствами. а) Неустранимый конфликт: сход­ лее сильное сходство Н - это ортологичное ные фрагменты на разных последователь­ сходство, представляющее экзон 10 локусе ностях расположены в разном порядке. Ь) Rfc2 (нуклеотиды 104514-104583 по после­ Неустранимый конфликт: проекции сходств довательности мыши). Каждое из коллине­ на последовательность U существенно пе­ арных между собой сходств А}, Л2 и А} не рекрываются. с) Есть незначительное пере­ является ортологичным. Однако их общий крытие проекций сходств на последова­ вес выше, чем вес сходства Н тельность U В этом случае конфликт может быть разрешен путем обрезания концов сходств Цепь локальных сходств, построенную исходя из сформулированных вы­ ше принципов, будем называть остовной (backbone) цепью. М ы полагаем (см .

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

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

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

Определение 4.1.1.

Р-зиачеиием сходства Я между последовательностями U и V называется вероятность того, что независимые случайные последователь­ ности длин \U\, | \ имеют локальное сходства веса не менее Score(H):

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

Цепь локальных сходств F в последовательностях [/, V называется рдостоверноіі, если каждое, входящее в F сходство/7-достоверно в F .

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

Построение/і-остовной цепи для последовательностей U, V выполняется

–  –  –

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

Описанный алгоритм дважды использует парадигму жадных алгоритмов .

Во-первых, описанная иерархическая (рекурсивная) процедура является жадной

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

Время работы описанного алгоритма оценивается величиной O(Z) + OfNlogN) + TimesaLoc, где Z - количество сходств в остовной цепи, N - общее ко­ личество локальных сходств, рассмотренных в ходе работы алгоритма, Тіте$еа,ос

- общее время построения локальных сходств. При обычно используемых малых значения параметрар (р 0.01) значение N = к Т, где к мало .

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

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

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

Практически все используемые в настоящее время алгоритмы поиска ло­ кальных сходств основаны на фильтрации пространства поиска с помощью предварительного выделения т.н. затравочных сходств. Приведенные ниже оп­ ределения обобщают определения из работ [Ма, В., Tromp, J, and Li, M. PatternHunter: 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.] H др .

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

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

Пусть л - затравка. Назовем слова w', w'' я-эквивалентными, если И'С(, и") е і О (, и ' " ) е л ) .

Очевидно, множество С(ж, ) всех слов w, образующих с данным словом затравочное сходство в смысле затравки я, есть объединение классов Ti­ ll эквивалентности. На этом наблюдении основан стандартный способ поиска за­ травочных сходств для данных последовательностей v, w.. Он состоит из двух этапов .

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

2. Поиск. Просматриваем последовательность w слева направо. Чтобы найти все фрагменты последовательности, образующие затравочное сходство с очередным фрагментом wfx, x+dj, достаточно просмотреть индексные списки для всех классов я -эквивалентности Z таких, что ZQ С(К, wfx, x+d) .

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

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

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

выше) .

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

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

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

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

Вычисление чувствительности затравки означает вычисление вероятности (в рамках заданной вероятностной модели) того, что случайное выравнивание из заданного множества целевых выравнивании содержит подвыравшівание, при­ надлежащее затравке. Алгоритмы вычисления чувствительности затравок рас­ смотрены в разделе 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. PatternHunter: Faster and More Sensitive Homology Search // Bioinformatics. 2002. V. 18. P .

440-445]. Неформально говоря, разреженная затравка, как и классическая за­ травка, требует наличия нескольких совпадений, но расположенных не подряд, а по описанной в затравке схеме. Более формально разреженные затравки описы­ ваются следующими определениями .

Определение 4.2.3. Разреженным термом Е называется список положи­ тельных целых чисел {pt,...,pj таких, что р;...pj \ipt=l. Размером терма Е называется величина spati(E) =pj; весом терма называется число weight(E) = d .

Отметим, что вес разреженной затравки напрямую связан с ее избирательно­ стью .

Терм Е ={pi,...,Pd} часто для наглядности представляют словом tE длины р! в двухбуквенном алфавите {#, -} таким, что ІЕ[і] = '#' & is {pi,...,Pd}- Сим­ вол '-' называют джокером .

Определение 4.2.5. Пусть G = безделеционное выравнивание слов и w; E ={рі, • ••,Pd} - разреженный терм. Выравнивание G соответствует терму Е, если 1)|!=И=^;

2) VJ е{1,...d}(v[k+Pj+l]=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, где г = [d/2],если=/, г = [ d/З], если к 1, где [х] - ближайшее целое к числу х и [п+1/2] = п .

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

1035-1044] .

Пример 4.2 .

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

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

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

Для произвольной разреженной затравки Е каждый класс С(Е, ) состоит ровно из одного класса іГ-эквивалентностн (говорят, что разреженные затравки допускают однозначное индексирование), что упрощает поиск соответствующих затравочных сходств. Возможность однозначного индексирования для разре­ женных затравок связана с тем, что эти затравки различают только два вида от­ ношений между символами - совпадение и несовпадение. В [Brejova В., Brown, D., Vinar T. Vector seeds: an extension to spaced seeds allows substantial improve­ ments 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) может состоять из десятков классов ^-эквивалентности, что усложняет как поиск, так и индексігровашіе .

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

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

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

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

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

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

Определение. 4.3.1. Классификационная затравка - это слово в некотором классификационном алфавите В. Затравка я = bj...bm e 5 m допускает фрагмент выравнивания а/...а„, е(ПхП/", если /е {7,..., да/ a, g b,. Размером span(iz) за­ травки ж называется ее длина т, #-весом - количество sharp(it) букв '#' среди bh • -, b,„ Определение. 4.3.2. Назовем буквы х, у еПхП эквивалентными относи­ тельно алфавита В ^-эквивалентными), если УЬеВ (хе 77ь = уе 77ь) .

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

Пример 4.3 .

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

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

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

Пусть на 77 задано распределение вероятностей В: 77 - [0,1], где

–  –  –

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

Утверждение 4.3.3.

Пусть к = b]...bm еВ'" - классификационная затравка длины т, w - количество символов І в і г и Sx = A, Q, qo, QF, У/:

- классифика­ ционный автомат затравки ж. Тогда количество состояний автомата Sx не пре­ восходит (w+l)'2'"'w .

Эта оценка не улучшаема, что показывает следующее Утверждение 4.3.4. Пусть А = {#, -} и я = #-г# (между символами # распо­ ложено г джокеров). Тогда классификационный автомат Sx неприводим, т.е .

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

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

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

Таблица 4.3 .

1 представляет данные о среднем количестве состояний клас­ сификационного автомата соответственно для разреженных и классификацион­ ных затравок из примера 4.3.1. Для каждого веса w было подсчитано среднее количество состояний у автомата Ахо-Корасика (столбцы «Ахо-Корасик») и классификационного автомата, описанного в разделе 4.2.4 (столбцы «Классиф .

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

В главах 2-4 представлены алгоритмы построения парного выравнивания биологических последовательностей, ориентированные на широкий спектр по­ становок задач. Большинство из этих алгоритмов основано на методе динамиче­ ского программирования. Как известно (см. [Finkelstein, A.V. and Roytberg, M.A .

Computation of biopolymers: a general approach to different problems. // BioSystems .

1993. Vol. 30, P.l-19.]), динамическое программирование, наряду с построением оптимальных объектов, позволяет решать, в определенном смысле, двойствен­ ную задачу. Это задача вычисления т.н. обобщенных статистических сумм, ко­ торые характеризуют множество допустимых объектов в целом. Более формаль­ но, речь идет о следующей задаче .

–  –  –

146.3 9 345.9 3.1 1.3 113.2 16.0 167.6 1900.7 1.4 119.0 10 380.9 3.2 155.1 120.6 2104.0 16.5 177.9 1.4 127.5 1.3 11 415.4 3.3 163.8 1.3 127.6 17.0 188.1 136.0 2306.3 1.4 17.4 12 449.5 3.3 172.4 1.3 134.9 2507.9 198.1 144.0 1.4 13 180.9 17.8 483.3 3.4 1.3 141.8 2709.0 208.1 152.3 1.4 Дан конечный ациклический ориентированный граф G.RJW простоты бу­ дем считать, что у графа G один источник А и один сток Z Полным путем в гра­ фе G называется путь из источника в сток. Ребра графа помечены элементами множества R, на котором определены две ассоциативные операции - «сложение»

(обозначается Ф ) и «умножение» (обозначается ® ), обладающие следующими свойствами:

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

хе М (0 Ф х) =*; хе М (1 ® х) = х;

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

х, ye М(у Фх "X Фу);

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

х, у, ze М ( (х ©у) ®z = (x®z) ® iy®z)) ;

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

Обобщенной статистической суммой (ОСС) графа G называется «сумма»

(относительно операции ©) весов всех его полных путей .

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

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

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

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

Множество 6'с А'", вероятность которого требуется найти - конечное, и, следовательно, допускается конечным детерминированным автоматом К с не более, чем m\S\ состояниями. Специальные случаи построения такого автомата К, распознающего множество S рассматриваются ниже. «Конечно-автоматность»

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

Определение 5.1.1. Пусть А - алфавит. Конечно-автоматный генератор ве­ роятностей над алфавитом А - это четверка G= Q, q, А, р, где Q - множество состояний; q°- начальное состояние; А - алфавит, р: Q x A x Q - [0, 1] - функ­ ция генерации вероятностей такая, что Vq e Q X ^Q^tp(q, a,q') = 1 .

Переходом в G называется тройка е =q,a,q' такая, чтоp(q, a, q') 0. Бу­ ква а называется меткой перехода и обозначается label(e). Состояния q и q' на­ зываются соответственно начальным и конечным состоянием перехода и обо­ значаются соответственно starlfe), end(e). Меткой пути Р = (еь..., ej в G назы­ вается слово label(ej)...label(e„) .

Генератор G называется детерминированным, если для любой пары q Q, а =А есть не более одного перехода вида q,a,q' .

Путь Р называется инициальным, если его начальное состояние - это со­ стояние q° генератора G. Вероятностью р(Р) пути Р = (eh..., е„) называется произведение/(?,/ = П^х йр(ві). Вероятностью слова w относительно генератора G называется величина Pa(w), равная сумме вероятностей всех инициальных пу­ тей с меткой w. Вероятностью конечного набора слов (языка) L с А* называется сумма PG(L) вероятностей всех слов w ~ L. Очевидно, для любого п выполнено Ра(А") = 1 .

Традиционно используемые способы задания распределений вероятностей могут быть переформулированы в терминах конечно-автоматных генераторов вероятностей. Бернуллиевское распределение описывается генератором с одним состоянием. В случае Марковских распределений порядка k вероятность очередного символа зависит от к предшествующих символов. Такое распределение может быть описано детерминированным генератором с не более, чем \А \ со­ стояниями; эти состояния соответствуют словам длины менее к в алфавите А Пусть даны КДА К = Qa q°K, $f& А, рК, - распознающий язык S и ко­ нечно-автоматный генератор G= Qa, q°G, A Pa, задающий распределение ве­ роятностей р на А'". Вычисление вероятности PQ(L) сводится к вычислению ОСС для графа т.н. вероятностного распознающего автомата (ВР-автомата), который строится как декартово произведение К л G. Говоря неформально, ВР-автомат это недетерминированный конечно-автоматный генератор вероятностей, в кото­ ром выделено подмножество допускающих состояний .

Определение 5.1.6. Пусть К = QK, qK°, (f к, A, f - детерминированный конечный автомат без выхода; G= QG, q°G. A, p • конечно-автоматный генера­ тор вероятностей над алфавитом А. ВР-автомат W = KxG - это пятерка W= = б к 4°w, fw, Л,, р„ где Q„- = QKxQG; q°w = q"Kxq°G ;

(fw= {k, ge = QKxQG | ke (fK};

p№{k, g, a, k\ g') = p(g, a, g'), если p(k,. a) = k';

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

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

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

2. Автомат Wимеет I ^ G I ' I & I состояний и для каждой пары, состоящей из состояния q автомата W и символа а е А есть не более \Qc\ исходящих из q ре­ бер .

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

Утверждение 5.1.4. Рассмотрим алфавит/1 и конечное множество L с А"' .

Пусть К = Qb q K, Q^K, А", ірк - КДА, распознающий множество L и G= 0G, q о, A, PQ - конечно-автоматный генератор, задающий распределение вероят­ ностей р на Ат. Тогда вероятность PG(L) множества L относительно распределе­ ния pG может быть найдена за время 0 ( ] 6 G I * * I & I ' M ^ c использованием памяти 0(16GI'I?A:IA Если генератор G детерминированный, то для времени работы ал­ горитма верна оценка 0(\QG\'\QK\'\A[) .

Следствие 1. Пусть распределение вероятностей на множестве А'" - бернуллневское. Тогда для времени и памяти вычисления вероятности PG(L) верны оценки TimeBcr„ 0(]QK\-\A\) и SpaceBen0(\QK\) Следствие 2. Пусть распределение вероятностей на множестве А'" - это Марковское распределение порядка г. Тогда для времени и памяти вычисления вероятности PG(L) верны оценки Time\tarllm, 0(\QK\'\A'*'\) И 5рясеЛЛи*0 0(\QK\-\AT\) Утверждение 5.1.6. Рассмотрим алфавите и конечное множество L с:А"' .

Пусть В = QB, q°B, Qfв, А, срв - автомат, распознающий множество L' такое, что L'D A" = L и G= QG, q G, A, pG - конечно-автоматный генератор, задаю­ щий распределение вероятностей р на Ат. Тогда вероятность PP(L) множества L относительно распределения р может быть найдена за время 0((\QB\%\QG\*'\A\'M) С использованием памяти 0(}QS\'\QG\)- В случае детермини­ рованного генератора G время работы равно 0((\QB\'[QG\'\A\'m) .

Следствие 1. Пусть распределение вероятностей на множестве Ат - Бернуллиевское. Тогда для времени и памяти вычисления вероятности PG(L) верны оценки TimeBem 0(\QB\'\A\-m) n SpaceBem 0(\QB[) Следствие 2. Пусть распределение вероятностей на множестве А'" - это Марковское распределение порядка г. Тогда для времени и памяти вычисления вероятности Pe(L) верны оценки Timeuarkor 0(\QB\'\A' + \'т) и SpaceMmkov 0(\QB\'\A'V Утверждение 5.1.8. Рассмотрим алфавит А и конечное множество L сАт .

Пусть М- конечное множество слов, множество L ' - это множество L' = {w е A \w содержит подслово из М} и при этом выполнено L = A"' nL' .

Пусть далее, В = QB, q"B, (fB, A, (pB - автомат Ахо-Корасик для множе­ ства М, распознающий множество L' и р ~ распределение вероятностей на А'", задаваемое марковской моделью порядка г. Тогда вероятность PP(L) множества L относительно распределения р может быть найдена за время 0((\QB\+\A'])'\A\'m) с использованием памяти 0((\QB\+\Ar[)) .

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

Определение 5.2.1 Через S(TT) а А обозначается множество всех выравни­ ваний, допускаемых затравкой ж. Автоматом затравки ж называется детерми­ нированный конечный автомат без выхода, распознающий множество S(x). Че­ рез Б(ж, т) гАт обозначается множество всех выравниваний, допускаемых за­ травкой ж Будем считать, что вместе с затравкой ж задан и ее автомат В(ж) = QB, qB°, (fB, А, рв. Такой автомат для всех известных классов затравок может быть по­ строен на основе автомата Ахо-Корасик, специальная конструкция автомата для классификационных затравок представлена в п.4.3.4. Из результатов раздела 5.1 вытекают следующие утверждения .

Утверждение 5.2.1.Пусть А - алфавит выравниваний, 6= Qc, q а А, ра конечно-автоматный генератор, задающий распределение вероятностей р на Ат;

к - затравка и В (ж) = QB, qB°, (fa, А, (рв - автомат затравки %. Тогда чув­ ствительность Sens(n, т) затравки к относительно множества выравниваний А'" может быть найдена методом динамического программігрования за время 0(\QG\'*\QB\W\A\) с использованием памяти 0(\0G\'\QB\). Если автомат В (л) детерминированный, то время работы равно 0(\Qc\'\QB\'in'\A\) .

Следствие 1. Пусть распределение вероятностей на множестве А"' - бернуллиевское. Тогда для времени и памяти вычисления чувствительности SCIIS(K,

т) верны оценки ТітеБег„ 0(\QB\'m \А\) и SpaceBem 0(\QB\*m) Следствие 2. Пусть распределение вероятностей на множестве Ат ~ это Марковское распределение вероятностен р порядка г. Тогда для времени и па­ мяти вычисления вероятности PQ(L) верны оценки TimeMarkmS 0(\QB\'m '\A'*J[) и SpacMarkor0(]QB\'m \Ar\) Утверждение 5.2.3.Пусть к - затравка в алфавите последовательностей П, А - алфавит выравниваніш, согласованный с затравкой я н автомат B(n) = QB, Чв, Q в. А, (рв является автоматом Ахо-Корасик. Пусть далее на множестве Ат задано Марковское распределение вероятностей р порядка г. Тогда чувстви­ тельность Sensfn, m, р) затравки я относительно множества выравниваний А"' и распределения р может быть найдена методом динамического программирова­ ния за время 0((\QB\+\A'])'\A\vn) с использованием памяти 0(1(1{?ЙІ + Й ' Р Л В разделе 5.3 приведен еще один пример приложения техники, описанной в разделе 5.1, - вычисление значимости найденного кластера регуляторных сай­ тов. Факторы регуляции транскрипции (ФРТ) связываются с фрагментами ДНК, содержащими специфичную для данного фактора последовательность нуклеотидов. Как правило, все последовательности, с которыми может связываться дан­ ный ФРТ имеют одну и туже длину. Множество таких последовательностей на­ зывается мотивом связывания ФРТ. В геноме область связывания ФРТ распо­ ложена перед регулируемым геном и называется цнс-регуляторным модулем (ЦРМ). В последние годы было показано, что регуляция транскрипции с помо­ щью ФРТ носит кумулятивный характер: в регуляции может участвовать не­ сколько ФРТ, причем для каждого из них может быть несколько потенциальных мест связывания (вхождений соответствующих мотивов). Существующие про­ граммы распознавания ЦРМ основаны на поиске фрагментов генома, в котором перепредствлены соответствующие мотивы. Для практического использования этих программ необходимы средства оценки значимости полученных результа­ тов. Формально задача может быть поставлена следующим образом .

Фиксируем алфавит ДНК Д={а, с, g, t}. Как и в разделе 5.2, будем считать, что на А™ (здесьда- длина предполагаемого ЦРМ) есть распределение вероятно­ стей р, которое задается конечно-автоматным генератором G= QG, Я°С, А, рG .

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

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

Определение 5.3.2. Пусть М- мотив длины t, D е Д" - последовательность ДНК длины т; т t. Вхождение мотива М в последовательность D - это фраг­ мент Dfx, x+t-IJ такой, что Dfx, x+t-lf е М .

Пусть Dfxj, Xi+trtf - вхождение мотива Mt и Dfx2, x2+t2-I] - вхождение мотива М2. Эти вхождения пересекаются, если пересекаются отрезки [xi, Xi+tr l]nD[x2,x2+t2-l] .

Определение 5.3.2. Пусть дан набор М = М\,..., М,, состоящий из 5 мотивов М, длины І(І=1,..., s) и вектор к = kj,..., ks, состоящий из s натуральных чисел kt (i~l,..., s). Пусть D e Д" - последовательность ДНК длины т .

Набор мотивов М имеет к -вхождение в последовательность D, если для каждо­ го / = {1 s} в D есть не менее к, (возможно, пересекающихся) вхождений мо­ тива Мі .

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

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

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

В качестве меры достоверности потенциального ЦРМ длины т, содержа­ щего кі вхождений мотива Mt (i=l,..., s) при заданном распределении вероятно­ стей р на Д" используется величина PP(F(M, к, т)), где М= Mt,..., Ms и к = кі,..., к,. С помощью техники, описанной в п. 5.1, вычисление этой вероят­ ности можно свести к вычислению обобщенной статистической суммы и, следо­ вательно, найти искомую вероятность алгоритмом, основанным на методе дина­ мического программирования .

Приведенные ниже утверждения дают оценки сложности этого алгоритма для различных вариантов задания распределения вероятностей р. Во всех этих оценках в качестве параметра фигурирует количество \Qc\ состояний автомата Ахо-Корасика С для множества М0 = MiU...uMs. В цитированной выше работе Ахо и Корасик показано, что \Qc\ L(M), (5.3.1) где L(M) — суммарная длина всех слов из множества М0. В приведенных ниже ут­ верждениях фигурирует величина \Qc\, а не более естественная величина посколь­ ку, как показано в разделе 4.3, оценка (5.3.1) недостаточно точна .

Утверждение 5.3.3. Пусть М = А/;,..., Ms - набор мотивов в алфавите А; к =- к!,..., ks - вектор с натуральными компонентами, С = Qc, fa (fa А, (рс - автомат Ахо-Корасик для множества М0 = M/U... uMs и G= Qo, q°G, A, Ра - конечно-автоматный генератор, задающий распределение вероятностей р на Л .

Тогда вероятность Pp(F(M, к, т)) множества F(M, к, т) относительно рас­ пределения р может быть найдена методом динамического программирования за время 0((]Qc\'k] «... 'ks'ni'\Qfjf'\A\) с использованием памяти 0(]Qc\'kj «... "ks •\Qa\). Если генератор G - детерминированный, то оценка времени может быть понижена до Of(\Qc\'k]«... •k1,m,\QG\,\A\) Следствие. Пусть распределение вероятностей на множестве А'" - Бернуллиевское. Тогда для времени и памяти вычисления вероятности PP(F(M, к, т)) верны оценки TumB,r„0((\Qc\'ki«... 'ks'm'\A\) иSpace Bem 0(\Qc\'h •... -ks) .

Утверждение 5.3.5. Пусть М = М,,.... Ms - набор мотивов в алфавите А; к == к],..., ks - вектор с натуральными компонентами, С = Qc, с. ?

(fc, А, рс - автомат Ахо-Корасик для множества М0 = MiU... uMs. яр- рас­ пределение вероятностей на Ат, задаваемое марковской моделью порядка г .

Тогда вероятность Pp(F(M, к, т)) множества F(M, к, т) относительно рас­ пределения р может быть найдена методом динамического программирования за время 0( (\Qc\'ki «... 'к,+ \А\Г) п'\А\) с использованием памяти 0(\Qc\'ki *.. .

-ks+\A\r) Основные результаты

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

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

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

4. Предложен алгоритм предсказания внутренних петель при построении оптимальной вторичной структуры РНК с временной сложностью 0(P*log2n), где Р - количество потенциальных спариваний нуклеотидов, п - длина последо­ вательности РНК. Предложен алгоритм построения оптимального выравнивания последовательностей РНК с заданной вторичной структурой относительно аф­ финных штрафов за делеции с временной сложностью 0(m"nlog (nj), где т, п длины сравниваемых последовательностей .

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

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

1. Roytberg М.А. 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, Provi­ dence. 1992. P. 103-117 .

3. Beridze Т., 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 dy­ namic 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., Astakhova 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 Scien­ tific Publ. Co. 1995. P. 173-183 .

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

9. Nazipova N.N., Shabalma 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 .

lO.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. Ронтберг М.А., Астахова Т.В., Гельфанд М.С. Алгоритм высокоспецифнчного распознавания белок-кодирующих областей в пос­ ледовательностях высших эукариот // Молекулярная биология. 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 ex­ periments//Bioinformatics. 1998. Vol.1, N. 14. P. 14-19 .

14. Mironov A.A., Roytberg M.A. Pevzner P.A., Gelfand M.S. Performance guar­ antee gene predictions via spliced alignment //Genomics. 1998. Vol. 51, P. 332Ройтберг 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 segmen­ tation 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. 11. P. 1065-1066 .

19.Kister A.E, Roytberg M.A, Chothia C, Gelfand I.M.' The sequence determi­ nants 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 hierarchi­ cal 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 to­ ward 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 sensi­ tivity and its application to subset seeds //Journal of Bioinformatics and Com­ putational 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 Science+Business Media. 2006. P. 3-10 .

27.0gurtsov, 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. Литвинов И.И., Лобанов М.Ю., Миронов A.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-I087 .

30.Asthana S., Roytberg M., Stamatoyannopoulos J., Sunyaev S. Analysis of se­ quence conservation at nucleotide resolution // PLoS Comput Biol. 2007. V. 3, N12. P. 254 .

ЗІ.Воеа V, Clement J, Regnier M, Roytberg MA, Makeev VJ. Exact p-value cal­ culation for heterotypic clusters of regulatory motifs and its application in com­ putational 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 .

ЗЗ.Поляновский, В.О., Ройтберг, М.А., Туманян, В.Г. Новый подход к оценке достоверности выявления вставок-делеций в парном выравнивании // Био­ физика. 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.Ройтоерг М.А. Вычисление вероятностей семейств биологических после­ довательностей // Биофизика. 2009. Т.54. № 5. С. 718-724

–  –  –

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

Формат 60x90/16 Объём 2,7 п.д .

Тираж 100 экз .

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

ИНН/КПП 7728572912V772801001 Адрес: 119333, г. Москва, Университетский проспект, д. 6, кор. 3 .

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

http://www.univerprint.ru




Похожие работы:

«1С • ггп: МАЛЫШЕВА Зинаида Георгиевна ЭКОЛОГО-БИОЛОГИЧЕСКОЕ ОБОСНОВАНИЕ ТЕХНОЛОГИИ ПОДГОТОВКИ СЕМЯН ОРЕХОПЛОДНЫХ ПОРОД к ПОСЕВУ (на примере Ростовской области) П.00.11 Охрана окрз^ающей среды и рациональное использо­ вание природных ресурсов 06.03.01 Лесные культуры, селекция и семеноводство АВТОРЕФЕРАТ диссертаци...»

«1. Цель изучения дисциплины "Биология". Цель освоения учебной дисциплины "Биология" для студентов специальности "Лечебное дело" состоит в формировании важнейших фундаментальных, системных знаний об уровневом пр...»

«Экосистемы. 2016. Вып. 8. С. 59–62 УДК 502.75 ДИНАМИКА ВОЗРАСТНОЙ СТРУКТУРЫ ПРОСТРЕЛА ЛУГОВОГО (PULSATILLA PRATENSIS MILL.) В БАЛАШОВСКОМ РАЙОНЕ САРАТОВСКОЙ ОБЛАСТИ Шаповалова А. А. Балашовский институт Саратовского национального государст...»

«ШОРИНА Марина  Владимировна АККУМУЛЯЦИЯ КАДАВЕРИНА И ЕГО ФИЗИОЛОГИЧЕСКАЯ РОЛЬ ПРИ ДЕЙСТВИИ СОЛЕВОГО СТРЕССА 03.00.12 - "физиология и биохимия растений" АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата биологических наук Москва - 2005 Работ...»

«Ископаемые водоросли УДК 551.77:561.26(265.2) В.С. ПУШКАРЬ1,3, М.В. ЧЕРЕПАНОВА2, О.Ю. ЛИХАЧЕВА1 Дальневосточный геологический ин-т ДВО РАН, пр. 100-летия Владивостока, 159, Владивосток 690022, Россия Биолого-почвенный ин-т ДВО РАН, пр. 100-летия Владивостока, 159, Владивосток...»

«БЕЛЕВИЧ Ольга Эдуардовна СТРЕКОЗЫ РОДА AESHNA (ODONATA, ANISOPTERA) ПАЛЕАРКТИКИ Специальность  03.00.09 - энтомология АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата биологических  наук Новосибирск - 2005 Работа выполнена в лаборатории Экологии насекомых Института систематики и экологии животных Сибирского отделения РАН доктор биолог...»

«СИМОНЯН Алина Руслановна НОВЫЕ ГИДРОКСИЛАМИНСОДЕРЖАЩИЕ АНАЛОГИ АГМАТИНА И БИОГЕННЫХ ПОЛИАМИНОВ 03.00.03 Молекулярная биология 02.00.10 Биоорганическая химия Автореферат диссертации на соискание ученой степени кандидата химических наук Москва 2008 Работа выполнена в Лаборатории молекулярных основ действия физиологически активных соедин...»

«Жамурина Надеязда Алексеевна ПОПУНЯЦИОННАЯ ИЗМЕНЧИВОСТЬ ДИК0РАСТУ1ДИХ ВИДОВ POPULUSL. НА ТЕРРИТОРИИ ОРЕНБУРГСКОГО ПРИУРАЛЬЯ 03.00.05.-ботаника АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата биологических н^к V V. Оренбург, 2006 Работа выполнена в ФГОУ ВПО "...»

«БЕСКОВ Артем Александрович ВАРИАНТЫ  СТРОЕНИЯ  СПЕРМАТОЗОИДОВ  ЧЕЛОВЕКА В НОРМЕ И ПРИ ПАТОЛОГИИ, КРИТЕРИИ ПРОГНОЗИРОВАНИЯ УСПЕШНОСТИ ЭКСТРАКОРПОРАЛЬНОГО  ОПЛОДОТВОРЕНИЯ И ДИФФЕРЕНЦИРОВАННОГО ПОДХОДА К ДИАГНОСТИКЕ  И ЛЕЧЕНИЮ  МУЖСКОГО БЕСПЛОДИЯ 03.00.25  -  гистология, цитология, клеточная биология АВТОРЕФЕРАТ диссе...»

«КАШУТИНА ЕЛЕНА  ВАНОВНА И КОМПЬЮТЕРНАЯ ТОМОГРАФИЯ В ПЕРВИЧНОЙ ДИАГНОСТИКЕ ЦЕНТРАЛЬНОГО РАКА ЛЕГКОГО 14.00.19 -лучевая диагностика, лучевая терапия АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата медицинских наук Москва 2004 Работа  выполнена  в  Московском  научн...»

«ЧЕРЕПАНОВ Геннадий  Олегович ПАНЦИРЬ ЧЕРЕПАХ: ПРОИСХОЖДЕНИЕ  И  РАЗВИТИЕ  В  ОНТОИ  ФИЛОГЕНЕЗЕ 03.00.08-зоология Автореферат диссертации на соискание ученой степени доктора биологических  наук Санкт-Петербу...»

«008674 Изобретение относится к медицине и ветеринарии, в частности, к эмбриологии и может быть использовано для хранения микроскопических биологических объектов. К уникальным единичным микроскопическим биологическим объектам могут быть отнесены единичные...»

«Сценарий внеклассного мероприятия Питание и здоровье Автор: учитель биологии высшей категории Новикова Н.Н. ЦЕЛИ: Пропагандировать здоровый образ жизни; активизировать познавательную деятельность учащихся; заинтересовать учащихся изучением вопросов здоровья; развивать творческие способности; расш...»






 
2018 www.lit.i-docx.ru - «Бесплатная электронная библиотека - различные публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.