Содержание к диссертации
Введение
Глава I. Обзор методов выявления структурных единиц в символьных последовательностях 14
1.1. Элементарные структурообразующие единицы текста 14
1.2. Методы сегментирования символьных последовательностей 17
1.2.1. Морфологический анализ текста без пробелов 17
1.2.2. Сложностные разложения символьных последовательностей .19
1.2.3. Иерархическое представление последовательностей с помощью порождающих грамматик 22
1.2.4. Выявление моментов изменения свойств последовательности 25
1.3. Методы фрагментирования символьных последовательностей 28
1.3.1. Статистические (частотные) методы фрагментирования 28
1.3.2. Позиционные методы фрагментирования 30
1.3.3. Суперсинтаксические методы фрагментирования 31
1.3.4. Методы фрагментирования, основанные на сопоставлении эволюционно и/или функционально близких текстов 32
1.3.5. Поиск локальных аномалий в режиме скользящего окна 33
1.3.6. Агрегирование алфавита как способ выявления локальных структурных закономерностей 36
1.3.7. Задание структурных элементов в виде образцов 37
Выводы по первой главе 41
Глава 2. Методы выделения структурных единиц на основе сложностных разложений текста 43
2.1. Различные модификации меры сложности Лемпеля-Зива 43
2.1.1. Понятие /-повтора и его использование в сложностных разложениях 43
2.1.2. Векторная мера сложности 46
2.1.3. Мера сложности с пошаговой оптимизацией по ограниченному набору подстановок 47
2.1.4. Мера сложности с пошаговой оптимизацией по полному набору подстановок (мера Cf) 51
2.2. Алгоритмы вычисления сложности символьной последовательности 52
2.2.1. Алгоритм вычисления сложности при фиксированной подстановке 53
2.2.2. Алгоритм вычисления меры С/ 59
2.3. Сложностные профили символьных последовательностей 62
2.4. Случай нескольких последовательностей 70
2.5. Некоторые свойства сложностных разложений 74
2.6. Примеры применения сложностного анализа к биологическим текстам 78
2.6.1. Выявление блочной структуры и эволюционных перестроек в промоторах 78
2.6.2. Выявление взаимосвязей в 5'-фланкирующих районах генов гормона роста 80
2.6.3. Анализ полных геномов 84
2.6.4. Сравнительный анализ последовательностей дисков политенных хромосом 89
Выводы по второй главе 92
Глава 3. Анализ серий в агрегированном алфавите 95
3.1. Агрегирование алфавита 95
3.2. Серийные характеристики 98
3.3. Использование серийных характеристик для анализа генетических текстов 100
3.3.1. Выявление аномалий в агрегированных ДНК-последовательностях 101
3.3.2. Анализ точечных мутаций 106
3.3.3. Выявление регулярностей в локализации аминокислот 108
3.3.4. Кластеризуемость элементов в ДНК-последовательностях: совместный учет разных агрегирований 111
3.4. Сравнительный анализ серийных характеристик 113
3.5. Анализ взаимного расположения серий 116
Выводы по третьей главе 118
Глава 4. Использование позиционной информации для выделения структурных единиц и оценивания их значимости 121
4.1. Статистики для выявления неравномерностей позиционного распределения 122
4.2. Схема анализа позиционного распределения заданной цепочки по длине текста 124
4.3. Описание экспериментов. Интерпретация результатов 128
4.3.1. Исходные данные 128
4.3.2. Описание экспериментов 128
4.3.3. Интерпретация результатов 130
4.4. Примеры позиционных аномалий. Их взаимосвязь 133
4.5. Пример практического использования позиционных аномалий 139
4.6. Обсуждение результатов 141
Выводы по четвертой главе 146
Глава 5. Представление структурных единиц в виде образцов и алгоритмы их поиска в тексте 148
5.1. Постановка задачи поиска по частично-специфицированному запросу 149
5.2. Алгоритмы поиска по групповому частично специфицированному запросу 151
5.2.1. Поиск группы константных образцов с помощью алгоритма Ахо~Корасик 151
5.2.2. Поиск по групповому частично специфицированному запросу: Алгоритм 1 154
5.2.3. Поиск по групповому частично специфицированному запросу: Алгоритм 2 159
5.2.4. Апробация алгоритмов 1 и 2 161
5.3. Использование недетерминированных конечных автоматов для поиска по групповому запросу 162
5.3.1. Поиск образца, содержащего неопределенные позиции 162
5.3.2. Алгоритм 3: Поиск по группе образцов с элементами типа X 166
5.3.3. Алгоритм 4: Поиск по группе образцов с элементами типа X 170
5.3.4. Алгоритм 5: Поиск по групповому частично специфицированному запросу (общий случай) 175
5.4. Выявление совпадений, вложений и пересечений среди образцов запроса 180
5.4.1. Описание алгоритма выявления взаимосвязанных образцов 182
5.4.2. Апробация алгоритма 187
5.5, Поиск образцов, содержащих переменные 188
5.5.1. Формулировка задачи 188
5.5.2. Адаптивный алгоритм поиска образцов с одной переменной в константном окружении 190
Выводы по пятой главе 193
Заключение 196
Список использованных источников
- Морфологический анализ текста без пробелов
- Мера сложности с пошаговой оптимизацией по ограниченному набору подстановок
- Использование серийных характеристик для анализа генетических текстов
- Описание экспериментов. Интерпретация результатов
Введение к работе
Объектом исследования в данной работе являются возникающие в различных предметных областях символьные последовательности (тексты), составленные из элементов конечного алфавита. Примером могут служить тексты на естественном языке, ДНК- и аминокислотные последовательности, нотные записи, знаменные песнопения, тексты программ, телеметрические данные, обычно представимые в виде двоичных последовательностей и т.п. Как видно из приведенного перечня, многие классы последовательностей являются неструктурированными, т.е. в них не выделены явным образом элементарные и производные от них структурно-семантические единицы, аналогичные, к примеру, словам, предложениям, абзацам в текстах естественного языка.
Все большую актуальность в связи с этим приобретает задача формального выделения структурных единиц в символьных последовательностях различной языковой природы. Часто ей сопутствует и задача ранжирования выделенных единиц по степени информативности. Иерархическая сегментация последовательностей на более мелкие части, выявление взаимосвязей между отдельными частями лежит в основе анализа длинных и плохо изученных текстов, примером которых являются полные геномы различных организмов. Используемые для решения этих задач подходы носят дешифро-вочный характер.
Следует отметить, что проблема выделения структурных единиц не теряет своей актуальности и при анализе уже структурированных текстов. Речь идет о введении промежуточных уровней иерархии в уже сложившихся иерархических системах. В частности, в естественном языке, где уровни иерархии задаются делением текста на слова, предложения, абзацы и т.д., часто возникает необходимость в рассмотрении промежуточных уровней со структурны- ми единицами типа "устойчивые словосочетания" [13, 7], "коммуникативные фрагменты" [12] или "межфразовые единства" [6, 41].
Универсальных, т.е. пригодных для любой языковой системы алгоритмов выделения структурных единиц не существует. Более того, даже в рамках одной языковой системы часто используются различные алгоритмы, особенно при выявлении единиц разных иерархических уровней. Так, для выделения упоминавшихся выше устойчивых словосочетаний обычно используется частотная и грамматическая информация, тогда как для выделения "межфразовых единств" — набор специальных связующих слов — "коннекторов" ("указанный", "такой", "наконец", "в частности" и т.п. [6]). Аналогично, для выявления экзон-интронной структуры эукариотических генов используются такие признаки как наличие достаточно длинной открытой (т.е. не содержащей терминальных кодонов) рамки считывания в последовательности выделяемых экзонов, существование характерных биграмм на стыках "экзон-интрон" и "интрон-экзон", скрытые проявления триплетной структуры генетического кода в экзонах и т.п., тогда как для выявления регуляторных элементов, например, промоторов, существенны совсем другие параметры. В силу указанных обстоятельств существующие не слишком многочисленные алгоритмы выделения структурных единиц в символьных последовательностях носят "предметно- (или объектно-) ориентированный" характер (см. обзор литературы в главе 1).
Основной целью данного исследования является разработка новых методов выделения структурных единиц в символьных последовательностях, способных работать при минимальной априорной информации об искомых объектах. В случае, когда уровень априорной информации об этих объектах достаточно высок (например, известно, что они представимы в виде опреде- ленных шаблонов или образцов) сформулированная выше цель трансформируется в задачу ускорения поиска, актуальность которой возрастает по мере усложнения поисковой ситуации (длинные тексты, большие алфавиты, значительное число одновременно предъявляемых запросов, поиск на приближенное соответствие и т.д.).
Для достижения указанных целей используются:
1) методы сложностного анализа текстов (глава 2), позволяющие выявлять взаимосвязи между отдельными фрагментами текста и выделять участки текста с аномально низкой сложностью, функциональная значимость которых подтверждается многочисленными экспериментальными данными. В основе подхода лежит принадлежащая А.Н. Колмогорову [35] идея оценивания сложности конечной символьной последовательности длиной кратчайшей программы, генерирующей эту последовательность с помощью фиксированного вычислительного устройства. Конструктивной реализацией идеи А.Н. Колмогорова является определение сложности конечной последовательности, предложенное Лемпелем и Зивом [108]. В качестве допустимых операций у них фигурируют: а) генерация символа (необходима, как минимум, для введения элементов алфавита); б) копирование любой цепочки символов из предыстории (т.е. из уже синтезированной части текста). Сложность последовательности по Лемпелю и Зиву определяется минимальным числом операций указанного типа, требующихся для ее синтеза.
Предлагаемое в данной работе обобщение меры Лемпеля и Зива состоит в максимально возможном расширении спектра допустимых операций копирования, число которых в общем случае составляет 2|Е|!, где |Е| — размер алфавита. Расширение спектра операций копирования эквивалентно более полному учету различных классов повторов, являющихся основными струк- турообразующими элементами текста. Под повтором в общем случае понимается пара фрагментов текста, совпадающих друг с другом с точностью до переименования элементов алфавита и (возможно) изменения направления считывания элементов в одном фрагменте на противоположное. Примером такого рода повторов являются комплементарные палиндромы в ДНК-последовательностях, секвентные переносы в нотных текстах, слова естественного языка, отличающиеся переименованием букв (например, "парапет" и "реферат") и т.п.;
2) различные способы агрегирования алфавита с последующим анализом серийных характеристик в тексте, представленном элементами алфавита меньшего размера (глава 3). Агрегирование — это объединение элементов алфавита в непересекающиеся группы по какому-либо функциональному признаку (разбиение множества букв на гласные и согласные, множества слов — по частеречному признаку, алфавита нуклеотидов — на пурины и пири-мидины и т.п.). Поскольку агрегирование приводит к резкому сокращению размера алфавита, облегчается выявление закономерностей, замаскированных в исходном (большом) алфавите. Эти закономерности проявляют себя в виде аномально длинных, аномально частых или аномально редких серий (цепочек из однотипных элементов, ограниченных по краям элементами другого типа). Аномально длинные серии связаны с кластеризацией отдельных элементов алфавита в локальных участках последовательности. Специфика предлагаемой методики анализа серий и элемент новизны состоит в использовании серийных характеристик, учитывающих\ результаты нескольких независимых агрегирований одновременно. Примером может служить суммарное по всем агрегированиям число серий с длиной выше пороговой. Значительный практический интерес представляет также методика выявления устойчиво повторяющихся комбинаций серий из разных агрегирований. Многие функционально-значимые конструкции в генетических текстах, такие как шпилечные структуры, ТЛТЛ-боксы в промоторах и др., часто представляют собой конкатенации серий из разных агрегирований;
3) методы позиционного анализа, позволяющие выявлять аномалии в распределении слов или связных цепочек символов по длине текста (глава 4). Предполагается, что слова, демонстрирующие неравномерность в позиционном распределении, являются более значимыми, чем слова, распределенные равномерно (примером последних являются служебные слова в естественном языке). Известные алгоритмы выявления позиционных аномалий ориентированы преимущественно на обнаружение кластеров — скоплений однородных элементов в ограниченном участке текста. В основе предлагаемой методики выявления неравномерности в позиционном распределении слов или цепочек символов лежит использование сканирующих статистик и имитационного моделирования для оценки значимости наблюдаемых аномалий. Элемент новизны состоит в существенном расширении номенклатуры выявляемых структурных единиц по сравнению с известными методами. Укажем, в частности, на возможность обнаружения "гэпов" (аномально длинных участков, не содержащих заданного слова), "изолированных точек" (элементов, удаленных на значительное расстояние от ближайшего соседа), "аналогов разделителей" (слов, не допускающих слишком большого сближения и/или разрежения), кластеров и периодичностей;
4) методы поиска структурных единиц, представимых в виде образцов (глава 5). Образец — это цепочка, составленная из константных и переменных символов. Множество слов, получаемых подстановкой произвольных "константных цепочек" вместо переменных символов, называют языком, поро- ждаемым заданным образцом. Нахождение в тексте всех слов конкретного языка представляет собой в общем случае трудноразрешимую проблему [68]. В работе рассмотрены два важных частных случая общей проблемы: групповой поиск частично-специфицироеанных образцов и поиск образцов с одной переменной в константном окружении (число вхождений переменной - не менее двух, на длину подстановки ограничений не накладывается). Первая задача является обобщением известной проблемы группового поиска точно определенных образцов [64] на случай, когда элементы образца заданы с точностью до принадлежности к определенным подмножествам исходного алфавита. Для решения этой проблемы предложены новые эффективные алгоритмы, основанные на использовании детерминированных и недетерминированных конечных автоматов. Для решения второй проблемы (поиск образцов с одной переменной в константном окружении) также предложен новый алгоритм, адаптивно настраивающийся на параметры текста и образца, трудоемкость которого "в среднем" существенно меньше, чем у известных аналогов.
На защиту выносятся следующие основные результаты: новая мера сложности символьных последовательностей, характеризующаяся максимально широким учетом повторов разного типа; схемы ее использования для выявления значимых фрагментов текста; алгоритм вычисления, позволяющий обойти факториальный перебор по всевозможным подстановкам на элементах алфавита; метод выявления функционально значимых фрагментов текста путем сочетания многократного агрегирования элементов алфавита с анализом серий в перекодированном тексте; —методика учета позиционной информации для оценки значимости слов или связных цепочек символов, основанная на использовании сканирующих статистик и имитационного моделирования; — эффективные алгоритмы поиска в тексте: а) частично-специфициро- ф ванных образцов в режиме группового запроса; б) образцов с одной пере- менной в константном окружении (без ограничений сверху на кратность вхождений переменной в образец).
Все подходы к выявлению значимых фрагментов текста доведены до программной реализации и апробированы на текстах различной языковой природы (ДНК- и аминокислотные последовательности, последовательности дис- *\ ков в политенных хромосомах, тексты на естественном языке, знаменные пес- нопения).
Работа состоит из введения, пяти глав и заключения. Во введении сформулирована цель работы, обосновывается ее актуальность, описаны предлагаемые подходы и методы решения, а также основные результаты, выносимые на защиту. В первой главе даются обзорные сведения по методам выявления структурных единиц в различных языковых системах с акцентом на направления, развиваемые в рамках данной работы. Содержание глав 2-5 кратко охарактеризовано в п.п. 1)-4) введения. В заключении представлены развернутые выводы по работе.
Морфологический анализ текста без пробелов
В работе [54] описана попытка автоматического вычленения морфем (эле ментарных смысловых единиц языка) из слитного текста с устраненными разделителями между словами и знаками препинания. Предполагается, что письменность исследуемого языка — фонематическая, т.е. не слоговая и не иероглифическая. В основе подхода лежит представление о морфемах как об "устойчивых" (в некотором смысле) отрезках текста.
Предлагаемая в [54] оценка устойчивости опирается на два наблюдения: 1) появление части морфемы сильно прогнозирует появление остальной ча-сти; 2) вхождения морфемы встречаются в разнообразных окружениях. Первое из этих свойств названо внутренней устойчивостью (Stint), второе — внешней устойчивостью (Stext).
Если k и Г{ — левая и правая части некоторой цепочки рі в разбиении текста, то прогнозирование оставшейся части цепочки по уже появившейся оценивается величиной f(hri)/f{k) при расширении вправо или f(hn)/f(ri) (при расширении влево), где f(a) — частота вхождения цепочки а в текст.
Эти величины можно рассматривать в качестве оценок соответствующих условных вероятностей. При "сильном прогнозировании" они стремятся к 1, при слабом — к нулю. Например, при расширении цепочки "челове" вправо с боль шой вероятностью прогнозируется появление буквы "к"; соответственно, при расширении цепочки "еловек" влево — появление буквы "ч". Для других ва риантов разбиения цепочки "человек" на 2 части степень прогнозируемости Ф будет не столь высокой. Внутренняя устойчивость цепочки pi длины d опре деляется как средняя лево- и правосторонняя прогнозируемость р{ по отдельным ее частям (префиксам и суффиксам): w і у (fikn) S(kn)\ " -iJtfUft) fin)) где (d—1) — число всевозможных разбиений pi на 2 части. Для однобуквенных & цепочек Stint полагается равной нулю.
Внешняя устойчивость определяется довольно грубо: Stext — 0, если существует цепочка, содержащая данную и имеющая ту же частоту; 1, в противном случае.
Внешняя устойчивость позволяет выделить цепочки, которые можно считать неделимыми в том смысле, в котором неделима комбинация букв "qu" в английском языке. В то же время это условие отсекает все однократно встречающиеся цепочки, поскольку все их расширения имеют ту же частоту.
Полная устойчивость цепочки р определяется как произведение обеих устойчивостей: St{p) = Stint(p)-Stext(p).
Цель работы состояла в получении разбиения текста (сегментации), кото рое характеризовалось бы максимальной суммарной устойчивостью состав ляющих его фрагментов (цепочек символов). Предложена приближенная последовательная процедура оптимизации, на каждом шаге которой список формируемых "морфем" увеличивается на единицу. Результаты апробации методики на реальном тексте в первом приближении признаны удовлетворительными. В качестве достоинства подхода отмечена его универсальность (возможность применения к текстам на неизвестном языке).
Близкие в идейном плане подходы были развиты для выявления структур ных единиц в ДНК- [90] и аминокислотных последовательностях [10], а также в знаменных песнопениях [3, 4], однако там не ставилось целью получение полного разбиения текста, т.е. решалась скорее задача фрагментирования, а не сегментирования. Это оправдано, поскольку методика носит статистический характер и начинает давать сбои на низкочастотных структурных единицах.
Мера сложности с пошаговой оптимизацией по ограниченному набору подстановок
Понятие /-повтора и его использование в сложностных разложениях Пусть / : Е — Е — взаимнооднозначное отображение алфавита 2 на себя ("переименование" элементов алфавита), Fp — множество всевозможных подстановок (переименований) элементов алфавита, \Fp\ — число подстано . вок (\Fp\ = !). Пусть и — u\U2...Uk — произвольное слово в алфавите , тогда результатом применения подстановки / к слову и является слово f(u\)f(ui)... f(uk)- Если прочесть слово и в обратном порядке, получим слово uR = .Щ. Результатом последовательного применения преобразований / и R к и является слово f(uk)f(uk-i) 1{щ). Слова и = и- щ ... Ufc и v = v\V2 ... Vk совпадают (и = v), если имеет место щ = Vi для всех 1 і к. Пусть и a v два произвольных фрагмента (слова) текста S одинаковой длины. Будем говорить, что пара (и, v) образует прямой повтор, если и = v\ симметричный повтор, если v = uR; прямой f-повтор (повтор с подстановкой /), если Vi = /(щ) для всех 1 і к; симметричный /-повтор, если V\V2 -Vk = f (щ)f (v k-i) f(ui)- Таким образом всего имеем 2 Е! различных типов повторов.
Пример 2.1. Пусть 2 = {А, В} — двоичный алфавит, f(A) = В, f{B) = А — подстановка, переименовывающая символы алфавита. Тогда опи санные выше типы повторов можно проиллюстрировать следующим образом: U V 1) ... ABBBAB ... ABBBAB ... прямой повтор; 2) ... ABBBAB ... BABBBA ... симметричный повтор; 3) ... ABBBAB ... BAAABA ... прямой /-повтор; 4) ... ABBBAB ... ABAAAB ... симметричный /-повтор.
В п. 1.2.2. определена сложность последовательности по Лемпелю и Зиву, основанная на понятии прямого повтора (ему соответствует тождественная подстановка /). В общем случае для любой подстановки / можно определить схему синтеза последовательности, использующую операцию "копирование с подстановкой /", а также схему с операцией: "симметричное копирование с подстановкой /". Операцию генерации символа, как и в мере С\, будем использовать только при отсутствии прототипа для копирования.
Условимся характеризовать тип повтора параметром р (р = 1 2Е!), а сам факт наличия повтора типа р, образуемого двумя фрагментами текста S длины I, начинающимися в позициях г и j, условимся записывать в виде: S[i :i + l - 1] = S\j : j + 1 - 1].
Тогда формула для длины k-то копируемого фрагмента (компонента разложения) будет выглядеть следующим образом: ік - _! = max { : 3[гк., + 1 : ък + if] = S\j : j + if - 1].} (2.1) Соответственно сам к-и компонент может быть записан в виде: З -.г і3 - 1- ПРИ (2.2) [ S [ _х + 1] при j(k) = О,
Если алфавит невелик (двоичные данные, ДНК-последовательности и т.п.), все возможные типы операций копирования (с любой подстановкой и направлением) могут быть использованы по отдельности для вычисления значений сложности C (S) последовательности S. Нижеследующие примеры показы вают, как меняется сложность при использовании разных подстановок.
Пример 2.2. Пусть Е = {А, В}, S = АВВАВААВВААВАВВА, f(A) = .В, f(B) — А. Если вместо прямого копирования (см. пример 1.1.), использовать симметричное (справа-налево), будем иметь разложение Я (5) = А-В-ВА-ВА- АВВА - АВАВвА] C(2)(S) = 6. Здесь для каждого компонента разложения существует симметричный про тотип в предшествующей части текста. Для примера схема копирования по щ, следнего компонента указана стрелками сверху. Если использовать прямое копирование с подстановкой /, схема синтеза 5 примет вид: Я(3)(5) = А-В-ВА- ВААІЇ ВААВАВвА; C(3 (S) = 5. Нетрудно видеть, что вторая половина последовательности повторяет первую, если заменить А на В, В на А, что дает низкое значение сложности. Схема синтеза S при симметричном копировании с подстановкой /: Я(4)(5) = А-В-В-АВ- ААВ ВАІЙ . АвВА] C {S) = 7.
Рассмотрение схем синтеза показывает, что: 1) сложность последователь ности существенно зависит от типа операции копирования; 2) некоторые ком поненты разложения имеют по два (и более) позиционно разнесенных про тотипа в предыстории (см., например, последний компонент в H (S))). В щ некоторых приложениях выбор конкретного прототипа (скажем, ближайшего или, наоборот, максимально удаленного) может иметь практическое значение; 3) если использовать сразу несколько операций копирования и оптимизировать выбор подстановки на каждом шаге, то результирующая сложность бу w # дет не выше минимальной из сложностей, получаемых с помощью одной из этих операций.
Использование серийных характеристик для анализа генетических текстов
После вычисления серийных характеристик на реальной последовательности проводится имитационное моделирование с целью выявления возможных аномалий в полученных значениях. При этом предполагается, что имитационным аналогом исходного текста в первом приближении может служить последовательность независимых одинаково распределенных случайных величин с тем же (что у реальной последовательности) частотным составом элементов. Такие последовательности получаются из исходного текста путем его случайного перемешивания. Более сложные модели, отражающие специфику генетического текста (например, правила динуклеотидного предпочтения [122], локальные неоднородности в распределении нуклеотидов и т.п.), могут быть получены с помощью более сложных схем перемешивания.
При проведении имитационного моделирования задается параметр т — число повторений эксперимента с новой случайной последовательностью (мы использовали значение т = 100). В каждом эксперименте определяются указанные выше характеристики серий. По результатам т экспериментов для каждого параметра а вычисляются его минимальное и максимальное значе — ( m \ ния aJfn = min {аЛ, a = max {аг }, среднее a ( J2 аЛ/тп и средне і—l...m i=l...m \j_l / // m _ \ N 2 квадратичное отклонение s = ((Yl(ai ск)2]/(т -1))
Вывод об аномальности и, соответственно, функциональной значимости параметра а, наблюдаемого на реальной последовательности, делается с помощью одного из двух критериев: "жесткого": а max(aII x, (a-\-3s)) или а 111111(0 , (a — 3s)) (3.1) или более "мягкого": а (a + 2s) или а (а - 2s) (3.2)
Каждый из сегментов вируса гриппа был обработан по схеме с полным агрегированием алфавита (7 вариантов агрегирования). Фиксировались аномалии, связанные с параметрами г (общее число серий), /gmax (максимально длинные серии из 0 и 1), rqj (число серий нулей или единиц длины j). Трудоемкость эксперимента с полным набором агрегирований и имитационным моделированием — 0(2 1 N т).
По результатам экспериментов сделаны следующие выводы.
1. Все 3 типа равномощных агрегирований обнаруживают аномалии в значениях параметра г.
При = {W,S}, как правило, выполняется соотношение г г х, где гпїах максимальное (по серии из 100 экспериментов) значение параметра г для случайных последовательностей (относительное исключение составляют сегменты NA и М). Это означает, что элементы множеств W и S чередуются в исходной последовательности более регулярно, чем это имеет место для их случайных аналогов. Поскольку основной вклад в общее число серий вносят серии длины 1 и 2, значения параметров rq\ и тчч (для q = 0 и q = 1) также близки к аномальным. В то же время, значения параметров lqmax близки к минимальным, т.е. достаточно длинные кластеры из элементов одного типа (W или S) встречаются редко.
Агрегирование = {R, Y} (разбиение на пурины и пиримидины) характеризуется аномально низким общим числом серий для большинства сегментов. Это означает, что элементы каждого из множеств проявляют тенденцию к образованию кластеров — фрагментов, состоящих только из пуринов или пиримидинов. Характерные размеры кластеров — 5-8 символов. Как и в предыдущем случае, параметр г положительно коррелирован с параметрами Гц, гої и (в меньшей степени) с Гі2 и Тог- Все они в большинстве случаев имеют аномально низкие значения.
Агрегирование = {М, К} также характеризуется аномально низким числом серий для большинства сегментов. Однако эффект проявлен в более слабой форме, чем в предыдущем случае: параметры г& ближе к средним значениям, чем к минимальным.
Остальные типы агрегирований (неравномощные) не обнаруживают устойчивых тенденций к аномальному отклонению общего числа серий от показателей, характеризующих случайные последовательности. Отдельные исключения (в сторону низкого общего числа серий), возможно, неявно вытекают из результатов агрегирований = {R, Y} и = {М, К}.
Полученные нами для агрегирования = {W, S} результаты совпадают с выводами Блайсдела [75] о том, что кодирующие последовательности ДНК эукариотического типа характеризуются избытком коротких и дефицитом длинных серий из W и S элементов. Некодирующие же последовательности, по Блайсделу, характеризуются дефицитом коротких и избытком длинных серий пуринов (Я) и пиримидинов (У).
Описание экспериментов. Интерпретация результатов
Рассматривались данные трех типов: подборка аминокислотных последовательностей из разных белковых семейств, подборка нуклеотидных последовательностей (промоторные области генов гормона роста) и тексты на естественном языке (оригинал известной книги Алана А. Милна "Винни-Пух" на английском языке) и два его перевода на русский язык: Б. Заходера (I960 г.) и В. Вебера, Н. Рейн (1999 г.)).
Для первого типа данных анализировалось распределение отдельных аминокислот (каждой из 20) по длине последовательностей. Для второго типа данных исследовалось распределение биграмм (двухэлементных цепочек) по длине нуклеотидных последовательностей. Алфавит биграмм включает в себя 42 = 16 элементов. Аномалии в биграммных характеристиках часто связаны с существованием нестандартных форм ДНК. В этих экспериментах использовалось перемешивание с сохранением биграммного состава.
Для третьего типа данных анализировалось распределение отдельных слов по длине текста. Учет словоизменительной парадигмы в русских текстах проводился путем отбрасывания окончаний. Данная процедура, осуществляемая в автоматическом режиме, не гарантирует 100%-й точности из-за омонимии окончаний ("ими", "ми", "и"), а также совпадения окончаний с частью основы ("ет" — как окончание в глагольных формах и как часть основы в слове "привет"). Однако для целей нашего исследования возникающими погрешностями можно пренебречь.
Целью экспериментов являлась оценка неравномерности позиционного распределения элементарных структурных единиц в текстах различной языко вой природы, выявление наиболее характерных аномалий в позиционном распределении и их взаимосвязи, а также выработка рекомендаций по интерпретации результатов обработки.
Были реализованы все три статистики, описанные в разделе 4.1. (см. (4.1), (4.2), (4.3))1. Для оценивания значимости выявляемых аномалий во всех случаях использовалось имитационное моделирование. Число рандомизированных аналогов исходной последовательности в имитационных экспериментах менялось от 100 (основной вариант) до 1000. Наиболее чувствительными к выявлению различных позиционных аномалий, обусловленных в общем случае не только кластеризацией, но и другими эффектами (периодичностью, запретами на сближение и т.п.), оказались сканирующие статистики. Причины подобной "универсальности" кроются, по-видимому, во взаимосвязи наблюдаемых аномалий, которая будет проиллюстрирована далее на различных примерах.
По степени предпочтительности на второе место можно поставить статистику (4.3) (индекс Моришиты), а на третье — статистику Эберхардта. То, что последняя уступает по своим возможностям сканирующим статистикам, видимо, объясняется недоиспользованием имеющейся позиционной информации (учитываются лишь расстояния от каждой точки до ближайшего соседа). Индекс Моришиты по построению ближе к сканирующим статистикам, но в нем отсутствует, как таковой, элемент сканирования, позволяющий точно локализовать (не пропустить) закономерность, к тому же процедура дробления (уменьшения величины интервала) носит более грубый характер, чем в сканирующих статистиках, что также может привести к пропуску аномалии.
По причинам, изложенным выше, основное внимание далее будет уделено сканирующим статистикам. Две последние были переформулированы для одномерного случая. Пусть х — анализируемый объект (символ, цепочка символов, слово, цепочка слов), распределение которого по длине текста Т мы исследуем, 1(х) — длина цепочки х (в символах или словах), F(x) — частота встречаемости х в Г, N —длина текста Т (в символах или словах). 1. Пусть п — целое число, не меньшее 2. Если dl(n) = п 1(х) и аномально мало, имеет место аномально длинная серия из повторяющихся элементов х. Здесь предполагается использование правила (4.4) со строгим неравенством либо правила (4.6) со значением а ф 0. 2. Если dl(2) аномально велико (что, как минимум, означает отсутствие тандемных повторов, т.е. выполнение неравенства dl(2) 2-/(re)), это можно трактовать как запрет на чрезмерное сближение элементов х. Таким свойством обладают разделители между словами (или более крупными структурными элементами) в естественном языке. Поэтому объекты с указанными свойствами будем называть "аналогами разделителей". 3. Если .01(2) мало, имеет место запрет на чрезмерное удаление. 4. Если имеет место (2) и (3) одновременно, можно говорить о "сверхрав-номерном" распределении пар смежных элементов по длине текста. В общем случае, если выполняются условия {dl(n) — аномально велико, a Dl(n) — аномально мало, п 2}, можно говорить о "сверхравномерном" распределении п-ок из объектов х по длине текста.
