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

•л

СО

* у

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

; сибирское отделение новосибйрский 'институт органической химии

На правах рукописи Чупахина Ольга Михайловна

удк 51-76:577.212

сложностной анализ генетических текстов

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

Автореферат диссертации на соискание ученой степени кандидата технических наук

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

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

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

с.н.с. В.Д.Гусев

Официальные оппоненты:

доктор технических наук, профессор Ю.Г.Косарев

доктор биологических наук, профессор В.А.Ратнер

Ведущая организация: Институт молекулярной биологии

им. В.А.Энгельгардта РАН

Защита состоится "_" _ 1993 г.в _ часов

на заседании специализированного совета K-002.42.0I по присуждению ученой степени кандидата наук при Новосибирском Институте органической химии СО РАН по адресу: 630090, г. Новосибирск-90, проспект Академика Лаврентьева, 9.

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

Автореферат разослан "_" _1993 г.

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

В.И.Смирнов

г

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

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

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

Научная новизна.

Элементы новизны содержатся во всех главах работы. К ним относятся: определение меры сложности генетических текстов и сложностного профиля как универсального инструмента для обнаружения локальных структурных закономерностей (глава 1); рекуррентный алгоритм вычисления сложностного профиля с трудоемкостью существенно меньше квадратичной (глава 2 ); классифика-

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

Практическая ценность.

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

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

Реализация результатов работы.

Программа, реализующая вычисление гистограмм сложности по мере С1 и применимая к текстам произвольной природы, использовалась в составе пакета прикладных программ "СИМВОЛ", разработанного в ИМ СО РАН, для классификации зашумленных двоичных последовательностей марковского типа (имеется отзыв от ЦНИИ "Комета", г. Москва).

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

Метод исследования.

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

Публикации и апробация.

Основные результаты диссертации опубликованы в работах [1-9], докладывались на 3-м всесоюзном совещании "Теоретические исследования и банки данных по молекулярной биологии и ге-

нетике" (Новосибирск, 1988) и на международной конференции "Моделирование и компьютерные методы в молекулярной биологии и генетике" (Новосибирск, 1990), а также обсуждались на семинарах Института математики СО РАН и Института молекулярной биологии им. В.А.Энгельгардта РАН.

Структура и объем работы.

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

КРАТКОЕ СОДЕРЖАНИЕ

В первой главе дается обзор по различным мерам сложности конечных последовательностей: сложность по Колмогорову, энтропийные меры, грамматическая сложность, сложность по Лемпелю и Зиву. Вводятся новые меры сложности с, и С2 , а также понятие сложностного профиля.

Общая идея измерения сложности конечного объекта (в частности, текста) принадлежит А.Н. Колмогорову (1963 г. ). Она заключается в выборе самого короткого (из всех возможных ) описания объекта, по которому он может быть однозначно восстановлен с помощью некоторого фиксированного способа (устройства ) декодирования. Количественной мерой сложности выступает при этом длина наикратчайшего описания объекта. Если последовательность проста, т.е. обнаруживает какие-то регулярные закономерности, например, типа периодичностей, то ее описание может быть очень коротким. И, наоборот, сложные последовательности практически несжимаемы, поскольку не обнаруживают регулярностей в своей структуре.

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

Одной из возможных конструктивных реализаций идеи Колмо-

горова является определение сложности конечной последовательности, предложенное Лемпелем и Зивом. За меру сложности последовательности предлагается принять число шагов некоторого гипотетического процесса, порождающего эту последовательность. Множество допустимых (порождающих) операций включает в себя: а ) операцию генерации символа; б ) операцию копирования любого слова из предыстории. Из множества вариантов порождения последовательности выбирается вариант с наименьшим числом шагов.

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

Введем предварительно следующие обозначения: 2 - конечный алфавит, |2| - число элементов алфавита; Б - конечная последовательность, составленная из элементов алфавита 2 ; |Б| -длина Б; Э[±] - элемент Б, стоящий в л.-ой позиции (1-й по счету элемент Б); Б [л.:]] фрагмент Б, включающий элементы с 1-го по ;)-й (З^Лс;)^); Б=ОИ конкатенация (сцепление) последователь--ностей 0 и и (если |и| =Ы2 , то |э| =ыг , причем 0=

=Б[1:Ы], Е=Б[Ы +1:Ы1+Ы2 ] ).

Переход к мере Сг связан с расширением понятия повтора. Пусть Х=х1х2...х1( - слово, составленное из элементов 2; х = =х)|хн . ..х - то же слово, прочитанное в обратном направлении; £:2*2 - взаимно однозначное отображение алфавита 2 на себя; £(Х)=£(х )£(х )...г(х ) - слово X, элементы которого переименованы в соответствии с ^ £ (Х)к =£ (хн )...£ (х ) £ (х ) - результат последовательного применения преобразований ± и Вк х.

