Содержание к диссертации
Введение
Глава 1. Обзор литературы 13
1.1. Выравнивание символьных последовательностей 13
1.1.1. Постановка задачи парного выравнивания символьных последовательностей 13
1.1.2. Использование динамического программирования при выравнивании последовательностей 16
1.1.3. Весовые матрицы замен 19
1.2. Базы данных эталонных выравниваний 20
1.2.1. Общие сведения 20
1.2.2. Обзор существующих баз данных 21
Глава 2. Эталонные выравнивания 24
2.1. База данных PREFAB-P 25
2.1.1. Общие сведения 25
2.1.2. Методика подготовки базы PREFAB-P -2 — Оглавление —
2.1.3. Структура базы данных PREFAB-Р 29
2.2. Модельные эталонные выравнивания 31
2.2.1. Общие сведения 31
2.2.2. Предварительные эксперименты 31
2.2.3. Общая схема построения набора модельных данных 32
2.2.4. Внесение мутаций-«замен» в символьные последовательности 34
Глава 3. Алгоритм и реализация 36
3.1. Исследование алгоритма Смита-Ватермана 36
3.1.1. Общие сведения 36
3.1.2. Методика проведения экспериментов 36
3.1.3. Результаты 37
3.2. Постановка новой задачи 38
3.2.1. Исключение параметра GEP 38
3.2.2. Формальная постановка задачи 40
3.3. Решение задачи построения набора выравниваний-кандидатов 40
3.3.1. Общие сведения 40
3.3.2. Алгоритм построения множества Парето-оптимальных выравниваний 42
3.3.3. Алгоритм выделения основных выравниваний 45
3.3.4. Оценка вычислительной сложности алгоритмов 46
3.4. Реализация 49
3.4.1. Общие сведения 49
3.4.2. Пользовательский интерфейс комплекса PARCA 50
3.4.3. Программный интерфейс комплекса PARCA 51
3.4.4. Детали реализации 54
3.5. Вспомогательные алгоритмы 55
3.5.1. Определение штрафа GOP для соответствующих выравниваний Смита-Ватермана 55
3.5.2. Выделение общей части основных выравниваний 58
Глава 4. Компьютерные эксперименты 67
4.1. Методика 67
4.1.1. Общие сведения 67
4.1.2. Построение выравниваний 67
4.1.3. Анализ полученных данных 69
4.2. Анализ модельных данных 69
4.3. Анализ выравниваний из PREFAB-P 70
4.4. Обсуждение результатов 72
Заключение 87
Список таблиц 89
Литература
- Весовые матрицы замен
- Модельные эталонные выравнивания
- Постановка новой задачи
- Анализ полученных данных
Введение к работе
Актуальность темы. Выравнивание аминокислотных и нуклеотид-ных последовательностей является классическим для биоинформатики методом сравнения последовательностей. Выявляемые при этом сходства часто являются следствием функциональных, структурных или эволюционных взаимосвязей между последовательностями. В 70-е годы XX века, когда сравнивались последовательности относительно небольшой длины, выравнивание производилось вручную, затем были предложены алгоритмы построения выравнивания. Актуальность задачи выравнивания обуславливается тем, что для многих белков известны их аминокислотные последовательности, но лишь для малой части из них известны пространственные структуры.
Для приложений важно, насколько алгоритмически полученные выравнивания отражают реальную эволюционную связь между сравниваемыми последовательностями. Количественной мерой этого служит точность выравнивания - доля таких сопоставлений эталонного выравнивания, которые присутствуют в алгоритмическом выравнивании. В качестве эталонных выравниваний аминокислотных последовательностей, например, используются выравнивания, основанные на наложении пространственных структур белков, соответствующих этим последовательностям.
Наиболее точным из известных в настоящее время алгоритмов построения глобального парного выравнивания аминокислотных последовательностей является алгоритм Смита-Ватермана, основанный на построении оптимального выравнивания, то есть выравнивания, для которого достигается максимальное значение весовой функции. Тем не менее, для слабогомологичных последовательностей точность выравниваний Смита-Ватермана невысока.
Существующие на данный момент алгоритмы попарного выравнивания, в частности, алгоритм Смита-Ватермана, требуют задания ряда параметров, выбор значений которых не имеет под собой надежного обоснования. Примером такого параметра является штраф за делецию (удаление) фрагмента; ошибка в выборе его значения приводит к существенному ухудшению точности алгоритмически полученного выравнивания. Одним из путей повышения точности алгоритмически построенных выравниваний является разработка метода выравнивания, который не использует штрафы за делеции, что определяет актуальность темы исследования.
Цели и задачи исследования. Цель исследования состоит в разработке метода глобального выравнивания биологических последовательностей, который позволяет получать выравнивания, более точные, чем выравнивания Смита-Ватермана. Исходя из поставленных целей, были сформулированы и решены следующие задачи:
1. Предложить новую формализацию задачи выравнивания, в которой не используются штрафы за делеции фрагментов.
Разработать эффективный алгоритм решения этой задачи.
Создать программную реализацию разработанного алгоритма.
Провести сравнительное исследование качества выравниваний, полученных с помощью разработанного алгоритма и выравниваний, полученных методом Смита-Ватермана.
Методы исследования. В работе использованы методы теории алгоритмов, теории вероятностей, математической статистики, биоинформатики и вычислительной молекулярной биологии, проведение вычислительных экспериментов с использованием существующих и оригинальных программ.
Достоверность результатов. Достоверность результатов обеспечивается адекватностью используемых методов теории алгоритмов, теории вероятностей, математической статистики и биоинформатики, верификацией математических моделей, а также сравнением аналитических результатов с результатами математического моделирования.
Научная новизна. Научная новизна работы состоит в сформулированной новой постановке задачи построения глобального выравнивания (задача построения упорядоченного множества выравниваний-кандидатов), а также в разработанных оригинальных алгоритмах. Предложен алгоритм построения упорядоченного набора выравниваний-кандидатов с временем работы 0(R-L2), где R - ограничение сверху на количество удаленных фрагментов в рассматриваемых выравниваниях, a L - это средняя длина выравниваемых последовательностей.
Личный вклад. Представленные в диссертационной работе результаты получены лично соискателем.
По материалам диссертационной работы опубликованы 4 научные работы. В работе [1] соискателю принадлежит алгоритм построения набора основных выравниваний, а также сравнительное исследование точности глобальных выравниваний Смита-Ватермана и наборов основных выравниваний, включая разработку методики исследования и подготовку исходных данных. В работе [2] соискателю принадлежит создание программы PARCA, разработка методики проведения компьютерных экспериментов, проведение самих экспериментов и их анализ. В работах [3] и [4] автору принадлежит разработка методики верификации базы данных эталонных выравниваний PREFAB, участие в проведении компьютерных экспериментов (совместно с И. Поверенной) и создание окончательной версии базы данных PREFAB-Р.
Теоретическая и практическая значимость. Теоретическая значимость исследования заключается в постановке нового варианта задачи выравнивания - задачи построения упорядоченного набора выравниваний-кандидатов, а также в разработанном алгоритме решения этой задачи.
Практическая значимость состоит в разработанных программах1'2, а
1 . org. ru/bio/online/pareto/
2 http: //server2. 1pm. org. ru/stati c/p area/
также в подготовленной базе эталонных выравниваний3, которая может быть использована при оценке точности других алгоритмов выравнивания. Реализация предложенного метода используется при создании опытного образца программного комплекса «СИМВОЛ», разрабатываемого в рамках государственного контракта №07.514.11.4004. Результаты работы использовались при выполнении работ по темам «Сравнительный анализ структур белков и нуклеиновых кислот» (номер государственной регистрации 01.2.00409635), «Математические методы анализа белков и нуклеиновых кислот: связь между последовательностями, структурой и функцией» (номер государственной регистрации 01.2.00952309), а также при выполнении проекта РФФИ 09-04-01053-а «Достоверность и полнота результатов при компьютерном анализе последовательностей биополимеров». Результаты работы можно рекомендовать к использованию для получения выравниваний слабогомологичных последовательностей - такие выравнивания необходимы при решении многих задач биоинформатики.
Апробация результатов. Результаты работы были представлены на международном рабочем совещании RECESS (Мюнхен, декабрь,
г.), международной конференции МССМВ'2011 (Москва, июль,
г.), на семинарах в Институте математических проблем биологии РАН, Московском Государственном Университете, Институте белка РАН, Институте теоретической и экспериментальной биофизики РАН.
Публикации. Основные материалы диссертации изложены в четырех работах общим объемом 47 страниц, из них - три статьи, написанных в соавторстве (общий объем 46 страниц), в том числе две статьи, опубликованных в журналах из списка ВАК (общий объем 32 страницы). Кроме того, опубликованы тезисы сообщения на международной конференции (объем - 1 страница).
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы (85 наименований). Полный объем диссертации составляет 98 страниц, количество рисунков - 16, количество таблиц - 19.
Весовые матрицы замен
Выравнивание аминокислотных и нуклеотидных последовательностей является классическим для биоинформатики методом сравнения последовательностей. Выявляемые при этом сходства часто являются следствием функциональных, структурных или эволюционных взаимосвязей между последовательностями. В 70-е годы XX века, когда сравнивались последовательности относительно небольшой длины, выравнивание производилось вручную, затем были предложены алгоритмы построения выравнивания [1, 2]. Актуальность задачи выравнивания символьных последовательностей обуславливается тем, что для многих белков известны их аминокислотные последовательности, но лишь для малой части из них известны пространственные структуры.
Для приложений важно, насколько алгоритмически полученные выравнивания отражают реальную эволюционную связь между сравниваемыми последовательностями. Количественной мерой этого служит точность выравнивания - доля таких сопоставлений эталонного выравнивания, которые присутствуют в алгоритмическом выравнивании. В качестве эталонных выравниваний аминокислотных последовательностей, как правило, используются выравнивания, основанные на наложении пространственных структур белков, соответствующих этим последовательностям.
Наиболее точным из известных в настоящее время алгоритмов построения глобального парного выравнивания аминокислотных последовательностей является алгоритм Смита-Ватермана[2]. Он основан на построении оптимального выравнивания, то есть выравнивания, для которого достигается максимальное значение соответствующей весовой функции. Тем не менее, для слабогомологичных последовательностей точность выравниваний Смита-Ва-термана невысока.
Существующие на данный момент алгоритмы попарного выравнивания, в частности, алгоритм Смита-Ватермана, требуют задания ряда параметров, выбор значений которых не имеет под собой надежного обоснования. Примером такого параметра является штраф за делецию (удаление) фрагмента; ошибка в выборе его значения приводит к существенному ухудшению точности алгоритмически полученного выравнивания. Одним из путей повышения точности алгоритмически построенных выравниваний является разработка метода выравнивания, который не использует штрафы за делеции, что определяет актуальность темы исследования.
Цель исследования состоит в разработке метода глобального выравнивания биологических последовательностей, который позволяет получать выравнивания, более точные, чем выравнивания Смита-Ватермана. Исходя из поставленных целей, были сформулированы и решены следующие задачи. 1. Предложить новую формализацию задачи выравнивания, в которой не используются штрафы за делеции фрагментов. 2. Разработать эффективный алгоритм решения этой задачи. 3. Создать программную реализацию разработанного алгоритма. -6 — Введение — 4. Провести сравнительное исследование качества выравниваний, полученных с помощью разработанного алгоритма и выравниваний, полученных методом Смита-Ватермана.
Теоретическая значимость исследования заключается в новом варианте задачи выравнивания - задаче построения упорядоченного набора выравниваний-кандидатов, а также в разработанном алгоритме решения этой задачи.
Практическая значимость состоит в разработанных программах [3, 4], а также в подготовленной базе эталонных выравниваний [5], которая может быть использована при оценке точности других алгоритмов выравнивания. Реализация предложенного метода используется при создании опытного образца программного комплекса «СИМВОЛ», разрабатываемого в рамках государственного контракта №07.514.11.4004. Результаты работы использовались при выполнении работ по темам «Сравнительный анализ структур белков и нуклеиновых кислот» (номер государственной регистрации 01.2.00409635), «Математические методы анализа белков и нуклеиновых кислот: связь между последовательностями, структурой и функцией» (номер государственной регистрации 01.2.00952309), а также при выполнении проекта РФФИ 09-04-01053-а «Достоверность и полнота результатов при компьютерном анализе последовательностей биополимеров». Результаты работы можно рекомендовать к использованию для получения выравниваний слабогомологичных последовательностей - такие выравнивания необходимы при решении многих задач биоинформатики
Модельные эталонные выравнивания
Метод парного выравнивания символьных последовательностей биологической природы (первичных структур нуклеиновых кислот и белков) является базовым методом, который лежит в основе многих методов биоинформатики, используемых при функциональном аннотировании геномов [9, 10], а также предсказании вторичной структуры белков и нуклеиновых кислот [11, 12, 13]. Парное выравнивание является ядром многих методов множественного выравнивания последовательностей [14, 15, 16, 17, 18, 19]. Программы парного выравнивания символьных последовательностей входят в состав многих биоинформатических программных пакетов и комплексов [20, 21]. Понятие выравнивания было перенесено в исследование биологических макромолекул из теоретических работ по анализу символьных последовательностей, в частности, работ, связанных с определением расстояния между последовательностями [22, 23]. Эти работы были связаны как с внутренней логикой развития теории алгоритмов, так и с потребностями технических приложений, в частности, анализа звуковых сигналов [24] и сравнения файлов [25].
Применительно к последовательностям биологической природы задача выравнивания последовательностей была сформулирована в 1970 году С.Нидлманом и К.Вуншем [1]. Предложенный ими алгоритм основан на методе динамического программирования и имеет вычислительную сложность О (га гг), где тип- длины сравниваемых последовательностей. Значительное число исследований в области выравнивания биологических последовательностей приходится на 70-е - начало 80-х годов XX века, их обзор приводится в монографии М.Ватермана [26]. Исследования этого периода были направлены на выработку такой формальной постановки задача, которая, с одной стороны, обеспечивала бы получение выравниваний, адекватных с биологической точки зрения, а с другой - допускала построение вычислительно эффективных алгоритмов. Тем не менее, несмотря на предпринятые исследования, до сих пор остается открытым [27] вопрос о выборе весовой функции выравнивания, и в частности - о выборе весов за делеции. В настоящее время широко применяемым стандартом являются предложенные в [28] аффинные веса вида R(l) = GOP + GEP I , где I - длина удаленного фрагмента, a GOP (Gap Opening Penalty) и GEP (Gap Elongation Penalty) - это числовые штрафы за удаление фрагмента целиком и удаление отдельных символов соответственно, которые являются параметрами алгоритмов выравнивания. Выбор значений этих параметров решен эмпирически [29]. Предложенная Т. Смитом и М. Ватерманом [2] постановка задачи, учитывающая удаления фрагментов целиком, позволяет строить не только глобальные, но и локальные выравнивания последовательностей, которые находят сходные участки в сильно различающихся последовательностях.
Для преодоления проблемы выбора весов за делеции, в 1984 году М. Ватерман и его соавторы предложили новую постановку задачи: поиск всех выравниваний, которые являются субопти - мальными, то есть имеющих вес, отличный от оптимального на заданную величину. Постановка задачи и алгоритм ее решения описаны в [30, 31]. Однако, даже при малом значении величины отклонения веса допустимых выравниваний от веса оптимального выравнивания, число субоптимальных выравниваний может быть очень велико, что затрудняет практическое применение данного подхода. Тем не менее, предложенный М. Ватерманом и соавторами подход нашел применение в качестве оценки меры надежности отдельных участков оптимальных выравниваний, определяемой как количество субоптимальных выравниваний, содержащих эти участки [32, 33].
Примерно в то же время была высказана [34] идея о представлении оптимальных выравниваний как функции весовых параметров, однако не был предложен алгоритм решения этой задачи. В начале 90-х годов М. Ватерманом и Д. Гасфилдом были предложены [35, 36, 37] алгоритмы декомпозиции пространства параметров на области, соответствующие отдельным оптимальным выравниваниям, таким образом стало возможным построение всех возможных оптимальных выравниваний с использованием одного из набора значений параметров для каждой области. Недостатком такого подхода является тот факт, что все значения параметров являются равноправными с математической точки зрения, даже несмотря на то, что некоторые из них противоречат биологическому смыслу.
В 1994 году М. А. Ройтбергом была предложена [6] идея использования многокритериального подхода к задаче выравнивания, который является двойственным к параметрическому подходу, предложенному М. Ватерманом и Д. Гасфилдом. В рамках предложенного подхода, каждое выравнивание определяется векторным весом, компонентами которого могут быть суммарный вес за сопоставление, а также количество удаленных символов и их фрагментов, в то время как используемый классическими методами вес выравнивания является линейной комбинацией этих компонент. По сравнению с параметрическим подходом, использование векторного веса имеет ряд преимуществ. Во-первых, он позволяет избежать трудоемкого явного разбиения пространства параметров на однородные области, а во-вторых, в рамках этого подхода естественным образом формулируется задача о выборе биологически адекватного выравнивания. Тем не менее, в предложенном в работе [7] методе остался нерешенным вопрос о биологически корректном выборе выравнивания среди набора Парето-оптимальных выравниваний.
Постановка новой задачи
Дано: — множество символов {алфавит) Л] — последовательности S\ и 5 2 символов из алфавита Л) — квадратная матрица М размерности \Л\ х \Л\ весов замен, модифицированных в соответствии со значением GEP = 1.0. Требуется: построить упорядоченный набор Е(п), состоящий не более чем из п глобальных выравниваний-кандидатов, таким образом, чтобы среди элементов Е(п) было выравнивание как можно более высокой точности.
Приведенная постановка задачи является обобщением задачи построения одного оптимального выравнивания, которая решается, например, алгоритмом Смита-Ватермана. С другой стороны, она является обобщением работ М. А. Ройтберга [7], М. Ватер-мана[35] и Д. Гасфилда [37], в которых рассматривается задача построения множества выравниваний. Отличие предложенной задачи от задач, рассмотренных в цитированных работах, состоит, во-первых, в том, что размер множества выравниваний-кандидатов невелик и заранее определяется пользователем, и, во-вторых, что набор выравниваний-кандидатов упорядочен. Таким образом, пользователь может перебрать все предложенные выравнивания и попробовать использовать каждое из них при решении своей задачи.
Алгоритм и реализация — L.-.i TT, ного подхода при выравнивании последовательностей [7], в рамках которого каждое выравнивание оценивается векторным весом, компонентами которого могут быть, например, суммарный вес за сопоставление, суммарное число удаленных фрагментов и отдельных символов. Аналогом алгоритма, который определяет максимальное значение некоторой линейной весовой функции, является построение Парето-оптимального множества векторных весов, которым соответствуют отдельные выравнивания.
Недостатком такого подхода является тот факт, что размер полученного Парето-множества может быть сколько угодно большим. Это препятствие, во-первых, может оказаться неприемлемым с точки зрения вычислительной сложности при практической реализации, а во-вторых, делает бессмысленным результат, поскольку он содержит такое число выравниваний, среди которых трудно выбрать подходящий вариант.
Как было показано в ходе исследования зависимости точности алгоритма Смита-Ватермана от штрафов за удаление символа и фрагмента, без большого ущерба для точности из компонент векторного веса V = (М, d, д) можно исключить число удаленных символов d, используя модифицированную матрицу весов. Таким образом, алгоритм построения Парето-оптимального множества весов оперирует векторами на плоскости, а не в пространстве, и очевидно, что таких векторов в множестве становится существенно меньше. В подразделе 3.3.2 описан алгоритм, который строит Парето-оптимальное множество векторных весов V = (М, d, д), содержащих компоненту d, однако в данном алгоритме присутствие данной компоненты обусловлено исключительно техническими причинами: ее значение рассматривается только при определении доминирующего вектора в том случае, когда значения компонент М и д совпадают.
Полученное множество Парето-оптимальных выравниваний, тем не менее, все еще содержит достаточно большое (несколько десят ої — Глава 3. Алгоритм и реализация — ков) количество выравниваний. Оно содержит все возможные алгоритмически оптимальные варианты построения выравнивания. Среди них выделяется упорядоченное множество основных выравниваний (см. подраздел 3.3.3), которое содержит только те выравнивания, в которые имеются существенные отличия от других выравниваний в Парето-множестве.
Парето-оптимальных выравниваний Данный алгоритм был предложен в работе [7] и является модификацией метода Смита-Ватермана. Здесь приводятся его краткое описание и некоторые уточнения.
Алгоритм построения множества Парето-оптимальных выравниваний основан на методе динамического программирования. Каждое выравнивание представляется списком «событий», где под событием понимается удаление символа в одной из последовательностей или сопоставление символов. Алгоритм построения Парето-мно-жества выравниваний последовательностей S\ = а\ащг и 52 = 6162... Ь\2 с длинами 1\ и І2 состоит из двух этапов.
На первом этапе (который называют прямым проходом) строится основная и две дополнительные матрицы переходов размерности (Zi +1) х (Z2 +1), в которых строкам соответствуют символы одной последовательности, а столбцам - символы другой. Элементами Tjj основной матрицы Т являются Парето-множества векторных весов (М, d, g) выравнивания начальных последовательностей Si = а\... сії и S = b\.. .bj. Элементами дополнительных матриц ТХ и TY являются веса выравниваний начальных последовательностей в случаях продолжения удаленного фрагмента в первой либо во второй символьной последовательности.
Анализ полученных данных
Задание матриц весов замен
В модуле имеются предопределенные матрицы весов замен семейств РАМ и BLOSUM. Эти матрицы представлены в виде констант, имена которых составлены из имени семейства в нижнем регистре и номера матрицы, который следует сразу после имени, например рат120.
Для того чтобы задать произвольные матрицы, необходимо создать словарь, ключами которого являются пары символов в верхнем регистре, а значениями - вещественные числа, соответствующие весам. Пример создания псевдослучайной матрицы приведен на рисунке 3.14.
Пример использования
На рисунке 3.15 приведен простой пример, который выравнивает две символьные последовательности, и выводит на экран подмножество из шести выравниваний-кандидатов, отмечая их общие части. Применимость к задачам вне области биоинформатики Предложенная реализация метода выравнивания символьных последовательностей поддерживает работу со всеми символами кодировки Unicode, что позволяет использовать ее в задачах обработки естественного языка. Для этого необходимо определить мат -53 — Глава 3. Алгоритм и реализация — рицу весов для используемого алфавита, например состоящего из букв кириллицы, латиницы, знаков пунктуации и других символов, используемых в обрабатываемых текстах. Однако исследование программы PARCA применительно к задачам естественного языка в рамках данной работы не проводилось.
Алгоритмы прямого и обратного проходов метода динамического программирования, используемого программой PARCA, реализованы на языке программирования C++ с использованием библиотеки шаблонов STL, которая является частью стандарта ISO/IEC 14882:2011. Помимо STL, она также использует библиотеки system, f ilesystem и python из набора BOOST [79]. Остальные алгоритмы программы, реализованы средствами PYTHON [78], что не является критичным с точки зрения эффективности ввиду доказанного в подразделе 3.3.4 утверждения 3.
Техника Парето-оптимального выравнивания, в отличии от оптимизации скалярной функции, имеет повышенные требования к оперативной памяти. Пусть средняя длина последовательности равна L, ограничение на число элементов Парето-множества равно R. Будем считать, что вес сопоставления может быть представлен любым, достаточно большим числом, в то время как число удаленных фрагментов и символов не может превышать 2 L, которое заведомо укладывается в диапазон от 0 до 65535. Для возможности проведения обратного прохода метода, необходимо для каждого элемента Парето-множества помнить «историю» его получения в виде направления обратного обхода. Таким образом, хранение одного элемента Парето-оптимального множества, требует 8 + 2 16 +32 = 72бит, или 9 байт. Соответственно, для хранения трех матриц переходов размера L х L, требуется 3 L2 R 9 байт оперативной памяти. Исходя из предположения, что R = 40, а характерное значение L равно 300, следует, что для хранения матриц переходов требуется порядка 100 Мбайт оперативной
Современные операционные системы легко справляются с задачей выделения большого объема памяти приложениям, используя механизм страничной подкачки [80], однако такой подход сильно увеличивает время работы за счет частого обращения к жесткому диску. Для построения матриц переходов на прямом проходе достаточно знать значения только соседних ячеек, а чтение матриц потребуется только на обратном проходе. Организация явного обмена данными с жестким диском, будет более эффективной, чем обмен страниц памяти, реализованный средствами операционной системой, поскольку операционная система выбирает страницы памяти для обмена с жестким диском, не имея предположений о том, какие из них в какой момент потребуются [80, 81]. Таким образом, используя явный файл подкачки, была достигнута эффективность программы PARCA при работе с длинными последовательностями. Подобный способ работы с памятью не является уникальным для PARCA, такую технику часто используют в программах для работы с мультимедийными и графическими данными.
