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

• Яковлев, Виктор Вадимович
• кандидат физико-математических наук
• 2012

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

Оглавление

Введение

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

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

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

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

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

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

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

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

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

Глава 1. Обзор литературы

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

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

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

1.1.3. Весовые матрицы замен

1.2. Базы данных эталонных выравниваний

1.2.1. Общие сведения

1.2.2. Обзор существующих баз данных

Глава 2. Эталонные выравнивания

2.1. База данных РИЕРАВ-Р

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

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

2.1.3. Структура базы данных PREFAB-Р

2.2. Модельные эталонные выравнивания

2.2.1. Общие сведения

2.2.2. Предварительные эксперименты

2.2.3. Общая схема построения набора модельных данных

2.2.4. Внесение мутаций-«замеп» в символьные последовательности

Глава 3. Алгоритм и реализация

3.1. Исследование алгоритма Смита-Ватермана

3.1.1. Общие сведения

3.1.2. Методика проведения экспериментов

3.1.3. Результаты

3.2. Постановка новой задачи

3.2.1. Исключение параметра GEP

3.2.2. Формальная постановка задачи

3.3. Решение задачи построения набора выравниваний-кандидатов

3.3.1. Общие сведения

3.3.2. Алгоритм построения множества Парето-оптимальных выравниваний

3.3.3. Алгоритм выделения основных выравниваний

3.3.4. Оценка вычислительной сложности алгоритмов

3.4. Реализация

3.4.1. Общие сведения

3.4.2. Пользовательский интерфейс комплекса PARCA

3.4.3. Программный интерфейс комплекса PARCA

3.4.4. Детали реализации

3.5. Вспомогательные алгоритмы

3.5.1. Определение штрафа GOP для соответствующих выравниваний Смита-Ватермана

3.5.2. Выделение общей части основных выравниваний

Глава 4. Компьютерные эксперименты

4.1. Методика

4.1.1. Общие сведения

4.1.2. Построение выравниваний

4.1.3. Анализ полученных данных

4.2. Анализ модельных данных

4.3. Анализ выравниваний из РЫЕКАВ-Р

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

Заключение

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

Литература

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

Введение

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. Предложена новая постановка задачи глобального выравнивания биологических последовательностей - задача построения заданного количества ранжированных выравниваний-кандидатов.

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

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

3. Предложенный алгоритм реализован в виде общедоступного программного комплекса PARCA [3] и соответствующего веб-сервиса [4].

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

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

6. Построена база данных эталонных выравниваний Р11ЕЕАВ-Р [5], которая может быть использована для оценки точности различных алгоритмов парного глобального выравнивания последовательностей .

Список литературы диссертационного исследования кандидат физико-математических наук Яковлев, Виктор Вадимович, 2012 год

Литература

[1] NeedlemanS. В., WunschC. D. A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol. 1970, vol. 48, pp. 443-453

[2] Smith T. F., Waterman M.S. Identification of common molecular subsequences. J. Mol. Biol. 1981, vol. 147, pp. 195-197

[3] http://server2.1pm.org.ru/static/download/parca/

[4] http://server2.1pm.org.ru/bio/pareto/

[5] http://server2.lpm.org.ru/static/prefab-p/

[6] Ройтберг M. A. IJapemo-оптимальные выравнивания символьных последовательностей. Пущино: ОНТИ НЦБИ, 1994. Препринт, 10 с.

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

[8] Pareto V. Manual of political economy. New York: A. M. Kelley, 1972

[9] AsthanaS., RoytbergM., StamatoyannopoulosJ., SunyaevS. Analysis of sequence conservation at nucleotide resolution. PLoS Comput Biol. 2007, vol.3, N. 12, p. 254

[10] Корзинов О. M., Астахова Т. В., Власов П. К., Ройтберг М. А. Статистический анализ участков ДНК в окрестности сайтов сплайсинга. Молекулярная биология. 2008, т. 42, №1, стр. 150-162

[11] LeskA.M. Introduction to protein architecture. Oxford, N.Y.: Oxford Univ. press. 2001. P.360

[12] PirovanoW., FeenstraK. A., HeringaJ. The meaning of alignment: lessons from structural diversity. BMC Bioinformatics. 2008, vol. 9, p. 556