Пусть Х1 и х2- произвольные слова текста Б. Назовем пару (Х1,Х2) прямым повтором, если Х1=Х2; симметричным повтором, если х =х"; прямым £-повтором, если Х2 =£ ); симметричным

е

f-повтором, если х =(f(x ))". Введем следующие допустимые операции: а) операцию генерации нового символа; б) 4 типа операций копирования, каждая го которых ведет к образованию одного из перечисленных выше типов повторов. Факт наличия повтора типа "р" (р=1+4 ), образуемого двумя словами длины 1, начинающимися в позициях i и j (i>j ), условимся записывать в виде: S[i:i+l-l]=S(р 1 [j:j+l-l]. Процесс порождения заданной последовательности с использованием описанного выше набора операций выглядит следующим образом. Если по ходу процесса встречается символ, которого не было ранее, используется первая операция (генерация символа). Если же очередная цепочка символов может быть скопирована из уже порожденного текста путем применения одной из четырех операций, указанных в п. "б", то осуществляется копирование, причем выбирается та операция, которая поз-' воляет удлинить синтезируемую последовательность максимальным образом.

Таким образом, каждому шагу процесса ставится в соответствие фрагмент длиной от одного до нескольких символов. Историей формирования последовательности S назовем конкатенацию таких фрагментов:

Н2 (S)=S[l:il ]S[il+l:i2]...S[il[_l+l:il(]...S[im_i+l:N].

Здесь m=mH(S) - число шагов процесса, a S[i +1:1 ]- к-й 2

компонент истории (l^k^m), длина которого

i -i = max {max 1<р):S[i +l:i +1(р)]=

k k-! p "-1 "-1 J

k - 1

=S<P) [j:j+l]'P,-l]}. (1)

Номер позиции j=j(k), с которой начинается копирование k-го компонента истории, назовем указателем копирования этого компонента. Если используется операция генерации (т.е копирование невозможно), полагаем j(k)=0. С учетом этого соглашения к-й компонент истории может быть записан в виде

S [ i +1:1 ]= fsMOO^lO+ij^»» -1] при 3 (*)*<>, (2) lt"1 " lst^.,+1] при j (k)=0,

где j(k) и p(k) - значения параметров j и р, обеспечивающие максимум выражения (1). Схему формирования S в соответствии с (1) и (2 ) обозначим н* (S). Тогда

С2 (Б) = тн< (Б) . 2

Мера С1 может рассматриваться как частный случай меры С1, когда используется лишь одна операция копирования (по аналогии

С (Б) = шн, (Б) ). 1

При анализе первичных структур нуклеиновых кислот в качестве Г естественно выбрать отношение комплементарности:£(А)=т, £(Т)=А, £(С)=с. При этом наличие симметричных ^повто-

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

мер С и С . ^ 1 г

Пример 1.(сегмент полимеразы 1 генома вируса гриппа, штамм РЕ, позиция 1411,|Б|=30)

Б=СТССАСАССТТТТАТССААССТ6ТААССТА; ПОЗИЦИЯ 1 5 10 15 20 25 30

Н* (Б)•Т•С•в * А•С•А■в•СГ•ТТТ•А•ТСвА•АѕѕҕСГ•АА•в•СТ•А; ЖЖЖЖЖЖЖЖЖ Ж Ж Ж Ж ЖЖЖ Ж ЖЖ Ж

](к)= 000103511 10 52 5 321 18 1 21 5 С1 (Б) =20.

? ж ж ж ж Ж Ж ж ж ж Ж Ж

3(к)=0 0 1 1 4 1 10 5 2 5 14

р =0 0 4 4 2 1 1 1 1 4 2

С2(Б)=11.

Здесь р=о соответствует генерации нового символа, р=1 - прямому повтору, р=2 - симметричному повтору (пунктирные стрелки) Р=4 - симметричному ^повтору (стрелки без разрывов).

Сопоставление Н4 (Б) и Н2(Б) в приведенном примере показы-

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

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

Сложностным профилем текста Э (или профилем по мере С) назовем последовательность

Р(3,П)=С1С2...С1...Си.в + 1 ,. (3)

где С( - сложность фрагмента 311:1+0-1], ы=|з|. При

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

Будем считать значение сложности С из последовательности (3 ) экстремальным (аномальным), если

I С - СI 3= Зб, (4 )

где с^/(Ы-о+1) -среднее значение сложности всех фрагмен-

тов текста, б2= 2 (С[-С)2/(Ы-0) - несмещенная оценка дисперсии 1

значений сложности.

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

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

1) блок вычисления меры сложности конечной последовательности с помощью компактного префиксного дерева;

