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

• Олейникова, Наталья Васильевна
• кандидат физико-математических наук
• 2004

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

ОГЛАВЛЕНИЕ.

ВВЕДЕНИЕ.

Актуальность проблемы.

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

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

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

Наиболее распространенные методы построения парных выравниваний.

Множественные выравнивания и профили.

Молекулярно-биологические банки данных.

РЕЗУЛЬТАТЫ И ОБСУЖДЕНИЕ.

Глава II. Исследование качества выравниваний, построенных методом Смита-Уотермана.

Методы и определения.

Сравнение эталонных выравниваний и выравниваний Смита-Уотермана.

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

Глава III. Острова в выравниваниях.

Восстановление островов эталонных выравниваний.

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

Глава IV. Новый алгоритм выравнивания двух последовательностей.

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

Построение якорей, использование затравок и оптимизация параметров.

Нахождение оптимального пути через якоря.

Сравнение качества построения выравниваний и скорости работы нового метода и стандартных.

Глава V. Применение новой методики к построению выравниваний последовательности и профиля.

Адаптация алгоритма ANCHOR к задаче выравнивания последовательности и профиля.

Сравнение качества выравниваний последовательности и профиля, построенных новым методом, и выравниваний Смита-Уотермана.

Глава VI. Поиск гомологов по банку данных с помощью метода ANCHOR.

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

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

Молекулярная биология совсем молодая, но очень быстро развивающаяся наука. Современный этап развития молекулярной биологии и генетики характеризуется лавинообразным ростом объема расшифрованных биологических последовательностей. Это произошло в значительной степени благодаря программе «Геном человека» и другим подобным, исследованиям. В то же время, как правило, аминокислотные последовательности являются лишь стартовой точкой исследования. В конечном итоге молекулярных биологов, интересует трехмерная структура белков и их функциональная активность. Получение трехмерной структуры белка и определение его функции является очень трудоемкой и дорогостоящей задачей. Количество известных трехмерных структур белков на порядок меньше количества расшифрованных последовательностей. Следовательно, нужны методы, позволяющие предсказывать структуру и функцию белка только по его последовательности. Или, как минимум, нужно уметь отнести новую последовательность к какому-нибудь из уже известных классов белков, т.е. найти группу сходных последовательностей с предположительно подобными структурами или функциями.

Одним из наиболее эффективных и удобных методов сравнения, классификации и выявления сходств биологических последовательностей является метод их выравнивания. Задача выравнивания двух последовательностей - одна из наиболее старых классических проблем вычислительной биологии [1-4]. Выравнивание новой последовательности с последовательностью уже хорошо изученного белка, т.е. такого, о котором известна третичная структура и функция, дает возможность количественно определить уровень сходства этих последовательностей, а так же указать участки наиболее вероятного сходства структур или функций. Для того чтобы предсказание было правдивым, необходимо уметь строить биологически адекватное выравнивание последовательностей, т.е. отражающее эволюционное превращение одного белка в другой [5]. К сожалению, на современном уровне развития вычислительной биологии невозможно в точности воспроизвести ход эволюции. Однако аккуратное выравнивание, отражающее сходство пространственных структур, можно считать достаточным приближением биологически адекватного выравнивания, т.к. структурные элементы белка остаются консервативными даже при достаточно сильном расхождении аминокислотных последовательностей [6]. На настоящий момент существуют алгоритмы, позволяющие строить выравнивания трехмерных структур напрямую, однако они работают далеко не для всех случаев [7-13].

Парные выравнивания используются во многих методах численного анализа биологических последовательностей, таких как функциональное аннотирование генов и белков [14], анализ доменов белков [15], моделирование трехмерной структуры белка по сходству последовательностей [16]. Многие сложные методы вычислительной биологии, например, множественные выравнивания [17-19] и построение профилей [20, 21], используют построение парных выравниваний как промежуточный этап.

Наиболее часто используемыми методами сравнения последовательностей являются: алгоритм Смита-Уотермана (SW) [2, 22] и более быстрые эвристические алгоритмы FASTA[3, 23] и BLAST [4, 24]. Тем не менее, все эти алгоритмы строят выравнивания далекие от совершенства. Выравнивания последовательностей достаточно хорошо сопоставляют элементы вторичной структуры только при высоком уровне гомологии белков. В то время как структурное сходство белков достоверно обнаруживается и при значительном расхождении, последовательностей. Мы употребляем слово «гомология» по традиции, хотя правильнее было бы использовать выражение «сходство последовательностей».

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

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

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

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