[13] KisterA.E., RoytbergM.A., ChothiaC., Gelfandl.M. The sequence determinants of cadherin molecules. Protein Science. 2001, vol. 10, pp. 1801-1810

[14] NotredameC., HigginsD.G., HeringaJ. T-Coffee: a novel method for fast and accurate multiple sequence alignment. J. Mol. Biol. 2000, vol. 302, pp. 205-217

[15] Thompson J. D., HigginsD.G., Gibson T.J. CLUSTALW: improving the sensitivity of progressive multiple sequence alignment through sequence eighting, position-specific gap penalties and weight matrix choice. Nucleic Acids Res. 1994, vol. 22, pp. 473-480

[16] KatohK., KumaK., TohH., MiyataT. MAFFT version5: Improvement in Accuracy of Multiple Sequence Alignment. Nucleic Acids Research. 2005, vol.3, pp. 511-518

[17] Edgar R. C. MUSCLE: multiple sequence alignment with high accuracy and high throughput. Nucleic Acids Research. 2004, vol. 32, N. 5, pp. 1792-1797

[18] Edgar R. C, BatzoglouS. Multiple Sequence Alignment. Current Opinion in Structural Biology. 2006, vol. 16, pp. 368-373

[19] Russell D., OutH., SayoodK. Grammar-based distance in progressive multiple sequence alignment. BMC Bioinformatics. 2008, vol. 9, p. 306

[20] Rice P., LongdenL, BleasbyA. EMBOSS: The European Molecular Biology Open Software Suite Trends in Genetics 2000, vol. 16, N. 6, pp. 276-277

[21] NazipovaN. N., ShabalinaS. A., Ogurtsov A. Yu., Kondrashov A. S., RoytbergM.A., BuryakovG.V., VernoslovS.E. SAMSON: a software package for the biopolymer primary structure analyses. Comput. Appl. Biosci. 1995, vol. 11, N. 4, pp. 423-426

[22] ЛевенштейнВ. И. Двоичные коды с исправлением выпадений, вставок и замещений символов. Доклады Академий Наук СССР. 1965. Т. 163, №4. С. 845-848

[23] UlamS.M. Some Ideas and Prospects in Biomathematics. Annu Rev Biophys Bioeng. 1972, vol. 1, p. 277

[24] KruskalJ.B. An Overview of Sequence Comparison: Time Warps. String Edit and Macromoleculas. SIAM Rev. 1983, vol. 25, N. 26, pp. 201-238

[25] RochkindM. J. The Source Code Control System. IEEE Transactions on Software Engineering. 1975, vol. 1, N. 4, pp. 364-370

[26] Waterman M.S. Introduction to Computational Biology. London: Chapman and Hall Press. 1995

[27] Cartwright. R. A. Logarithmic gap costs decrease alignment accuracy. BMC Bioinformatics. 2006, vol. 7, p. 527

[28] GonnetG. H, Cohen M. A, BennerS. A. Exhaustive matching of the entire protein sequence database. Science. 1992, vol. 256, N. 5062, pp. 1443-1445

[29] ZvelebilM., BaumJ.O. Understanding bioinformatics. London: Garland Science. 2007. 800 p.

[30] Waterman M.S. Sequence alignments in the neighborhood of the optimum with general application to dynamic programming. PNAS. 1983, vol. 80, N. 10, pp. 3123-3124

[31] ByersT. M., Waterman M.S. Determining all optimal and near-optimal solutions when solving shortest path problems by dynamic programming. Oper Res. 1984, vol. 32, pp. 1381-1384

[32] VingronM., ArgosP. Determination of reliable regions in protein sequence alignments. Protein Engineering. 1990, vol. 3, N. 7, pp. 565-569

[33] ZukerM. Suboptimal sequence alignment in molecular biology. Alignment with error analysis. J. Mol. Biol. 1991, vol.221, N. 2, p. 403

[34] Fitch W. M., Smith T. F. Optimal sequence alignments. Proc. Natl. Acad. Sci. USA. 1983, vol.80, pp. 1382-1386