2) блок пересчета префиксного дерева при продвижении окна анализа вдоль последовательности;

3) блок пересчета меры сложности при движении окна

вдоль последовательности (этап вычисления сложностного профиля ).

Первый блок предназначен для вычисления начального значения сложностного профиля. Им является значение c^j , поскольку из алгоритмических соображений удобно сдвигать окно справа-налево, а не наоборот. Последующие значения профиля (cn-d,cn-d-i •'" ^ уже не считаются заново, а пересчитываются по рекуррентной схеме, в основе которой лежит перекрьгваемость соседних окон анализа на участке длиной в (D-1) символ.

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

Во втором блоке осуществляется рекуррентный пересчет префиксного дерева т , соответствующего окну S[i:i+D-l], в дерево т , соответствующее окну, сдвинутому на один символ влево. Экономия достигается за счет того, что коррекции подвергаются лишь отдельные узлы и связи дерева т .

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

Суммарная трудоемкость в среднем алгоритма вычисления сложностного профиля имеет порядок N-log2D/|2|.

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

ганизмов (сдвиговые и дрейфовые варианты вируса гриппа, бактериофаги X, Т7, вирусы БУ40, Эпштейна-Барра и ряд других), а также подборки знаков пунктуации различного вида. Устойчиво встречающиеся структурные закономерности можно разделить на элементарные и комбинированные.

К числу наиболее характерных элементарных закономерностей относятся:

а) серии повторяющихся фрагментов (периодичности);

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

в ) фрагменты с резким пре^Зладанием частоты какой-либо 1--граммы над остальными;

г ) разнесенные повторы;

д) палиндромно-шпилечные структуры;

в ) симметричные повторы;

Многие аномальные фрагменты (особенно длинные ) возникают в результате комбинации элементарных структурных закономерностей. Некоторые комбинации устойчиво повторяются в разных геномах. Из наиболее интересных и ранее не отмечавшихся закономерностей укажем на:

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

Этот класс закономерностей интересен с двух точек зрения:

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

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

Пример 2. (фрагмент генома вируса SV40, D=30, поз.5161, область начала репликации)

_2__2__4 4

1 1 11 3 3

" | cat | с | т • тт ■ g • с aaa • gc • ттт ■ ttgcaaa • agc • ст • aggc • с | тс | C2(S)=11

I—начало большого Т-антигена (по комплементарной цепи) Здесь повтор палиндрома (1) приводит к образованию шпилечной

структуры (2); повтор левой половины палиндрома (3) приводит к образованию палиндрома (4 ). Таким образом, даже частичное повторение палиндрома может привести к образованию новых структур . *

Все выше сказанное (с соответствующей перефразировкой) справедливо и по отношению к повторению симметрии.

з) блочные симметрии. Этим термином мы обозначаем конструкции вида:ар7>. ."ура, где а, р, 7 - элементарные повторы. Обычная симметрия является частным случаем блочной (при |а|= = 1 Р1 = IТi = - • -=1 )• Совпадение обоих типов симметрия имеет место, когда а, р, 7... - симметричные блоки (например,

ctcgaag'gaagctc ). Простейшую и наиболее распространенную фор-

W

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

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

и) дуальные структуры. Этот термин используется для отражения своего рода "дуализма", существующего (далеко не всегда ) между разнесенными симметричными и комплементарными симметричными повторами (шпильками). Он проявляется в том, что петля у шпильки нередко имеет симметричную форму и, наоборот, "петля" у симметричного повтора иногда имеет форму комплементарного палиндрома. Обе возможности иллюстрируются ниже.

Пример 3.(фрагмент эукариотического промотора HSLCAT,

-91 позиция )

1 2,2 1

CTGGCCACAACCCCCACTGGCCAG I_I I_I

Шпилечная структура (1) здесь образована повторением элементарного палиндрома TGGCCA. Петля в шпилечной структуре представлена симметричным фрагментом (2 ).

Пример 4.(фрагмент генома фага X, ген J, поз. 17357) 1 2 2 1

CGCCAGCGGTGCAGCACCTGACCGC Здесь симметричные фрагменты (1) фланкируют комплементарный палиндром (2 ).

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

В главе 4 иллюстрируется процесс построения сложностных профилей с окнами увеличивающегося размера (D=20, 30, 50, 100, 150 нк) - на примере генома с известной разметкой (бактериофаг X). Обсуждается вопрос о функциональной значимости минимальных по сложности фрагментов. Показано, что около половины выделяемых аномальных фрагментов позиционно тяготеют к активным (в плане управления) зонам генома (это - начала и концы генов; промоторы и терминаторы транскрипции; зона начала репликации; границы между модулями - группами последовательно расположенных генов, выполняющих определенную функцию; потенциальные "горячие" точки генома, содержащие аналоги сайта рекомбинации фага X).

