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

Поляновский, Валерий Олегович

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

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

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

003454Э12

Поляновский Валерий Олегович

О достоверности процедуры выравнивания первичных структур

биополимеров

Специальность 03.00.03 - Молекулярная биология

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

Москва-2008

003454912

Работа выполнена в Лаборатории биоинформатики и системной биологии Учреждения Российской академии наук Институте молекулярной биологии им. В.А.Энгельгардта

Научный руководитель:

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

Официальные оппоненты:

доктор физико-математических наук В.А. Намиот кандидат физико-математических наук В.Ю. Макеев Ведущая организация:

Институт биомедицинской химии им. В.Н. Ореховича РАМН

Защита состоится. 2008 г. в ,'1.?г. на заседании

Диссертационного совета Д 002.235.001 при Институте молекулярной биологии им. В.А.Энгельгардта РАН по ащзесу: 119991, Москва, ул. Вавилова, 32

С диссертацией можно ознакомиться в библиотеке Института молекулярной биологии им. В.А.Энгельгардта РАН

Автореферат разослан di

Ученый секретарь

Диссертационного совета кандидат химических наук у. ---^А.М. Крицын

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

Актуальность темы

В геноме человека имеется порядка 30 тысяч генов, кодирующих белки. В результате постгранскрипционных процессов число белков увеличивается в 2-3 раза по сравнению с числом кодирующих генов. Есть большое число родственных генов и, соответственно, родственных белков, объединяемых в семейства, некоторые из которых состоят из многих сотен представителей. Например, семейство_иммуноглобулинов, семейства других белков, которые по степени сходства и функциональным свойствам подразделяют на подсемейства. Постоянно возникает необходимость сопоставления полипептидных последовательностей для установления степени родства, выявления наиболее консервативных и потенциально значимых участков. Аналогичные задачи стоят при исследовании родственных белков из разных организмов, находящихся на разных ступенях эволюции. Их решение позволяет устанавливать степень родства, а также скорость эволюции тех или иных белков. Для сравнения родственных полипептидных последовательностей, а также выявления врожденных и соматических мутаций проводится процедура выравнивания.

В последние годы в различных областях медицины исследуется генетический полиморфизм в отдельных локусах генома человека: анализ мутаций при диагностике наследственных заболеваний, определение наследственной предрасположенности к онкологическим заболеваниям, а также диагностика этих заболеваний на ранних стадиях (Заседателев A.C., 2007; Yordan Y., 2007). Аналогичные задачи стоят при исследовании родственных белков из разных организмов, находящихся на разных ступенях эволюции. Их решение позволяет устанавливать степень родства, а также скорость эволюции тех или иных белков, разрешать проблемы молекулярной филогении (Ильин Ю.В., 2007; Крамеров Д.А., 2003,2007).

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

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

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

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

1. На основании существующей модели эволюции аминокислотных последовательностей оценить качество восстанавливаемости истинных выравниваний методом глобального выравнивания; выяснить причины неточного восстановления истинных выравниваний.

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

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

Одним из направлений в изучении выравниваний последовательностей белков является решение вопроса о соответствии алгоритмически полученных выравниваний биологически корректным. Качество алгоритмов выравнивания, то есть соответствие между алгоритмическими и «эталонными» выравниваниями рассматривалось с разных точек зрения, при этом в качестве эталона обычно использовались выравнивания, основанные на сопоставлении пространственных структур, что само по себе не является безусловным критерием. В работе Вингрона и Аргоса (Vingron М. and Argos P., 1990) показана связь между устойчивостью (консервативностью) области оптимального глобального выравнивания во множестве субоптимальных выравниваний и её сходством со структурным выравниванием. Показано, что области оптимального выравнивания, наиболее часто повторяющиеся в субоптимальных выравниваниях, имеют большее сходство со структурным выравниванием. В работе Сюняева с соавторами (Sunyaev S.R. et al., 2004), на основании сравнения структурных выравниваний с локальными алгоритмическими выравниваниями Смита-Ватермана, были сделаны выводы о возможности восстановления структурного выравнивания алгоритмическим в зависимости от степени сходства белков.

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

упрощенная схема внесения делеций (вставки вообще не рассматривались). В представленной работе при генерации тестовых последовательностей мы используем общепринятую в настоящее время модель эволюции, описанную в работах Дэйхофф с соавт. (DayhofFM. et al., 1978), Беннер с соавт.( Benner S.A., et al., 1993), Риз и Пирсон (Reese J.T. and Pearson W.R., 2002), включающую в себя точечные замены, а также вставки и делеции. Это позволяет оценить качество восстанавливаемости истинных выравниваний, провести сравнительный анализ структуры вставок-делеций и замен в алгоритмических и эталонных выравниваниях, выяснить причины неточного восстановления истинных выравниваний вне ошибки, вносимой особенностями той или иной базы данных.

Апробация работы

Материалы по теме работы были представлены на Седьмой Международной Энгельгартовской конференции по молекулярной биологии (Суздаль, 28 нояб.-2 дек. 2004 г.), на Московской Международной конференции по вычислительной молекулярной биологии (МССМВ'05, Москва, 18-21 июля, 2005), на Московской Международной конференции по вычислительной молекулярной биологии (МССМВ'07, Москва, 27-31 июля, 2007), на Шестой Международной конференции "Биоинформатика регуляции и структуры генома" (BGRS'2008, Новосибирск, 22-28 июня, 2008).

Объём и структура диссертации

Диссертационная работа изложена на 20 страницах, содержит п рисунков и 18 таблиц. Работа состоит из четырёх глав и выводов. Глава 1 содержит введение и обзор литературы по теме диссертации. В Главе 2 изложен метод определения качества (достоверности) выравнивания двух аминокислотных последовательностей на примере выравнивания, полученного глобальным алгоритмом. В Главе 3 обсуждаются результаты предложенного метода оценки качества (достоверности) парного выравнивания. Глава 4 содержит сравнительный анализ качества глобального и локального алгоритмов выравнивания двух последовательностей. Список цитированной литературы содержит S6 наименований.

Содержание работы Глава 1. Введение

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

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

2.1. Общее описание процедуры определения качества выравнивания.

Процедура определения качества алгоритма парного выравнивания состояла в

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

2.2. Генерация исходных последовательностей (первые элементы пар").

Исходные последовательности - это случайные последовательности, в

которых каждый символ генерировался датчиком случайных чисел независимо от остальных с некоторой частотой. Распределение частот встречаемости аминокислот было принято соответствующим среднему аминокислотному составу белков, приведенному в работе Дейхофф с соавт (Dayhoff М. et al., 1978). Мы построили два тестовых набора по 10000 последовательностей в каждом, в одном все последовательности имеют длину 200, в другом - 500.

Соответствие полученного распределения частот встречаемости аминокислот заданному распределению оценивалось величиной || ADistr |[ / || Distr ||, где Distr -требуемое распределение частот встречаемости аминокислот, ADistr - разность векторов реально полученного распределения и требуемого распределения,

||Х|| = £ |Х|| - норма числового вектора X = <xi.....х„> - сумма абсолютных величин

его компонентов. Полученное значение ошибки составило соответственно 1.6 и 1.5 % на наборах последовательностей длиной 200 и 500 символов.

2.3. Модифицирование исходных последовательностей ("вторые элементы

пар!

Модифицирование исходных последовательностей состояло из поэтапного внесения делеций, точечных замен (мутаций) и вставок. При этом на основе каждой исходной последовательности мы строили 4 тестовых пары, соответствующих эволюционным расстояниям 60,100, 200, 300 РАМ (РАМ - Point Accepted Mutations - число происшедших точечных замен). Таким образом, было получено 2x4=8 тестовых наборов по 10000 пар последовательностей в каждом.

2.3.1 Делеции и вставки

i) Суммарная длина вставок и делеций

Суммарная длина вставок и делеций D для каждой исходной последовательности полагалась равной

D = L-P(indel)-MS, (1)

где L - длина последовательности;

P(indel) - вероятность возникновения вставки-делеции, которая

согласно работе Беннер с соавт.(Веппег S.A. et al., 1993), вычислялась по

формуле:

P(indel) = 0.0224 - 0.0219- е <-0-<" 168'рам) ( (2)

где РАМ - число, характеризующее эволюционное расстояние между

исходной и измененной последовательностями;

MS - математическое ожидание длины вставки-делеции:

М5 = £ d-l...dmax d- P{5=d}, (3)

где P{5=d} - вероятность возникновения вставки-делеции длиной d, взятое из распределения Ципфа, которое, согласно работе Беннер с соавт., не зависит от значения эволюционного расстояния.

Для каждой пары исходной и модифицированной последовательностей суммарная длина вставок была равной суммарной длине делеций, и равна D/2. U) Внесение делеций

В исходной последовательности длины L, с помощью датчика случайных чисел, исходя из равномерного распределения, выбирался номер элемента последовательности N, 1<N^L, соответствовавший началу делеции; с помощью другого случайного числа из распределения Ципфа выбиралась длина делеции d, 15сЫ5/2). Если d больше чем расстояние от N до конца последовательности или до уже внесенной делеции, или если суммарная длина делеций больше D/2, то попытка игнорировалась. Таким образом, предотвращалось внесение делеций, длина которых не равна значению, полученному из заданного распределения. Процедура повторялась до достижения суммарной длиной делеций значения D/2. Ш) Внесение вставок

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