[35] Waterman M. S., EggertM., Lander E. Parametric sequence comparisons. Proc.Nat. Acad. Sci. USA. 1992, vol.89, pp. 6090-6093

[36] Fernandez-Baca. D., SrinivasamS. Constructing tile minimization diagram of a two-parameter problem. Operat. Res. Letters. 1991, vol.10, pp. 87-93

[37] GusfieldD., BalasubramianK., NaorK. Proc. 3rd Ann. ACM-SIAM Discrete Algorithms. 1992, pp. 432-439

[38] Bellman R. On the theory of dynamic programming. Proc. Nat. Acad. Sci. U.S.A. 1952, vol.38, pp. 716-719

[39] KleeneS.C., Representation of events in nerve nets and finite automata. Shannon C.E., McCarthy J. (Eds.), Automata Studies, Princeton University Press. 1956. P. 3-41

[40] McNaughtonR., YamadaH. Regular expressions and state graphs for automata. IRE Transactions on Electronic Computer. 1960, vol.9, N. 1. pp.39-47

[41] Kramers H. A., Wannier G. H. Statistics of the one-dimensional ferromagnet. Phys. Rev. 1941, vol.60, pp. 252-276

[42] AhoA., HopcroftJ., UlmanJ. The design and analysis of computer algorithms. Addison-Wesley, Reading, MA., USA. 1974. P.470

[43] GelfandM.S., Podolsky L. I., AstakhovaT. V., RoytbergM.A. Prediction of the exon-intron structure and multicriterial optimization. Bioinformatics and Genome Research (H.A.Lim, C.R.Cantor, eds.). World Scientific Publ. Co., Singapore. 1995. PP. 173-183

[44] RoytbergM.A., AstahovaT.V., GelfandM.S. Combinatorial approaches to gene recognition. Computers and Chemistry. 1998, vol. 1, N. 21, pp. 229-236

[45] RamenskyV.E., MakeevV.Ju., RoytbergM.A., Tumanyan.V.G. DNA segmentation through the Bayesian approach. J. Comput. Biol. 2000, vol. 7, N. 1-2, p. 215-31

[46] Ramensky V.E., MakeevV. Y., RoytbergM. A., TumanyanV. G. Segmentation of long genomic sequences into domains with homogeneous composition with BASIO software. Bioinformatics. 2001, vol. 17, N. 11, pp. 1065-1066

[47] Vogt G., EtzoldT., ArgosP. An assessment of amino acid exchange matrices in aligning protein sequences: the twilight zone revisited. J. Mol. Biol. 1995, vol. 249, pp. 816-831

[48] GribskovM, VeretnikS. Identification of sequence pattern wit hprofile analysis. Methods Enzymol. 1996, vol. 266, pp. 198 -212

[49] Sunyaev S. R., Bogopolsky G. A., OleynikovaN. V., VlasovP.K., FinkelsteinA.V., RoytbergM.A. From analysis of protein structural alignments toward a novel approach to align protein sequences. Proteins. 2004, vol. 54, pp. 569-582

[50] Huang X., ChaoK.-M. A generalized global alignment algorithm. Bioinformatics. 2003, vol. 19, no. 2, pp. 228-233

[51] DayhoffM. O., Schwartz R. M., Orcutt B. C. A model of evolutionary change in proteins. Atlas of Protein Sequence and Structure. 1978, vol. 5, suppl. 3, pp.345-352

[52] http://www.biorecipes.com/Dayhoff/code.html

[53] Polyanovsky V., Roytberg M., Tumanyan V. Reconstruction of genuine pair-wise sequence alignment. Computational Biology. 2008, vol. 15, N. 4. pp. 379-391

[54] HenikoffS., HenikoffJ. G. Amino Acid Substitution Matrices from Protein Blocks. PNAS. 1992, 89(22), pp. 10915-10919

[55] Smith R. F. and Smith T.F. Pattern-induced multi-sequence alignment (PIMA) algorithm employing secondary structure-dependent gap penalties for use in comparative protein modelling. Protein Eng. 1992, vol. 5, pp. 35-41

[56] DeperieuxE., BaudouxG., BriffeuilP., ReginsterL, DeBolleX., VinalsC. and FeytmansE. MATCH-BOX server: a multiple sequence alignment

