Бесплатный автореферат и диссертация по биологии на тему

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

ВАК РФ 03.01.09, Математическая биология, биоинформатика

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

005013547

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

ьйШ

Яковлев Виктор Вадимович

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

03.01.09 Математическая биология, биоинформатика

АВТОРЕФЕРАТ

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

1 5 ИДР 1Ш

Москва-2012

005013547

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

Научный руководитель: доктор физико-математических наук,

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

Официальные оппоненты: Андрей Александрович Миронов

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

Александр Владимирович Фаворов кандидат физико-математических наук, Государственный научный центр Российской Федерации ФГУП Государственный научно-исследовательский институт генетики и селекции промышленных микроорганизмов, старший научный сотрудник

Ведущая организация: Федеральное государственное бюджетное

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

Защита состоится « Р£> » ofipa./\iL 2012 г. в АЦ : оо ч. на заседании диссертационного совета Д 002.077.04 на базе Федерального государственного бюджетного учреждения науки Института проблем передачи информации РАН им. A.A. Харкевича по адресу 127994, Москва, ГСП-4, Большой Каретный переулок, д. 19, стр.1.

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

Автореферат разослан «02 » Марго- 2012 г.

Ученый секретарь диссертационного совета Д 002.077.04

доктор биологических наук, профессор СМ^Тм-Л^^ ' И. Рожкова

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

2. Разработать эффективный алгоритм решения этой задачи.

3. Создать программную реализацию разработанного алгоритма.

4. Провести сравнительное исследование качества выравниваний, полученных с помощью разработанного алгоритма и выравниваний, полученных методом Смита-Ватермана.

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

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

Научная новизна. Научная новизна работы состоит в сформулированной новой постановке задачи построения глобального выравнивания (задача построения упорядоченного множества выравниваний-кандидатов), а также в разработанных оригинальных алгоритмах. Предложен алгоритм построения упорядоченного набора выравниваний-кандидатов с временем работы 0(R-L2), где R - ограничение сверху на количество удаленных фрагментов в рассматриваемых выравниваниях, a L- это средняя длина выравниваемых последовательностей.

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

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

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

Практическая значимость состоит в разработанных программах1'2, а

1 http://server2.lpm.org.ru/bio/online/pareto/

2 hltp://server2.lpm.org.ru/static/parca/

также в подготовленной базе эталонных выравниваний3, которая может быть использована при оценке точности других алгоритмов выравнивания. Реализация предложенного метода используется при создании опытного образца программного комплекса «СИМВОЛ», разрабатываемого в рамках государственного контракта №07.514.11.4004. Результаты работы использовались при выполнении работ по темам «Сравнительный анализ структур белков и нуклеиновых кислот» (номер государственной регистрации 01.2.00409635), «Математические методы анализа белков и нуклеиновых кислот: связь между последовательностями, структурой и функцией» (номер государственной регистрации 01.2.00952309), а также при выполнении проекта РФФИ 09-04-01053-а «Достоверность и полнота результатов при компьютерном анализе последовательностей биополимеров». Результаты работы можно рекомендовать к использованию для получения выравниваний слабогомологичных последовательностей - такие выравнивания необходимы при решении многих задач биоинформатики.

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

2010 г.), международной конференции МССМВ'2011 (Москва, июль,

2011 г.), на семинарах в Институте математических проблем биологии РАН, Московском Государственном Университете, Институте белка РАН, Институте теоретической и экспериментальной биофизики РАН.

Публикации. Основные материалы диссертации изложены в четырех работах общим объемом 47 страниц, из них - три статьи, написанных в соавторстве (общий объем 46 страниц), в том числе две статьи, опубликованных в журналах из списка ВАК (общий объем 32 страницы). Кроме того, опубликованы тезисы сообщения на международной конференции (объем - 1 страница).

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы (85 наименований). Полный объем диссертации составляет 98 страниц, количество рисунков - 16, количество таблиц - 19.

Основные положения, выносимые на защиту:

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

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

1 http://server2.lpm.org.ru/static/prefab-p/

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

Определение 1. Сопоставлением позиций в последовательностях ,S'i и Si называется пара целых чисел z=<X\, /-2>, таких что 1 < h < |.S'i и

1 <А,2<|52|.

Определение 2. Выравниванием последовательностей S¡ и S2 называется тройка <S\, Si, А>, где A={<ii, Д>,...,</„, ja>} - последовательность сопоставлений, таких что

