Главная » 2014 » Август » 11 » Скачать Потенциальные функции для анализа сигналов и символьных последовательностей разной длины. Сулимова, Валентина Вячеславовна бесплатно
4:44 AM
Скачать Потенциальные функции для анализа сигналов и символьных последовательностей разной длины. Сулимова, Валентина Вячеславовна бесплатно
Потенциальные функции для анализа сигналов и символьных последовательностей разной длины
Диссертация
Автор: Сулимова, Валентина Вячеславовна
Название: Потенциальные функции для анализа сигналов и символьных последовательностей разной длины
Справка: Сулимова, Валентина Вячеславовна. Потенциальные функции для анализа сигналов и символьных последовательностей разной длины : диссертация кандидата физико-математических наук : 05.13.17 / Сулимова Валентина Вячеславовна; [Место защиты: Вычисл. центр РАН] - Тула, 2009 - Количество страниц: 121 с. ил. Тула, 2009 121 c. :
Объем: 121 стр.
Информация: Тула, 2009
Содержание:
ВВЕДЕНИЕ
1 ПРОБЛЕМА АНАЛИЗА СИГНАЛОВ И СИМВОЛЬНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ПО КРИТЕРИЮ ПАРНОГО СХОДСТВА
11 Примеры прикладных задач анализа сигналов и символьных последовательностей
111 Идентификация личности по динамике подписи
112 Исследование связи между первичной структурой белков и их биологическими функциями
12 Метод потенциальных функций как методология погружения множеств объектов произвольной природы в линейное пространство со скалярным произведением
121 Метрики и потенциальные функции на множестве объектов произвольной природы
122 Линейное пространство, порождаемое потенциальной функцией
123 Принципы восстановления зависимостей на основе метода потенциальных функций
13 Недостаточность существующих методов измерения сходства сигналов и символьных последовательностей
14 Построение потенциальных функций по принципу вычисления правдоподобия гипотезы об общем случайном происхождении пары последовательностей
15 Основные задачи исследования
2 ПОТЕНЦИАЛЬНЫЕ ФУНКЦИИ НА МНОЖЕСТВЕ ПРИМИТИВОВ
21 Потенциальные функции на множестве элементов сигналов
211 Скалярное произведение векторных элементов сигналов
212 Радиальные потенциальные функции на множестве векторов
22 Потенциальные функции на конечном алфавите
221 Марковская цепь на конечном алфавите и определяемая ею потенциальная функция
2211 Общий принцип формирования потенциальной функции на основе марковской цепи
2212 Специфика эргодической и обратимой марковской цепи
222 Пример введения потенциальных функций на алфавите аминокислот, составляющих полимерные молекулы белков
2221 Модель эволюции Маргарет Дэйхофф
2222 Положительно определенные подстановочные матрицы РАМ
2223 Положительно определенные подстановочные матрицы BLOSUM
3 ВЕРОЯТНОСТНЫЙ ПРИНЦИП ФОРМИРОВАНИЯ ПОТЕНЦИАЛЬНЫХ ФУНКЦИЙ НА МНОЖЕСТВЕ СИГНАЛОВ И СИМВОЛЬНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ
31 Потенциальная функция как правдоподобие гипотезы независимого происхождения двух последовательностей от общего прародителя относительно заданного случайного преобразования
32 Модель случайного преобразования последовательностей
321 Семейство двухэтапных случайных преобразований
3211 Случайная структура преобразования
3212 Преобразование, зависящее от структуры
322 Основные предположения о модели случайного преобразования
33 Общая структура потенциальной функции
34 Частные виды потенциальных функций
341 Потенциальные функции фиксированного и нефиксированного порядка
342 Локальные и глобальные потенциальные функции
343 Потенциальные функции для символьных последовательностей
344 Потенциальные функции для сигналов
35 Алгоритмы вычисления потенциальных функций
351 Общая идея построения алгоритмов вычисления потенциальных функций
352 Потенциальные функции нефиксированного порядка для символьных последовательностей
353 Потенциальные функции нефиксированного порядка для сигналов
354 Потенциальные функции фиксированного порядка
4 ПРЕДСТАВЛЕНИЕ ГРУППЫ АМИНОКИСЛОТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ В ВИДЕ ВЕРОЯТНОСТНОГО ПРОФИЛЯ ИХ НАИБОЛЕЕ ПРАВДОПОДОБНОГО ПРАРОДИТЕЛЯ
41 Проблема наглядного представления группы последовательностей, полученной на основе метода потенциальных функций
42 Локальная вероятностная модель происхождения группы последовательностей от общего прародителя заданной длины
43 Оценка вероятностной модели прародителя
431 Постановка задачи поиска наиболее правдоподобного общего прародителя заданной длины в виде его вероятностного профиля
432 Итерационная процедура оценивания вероятностного профиля
433 Вычисление апостериорных вероятностей на каждом шаге итерационной процедуры оценивания вероятностного профиля
4331 Процесс преобразования прародителя в формируемую последовательность как случайный процесс со скрытой марковской и условной наблюдаемой компонентами
4332 Априорные вероятностные свойства скрытого марковского процесса преобразования последовательностей
4333 Нахождение искомых апостериорных свойств скрытого марковского процесса
5 ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ ПРЕДЛОЖЕННОГО МАТЕМАТИЧЕСКОГО АППАРАТА
51 Верификация личности по динамике подписи на основе метода потенциальных функций
511 Потенциальные функции на множестве подписей
5111 Структура сигнала, порождаемого динамической подписью
5112 Множество потенциальных функций, используемых для верификации личности
512 Обучение верификации личности
5121 Обучение по одной потенциальной функции: Метод опорных объектов
5122 Обучение по конечному множеству потенциальных функций
513 Экспериментальное исследование алгоритмов верификации личности
5131 Структура экспериментов
5132 Результаты экспериментов
52 Установление гомологии белков путем автоматической классификации составляющих их аминокислотных последовательностей
521 Задача установления гомологии белков
522 Автоматическая классификация белков методом ^-средних, адаптированным для потенциальных функций
523 Структура экспериментов
524 Результаты экспериментов
53 Экспериментальное исследование процедуры поиска общего прародителя группы последовательностей
531 Модельные эксперименты
532 Эксперименты на реальных данных
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
Введение:
Сигналы и символьные последовательности являются наиболее распространенными видами организации данных.
Особый интерес к компьютерной обработке именно сигналов в значительной мере определяется тем фактом, что это естественный вид организации потоков информации о внешнем мире, получаемой человеком через органы чувств, главным образом, посредством осязания, обоняния, слуха и зрения, и играющей фундаментальную роль в формировании их поведения.
Под сигналом принято понимать любую физическую величину, изменение которой во времени несет информацию о мире, внешнем по отношению к тому объекту, который эту информацию воспринимает. С точки зрения организации компьютерной обработки, когда время вынужденно рассматривается как дискретная переменная, сигнал представляет собой упорядоченную последовательность либо векторов некоторой определенной размерности, либо символов, если физическая величина, несущая информацию, сама имеет дискретный характер (в этом случае речь идет о символьных последовательностях). Роль оси, упорядочивающей отдельные единицы информации в массив данных, не обязательно должно играть время, это может быть и любая другая ось, например, пространственная координата.
Широко известны такие прикладные задачи анализа сигналов как задача распознавания речевых команд и слитной речи, задача распознавания рукописных символов, текстов в процессе их написания, задача идентификации личности по динамике подписи, задачи анализа электрокардиограмм и сейсмических сигналов, задача распознавания пространственной структуры белков по составляющим их последовательностям аминокислотных остатков, задача исследования зависимости между первичной структурой белков и их биологическими функциями и др.
Согласно классической теории распознавания образов, во всех этих задачах требуется определить скрытую принадлежность поступающего на вход системы сигнала (или символьной последовательности) к одному из известных классов (например, установить личность автора в задаче идентификации личности по динамике подписи; определить, какое слово произнесено или написано и т.д.) на основе имеющейся информации об объективной классификации некоторого доступного подмножества всех возможных объектов и известных значений некоторых числовых характеристик для любого объекта (вектора его признаков), которые должны быть сформированы до начала обучения.
Все рассмотренные задачи имеют очень важную характерную особенность — в них дискретные сигналы или символьные последовательности, представляющие реальные объекты, в общем случае имеют различную длину. В результате в них трудно заранее указать фиксированное число признаков, которые смогли бы сформировать пространство, удовлетворяющее гипотезе компактности, лежащей в основе классических методов распознавания, т.е. пространство, в котором объекты, принадлежащие к одному классу, занимали бы некоторую обособленную область и выпуклые оболочки таких областей не пересекались.
Вообще говоря, проблеме представления векторных и символьных последовательностей разной длины в алгоритмах анализа данных посвящена обширная литература. Наиболее популярным является беспризнаковый подход, основанный на измерении парного сходства последовательностей путем вычисления потенциальной функции, т.е. двухместной симметрической действительной функции, образующей неотрицательно определенную матрицу для любой конечной совокупности объектов. В результате множество всех последовательностей разной длины оказывается погруженным в гипотетическое линейное пространство со скалярным произведением, роль которого играет сама потенциальная функция. Такая математическая конструкция позволяет применять хорошо разработанные линейные методы анализа данных к совокупностям объектов произвольной природы.
В то же время, методология формирования потенциальных функций над множествами последовательностей разной длины еще далека от завершения и требует дальнейшего развития.
Первая проблемная ситуация заключается в том, что для большинства прикладных задач потенциальная функция на множестве последовательностей отвечает практическим целям анализа данных только в том случае, если она основана на некоторой элементарной потенциальной функции на множестве примитивов. Такое требование естественным образом выполняется для векторных сигналов, в качестве примера которых в данной диссертации рассматриваются динамические подписи.
Что же касается символьных последовательностей, то подавляющее большинство публикаций на эту тему ориентировано на анализ биологических полимеров, в частности, аминокислотных последовательностей белков. Именно этот вид символьных последовательностей находится в центре внимания в данной диссертации. В современной биохимии общепринятым способом измерения сходства аминокислот являются подстановочные матрицы РАМ (Point Accepted Mutation) и BLOSUM (BLock Substitution Matrix), которые в традиционной форме не являются потенциальными функциями. С этой точки зрения соответствующие способы построения потенциальных функций на множествах символьных последовательностей разной длины являются эвристическими.
Вторая проблемная ситуация порождена тем обстоятельством, что наличие формальных свойств скалярного произведения у формируемой меры сходства аминокислотных последовательностей, как правило, оказывается недостаточным для ее эффективного использования при решении задач классификации белков на семейства, обладающие сходными биологическими функциями. Центральной гипотезой биоинформатики, многократно подтвержденной на практике, является предположение, что эволюционно близкие белки выполняют похожие биологические функции в организме. В связи с этим специалисты в области молекулярной биологии крайне недоверчиво относятся к мерам сходства белков, значения которых не могут быть интерпретированы как меры их эволюционной близости. Однако ни один из известных способов формирования потенциальных функций на множестве аминокислотных последовательностей не является одновременно математически корректным и обоснованным с точки зрения вероятностной модели эволюции белков.
Кроме того, несмотря на то, что дискретные сигналы и символьные последовательности имеют похожую структуру, в настоящее время не существует единого математического аппарата для их сравнения. Единственный корректный способ построения потенциальных функций на множестве сигналов разной длительности, предложенный французским ученым Ж.-Ф. Вертом, имеет ряд неестественных ограничений, дополнительно введенных по сравнению с аналогичным подходом, разработанным для символьных последовательностей.
Наконец, третья проблемная ситуация, выбранная для исследования в данной диссертации, порождена необходимостью интерпретации результатов классификации последовательностей разной длины, полученной тем или иным алгоритмом, основанным на их погружении в линейное пространство путем введения потенциальной функции. Всякая конечная совокупность последовательностей, выделенная в качестве класса, имеет естественную модель в виде его центра, т.е. гипотетического среднего объекта в линейном замыкании всех последовательностей. Можно доказать, что результат усреднения конечного множества последовательностей разной длины, в частности, аминокислотных последовательностей белков, в смысле линейных операций, определяемых некоторой потенциальной функцией, в общем случае не будет являться последовательностью конечной длины.
Для разрешения первой проблемной ситуации относительно аминокислотных последовательностей белков в диссертации используется тот факт, что обе общепринятые меры сходства аминокислот, как РАМ, так и ВЬОБЦМ, численно выражают правдоподобие гипотезы об общем происхождении двух указанных аминокислот от одной неизвестной аминокислоты в результате двух независимых шагов эволюции. Такая двухместная функция на алфавите аминокислот всегда является потенциальной функцией по своей структуре. Практически используемые подстановочные матрицы РАМ и ВЪОБЦМ не являются положительно определенными только в силу логарифмического представления результата, к тому же округленного до целого значения.
Разрешение второй проблемной ситуации основано на идее прямого переноса принципа измерения эволюционного сходства аминокислот на аминокислотные последовательности в целом. Потенциальные функции предлагается строить как функции правдоподобия гипотезы, что две заданные последовательности получены из общего неизвестного прародителя в результате двух независимых ветвей эволюции. Разные потенциальные функции на множестве символьных последовательностей, рассматриваемые в диссертации, отличаются друг от друга только разными предположениями о множестве допустимых прародителей и априорном распределении вероятностей на нем, а также разными вероятностными моделями эволюционных преобразований, сводящихся к случайным вставкам, удалениям и заменам символов в исходной последовательности.
Что касается сигналов, то, хотя прикладные задачи их анализа не требуют измерения именно эволюционного сходства, предложенная вероятностная концепция не противоречит их природе. Потенциальные функции на множестве сигналов строятся по тому же принципу и отличаются только спецификой случайных преобразований, в которых вместо вставок и удалений элементов фигурируют локальные сжатия и растяжения оси времени.
В качестве теоретической основы разрешения третьей проблемной ситуации предлагается постановка задачи поиска общего прародителя фиксированной длины п для группы последовательностей путем максимизации правдоподобия гипотезы об их случайном независимом происхождении из скрытого общего прародителя известной длины п в результате предложенных в данной работе случайных преобразований. При этом последовательность-прародитель предлагается искать в виде совокупности независимых распределений его элементов, что соответствует общепринятому в биоинформатике понятию профиля.
Цель работы. Целью диссертационной работы является разработка методов построения и алгоритмов вычисления потенциальных функций на множествах сигналов и символьных последовательностей разной длины, позволяющих погрузить исходное множество объектов в соответствующее гипотетическое линейное пространство со скалярным произведением, адекватное решаемой типовой задаче классификации сигналов либо символьных последовательностей.
Задачи исследования. Для достижения поставленной цели в диссертации сформулированы и решены следующие задачи:
1. Разработка вероятностного принципа построения потенциальных функций на конечном алфавите элементов последовательностей на основе марковской модели их случайных преобразований.
2. Построение потенциальных функций на множестве аминокислот на основе модели эволюции М. Дэйхофф.
3. Построение моделей случайного преобразования на множествах сигналов и символьных последовательностей разной длительности.
4. Разработка вероятностного принципа формирования потенциальных функций на множествах сигналов и символьных последовательностей разной длительности.
5. Разработка алгоритмов вычисления потенциальных функций на множествах сигналов и символьных последовательностей.
6. Разработка методов наглядного представления об общем прародителе для заданной совокупности последовательностей разной длины.
7. Использование потенциальных функций для автоматической классификации белков на функциональные семейства и для верификации личности по динамике подписи.
Методы исследования. Исследование базируется на использовании теории распознавания образов, теории линейных пространств со скалярным произведением, теории марковских случайных процессов.
Научная новизна. В работе предложены новые вероятностные модели случайных преобразований сигналов и символьных последовательностей, в частности, модели эволюционных изменений аминокислотных последовательностей белков. На основе этих моделей впервые построен класс корректных потенциальных функций, выражающих правдоподобие гипотезы о наличии общего прародителя у пары сравниваемых сигналов либо символьных последовательностей разной длины. Впервые доказано, что меры сходства аминокислот РАМ и ВЬОЗЦМ, общепринятые в современной биоинформатике, основаны на одной и той же модели эволюции аминокислот, разработанной Маргарет Дэй-хофф, и по своей структуре являются потенциальными функциями. Впервые поставлена и решена задача поиска общего прародителя заданной длины для группы последовательностей в терминах введенного случайного преобразования.
Положения, выносимые на защиту
1. Семейство потенциальных функций на алфавите аминокислот, выражающее смысл общепринятых подстановочных матриц РАМ и BLOSUM.
2. Комплекс вероятностных моделей случайных преобразований сигналов и символьных последовательностей.
3. Класс корректных потенциальных функций, выражающих правдоподобие гипотезы о наличии общего прародителя у пары сравниваемых сигналов либо символьных последовательностей разной длины.
4. Алгоритмы вычисления потенциальных функций на множествах сигналов и символьных последовательностей разной длины.
5. Задача поиска общего прародителя заданной длины для группы последовательностей.
Достоверность полученных результатов подтверждается доказательствами сформулированных в диссертации теорем и результатами решения прикладных задач.
Практическая значимость. Разработанные принципы и алгоритмы позволяют корректно использовать методы анализа данных, разработанные для линейных признаковых пространств, для решения задач классификации сигналов и символьных последовательностей разной длины, в которых трудно заранее сформировать пространство достаточно информативных числовых характеристик объектов.
Связь с плановыми научными исследованиями. Работа выполнена при поддержке грантов Российского фонда фундаментальных исследований №№ 05-01-00679-а, 06-01-08042-офи, 08-01-00695-а и 08-01-12023-офи, а также грантов INTAS № 04-77-7347 и Young Scientist PhD Fellowship № 06-10000146563.
Реализация и внедрение результатов работы. Результаты исследования применены для решения задачи автоматической классификации белков по составляющим их последовательностям аминокислот на классы белков, выполняющих сходные биологические функции в организме, и задачи верификации личности по динамике подписи.
Апробация работы. Основные положения и результаты диссертации докладывались на конференциях: «Математические методы распознавания образов» (Пущино, 2003 г., Звенигород, 2005 г., Зеленогорск, 2007 г.), «Распознавание образов и анализ изображений» (Санкт-Петербург, 2004), «Интеллектуализация обработки информации» (Алушта, Крым, 2004, 2006, 2008 гг.), «Обработка сигналов и изображений» (IASTED SIP-2006, Гонолулу, Гавайи, 2006 г.), «Международная конференция по распознаванию образов» (ICPR-2008, Флорида, США, 2008 г.), на семинарах партнеров по гранту INTAS «Принципы распознавания сигналов, символьных последовательностей и изображений на основе измерения их несходства» в Москве (2005 г.), в Гилдфорде, Великобритания (2005 г.), в Праге, Чехия (2006 г.) и Киеве, Украина (2007 г.), на семинаре по анализу данных, Биркбек колледж, Лондон, Великобритания, 2008 г.
Публикации. По тематике исследований опубликовано 11 статей, в том числе 2 статьи в журналах, рекомендованных ВАК.
Структура и объем работы. Диссертация состоит из введения, 5 глав, основных выводов и списка литературы. Материал изложен на 121 страницах, содержит 22 рисунка, 6 таблиц и список литературы из 118 наименований.