В процессе работы решались следующие основные задачи исследования:

1) Определение степени максимально возможного приближения к эталонному выравниванию за счет индивидуального подбора параметров алгоритма SW.

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

3) Разработка нового метода выравнивания аминокислотных последовательностей. Сравнение качества восстановления эталонных выравниваний и скорости работы нового метода и стандартных методов выравнивания.

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

Все проведённые исследования нашли своё отражение в представленном детальном описании работ, выполненных в рамках диссертационного проекта.

Список используемых сокращений: SW — метод Смита-Уотермана,

PDB - Protein Data Bank - банк данных трехмерных структур белков.

Заключение диссертации по теме «Биофизика», Олейникова, Наталья Васильевна

ВЫВОДЫ

1. Получена зависимость надежности восстановления выравнивания пространственных структур (эталонных выравнивании) по аминокислотным последовательностям белков методом Смита-Уотермана. Показано, что индивидуальный подбор штрафов за делеции существенно (более чем на 10%) увеличивает точность выравниваний для белков с уровнем сходства 10-30% (серая зона). Однако даже в этом случае средняя точность выравниваний для этого диапазона %Ю не превышает 52%, а достоверность — 70%.

2. Обнаружены различия алгоритмических и структурных выравниваний на уровне внутренней структуры «островов» (безделяционных участков выравнивания). В выравниваниях SW восстановлено 53% островов, из которых 42% приходится на острова, которые угаданы на 90% и более. Потерянных островов 47%, они имеют малый вес и длину. Показано, что 32% островов эталонных выравниваний имеет вес < 5, суммарная длина таких островов составляет 20% всей длины эталонных выравниваний, потерянные острова веса < 5 оставляют 65% от всех потерянных островов и покрывают 63% суммарной длины потерянных островов. Только 5% островов такого малого веса были восстановлены алгоритмом. Для выравниваний из серой зоны эти цифры аналогичны, однако восстановлено только 2.5% островов с весом меньше 5, и потерянные острова оставляют 65% от общего количества эталонных островов. Проблемы с восстановлением островов малого веса являются причиной недостаточной точности алгоритмических выравниваний.

3. Разработан новый алгоритм ANCHOR выравнивания последовательностей, который при построении выравнивания учитывает не весь вес острова, а только его положительную основу (ядро). Показано, что новый алгоритм не уступает в качестве восстановления структурного выравнивания методу Смита-Уотермана, но работает примерно в 2 раза быстрее.

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

5. На основе нового алгоритма разработана программа поиска гомологов по банку данных (Search-Anchor). Новая программа выдает более точный список гомологов, чем FASTA и BLAST, но работает медленнее более чем в 3 раза. Новый алгоритм работает быстрее алгоритма Смита-Уотермана, незначительно уступая ему в качестве.

Список публикаций по теме диссертации

1. S.R.Sunyaev, G.A.Bogopolsky, N.V.Oleynikova, P.K.Vlasov, A.V.Finkelstein, M.A.Roytberg. From Analysis of Protein Structural Alignments Toward a Novel Approach to Align Protein Sequences. PROTEINS: Structure, Function, and Bioinformatics, 2004,54(3), 569-582.

2. S.R.Sunyaev, G.A.Bogopolsky, N.V.Oleynikova, P.K.Vlasov, A.V.Finkelstein, M.A.Roytberg. Anchor-based alignment of sequences and profiles: accurancy and effectiveness, Proceedings of the international Moscow conference on computational molecular biology, MCCMB'03 Moscow Russia 22-25, July, 2003, p.222-224.

3. G.A.Bogopolsky, A.V.Finkelstein, N.V.Oleinikova, M.A.Roytberg, S.R.Sunyaev, P.K. Vlasov. How similar are aminoacid sequences of the proteins with the common fold?, V International congress of mathematical modeling, Dubna, Russia, Sept. 30-0ctob. 6, 2002, v.2, p.191-192.

4. N.V.Oleynikova, G.A.Bogopolsky, P.K.Vlasov, Sh.R.Sunyaev, M.A.Roytberg. Accuracy of the pairwise protein sequence alignment: From the observations to a new approach, Artificial Intelligence and Heuristic Methods for Bioinformatics, NATO Advanced Studies Institute, San Milano, Italy, 1-11 October 2001, p. 19.

