автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Банки данных и алгоритмы выравнивания и классификации нуклеотидных и аминокислотных последовательностей

российская академия наук

ОРДЕНА ЛЕНИНА СИБИРСКОЕ ОТДЕЛЕНИЕ Новосибирский институт цитолопш и генетики

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

УДК 578.088:(176.12+575.24)

Стрелец Виктор Борисович

БАНКИ ДАННЫХ И АЛГОРИТМЫ ВЫРАВНИВАНИЯ И КЛАССИФИКАЦИИ НУКЛЕОТИДНЫХ И АМИНОКИСЛОТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

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

Автореферат

диссертации на соискание ученой степени кандидата биологических наук

Новосибирск - 1992

Работа выполнена в Институте цитологии н генетики СО РАН г. Новосибирск

Научный руководитель: доктор биологических наук, зав.лаб.

Колчанов Николай Александрович Институт цитологии и генетики СО РАН

Официальные оппоненты: доктор биологических наук, зав.лаб.

Каракин Евгений Иннокентьевич Институт цитологии и генетики СО РАН

кандидат биологических наук, в.н.с. Ерошкин Алексей Максимович НПО "ВЕКТОР", НИИ молекулярной биологии

Ведущее учреждение: Институт молекулярной биологии РАН,

г. Москва

Защита состоится " М " апреля_ 1992 г.

на открытом заседании специализированного совета по защите диссертаций на соискание ученой степени кандидата наук при Новосибирском институте органической химии СО РАН (К 002.42.01) в конференц-зале института по адресу: 630090, г. Новосибирск, 90, проспект академика Лаврентьева, 9.

С диссертацией можно ознакомиться в библиотеке Новосибирского института органической химии СО РАН.

