Содержание к диссертации
Введение
Глава I. Обзор литературы 7
Задача выравнивания биологических последовательностей 7
Наиболее распространенные методы построения парных выравниваний ... 13
Множественные выравнивания и профили 21
Молекулярно-биологические банки данных 23
Глава II. Исследование качества выравниваний, построенных методом Смита-Уотермана 27
Методы и определения 27
Сравнение эталонных выравниваний и выравниваний Смита-Уотермана... 32
Улучшение качества выравниваний Смита-Уотермана за счет индивидуального подбора параметров 36
Глава III. Острова в выравниваниях ... 39
Восстановление островов эталонных выравниваний 39
Выделение ядер в островах 48
Глава IV. Новый алгоритм выравнивания двух последовательностей 51
Схематическое описание нового алгоритма 51
Построение якорей, использование затравок и оптимизация параметров... 53
Нахождение оптимального пути через якоря 60
Сравнение качества построения выравниваний и скорости работы нового метода и стандартных 62
Глава V. Применение новой методики к построению выравниваний последовательности и профиля 66
Адаптация алгоритма ANCHOR к задаче выравнивания последовательности и профиля 66
Сравнение качества выравниваний последовательности и профиля, построенных новым методом, и выравниваний Смита-Уотермана . 69
Глава VI. Поиск гомологов по банку данных с помощью метода ANCHOR ... 73
Заключение 77
Практическое значение работы 78
Выводы 79
Список публикаций по теме диссертации 80
Литература 81
- Наиболее распространенные методы построения парных выравниваний
- Улучшение качества выравниваний Смита-Уотермана за счет индивидуального подбора параметров
- Сравнение качества построения выравниваний и скорости работы нового метода и стандартных
- Сравнение качества выравниваний последовательности и профиля, построенных новым методом, и выравниваний Смита-Уотермана
Введение к работе
Молекулярная биология совсем молодая, но очень быстро развивающаяся наука. Современный этап развития молекулярной биологии и генетики характеризуется лавинообразным ростом объема расшифрованных биологических последовательностей. Это произошло в значительной степени благодаря программе «Геном человека» и другим подобным, исследованиям. В то же время, как правило, аминокислотные последовательности являются лишь стартовой точкой исследования. В конечном итоге молекулярных биологов, интересует трехмерная структура белков и их функциональная активность. Получение трехмерной структуры белка и определение его функции является очень трудоемкой и дорогостоящей задачей. Количество известных трехмерных структур белков на порядок меньше количества расшифрованных последовательностей. Следовательно, нужны методы, позволяющие предсказывать структуру и функцию белка только по его последовательности. Или, как минимум, нужно уметь отнести новую последовательность к какому-нибудь из уже известных классов белков, т.е. найти группу сходных последовательностей с предположительно подобными структурами или функциями.
Одним из наиболее эффективных и удобных методов сравнения, классификации и выявления сходств биологических последовательностей является метод их выравнивания. Задача выравнивания двух последовательностей - одна из наиболее старых классических проблем вычислительной биологии [1-4]. Выравнивание новой последовательности с последовательностью уже хорошо изученного белка, т.е. такого, о котором известна третичная структура и функция, дает возможность количественно определить уровень сходства этих последовательностей, а так же указать участки наиболее вероятного сходства структур или функций. Для того чтобы предсказание было правдивым, необходимо уметь строить биологически адекватное выравнивание последовательностей, т.е. отражающее эволюционное превращение одного белка в другой [5]. К сожалению, на современном уровне развития вычислительной биологии невозможно в точности воспроизвести ход эволюции. Однако аккуратное выравнивание, отражающее сходство пространственных структур, можно считать достаточным приближением биологически адекватного выравнивания, т.к. структурные
элементы белка остаются консервативными даже при достаточно сильном расхождении аминокислотных последовательностей [6]. На настоящий момент существуют алгоритмы, позволяющие строить выравнивания трехмерных структур напрямую, однако они работают далеко не для всех случаев [7-13].
Парные выравнивания используются во многих методах численного анализа биологических последовательностей, таких как функциональное аннотирование генов и белков [14], анализ доменов белков [15], моделирование трехмерной структуры белка по сходству последовательностей [16]. Многие сложные методы вычислительной биологии, например, множественные выравнивания [17-19] и построение профилей [20, 21], используют построение парных выравниваний как промежуточный этап.
Наиболее часто используемыми методами сравнения последовательностей являются: алгоритм Смита-Уотермана (SW) [2, 22] и более быстрые эвристические алгоритмы FASTA[3, 23] и BLAST [4, 24]. Тем не менее, все эти алгоритмы строят выравнивания далекие от совершенства. Выравнивания последовательностей достаточно хорошо сопоставляют элементы вторичной структуры только при высоком уровне гомологии белков. В то время как структурное сходство белков достоверно обнаруживается и при значительном расхождении, последовательностей. Мы употребляем слово «гомология» по традиции, хотя правильнее было бы использовать выражение «сходство последовательностей».
Алгоритм Смита-Уотермана в настоящий момент считается самым чувствительным, но работает он наиболее медленно. В дальнейшем выравнивания, построенные только по последовательностям с помощью какого-либо алгоритма, будем называть алгоритмическими, чтобы подчеркнуть их отличие от структурных выравниваний, при построении которых используются дополнительные знания о вторичной и третичной структуре белков.
Сказанное выше определяет актуальность темы настоящего исследования — сравнение структурных выравниваний с выравниваниями, построенными методом SW (как самого чувствительного), и построение нового более эффективного и точного алгоритма выравнивания аминокислотных последовательностей, используя знания о различиях структурных и алгоритмических выравниваний.
Цель и задачи исследования
Основная часть работы заключалась в исследовании различий и сходств алгоритмических и структурных выравниваний. Оценивалось качество восстановления структурных выравниваний методом SW с целью выявить причины неточного восстановления структурных выравниваний и, на основе проведенного исследования, разработать новый метод выравнивания аминокислотных последовательностей. Выравнивания белков, полученные наложением их пространственных структур, рассматриваются в качестве эталонных, т.к. они в наилучшей степени отражают эволюцию белков по сравнению с другими способами выравнивания.
В процессе работы решались следующие основные задачи исследования:
(1) Определение степени максимально возможного приближения к эталонному выравниванию за счет индивидуального подбора параметров алгоритма SW.
(2) Детальное исследование внутренней структуры эталонных и алгоритмических выравниваний аминокислотных последовательностей для определения причин различий между ними.
(3) Разработка нового метода выравнивания аминокислотных последовательностей. Сравнение качества восстановления эталонных выравниваний и скорости работы нового метода и стандартных методов выравнивания.
(4) Адаптация разработанного метода выравнивания двух аминокислотных последовательностей для решения близких задач (построение выравнивания последовательности и профиля, поиск гомологов по банку данных).
Все проведённые исследования нашли своё отражение в представленном детальном описании работ, выполненных в рамках диссертационного проекта.
Список используемых сокращений: SW — метод Смита-Уотермана, PDB - Protein Data Bank - банк данных трехмерных структур белков.
Наиболее распространенные методы построения парных выравниваний
Сравнение эталонных структурных выравниваний (GS) и выравниваний Смита-Уотермана (SW). (а), (г) - структурные выравнивания (GS) виде совмещения структур в пространстве; (б), (д) - структурные выравнивания (GS) в буквенном представлении; (в), (е) - выравнивания последовательностей соответствующих белков, построенные методом Смита-Уотермана (SW).
Выравнивания строились для 2-х пар белков: (а-в) кардиотоксин (код PDB [27]: ltgx) с эрабутоксином b (код PDB: lera); (г-е) кобратоксин (код PDB: lctx) с токсином FS2 (код PDB: ltfs). На Рисунке 2 (а), (д) представлены выравнивания трехмерных структур для 2-х пар белков: ltgx vs. 1 era и lctx vs. ltfs. Сопоставленные позиции окрашены красным для белков ltgx и lctx и синим для lera и ltfs, несопоставленные позиции окрашены желтым в белках ltgx и lctx и зеленым в lera и ltfs. Среднее отклонение Са атомов для выровненных аминокислот составляет 3 А, однако на концах выровненных участков это отклонение может достигать 9 А. На Рисунке 2 (б) и (д) представлена буквенная запись выравниваний трехмерных структур (а) и (г) соответственно.
Выравнивания бывают глобальные и локальные. В глобальных выравниваниях последовательности сопоставляются от начала до конца, а в локальных - концевые участки последовательностей не влияют на общий вес выравнивания, следовательно, их можно не сопоставлять [26]. Таким образом, оптимальное локальное выравнивание не может иметь вес меньше нуля, глобальное может принимать любой вес. Локальные выравнивания применяются для нахождения локальных сходств, например при сравнении многодоменных белков. Схематически локальное выравнивание изображено на Рисунке 3.
Схематическое представление локального выравнивания. Выровнены блоки В и В , в то время как боковые цепи А и С не сопоставлены и не штрафуются. При построении выравнивания только по первичным структурам белков используется метод динамического программирования, который заключается в нахождении оптимального выравнивания, т.е. выравнивания, имеющего максимально возможный вес. Вес W выравнивания двух последовательностей определяется как суммарный вес сопоставления (вычисляется по матрице замен S) минус суммарный штраф за делеции/вставки символов: U где Sy — веса сопоставлений /-го символа первой последовательности и у-го символа второй последовательности, сумма производится по всем сопоставлениям выравнивания, kj - количество вставок/делеций, а - штраф за вставку/делецию одного символа [26]. Первый алгоритм выравнивания двух биологических последовательностей был предложен Нидельманом и Вуншем [1]. Их алгоритм, основанный на методе динамического программирования, заключается в нахождении выравнивания, имеющего максимальное значение весовой функции (оптимального выравнивания): Весовую функцию W также иногда называют функцией сходства или функцией подобия. Матрицы весов сопоставлений Sy (матрицы замен), как правило, вычисляются по частотам замен символов в среднем по банку структурных выравниваний белковых семейств, то есть в основе этих матриц косвенно лежат физико-химические свойства аминокислот. Очевидно, что такая матрица зависит от анализируемого банка и от метода оценки частот замен. На сегодняшний день существует несколько семейств матриц замен аминокислот, наиболее известные из них: РАМ [28], BLOSUM [29], GONNET [30]. Матрицы в этих семействах получены, исходя из частот замен аминокислот в гомологичных фрагментах эволюционно близких белков; различные матрицы в серии различаются степенью близости использованных фрагментов. Другой способ составления матриц замен следует из анализа физико-химических свойств аминокислот. Например, боковая цепь триптофана (W) содержит цикл и имеет огромные размеры по сравнению с боковыми цепями аланина (А) или глицина (G). Мутация триптофана на любой из этих остатков приведет к стерическим затруднениям, следовательно, соответствующие веса замены должны быть сильно отрицательными. Таким образом, чем критичнее для пространственной структуры замена аминокислот, тем более отрицательный вес будет ей соответствовать в матрице замен, и наоборот. Сравнение матриц, вычисленных по банкам структурных выравниваний, и матриц, составленных на основе физико-химических свойств аминокислот, показывает, что они незначительно отличаются друг от друга. Матрица замен как один из параметров выравнивания имеет обоснованную биологическую мотивацию. Хуже обстоит дело со штрафом за удалённый символ, в том смысле, что нет никаких разумных доводов в пользу того или иного значения этого параметра. С точки зрения эволюционных событий, наличие вставки или делеции длиной в несколько символов соответствует единичному событию, причем длинные делеции для родственных последовательностей менее вероятны, чем короткие, поэтому логично ввести штраф за множественную делецию, как функцию от ее длины: где A — штраф за открытие делеции, а В — штраф за продолжение множественной делеции [25]. Такая схема называется аффинным штрафом за вставку/делецию. В некоторых специфических задачах используются другие схемы штрафования множественных делеции, например: т(/) = А + В log(/); сг{1) = A + Blc .
В любом случае пользователю приходится подбирать подходящие значения для параметров А и В. Никаких точных биологически оправданных оценок для этих параметров нет [31]. Известно только то, что для разных матриц замен нужно использовать разные штрафы и что для разных семейств параметр А варьируется.
В некоторых случаях небольшие изменения весов аминокислот или штрафной функции вставок/делеций приводят к существенным изменениям в результирующих выравниваниях. В других случаях выравнивания остаются устойчивыми к изменениям алгоритмических параметров. Однако единого множества «правильных» параметров не существует [25, 32]. Таким образом, штрафы за вставки/делеции подбираются эмпирически так, чтобы в среднем по выборке белков оптимальные выравнивания были максимально похожими на структурные.
Улучшение качества выравниваний Смита-Уотермана за счет индивидуального подбора параметров
Из предыдущих результатов следует, что внутренние различия эталонных и алгоритмических выравниваний не позволяют точно воссоздать эталонное выравнивание по последовательностям. Если удастся определить и желательно устранить основные причины этих различий, можно создать более точный метод выравнивания или как минимум выяснить, каким участкам существующих алгоритмических выравниваний можно доверять.
Внутреннее строение выравниваний последовательностей удобно описывать с помощью понятия «острова». Назовем «островом» непрерывный участок сопоставлений, в котором отсутствуют делеции/вставки в каждой из последовательностей. Выравнивание можно представить как цепочку островов, соединенных делециями. На Рисунке 2 (б, в, д, е) (стр. 8) острова выравниваний подписаны латинскими буквами и отмечены черточками. Так эталонное выравнивание, представленное на Рисунке 2 (б), содержит 4 острова, в то время как выравнивание Смита-Уотермана (SW) этих же последовательностей (Рисунок 2 (д)) содержит всего 2 острова.
Мы исследовали характеристики, аналогичные точности и достоверности выравниваний в целом, для отдельных островов. Подобно точности выравнивания (АИ_Асс) определим точность восстановления острова эталонного выравнивания (Isl_Acc) равной отношению количества позиций, одинаково выровненных в построенном и эталонном выравниваниях (I_isl), к полной длине эталонного острова (Gisl): Аналогично достоверности алгоритмического выравнивания (AliConf) определим достоверность построенного острова (IsljConJ) как отношение количества правильных сопоставлений (I_isl) к полной длине построенного острова (Aisl):
Как видно из Рисунка 21, остров эталонного выравнивания или достаточно точно восстановлен, или полностью потерян. Частичное восстановление острова случается достаточно редко. Точно также частично правильные острова в выравниваниях Смита-Уотермана составляют небольшую долю. Дальнейший анализ показал, что это в целом верно для всех диапазонов %Ю (данные не представлены). Таким образом, острова условно можно поделить на «потерянные» (не имеющие ничего общего с эталонными выравниванием) и «найденные» (содержащие хотя бы одно правильное сопоставление). Тем не менее, ситуация «все или ничего» не верна для точности и достоверности по выравниванию в целом. Например, при линейных параметрах (см. Рисунок 18, стр. 32), получилось 69 выравниваний SW с АН_Асс = 0; Ali_Acc больше либо равное 80% наблюдается у 249 выравниваний (229 из них соответствует ID 30%), в то время как 264 выравнивания имеют Ali_A.cc в диапазоне 0 - 80%.
Свойства эталонных островов очень важны для возможности их восстановления каким-либо алгоритмом выравнивания последовательностей. Так точность восстановления эталонного выравнивания определяется двумя факторами: свойствами островов эталонных выравниваний и весом других возможных путей выравнивания, альтернативных эталонному острову [64]. Определим суммарный вес (или просто вес) острова как
На Рисунке 22 (а) представлена гистограмма распределения весов островов эталонных выравниваний и; выравниваний SW. Оказалось, что неожиданно много эталонных островов имеют очень низкий или даже отрицательный вес, в то время как алгоритмические выравнивания совсем не содержат островов малого веса. Стоит отметить, что суммарная длина таких «слабых» островов довольно велика (Рисунок 22 (б)).
Эталонные острова веса меньше 5 составляют 32% от всех островов и покрывают 20% всей длины эталонных выравниваний, острова веса 5 оставляют 65% от всех потерянных островов и покрывают 63% суммарной длины потерянных островов. Только 5% островов такого малого веса были восстановлены алгоритмом. Для выравниваний из серой зоны (10 %ID 30) картина еще более критическая — восстановлено всего 2.5% островов веса меньше 5. Эти «слабые» острова обычно не имеют шансов быть восстановленными любым алгоритмом, использующим данную матрицу замен. В частности, наличие таких эталонных островов малого веса говорит о неадекватности применения одной и той же матрицы замен для всей длины выравнивания.
Эталонные острова высокого веса (больше 25) почти всегда восстановлены, в то время как острова с весом от 10 до 25 составляют зону неопределенности. Вероятность восстановления острова из этого весового диапазона сильно зависит от наличия альтернативных путей более высокого веса. Итак, алгоритм SW не может восстановить остров с невысоким весом по двум причинам: 1) если штраф за открытие делеции относительно большой, то алгоритму не выгодно вставлять новую делецию (или делеции), чтобы построить этот остров (см. остров «-а-» на Рисунке 2(6), стр. 8); 2) если штрафы низкие - найдется альтернативный путь более высокого веса по чисто статистическим причинам (острова выравниваний на Рисунке 2 (д) и (е), стр. 8). Со стандартными параметрами первый случай типичен для пар белков с высокой степенью гомологии, второй — для дальних гомологов. Гистограммы суммарных длин островов с весом в пределах указанных по оси X диапазонов отдельно для каждой их 3-х областей %Ю (более детальное рассмотрение Рисунка 22 (а)).Данные по эталонным островам показаны белым, SW — черным. Выравнивания SW получены с «линейными» параметрами». Гистограммы, представленные на Рисунке 23, являются более детальным рассмотрением гистограммы Рисунке 22 (б). В них данные представлены отдельно для трех диапазонов %Ю. Видно, что с увеличением гомологи сравниваемых белков различие в весе эталонных и построенных островов уменьшается. Однако даже для высокого уровня сходства белков (ID 30%) встречаются эталонные острова отрицательного веса.
Мы проверили, что такая ситуация типична не только для матрицы замен Gonnet250, но и для других матриц. В Таблице 2 представлено количество и суммарная длина отрицательно весящих эталонных островов для разных матриц замен. Первые две колонки этой таблицы относятся к часто используемым матрицам замен Blosum62 и Gonnet250. Данные третьей колонки получены при использовании матриц замен, вычисленных по множественным выравниваниям базы данных BaliBase в соответствии с формулами указанными в [29]. Эти матрицы были вычислены отдельно для трех категорий выравниваний: ID 25%, 25% ID 50% и ID больше 50%. Вес островов для колонки «BaliBase» вычислялся по матрице, соответствующей уровню гомологии сравниваемых белков в эталонном выравнивании.
Сравнение качества построения выравниваний и скорости работы нового метода и стандартных
Теперь остановимся более подробно на пункте II нашего алгоритма (Рисунок 26II) - нахождении оптимального пути через якоря.
Мы находим путь оптимального выравнивания блоков через построенные якоря. Блок - это непрерывная часть якоря. Выравниванием блоков назовем цепочку блоков {Вь ... , BN}, где Bj предшествует Ві+i в обеих последовательностях S1 и S2. Выравнивание блоков {Bi, ... , BN} считается оптимальным, если на нем достигается максимальный блочный вес, который определяется следующим образом: где а - штраф за открытие связки или за сход с якоря (LOP); р — штраф за увеличение размера связки (LEP); х, у - координаты последних аминокислотных остатков, используемых в блоке BJ; х\ у - координаты первых аминокислотных остатков, используемых в блоке Bj+i последовательностей. Координата «х» соответствует последовательности S1, «у» - последовательности S2. Штрафы LOP и LEP нашего алгоритма соответствуют штрафам за открытие делеции (GOF) и за удлинение делеции (GEP) соответственно, использующимся при построении выравниваний Смита-Уотермана.
Стоит отметить, что штрафуемая длина связки равняется расстоянию между диагоналями, на которых находятся связываемые блоки. Т.е. вес связки двух блоков, находящихся на одной диагонали, будет равняться просто штрафу за открытие связки, т.к. длина связки равна нулю. В отличие от стандартных штрафных функций мы штрафуем связку между якорями, находящимися на одной диагонали.
Для того чтобы найти оптимальный блочный путь через построенные якоря, мы применяли два алгоритма: алгоритм Вилбура-Липпмана [66] и метод динамического программирования на разреженных матрицах [67] (sparse dinamic programming metod - SPD). Эти процедуры строят одинаковые выравнивания (при одинаковых параметрах и наборе якорей), но различаются по скорости работы.
Время работы алгоритма Вилбура-Липпмана пропорционально К, где К равняется количеству якорей. Время работы метода динамического программирования на разреженных матрицах пропорционально K log(L), где К — количество якорей; L = min(L/, Li) - длина более короткой последовательности. Если используется небольшое количество якорей, алгоритм Вилбура-Липпмана строит выравнивание быстрее, потому что в нем применяется более простая техника в реализации. Метод SPD более эффективен в случае большого количества якорей при выравнивании длинных последовательностей. Наши эксперименты показали, что на реальных белках наилучшее время работы можно достичь методом Вилбура-Липпмана, который мы и применяли для дальнейших экспериментов.
Для тестов нашего метода мы использовали две базы данных: BaliBase и FSSP. База BaliBase использовалась для оптимизации алгоритма и его параметров, FSSP - как независимый тест для того, чтобы исключить зависимость от одной базы данных.
При тестах на базе BaliBase мы старались подобрать такие параметры алгоритма, принадлежащие логарифмическому домену, чтобы соотношение скорости и качества выравнивания было наилучшим. Естественным образом характеристики АН_Асс и AlijConf являются взаимодополняющими, увеличение одной характеристики приводит к уменьшению другой. Время работы алгоритма, точность и достоверность выравниваний, построенных нашим методом ANCHOR, зависит от параметров. Наиболее сильное влияние на эти характеристики оказывает порог на участвующие в рассмотрении якоря.
В Таблице 10 представлены наиболее оптимальные параметры для построения выравниваний нашим методом ANCHOR для трех наиболее часто используемых матриц замен. Эти параметры принадлежат логарифмическому домену и пригодны для работы с многодоменными белками. Для дальнейших тестов мы использовали параметры, соответствующие матрице замен Gonnet250.
С этими подобранными параметрами мы строили парные выравнивания, используя в качестве эталонных выравнивания, извлеченные из FSSP (см. Материалы и методы). В итоге точность и достоверность нашего метода были протестированы на -13 000 парных структурных выравниваний из баз данных BaliBase и FSSP.
Мы сравнили нашу программу выравнивания со стандартной реализацией алгоритма Смита-Уотермана, извлеченной из программного пакета FASTA (см. Методы и определения). В Таблице 11 представлены сравнительные характеристики нашего метода (ANCHOR) и метода Смита-Уотермана (SW). В результате тестов выяснилось, что выравнивания, полученные новым методом, в среднем эквивалентны выравниваниям Смита-Уотермана как по точности восстановления эталонных выравниваний, так и по достоверности. Это справедливо как для всего диапазона уровня гомологии сравниваемых белков, так и для «серой зоны». Как было указано выше, использование только областей высокого веса (якорей) для построения выравнивания может существенно улучшить скорость работы программы. Видно, что предложенный метод ANCHOR требует примерно в два раз меньше времени, чем классический SW. 1) При помощи стандартной функции clockQ макроязыка Си фиксировалось время начала работы процедуры выравнивания и время окончания её работы. Их разность дает время, затраченное на построение выравнивания. Именно эти данные представлены в Таблице 11. Известно, что процедура clockQ имеет сильную погрешность в измерении времени. Поэтому процедуры построения выравниваний были заключены в цикл с повторением до 100 раз для увеличения точности измерения. 2) Встроенный измеритель времени работы процедур profiler системы разработки программ MS-VisualStudio (VisualC++ 6.0) дает возможность измерять абсолютное и относительное (ко времени работы других процедур программы) время работы процедур. Однако в массовых тестах его использование неудобно.
Сравнение качества выравниваний последовательности и профиля, построенных новым методом, и выравниваний Смита-Уотермана
Мы исследовали соответствие между эталонными выравниваниями трехмерных структур белков и выравниваниями, построенными по последовательностям методом, Смита-Уотермана. В результате работы была получена зависимость надежности восстановления выравнивания пространственных структур по аминокислотным последовательностям от уровня сходства сравниваемых последовательностей. Определены границы уровня сходства, для которых алгоритмическое выравнивание достоверно, т.е. в значительной степени совпадет с эталонным структурным выравниванием.
Показано, что индивидуальный подбор штрафов за делеции существенно (более чем на 10%) увеличивает точность выравниваний для белков с уровнем сходства 10-30% (серая зона). Однако даже в этом случае средняя точность вьфавниваний для этого диапазона %Ю не превышает 52%, а достоверность - 70%. Следовательно, различия структурных и алгоритмических выравниваний не могут быть устранены с помощью точной настройки параметров под каждую конкретную пару сравниваемых белков.
При детальном рассмотрении алгоритмических и структурных вьфавниваний обнаружены различия на уровне внутренней структуры - «островов» (безделяционных участков выравнивания). В выравниваниях SW восстановлено 53% островов, из которых 42% приходится на острова, которые угаданы на 90% и более. Потерянных островов 47%, они имеют малый вес и длину. 32% островов эталонных выравниваний имеет вес меньше 5, а суммарная длина таких островов составляет 20% всей длины эталонных вьфавниваний. Потерянные острова веса меньше 5 оставляют 65% от всех потерянных островов и покрывают 63% суммарной длины потерянных островов. Только 5% островов такого малого веса были восстановлены алгоритмом. То есть все эти острова малого веса находятся вне пределов досягаемости стандартных методов сравнения последовательностей. Для выравниваний из серой зоны эти цифры аналогичны, однако восстановлено только 2.5% островов с весом меньше 5, и потерянные острова оставляют 65% от общего количества эталонных островов.
Однако не все острова малого веса безнадежны. Выявлено, что в некоторых «слабых» островах можно выделить положительные участки существенного веса. Таких областей не много по сравнению с общей площадью матицы Нидельмана-Вунша, и, следовательно, алгоритм, не просматривающий заведомо несопоставимые области, будет работать быстрее стандартного алгоритма Смита-Уотермана.
На основе этих результатов исследований остров и их ядер мы разработали новый алгоритм ANCHOR выравнивания последовательностей. На первом шагу построения выравнивания последовательностей методом ANCHOR выделяются непрерывные участки высокого веса (якоря). Далее метод находит оптимальный пусть через вычисленный на предыдущем шаге набор якорей, а потом путь между концами закрепленных якорей дополняется методом Смита-Уотермана.
Получившийся алгоритм не уступает в качестве восстановления структурного выравнивания методу Смита-Уотермана, но работает примерно в 2 раза быстрее. Отсюда следует, что уменьшение качества выравнивания не обязательная плата за увеличение скорости работы алгоритма.
Новый алгоритм ANCHOR адаптирован для построения выравнивания последовательности и профиля. Показано, что и для выравнивания профиля и последовательности новый метод хорошо восстанавливает эталонные выравнивания, и работает как минимум в 2 раза быстрее, метод Смита-Уотермана.
На основе нового алгоритма разработана программа поиска гомологов по банку данных (Search-Anchor). Новая программа выдает более точный список гомологов, чем FASTA и BLAST, но работает медленнее более чем в 3 раза. Новый алгоритм работает быстрее алгоритма Смита-Уотермана, незначительно уступая ему в качестве.
На основе нового метода построения выравниваний разработан программный комплекс, который позволяет строить выравнивания в 2 раза быстрее метода Смита-Уотермана, не теряя точности и достоверности. Программа и исходные коды доступны через всемирную компьютерную сеть по адресу: ftp://genetics.bwh.harvard.edu/Sunvaev/saadi/
Данные программы могут применяться молекулярными биологами для сравнения двух последовательностей, выравнивания профиля (построенного из множественного выравнивания) и последовательности. С помощью программы Search-Anchor можно осуществлять поиск гомологов по любой заданной базе данных в формате FASTA. 1. Получена зависимость надежности восстановления выравнивания пространственных структур (эталонных выравнивании) по аминокислотным последовательностям белков методом Смита-Уотермана. Показано, что индивидуальный подбор штрафов за делеции существенно (более чем на 10%) увеличивает точность выравниваний для белков с уровнем сходства 10-30% (серая зона). Однако даже в этом случае средняя точность выравниваний для этого диапазона %ID не превышает 52%, а достоверность — 70%. 2. Обнаружены различия алгоритмических и структурных выравниваний на уровне внутренней структуры «островов» (безделяционных участков выравнивания). В выравниваниях SW восстановлено 53% островов, из которых 42% приходится на острова, которые угаданы на 90% и более. Потерянных островов 47%, они имеют малый вес и длину. Показано, что 32% островов эталонных выравниваний имеет вес 5, суммарная длина таких островов составляет 20% всей длины эталонных выравниваний, потерянные острова веса 5 оставляют 65% от всех потерянных островов и покрывают 63% суммарной длины потерянных островов. Только 5% островов такого малого веса были восстановлены алгоритмом. Для выравниваний из серой зоны эти цифры аналогичны, однако восстановлено только 2.5% островов с весом меньше 5, и потерянные острова оставляют 65% от общего количества эталонных островов. Проблемы с восстановлением островов малого веса являются причиной недостаточной точности алгоритмических выравниваний. 3. Разработан новый алгоритм ANCHOR выравнивания последовательностей, который при построении выравнивания учитывает не весь вес острова, а только его положительную основу (ядро). Показано, что новый алгоритм не уступает в качестве восстановления структурного выравнивания методу Смита-Уотермана, но работает примерно в 2 раза быстрее. 4. Новый алгоритм ANCHOR адаптирован для построения выравнивания последовательности и профиля. Показано, что он так же хорошо восстанавливает эталонные выравнивания, как и SW, но работает быстрее как минимум в 2 раза. 5. На основе нового алгоритма разработана программа поиска гомологов по банку данных (Search-Anchor). Новая программа выдает более точный список гомологов, чем FASTA и BLAST, но работает медленнее более чем в 3 раза. Новый алгоритм работает быстрее алгоритма Смита-Уотермана, незначительно уступая ему в качестве.
Похожие диссертации на Выравнивание аминокислотных последовательностей: анализ существующих методов и разработка новых алгоритмов