1< Ó <...(„< |Я l</i <■:/-.<

Это определение соответствует тому, что г'к-й символ последовательности .Vi сопоставлен j¡¡ -му символу в S2 (к 1, ..., п), а остальные символы в последовательностях Si и Si удалены.

Алгоритм Смита-Ватермана использует следующее определение веса Wsn(Á) выравнивания А:

WS„(A)-M(A) - GEPd(A) - GOPg(A).

Здесь М(А) -- суммарный вес сопоставлений относительно заданной матрицы весов сопоставлений символов; d{A) - число удаленных символов; g(A) - число удаленных фрагментов; GEP (Gap Elongation Penalty) и GOP (Gap Opening Penalty) - параметры алгоритма (соответственно, штраф за удаление символа и штраф за удаление фрагмента).

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

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

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

2. Набор псевдослучайных аминокислотных последовательностей.

имеющих статистическое сходство с реально существующими последовательностями (модельные данные). Эталонные выравнивания для этих последовательностей определяются их построением.

Задача построения корпуса модельных последовательностей возникает из-за ограниченности числа реальных последовательностей, на которых можно проводить испытания. В частности, корпус эталонных выравниваний, полученных из базы данных PREFAB содержит всего 581 пару последовательностей, а корпус модельных последовательностей-12 ООО последовательностей. Результаты, полученные на обоих наборах данных, в целом, совпадают.

Раздел 2.1 посвящен созданной базе эталонных выравниваний PREFAB-P, которая является уточненным вариантом разработанной Р. Эдгаром свободно распространяемой базы данных PREFAB.

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

Как показал проведенный анализ, база данных PREFAB не свободна от недостатков. В ней есть опечатки и отсутствуют данные о степени родства выравниваемых белков. Анализ базы данных состоял из двух этапов: верификации последовательностей и верификации выравниваний. В первом случае имеется в виду сравнение между собой последовательности из PREFAB-выравнивания и соответствующей ей последовательности, полученной из банка PDB. Под верификацией эталонных выравниваний мы подразумеваем сравнение типов структур сравниваемых доменов по классификации SCOP: выравнивания последовательностей, не принадлежащих к одному семейству в смысле SCOP исключались из рассмотрения.

В результате проведенных уточнений, на основе оригинальной базы данных PREFAB, состоящей из 1682 выравниваний, был создан корпус, состоящий из 581 выравнивания. В дополнение к сведениям, содержащимся в базе PREFAB, база данных PREFAB-P содержит сведения о типе пространственной структуры белков по классификации SCOP, наличии не выровненных фрагментов на концах и другие данные. База эталонных выравниваний PREFAB-P доступна4 в виде реляционной базы данных.

4 http://server2.lpni.org.ru/slalic/prefab-p/

Раздел 2.2 посвящен подготовке модельных данных, эти данные сгруппированы по сериям. Каждая серия состоит из 200 пар последовательностей и характеризуется следующими параметрами:

- средняя длина последовательностей LSeq\

- процент совпадений в эталонном выравнивании сравниваемых последовательностей %id\

- суммарное количество вставленных в последовательности фрагментов NGap.

При построении корпуса модельных тестовых данных для этих характеристик были выбраны следующие значения:

- %id = 10, 15,20, 30, 50 и 90% (6 возможных значений);

LSecj = 300, 600 и 1000 (3 возможных значения);

-NGap = 5, 10, 15 и 20 (4 возможных значения) при LSeq-300, и 10, 15, 20 (3 возможных значения) при LSeq=600 и LSeq= 1000;

Эти значения варьировались независимо друг от друга. Таким образом, всего было построено 6-4+6-3+6-3 = 60 серий, что составляет 12 000 выравниваний.

Модельные данные готовились в два этапа.

1 этап - предварительный. На этом этапе производится анализ набора выравниваний реальных белков. В качестве такового использовалась база данных PREFAB; она была разбита на секции в соответствии с уровнем сходства сравниваемых последовательностей от 5 до 95% с шагом в 10%: от 5% до 15%, от 15% до 25% и т. д. В результате анализа для каждой секции была вычислена «вероятность появления удаленного фрагмента данной длины». Говоря более формально, вычислялась следующая величина:

p(l)=N, /N,

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

2 этап. Построение нужного количества тестовых аминокислотных последовательностей с заданными параметрами:

- средняя длина последовательности Lscq;

- процент совпадения в сравниваемых последовательностях %id\

- количество вставленных фрагментов Ngap;

- матрица вероятностей замен MutationProbMatrix;

- статистическая плотность распределения длин вставок р(1).

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

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

Исходная последовательность генерируется в соответствии с Бернулли-евской моделью, параметры которой взяты из работы5. Вероятность наличия мутации в каждой позиции определялась в соответствии со значением параметра %iJ. В качестве матрицы вероятностей замен Mutationl'robMatrix использовалась одна из матриц семейства РАМ6. Основываясь на результатах работы7, использовались следующие матрицы:

- РАМ-480 для %id <10%;

РДМ-360 для 10% <%Ы< 15%;

- РАМ-240 для 15% <%id < 20%;

- РАМ-120 для %id > 20%.

Процесс внесения вставок был организован следующим образом:

1) генерируется заданное число Ngap вставок, длины /¡ которых определяются случайным образом в соответствии с вероятностью />(/,), а их символьные последовательности определяются таким же образом, как и при построении исходной последовательности;