Автореферат разослан < ¿(/"Л /УШ1992 г.

ч

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

Актуальность темы. Использование эффективных методов расшифровки первичных структур молекул ДНК, РНК и белков ( включая технологию автоматического секвенирования) привело к резкому росту объемов информации, накапливаемой в соответствующих банках данных (ЕМВЬ, swiss-prot, GENBANK, PIR). В подавляющем большинстве институтов РАН и прикладных научно-исследовательских организаций России, работающих в области молекулярной биологии и генетики, наиболее распространенными типами компьютеров являются персональные компьютеры типа ibm PC или их аналоги.

Таким образом, для . успешного решения проблемы компьютерного анализа результатов массового секвенирования первичных структур (последовательностей ) ДНК, РНК и белков первостепенным становится создание компактных

автоматизированных банков данных, ориентированных на указанные выше персональные компьютеры. Такие банки данных должны обеспечивать возможность в полном объеме использовать указанные выше базы данных (embl, SwiseProtein, PIR, GENbank) на персональных компьютерах для анализа первичных структур ДНК, РНК и белков, а также для информационно-справочного обеспечения экспериментальных работ по молекулярной биологии, и генетике. Резкое увеличение объемов информации в перечисленных выше базах данных делает также актуальной разработку новых методов быстрого поиска сходства между последовательностями и их выравнивания.

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

ДНК, РНК и белков (включая те, которые необходимы при анализа результатов секзенирсваная геномной ДНК). При этом долзла быть предусмотрена возможность использования стандартного формата для ввода/вывода, хранения и рс-дактировагатя ясходаой НЕформация, а такяе той информации, которая продуцируете:?. в ходэ работы система.

Цели и задачи работы. Целью настоящего иеслидовагом являлась разработка комплекса алгор;шюв у программ для классификации и сравнения биологических посладоаятельиоетой, автоматизированных банков данных по первиаш:,; структура;.! нуклеотидных л аминокислотных последовательностей, а такгаз разработка инструментальных программных средств гля создания штегрированних пакетов программ, реализующих слокные сценарии компьютерного анализа первичных структур ДНК, РНК и балков. Для достижения этой цели решались следующие задачи:

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

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

3. Разработка автоматизированных банков данных для компактного хранения и использования информации из наиболее крупных баз данных по - последовательностям (ЕШЗЬ,3«1взР:гс^е:т,Р1Н) .с возможностями диалогового и программного доступа и с ориентацией на использование персональных компьютеров с винчестерскими дисками малой емкости (до 40 Мбайт).

4. Разработка инструментальных программных средств, позволяющих создавать интегрированные пакеты программ, реализующие сложные сценарии анализа первичных структур ДНК, РНК и белков ( с использованием стандартного формата для ввода/вывода, обмена, хранения и редактирования информации).

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

натрицу точечной гог.-элопш последовательностей во ззвэвенный ориентировонннй граф. Маршрут максимального веса в таком графе задает оптимальное выравнивание посладовательностей, построенное на основе фрагментов гомологичных подпос.'.;э;:оЕателкюс~ей. Второй алгоритм использует предварительной статистический анализ и отбор гомологичных подгослэдователъностэй и обеспечивает быстрое построение оптимального выравнивания на основе таких подпоследовательностей. Этот алгоритм представляет собой кодификацию классического алгоритма Needleman-VfunBch для случая работы со снатымк матрицами точечной гомологии и позволяет учитывать информацию о статистической значимости гомологий подпоследовательностей на всех этапах построения выравнивания. Эти алгоритмы позволяют использовать преимущества классических матричных алгоритмов выравнивания одновременно с учетом статистической значимости гомологии коротких подпоследовательностей. Высокая эффективность алгоритмов позволяет использовать их для проведения серийных выравниваний вновь секвенировановых последовательностей с последовательностями из баз данных за приемлемое время.

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

Созданы автоматизированные банки данных для компактного хранения и обработки информации из наиболее распространенных баз данных по последовательностям (емвъ, SwissProtein, PIR). Банки имеют развитый ориентированный на пользователя-экспериментатора диалоговый интерфейс а также обеспечивают возможность программного доступа к хранимой информации из программ пользователя. Банки ориентированы на использование персональных компьютеров IBM PC с I винчестерскими дисками емкостью 40Мбайт.

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

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

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

Автоматизированные банки данных мо!<ут' быть использованы в качестве информационно-поисковых систем в

молекулярно-генетических лабораториях, использующих персональные компьютеры типа ibm-pc. Они позволяют существенно компрессировать имеющуюся информацию (исходным объемом 100-200 Мбайт) обеспечивая работу с ней на персональных компьютерах с винчестерскими дисками емкостью не более 40Мбайт. Такие банки данных позволяют вести поиск и обработку информации по сценариям, удобным пользователям-экспериментаторам, а также обеспечивают простой и удобный доступ к информации из прикладных обрабатывающих программ.

Апробация работы. Разработанное матобеспечение

используется в ряде молекулярно-биологических и молекулярно-генетических институтов РАН и в прикладных научно-исследовательских организациях России: ИЦиГ СО РАН, ВШИ МБ, ИБХ СО РАН, ИМГ.РАН, ВНИИ ящура, ВНИИ ОЧБП и др. Оно использовалось в рамках государственных научно-технических программ "Геном Человека", "Генинформ" и КПНТП СЭВ. На основе созданной оболочки базы знаний с 1990г. разрабатывается система автоматизированного анализа результатов секвенирования нуклеотидных последовательностей генома Человека.

Публикации. По теме диссертации опубликовано 8 работ.

Структура и объем работы Работа состоит из введения, пяти глав, выводов и списка цитируемой литературы. Работа содержит 98 страниц текста, 30 рисунков, 8 таблиц. Общий объем 143 страницы. Список литературы содержит 79 ссылок.

ГЛАВА 2. АЛГОРИТМЫ ВЫРАВНИВАНИЯ ПОСЛЕДОВАТЕЛЬНОСТИ!

Эмпирический алгоритм с отражением dot в ориентированный граф

Диагональным фрагментом (Df) назовем участок диагонали матрицы точечной гомолгии (dot), соответствупций гомологичным подпоследовательностям. Каждому элементу Df приписывается вес, который отражает гомологию двух подпоследовательностей на участке от начала Df до этого элемента. Опорное выравнивание - это маршрут максимального веса по DOT (проходящий через элементы различных Df) Маршрут может проходить не по всему Df целиком, а лишь по его участку, переходя на соседние Df в DOT, если такие переходы дают выигрыш в гомологии для опорного выравнивания. Разница весов элементов Df, ограничивающих переход маршрута между парой Df, может быть мерой выигрыша в локальной гомологии последовательностей, который достигается при прохоадении этого перехода маршрутом опорного выравнивания. Переход должен быть наибольшим (по разнице весов элементов, ограничивающих переход). Переход между Df соответствует делеции в одной из последовательностей, поэтому мы вводим штраф на делецию, равный ее длине. При выборе точки оптимального перехода мевду Df может оказаться, что несколько пар элементов дают переход.одного и того же максимального веса. Эта ситуация соответствует альтернативным вариантам оптимального локального выравнивания последовательностей. Мы выбираем один из этих вариантов, поскольку все они близки друг к другу по виду выравнивания. Для упрощения, мы добавляем к концам рассматриваемых последовательностей одинаковые элементы, считаем их гомологию в выравнивании обязательной ("принудительная привязка" концов последовательностей друг к другу) и после этого можем искать маршрут оптимального выравнивания, начинающийся с элемента dot1 1 и кончающийся элементом dotn м> где N и м - длины последовательностей. Такой прием позволит находить выравнивания с делециями на концах последовательностей. Попав на некоторый Df, маршрут может перейти (в точках оптимальных переходов) на другие Df или же пройти по этому Df до его конца. При переходе на другой Df выигрыш в гомологии опорного

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

abcabcdbc a bc abcdbc

Возможные перехода между Df Выбранный маршрут

максимального веса

Результирующее выравнивание: abcabc—dbc

**• ***

---ABCDKDBC

Рис.1. Пример построения выравнивания как маршрута через Df в DOT для двух коротких последовательностей.

оптимальному маршруту е таком графе. Тагам образом, задачз нахождения опорного выравнивания по dot сведена к задаче нахождения пути максимального веса по графу, вершины которого соответствуют Df, а ребра - возможным переходам менду Df с соответствующими весами. Для нахождения маршрута оптимального веса в полученном графе использован алгоритм DijlcBtra. Нахождение опорного выравнивания ведется, соответственно, с эффективностью порядка N;<log(ll), где N - число обрабатываемых Df. Найденное опорное выравнизание нельзя считать оптимальным: число Df, использованных при его иахоидении, ограничено. Нами реализована процедура локальной оптимизации выравнивания, при которой из соображений улучшения локального соответствия последовательностей их участки, стоящие в выравнивании друг напротив друга (группы), сдвигами приводятся в более предпочтительное положение. Мы оцениваем оптимальность bopy.okhux сдвигов групп и отбираем те из них, для которых выполняется условие допустимости (это условие имеет очевидный смысл: реализуются только те сдвиги, при которых гомология подпоследовательностей на участках групп возрастает). Таким образом несколько раз итерационно обрабатывается полученное выравтппзание (перебором его позиций) до тех пор, пока не останется ни одного улучшающего гомологию сдвига ни для одной из возможных групп символов в выравнивании. На большей части последовательностей такая локальная оптимизация сходится к некоторому конечному варианту выравнивания за 5-8 итераций. Это говорит о том, что получаемое на первой стадии работы алгоритма опорное выравнивание является достаточно хорошим приближением оптимального (см.Рис Л).

Алгоритм с записью информации о Df в компактные матрицы

Алгоритм имеет линейные требования к памяти и трудоемкость (от длины последовательностей) и позволяет получать биологически осмысленное выравнивание в тех случаях, когда использование классических алгоритмов невозможно (при гомологии менее 25%, в случае выравнивания слабоперекрывающихся контигов и др.). Он представляет собой модификацию классических алгоритмов типа Needleman-Wunsch для

обработки компрессированных ИОТ-матриц. Ка первом этапе работы алгоритма производится выявление гомологичных подпоследовательностей (ДЯ со статоцонкой неслучайности полученной гомологии. Одновременно с выявлением информация о ДГ записывается в компактные матрицы, в которых сохраняются данные о положении ДГ в Бот-матрице, о неслучайности гомологии подпоследовательностей, о внутренней структуре гомологий позиций последовательностей на всем протяжении ДГ. Запись ведется таким образом, что после записи каждая пара позиций гомологичных подпоследовательностей рассматривается как самостоятельный объект и поэтому выравнивание может строиться как комбинация участков различных ДГ. На заключительной стадии работы алгоритма производится поиск оптимального (имеющего максимальный вес) маршрута по компрессированным матрицам, который соответствует оптимальному выравниванию последовательностей. При этом в качестве веса гомологии пары позиций, в отличие от классических алгоритмов, используется статистическая оценка гомологии ДГ, к которому принадлежит гомология данной пары. Предполагая, что в случайной последовательности все типы позиций встречаются с некоторой частотой Рт, вероятность р совпадения двух произвольных позиций в последовательностях А

и в определяется как

1=п

р = Р^ , где п - число элементов алфавита.

Использовались значения р=0,058 для аминокислотных последовательностей и р=0,26 для нуклеотидных, полученные при анализе баз данных ЕМВЬ (г19,1989) и SwissPгot (г14,1990). Вероятность (неслучайность) и гомологии двух участков длины I с Ы совпадениями определялась как

V = 1 - х р* х (1-р)1_й.

глава 3. быстрое сравнение последовательностей белков

При упрощенном сравнении белков по аминокислотному составу мерой сходства последовательностей считался ранговый коэфициент корреляции {КС) векторов относительных частот

аминокислот. Если корреляция достоверна, будем считать последовательности неслучайно близкими друг к другу. Использование относительных частот встречаемости выравнивает значения отдельных компонент векторов, что позволяет избежать сильных колебаний на очень редких или очень распространенных аминокислотах. Ранговый коэффициент корреляции позволяет анализировать не столько сходство значений частот отдельных аминокислот, сколько соответствие межаминокислотного баланса в сравниваемых белках (это позволяет сравнивать белки с заметно различающимися длинами). Для проверки работоспособности алгоритма проведены все возможные парные сравнения 10 групп неродственных белков. Близкими считались белки, имещие положительный коэффициент ранговой корреляции при достоверности более 95%. Оценка эффективности алгоритма проводилась по двум параметрам. I.Эффективность предсказания (или просто предсказание) - число предсказаний родственности белков внутри всех групп (белки, составляющие группу, гомологичны и все должны выявляться алгоритмом как родственные). 2. Ошибка предсказания (или перепредсказание) -число предсказаний болков как родственных при их принадлежности разным группам (т.е. когда они не имеют родства или заметной гомологии). Полученные значения нормировались на число всевозможных пар белков из всех групп. Получена предсказание 86%, при перепредсказании Ий. Получено прямое соответствие мезду степенью достоверности корреляции аминокислотных составов белков и гомологией их последовательностей (т.е. структурно-функциональная специфичность белков и аминокислотный состав связаны между собой: состав в пределах каждого суперсемейства приблизительно одинаков и, видимо, уникален, причем это оказалось верно даже для проанализированных мутаций).

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

^Х = уХ, > , где ^Х, - количество отрезков, имеющих ровно í ^ 1) 1 аминокислот тша ].