2.3.2. Точечные замены fмутации-)

Точечные замены вносились после делеций и вставок в неделетированные участки исходной последовательности (вставки также игнорировались). Внесение замен выполнялось с использованием матрицы замен РАМ1. Для каждой буквы исходной последовательности с помощью датчика случайных чисел из соответствующего столбца матрицы выбирается другая буква или та же самая.

Число проходов последовательности равно требуемому значению эволюционного расстояния (60,100,200 или 300 РАМ) для мутированной последовательности.

При тестировании описанной процедуры было получено следующее соответствие средней доли совпадений (%id) числу РАМ.

Таблица 1. Соответствие % id числу РАМ

РАМ 10 50 100 200 300

%id 90 63 43 24 16

что согласуется с данными из работы Дейхофф с соавт (Dayhoff М. et al., 1978).

2.4. Алгоритм выравнивания

В качестве тестируемой процедуры для проведения выравнивания исходных и модифицированных последовательностей была применена программа, реализующая алгоритм динамического программирования для глобального выравнивания двух последовательностей, основанный на максимизации сходства (алгоритм Нидлмана-Вунша), с аффинной функцией штрафов за вставку или делецто. Для определения оптимальной матрицы весов замен и оптимальных штрафов за открытие и продолжение вставки или делеции на тех же тестовых наборах последовательностей было проведено выравнивание с РАМ матрицами, соответствующими эволюционным расстояниям 60, 120, 200 и 300 РАМ и различными значениями штрафов, а также с матрицей РАМ250 и штрафом за открытие вставки-делеции равным 14 и за продолжение равньм 2. Значения сходства алгоритмических выравниваний с истинным выравниваниями (определение мер сходства - см. Глава 2, п. 2.5), полученные со «своими» матрицами и с РАМ250 отличались на ±0.5%. В качестве аффинных штрафов за встаки-делеции мы использовали 14 и 2. Наши эксперименты показали, что в среднем они дают наилучшее качество выравнивания, причем протрыш оптимальному для данной группы штрафу невелик (менее 2%), В качестве матрицы весов замен использовалась матрица РАМ250.

2.5. Определение сходства между алгоритмическим и истинным выравниваниями.

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

Accuracy = I / G - точность алгоритмического выравнивания и

Confidence = I / А - достоверность алгоритмического выравнивания (аналогично

работам Фогт с соавт. (Vogt О. et al., 1995) и Сюняев с соавт. (Sunyaev S.R. et al,,

2004)),

а также Overall_Correctness = 2I/(G + А) - обобщенный показатель сходства

алгоритмического и истинного выравниваний,

где I - число общих сопоставлений "буква-буква" в выравниваниях;

в, А - числа сопоставлений "буква-буква" в истинном и алгоритмическом выравниваниях соответственно.

Глава 3. Результаты оценки качества глобального выравнивания и их

обсуждение

3.1. Точность и достоверность алгоритмических выравниваний.

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

№0 «00 2000 о

(а)

_а

6000 4000 2000 о

(С)

00- 01- 0.2- 0J- 04- 0S- 06- 07. 01- 090.1 02 03 04 03 06 07 01 09 10

Overall Correctness

0.0- 01- 0!. 03- 04- oj. 04- 07. 08- 0901 02 03 04 03 Об 07 08 09 10

Overall Correctness

4000 20CO

(d)

{□РАМ 60

■ РЛМ !W jDPAMJOO

■ РАМ 300

00- 01- 02- 0.3- 04- 03- 06. 0.7- 08- 0» 01 02 OJ 04 03 06 07 08 09 10

Overall Correctness

00- 01- 02- 03- 04- OS- 06- 07. 08- 0 901 02 03 04 0! 06 07 08 09 1 0

Overall Correctness

Рис. 1 Распределения числа пар выровненных последовательностей, отстоящих на расстояние в 60, 100,200 и 300 РАМ, в зависимости от значения меры сходства Overall Correctness (см. п. 2.5) между алгоритмическими и истинными выравниваниями (а, с). Для сравнения приведены распределения сходства случайных выравниваний пар последовательностей, удаленных на то же эволюционное расстояние (b, d). Графики а, Ь соответствуют последовательностям длины 200; с, d - последовательностям длины 500.

Характеристики этих распределений приведены в таблицах 2 и 3. В таблице 2 указаны средние значения точности (Accuracy), достоверности (Confidence) и сводной меры сходства (Overall Correctness) для всех восьми тестовых наборов. Для сравнения приведены средние значения величины Overall Correctness для двух случайных выравниваний из нашего набора, то есть для двух систем вставок-делеций, независимо сгенерированных в соответствии с процедурой, описанной в разделе 2.3.

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

Длина Эвол. расстояние, РАМ %ld Алгоритмические и истинные выравнивания Случайные выравнивания

Accur. Confld. Overall Correcta. Overall Correctn.

200 60 58 0.97 0.97 0 97 0 23

200 100 43 0.95 0.94 0.95 0.19

200 200 24 0 85 Ó.84 0.85 0.17

200 300 16 0.70 0.69 0 70 0.16

500 60 58 0 98 0.98 0.98 0.14

500 100 43 0.96 0 96 0.96 0.11

500 200 24 0.87 0.85 0 87 0 09

500 300 16 0.73 0 72 0 73 0.09

Определения мер сходства см. Глава 2, п. 2.5. Для сравнения приведены средние значения сходства между двумя случайными выравниваниями. Данные приведены для всех восьми тестовых наборов (дайны последовательностей 200 и 500, величина РАМ - 60,100,200, 300). В столбце «%М» приведены средние значения доли совпадений сопоставленных символов в выравниваниях.

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

Длина Эвол. расстояние, РАМ %ld Алгоритмические и истинные выравнивания Случвйные выравнивания

Интервал Максимум Интервал Максимум

200 60 58 0.9..1.0 99.1 0.1..0 2 29.1

200 100 43 0.9,.1.0 89.4 0.1..02 34.2

200 200 24 0 8.09 48 9 0.1..0 2 37.0

200 300 16 0.7..0.8 31.3 0.1..0.2 37.7

500 60 58 0.9 .1 0 100 0 0.1..0.2 40.2

500 100 43 0 9..1.0 99.2 0.0 0.1 50 6

600 200 24 0.8..0.9 61.2 0 0..0.1 62 5

500 300 16 0.7. .0.8 42.0 0.0..0.1 63.7

Графики распределений восстанавливаемости (Оуега11_Соггесй1е5з) для разных тестовых наборов см. Рис.1. Наибольшие значения («Максимум») и диапазоны гистограммы («Интервал»), в которых эти максимумы достигаются. Данные приведены для сравнения алгоритмических выравнивания с истинными и для сравнения двух независимых случайных выравниваний.

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

Как видно из таблицы 2, средние значения восстанавливаемости истинных выравниваний алгоритмическими уменьшаются с увеличением эволюционного расстояния. Так, среднее значение достоверности выравнивания для последовательностей длиной 200 аминокислотных остатков (а. к.), удалённых на расстояние 60 РАМ, составляет 97%; в 300 РАМ - 70%, что намного превышает сходство случайных выравниваний (23% и 16%). Для длины 500 а. к. значения достоверности практически те же, но сходство случайных выравниваний ниже (14% и 9%), чем для длины в 200 а. к.

Значения максимумов распределений восстанавливаемости истинных выравниваний алгоритмическими также монотонно уменьшаются с увеличением эволюционного расстояния. Но если средние значения мало зависят от длины последовательностей, то значения максимумов распределений для последовательностей длины 500 существенно выше, чем для последовательностей длины 200 (см. таблицу 3). Так, при эволюционном расстоянии 300 РАМ разность между значениями максимумов составляет около 30%.

3.2. Сравнение характеристик алгоритмических и истинных выравниваний.

Для получения более полного представления о восстанавливаемости истинных выравниваний алгоритмическими было проведено изучение связи между различными характеристиками алгоритмических и истинных выравниваний при разных длинах последовательностей и эволюционных расстояниях. Мы рассмотрели следующие характеристики: (1) %id - отношение количества совпадений к общему количеству сопоставлений; (2) количество вставок-делеций, (3) среднюю длину вставок-делеций и (4) общую длину вставок-делеций.

На рис.2 представлены распределения отношений указанных характеристик для эволюционных расстояний в 60 и 300 РАМ и длины последовательностей L= 200. Данные для других наборов имеют такой же вид, Средние значения этих величин приведены в таблицах 4 и 5.

Графики А-60 и А-300 практически симметричны, то есть %id алгоритмических выравниваний незначительно отличается от %¡d истинных. Асимметрия распределения отношений средних значений длин и отношений количеств вставок-делеций относительно диагонали графика демонстрирует уменьшение средней длины и числа вставок-делеций в алгоритмических выравниваниях относительно истинных. Именно такие пары последовательностей имеют наибольшее значение несовпадения алгоритмических выравниваний с истинными. Вертикальные полосы на графике распределения отношений средних значений длин вызваны фиксированной суммарной длиной вставок-делеций в истинных выравниваниях; их координаты можно определить по формуле: dcp = D/k,

где D= ins + del - суммарная длина вставок-делеций, k = 1,2,...,D - возможные количества вставок-делеций в истинных выравниваниях.

(Ъ-60)

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8

GS-alignments

0 2 4 6 8 10 12 14 16 ]