2) полученные фрагменты вставляются в каждую из последовательностей выравнивания равномерно и равновероятно.

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

Lbase - Lseq - Y, h.

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

Третья глава посвящена разработке новых алгоритмов выравнивания и реализации этих алгоритмов. В разделе 3.1. описано исследование зависимости точности выравниваний Смита-Ватермана от значений параметров GOP и GEP. Далее описана новая постановка задачи выравнивания (раздел 3.2), сформулированная в результате этого анализа, и разработанный алгоритм ее решения (раздел 3.3). Программная реализация разработанных алгоритмов в виде программного комплекса PARCA описана в разделе 3.4. Раздел 3.5 посвящен построению выравниваний Сми-та-Ватермана с помощью программы PARCA, этот раздел носит технический характер, поэтому его содержание не разбирается в автореферате подробно.

5 Dayhoff, М.О., Schwartz, R.M. & Orcutt, B.C. (1978) "A model of evolutionary change in proteins." In "Atlas of Protein Sequence and Structure, vol. 5, suppl. 3." M.O. Dayhoff (ed.), pp. 345-352, Natl. Biomed. Res. Found., Washington, DC.

6 http://www.biorecipes.com/Dayhoff/code.html

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

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

1. Строятся выравнивания Смита-Ватермана для каждой пары последовательностей из данной серии и каждой пары значений параметров GEP и GOP; значения параметров меняются независимо друг от друга в диапазонах от 0 до 3 с шагом 0.5 (параметр GEP) и от 0 до 100 с шагом 1 (параметр GOP).

2. Определяется среднее значение точности выравниваний для каждой серии при каждой паре значений GEP и GO Р.

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

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

Эксперименты показали, что значение GEP можно брать равным 1.0 в широком диапазоне эволюционных расстояний (при проценте сходства %id < 50%), см. рис. 1 и табл. 1. Для высокогомологичных последовательностей несколько большая точность достигается при меньших значениях параметра GEP, однако разница в точностях невелика. Значения в таблице 1 были получены со следующими матрицами весов замен: РАМ120 (для последовательностей с %id=30 и выше), РАМ240 (при %id=20), РАМ360 (при %id=15), РАМ480 (при %id=10).

Таблица 1

Значения параметров GOP и GEP, обеспечивающие максимальную среднюю точность выравниваний Смита-Ватермана в различных сериях

экспериментов.

%ID 5 удаленных фрагментов 10 удаленных фрагментов 15 удаленных фрагментов 20 удаленных фрагментов

GOP GEP GOP GEP GOP GEP GOP GEP

10 37 1.0 29 1.0 21 1.0 16 1.0

15 27 1.0 20 1.0 18 1.0 16 1.0

20 16 1.0 16 1.0 14 1.0 11 1.0

30 17 1.0 13 1.0 11 1.0 10 1.0

50 12 1.0 11 1.0 9 1.0 10 0.5

70 12 0.5 9 0.5 9 0.5 10 0.5

90 7 0.0 6 0.0 5 0.0 6 0.0

Типичные кривые точности при различных значениях СЕР показаны на рисунке 1, где отдельные графики (а) - (б) соответствуют различным количествам удаленных фрагментов g(A). Различным линиям на графиках соответствуют различные значения штрафа за удаление символа СЕР (0.0, 0.5, 1.0, 1.5, 2.0, 2.5, 3.0). Полужирная линия на каждом графике соответствует значению СЕР=1.0. Кривая на графиках, которая имеет ярко выраженную низкую точность, соответствует значению СЕР=0.0.

a) %id= 10, я(Л)=5

if/

11/

б) %ich 10, g(A)=20

0.25

0.20 т

:;};' / \

0.15 ¡¡ / /

0 20 40 60

Рис. 1. Типичные кривые зависимости точности выравнивания Смита-Ватермана от штрафа за удаление фрагмента GOP для модельных данных.

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

1) суммарным весом замен (относительно модифицированной матрицы замен) и