Вектор ^X является интегральной характеристикой

неравномерности распределения аминокислот типа J в белке.

Далее строится тестовое нормальное распределение

* = (Ц •

имеющее среднее и дисперсию те же, что и распределение ¿Х. Тестовое и реальное интегральные распределения сравниваются с помощью нзпараметрического критерия Колмогорова-Смирнова, значение которого дает после нормировки параметр ^¡з, описыващий характер распределения. При ^>1 распределеше аминокислоты ./-го типа значительно отличается от тестового (нормального), в прочих случаях это распределение можно считать совпадающим с тестовым. Вычисляя значения •'З для всех типов аминокислот 1,..,20), получаем вектор г, который . характеризует отклонение распределения аминокислот различных типов от тестового (случайного). Таким образом, любая последовательность может характеризоваться вектором 5, задающим координаты точки в многомерном статистическом пространстве. Для отбора близких последовательностей мы используем сферу единичного радиуса описанную вокруг точки, соответствующей белку в многомерном статистическом пространстве. Длина отрезка разбиения последовательности выбрана равной 10. Для проверки работоспособности алгоритма ш выбрали 10 групп неродственных белков и провели сравнения всех со всеми. Получена эффективность предсказания 88% при перепредсказании менее 3*. Часть перепредсказаний вскрывает возможные структурно-функциональные взаимосвязи белков различных супесемейств. Показана прямая зависимость между гомологией белков и растоянием между ними в многомерном статистическом пространстве.

глава 4. автоматизированным банк последовательностей (АБД)

Определим следующие термины: базу данных СБУ) как совокупность представленной в некотором формате информации об известных последовательностях; информационный объект (ИО) базы как отдельную последовательность с описаниями ее