GS-aäigimente

0.0 0,1 0.2 0.3 0.4 0.5 (1.6 0.7 0.!

GS-alignments

0.0 2.0 4.0 6.0 8.0 Ю.О 12.0

ГК-alianments

(»300) *

* * i '

л j :

я t 1

я i .

2 4 6 8 10 12 14 16 18

GS-aligmerte

0.0 20 4.0 i0 SO 10.0 12.0

GS-aligpments

Рис. 2 Представление в виде точечных диаграмм различных характеристик алгоритмического и эталонного выравниваний. Каждая точка соответствует одной паре последовательностей; абсцисса равна значению характеристики для эталонного выравнивания; ордината - значению характеристики для алгоритмического выравнивания. Приведены данные для таких характеристик: (а) уровень сходства - %1Й ( отношение количества сопоставлений совпадающих символов к общему числу сопоставлений символов в данном выравнивании); (Ь)общее количество вставок-делеций; (с) средняя длина вставки-делеции для эволюционных расстояний 60 и 300 РАМ.

В таблицах 4а и 46 приведены средние значения характеристик для алгоритмических и истинных выравниваний.

В таблице 5 - средние значения и среднеквадратические отклонения а для отношений значений характеристик алгоритмического и истинного выравнивания, полученных для пар из тестового множества. Как видно из таблицы 5, значения среднеквадратичного отклонения а для всех характеристик возрастают с увеличением эволюционного расстояния (РАМ) и для последовательностей длиной Ь=200 значения а больше, чем длиной Ь=500.

Таблица 4а. Средние значения %id алгоритмических («Алг.») и истинных

Длина РАМ %ld

Алг. Ист. Оти.

200 60 58 58 1.00

200 100 43 43 1.00

200 200 25 24 1 04

200 300 18 16 1.13

500 60 58 58 1 00

600 100 43 43 1.00

500 200 25 24 1.04

500 300 18 16 1.13

Таблица 46. Средние значения характеристик вставок-делеций алгоритмических («Алг.») и истинных («Ист.») выравниваний для разных тестовых наборов_ | __

Длина РАМ Число вставок-делеций Средняя вставок- длина делеций Суммарная длина вставок-делеций

Алг. Ист. Отн. Алг. Ист. Отн. Алг. Ист. о™.

200 60 2.17 2.11 1.03 4.85 5.69 0.85 10 12 0.83

200 100 5.49 6.85 0.80 2.43 2.34 1.04 14 16 0 88

200 200 5 78 7.98 0.72 2.61 2.51 1.04 16 20 0.80

200 300 6.10 8.54 0.71 2 67 2.58 1.04 16 22 0.73

500 60 2.92 2.83 1.03 9 37 10.58 0.89 25 30 0.83

500 100 10.81 12.72 0.85 3.26 3.14 1.04 35 40 0.88

500 200 12.67 16.06 0.79 3 41 3.36 1.02 45 55 0 82

500 300 13 46 16.12 0.84 3.29 3.47 0.95 45 55 0.82

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

Таблица 5. Средние значения отношения %id и средние значения отношений

Длина РАМ Алгоритмическое / Истинное

%ld (А) Число вставок-делеций (В) Сре; дл вста долей ЗИЯЯ >ша вок-ий (С) Суммарная длина вставок-делеций (D)

Средн а Средн С! Средн а Средн а

200 60 0.99 0.02 0.86 0.17 1.02 0.18 0.88 0.19

200 100 0 99 0.03 0.82 0.17 1 03 0 21 0 83 0 20

200 200 1.01 0.06 0.75 0.20 1 03 0.28 0.76 023

200 300 1.11 0.14 0 75 0 25 1 02 0 35 0.74 0.27

500 60 0.99 0.01 0.89 0.11 1.03 0.13 0.92 013

500 100 0.99 0 02 0 86 0.12 1 03 0.15 0 89 0.14

500 200 1.01 0.04 0.81 0.15 1.01 0 20 0.79 0.16

500 300 1.11 0.08 0.87 0.22 0.94 0.23 0 80 019

Дня четырёх характеристик выравниваний: (A) %id, (В) числа вставок-делеций, (С) средней длины и (D) общей длины вставок-делеций:- представлены отношения значения для алгоритмических выравниваний к значению для истинных выравниваний. Д ля каждого из восьми тестовых наборов дано значения отношений характеристик и их среднеквадратичное отклонение о.

Доля совпадающих позиций %id не меняется с длиной последовательности (см. таблицу 4а) и слабо отличается у алгоритмических и истинных выравниваний (для больших значений РАМ у алгоритмических выравниваний %id несколько повышается). С увеличением эволюционного расстояния значение %id, естественно, снижается.

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

3.3 Зависимость качества алгоритмического выравнивания от характеристик вставок-делеций

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

Как видно из таблицы 6а, наибольшее количество пар последовательностей приходится на подмножества ЧМ, в которых число вставок-делеций в алгоритмических выравниваниях меньше, чем в эталонных (70% и 74% от общего числа пар последовательностей для длин 200 и 500 аминокислот), а также на подмножества СДБ, в которых средняя длина вставок-делеций в алгоритмических выравниваниях больше, чем в эталонных (42 и 47% от общего числа пар последовательностей). Кроме того, в таблице 66 представлена зависимость качества алгоритмических выравниваний от соотношения средней длины и числа вставок-делеций в алгоритмических и эталонных выравниваниях. Очевидно, что наибольшее сходство алгоритмических выравниваний с эталонными достигается при равенстве, как средней длины, так и числа вставок-делеций в алгоритмических и эталонных выравниваниях; причем это единственное подмножество пар

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

Таблица ба. Распределение пар последовательностей из тестовых наборов по

подмножествам в зависимости от характеристик вставок-делеций

Характеристики вставок-делеций Описание подмножества Обозначение Подм-ва Число пар в подмн-ве, % от общего числа пар

Длина L=200 Длина L=500

Средняя длина вставок-делеций Алг<Ист СДМ 32 2 38 3

Алг> Ист СДБ 42.1 47.0

Алг= Ист СДР 25.7 14.7

Число вставок-делеций Алг<Ист ЧМ 70.6 74 0

Апг> Ист ЧБ 38 7.4

Алг = Ист ЧР 25 6 18 5

Подмножества всего тестового множества последовательностей, удовлетворяющие следующим условиям: 1) средняя длина вставок-делеций в алгоритмических выравниваниях меньше, чем в истинных (СДМ); 2) средняя длина вставок-делеций в алгоритмических выравниваниях больше, чем а истинных (СДБ); 3) средние длины вставок-делеций в алгоритмических выравниваниях и в истинных равны (СДР); 4) число вставок-делеций в алгоритмических выравниваниях меньше, чем в истинных (ЧМ); 5) число вставок-делеций в алгоритмических выравниваниях больше, чем в истинных (ЧБ); 6) числа вставок-делеций в алгоритмических выравниваниях и в истинных равны (ЧР). Данные величины являются средними для четырех тестовых наборов, соответствующих эволюционным расстояниям в 60,100,200 и 300 РАМ.