tool placing emphasis on reliability. Comput. Appl. BioSci. 1997, vol. 13, pp.249-256

[57] Thompson J. D., GibsonT. J, PlewniakF., JeanmouginF. and HigginsD.G. The CLUSTAL_X windows interface: flexible strategies for multiple sequence aligment aided by quality analysis tools. Nucleic Acids Res. 1997, 24, pp. 4876-4882

[58] Edgar R. C. Quality measures for protein alignment benchmarks. Nucleic Acids Res. 2010, vol. 38, pp. 2145-2153

[59] BermanH. M. et al. The Protein Data Bank. Nucleic Acids Res. 2010, vol. 28(1), pp. 235-242

[60] Cochrane G. el.al. Petabyte-scale innovations at the European Nucleotide Archive. Nucleic Acids Research. 2009, vol. 37, pp. 19-25

[61] http: //www. uniprot. org/

[62] MurzinA. G., Brenner S.E., Hubbard T. and ChothiaC. SCOP: a structural classification of proteins database for the investigation of sequences and structures. J. Mol. Biol. 1995, 247, pp. 536-540

[63] OrengoC., MichieA., JonesS., Jones D., Swindells M. and Thornton J. CATH - a hierarchic classification of protein domain structures. Structure.

1997, vol. 5, pp. 1093-1108

[64] http://www.drive5.com/muscle/prefab.htm

[65] Thompson J. D., PlewniakF., PochO. BAliBASE: a benchmark alignment database for the evaluation of multiple alignment programs. Bioinformatics.

1998, vol. 15, pp. 87-88

[66] VanWalleL, LastersL, WynsL. SABmark - a benchmark for sequence alignment that covers the entire known fold space. Bioinformatics. 2005, vol.21, pp. 1267-1268

[67] MizuguchiK., DeaneC.M. , BlundellT. L., Overington J. P. HOMSTRAD: a database of protein structure alignments for homologous families. Protein Sci. 1998, vol. 7, pp. 2469-2471

[68] RaghavaG. P., SearleS.M., AudleyP.C., Barber J. D., Barton G.J. OXBench: a benchmark for evaluation of protein multiple sequence alignment accuracy. BMC Bioinformatics. 2003, vol. 4, p. 47

[69] http://www.ncbi.nlm.nih.gov/BLAST/tutorial/Altschul-1.html

[70] SadreyevR. and GrishinN. COMPASS: a tool for comparison of multiple protein alignments with assessment of statistical significance. J. Mol. Biol. 2003, N. 326, pp. 317-336

[71] Edgar R. С. and SjolanderK. A comparison of scoring functions for protein sequence profile alignment. Bioinformatics. 2004, DOI: 10.1093/bioinformatics/bth090

[72] HolmL. and Sander C. Touring protein fold space with Dali/FSSP. Nucleic Acids Res. 1998, 26, pp. 316-319

[73] Shindyalovl. N. and Bourne P. E. CE: A Resource to Compute and Review 3-D Protein Structure Alignments. Nucleic Acid Research. 2001, 29(1), pp.228-229

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

[75] PoverennayaL, LobanovM., YacovlevV., RoytbergM.. Using of PREFAB for analysis of amino-acid sequence alignment algorhitms. Proc, MCCMB'll. p. 327

[76] К. Дж. Дейт Введение в системы баз данных - 7-е изд. -М.: Вильяме, 2001. - С. 1072

[77] Waterman М. S. Mathematical methods for DNA sequences. Boca Raton, FL: CRC Press, 1989

[78] http://www.python.org/

[79] http://www.boost.org/

[80] Tanenbaum A. S. Operating Systems: Design and Implementation. -Prentice Hall, 1987. 719 P.

[81] Робачевский A. M. Операционная система UNIX. -СПб.: БХВ, 2002. -С. 526

[82] http://fasta.bioch.Virginia.edu/fasta_www2/fasta_list2.shtml

[83] Pearson WR, Lipman DJ. Improved tools for biological sequence comparison. Proc Natl Acad Sci USA. 1988, vol 85. pp. 2444-2448

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

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