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

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

Мирошниченко Любовь Александровна

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

Специальность 05.13.17 - Теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

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

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

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

кандидат технических наук, старший научный сотрудник Гусев Владимир Дмитриевич

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

доцент Васюков Василий Николаевич

кандидат технических наук Витяев Евгений Евгеньевич

Ведущая организация: Институт вычислительных

технологий СО РАН (г. Новосибирск)

Защита состоится 21 декабря 2005г. в 14-00 на заседании диссертационного совета Д 212.173.06 в Новосибирском государственном техническом университете, 630092 г. Новосибирск, пр. К. Маркса, 20

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

Автореферат разослан 18 ноября 2005 г.

Ученый секретарь

диссертационного совета ¡Муь- Чубич В.М.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Цели исследования:

— разработка новых методов выделения структурных единиц в символьных последовательностях, применимых в условиях минимальной априорной информации об искомых объектах;

— построение эффективных алгоритмов поиска структурных единиц, заданных в виде определенных шаблонов (или образцов).

Основные направления исследований:

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

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

— учет позиционной информации для выделения и оценивания значимости структурных единиц;

— разработка эффективных алгоритмов поиска в тексте образцов, представленных в виде цепочек из константных и переменных символов.

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

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

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

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

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

Известная задача поиска по групповому запросу (Ахо, Корасик, 1975г) обобщена на случай частично специфицированных образцов. Предложены эф-

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

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

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

Апробация работы. Основные результаты докладывались на Сибирских конгрессах по прикладной и индустриальной математике (ИНПРИМ-98 и ИН-ПРИМ-2000); на конференции по распознаванию образов и анализу изображений (РОАИ-4-98); на конференциях по биоинформатике (ВОК8'2000 и ВОКБ'2002, г. Новосибирск), на 6-м российско - немецком семинаре "Распознавание образов и понимание изображений" (СЮК\У-6-2003), на конференции "Компьютерная лингвистика и интеллектуальные технологии" (Диалог-2005). Отдельные этапы работы прошли экспертизу в ходе выполнения проектов, под-

держанных грантами РФФИ (проекты № 96-06-80576, 00-06-80420, 03-0680118), РГНФ (№ 03-04-00392) и СО РАН (№ 65, 2001-2002гг).

Личный вклад. Основные результаты, связанные с разработкой, исследованием и апробацией алгоритмов выделения структурных единиц в символьных последовательностях, получены автором лично. Постановка задач сложно-стного анализа и обсуждение возможных путей их решения осуществлялись совместно с руководителем. Разработка ДНК-ориентированного комплекса программ LZcompozer (http://wwwmgs.bionet.nsc.ru/mgs/programs/lzconiposer/) проводилась совместно с сотрудниками ИЦиГ СО РАН [15,20]. Процедура поиска по групповому частично специфицированному запросу разработана лично соискателем. Адаптация ее применительно к информационно-поисковой системе PROF-PAT 1.0 осуществлена разработчиками этой системы [4]. В приложениях, связанных с анализом текстов на естественном языке, вклад автора состоял в выделении структурных единиц высокого уровня (сверхфразовых единств).

Публикации. По теме диссертации опубликованы 22 работы, из них 10 статей в рецензируемых журналах, 7 в научных сборниках и 5 в трудах международных конференций. До 2003 года автор диссертационной работы представлен под фамилией Немытикова.

Структура работы. Диссертационная работа изложена на 222 страницах и состоит из введения, обзора литературы (глава 1), четырех глав, содержащих основные результаты, и заключения. Иллюстративный материал представлен 14 рисунками и одной таблицей. Список литературы включает 180 ссылок КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ В первой главе представлен обзор работ, связанных с выделением структурных единиц в текстах различной языковой природы. Сделан вывод о том, что основным структурообразующим элементом текста является повтор, трактуемый в Простейшем случае как пара тождественных фрагментов текста. В общем случае можно рассматривать несовершенные (те. искаженные или

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

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

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

— дешифровочный подход Б.В. Сухотина, где введено понятие устойчивости отрезка текста и формируется словарь структурных единиц с максимальной суммарной устойчивостью составляющих его элементов;

— метод Лемпеля и Зива, минимизирующий число шагов порождающего процесса, где каждый шаг связан с формированием структурной единицы;

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

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

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

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

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

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

Пусть £ - конечный алфавит; |£| - число элементов алфавита; 5 - конечная последовательность, составленная из элементов £ (текст); N = |51 - длина текста 5 [г] -элемент стоящий в /'-й позиции (1 < г < Ы)\ 3 [г: /] - фрагмент 5, включающий элементы с г-го по у'-й (1 </<_/< 5 = QR - конкатенация (сцепление) последовательностей <2 и Л. Лемпель и Зив предложили измерять сложность последовательности числом шагов порождающего процесса. Каждый шаг состоит в копировании максимально длинной "заготовки" из уже синтезированной части текста и (или) генерации символа Схема порождения 5, называемая в дальнейшем сложностным разложением, представляется в виде конкатенации фрагментов

Я(5) = 5[1:/1]5[/1+1:/2]„.5[/4_1+1:/4]...5[/и_,+1:ЛГ], (1)

где +1: ¡к ] — фрагмент, синтезируемый на к-м шаге, т — число шагов процесса, определяющее сложность последовательности по Лемпелю и Зиву: Си{8) = т = тн{8). (2)

Пример 1. Пусть £ = {А,В} и 8 = АВВАВААВВААВАВВА. Пошаговая схема порождения 5 имеет вид: Я(5) = А В ВА ВАА ВВАА ВАВВ А , С17 = 7. Здесь компоненты разложения отделены друг от друга точками, а копируемые фрагменты подчеркнуты.

Разложение (1) можно рассматривать как простейший способ структурирования последовательности, но оно не учитывает внутритекстовые проявления симметрии и изоморфизма. Первый шаг в этом направлении был сделан Гусевым В.Д. и Чупахиной О.М., предложившими ДНК-ориентированный вариант меры (2). В настоящей работе сделан следующий шаг в обобщении меры (2): разрешено прямое и симметричное копирование, а также любые (не фиксируемые заранее) переименования элементов алфавита. Общее число допустимых операций копирования составляет 2|Г|!. Запись S [;': i + / - 1] = S w (/' \j + l - 1] фиксирует факт наличия повтора типа р (1 < р < 2|Е|!), образуемого двумя фрагментами длины /. Схема порождения 5, обозначаемая далее Hf, представи-ма в виде (1), но длина (ц - ц-\) фрагмента, синтезируемого на к-м шаге, максимизируется путем выбора наиболее подходящей операции копирования. Формально

ik - = тах {тах/ : +1: + l/p)} = S^ [j: j +llp> - J]}. (3)

m-\ l p J

Если вместо копирования используется генерация символа, полагаем j(k) = 0. К-й компонент сложностного разложения можно записать в виде:

+ ПРИ Кк)Ф°' (4)

+1] при j(k) = 0,

Пример 2. Пусть S = GCGGAGGGCGGAGTGGTGCCTTTAAAAGGC, I = {A,C,G,T}. Hf{S) = G(0,0) CG(1,3) GAGG(1,7) GCGGAG(1,1) TGG(10, -12) TGC(12,12) CTTTA(5,8) AAAGGC(18, -24).3десь в скобках справа от каждого компонента разложения указана пара чисел: j(k) — указатель начальной позиции копирования на к-м шаге; р(к) — указатель способа копирования (номер подстановки в списке из 24 возможных подстановок; знак (+) при р{к) соответствует прямому копированию, а (-) -симметричному). Например, четвертый компонент фиксирует тандемный повтор со вставкой (GCGGAG)G(GCGGAG), расположенный в начале S. Компонент № 7 (СТТТА) демонстрирует наличие в тексте серий Т3 и G3 одинаковой длины (подстановка А о С, G Т). Компо-

нент № В фиксирует комплементарный палиндром ОССТГТ А АААСЮС (подстановка А <-> Т, С <-» С). Число компонентов в разложении Н^) определяет значение сложности С/5) = 8 (Си. (5)= 12).

Основную трудность при вычислении меры сложности С/составляет выбор оптимальной подстановки на каждом шаге. Пусть и — произвольное слово длины I. Наддиагональную матрицу В(и) порядка 1x1 с элементами

1. если иЩ = и\к] ,, „