Таблица 66. Пересечения подмножеств и качество выравнивания

Описание пересечения подмножеств Размер пересечения, % от обшего числа пар Overall Correctness

Длина L-200 Длина L=500 Длина L=200 Длина L=500

СДМ и ЧМ 25.7 26 7 0.83 0.85

СДМ и ЧБ 34 7.1 0.77 0 80

СДБ и ЧМ 40 9 46 1 0 85 0 89

СДБ И ЧБ 0.4 0.4 0.65 0 71

СДР и ЧР 21.6 13.4 0.97 0.98

Распределение пар последовательностей из тестовых наборов последовательностей длиной 200 и 500 а. к. по пересечениям подмножеств (определение подмножеств см. в Тайл. ба), и Overall Correctness - обобщенный показатель сходства алгоритмического и истинного выравниваний (см. Глава 2, п. 2.5), соответствующее каждому подмножеству.

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

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

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

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

Нашей задачей было определить соотношение качества выравниваний, полученных глобальным и локальным алгоритмами, в зависимости от степени гомологии сходных фрагментов последовательностей («ядра») и длины негомологичных участков по краям последовательностей («консолей»). В частности, определение порога применения глобального алгоритма, то есть тех значений указанных параметров, при которых качество выравнивания глобальным алгоритмом не ниже качества выравнивания локальным алгоритмом (Определение качества выравнивания см. Глава 4, п. 4.2.3).

4.2 Описание метода

Для решения данной задачи была предложена следующая схема.

4.2.1 Получение тестовых наборов пар последовательностей.

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

(ядро). Модель "расходящейся"эволюции.

Каждая тестовая пара последовательностей включает две модифицированных_последовательности, порожденных от общей исходной последовательности и состоит из гомологичного ядра и негомологичных консолей. Гомологичная часть исходной последовательности (ядро) генерируется, как описано в п. 2.2 Главы 2. Длина ядра исходной последовательности составляла 200 а к. Далее, из ядра исходной последовательности СО получались ядра двух модифицированных последовательностей С1 и С2 путем внесения делеций, вставок и замен. Эволюционные расстояния между ядром исходной последовательности СО и ядрами порожденных последовательностей С1 и С2 составляли 30, 60, 120 и 240 РАМ. Для проведения численного эксперимента по определению эволюционного расстояния между порожденными последовательностями было получено 4 тестовых набора по 1000 пар последовательностей, и 4 тестовых набора по 10000 пар последовательностей в каждом (см. Табл. 7).

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

последовательности каждая позиция < проверялась на возникновение вставки или делеции с вероятностью, описанной формулой (2) на основе эволюционной модели примененной ранее в Главе 2, п. 2.3.1 (Benner S.A. et al., 1993 и Reese J.T. and Pearson W.R., 2002). На следующем шаге разыгрывалось возникновение вставки или делеции. Из условия равенства суммарной длины вставок и делеций вероятность возникновения делеции была принята равной 0.55.Длина вставки или делеции выбиралась случайным образом из распределения Ципфа, которое, согласно работе Беннер с соавт., не зависит от значения эволюционного расстояния. Если выбранная длина делеции превышала расстояние от i до конца последовательности или начало делеции приходилось на уже делегированную позицию, то попытка игнорировалась. Также игнорировалась вставка, если ее начало совпадало с продолжением сделанной ранее вставки или делеции. Таким образом, предотвращалось внесение вставок и делеций, длина которых не равна значению, полученному из заданного распределения. Буквенный состав вставок генерировался аналогично исходным последовательностям. В отличие от схемы, примененной в Главе 2, в этом случае суммарная длина вставок-делеций не является постоянной величиной для всех пар последовательностей из одного тестового набора, а подчиняется закону случайных чисел (что ближе к истинной эволюционной картине).

Внесение мутаций производилось согласно п. 2.3.2 Главы 2.

Таблица 7. Характеристики модифицированных последовательностей, полученных по схеме последовательной и расходящейся моделей эволюции

Число пар Последовательная Расходящаяся

послед-тей Эволюция Эволюция

N РАМ Id Indel id PAM(ld) indel PAM(indel)

1000 30 0.7490 0 0334 0.5793 60.55 0.0662 68.56

1000 60 0.5792 0.0543 0.3756 122.25 0.1072 202.14

1000 120 0 3764 0.0747 0 2009 245.08 0.1473 >830PAM

1000 240 0.2020 0 0889 0.1047 473.87 01732 > 830PAM

10000 30 0.7503 0.0333 0.5804 60.31 0.0661 68.30

10000 60 0.5806 0.0519 0.3773 121.53 0.1023 170.52

10000 120 0.3765 0.0759 0.2025 243.45 0.1490 > 830PAM

10000 240 0.2024 0 0908 0.1044 474.83 0.1773 > 830PAM

Здесь: РАМ - эволюционное расстояние между исходной и измененной последовательностями; Ш - отношение числа совпадающих символов к общему числу сопоставленных символов; 1пс1е1 - отношение общей длины вставок-делеций к длине исходной последовательности; РАМ^) - эволюционное расстояние между измененными последовательностями, определенное исходя из значения Ш; РАМ(1пйе1) - эволюционное расстояние между измененными последовательностями, определенное исходя из значения Ме1.

Как и в случае последовательной эволюции, данные о внесенных в исходные последовательности изменениях сохранялись в виде выравниваний А(С0,С1) и А(С0,С2). Для установления эволюционного расстояния между модифицированными последовательностями, на основании этих выравниваний строилось выравнивание последовательностей С1 и С2, таким образом, что

позиции, происходящие от общего предка в СО, сопоставлялись друг другу. Для оценки различия между последовательностями Cl и С2 были определены %id и %indel (см. Табл. 7).

Кроме того, для полученных значений %id и %indel были посчитаны соответствующие значения эволюционного расстояния в единицах РАМ. Как видно из Таблицы 7, значения PAM(id) превышают соответствующие значения РАМ для последовательной эволюции примерно в 2 раза, тогда как PAM(indel) имеет существенно большие значения.

и) Негомологичные участки последовательностей (консоли)

Далее, к началу и к концу вдер последовательностей были присоединены негомологичные консоли, представляющие собой случайные последовательности, полученные датчиком случайных чисел. Суммарная длина консолей каждой последовательности составляла 10, 20, 50, 100 и 200% от длины ядра (200 а. к.), а разница в длинах левой и правой консолей (сдвиг) изменялась от 0 до 100% от их суммарной длины. При этом длина левой консоли первой последовательности равнялась длине правой консоли второй последовательности. Таким образом, для каждого эволюционного расстояния было получено 56 наборов пар последовательностей, отличающихся длиной и сдвигом консолей, по 1000 пар последовательностей в каждом наборе.

4.2.2 Выравнивание последовательностей с консолями,

Выравнивание полученных последовательностей производилось как глобальным, так и локальным вариантами метода Смита-Ватермана. Как и в случае последовательностей без консолей, при выравнивании глобальным алгоритмом применялась матрица весов замен РАМ250 и штрафы 14 и 2 за открытие и продолжение вставки-делеции; при выравнивании локальным алгоритмом применялась матрица Gonnet250 и штрафы 10 и 0.5.

4.2.3 Определение качества алгоритмических выравниваний.

Для оценки качества полученных программой выравниваний последовательностей с консолями применялись меры Accuracy и Confidence, описанные в п. 2.5 Главы 2. Заметим, что при подсчете числа сопоставлений в алгоритмическом выравнивании учитывались только такие столбцы, в которых хотя бы один символ принадлежал гомологичному участку.

4.3 Результаты

Были получены зависимости мер качества глобального и локального выравниваний последовательностей с консолями от следующих величин: 1) эволюционного расстояния между гомологичными фрагментами последовательностей; 2) длины консолей; 3) асимметрии консолей (сдвига «ядра»). В Таблице 8 представлена зависимость значения Accuracy и Confidence от эволюционного расстояния между ядром исходной последовательности и ядрами измененных последовательностей изменяющегося от 30 до 240 РАМ при симметричном расположении ядра и изменении суммарной длины консолей от 0% до 200% от длины гомологичных участков.

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

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