ю

особенностей; информационное 'поле (ИП) информационного объекта как совокупность информации о каком-либо одном виде его особенностей; запросы к БД как часто используемые в процессе ее эксплуатации задания по поиску данных.

АБД "Sagittarius" предназначен для работы с информацией БД Swiss Protein и EMBL, которые служат основой для его заполнения. Для снижения объема памяти, необходимой для хранения в АБД информации использовался сокращенный по сравнении с исходными БД список ИП ( номенклатурный и идентификационный индексы, название, источник, классификация, ключевые слова, литературные ссылки, ссылки на другие БД, текстовые комментарии, структурно-функциональная разметка, собственно последовательность).

При определении информационной структуры разрабатываемого АБД была учтена общая особенность содержащейся в БД по последовательностям информации: высокое содержание повторявдэйся информации во многих ИП. Это позволило заметно уменьшить объем файлов АБД, содержащих информацию из таких ИП, благодаря использованию словарной организации хранения информации. При этом вместо текста ИП (или части его) в АБД хранится ссылка на запись в словаре. При использовании словарей структура ИО из древовидной превращается в сетевую: каждой записи словаря могут соответствовать участки ИП нескольких ИО, и наоборот. Такая схема взаимосвязи хранимой информации соответствует структуре сетевых АБД, к которым может быть отнесен описываемый АБД "Sagittarius". В разработанном АБД используются два типа словарей:_ статические и динамические. -Динамические словари используются для кодирования тех ИП, которые состоят из часто используемых общих для данного ИП слов и словосочетаний (ключевые слова, организмы и др.). Динамические словари формируются дополнением и переупорядочением при записи в АБД новых ИО. Статические словари позволяют заменять в тексте ИП наиболее часто ветре- чающиеся короткие контексты ссылками на записи этих контекстов в словаре. Выбранная словарная организация позволяет значительно уплотнять вводимую в банк информацию, хотя.и увеличивает время заполнения банка. Кроме того, все динамические словари снабжены индексными файлами, в которых