5. Г.В.Богопольский, П.К.Власов, Н.В.Олейникова, М.А.Ройтберг Ш.Р.Сюняев. Определение сходства пространственных структур белков на основе сопоставления их аминокислотных последовательностей. Сборник отчетов по ГНТП "ГЕНОМ ЧЕЛОВЕКА-2000", Москва, 2001, с.145.

6. Г.В.Богопольский, П.К.Власов, Н.В.Олейникова, М.А.Ройтберг, Ш.Р.Сюняев. Распознавание типа укладки белка с помощью многокритериального выравнивания первичных структур белков с профилем семейства. Сборник отчетов по ГНТП "ГЕНОМ ЧЕЛОВЕКА-1999", Москва, 2000, с.38-39.

ЗАКЛЮЧЕНИЕ

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

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

При детальном рассмотрении алгоритмических и структурных выравниваний обнаружены различия на уровне внутренней структуры - «островов» (безделяционных участков выравнивания). В выравниваниях SW восстановлено 53% островов, из которых 42% приходится на острова, которые угаданы на 90% и более. Потерянных островов 47%, они имеют малый вес и длину. 32% островов эталонных выравниваний имеет вес меньше 5, а суммарная длина таких островов составляет 20% всей длины эталонных выравниваний. Потерянные острова веса меньше 5 оставляют 65% от всех потерянных островов и покрывают 63% суммарной длины потерянных островов. Только 5% островов такого малого веса были восстановлены алгоритмом. То есть все эти острова малого веса находятся вне пределов досягаемости стандартных методов сравнения последовательностей. Для выравниваний из серой зоны эти цифры аналогичны, однако восстановлено только 2.5% островов с весом меньше 5, и потерянные острова оставляют 65% от общего количества эталонных островов.

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

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

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

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

На основе нового алгоритма разработана программа поиска гомологов по банку данных (Search-Anchor). Новая программа выдает более точный список гомологов, чем FASTA и BLAST, но работает медленнее более чем в 3 раза. Новый алгоритм работает быстрее алгоритма Смита-Уотермана, незначительно уступая ему в качестве.

Практическое значение работы.

На основе нового метода построения выравниваний разработан программный комплекс, который позволяет строить выравнивания в 2 раза быстрее метода Смита-Уотермана, не теряя точности и достоверности. Программа и исходные коды доступны через всемирную компьютерную сеть по адресу: ftp://genetics.bwh.harvard.edu/Sunvaev/saadi/

Данные программы могут применяться молекулярными биологами для сравнения двух последовательностей, выравнивания профиля (построенного из множественного выравнивания) и последовательности. С помощью программы Search-Anchor можно осуществлять поиск гомологов по любой заданной базе данных в формате FASTA.

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

1. Needlman S, Wunsch С. A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol. 1970; 48:443-453.

2. Smith TF, Waterman MS. Identification of common molecular subsequences. J. Mol. Biol. 1981; 147:195-197.

3. Lipman DJ, Pearson WR. Rapid and sensitive protein similarity searches. Science 1985; 227:1435-1441.

4. Altschul SF, Gish W, Miller W, Myers E, Lipman DJ. Basic local alignment search tool. J. Mol. Biol. 1990; 215:403-410.

5. Li WH. Molecular Evolution. Sunderland: Sinauer Associates; 1997.

6. Doolittle RF. Similar amino acid sequences: chance or common ancestry? Science 1981; 214: 149-159.

7. Shindyalov IN, Bourne PE. Protein structure alignment by incremental combinatorial extension (CE) of the optimal path. Protein Eng. 1998; 11(9):739-47.

8. Orengo CA, Taylor WR. SSAP: sequential structure alignment program for protein structure comparison. Methods Enzymol. 1996; 266: 617-635.

9. Alexandrov NN. SARFing the PDB. Protein Eng. 1996; 9: 727-732.

10. Koch I, Lengauer T, Wanke E. An algorithm for finding maximal common subtopologies in a set of protein structures. J. Comput. Biol. 1996; 3: 289-306.

11. Gibrat JF, Madej T, Bryant SH. Surprising similarities in structure comparison. Curr. Opin. Struct. Biol. 1996; 6: 377-385.