Таблица 8. Характеристики Accuracy я Confidence для глобального и

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

Эвол. расстояние, РАМ Длина консолей, % Глобальное выравнивание, % Локальное выравнивание, %

Accuracy Confidence Accuracy Confidence

30 0 98 98 98 86 9819 98.57

30 10 98.90 98.62 98.23 98.20

30 20 98.77 98.38 98.11 97.95

30 50 98.50 97.88 97 91 97.45

30 100 98 47 97.82 97 91 97 36

30 200 98.40 97.61 97.65 96 93

60 0 95 88 95 42 9319 94 37

60 10 95 89 95.25 93.61 93.91

60 20 95 24 94.38 93 29 93 20

60 50 94.59 93 22 92.92 91.99

60 100 94 65 93 05 92 84 91.46

60 200 94.35 92.77 92.57 91 21

120 0 82.47 81.47 71.76 76 71

120 10 81.13 79.79 71,34 74.18

120 20 79 30 77.69 71 16 72 64

120 50 77.95 75.77 70 51 69 77

120 100 76 70 7411 69.48 67.78

120 200 76.32 73 34 68.69 66.79

240 0 38 86 38.31 1514 19.30

240 10 36.80 35.90 15.50 18 12

240 20 33 06 32.05 14 22 15.71

240 50 30 71 29.46 14 22 14.49

240 100 27.93 26 63 12.79 12 43

240 200 25.33 23 90 9 27 8 88

Здесь «Эволюционное расстояние» обозначает число РАМ между гомологичными участками (ядрами) исходной последовательности и измененных последовательностей; «Длина консолей» - суммарные длины консолей в процентах от длины гомологичных участков.

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

выравнивания происходит при все меньшей длине консолей и все меньшем сдвиге ядра от центра последовательностей.

Эволюционное расстояние ЗОРАМ

Эволюционное расстояние 120РАМ

¡S ™ § во в) ТО S ю 2 40 J „ Console length' 100%

20 40 Ю вО 1 •Shift, % ю

я too

£ so

if 40

а 20

1 С

Console length» 200%

3L,

Л ;

—4—ОЬЛссиг -«-GfciConf. j LclAccur | —*— LcLConf

20 40 Ю

Shift, %

Рис. 3 Зависимость значений Accuracy и Confidence от величины сдвига ядра (определение параметра Shift см. п. 4.2.1 .ii) для глобального и локального выравниваний при длине консолей 100% и 200% от длины ядра.

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

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

Выводы

1. Исследование достоверности алгоритмических выравниваний, проведенное на модельных парах аминокислотных последовательностей в диапазоне эволюционных расстояний от 60 до 300 РАМ показало, что уровень восстанавливаемости истинных выравниваний алгоритмическими существенно зависит от эволюционного расстояния между последовательностями и составляет 97+98% для расстояния 60 РАМ и 70+72% для расстояния 300 РАМ, независимо от длины последовательностей биополимеров.

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

3. Показано, что наиболее выраженной тенденцией в алгоритмическом выравнивании, вызывающей снижение его сходства с истинным, является уменьшенное число вставок-делеций относительно истинного (в «70% выравниваний от общего числа). Тенденция к увеличению средней длины вставок-делеций менее значительна (в 26% от общего числа выравниваний). Наличие именно этих двух тенденций в алгоритмических выравниваниях приводит к наибольшему отличию от истинных выравниваний. Уровень сходства с эталоном этих выравниваний в среднем на 6+9% ниже уровня, достигаемого при равенстве как числа, так и средней длины вставок-делеций в алгоритмическом и истинном выравниваниях, что является ресурсом для улучшения процедуры выравнивания.

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

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

Список работ, опубликованных по теме диссертации:

1. Поляновскнй В.О., Демчук Е.Я., Туманян В.Г. (1994) Эффективность процедуры выравнивания последовательностей в смысле возможности восстановления истинного выравнивания. Молекулярная Биология, 28(6), 1341-1345.

2. Polyanovsky.V.O., Roytberg,M.A., Tumanyan,V.G. (2008) Reconstruction of genuine pair-wise sequence alignment. J. Comput. Biol., 15(4), 379-391.

3. Поляновский B.O., Ройтберг M.A., Туманян В.Г. (2008) Новый подход к оценке достоверности выявления вставок-делеций в парном выравнивании. Биофизика, 53(4), 533-537.

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г Подписано к печати 06.10.2008 г. Формат 60x90 1/16. Усл.печ л. 1,25. Тираж 100 экз Заказ 545. Тел 939-3890. Тел7Факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

Содержание диссертации, кандидата физико-математических наук, Поляновский, Валерий Олегович

СПИСОК ТЕРМИНОВ И СОКРАЩЕНИЙ.

ВВЕДЕНИЕ.

Глава 1. ОБЗОР ЛИТЕРАТУРЫ.

1.1. Основы изменчивости генома.:.

1.2. Сравнение последовательностей и алгоритмы выравнивания.

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

1.4. Выравнивание и расстояние.

1.5. Выравнивание и сходство.

1.6. Вхождение одной последовательности в другую.

1.7. Поиск сходных фрагментов.

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

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

В последние годы в различных областях медицины исследуется генетический полиморфизм в отдельных локусах генома человека: анализ мутаций при диагностике наследственных заболеваний, определение наследственной предрасположенности к онкологическим заболеваниям, а также диагностика этих заболеваний на ранних стадиях (Senchenko et al,2004; Kolchinskiíí, Barskií, Zasedatelev, 2007; Rubina et al., 2008; Amit et al, 2007). Аналогичные задачи стоят при исследовании родственных белков из разных организмов, находящихся на разных ступенях эволюции. Их решение позволяет устанавливать степень родства, а также скорость эволюции тех или иных белков, разрешать проблемы молекулярной филогении (Koonin et al. 2000, Makarova, Kramerov, 2007).

Задача построения алгоритма для осуществления такой процедуры на основе методов динамического программирования была решена разными авторами (Туманян с соавт., 1966; Needleman and Wunsch, 1970; Smith and Waterman, 1981; Поройков с соавт., 1984). Среди наиболее широко используемых алгоритмов выравнивания укажем BLAST (Altschul, et al. 1990), FASTA (Lipman and Pearson, 1985). В последнее время разработан ряд алгоритмов для выравнивания последовательностей, учитывающих специфику вторичных структур белков (Wallqvist et al., 2000; Литвинов с соавт., 2006), а также их пространственных структур (Yang, 2002). При этом важно понимать -насколько алгоритмическое выравнивание, полученное оптимизацией той или иной целевой функции, восстанавливает эволюционное выравнивание аминокислотных последовательностей, т.е. такое выравнивание, в котором сопоставлены те позиции сравниваемых белков, которые происходят от одной и той же позиции их общего предка. Так, например, для построения эволюционных деревьев аминокислотных последовательностей в настоящее время широко применяются методы, основанные на определении расстояния между последовательностями (Saitou and Neil, 1987). Способы измерения расстояния между двумя последовательностями можно отнести к двум классам: 1-й — простым подсчетом доли (процентного содержания) несовпадающих позиций; 2-й — с использованием матриц весов замен аминокислот (Hollich et а1., 2005). При1 применении способов измерения расстояния второго типа необходимо иметь достоверные выравнивания каждой пары последовательностей, расстояние между которыми определяется. Процедура выравнивания, применяемая с целью выявления мутаций и делеций в белках, может иметь первостепенное значение для диагностики и выбора стратегии терапии заболеваний. Таким образом, решение вопроса о биологической корректности алгоритмически полученных выравниваний является актуальной задачей.

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

Заключение Диссертация по теме "Молекулярная биология", Поляновский, Валерий Олегович

выводы

1. Исследование достоверности алгоритмических выравниваний, проведённое на модельных парах аминокислотных последовательностей в диапазоне эволюционных расстояний от 60 до 300 РАМ показало, что уровень восстанавливаемости истинных выравниваний алгоритмическими существенно зависит от эволюционного расстояния между последовательностями и составляет 97-^98% для расстояния 60 РАМ и 70-^-72% для расстояния 300 РАМ, независимо от длины последовательностей биополимеров.

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