для каждой записи словаря указаны номера ИО в АБД, содержащих эту запись. Использование индексных файлов обеспечивает быстрое выполнение многих стандартных . запросов к АБД (например, поиск всех ИО в АБД, характеризующихся заданным ключевым словом в некотором Я/7).

Диалоговый вариант АБД (в дальнейшем "банк") обеспечивает поиск ИО, удовлетворяющих определенным условиям: поиск контекстов в последовательностях и других ИП (см.Рис.2). Во многих блоках банк позволяет пользователю работать с картами, которые в скатом виде отображают расположение информации в отдельных информационных файлах банка (режим MAPPING).

Программный доступ к информации, хранимой в файлах АБД, обеспечивается интерфейсом, который используется в виде объектных модулей для сборки задач пользователя. С учетом наиболее популярных трансляторов, используемых при написании программ для персональных компьютеров, интерфейс реализован в нескольких вариантах для считывания информации в программы пользователя, написанные на языках:Turbo с,Turbo Pascal,Мв С,Ms Fortran. Интерфейс позволяет считывать ИП заданных ИО в АБД. Для увеличения скорости считывания информации интерфейс имеет набор внутренних буферов, оптимизирующих обмены с магнитным носителем. Механизм буферизации интерфейса аналогичен используемому в оптимизирующих драйверах операционной системы MS DOS (Smart Drive и др.).

