МОЛЕКУЛЯРНАЯ БИОЛОГИЯ, 2004, том 38, № 1, с. 92-103
== КОМПЬЮТЕРНАЯ ГЕНОМИКА
УДК 577.2.08:681.3
СРАВНИТЕЛЬНЫЙ АНАЛИЗ ПЕРВИЧНЫХ СТРУКТУР НУКЛЕИНОВЫХ КИСЛОТ И БЕЛКОВ
© 2004 г. М. А. Ройтберг*
Институт математических проблем биологии Российской академии наук, Пущино, Московская обл., 142290
Поступила в редакцию 15.08.2003 г.
Представлен обзор работ по анализу первичных структур биополимеров, выполненных автором в 1983-2003 гг. Большая часть этих работ выполнена в рамках Российской национальной программы "Геном человека" и предшествовавших ей близких по тематике отечественных научных программ. Подробно обсуждены малоизвестные публикации 1983-1993 гг., а также недавно полученные и частично неопубликованные результаты. В области сравнения геномных последовательностей - это иерархический алгоритм выравнивания синтенных участков двух геномных последовательностей OWEN. Результирующее глобальное выравнивание представляется в виде упорядоченной цепи локальных сходств. Выравнивание последовательностей длиной ~106 может быть выполнено в течение нескольких минут. Предложено обобщение понятия конфликта локальных сходств на случай выравнивания нескольких последовательностей. Описаны новые алгоритмы выравнивания белковых последовательностей и исследованы их характеристики по сравнению с одним из наиболее точных в настоящее время алгоритмов - алгоритмом Смита-Ватермана. Предложен также новый способ описания семейств белков. Иерархический алгоритм ANCHOR порождает выравнивания примерно той же точности, что и алгоритм Смита-Ватермана, но работает примерно в 2 раза быстрее. Алгоритм STRSWer позволяет учитывать данные о вторичной структуре сравниваемых белков. При использовании вторичных структур, предсказанных с помощью сервера PSI-PRED, для пар белков с уровнем сходства 10-30% точность выравниваний, порождаемых алгоритмом STRUSW, в среднем на 15% выше, чем у выравниваний, полученных с помощью алгоритма Смита-Ватермана.
Ключевые слова: первичные структуры биополимеров, выравнивание биологических последовательностей, пространственная структура белка, сравнение геномов.
Большой честью для меня является приглашение руководителей Российской национальной программы "Геном человека" написать обзор для мемориального выпуска журнала "Молекулярная биология", посвященного памяти А.А. Баева.
Программа "Геном человека", лидером которой в течение многих лет был академик А.А. Баев, создавала среду, которая очень помогала моей работе и, думаю, работе многих моих коллег. Я начал работать в области анализа первичных структур биополимеров в начале 80-х годов по предложению директора нашего института (тогда - Научно-исследовательский вычислительный центр АН СССР) А.М. Молчанова. Насколько мне известно, А.М. Молчанов инициировал в НИВЦ АН СССР работы по анализу биологических последовательностей по прямому указанию А.А. Баева, в то время академика-секретаря отделения физико-химической биологии АН СССР. В это же время к работам по этому направлению привлекли А.С. Кондрашова и ряд других сотрудников института, было начато сотрудничество с другими
Принятые сокращения: МЛС - множественное локальное сходство.
*Эл. почта: roytberg@impb.psn.ru
институтами, в частности, с лабораторией физики белка Института белка РАН (заведующий лабораторией проф. О.Б. Птицын).
Основным объектом изучения для меня стали первичные структуры (последовательности) биополимеров - нуклеиновых кислот и белков, а основной задачей - разработка методов их сравнительного анализа и применение этих методов для решения биологических задач.
К началу 80-х годов - моменту создания первых баз данных последовательностей ДНК и белков - необходимый алгоритмический аппарат был, в значительной степени, готов. При этом специалисты в области алгоритмов рассматривали биологические приложения в одном ряду с техническими, одни и те же алгоритмы применялись как для сравнения ("выравнивания") биологических последовательностей, так и для поиска сбоев при хранении файлов, не делали различий в методах сравнения нуклеотидных и аминокислотных последовательностей. Характерно название книги, содержащей, по-видимому, первый обзор по биоалгоритмике [1] - "Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison" (Eds Sankoff D. and Kruskal J.B., 1983).
Впрочем, довольно скоро выяснилось, что анализ биологических последовательностей имеет свою специфику - прежде всего с точки зрения постановок задач. Прогресс в области математического анализа биологических последовательностей имел два источника: 1) уточнение формальных постановок задач, приведение их в соответствие с содержательными биологическими задачами и особенностями изучаемых объектов и 2) привлечение новых математических идей. В качестве примера такого прогресса в области сравнительного анализа последовательностей укажем, например, введение понятия частотного профиля семейства последовательностей (иначе Position-Specific Scoring Matrix, PSSM), разработку методов их построения и использования при поиске родственных последовательностей [2, 3]. При этом за последние 20 лет быстродействие и память компьютеров выросли на несколько порядков, что сделало сейчас актуальными алгоритмические методы, которые 20 лет назад имели чисто теоретическое значение. Отметим, что успех международной программы "Геном человека", наряду с успехами в области техники секвениро-вания, определяется и наличием аппаратных (hardware) и программных (software) средств, позволяющих обрабатывать последовательности длиной в десятки и сотни миллионов нуклеотидов и хранить базы данных, содержащие миллиарды мономеров.
Первая из моих работ (выполненная под влиянием плодотворного общения с А.С. Кондра-шовым) посвящена разработке эффективных методов выравнивания первичных структур, позволяющих отразить биологическую специфику сравниваемых последовательностей [4]. В этой работе предложена новая постановка задачи выравнивания биологических последовательностей и алгоритм решения этой задачи. Основной результат работы - выделение класса весовых функций делеций, допускающих построение эффективного алгоритма выравнивания двух символьных последовательностей. Более точно, веса делеций в выравнивании могут задаваться следующим набором функций (в качестве аргумента всюду L обозначает длину делеции, X - символьный контекст фиксированного размера на краю делеции, i = 1, 2 - номер последовательности):
Si (L) + T (X) - штраф за удаление начального фрагмента i-й последовательности,
Fi (L) + Gi (X) - штраф за удаление концевого фрагмента i-й последовательности,
Di (L) + Bi (X) - штраф за удаление внутреннего фрагмента i-й последовательности.
Здесь функции Si (L), T (X), Ft (L), Gt (X), Bi (X) могут быть произвольными, а функция Di (L) должна быть кусочно-линейной.
Для такого класса весовых функций предложен алгоритм LINNEUS, который строит оптимальное выравнивание за время, пропорциональное k1*k2*L1*L2, где L1, L2 - длины сравниваемых последовательностей, kl, к2 - количества интервалов линейности у функций D1, D2. Память, необходимая для работы алгоритма, была (примерно) пропорциональна m1*L1, где ml - начало последнего интервала линейности функции D1. Последнее обстоятельство (необходимая память пропорциональна не произведению длин сравниваемых последовательностей, а "примерно" длине кратчайшей из них) было весьма важно в условиях начала 80-х гг. Последующее развитие биоалгоритмики показало, что лишь небольшая часть предусмотренной общности определения оказалась востребованной. Современные программы выравнивания, в частности, не используют произвольных весовых функций для краевых делеций (возможны только два варианта - совпадающий со штрафом за внутреннюю делецию или нулевой). Не применяют зависимость штрафа от контекста в точке разрыва (хотя это и может быть биологически мотивировано). Вместо произвольных кусочно-линейных функций используют лишь функции с одним интервалом линейности. Такая излишняя для реальных биологических задач математическая общность характерна для работ того времени. Описанный результат опубликован лишь в виде препринта (еще одна примета времени) и не стал известен за пределами СССР. Весьма близкий класс весовых функций и соответствующий алгоритм выравнивания был позднее независимо рассмотрен в вышедшей в 1988 г. работе Дж. Майерса и В. Миллера [5].
Примерно тогда же разработан значительно более быстрый, но рассчитанный на существенно более узкий класс весовых функций, алгоритм выравнивания последовательностей KARL [6]. Подробное описание алгоритма содержится в работе [7]. Завершают эту серию работ алгоритмы поиска всех локальных сходств в двух и нескольких последовательностях [8-12], среди которых стоит отметить публикацию [11] в Трудах первой всесоюзной конференции "Геном человека" (Пе-реславль-Залесский, октябрь 1990 г.), а также подробное изложение тех же результатов [12].
Перечисленные программы, как и более традиционные программы анализа последовательностей, например, статистического анализа, вошли в разработанный в НИВЦ АН СССР под руководством А.С. Кондрашова открытый пакет программ САМСОН [13-16]. При разработке этого пакета большую роль сыграла общая высокая программистская и математическая культура тогдашнего НИВЦ АН СССР, заложенная его основателями А.М. Молчановым и Э.Э. Шнолем. Для меня, в частности, очень важным было тесное сотрудничество с В.В. Левитиным, который в то
время возглавлял группу (позднее - лабораторию) программирования (см. публикацию [17] в Трудах второй всесоюзной конференции "Геном человека", Переславль-Залесский, октябрь 1991 г.). Примерами использования разработанных программ являются публикации [18-20].
Большое значение для меня (и, я думаю, для всех участников) имел существовавший в середине 80-х гг. межлабораторный семинар под руководством О.Б. Птицына и Э.Э. Шноля. В 1985 г. по предложению руководителей семинара я совместно с А.В. Финкельштейном подготовил развернутый обзор математических методов анализа биополимеров. В ходе работы над обзором нами был предложен единый способ описания различных
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.