Ь, -1 (к > [) назовем структурной матрицей слова и.

[О, если «[/] * и[к] Ее можно преобразовать в двоичный (структурный) вектор Ф(и) путем конкатенации наддиагональных столбцов. На принципиальную возможность обхода факториального перебора при вычислении меры С/указывает следующее

Утверждение. Пусть х - произвольный компонент длины I в сложност-ном разложении последовательности 5 по мере С/, у - его прототип (| у \ = | х |), р - подстановка, переводящая уъх. Тогда при любом р В(у) = В(х) (соответственно, Ф(у) =Ф(х)).

Пример 3. Пусть £ = {а, Ь, с}, х = аЬасса, у = ЬсЬааЬ, р={Ь~>а, а->с, с->Ь}.Тогда

аЬасса Ьс

а а

= 010 0 1 а = 010 0 1 ь

= 00 0 0 Ъ = 00 0 0 с

= 0 0 1 а =В(х)=В(у)= = 0 0 1 ь

= 1 0 с = 1 0 а

= 0 с 3 0 а

з а 5 Ь

и, соответственно, Ф(и) = 0 10 ООО 0001 10100.

Реализующий эту идею алгоритм вычисления меры Су основан на построении дерева по множеству структурных векторов, соответствующих всевозможным ¿-символьным цепочкам исходного текста. Трудоемкость алгоритма составляет 0(Ь2М), где значение Ь зависит от размера алфавита и имеющих-

ся ресурсов оперативной памяти. Для широкого круга приложений приемлемым является выбор Ь в диапазоне от 6 до 10.

Частные случаи меры С/ возникают при сужении множества допустимых подстановок. В пределе для каждой подстановки может быть вычислена своя мера сложности и текст может быть охарактеризован вектором из 2|2|! чисел. Векторная мера сложности ориентирована на малые алфавиты и позволяет определить, какой тип повторности преобладает в тексте и каково количественное соотношение между прямыми и симметричными повторами.

65

15

0 20000 40000 60000 80000 100000 120000 140000 160000

Позиции текста 1 (положение окна)

Рис. 1. Профиль сложности последовательности "Epstein-Barr virus (EBV)". Длина текста - 172281, размер окна - 200. Среднее значение сложности в окне - 52.85 (обозначено пунктиром), s = 4,77.

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

P(S,W) = clc2...cl...cN-lr+l, (5)

где с, - сложность фрагмента S [/: i + W- 1], 1 <i<N- W+ 1. Важными параметрами сложностного профиля являются:

11

стт =пипс,; с = &с,)/(ЛГ - 1Г +1); = 1Дс,-с)2/(Ы-1У)

I

и ряд других. Реализован алгоритм рекуррентного пересчета значений сложности в скользящем окне. Наиболее значимы фрагменты текста с аномально низкими значениями сложности. Они характеризуются интересными структурными особенностями. На рис. 1 приведен график сложностного профиля генома вируса Эпштейна-Барр. Главный минимум обусловлен не менее чем 30-кратным варьированным повторением цепочки из 18 нуклеотидов.

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

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

(большом) алфавите. На рис.2 приведен пример аномально длинной (/ = 41) (не С)-серии в сегменте ИБ (штамм РЯ) вируса гриппа.

поз. 710 (начало поз. 717 (терминальный кодон N81) серии)4 ^

...ÇA (GAAGTT (GTT GAI

TGA TGA

AGAAATAAGA) TG

_|A GAA GTG AGA1 ÇA

поз. 738T~GhT Glu ArgN™»- 750

(_) (_) (+) (конец серии)

Рис 2 Серия, не содержащая С-элементов, выявленная при агрегировании {С}, {A,G,T}.

Подобные структурные элементы далеко не всегда могут быть выявлены с помощью сложностного профиля. Локальная сложность таких участков обычно ниже средней, но не каждый из них проходит тест на аномальность Для малых алфавитов (в частности, для ДНК-последовательностей) в работе реализованы все возможные варианты агрегирований. При каждом агрегировании вычисляются следующие серийные характеристики: /imax - длина максимальной серии типа q (при разбиении I на два подмножества q принимает значения 0 и

шах

1 )\ rv - число д-серий длины j (J = 1,2,..., /imax); г = £ Е гщ - общее число сеч J-1

к

рий; rq(k)= Y.rq/ ~ число д-серий с длиной, не превышающей к;

i=1

'дтах

рч(к) = X гц ~ число ç-серий, длина которых не меньше к\ d4{k) - длина мак-

j=k

симального фрагмента, в котором расстояние между соседними элементами типа q не превышает к (кластеры из ^-элементов).

Предложено несколько новых критериев кластеризуемости, отличительной чертой которых является совместный учет результатов разных агрегирований. Один из таких критериев оперирует с суммарным по всем агрегированиям числом серий, длина которых не меньше k Ъ{к) = Y.T.p'q(k), где параметр

' ч

i пробегает по всем учитываемым вариантам агрегирования, a q - по всем ти-

13

пам серий при 1-м агрегировании, рч'(к) - число серий типа д с длиной не меньшей чем к при 1-м варианте агрегирования. Значимость выявляемых аномалий оценивалась с помощью имитационного моделирования.

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

— наиболее интересными в структурном и функциональном отношении являются аномально длинные серии Чаще всего они носят дупликативный характер и расположены на границах крупных структурных единиц;

— характер избыточности ДНК- и АМ-последовательностей, которые в целом мало отличаются от случайных, в значительной мере определяется кластеризацией элементов определенного типа в отдельных участках текста;

— критерий кластеризуемое™, основанный на совместном учете результатов разных агрегирований, дает дополнительные возможности по сравнению с критериями, использующими какое-то одно агрегирование;

— существуют устойчивые комбинации совместно встречающихся серий из разных агрегирований с длинами не меньшими заданного порога к. С помощью специально разработанного алгоритма для обнаружения таких конструкций выявлено, например, что комбинация серий типа А? (Л = {А,О}, £ = {О,С}) аномально часто встречается в эукариотических промоторах (к - 5,6,7), тогда как комбинация ¿7? не обнаруживает таких аномалий;

— важное значение имеют агрегирования типа { а, £ \ а), где а - выделенный элемент алфавита, а £ \ « - множество оставшихся элементов. Они позволяют исследовать степень равномерности позиционного распределения элемента а по тексту. Показано, что многие аминокислоты демонстрируют яркие аномалии в позиционном распределении. Это может свидетельствовать об их повышенной функциональной нагрузке. Техника позиционного анализа более подробно рассмотрена в следующей главе.

В четвертой главе исследуется возможность использования позиционной информации для выделения структурных единиц и оценивания их информативности. Наиболее информативными лингвисты считают среднечастотные цепочки (слова), демонстрирующие неравномерное распределение по длине текста. Эффективным средством для выявления позиционных аномалий являются сканирующие статистики. В работе используется статистика с/1 (я), равная длине минимального интервала, содержащего ровно п точек (выделенных символов или слов) и статистика £>1(я), определяющая длину максимального несужаемо-го интервала, содержащего и точек. Интерес представляют также второй минимум (<й(л)) и второй максимум (£>2(л)). На основе указанных и связанных с ними статистик предложена методика выявления и интерпретации позиционных аномалий в тексте.

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

Апробация разработанной методики проводилась на биологических текстах (ДНК- и АМ-последовательности) и текстах на естественном языке.

Пример 4. а) распределение слова "Тигер", встречающегося 183 раза в варианте перевода книги Алана А. Милна "\Vinnie-the-pooh", сделанного В. Ве-бером и Н. Рейн (Ы = 43554 слов), демонстрирует сильную аномалию в виде "гэпа" (первая половина текста не содержит этого слова) и три значимых кластера во второй половине. Аномальные кластеры либо совпадают с крупными

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

б) слово "chapter" (глава) в оригинале "Винни-Пуха" демонстрирует сверхравномерное распределение.

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

В пятой главе рассматривается проблема эффективного поиска образцов в тексте Исследуется два типа образцов: частично специфицированные (ЧС) и образцы с одной переменной в константном окружении,

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

Пример 5. Пусть Е = {A,G,C,T} - исходный алфавит, У={С,Т}, R={A,G}, Х - указатель "несущественной" позиции, где может стоять любой элемент исходного алфавита. Цепочка p=GTTGC YXGRCA А С является примером ЧС-образца. Он описывает множество из Q(p) = 2x2x4 = 16 цепочек в алфавите Е, получаемых подстановкой допустимых элементов вместо Y, R и X Величина Q(p) характеризует степень неопределенности ("размытости") образцар (если р е т.е. образец задан точно, то Q(p) = 1).