Головной блок диалога АБД

i t t i

Рис.2. Общая схема структуры диалогового варианта АБД "Sagittarius" и взаимодействия его модулей.

ГЛАВА 5. ОБОЛОЧКА БАЗЫ ЗНАНИИ ДЛЯ АНАЛИЗА ПОСЛЕДОНАТЕЛЬНОСТЕЯ

Для организации хранения информации о последовательностях в наиболее общем виде необходимо выбрать оптимальную форму представления знаний, которая во многом определяет структуру оболочки базы знаний (ОБЗ). Проблема выбора формы представления знаний о последовательностях и их особенностях является решенной в некотором общем виде, поскольку в настоящий момент большинство БД по последовательностям имеют согласованный формат записи данных. В этом формате ключевым информационным полем является поле Feature Table, позволяющее описывать любые известные особенности участков последовательностей. Мы попытались использовать поле ft в качестве базового представления произвольных знаний о последовательностях. В некоторых случаях программы анализа последовательностей при выделении участков, соответствующих сайтам или структурным особенностям последовательностей, используют дополнительную числовую информацию, характеризующую выделяемый участок в целом или каждую входящую в него позицию последовательности в отдельности (например, профили гидрофобности пептидов). Таким образом, для обеспечения работы программ пакетов ОБЗ долина иметь формат записи FT, расширенный возможностью записи для каждой особенности последовательности дополнительной числовой информации, объем которой заранее не определен. В отличие от описанных ранее АБД, ОБЗ должна иметь развитый диалоговый интерфейс, позволяющий, в частности, производить редактирование {или уничтожение) ранее записанной информации.

С учетом описанных требований, нами выбрана следующая информацио1шая структура для описания последовательности как информационного объекта ОБЗ: номер клона; название клона; название последовательности; редактируемый текстовый комментарий к последовательности; программно редактируемый набор численных характеристик, описывающих последовательность (используется как набор флагов при обработке информации ОБЗ программами пакета); редактируемый набор особенностей (FT) участков последовательности.

Каждая из особенностей FT последовательности состоит из следующих составляющих: номер особенности (введен для

упрощения анализа списка особенностей последовательности программами пакета); числовой пароль (используется для предотвращения несанкционированного редактирования хранимой в ОБЗ разметки последовательностей); номер позиции е последовательности, соответствующий началу описываемого участка; номер позиции в последовательности, соответствующий концу описываемого участка; название (текстовое описание) особенности участка; редактируемый комментарий к особенности; ссылка на использованные при еыдэлэнии особенности АБД (используется при описании особенностей, выявленных яри сравнении с последовательностями из других баз); номер последовательности из АБД, сравнение с которой позволило выделить данную особенность; номера позиций в последовательности кз АБД, соответствующие началу и концу участка, использованного для выделения данной особенности; числовой массив и его длина (используется для записи различных функций, профилей и др. численной информации, характеризующей данную особенность); дата и время записи особенности в ОБЗ (используется для упрощения редактирования списка особенностей).

Аналогично АБД "Sagittarius", который являлся основой для создания описываемой оболочки, _ созданная ОБЗ имеет статические и динамические словари, упрощающие работу с информацией в диалоговом режиме. Используемая для хранения информации структура файлов аналогична описанным АБД, но с обеспечением возможности редактирования для большинства ■ информационных полей. Диалоговый и программный интерфейсы оболочки обеспечивают доступ ко всем информационным полям объектов (после- довательностей) с возможностями организации поиска, группировки объектов, ввода/вывода информации и т.д. Принципиальным отличием диалогового интерфейса оболочки от аналогичного интерфейса АБД является возможность редактирования комментариев к последовательностям и особенностям, а также редактирование (с использованием дедотирования) списка особенностей последовательности.

в н в о д ы

I. Разр5бот1я алгоритм иогтсльзуюпзй отражение