2) количеством удаленных фрагментов.

Определения 3-5 и утверждение 1 получены на основе результатов из работы9.

Определение 3. Пусть заданы последовательности S¡ и S2, матрица весов замен W и значение параметра СЕР. Векторным весом У (Л) выравнивания А называется величина

F(A)-<M(A), -g(A)>, (1)

где к - 2, М(А) - суммарный вес сопоставлений в соответствии с матрицей весов IV, модифицированной относительно значения СЕР, a g(A) -количество удаленных фрагментов.

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

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

Определение 4. Выравнивание А\ доминирует над выравниванием Аг, если выполнено

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

Выравнивание Л называется Парето-оптимальпым, если никакое выравнивание не доминирует над ним. Вес <М, называется Парето-оптимальпым, если существует такое выравнивание А, что

У(А)=<М, %>.

Определение 5. Набор выравниваний называется Парето-опти-мальным, если в этом наборе для каждого Парето-оптмального веса <М, ц> существует такое выравнивание Л, что У(А)- <М,^>.

Утверяедение 1. Пусть выравнивание Л является оптимальным выравниванием Смита-Ватермана относительно весовой матрицы IV, штрафа за удаление символа СЕР и некоторого значения штрафа за удаление фрагмента. Тогда выравнивание А является Парето-оптимальным.

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

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

Дано:

- две биологические последовательности;

- матрица весов замен (говоря неформально, одна из стандартных весовых матриц, модифицированная в соответствии с заданным значением параметра ОК1у).

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

Определение 6. Точностью набора выравниваний-кандидатов считается точность наилучшего из выравниваний этого набора.

Приведенная постановка задачи является обобщением задачи построения одного оптимального выравнивания, которая решается, например, алгоритмом Смита-Ватермана. С другой стороны, она является обобщением цитированной выше работы9, а также работ М. Ватермана, Д. Гасфилда и других авторов, в которых рассматривается задача построения множества выравниваний. Отличие предложенной задачи от задач, рассмотренных в цитированных работах, состоит, во-первых, в том, что размер множества выравниваний-кандидатов невелик и заранее определяется пользователем, и, во-вторых, что набор выравниваний-кандидатов упорядочен. Таким образом, пользователь может перебрать все

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

В диссертации предложен алгоритм решения сформулированной выше задачи; этот алгоритм состоит из двух этапов. На первом этапе строится набор Парето-оптимальных выравниваний. Алгоритм выполнения этого этапа, в целом, следует цитированной выше работе, некоторые уточнения описаны в диссертации. Время выполнения этого этапа -О{К-Ь2) операций, используемая память - 0(Л7,2) байт. Здесь Я - априорное ограничение на максимальное количество удаленных фрагментов в просматриваемых выравниваниях.

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

Рис. 2. Пример графика зависимости суммарного веса сопоставлений M(g) от числа удаленных фрагментов g.

Пусть A(g)......Парето-оптимальное выравнивание, содержащее g удаленных фрагментов, M(g) - суммарный вес сопоставлений в выравнивании /<(g); Положим (для g> 1):

dM(g) = Ai(g)-Aife-l).

Тангенсы углов наклона отрезков, примыкающих к точке T(g) будут равны соответственно tgk/, = dM(g)!a и tgr/g/„ = dM(g+l)/a, здесь a -масштабный коэффициент. В настоящей работе он принят равным 20 (это число подобрано эмпирически, результаты не зависят от изменения коэффициента в очень широких пределах). Тангенс угла между отрезками, примыкающими к точке T(g), равен

