Методы выявления структурных единиц в символьных последовательностях тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Мирошниченко, Любовь Александровна

• Мирошниченко, Любовь Александровна
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Мирошниченко, Любовь Александровна

Введение

Глава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 — длина текста, что в большинстве случаев обеспечивает значительный выигрыш по сравнению с известными (неадаптивными) алгоритмами. Алгоритм может быть использован для поиска "аспектных" словосочетаний в научно-технических текстах, а также для обнаружения "скрытого" цитирования.

Список литературы диссертационного исследования кандидат технических наук Мирошниченко, Любовь Александровна, 2005 год

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.