3. Показано, что наиболее выраженной тенденцией в алгоритмическом выравнивании, вызывающей снижение его сходства с истинным, является уменьшенное число ' вставок-делеций относительно истинного (в «70% выравниваний от общего числа). Тенденция к увеличению средней длины вставок-делеций менее значительна (в 26% от общего числа выравниваний). Наличие именно этих двух тенденций в алгоритмических выравниваниях приводит к наибольшему отличию от истинных выравниваний. Уровень сходства с эталоном этих выравниваний в среднем на 6-н9% ниже уровня, достигаемого при равенстве как числа, так и средней длины вставок-делеций в алгоритмическом и истинным выравниваниях, что является ресурсом для улучшения процедуры выравнивания.

БЛАГОДАРНОСТИ

Приношу глубокую благодарность моему руководителю Владимиру Гайевичу Туманяну за предложенную тему, постоянное внимание к работе и плодотворное обсуждение полученных результатов. Я благодарен Михаилу Абрамовичу Ройтбергу за участие в оценке результатов и за внесенные им конструктивные предложения по расширению области исследования. Глубоко признателен Наталии Георгиевне Есиповой за моральную поддержку и внимание.

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

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

За последнее время прогресс в области математического анализа биологических последовательностей был обусловлен двумя тенденциями: первая - уточнение формальных постановок задач с целью приблизить их к содержательным биологическим задачам и особенностям изучаемых объектов; вторая - привлечение новых математических идей. В качестве примера такого прогресса в области биологически-адекватного сравнительного анализа последовательностей можно назвать введение понятие частотного профиля семейств последовательностей, разработку методов их построения и использования при поиске родственных последовательностей (Eddy, 1998; Sunyaev et al., 1999; Stark et al. 2003; Finkelstein AV, Roytberg MA., 1993). Как уже было упомянуто, способность алгоритмов выравнивания отражать биологическую специфику последовательностей во многом определяется типом используемой весовой функции (см. комментарий к теореме 3). Выделению класса весовых функций делеций, допускающих построение эффективного алгоритма выравнивания посвящены работы (Myers and Miller, 1988; Ройтберг, 1984), которые могут быть примером привлечения усовершенствованных математических методов.

Предсказанию дальних гомологий структур белков, основаванному на статистической значимости, посвяшено значительное число работ (Bray et al., 2000; John and Sali, 2004; Madden et al.,.2001; Mayr et al., 2007; Mitrophanov and Borodovsky, 2006; Shah et al., 2008).

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

Качество» алгоритмов выравнивания, т.е. соответствие между алгоритмическими и «эталонными» выравниваниями рассматривалось с разных точек зрения. При этом в качестве эталона обычно использовались выравнивания, основанные на сопоставлении пространственных структур, что основано на том соображении, что трехмерные структуры белков более консервативны, чем их последовательности (Doolittle, 1981), хотя это само по себе не является безусловным критерием. В работе Вингрона и Аргоса (Vingron and Argos, 1990) показана связь между устойчивостью (консервативностью) области оптимального глобального выравнивания во множестве субоптимальных выравниваний и её сходством со структурным выравниванием. Показано, что области оптимального выравнивания, наиболее часто повторяющиеся в субоптимальных выравниваниях, имеют большее сходство со структурным выравниванием.

В работах (Mevissen and Vingron, 1996; Schlosshauer and Ohlsson, 2002) оценка достоверности оптимального выравнивания основана на определении достоверности каждой пары сопоставленных аминокислотных остатков, в результате чего строится зависимость «индекса надёжности» (robustness index) от номера выровненной пары остатков. Так, в работе Мевиссена и Вингрона в качестве меры надёжности сопоставления i-ro и j-ro остатков принимается разность весов оптимального выравнивания и выравнивания с наибольшим весом, в котором элементы i и j не сопоставляются. В работе (Schlosshauer and Ohlsson, 2002) мера надёжности сопоставления i-ro и j-ro остатков основана на замещении дискретной функции "шах" в определении алгоритма динамического программирования на непрерывную функцию, зависящую от параметра. Это позволяет оценить наличие субоптимальных конкурентов для данной выровненной пары остатков и, таким образом, получить значение достоверности их сопоставления. Полученный для каждой пары индекс даёт представление о локальной достоверности выравнивания.

В работах Фогт с соавторами (Vogt et al., 1995), Доминик с соавторами (Domingues et al., 2000) и Сюняев с соавторами (Sunyaev et al., 2004.) и на основании сравнения структурных выравниваний с локальными алгоритмическими выравниваниями Смита-Ватермана были сделаны выводы о возможности восстановления структурного выравнивания алгоритмическим в зависимости от степени сходства белков. Кроме того, в работе (Sunyaev et al., 2004.) изучение внутренней структуры тех и других выравниваний позволило создать более эффективную процедуру выравнивания двух последовательностей, учитывающую не только средний уровень их идентичности, но и распределение более или менее совпадающих участков последовательностей в структурном выравнивании.

Недостатком всех цитированных работ является то, что алгоритмические выравнивания сравнивались не с истинным эволюционным выравниванием, которое неизвестно, а с его приближением, что вносит в результаты погрешность, величина которой не поддается оценке. Мы предлагаем для оценки качества алгоритмов сравнивать искусственно сгенерированные последовательности, для которых истинное выравнивание известно «по построению». Подобный численный эксперимент был осуществлен (Polyanovskii, et al., 1995), однако, построение тестового набора последовательностей не отражало в полной мере имеющихся данных об эволюционном процессе, поскольку применялась упрощенная схема внесения делеций (вставки вообще не рассматривались). Впоследствии при генерации тестовых последовательностей нами была использована общепринятая в настоящее время модель эволюции, описанная в (Dayhoff et al. 1978; Benner et al., 1993; Reese, et al., 2002), которая включала в себя точечные замены, а также вставки и делеции. Проведён сравнительный анализ структуры вставок-делеций и замен в алгоритмических и эталонных выравниваниях. Анализ показал, что различия между алгоритмическими и эталонными выравниваниями, в основном, проявляются в различии в количестве и средних длинах вставок-делеций. Получены численные значения средней достоверности метода глобального выравнивания с аффинными штрафами за делеции (глобальный вариант метода Смита-Ватермана) для эволюционных расстояний от 60 до 300 РАМ. Эти значения существенно выше, чем соответствующие значения для локального варианта метода Смита-Ватермана. Таким образом, появляется возможность альтернативной оценки качества выравнивания, вне зависимости от информации о пространственной структуре.

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

Глава 2. МЕТОД ОЦЕНКИ КАЧЕСТВА ГЛОБАЛЬНОГО ВЫРАВНИВАНИЯ ДВУХ АМИНОКИСЛОТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

2.1. Общее описание процедуры определения качества выравнивания

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

2.2. Генерация исходных последовательностей первые элементы пар)

Исходные последовательности - это случайные последовательности, в которых каждый символ генерировался датчиком случайных чисел независимо от остальных с некоторой частотой. Распределение частот встречаемости аминокислот было принято соответствующим среднему аминокислотному составу белков, приведенному в работе Дейхофф с соавт (Dayhoff М. е! а1., 1978). Мы построили два тестовых набора по 10000 последовательностей в каждом, в одном все последовательности имеют длину 200, в другом - 500. Соответствие полученного распределения частот встречаемости аминокислот заданному распределению оценивалось величиной || АБ151г || / || Б1з1х ||, где

- требуемое распределение частот встречаемости аминокислот, ADistr -разность векторов реально полученного распределения и требуемого распределения,

Х|| = Е |Xj| - норма числового вектора X = <xi, ., хп> - сумма абсолютных величин его компонентов. Полученное значение ошибки составило соответственно 1.6 и 1.5 % на наборах последовательностей длиной 200 и 500 символов.

2.3. Модифицирование исходных последовательностей вторые элементы пар)

Модифицирование исходных последовательностей состояло из поэтапного внесения делеций, точечных замен (мутаций) и вставок. При этом на основе каждой исходной последовательности мы строили 4 тестовых пары, соответствующих эволюционным расстояниям 60, 100, 200, 300 РАМ (РАМ -Point Accepted Mutations - число происшедших точечных замен). Таким образом, было получено 2x4=8 тестовых наборов по 10000 пар последовательностей в каждом.

2.3.1 Делеции и вставки i) Суммарная длина вставок и делеций

Суммарная длина вставок и делеций D для каждой исходной последовательности полагалась равной

D = L- P(indel)-M5, (1) где L - длина последовательности;

P(indel) - вероятность возникновения вставки-делеции, которая согласно работе Беннер с соавт.(Веппег S.A. et al., 1993), вычислялась по формуле:

P(indel) = 0.0224 - 0.0219- е ("°-01168*РАМ), (2) где РАМ - число, характеризующее эволюционное расстояние между исходной и измененной последовательностями;

Мб - математическое ожидание длины вставки-делеции:

M5 = Id=1.dmaxd-P{5=d}, (3) где P{5=d} - вероятность возникновения вставки-делеции длиной d, взятое из распределения Ципфа, которое, согласно работе Беннер с соавт., не зависит от значения эволюционного расстояния.

Для каждой пары исходной и модифицированной последовательностей суммарная длина вставок была равной суммарной длине делеций, и равна D/2. ii) Внесение делеций

В исходной последовательности длины L, с помощью датчика случайных чисел, исходя из равномерного распределения, выбирался номер элемента последовательности N, 1<N<L, соответствовавший началу делеции; с помощью другого случайного числа из распределения Ципфа выбиралась длина делеции d, l<d<D/2). Если d больше чем расстояние от N до конца последовательности или до уже внесенной делеции, или если суммарная длина делеций больше D/2, то попытка игнорировалась. Таким образом, предотвращалось внесение делеций, длина которых не равна значению, полученному из заданного распределения. Процедура повторялась до достижения суммарной длиной делеций значения D/2. При внесении делеций в исходную последовательность наблюдалось отклонение полученного распределения длин делеций от заданного (т.н. "эффект решета"). Для получения точного распределения длин применялась корректировка вектора распределения длин делеций (см. Дополнение 1).

Ш) Внесение вставок

2.3.2 Точечные замены (мутации)

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

1) с использованием матрицы замен РАМ1. Для каждой буквы исходной последовательности с помощью датчика случайных чисел из соответствующего столбца матрицы выбирается другая буква или та же самая. Число проходов последовательности равно требуемому значению эволюционного расстояния (60, 100, 200 или 300 РАМ) для мутированной последовательности.

2) с использованием матрицы замен, полученной возведением матрицы РАМ1 в степень равную числу, определяющему эволюционное расстояние (60, 100, 200 или 300 РАМ). Число проходов последовательности равно одному. При тестировании процедуры (1) было получено следующее соответствие средней доли совпадений (%\6) числу РАМ (примерно одинаковые для обоих способов мутирования):

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

1. Alberts B., Johnson A., Lewis J., Raff M., Roberts K., Walter P. 2002. Molecular Biology of the Cell. 4th Edition. Garland Science, US.

2. International Human Genome Sequencing Consortium. Initial sequencing and analysis of the human genome. Nature, 2001, 409, 860-921.

3. Altschul S.F., Gish W., Miller W., Myers E.W., Lipman D.J. 1990. Basic local alignment search tool. J Mol Biol. 215(3), 403-410.

4. Amit I, Wides R, Yarden Y. 2007. Evolvable signaling networks of receptor tyrosine kinases: relevance of robustness to malignancy and to cancer therapy.

5. Mol. Syst. Biol. 3, 151-172.

6. Arratia R., Gordon L. and Waterman M.S. 1986. An extreme value theory for sequence matching. Ann. Stat. 14, 971-993.

7. Benner S.A., Cohen M.A. and Gonnet G.H. 1993. Empirical and structural models for insertions and deletions in the divergent evolution of proteins. J. Mol.Biol., 229, 1065-1082.

8. Blaisdell B.E. 1985. Markov chain analysis finds a significant influence of neighboring bases on the occurence of a base in eukaryotic nuclear DNA sequences both protein coding and noncoding. J. Mol. Evol., 21, 278-288.

9. Bourque G., Pevzner P.A., Tesler G. 2004. Reconstructing the genomic architecture of ancestral mammals: lessons from human, mouse, and rat genomes. Genome Res. 14(4), 507-516.

10. Boussau B, Gueguen L, Gouy M. 2008. Accounting for horizontal gene transfers explains conflicting hypotheses regarding the position of aquificales in the phylogeny of Bacteria. BMC Evol Biol. 8(1), 272.

11. Bray J.E., Todd A.E., Pearl F.M., Thornton J.M., Orengo C.A. 2000. The CATH Dictionary of Homologous Superfamilies (DHS): a consensus approach for identifying distant structural homologues. Protein Eng. 13(3), 153-165.

12. Chimpanzee Sequencing and Analysis Consortium. 2005. Initial sequence of the chimpanzee genome and comparison with the human genome. Nature. 437(7055), 69-87. Comment in: Nature. 2005. 437(7055), 50-1.

13. Dayhoff M., Schwartz R. and Orcutt B. 1978. A model of evolutionary change in proteins. 345-352. In: Dayhoff M., ed., Atlas of protein sequence and structure. National Biomedical Research Foundation, Washington, DC.

14. Denker E, Bapteste E, Le Guyader H, Manuel M, Rabet N. 2008. Horizontal gene transfer and the evolution of cnidarian stinging cells. Curr Biol. 18(18), R858-859.

15. Domingues F.S., Lackner P., Andreeva A., et al. 2000. Structure-based evaluation of sequence comparison and fold recognition alignment accuracy. J. Mol. Biol. 297, 1003-1013.

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

17. Eddy S.R. 1998. Profile hidden Markov models. Bioinformatics, 14, 755-763.

18. Ewing B., Green P. 2000. Analysis of expressed sequence tags indicates 35,000 human genes. Nature Genet., 25, 232-234.

19. Finkelstein A.V., Roytberg M.A. 1993. Computation of biopolymers: a general approach to different problems. Biosystems. 30(1-3), 1-19.

20. Gamier N., Friedrich A., Bolze R., Bettler E., Moulinier L., Geourjon C., Thompson J.D., Deleage G., Poch O. 2006. MAGOS: multiple alignment and modelling server.

21. Bioinformatics. 22(17), 2164-2165.

22. Gotoh O. 1982. An improved algorithm for matching biological sequences. J. Mol. Biol., 162, 705-708.

23. Gotoh O. 1999. Multiple sequence alignment: algorithms and applications. Adv Biophys. 36, 159-206. Review.

24. Hollich V, Milchert L, Arvestad L, Sonnhammer ELL. 2005. Assessment of Protein Measures and Tree Building Methods for Phylogenetic Tree Reconstruction. Mol. Biol. Evol. 22(11), 2257-2264.

25. John B., Sali A. 2004. Detection of homologous proteins by an intermediate sequence search. Protein Sci. 13(1), 54-62.

26. Jordan I.K., Kondrashov F.A., Adzhubei I.A., et al. 2005. A universal trend of amino acid gain and loss in protein evolution. Nature. 433, 633-638.

27. Kaback D.B., Guacci V., Barber D., Mahon J.V. 1992. Chromosome size-dependent control of meiotic recombination. Science. 256, 228-232.

28. Karlin S. and Ost F. 1987. Counts of long aligned word matches among random letter sequences. Adv. Appl. Prob. 19, 293-351.

29. Karlin S., Morris M., Ghandour G. and Leung M.-Y. 1988. Efficient algorithms for molecular sequence analysis. Proc. Natl. Acad. Sci. U.S.A. 85, 841-845.

30. Karlin S., Morris M., Ghandour G., Leung M.Y. 1988. Algorithms for identifying local molecular sequence features. Comput Appl Biosci. 4(1), 41-51.

31. Keese P. 2008. Risks from GMOs due to Horizontal Gene Transfer. Environ Biosafety Res. 7(3), 123-149.

32. Kolchinskiii A.M., Barskii V.E., Zasedatelev A.S. 2007. Biochips in the laboratory of A. D. Mirzabekov: 1988-2007. Mol Biol. 41(5), 757-764. Russian.

33. Koonin E.V., Aravind L., Kondrashov A.S. 2000. The impact of comparative genomics on our understanding of evolution. Cell. 101(6), 573-576.

34. Kruskal J.B. and Sankoff D. 1983. Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison. In: Sankoff, D. and Kruskal, J.B., Eds., Addison-Wesley, London.

35. Laurie D.A. and Hulten M.A. 1985. Further studies on bivalent chiasma in human males with normal kariotypes. Ann. Hum. Genet. 49, 189-201.

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

37. Madden T.L., Shavirin S., Spouge J.L, Wolf Y.I., Koonin E.V., AltSchul S.F. 2001. Improving the accuracy of PSI-BLAST protein database searches with composition-based statistics and other refinements. Nucleic Acids Res. 29(14), 29943005.