tg(g) = (tgleft' Щпф,)1{1+Щ,е(, ■ tgngk.) =

= (dM(g) - dM(g+1)) / (fl2 + dM(g) ■ dM(g+l))

Парето-оптимальное выравнивание A(g) будем называть основным, если ¿»-точка локального максимума в последовательности {tg(g)}.

Основные выравнивания будем считать упорядоченными по убыванию величины tg(g), через Е(п) будем обозначать набор из п первых основных выравниваний. На рис. 2 числами обозначены точки, соответствующие выравниваниям-кандидатам, вошедшим в набор Л'(6), каждое число соответствует порядковому номеру выравнивания в наборе.

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

Утверждение 2. Предложен алгоритм построения набора выравниваний-кандидатов с временем работы 0(R-L2) и использующий память О (R-L2).

Раздел 3.4 посвящен реализации предложенных алгоритмов - программному комплексу PARCA (от PAReto CAndidate). Программный комплекс реализован частично на языке С++ (построение Парето-опти-мального множества выравниваний), и частично - на языке Python (все остальные алгоритмы). Такое решение, с одной стороны, эффективно использует вычислительные ресурсы, а с другой - позволяет добиться гибкости как при проведении вычислительных экспериментов, так и при интеграции с другими программными пакетами.

Исходные тексты программного комплекса распространяются под открытой лицензией MIT и являются общедоступными10. Комплекс может использоваться как в UNIX-подобных системах, так и на компьютере под управлением операционных систем Windows ХР/7. Помимо исходных текстов программ, поставка комплекса включает в себя готовые к работе пакеты для openSUSE и Fedora Linux, а также программу для использования в среде Windows. Возможно использование комплекса с другими UNIX-подобными системами, например MacOS X или FreeBSD, в поставке исходных текстов прилагается инструкция по сборке программы для этих систем.

Помимо использования программы на локальном компьютере, комплекс PARCA может использоваться с помощью WEB-интерфейса, доступного на сервере лаборатории прикладной математики ИМПБРАН11. Это WEB-приложение поддерживает как построение списка выравниваний кандидатов, так и сервисные функции - просмотр построенных выравниваний и их хранение.

Архитектурно комплекс PARCA состоит из следующих компонент.

1. Библиотека, оформленная в виде РуШоп-модуля, которая может быть использована в качестве компоненты более крупного программного комплекса. Эта библиотека является платформозависимой и поставляется в вариантах для Windows и Linux.

10 http://server2.Ipm.org.ru/static/parca/

11 htip://server2. lpm.org. ru/bio/onlme/pareto/

2. Консольная программа parca, которая является программной оболочкой над библиотекой комплекса, предназначенной для использования из командной строки UNIX-подобной системы или Windows.

3. Веб-приложение, работающее на Linux-сервере, и предоставляющее возможность удаленной работы с программой, используя браузер. Данное веб-приложение реализовано с использованием инструментальных средств Django.

В четвертой главе описаны методика проведения численных экспериментов и их результаты. Все эксперименты производились на сервере лаборатории прикладной математики ИМПБ РАН под управлением openSUSE Linux 64-bit, с 4-х ядерным процессором Intel Core i5 и 8 гигабайтами оперативной памяти. Поскольку предложенный алгоритм не был спроектирован с учетом возможности параллельного вычисления, эффективное использование всех ядер процессора обеспечивалось одновременным запуском нескольких различных серий экспериментов.

Эксперименты состояли из 60 серий, две из которых были посвящены работе с реальными последовательностями (581 пара последовательностей из базы PREFAB-P) с использованием одной из матриц семейства РАМ, и с использованием матрицы BLOSUM-62. Остальные серии экспериментов проводились с модельными последовательностями. В каждой такой серии анализировались 200 пар последовательностей, серии отличались друг от друга процентом начального сходства, числом удаленных фрагментов и длиной сравниваемых последовательностей.

Методика проведения вычислительных экспериментов с каждой серии (в том числе - в экспериментах с реальными последовательностями) состояла в следующем:

1. Для каждой пары последовательностей строится набор Парето-оп-тимальных выравниваний. Значение параметра R принималось равным 40. В качестве матриц весов замен использовались матрицы семейства РАМ с эволюционным числом: 480 - для последовательностей с уровнем начального сходства (%id) от 7 до 12%, 360 - от 13 до 17%, 240 - от 17 до 28%, и 120 при уровне начального сходства более 28%. Для последовательностей из базы данных PREFAB-P были также проведены отдельные эксперименты с матрицей весов BLOSUM-62. Поскольку данный шаг является вычислительно трудоемким, то все внутреннее представление этого этапа сохраняется на диске (dump состояния). Это неоднократно использовалось позже, поскольку позволяло проводить различные эксперименты, не выполняя заново длительную процедуру получения множества Парето-оптимальных выравниваний. Вычисляются характеристики каждого Парето-оптимального выравнивания, в том числе -точность и достоверность (доля сопоставлений алгоритмического выравнивания, которые присутствуют в эталонном выравнивании). Как показали проведенные предварительные эксперименты, достоверность гло-

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

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

В ходе компьютерных экспериментов сравнивались полученные точности наборов основных выравниваний, состоящих из трех элементов (набор /:(3)) и шести элементов (набор Е(6)), с точностью соответствующих выравниваний Смита-Ватермана при значениях штрафов, приведенных в табл. 1. Данные сравнения точности наборов выравниваний-кандидатов с точностями выравниваний Смита-Ватермана, которые были определены на корпусе модельных данных со средней длиной последовательности 300, приведены в табл. 2. Эти данные согласуются с результатами выравниваний последовательностей с длинами 600 и 1000.

Результаты аналогичных экспериментов для последовательностей из базы данных PREFAB-P приведены в табл. 3. Здесь были проведены эксперименты как с одной из матриц семейства РАМ (конкретная матрица выбиралась в соответствии со степенью сходства сравниваемых последовательностей, см. раздел 4.2 диссертации), так и с использованием матрицы BLOSUM-62 - лучшей «универсальной» матрицей замен.

В таблицах 2 и 3 столбец SW соответствуют точностям выравниваний Смита-Ватермана; эволюционные значения используемых в ходе экспериментов матриц семейства РАМ приведены в квадратных скобках после соответствующих уровней сходства (столбец %id). Точностям выравниваний с использованием матрицы BLOSUM-62 в табл. 3 соответствует столбец BS-62.

Как видно из результатов, предложенный в диссертации метод имеет выигрыш в точности по сравнению с методом Смита-Ватермана в тех случаях, когда выравниваются слабогомологичные последовательности (процент сходства %id < 30). Для высокогомологичных последовательностей, использование метода построения выравниваний-кандидатов не имеет превосходства в точности. Эта закономерность характерна как для модельных последовательностей, так и для реальных исходных данных из базы данных PREFAB-P.

Таблица 2

Сравнение средней точности основных наборов £'(3), Л'(6) со средними

точностями субэталонных выравниваний и выравниваний _______С\пп а-Ватср\1а11а^для модельных данных.___________

.....101480 — 8\¥ , 0.38 т____ 0.42 т 0.43 Субэтал. выр. 0.46

15 |360 0.54 h 0.57 0.59 0.61

20 Г240 0.75 0.76 0.77 0.79

30 [120 0.88 0.88 0.89 0.90

Таблица 3

Сравнение средней точности основных наборов Е{3), Е{6) со средними

точностями субэталонных выравниваний и выравниваний Смита-Ватермана для последовательностей из базы данных РЛЕРАВ-Р.

°/М г /{(3) т Субэтал. выр.

РАМ В 3-62 РАМ вБ-бг^ РАМ В8-62 РАМ В8-62

7..12 Г4801 0.17 0.21 0.20 0.23 0.22 0.26 0.25 0.32

12..17 Г3601 0.28 0.33 0.33 0.41 0.35 0.43 0.38 0.46

17..28 [240] "" >28 [1201 0.58 0.58 0.63 0.64 0.64 0.65 0.67 0.67

0.90 0.90 0.90 0.90 0.90 0.91 0.91 0.92

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

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

В заключении приведены основные результаты, полученные в диссертации:

¡.Предложена новая постановка задачи глобального выравнивания биологических последовательностей - задача построения заданного количества ранжированных выравниваний-кандидатов.

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

ментов. Время работы алгоритма составляет 0(R-L2), где /^-ограничение сверху на количество удаленных фрагментов в рассматриваемых выравниваниях, L — ограничение сверху на Длину сравниваемых последовательностей.

3. Предложенный алгоритм реализован в виде общедоступного программного комплекса PARCA и соответствующего веб-сервиса, доступного по адресу: http://server2.1pm.org.ru/bio/online/pareto

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

5. Показано, что наилучшее по точности выравнивание Смита-Ва-термана в случае слабогомологичных последовательностей и использования матриц семейства РАМ получается при значении параметра GHP = 1.0.

6. Построена база данных эталонных выравниваний PREFAB-P, которая может быть использована для оценки точности различных алгоритмов парного глобального выравнивания последовательностей.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1.В. В. Яковлев, М. А. Ройтберг. Увеличение точности глобального выравнивания аминокислотных последовательностей с помощью построения набора выравниваний-кандидатов. // Биофизика, 2010. Т. 55, N6.-С. 965-975.

2. И. В. Поверенная, М. А. Ройтберг, В. В. Яковлев. Использование программы PARCA для выравнивания аминокислотных последовательностей. // Информационные процессы, 2011. Т. 11, N 4. - С. 510-519.

3. Т. В. Астахова, И. В. Поверенная, М. А. Ройтберг, В. В. Яковлев. Верификация базы эталонных выравниваний PREFAB. // Биофизика, 2012.Т. 57,N2.-С. 205-211.

4. Poverennaya I., Lobanov M., Yacovlev V., Roytberg M.. Using of PREFAB for analysis of amino-acid sequence alignment algorithms. Proc, MCCMB'll.P. 327.

Подписано в печать 01 марта 2012 г.

Формат 60x90/16

Объём 1,00 п. л.

Тираж 100 экз.

Заказ №010312420

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

ИНН/КПП 7728572912У772801001

Адрес: г. Москва, улица Ивана Бабушкина, д. 19/1.

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

http://www.univerprmi.ru

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

61 12-1/699

РОССИЙСКАЯ АКАДЕМИЯ НАУК Федеральное государственное бюджетное учреждение науки Институт математических проблем биологии

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

Яковлев Виктор Вадимович

Методы выравнивания биологических

последовательностей, не использующие штрафы за делеции

03.01.09 - Математическая биология, биоинформатика

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

Научный руководитель доктор физико-математических наук

Ройтберг М. А.

Москва - 2012

Оглавление

Введение......................................................................5

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

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

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

1.3. Теоретическая и практическая значимость................7

2. Основные понятия....................................................7

2.1. Выравнивания последовательностей........................7

2.2. Многокритериальное выравнивание........................9

2.3. Меры качества выравниваний..............................10

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

Глава 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. База данных РИЕРАВ-Р..............................................25

2.1.1. Общие сведения ..............................................25

2.1.2. Методика подготовки базы РЯЕРАВ-Р....................26

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. Анализ выравниваний из РЫЕКАВ-Р ............... 70

4.4. Обсуждение результатов ............................................72

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

Список таблиц................................ 89

Литература....................................................................91

Введение

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

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

Выравнивание аминокислотных и нуклеотидных последовательностей является классическим для биоинформатики методом сравнения последовательностей. Выявляемые при этом сходства часто являются следствием функциональных, структурных или эволюционных взаимосвязей между последовательностями. В 70-е годы XX века, когда сравнивались последовательности относительно небольшой длины, выравнивание производилось вручную, затем были предложены алгоритмы построения выравнивания [1, 2]. Актуальность задачи выравнивания символьных последовательностей обуславливается тем, что для многих белков известны их аминокислотные последовательности, но лишь для малой части из них известны пространственные структуры.

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

Наиболее точным из известных в настоящее время алгоритмов построения глобального парного выравнивания аминокислотных последовательностей является алгоритм Смита-Ватермана[2]. Он основан на построении оптимального выравнивания, то есть выравнивания, для которого достигается максимальное значение соответствующей весовой функции. Тем не менее, для слабогомологичных последовательностей точность выравниваний Смита-Ва-термана невысока.

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

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

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

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

2. Разработать эффективный алгоритм решения этой задачи.

3. Создать программную реализацию разработанного алгоритма.

4. Провести сравнительное исследование качества выравниваний, полученных с помощью разработанного алгоритма и выравниваний, полученных методом Смита-Ватермана.

1.3. Теоретическая и практическая значимость

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

Практическая значимость состоит в разработанных программах [3, 4], а также в подготовленной базе эталонных выравниваний [5], которая может быть использована при оценке точности других алгоритмов выравнивания. Реализация предложенного метода используется при создании опытного образца программного комплекса «СИМВОЛ», разрабатываемого в рамках государственного контракта №07.514.11.4004. Результаты работы использовались при выполнении работ по темам «Сравнительный анализ структур белков и нуклеиновых кислот» (номер государственной регистрации 01.2.00409635), «Математические методы анализа белков и нуклеиновых кислот: связь между последовательностями, структурой и функцией» (номер государственной регистрации 01.2.00952309), а также при выполнении проекта РФФИ 09-04-01053-а «Достоверность и полнота результатов при компьютерном анализе последовательностей биополимеров». Результаты работы можно рекомендовать к использованию для получения выравниваний слабогомологичных последовательностей - такие выравнивания необходимы при решении многих задач биоинформатики.

2. Основные понятия

2.1. Выравнивания последовательностей

Пусть даны символьные последовательности 51, 52 в некотором алфавите. Введем формальное определение их выравнивания.

Определение 1. Сопоставлением позиций в последовательностях Si и S2 называется пара целых чисел (Ai, Л2), таких что

l<Ai<|Si|, 1<Л2<|52|.

Определение 2. Выравниванием последовательностей Si и S2 называется тройка (Si, S2, А), где А — {(ii,ji), ..., (imjn)} - последовательность сопоставлений, таких что

1 < к < - ..in < |Si|, 1 <ji < ...jn < |S2|.

Это определение соответствует тому, что г^-я позиция последовательности Si сопоставлена jk-R позиций в S2, где к — 1,... ,п, а остальные символы в последовательностях Si и S2 удалены.

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

Алгоритм Смита-Ватермана использует следующее определение веса Wsw(А) выравнивания А [2]:

Wsw(А) - М(А) - GEP • d(А) - GOP • д(А),

где где М(А) - суммарный вес за сопоставления символов, полученный на основании весовой матрицы М, d(А) - число удаленных символов, д(А) - число удаленных непрерывных фрагментов символов. GOP (Gap Opening Penalty) и GEP (Gap Elongation P enalty) - соответственно штраф за удаление фрагмента и штраф за удаление символа, которые являются параметрами алгоритма.

2.2. Многокритериальное выравнивание

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

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

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

У(А) = <М(А), -д{А)),

где к = 2, М(А) - суммарный вес сопоставлений, а д{А) - количество удаленных фрагментов. Другим возможным вариантом векторного веса может быть функция

У*(А) = (М(А), -б.{А), -д{А)),

где к = 3, М(А) и д(А) имеют тот же смысл, что и в предыдущем примере, а б?(А) - суммарная длина удаленных фрагментов (или число удаленных символов).

Понятие Парето-оптималъного множества, впервые предложенное социологом и экономистом В. Парето в работе [8], вводится через определение доминирования одного векторного веса над другим. Применительно к задаче выравнивания последовательностей, соответствующие определения были введены в работе [7].

Определение 4. Выравнивание Ai, имеющее векторный вес

V(Ai) = (M(Ai), -g{Ах))

доминирует над выравниванием А2 с векторным весом

V(A2) = (М(А2), -д{А2)) ,

если

M{Al)>M(A2)^g{Al)<g{A2),

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

Выравнивание А называется Парето-оптимальным, если никакое выравнивание не доминирует над ним. Вес (М, д) называется Парето-оптимальным, если существует такое Парето-оптималь-ное выравнивание А, что V(A) = (М,д).

Определение 5. Набор выравниваний называется Парето-оптимальным, если в этом наборе для каждого Парето-оптимального веса (М,д) существует такое Парето-оптимальное выравнивание А, что V(A) = (М,д).

2.3. Меры качества выравниваний

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

Стандартными количественными оценками качества выравниваний являются точность (обозначается Асс - от accuracy), и достоверность (Conf, - от confidence).

Определение 6. Пусть для выравнивания А существует соответствующее эталонное выравнивание С. Тогда точностью выравнивания А относительно эталонного выравнивания в называется величина

где |АпС| - число сопоставлений, присутствующих в обоих выравниваниях, |0| — число сопоставлений в эталонном выравнивании.

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

Определение 7. Достоверностью выравнивания А относительно эталонного выравнивания С называется величина

_ |АПС|

СопЦ А) = ,

где |А П С| - число сопоставлений, присутствующих в обоих выравниваний, |А| - число сопоставлений в алгоритмическом выравнивании.

Достоверность показывает, какая доля сопоставлений в алгоритмическом выравнивании является «правильной».

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

Определение 8. Точностью набора выравниваний-кандидатов считается максимальная точность выравниваний из этого набора.

Определение 9. Достоверностью набора выравниваний-кандидатов считается максимальная достоверность выравниваний из этого набора.

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

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

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

Третья глава посвящена описанию новых алгоритмов выравнивания и реализации этих алгоритмов.

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

В заключении приведены основные результаты, полученные в диссертации.

Глава 1

Обзор литературы

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

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

Метод парного выравнивания символьных последовательностей биологической природы (первичных структур нуклеиновых кислот и белков) является базовым методом, который лежит в основе многих методов биоинформатики, используемых при функциональном аннотировании геномов [9, 10], а также предсказании вторичной структуры белков и нуклеиновых кислот [11, 12, 13]. Парное выравнивание является ядром многих методов множественного выравнивания последовательностей [14, 15, 16, 17, 18, 19]. Программы парного выравнивания символьных последовательностей входят в состав многих биоинформатических программных пакетов и комплексов [20, 21]. Понятие выравнивания было перенесено в исследование биологических макромолекул из теоретических работ по анализу символьных последовательностей, в частности, работ, связанных с определением расстояния между последовательностями [22, 23]. Эти работы были связаны как с внутренней логикой развития теории алгоритмов, так и с потребностями технических приложений, в частности, анализа звуковых сигналов [24] и сравнения файлов [25].

Применительно к последовательностям биологической природы задача выравнивания последовательностей была сформулирована в 1970 году С.Нидлманом и К.Вуншем [1]. Предложенный ими алгоритм основан на методе динамического программирования и имеет вычислительную сложность О (га • п), где тип- длины сравниваемых последовательностей. Значительное число исследований в области выравнивания биологических последовательностей приходится на 70-е - начало 80-х годов XX века, их обзор приводится в монографии М.Ватермана [26]. Исследования этого периода были направлены на выработку такой формальной постановки задача, которая, с одной ст