клвсскческса м^трлин точечной гомодепга последовательностей в ор',;вн-т>с'!С!Ш1.чй граф. .Маршрут максимального веса в таном гр'-'ф-"; r::v;:--T опткмальной выравнивание шсхэдователькбстей, •тсс'.т.спнпсо на псночз фрагментов гомологичных .■•п'-тгсе; -?лола?;/ тькоотей.

?. ?адр:.бо?.зн аятрпти вароБниваяия, использующий лрзр.ы.рятглыкР: отетис".гческай анализ и отбор гомологичных псглсс тедсяатэ-а^остей и обеспечиваквдЯ быстрое построение ог::1т;-,о."ь"ого выравнивания на основе таких 1го;ж;олодооател11-гасте.:й. Алгоритм представляет собой хлассчч'оского алгоритма Needlsraan-Wunsch для случая работы со сгатмки матрицам точечной гемолопга и позволяет учитывать икРорчацлю о статистической значимости го;.'.о.гог;п; подпоследовательностей на всех этапах построек:«! выравнивания.

3. Создея алгоритм сревнетшя к класси&жацки очинокислотинх последовательностей белков на оснобс анализа распределен:!« а:,':о:окислот в последовательностях, позволяяцай определить принадлежность белка к определенному семейству з общепринятой системе классификации по Eay'ioif.

4. Созданы автоматизированные банки дачных для компактного хране:п1я и обработки информации из наиболее распространении:* баз данных по последовательностям биополимеров (ЕШЗЬ, SwissF-rotein, PIR). Бршш имеют развитый ориентированный на пользователя диалоговый интерфейс, а также об.еспечивают возможность доступа к хранимой информации из программ пользователя.'

5. На основе разработанных банков данных создана оболочка базы знаний, обеспечивающая хранение результатов компьютерного анализа биологических последовательностей. База снабжена диалоговым интерфейсом (с возможностью редактирования информации) и обеспечивает чтение и запись информации из прикладных программ, что позволя"? использова tree в качестве основы для создания интегрированных пакетов программ обработки результатов анализа последовательностей биополимеров.

6. Разработанные■ банки данных, оболочка базы знаний, программы выравнивания использованы в качестве основы для создания интегрированного пакета программ, предназначенного для анализа результатов секвенирования нуклеотидных последовательностей в рамках программы "Геном человека".

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

1. Стрелец В.Б. // Метод выравнивания аминокислотных последовательностей. Институт цитологии и генетики СО АН СССР, Новосибирск, 1986, 31 стр.

2. Стрелец В.Б. // Банк первичных структур белков с пакетом прикладных программ для сравнения белковых последовательностей. Тезисы Всесоюзной конференции "Теоретические исследования и банки данных в молекулярной биологии и генетике", Новосибирск, 1988, стр.25-26.

3. Стрелец В.Б., Шиндялов И.Н. // Быстрый поиск сходства между аминокислотными последовательностями. Тезисы Всесоюзной конференции "Теоретические исследования и банки данных в молекулярной биологии и генетике".Новосибирск, 1988, стр.53-54.

4. Стрелец В.Б., Шиндялов И.Н. // Быстрые методы поиска сходства между аминокислотными последовательностями., Институт цитологии и генетики СО АН СССР, Новосибирск, 1988, 25 стр.

5. Стрелец В.Б., Колчанов Н.А. // Классификация аминокислотных последовательностей на основе экспертных оценок физико- химических и статистических параметров. Тезисы Всесоюзной конференции "Теоретические исследования и банки данных в молекулярной биологии и генетике", Новосибирск, 1988, стр.54-55.

6. Ponomarenko М.Р., Streleto V.B. // Expert system for protein sequences funotional recognizing. Abstraots of international conference "Modelling and computer methods in moleoular biology and geneticB", Novosibirsk, 1990, p.126-128.

7. Streleto V.B., Kolchanov N.A. // The programming support for the structural-functional analysis of sequences. Abstracts of international conference "Modelling and computer methods in moleoular biology & genetics", Novosibirsk, 1990, p.255-256.

8. Streleto V.B.,Shindyalov I.N., Kolchanov N.A., Milanesi L. // Effective statistically - based alignment of sequences. CAB10S, 1992, in press.