12. Holm L, Sander C. Protein structure comparison by alignment of distance matrices. J. Mol. Biol. 1993; 233: 123-138.

13. Russell RB, Barton GJ. Multiple protein sequence alignment from tertiary structure comparison: assignment of global and residue confidence levels. Proteins 1992; 14: 309323.

14. Bork P, Koonin EV. Predicting functions from protein sequences—where are the bottlenecks? Nat. Genet. 1998; 18: 313-318.

15. Bateman A, Birney E. Searching databases to find protein domain organization. Adv. Protein Chem. 2000; 54: 137-157.

16. Sanchez R, Sali A. Comparative protein structure modeling. Introduction and practical examples with modeller. Methods Mol Biol. 2000; 143: 97-129.

17. Thompson JD, Higgins DG, Gibson TJ. CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucleic Acids Res. 1994; 22:4673-4680.

18. Park J, Karplus K, Barrett C, Hughey R, Haussler D, Hubbard T and Chothia C. Sequence Comparisons Using Multiple Sequences Detect Three Times as Many Remote Homologues as Pairwise Methods. J. Mol. Biol 1998; 284: 1201-1210.

19. Notredame C, Higgins DG, Heringa J. T-Coffee: A novel method for fast and accurate multiple sequence alignment. J. Mol. Biol. 2000; 302: 205-217.

20. Gribskov M, McLachlan AD, Eisenberg D. Profile analysis: detection of distantly related proteins. Proc Natl Acad Sci USA 1987; 84(13):4355-8.

21. Gribskov M, Veretnik S. Identification of sequence pattern with profile analysis. Methods Enzymol. 1996; 266:198-212.

22. Smith TF, Waterman MS. Comparison of biosequences. Adv. Appl. Math. 1981; 2:482489.

23. Pearson WR, Lipman DJ. Improved Tools for Biological Sequence Analysis. Proc. Natl. Acad. Sci. USA 1988; 85:2444-2448.

24. Altschul SF, Boguski MS, Gish W & Wootton JC. Issues in searching molecular sequence database. Nature Genet. 1994; 6,119-129.

25. Waterman MS. Introduction to Computational Biology. London New York — Tokyo: Chapman & Hall; 1985.

26. Waterman MS, Sequence Alignments, in Mathematical Methods for DNA Sequences, Waterman MS (ed.) CRC Press, Boca Raton, FL, 1989;0:53-92.

27. Dayhoff MO. Atlas of protein sequence and structure. Washing-ton, DC: National Biomedical Research Foundation; 1979; 345-358.

28. Henikoff S, Henikoff JG. Amino acid substitution matrices from protein blocks. Proc Natl Acad Sci USA 1992;89:10915-10919.

29. Brenner SA, Cohen MA, Gonnet GH. Amino acid substitution during functionally constrained divergent evolution of protein sequences. Protein Eng 1994;7:1323—1332.

30. Altschul S. A protein alignment scoring system sensitive at all evolutionary distances. Journal of Molecular Evolution, 1993; 36:290-300.

31. Karlin S and Altschul SF. Methods for assessing the statistical significance of molecular sequence features by using general scoring schemes. Proc. Natl. Acad. Sci. USA., 1990; 87:2264-2268,.

32. Pearson WR. Protein sequence comparison and protein evolution. Tutorial-ISMB 2000. Charlottesville, VA: University of Virginia; 2000; 1-51.

33. Pearson W.R. Empirical statistical estimates for sequence similarity searches. «/. Mol. Biol. 1988; 276: 71-84

34. Attwood TK, Beck ME, Flower DR., Scordis P and Selley J. The PRINTS protein fingerprint database in its fifth year. Nucleic Acids Research, 1998; 26 (1), 304-308.

35. Altschul SF, Madden TL, Schaffer AA, Zhang J, Zhang Z, Miller W, Lipman DJ Gapped BLAST and PSI-BLAST: a new generation of protein database search programs Nucl. Acids. Res. 1997; 25: 3389-3402.

36. Apweiler R. Functional information in SWISS-PROT: the basis for large-scale characterisation of protein sequences. Brief Bioinform 2001; 2 (1):9-18

37. Thompson JD, Plewniak F, Poch O. BAliBASE: a benchmark alignment database for the evaluation of multiple alignment programs. Bioinformatics. 1999; 15: 87-88.