Рассматривается задача поиска по групповому ЧС-запросу, когда число образцов в группе велико (~ 103 - 104). Для случая, когда образцы точно заданы (т.е. Q(p,) = 1, 1 < I <п, п- число образцов в группе), эффективный алгоритм поиска, основанный на предобработке образцов и построении распознающего конечного автомата, предложен Ахо и Корасик. Прямое сведение нашей задачи к алгоритму поиска по детерминированному групповому запросу не проходит из-за экспоненциально возрастающих в зависимости от числа ЧС-позиций затрат памяти и времени. Предлагаемое решение состоит: 1) в выборе в каждом образце /7, опорного ядра г, длины / с минимальной степенью неопределенности {,) « <2(р)\ 2) замене ядер г, эквивалентными множествами константных ядер; 3) построении по ним распознающего автомата; 4) обнаружении с его помощью константных ядер в анализируемом тексте; 5) расширении их до размеров образца с целью проверки согласованности символов текста с элементами образца, не вошедшими в состав ядра. Оптимизирован выбор размера ядра /, получены оценки трудоемкости алгоритма.

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

Образцы второго типа задаются в виде цепочек, составленных из элементов двух непересекающихся алфавитов: константных символов Е и переменных Д. Образец, например, может иметь видр = г^Х^ХгИХ^, где цепочки е I* (/ = О -н 3), т.е. содержат только константные символы, а элементы Х1 е Д (/' = 1, 2) и

каждый из них может быть заменен произвольной цепочкой константных символов. При этом вхождениям одной и той же переменной должна соответствовать одна и та же подстановка. Задача поиска таких образцов при отсутствии ограничений на размер алфавита Д относится к числу NP-полных проблем. Однако значительный практический интерес представляют различные частные случаи общей проблемы, допускающие полиномиальное решение К ним относится задача поиска образцов с одной переменной в константном окружении, представимых в видер = t0X ttX...X tk, где все t, £ £*, X е Д, | А | = 1. Предложен алгоритм отыскания таких образцов, адаптивно настраивающийся на параметры образца и текста (число вхождений (к) переменной в образец (к > 2), длина максимального повтора кратности к в тексте и др.). В предположении, что /'„ах имеет порядок \nN (это справедливо для случайных текстов), трудоемкость алгоритма в среднем составляет 0(N InJV), где N- длина текста. Наилучший из известных алгоритмов-аналогов имеет трудоемкость 0(N2 \nN).

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

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

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

ных и бактериальных геномов, выявления блочных перестроек в регуляторных областях различных генов, вычисления мер сходства между последовательностями дисков политенных хромосом хирономид и в ряде других приложений. Совместно с Институтом Цитологии и Генетики СО РАН реализован многоцелевой программный продукт для оценивания сложности, доступный по адресу http://wwwmgs.bionet.nsc.ru/mgs/programs/lzconiposer/.

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

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

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

6. Предложен алгоритм отыскания в тексте образцов с одной переменной в константном окружении, адаптивно настраивающийся на параметры текста и образца. Трудоемкость алгоритма в среднем составляет 0(N InN), где N - длина текста, что в большинстве случаев обеспечивает значительный выигрыш по сравнению с известными (неадаптивными) алгоритмами.

Содержание диссертации отражено в следующих работах:

1. Немытикова Л.А. Методы сравнения символьных последовательностей // Вычислительные системы,. вып. 132. - Новосибирск, 1989. — С. 3-34.

2. Гусев В.Д., Немытикова Л.А. Анализ серий в генетических текстах // Вычислительные системы, вып. 141. -Новосибирск, 1991. - С. 46-76.

3. Немытикова Л.А. Использование серийных характеристик для исследования эффекта кластеризации элементов в ДНК-молекулах // Вычислительные системы, вып. 150. - Новосибирск, 1994. - С. 147-163.

4. Бачинский А.Г., Гусев В.Д., Немытикова и др. Новая версия банка образов PROF-PAT 1.0: технология формирования и программа быстрого поиска образов в аминокислотных последовательностях // Молекулярная биология. -1996, №. 6, C.I409—1417.

5. Гусев В.Д., Немытикова Л.А. Алгоритмы поиска в текстовых базах данных по групповому частично специфицированному запросу // Вычислительные системы, вып. 157.-Новосибирск, 1996.-С. 12-39.

6. Немытикова Л.А. Использование недетерминированных конечных автоматов для ускорения поиска в текстовых базах данных // Вычислительные системы, вып. 160. - Новосибирск, 1997. - С. 188-209.

7. Gusev V.D., Nemytikova L.A. Complexity Characteristics of Genetic Texts (Сложностные характеристики генетических текстов) / Pattern Recognition and Image Analysis. -1999. - Vol.9, №1.-C. 52-55.

8. Gusev V.D., Nemytikova L.A. The use of finite automata to speed up searching in the text data bases (Использование конечных автоматов для ускоре-

ния поиска в текстовых базах данных) // Joint Bulletin of NCC & IIS, Series: Computer Sciences. - 1999. - Issue 12. -C.10-14

9. Gusev V.D, Nemytikova L.A., Chuzhanova N.A. On the complexity measures of genetic sequences (Меры сложности генетических последовательностей) // Bioinformatics. - 1999. - Vol.15, № 12. - P. 994-999.

10. Chuzhanova N.A., Krawczak M., Nemytikova L.A., Gusev V.D., Cooper D.N. Promoter shuffling has occurred during the evolution of the vertebrate growth hormone gene (Перестановка блоков - как элемент эволюции генов гормона роста у позвоночных) // Gene. - 2000. - Vol. 254. - P. 9-18.

11. Chuzhanova N.A., Krawczak M., Gusev V.D., Nemytikova L.A., Cooper D.N. Complexity measures of symbolic sequences and their application to DNA analysis (Меры сложности символьных последовательностей и их применение к анализу ДНК) // Ргос. 2nd Int. Conference on Bioinformatics of Genome Regulation and Structure (BGRS'2000), Novosibirsk, August 7-11,2000, Vol.2, P.79-81.

12. Гусев В.Д., Немытикова JI.A., Чужанова H.A. Быстрый метод выявления взаимосвязей в подборках функционально и/или эволюционно близких биологических текстов // Молекулярная биология, 2001, 35(6), С. 1015-1022

13. Гусев В.Д., Немытикова JI.A. Учет проявлений повторности, симметрии и изоморфизма в символьных последовательностях II Вычислительные системы, вып. 167. - Новосибирск, 2001. - С. 11-33.

14. Kiknadze I.I., Gunderina L.I., Istomina A.G., Gusev V.D.,Nemytikova L.A. Similarity analysis of inversion banding sequences of Chironomus species (breakpoint phylogeny) (Анализ сходства инверсионных последовательностей дисков у видов хирономид - филогения по точкам разрыва хромосом) // Bioinformatics of genome regulation and structure, Boston-Dordcht-London, 2003, P. 245-253.

15. Orlov Yu.L., Gusev V.D., Nemytikova L.A., Filippov V.P. Internet-available software system LZcomposer for analysis of genome sequence structure on the basis of complexity decompositions (Интернет-доступный пакет Lzcomposer для анализа структуры генома на основе сложностных разложений) // Ргос. 3d

Int. Conference on Bioinformatics of Genome Regulation and Structure (BGRS'2002), Novosibirsk, 2002. - Vol. 3. - P. 260-263.

16. Orlov Yu.L., Gusev V.D., Nemytikova L.A Software package LZcom-poser: analysis of occurrence of repeats in complete genomes (Пакет Lzcomposer: анализ повторов в полных геномах) И там же, Р. 247-250.

17. Chuzhanova N.A., Krawczak М., Thomas N., Nemytikova L.A., Gusev V.D., and Cooper D.N. The evolution of the vertebrate beta-globin gene promoter (Эволюция промоторов (3-глобиновых генов позвоночных) // Evolution. - 2002. -Vol. 56,№2.-P. 224-232.

18. Гусев В.Д., Немытикова JI.A., Саломатина Н.В. Выявление аномалий в распределении слов или связных цепочек символов по длине текста // Вычислительные системы,. вып. 171.-Новосибирск, 2002.-С. 51-74.

19. Gusev V.D, Nemytikova L.A., Chuzhanova N.A. Adaptive algorithm of pattern matching in symbolic sequences (Адаптивный алгоритм поиска образцов в символьных последовательностях) // Pattern recognition and image understanding (OGRW-6-2003) / Workshop Proceedings. - 2003. - C.42-45.

20. Orlov Yu.L., Gusev V.D., Miroshnichenko L.A. LZcomposer: decomposition of genomic sequences by repeat fragments (LZcomposer: разложение геномных последовательностей на повторяющиеся фрагменты) // Biophisics, Vol.48, Suppl.l, 2003, S7-S16.

21. Гусев В.Д., Мирошниченко Л.А., Саломатина Н.В. Тематический анализ и квазиреферирование текста с использованием сканирующих статистик //"Компьютерная лингвистика и интеллектуальные технологии" / Труды международной конф. Диалог'2005, М., Наука, 2005.

22. Гундерина Л.И., Кикнадзе И.И., Истомина А.Г., Гусев В.Д., Мирошниченко Л.А. Дивергенция последовательностей дисков политенных хромосом как отражение эволюционных преобразований линейной структуры генома // Генетика, 2005, Т. 41, № 2, стр. 187-195.

Отпечатано в типографии Новосибирского государственного технического университета формат 60x84/16, объем 1 пл., тираж 100 экз., заказ , подписано в печать 17.11.05 г.

15 2 з 3 3 f

РНБ Русский фонд

2006-4 27572

Введение

Глава1. Обзор методов выявления структурных единиц в символьных последовательностях

1.1. Элементарные структурообразующие единицы текста

1.2. Методы сегментирования символьных последовательностей

1.2.1. Морфологический анализ текста без пробелов

1.2.2. Сложностные разложения символьных последовательностей

1.2.3. Иерархическое представление последовательностей с помощью порождающих грамматик.

1.2.4. Выявление моментов изменения свойств последовательности

1.3. Методы фрагментирования символьных последовательностей

1.3.1. Статистические (частотные) методы фрагментирования

1.3.2. Позиционные методы фрагментирования

1.3.3. Суперсинтаксические методы фрагментирования.

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

1.3.5. Поиск локальных аномалий в режиме скользящего окна.

1.3.6. Агрегирование алфавита как способ выявления локальных структурных закономерностей

1.3.7. Задание структурных элементов в виде образцов.

Выводы по первой главе

Глава 2. Методы выделения структурных единиц на основе сложностных разложений текста

2.1. Различные модификации меры сложности Лемпеля-Зива

2.1.1. Понятие /-повтора и его использование в сложностных разложениях

2.1.2. Векторная мера сложности

2.1.3. Мера сложности с пошаговой оптимизацией по ограниченному набору подстановок

2.1.4. Мера сложности с пошаговой оптимизацией по полному набору подстановок (мера С/)

2.2. Алгоритмы вычисления сложности символьной последовательности

2.2.1. Алгоритм вычисления сложности при фиксированной подстановке

2.2.2. Алгоритм вычисления меры С/

2.3. Сложностные профили символьных последовательностей.

2.4. Случай нескольких последовательностей

2.5. Некоторые свойства сложностных разложений

2.6. Примеры применения сложностного анализа к биологическим текстам

2.6.1. Выявление блочной структуры и эволюционных перестроек в промоторах.

2.6.2. Выявление взаимосвязей в 5'-фланкирующих районах генов гормона роста.

2.6.3. Анализ полных геномов

2.6.4. Сравнительный анализ последовательностей дисков политенных хромосом

Выводы по второй главе

Глава 3. Анализ серий в агрегированном алфавите

3.1. Агрегирование алфавита

3.2. Серийные характеристики

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

3.3.1. Выявление аномалий в агрегированных ДНК-последовательностях

3.3.2. Анализ точечных мутаций

3.3.3. Выявление регулярностей в локализации аминокислот.

3.3.4. Кластеризуемость элементов в ДНК-последовательностях: совместный учет разных агрегирований

3.4. Сравнительный анализ серийных характеристик

3.5. Анализ взаимного расположения серий

Выводы по третьей главе

Глава 4. Использование позиционной информации для выделения структурных единиц и оценивания их значимости

4.1. Статистики для выявления неравномерностей позиционного распределения

4.2. Схема анализа позиционного распределения заданной цепочки по длине текста

4.3. Описание экспериментов. Интерпретация результатов.

4.3.1. Исходные данные

4.3.2. Описание экспериментов

4.3.3. Интерпретация результатов

4.4. Примеры позиционных аномалий. Их взаимосвязь.

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

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

Выводы по четвертой главе

Глава 5. Представление структурных единиц в виде образцов и алгоритмы их поиска в тексте

5.1. Постановка задачи поиска по частично-специфицированному запросу

5.2. Алгоритмы поиска по групповому частично специфицированному запросу

5.2.1. Поиск группы константных образцов с помощью алгоритма Ахо-Корасик

5.2.2. Поиск по групповому частично специфицированному запросу: Алгоритм

5.2.3. Поиск по групповому частично специфицированному запросу: Алгоритм

5.2.4. Апробация алгоритмов 1 и

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

5.3.1. Поиск образца, содержащего неопределенные позиции

5.3.2. Алгоритм 3: Поиск по группе образцов с элементами типа X

5.3.3. Алгоритм 4: Поиск по группе образцов с элементами типа X

5.3.4. Алгоритм 5: Поиск по групповому частично Ф специфицированному запросу (общий случай)

5.4. Выявление совпадений, вложений и пересечений среди образцов запроса

5.4.1. Описание алгоритма выявления взаимосвязанных образцов

5.4.2. Апробация алгоритма.

5.5. Поиск образцов, содержащих переменные

5.5.1. Формулировка задачи.

5.5.2. Адаптивный алгоритм поиска образцов с одной переменной в константном окружении.

Выводы по пятой главе

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

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

Следует отметить, что проблема выделения структурных единиц не теряет своей актуальности и при анализе уже структурированных текстов. Речь идет о введении промежуточных уровней иерархии в уже сложившихся иерархических системах. В частности, в естественном языке, где уровни иерархии задаются делением текста на слова, предложения, абзацы и т.д., часто возникает необходимость в рассмотрении промежуточных уровней со структурными единицами типа "устойчивые словосочетания" [13, 7], "коммуникативные фрагменты" [12] или "межфразовые единства" [6, 41].

Универсальных, т.е. пригодных для любой языковой системы алгоритмов выделения структурных единиц не существует. Более того, даже в рамках одной языковой системы часто используются различные алгоритмы, особенно при выявлении единиц разных иерархических уровней. Так, для выделения упоминавшихся выше устойчивых словосочетаний обычно используется частотная и грамматическая информация, тогда как для выделения "межфразовых единств" — набор специальных связующих слов — "коннекторов" ("указанный", "такой", "наконец", "в частности" и т.п. [6]). Аналогично, для выявления экзон-интронной структуры эукариотических генов используются такие признаки как наличие достаточно длинной открытой (т.е. не содержащей терминальных кодонов) рамки считывания в последовательности выделяемых экзонов, существование характерных биграмм на стыках "экзон-интрон" и "интрон-экзон", скрытые проявления триплетной структуры генетического кода в экзонах и т.п., тогда как для выявления регуляторных элементов, например, промоторов, существенны совсем другие параметры. В силу указанных обстоятельств существующие не слишком многочисленные алгоритмы выделения структурных единиц в символьных последовательностях носят "предметно- (или объектно-) ориентированный" характер (см. обзор литературы в главе 1).

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

Для достижения указанных целей используются:

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

Предлагаемое в данной работе обобщение меры Лемпеля и Зива состоит в максимально возможном расширении спектра допустимых операций копирования, число которых в общем случае составляет 2|Е|!, где |Е| — размер алфавита. Расширение спектра операций копирования эквивалентно более полному учету различных классов повторов, являющихся основными структурообразующими элементами текста. Под повтором в общем случае понимается пара фрагментов текста, совпадающих друг с другом с точностью до переименования элементов алфавита и (возможно) изменения направления считывания элементов в одном фрагменте на противоположное. Примером такого рода повторов являются комплементарные палиндромы в ДНК-последовательностях, секвентные переносы в нотных текстах, слова естественного языка, отличающиеся переименованием букв (например, "парапет" и "реферат") и т.п.;

2) различные способы агрегирования алфавита с последующим анализом серийных характеристик в тексте, представленном элементами алфавита меньшего размера (глава 3). Агрегирование — это объединение элементов алфавита в непересекающиеся группы по какому-либо функциональному признаку (разбиение множества букв на гласные и согласные, множества слов — по частеречному признаку, алфавита нуклеотидов — на пурины и пири-мидины и т.п.). Поскольку агрегирование приводит к резкому сокращению размера алфавита, облегчается выявление закономерностей, замаскированных в исходном (большом) алфавите. Эти закономерности проявляют себя в виде аномально длинных, аномально частых или аномально редких серий (цепочек из однотипных элементов, ограниченных по краям элементами другого типа). Аномально длинные серии связаны с кластеризацией отдельных элементов алфавита в локальных участках последовательности. Специфика предлагаемой методики анализа серий и элемент новизны состоит в использовании серийных характеристик, учитывающих(результаты нескольких независимых агрегирований одновременно. Примером может служить суммарное по всем агрегированиям число серий с длиной выше пороговой. Значительный практический интерес представляет также методика выявления устойчиво повторяющихся комбинаций серий из разных агрегирований. Многие функционально-значимые конструкции в генетических текстах, такие как шпилечные структуры, ТАТА-воксы в промоторах и др., часто представляют собой конкатенации серий из разных агрегирований;

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

4) методы поиска структурных единиц, представимых в виде образцов (глава 5). Образец — это цепочка, составленная из константных и переменных символов. Множество слов, получаемых подстановкой произвольных "константных цепочек" вместо переменных символов, называют языком, порождаемым заданным образцом. Нахождение в тексте всех слов конкретного языка представляет собой в общем случае трудноразрешимую проблему [68]. В работе рассмотрены два важных частных случая общей проблемы: групповой поиск частично-специфицированных образцов и поиск образцов с одной переменной в константном окружении (число вхождений переменной - не менее двух, на длину подстановки ограничений не накладывается). Первая задача является обобщением известной проблемы группового поиска точно определенных образцов [64] на случай, когда элементы образца заданы с точностью до принадлежности к определенным подмножествам исходного алфавита. Для решения этой проблемы предложены новые эффективные алгоритмы, основанные на использовании детерминированных и недетерминированных конечных автоматов. Для решения второй проблемы (поиск образцов с одной переменной в константном окружении) также предложен новый алгоритм, адаптивно настраивающийся на параметры текста и образца, трудоемкость которого "в среднем" существенно меньше, чем у известных аналогов.

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

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

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

Выводы по пятой главе

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

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

3. Для групповых запросов со значительным количеством элементов типа "don't care" (несущественная для поиска позиция) предложен алгоритм поиска, основанный на построении недетерминированного конечного автомата (элемент новизны). Диапазон применимости этого алгоритма шире, чем двух предыдущих, при незначительном увеличении памяти и времени поиска.

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

5. Разработан адаптивный алгоритм отыскания в тексте образцов с одной переменной в константном окружении. Алгоритм имеет трудоемкость 0(N log N) в среднем (N — длина текста), что является существенным продвижением по сравнению с известным аналогом (0(N2 log N)).

6. Алгоритм поиска по групповому частично специфицированному запросу реализован в рамках поисковой системы PROF-PAT 1.0, созданной в НПО

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

Заключение

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

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

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

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

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

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

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

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

Методика использовалась для анализа структуры полных вирусных и бактериальных геномов, выявления блочных перестроек в промоторных областях различных генов, вычисления мер сходства между последовательностями дисков политенных хромосом хирономид и в ряде других приложений. Совместно с Институтом Цитологии и Генетики СО РАН реализован многоцелевой программный продукт для оценивания сложности, доступный по адресу http://wwwmgs.bionet.nsc.ru/mgs/programs/lzcomposer/.

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

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

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

Анализ серийных характеристик в агрегированных ДНК- и РНК-последовательностях показал, что: кластеризуемость элементов в них носит фундаментальный характер, т.е. проявляется при разных агрегированиях и у разных семейств последовательностей. Наиболее типичное проявление кластеризуемости связано с избытком длинных серий из пуринов (Д = {А, С}) и пиримидинов

У = {С,Т}); аномально длинные серии часто имеют дупликативный характер, расположены на границах крупных структурных единиц и могут дублировать некоторые регуляторные сигналы (например, сигнал окончания трансляции гена); существуют устойчивые комбинации серий от разных агрегирований (примером может служить "контрастное" оформление ТАТА-бокса в эукари-отических промоторах).

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

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

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

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

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

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

Предложен алгоритм отыскания в тексте образцов с одной переменной в константном окружении, адаптивно настраивающийся на параметры текста и образца. Трудоемкость алгоритма в среднем составляет 0(NlnN), где N — длина текста, что в большинстве случаев обеспечивает значительный выигрыш по сравнению с известными (неадаптивными) алгоритмами. Алгоритм может быть использован для поиска "аспектных" словосочетаний в научно-технических текстах, а также для обнаружения "скрытого" цитирования.

1. Арефьев С.С., Шебалин Н.В. Оценка уровня скученности (кластеризации) землетрясений Кавказа // ДАН СССР . 1988. - Т. 298, №6. -С. 1349-1352.

2. Ахо А., Хопркофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов, М., Мир, 1979.

3. Бахмутова И.В., Гусев В.Д., Титкова Т.Н. L-граммные азбуки для дешифровки знаменных песнопений // Сибирский журнал прикладной и индустриальной математики. Новосибирск, 1998. -Т.1, №2. - С. 51-66.

4. Бахмутова И.В., Гусев В.Д., Титкова Т.Н. Иерархия повторов в мелодиях песен (взаимосвязь "текст мелодия") // Анализ данных исигналов, Новосибирск, 1998. Вып. 163: Вычислительные системы. -С. 143-171.

5. Берзон В.Е., Брайловский А.Б. Классификация коннекторов и диалоговые системы автоматического реферирования // НТИ, сер.2: Информационные процессы и системы. № 11. 1979. - С. 19-23.

6. Большаков И. А .Какие словосочетания следует хранить в словарях? / "Компьютерная ленгвистика и интеллектуальные технологии". Труды междунар. семинара Диалог-2002. - Т. 2.- М., Наука, 2002 . - С. 61-69

7. Бондаренко Г.В. К изучению текста как иерархической структуры суперсинтаксических единиц // НТИ, сер.2., 1975, №8.

8. Бондаренко Г.В. Распределение повторов в связном тексте как основа для обнаружения суперсинтаксических единиц // НТИ, сер.2., 1975, №12.

9. Василевская В.В., Гусев JI.B., Хохлов А.Р. Белковые последовательности как "литературный текст" // ДАН, 2004, Т. 397, №4, С. 542-545.

10. Винцюк Т.К. Анализ, распознавание и интерпретация речевых сигналов, Киев, Наукова Думка, 1987, С. 53-57 (3.2. Оптимальная сегментация реализаций)

11. Гаспаров Б.М. Язык, память, образ. М., 1996. - С.118-119

12. Гиндин С.С., Леонтьева H.H. Задачи и общее строение системы автоматического индексирования с использованием информационного языка словосочетаний // Вопросы информационной теории и практики. -М., ВИНИТИ. Вып. 27, 1975. - С. 88-93.

13. Гиндин С.И. Методы автоматического фрагментирования текста, опирающиеся на характеристики внутреннего состава фрагментов // Семиотика и информатика. 1977. - Вып. 9. - М., ВИНИТИ. - С. 35-82.

14. Гиндин С.И. Позиционные методы автоматического фрагментирования текста, их теоретико-текстовые и психо- лингвистические предпосылки // Семиотика и информатика. 1978. - Вып. 10. - М., ВИНИТИ. - С. 32-73.

15. Григорьева А.Н. Меры сложности слов на основе предиката вхождения и редакционного расстояния // Зап. научн. семинаров ЛОМИ АН СССР. 1981. - Т.105. - С. 18-24.

16. Гусев В.Д. Характеристики символьных последовательностей // Машинные методы обнаружения закономерностей. Новосибирск, 1981. -Вып. 88: Вычислительные системы. - С. 112-123.

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

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

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

20. Гусев В.Д. Сложностные профили символьных последовательностей // Методы обработки символьных последовательностей и сигналов. -Новосибирск, 1989. Вып. 132: Вычислительные системы. - С. 35-63.

21. Гусев В.Д., Косарев Ю.Г., Титкова Т.Н. О задаче поиска повторяющихся отрезков текста // Ассоциативное кодирование. Новосибирск, 1975. - Вып. 62: Вычислительные системы. - С. 11-33.

22. Гусев В.Д., Куличков В.А., Титкова Т.Н.Анализ генетических текстов. I. l-грамные характеристики // Эмпирическое предсказание и распознавание образов. Новосибирск, 1980. - Вып. 83: Вычислительные системы. - С. 11-33.

23. Гусев В.Д., Куличков В.А., Никулин А.Е. Алгоритм поиска несовершенных повторов в генетических текстах // Анализ символьных последовательностей. Новосибирск, 1985. - Вып. 113: Вычислительные системы. - С. 107-122.

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

25. Гусев В.Д., Титкова Т.Н. Хеширование символьных цепочек в режиме скользящего окна // Вычислительные системы, вып. 150. Новосибирск, 1994. - С. 94-106.

26. Добровольский Д.О. Корпус параллельных текстов и литературный перевод // НТИ, сер.2, Информационные процессы и системы. №10, 2003. - С. 13-18.

27. Зарипов Р.Х. Машинный поиск вариантов при моделировании творческого процесса. М., Наука, ФМ, 1983, 232 стр.

28. Зубков A.M., Михайлов В.Г. Предельные распределения случайных величин, связанных с длинными повторениями в последовательностинезависимых испытаний // Теория вероятностей и ее применения, 1974. Т. XIX, Ш. - С. 173-181.

29. Касьянов В.М. Лекции по теории формальных языков, автоматов и сложности вычислений. Учеб. пособ., НГУ, Новосибирск, 1995.

30. М. Кендэл Ранговые корреляции, М., Статистика, 1975.

31. Клигене М., Тельскинс Л. Методы обнаружения моментов изменения свойств случайных процессов // Автоматика и телемеханика, №10,1983.

32. Клиометрика. М., 1982. Вып. 1.

33. Колмогоров А.Н. Три подхода к определению понятия <количество информации> / / Проблемы передачи информации. Т.1, вып. 1, 1965. - С. 3-11.

34. Компьютерный анализ генетических текстов. Под ред. М.Д.Франк-Каменецкого. М., Наука, 1990. - С.81-112.

35. Кондратович И.В. Опыт сравнения византийских и древнерусских певческих памятников XII в. // Проблемы дешифровки древнерусских нотаций, Сб. научных трудов, Л-д, изд-во ЛОЛГК, 1987, С. 5-27.

36. Д.Кнут Искусство программирования для ЭВМ, Т.2-3, М., Мир, 1977.

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

38. Лингвистические проблемы автоматизации редакционно издательских процессов, под редакцией Перебейнос и Феллер, Киев, Наукова думка, 1986. - С. 7-8.

39. Мирам Г.Э. Машинная интерпретация текста// НТИ, сер.2: Информационные процессы и системы. № 9, 1988. - С. 19-23.

40. Михайлов М.Н. Стыковка параллельных текстов в автоматическом режиме: иллюзии и перспективы // НТИ, сер. 2, Информационные процессы и системы. №10, 2003. - С. 18-26.

41. Обнаружение изменеия свойств сигналов и динамических систем. Под ред. М. Бассвиль, А. Банвениста. - М., Мир., 1989 - 278 стр.

42. Пащенко H.A., Кнорина JI.B., Молчанова Т.В. и др. Проблемы автоматизации индексирования и реферирования // Итоги науки и техники. Информатика. Т.7, 1983. - С. 7-164.

43. Рылова Т.Н. Некоторые формальные критерии выявления семантических связей между предложениями текста // Семантические проблемы автоматизации информационного поиска. Киев, Наукова Думка, 1971, С. 73-84.

44. Садовский М.Г. Информационно-статистический анализ нуклеотид-ных последовательностей // Диссертация на соиск. уч. степ, д.ф.-м.н. по специальности 03.00.02 Биофизика., Красноярск, 2004г.

45. Саломатина Н.В. Количественные исследования морфемной структуры слов русского языка (на базе электронного словаря Д.Уорта) // Обнаружение эмпирических закономерностей, Новосибирск, 1999, Вып. 166: Вычислительные системы, С. 104-118.

46. Севбо И.П. Структура связного текста и автоматизация реферирования, М., Наука, 1969.

47. Серебрякова JI.A. О возможности смысловой компрессии документов на основе извлечения предложений с ядерными конструкциями // НТИ, сер.2, №, 1974.

48. Скороходько Э.Ф. Семантические связи в лексике и текстах . // Вопросы информационной теории и практики. М., ВИНИТИ, 1974, С. 6-116.

49. Скороходько Э.Ф. Семантические сети и автоматическая обработка текста . Киев, Наукова Думка, 1983, 218стр.

50. Слисенко А.О. Нахождение в реальное время всех периодичностей в слове // ДАН СССР. 1980. - Т. 251, №1. - С. 48-51.

51. Сприжицкий Ю.А. Статистический анализ и распознавание функциональных участков генома: Дисс. канд.физ.-мат. наук: 03.00.02, М., 1987, 145 с.

52. Сухотин Б.В. Оптимизационные методы исследования языка, М., Наука, 1976.

53. Трифонов Э.Н. Генетическое содержание последовательности ДНК определяется суперпозицией многих кодов // Молекулярная биология. 1997. - Т. 31. №4. - С. 759-767.

54. Феллер В. Введение в теорию вероятностей и ее приложения, М., Мир, 1964, 498 с.

55. Фрид А.Э. О комбинаторной сложности итеративно порождаемых символьных последовательностей // Дискретный анализ и исследование операций, Серия 1, Том 4, №1. 1997. - С. 53-59

56. Хьетсо Г., Густавсон С., Бекман Б., Гил С. Кто написал "Тихий Дон"?, М., Книга, 1989.

57. Чанышев О.Г. Ассоциативная модель естественноязыкового текста // Вестник Омского университета, №4, 1997, С. 17-20.

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

59. Шеннон К. Предсказание и энтропия печатного английского текста, Работы по теории информации и кибернетике, М., 1963, 669-686.

60. Abarbanel R.M., Wieneke P.R. et al. Rapid searches for complex patterns in biological molecules // Nucleic Acids Research. 1984. - Vol. 12, №1. -P. 263-280.

61. Allison L., Edgoose Т., Dix T.I. Compression of Strings with Approximate Repeats // Intelligent Systems in Molecular Biology (ISMB'98).- Montreal, 28 June-1 July 1998.

62. Aho A.V., Corasick M.J., Efficient string matching: an aid to bibliographic search, // Communications of the ACM. 1975. - Vol. 18, №6. - C. 333340.

63. Alba M. Mar, Laskowski R.A. and Hancock J.M. Detecting cryptically simple protein sequences using the SIMPLE algorithm // Bioinformatics. 2002. - Vol. 5. - P. 672- 678

64. Altschul S.F., Gish W., Miller W., Myers E.W., Lipman D.J. Basic local alignment search tool // J. Mol. Biol. 1990. - Vol. 215. - P. 403-410.

65. Altschul S.F., Madden T.L., Schaffer A.A., Zhang J., Zhang Z., Miller W., Lipman D.J. Gapped BLAST and PSI-BLAST: a new generation of protein database programs // Nucleic Acids Res. 1997. - Vol. 25. - P. 3389-3402.

66. Angluin D. Finding patterns common to a set of string // J. Comput. Syst. Sci. 1980. - Vol. 21. - P. 46-62.

67. Angluin D. Learning Regular Sets From Queries and Counterexamples // Information and Computation. 1987. - Vol. 75. - P. 87-106.

68. Aol J., Yamamoto Y., Shimada Y. A method for improving string pattern matching machines // IEEE Trans, on Software Engineering. 1984. - Vol. SE-10, №. - P. 116-120.

69. Baeza-Yates R., Gonnet G.H. A New Approach to Text Searching // Communications of the ACM. 1992. - Vol. 35, №10. - P. 74-82.

70. Baker B.S. A theory of parameterized pattern matching: algorithms and applications // Proc. 25th Annual ACM Symposium on the Theory of Computation, 1993. P. 71-80.

71. Baker B.S. Parameterized pattern matching: algorithms and applications // Journal of computer and system sciences. 1996. - Vol. 52. - P. 28-42.

72. Blaisdell B.E. A prelevant persistent global nonrandomness that distinguishies coding and non-coding eucaryotic nuclear DNA sequences // J.Mol.Evol., 1983, Vol.19, №2. P. 122-133.

73. Blumer A., Blumer J., Ehrenfeucht A., Hausler D., McConnell R. Linear size finite automata for the set of all subwords of a word an outline of results 11 Bull. Europ. Assoc. Theoret. Comput. Sci. 1983. - Vol. 21. - P.12-20.

74. Bolshoy A., Shapiro K., Trifonov E.N., Ioshikhes I. Enhancement of the nucleosomal pattern in sequences of lower complexity // Nucl. Acids Res, 1997. Vol. 25. - P. 3248-3254.

75. Boyer R.S., Moore J.S. A fast string searching algorithm // Communications of the ACM. 1977. - Vol. 20. - P. 767-772.

76. Cambouropoulos E., Crochemore M., Iliopoulos C.S., Mouchard L., Pinzon Y.J. Algorithms for Computing Approximate Repetitions in Musical Sequences 11 Proceedings of the tenth Australian Workshop on Combinatorial Algorithhms, AWOCA'99, P. 129-144.

77. Chen Xin, Francia Brent, Li Ming, McKinnon Brian, Seker Amit Shared Information and program plagiarism detection // IEEE Transactions on Infotmation Theory, 2004, V. 50, №7, P. 1545-1551.

78. Churchill G.A. Stochastic models for heterogeneous DNA sequences // Bull. Math. Biol., V.41, 1989, P.164-171.

79. Churchill G.A. Hidde Markov chains and the analysis of genome structure // Computers Chem., V.16, №2, 1992, P.107-115.

80. Cornish-Bowden A. Nomenclature for incompletely spesified bases in nucleic acid sequences: recomendation // NAR, 1985, Vol.13, №9. P. 3021-3030.

81. Crawford T, Iliopoulos C.S. String-Matching Techniques for Musical Similarity and Melodic Recognition // Melodic Similarity. Concepts, Procedures, and Applications. Computing in Musicology 11, 1998, P. 73100.

82. Crochemore M., Rytter W. Text Algorithms, Oxford University Press, New York, Oxford, 1994.

83. Crochemore M., Verin R. Zones of low entropy in genomic sequences // Computers and Chemistry. 1999. - Vol. 23. - P. 275-282.

84. Dick Grune, Matty Huntjens Detecting copied submissions in computer science workshops // Informatie, 31, 11, 1989, 864-867 (in Dutch) (http://www.cs.vu.nl/ dick/sim.html)

85. Ebeling W., Jimenes-Montario M.A. On Grammars, Complexity, and Information Measures of Biological Macromolecules // Math. Biosci. -1980. №52. - P. 53-71.

86. Gabrielian A.E., Bolshoy A. Sequence complexity and DNA curvature // Comput. Chem., 1999. Vol. 23. - P. 263-274.

87. Gelfand M.S., Kozhukhin G.S., Pevzner P.A. (1992) Comput. Appl. Biosci, V.8, 129

88. Glaz J. Approximations and bounds for the distribution of the scan statistic // Journal of the American Statistical Association, 1989. Vol. 84, №406. - P. 560-566.

89. Goad W.B., Kanehisa M.I. // Nucl. Acids. Res. 1982. - Vol. 10. - P. 247-263.

90. Golomb S.W. Shift Register Sequences. San Francisco: Holden-Day, 1967

91. Grantham R. Nucleic acid sequence semilarities: "Poly(A) tendency" // Febs Letters, 1980. Vol. 121, №2. - P. 193-199.

92. Gusev V.D., Kulichkov V.A., Chupakhina O.M. The Lempel-Ziv complexity and local structure analysis of genomes // BioSystems, Elsevier Scientific Publishers Ireland, Vol. 30, 1993. P. 183-200.

93. Hancock J.M., Armstrong J.S. SIMPLE34-' an improved and enhanced implementation for VAX and Sun computers of the SIMPLE algorithm for analysis of clustered repetitive motifs in nucleotide sequences // Comput. Appl. Biosci., 1994. Vol. 10. - P. 67-70

94. Handbook of Formal Languages, G. Rosenberg, A. Salomaa (Eds), Vol. 1, 1996. Ch.4.

95. Hines W.G.S., Hines R.J.O'Hara. The Eberhardt statistic and the detection of nonrandomness of spatial point distributions // Biometrica, 1979. Vol. 66, m. - P. 73-79.

96. Karlin S., Brendel V. Charge configurations in viral proteins // Proc. Natl. Acad. Sci. USA, 1988, V. 85, P. 9396-9400.

97. Karlin S., Ost F., Blaisdell B.E. Patterns in DNA and aminoacid sequences and their statistical significance // In: Mathematical methods for DNA sequences. Ed. by Waterman M.S. - CRC Press, Inc., 1989, P. 134-157.

98. Karlin S., Machen C. Some statistical problems in the assessment of inhomogeneities of DNA sequence data // Journal of the American Statistical Association, 1991. Vol. 86, №413. - P. 27-35.

99. Kel O.V., Romaschenko A.G., Kel A.E., Wingender E. and Kolchanov N.A. (1995) A compilation of composite regulatory elements affecting gene transcription in vertebrates // Nucleic Acids Res. 23, 4097-4103.

100. Krawczak M., Chuzhanova N.A. and Cooper D.N. (1999) Evolution of the proximal promoter region of the mammalian growth hormone gene. Gene 237, 143-151.

101. Knuth D.E., Morris J.H., Pratt V.R. Fast pattern matching in strings // TR CS-74-440, Stanford University, Stanford, California, 1974.

102. Knuth D.E., Morris J.H., Pratt V.R. Fast pattern matching in strings // SIAM J. Computing, 1977. Vol.2 №6. - P. 323-350.

103. Sudhir Kumar, Koichiro Tamura, Ingrid B. Jakobsen, and Masatoshi Nei (2001) MEGA2: Molecular Evolutionary Genetics Analysis software, Arizona State University, Tempe, Arizona, USA.

104. Lempel A., Ziv J. On the complexity of finite sequences // IEEE Trans. Inform. Theory., 1976. Vol. IT-22, №. - P. 75-81.

105. Li W. em The complexity of DNA: the measure of compositional heterogeneity in DNA sequences and measures of complexity, Complexity, V.3, 1997, P. 33-37.

106. Lin J. Divergence measure based on the Shannon entropy, IEEE Transactions on Information theory, V. 37, 1991, P. 145-151.

107. Luhn H.P. The automatic creation of literature abstacts // IBM Journal of Research and Development, V. 2, №2, 1958, P. 159-165

108. Mongeau M., Sankoff D. Comparison of musical sequences // Computers and Humanities, 1990, V.24, P. 161-175.

109. Martinez H.M. An efficient method for finding repeats in molecular sequences // Nucleic Acids Research, 1983. Vol. 11. - P. 4629-4634.

110. McCreight E.M. A space-economical suffix tree construction algorithm // J.ACM, 1976. Vol. 23 №2. - P. 262-272.

111. Melodic Similarity. Concepts, Procedures and Applications // Computing in Musicology 11. Ed. by Walter B. Hewlett and Eleanor Selfridge-Field. The MIT Press, Cambridge, Massachusets, London, England, 1998, P. 1-244.

112. Naus J.I. The distribution of the size of the maximum cluster of points on a line // J. Amer. Statist. Assoc., 1965. Vol. 61, 310. - P. 532-538.

113. Naus J.I. A power comparison of two tests of nonrandom clustering // Technometrics, 1966. №8. - P. 493-517.

114. Needleman S.B., Wunsch C.D. A general method applicable to the search for the similarities in the amino-acid sequence of two proteins //J. Mol. Biol., 1970 Vol. 48. - P. 443-453.

115. Neraud J. Algorithms for detecting morphic images of a word // Information and Computation, 1995. Vol. 120. - P. 126-148.

116. Nevill-Manning C.G., Witten I. H. Identifying Hierarchical Structure in Sequences: A linear-time algorithm // Journal of Artificial Intelligence Research, 1997. Vol. 7. - P. 67-82

117. Nikolaou C., Almirantis Y. A Study of the middle-scale nucleotide clustering in DNA sequences of various origin and functionality, by means of method based on modified standard deviation // J. Ther. Biol., 2002. Vol. 217. -P. 479-492.

118. Nussinov R. Strong doublet preferences in nucleotide sequences and DNA geometry // J. Mol. Evol., 1984. Vol.20. - P. 111-119.

119. Nussinov R. The eukatiotic CCA AT and TATA boxes, DNA spacer flexibility and looping // J. Theor. Biol., 1992. Vol.155. - P. 243-270.

120. Oliver J.L., Román-Roldán R., Pérez J., Bernaola-Galván P. SEGMENT: identifying compositiional domains in DNA sequences , Bioinformatics, v. 15 (2), 1999, P. 974-979.

121. OrlovYu.L., Potapov V.N. Estimation of stochastic complexity of genetical texts // Computational technologies (Novosibirsk), 2000. V.5 (Special issue). - P.5-15.

122. Orlov Yu.L., Filippov V.P., Potapov V.N., Kolchanov N.A. Construction of stochastic context trees for genetic texts // (Bioinformation Systems e.V.) In Silico Biology 2, 0022 (2002) (http://www.bioinfo.de/isb/2002/02/0022/)

123. Pertsev I.V. Effective method of data compression on basis of modified arithmetic codes // International congress on computer systems and applied mathematics, St. Petersburg, july 1993, p.237.

124. Pinter Ron Y. Efficient string matching with don't-care patterns // Combinatorial algorithms on words (ed. bu A.Apostolico and Z.Galil), Springer Verlag, 1985, NATO ASI Series, V. F12, P. 11-29.

125. Rissanen J. A universal data compression system // IEEE Trans. Inform. Theory, 1983. V.IT-29, №5. - P.656-664.

126. Rissanen J. Fast universal coding with context models // IEEE Trans. Inform. Theory, 1999. Vol. 45. - P. 1065-1071.

127. Rivest R.L. Partial-match retrieval algorithms // SIAM J. Comput., 1976, V.5, №1, P. 19-50.

128. Saitou N., Nei M. The neighbor- joining method: A new method for reconstructing phylogenetic trees. Mol. Biol. Evol. 1987; 4:406-425.

129. Peter Salamon and Andrzej K. Konopka. A maximum entropy principle for the distribution of local complexity in naturally occurring nucleotide sequences, Computers Chem., 16(2),1992,117-124.

130. Sellers P.H. On the theory and computation of evolutionary distances // SIAM. J. Appl. Math., 1974. Vol. 26, №. - P. 787-793.

131. Sellers P.H. Pattern recognition in genetic sequences by mismatch density // Bull. Math. Biol., 1984. Vol. 46, №4. - P. 501-514.

132. Sharp P.M., Li W-H. The codon adaptation index — a measure of directional synonymous codon usage bias, and its potential applications // Nucleic Acids Research, 1987. Vol. 15, №3. - P. 1281-1295.

133. Smith T.F., Waterman M.S. Identification of common molecular subsequences // J. Mol. Biol., 1981. Vol. 147. - P. 195-197.

134. Suboch G.M., Sprizhitsky Yu.A. Statistical significance of some complex nucleotide combinations: a comparison of DNA models // CABIOS, 1990, Vol.6, №1, P. 43-48.

135. Surguchov, A. (1991) Migration of promoter elements between genes: a role in transcriptional regulation and evolution. Biomed. Sci. 2, 22-28.

136. Tatusova T.A., Madden T.L. BLAST 2 Sequences, a new tool for comparing protein and nucleotide sequences // FEMS Microbiology Letters. 1999. -Vol. 174. - P. 247-250.

137. Tautz D., Trick M., Dover G.A. Cryptic simplicity in DNA is major source of genetic variation // Nature, 1986. Vol. 322. - P. 652-656.

138. Trifonov E.N., Brendel V. GNOMIC : a dictionary of the genetic code // Philadelphia: Balaban Publishing. 1986, 272 p.

139. Trifonov E.N. Making sense of the human genome / In: Structure & Methods (Sarma R.H. & Sarma M.H. Eds.), Adenine Press, 1990. Vol. 1. - P. 69-77.

140. Troyanskaya O.G., Arbell 0., Koren Y., Landau G.M. and Bolshoy A.

141. Sequence Complexity Profiles of Prokaryotic Genomic Sequences: A Fasti

142. Ukkonen E. Constructing suffix trees on-line in linear time in (IFIP'92): 484-492

143. U. Vishkin, Deterministic sampling a new technique for fast pattern matching // SIAM J. Comput., 1991. - Vol. 20, №1. - P. 22-40.

144. Wagner R.A., Fisher M.J. The string-to-string correction problem //J. ACM. 1974. - Vol. 21, №158. - P. 168-173

145. Wallenstein S.R., Naus J.I. Probabilities for a k-th nearest neighbor problem on the line // The Annals of Probability, 1973. Vol. 1, №1. - P. 188-190.

146. H.Wan, J.C.Wootton A global compositional complexity measure for bioligical sequences: AT-rich and CG-rich genomes encode less complex proteins ¡I Computers and Chem., 24, 2000, 71-94.

147. Weiner P., Linear pattern matching algorithms / in Proc. 14th IEEE Annual Symposium on Switching and Automata Theory, New York, 1973. P. 1-11.

148. Weitzman M.P. The evolution of manuscripts traditions 11 J. Royal Statist. Soc. A., V. 150, Part 4, 1987, P. 287-308.

149. Wu S., Manber U. Fast Text Searching Allowing Errors // Communications of the ACM, 1992. Vol. 35, №10. - P. 83-91.

150. Ziv, J., and Lempel, A. 1977. A Universal Algorithm for Sequential Data Compression. IEEE Trans. Inform. Theory 23, 3 (May), 337-343.

151. Ziv J., Lempel A. Compression of Individual Sequences via Variable-Rate Coding 11 IEEE Trans. Inform. Theory., 1978. Vol. IT-24, №5. - P. 530536.

152. Yowe, D.L., Epping, R.J. (1995) Cloning of the barramundi growth hormone-encoding gene: comparative analysis of higher and lower vertebrate GH genes. Gene 162, 255-259.

153. Немытикова JI.А. Методы сравнения символьных последовательностей // Методы обработки символьных последовательностей. Новосибирск, 1989. - вып. 132: Вычислительные системы. - С. 3-34.

154. Гусев В.Д., Немытикова JI.A. Анализ серий в генетических текстах II Анализ временных рядов и символьных последовательностей. Новосибирск, 1991. - вып. 141: Вычислительные системы. - С. 46-76.

155. Немытикова JI.A. Использование серийных характеристик для исследования эффекта кластеризации элементов в ДНК-молекулах // Анализ последовательностей и таблиц данных. Новосибирск, 1994. - вып. 150: Вычислительные системы. - С. 147-163.

156. Бачинский А.Г., Гусев В.Д., Немытикова и др. Новая версия банка образов PROF-PAT 1.0: технология формирования и программа быстрого поиска образов в аминокислотных последовательностях // Молекулярная биология. 1996, Ж 6, С.1409-1417.

157. Гусев В.Д., Немытикова JI.A. Алгоритмы поиска в текстовых базах данных по групповому частично специфицированному запросу // Вычислительные системы, вып. 157. Новосибирск, 1996. - С. 12-39.

158. Немытикова JI.A. Использование недетерминированных конечных автоматов для ускорения поиска в текстовых базах данных // Вычислительные системы, вып.160. Новосибирск, 1997. - С. 188-209.

159. Гусев В.Д., Немытикова JI.A. Сложностные характеристики генетических текстов, Труды IV Всероссийской конф. "Распознавание образов и анализ изображений", Новосибирск, 1998. 4.1, 83-87.

160. Бахмутова И.В., Гусев В.Д., Немытикова JI.A., Титкова Т.Н. Количественные и качественные характеристики варьирования песенных мелодий на микро- и макроуровне // Вычислительные системы, вып. 163.-Новосибирск, 1998. С. 113- 142.

161. Gusev V.D., Nemytikova L.A. Complexity Characteristics of Genetic Texts (Сложностные характеристики генетических текстов) // Pattern Recognition and Image Analysis. 1999. - Vol.9, № 1. - P. 52 - 55.

162. Gusev V.D, Nemytikova L.A., Chuzhanova N.A. On the complexity measures of genetic sequences (Меры сложности генетических последовательностей) // Bioinformatics. 1999. - Vol.15, № 12. - P. 994-999.

163. Гусев В.Д., Немытикова JI.А., Чужанова H.A. Быстрый метод выявления взаимосвязей в подборках функционально и/или эволюционно близких биологических текстов // Молекулярная биология. 2001. - Т. 35, № 6. - С.1015-1022

164. Гусев В.Д., Немытикова J1.A. Учет проявлений повторности, симметрии и изоморфизма в символьных последовательностях // Методы обнаружения эмпирических закономерностей. Новосибирск, 2001. - вып. 167: Вычислительные системы. - С. 11-33.

165. Chuzhanova N.A., Krawczak M., Thomas N., Nemytikova L.A., Gusev V.D., Cooper D.N. The evolution of the vertebrate beta-globin gene promoter (Эволюция промоторов /?-глобиновых генов позвоночных) // Evolution. 2002. - Vol. 56, № 2. - P. 224-232.

166. Гусев В.Д., Немытикова J1.A., Саломатина Н.В. Выявление аномалий в распределении слов или связных цепочек символов по длине текста // Вычислительные системы, вып. 171. Новосибирск, 2002. - С. 51-74.

167. OrlovYu.L., Gusev V.D., Miroshnichenko L.A. LZcomposer: decomposition of genomic sequences by repeat fragments (LZcomposer: разложение геномных последовательностей на повторяющиеся фрагменты) // Biophisics, Vol.48, Suppl.1,2003, S7-S16.

168. Гундерина Л.И., Кикнадзе И.И., Истомина А.Г., Гусев В.Д., Мирошниченко Л.А. Дивергенция последовательностей дисков политенных хромосом как отражение эволюционных преобразований линейной структуры генома // Генетика, 2005, Т. 41, №2, С. 187-195.