38. Makarova Iu.A, Kramerov D.A. 2007. Small nucleolar RNA genes. Genetika. 43(2), 149-58.

39. Mayr G., Domingues F.S., Lackner P. 2007. Comparative analysis of protein structure alignments. BMC Struct Biol. 26(7), 50.

40. Mevissen H.Th. and Vingron M. 1996. Quantifying the local reliability of a sequence alignment. Prot. Eng. 9, 127-132.

41. Mitrophanov A.Y., Borodovsky M. 2006. Statistical significance in biological sequence analysis. Brief Bioinform. 7(1), 2-24

42. Mouse genome sequenbing Consortium 2002. Initial sequencing and comparative analysis of the mouse genome. Nature. 420(6915), 520-62. Comments in: Nat. Biotechnol. 2003. 21(1), 31-2. Nature. 2002. 420(6915), 512-4. Nature. 2002. 420(6915), 515-6.

43. Myers E., Miller W. 1988. Sequence comparison with concave weighting functions. Bull. Math. Biol. 50, 97-120.

44. Needleman S.B. and Wunsch C.D. 1970. A general method applicable to the search of similarity in the amino-acid sequence of two proteins. J. Mol. Biol. 48, 443453.

45. Notredame C., Higgins D.G., Heringa J. 2000. T-Coffee: A novel method for fast and accurate multiple sequence alignment. J Mol Biol. 302(1), 205-217

46. Pearson W.R. and Lipman D.J. 1988. Improved tools for biological sequence comparisons. Proc. Natl. Acad. Sci. U.S.A. 85, 2444-2448.

47. Perrodou E., Chica C., Poch O., Gibson T.J., Thompson J.D. 2008.

48. A new protein linear motif benchmark for multiple sequence alignment software. BMC Bioinformatics. 25(9), 213.

49. Pontius J.U., Mullikin J.C., Smith D.R. et al. 2007. Initial sequence and comparative analysis of the cat genome. Genome Res. 17(11), 1675-89. Comment in: Genome Res. 2007. 17(11), 1547-1549.

50. Reese J.T., Pearson W.R. 2002. Empirical determination of effective gap penalties for sequence comparison. Bioinformatics, 18, 1500-1507.

51. Rigoutsos I., Huynh T., Floratos A., Parida L., Piatt D. 2002. Dictionary-driven protein annotation. Nucleic Acids Res. 30(17), 3901-3916.

52. Rosenberg M.S. 2005. Evolutionary distance estimation and fidelity of pair wise sequence alignment. BMC Bioinformatics. 19(6), 102.

53. Rubina A.Y., Kolchinsky A., Makarov A.A., Zasedatelev A.S. 2008. Why 3-D? Gel-based microarrays in proteomics. Proteomics. 8(4), 817-831

54. Saitou N., Nei M. 1987. The Neighbor-joining Method: A New Method for Reconstructing of Phylogenetic Trees. Mol. Biol. Evol. 4, 406-425.

55. Sankararaman S, Sjolander K. 2008. INTREPID INformation-theoretic TREe traversal for Protein functional site IDentification. Bioinformatics. 24(21), 24452452.

56. Schlosshauer M. and Ohlsson M. 2002. A novel approach to local reliability of sequence alignments. Bioinformatics. 6, 847-854.

57. Sellers P. 1974. On the theory and computation of evolutionary distances. SIAM J. Appl. Math., 26, 787-793.

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

59. Sellers, P. 1984. Pattern recognition in genetic sequences by mismatch density. Bull. Math. Biol. 46, 501-514.

60. Senchenko V.N., Liu J., Loginov W. et al. 2004. Discovery of frequent homozygous deletions in chromosome 3p21.3 LUCA and AP20 regions in renal, lung and breast carcinomas. Oncogene. 23(34), 5719-5728.

61. Shah A.R., Oehmen C.S., Webb-Robertson B.J. 2008. SVM-HUSTLE an iterative semi-supervised machine learning approach for pairwise protein remote homology detection. Bioinformatics. 24(6), 783-790.

62. Smith T.F. and Waterman M.S. 1981. Identification of common molecular subsequnces. J. Mol. Biol. 147, 195-197.

63. Stark A., Sunyaev S., Russell R.B. 2003. A model for statistical significance of local similarities in structure. J Mol Biol. 326(5), 1307-1316.

64. Sunyaev S.R., Eisenhaber F., Rodchenkov I.V., Eisenhaber B., Tumanyan V.G., Kuznetsov E.N. 1999. PSIC: profile extraction from sequence alignment with position-specific counts of independent observations. Prot. Eng. 12, 387-394.

65. Thomas P.D., Campbell M.J., Kejariwal A., Mi H., Karlak B., Daverman R., Diemer K., Muruganujan A., Narechania A. 2003. PANTHER: a library of protein families and subfamilies indexed by function. Genome Res. 13(9), 2129-41.

66. Thompson J.D., Plewniak F., Poch O. 1999. BAliBASE: a benchmark alignment database for the evaluation of multiple alignment programs. Bioinformatics. 15, 8788.

67. Thompson J.D., Koehl P., Ripp R., Poch O. 2005. BAliBASE 3.0: latest developments of the multiple sequence alignment benchmark. Proteins. 61(1), 127136.

68. Thompson J.D., Prigent V., Poch O. 2004. LEON: multiple alignment Evaluation Of Neighbours. Nucleic Acids Res. 32(4), 1298-307.

69. Thompson J.D., Koehl P., Ripp R., Poch O. 2005. BAliBASE 3.0: latest developments of the multiple alignment benchmark. Proteins. 61(1), 127-136.

70. Thompson J.D., Muller A., Waterhouse A., Procter J., Barton G.J., Plewniak F., Poch O. 2006. MACSIMS: multiple alignment of complete sequences information management system. BMC Bioinformatics. 23, 7, 318-329.

71. Vingron M. and Argos P. 1990. Determination of reliable regions in protein sequence alignments. Prot. Eng. 3, 565-569.

72. Vingron M and Argos P. 1991. Motif recognition and alignment for many sequences by comparison of dot-matrices. J Mol Biol. 218(1), 33-43.

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

74. Waterman M.S., Smith T.F. and Beyer W.A. 1976. Some biological sequence metrics. Adv. Math. 20, 367-387.

75. Waterman M.S. 1984. Efficient sequence alignment algorithms. J. Theor. Biol. 108, 333- 337.

76. Waterman M.S., Galas D. and Arratia R. 1984. Pattern recognition in several sequences: consensus and alignment. Bull. Math. Biol., 46, 515-527.

77. Waterman M.S. 1987. A new algorithm for best subseqence alignment with application to tRNA-rRNA comparisons. J. Mol. Biol., 197, 723-728.

78. Waterman M.S., ed. 1989. Mathematical methods for DNA sequences. CRC Press, Boca Raton, Florida.

79. Wilbur W.J. and Lipman D.J. 1983. Rapid similarity searches of nucleic acid and protein data banks. Proc. Natl. Acad. Sci. U.S.A. 80, 726-730.

80. Yamada S., Gotoh O., Yamana H. 2006. Improvement in accuracy of multiple sequence alignment using novel group-to-group sequence alignment algorithm with piecewise linear gap cost. BMC Bioinformatics. 7, 524.

81. Yang AS. 2002. Structure-dependent sequence alignment for remotely related proteins. Bioinformatics. 18(12), 1658-1665.

82. Литвинов И.И., Лобанов М.Ю., Миронов А.А., Финкелынтейн A.B., Ройтберг M.A. 2006. Информация о вторичной структуре белка улучшает качество выравнивания. Мол. Биол., 40(3), 533-540.

83. Поройков В.В., Есипова Н.Г., Туманян В.Г. 1984. Распределение аминокислотных остатков в первичных структурах белков. Мол. Биол., 18(2),

84. Ройт А., Бростофф Дж., Мейл Д. 2000. В кн. Иммуноглобулины, Мир, Москва, стр. 131-144.

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

86. Самарский A.A., Гулин A.B. 1989. В кн.: Численные методы. Наука, Москва, стр. 209.

87. Туманян В.Г., Сотникова Л.Е., Холопов A.B. 1966. Об определении вторичной структуры РНК по последовательности нуклеотидов. Докл. Акад. Наук, 166(6), 1465-1468.541.547.

Информация о работе

Поляновский, Валерий Олегович
кандидата физико-математических наук
Москва, 2008
ВАК 03.00.03

Диссертация

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

Автореферат

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