38. Berman HM, Westbrook J, Feng Z, Gilliland G, Bhat TN, Weissig H, Shindyalov IN, Bourne PE. The Protein Data Bank. Nucl. Acids. Res. 2000; l;28(l):235-42.

39. Murzin AG, Brenner SE, Hubbard T, Chothia C. SCOP: A structural classification of proteins database for the investigation of sequences and structures. J. Mol. Biol. 1995; 247, 536-540.

40. Andreeva A, Howorth D, Brenner SE, Hubbard TJP, Chothia C, Murzin AG. SCOP database in 2004: refinements integrate structure and sequence family data. Nucl. Acids. Res. 2004; 32:226-229.

41. Schultz J, Milpetz F, Bork P, Ponting CP. SMART, a simple modular architecture research tool: identification of signaling domains. Proc Natl Acad Sci USA. 1998; 26;95(ll):5857-64.

42. Letunic I, Goodstadt L, Dickens NJ, Doerks T, Schultz J, Mott R, Ciccarelli F, Copley RR, Ponting CP, Bork P. Recent improvements to the SMART domain-based sequence annotation resource. Nucl. Acids. Res. 2002; l;30(l):242-4.

43. Holm L, Sander C. Searching protein structure databases has come of age. Proteins 1994; 19, 165-173.

44. Holm L, Sander C. 0. Touring protein fold space with Dali/FSSPNucl. Acids Res. 1998; 26,316-319.

45. Holm L, Sander C. The FSSP database: fold classification based on structure-structure alignment of proteins. Nucl. Acids Res. 1996; 24,206-210.

46. Holm L, Sander C. The FSSP database of structurally aligned protein fold families. Nucl. Acids Res. 1994; 22,3600-3609.

47. Sander C, Schneider R. Database of homology derived protein structures and the structural meaning of sequence alignment. Proteins 1991; 9,56-68.

48. Attwood TK, Beck ME, Bleasby AJ, Parry-Smith DJ. PRINTS A database of protein motif fingerprints. Nucl. Acids Res. 1994; 22 (17), 3590-3596.

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

50. Domingues FS, Lackner P, Andreeva A, Sippl MJ. Structure-based evaluation of sequence comparison and fold recognition alignment accuracy. J. Mol. Biol. 2000; 297: 1003-1013.

51. Henikoff S, Henikoff JG. Amino acid substitution matrices. Adv. Protein Chem. 2000; 54: 73-97.

52. Abagyan RA, Batalov S. Do aligned sequences share the same fold? J. Mol. Biol. 1997; 273: 355-368.

53. Altschul SF. Generalized affine gap costs for protein sequence alignment. Proteins 1998; 32:88-96.

54. Sander С, Schneider R. Database of homology-derived protein structures and the structural meaning of sequence alignment. Proteins. 1991; 9: 56-68.

55. Rost, В. Twilight zone of protein sequence alignments. Protein Eng. 1999; 12: 85-94.

56. Brenner SE, Chothia C, Hubbard TJP. Assessing sequence comparison methods with reliable structurally identified distant evolutionary relationships. Proc. Natl. Acad. Sei. USA, 1998; 95,6073-6078.

57. Sauser JM, Arthur JW, and Dunbrack Jr. RL. Large-Scale Comparison of Protein Sequence Alignment Algorithms With Structure Alignments. Proteins, 2000; 40: 6-22.

58. Finkelstein AV, Roytberg MA. Computation of biopolymers: a general approach to different problems. Biosystems. 1993;30(1 -3): 1-19.

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

60. Saqi MA, Russell RB, Sternberg MJ. Misleading local sequence alignments: implications for comparative protein modelling. Protein Eng. 1998; 11: 627-630.

61. Altschul SF, Gish W. Local alignment statistics. Methods Enzy-mol 1996;266:460-480.

62. Wilbur WJ, Lipman DJ. Rapid similarity searches of nucleic acid and protein data banks. Proc Natl Acad Sei USA 1983;80:726-730.

63. Eppstein D, Galil Z, Giancarlo R, Italiano GF. Sparse dynamic programming. 1. Linear cost-functions. J ACM 1992;39:519-545.

64. Sunyaev SR, Eisenhaber F, Rodchenkov IV, Eisenhaber В, Tumanyan VG, Kuznetsov EN. PSIC: profile extraction from sequence alignments with position-specific counts of independent observations. Protein Eng. 1999; 12,387-94.