Введение
Глава 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
Список использованных источников