Среди аномальных фрагментов, выявленных окном размера 150 и более, многие можно условно назвать "зонами обширной гомологии" - ЗОГ (к таковым, к примеру, относится фрагмент из orf-401 (позиция 20083+20416 ), фрагмент из некодирующей области (позиция 35547+35809 ), содержащий промотор X.PL И TIMM -

терминатор транскрипции, зона начала репликации в гене О (позиция 38963т39200 ) и ряд других ). Малая сложность таких фрагментов обусловлена наличием в них достаточно протяженных гомологичных участков (типа итеронов в гене О или 4-кратной периодичности в промоторе Хрь), многие из которых в свою очередь, содержат внутренние периодичности. Подобная иерархическая структура ЗОГ инициировала появление "гипотезы об иерархической дупликации".

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

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

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

Глава 5 посвящена анализу геномов на глобальном уровне. Он подразумевает оценку сложности генома в целом, а также выявление ассоциативных связей между локальными (уже не обязательно аномальными по сложности) фрагментами, произвольно разнесенными по длине генома.

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

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

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

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

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

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

5. На основе анализа длинных аномальных фрагментов в различных геномах (в частности, в геномах фага X, вируса Эпштей-

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

6. Результаты обработки геномов с известной разметкой демонстрируют широкий спектр возможных интерпретаций аномальных зон: а ) аномальные зоны небольшого размера (0=2(Н50 ) могут выделять отдельные знаки пунктуации; б ) происхождение некоторых аномальных зон обусловлено повышенной активностью блочных перестроек на границах крупных структурных областей (начала и концы генов, межмодульные интервалы, экзон-интронные и инт-рон-экзонные переходы и т.п. ); в) аномальные фрагменты внутри кодирующих областей часто выявляют некоторые регулярности на белковом уровне (повторяющиеся цепочки аминокислот, кластеры заряженных аминокислот и т.п.); г) "горячие" точки рекомбинации могут сигнализировать о себе аномально низкими значениями сложности. Часть аномальных фрагментов, особенно коротких, по-видимому, не несет функциональной нагрузки или не может быть пока проинтерпретирована в рамках существующих представлений о структуре генома.

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

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

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

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

ЛИТЕРАТУРА

1. Гусев В.Д., Чупахина О.М., Куличков В.А. Сложностные профили - новый метод обнаружения структурных закономерностей в первичных структурах НК-молекул и белков // 3 Всесоюз. со-вещ. "Теоретические исследования и банки данных по молекулярной биологии и генетике", Новосибирск, июль 1988: Тез. докл. -Новосибирск, 1988. - С. 38-39.

2. Гусев В.Д., Куличков В.А., Чупахина О.М. Сложностной анализ генетических текстов (на примере фага X).- Новосибирск, 1989. - 48 С. - (Препр. / Ин-т математики СО АН СССР; N 20).

3. Чупахина О.М. Алгоритм построения сложностного профиля для символьной последовательности // Вычислительные системы. - Новосибирск, 1989. - Вып. 132: Методы обработки символьных последовательностей и сигналов. - С. 64-91.

4. Гусев В.Д., Куличков В.А., Чупахина О.М. Сложностной анализ геномов. I: Меры сложности и классификация выявляемых структурных закономерностей // Молекуляр. биология. - 1991, Т. 25, ВЫП N 3-е. 825-833.

5. Гусев В.Д., Куличков В.А., Чупахина О.М. Сложностной анализ геномов. II: Зоны обширной гомологии в бактериофаге х // Молекуляр. биология. - 1991.- Т. 25, ВЫП N 4.-е. 1080-1089.

6. Гусев В.Д., Чупахина О.М. Поиск и классификация фрагментов текста с одинаковой сложностной структурой // Вычислительные системы. - Новосибирск, 1991. - Вып. 141: Анализ временных рядов и символьных последовательностей. - С.25-45.

7. Gusev V.D., Chupakhina О.М., Kulichkov V.A. Complexity Profiles of Genetic Texts // Modelling and computer methods in molecular biology and genetics. - Nova Science Publishers,

Inc. - 1992.

8. Gusev V.D., Kulichkov V.A., Chupakhina O.M. The Lempel-Ziv complexity and local structure analysis of genoras // BioSystems. - 1993. - V. 30. - P. 183-200.

9. Gusev V.D., Kulichkov V.A., Chupakhina O.M. Global complexity analysis of genoms // BioSystems. - 1993. - V. 30. -P. 201-214.

Подписано к печати 1993 г. Заказ Ц1

Формат бумаги 60 * 84/16 Объем 1 п.л. Уч.-изд. 0.75

Тираж 100 экз.

Ротапринт Института математики СО РАН,

630090, Новосибирск - 90, Университетский пр., 4.