Потенциальные функции для анализа сигналов и символьных последовательностей разной длины тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Сулимова, Валентина Вячеславовна

• Сулимова, Валентина Вячеславовна
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Сулимова, Валентина Вячеславовна

ВВЕДЕНИЕ.

1 ПРОБЛЕМА АНАЛИЗА СИГНАЛОВ И СИМВОЛЬНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ПО КРИТЕРИЮ ПАРНОГО СХОДСТВА.

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

1.1.1 Идентификация личности по динамике подписи.

1.1.2 Исследование связи между первичной структурой белков и их биологическими функциями.

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

1.2.1 Метрики и потенциальные функции на множестве объектов произвольной природы.

1.2.2 Линейное пространство, порождаемое потенциальной функцией.

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

1.3 Недостаточность существующих методов измерения сходства сигналов и символьных последовательностей.

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

1.5 Основные задачи исследования.

2 ПОТЕНЦИАЛЬНЫЕ ФУНКЦИИ НА МНОЖЕСТВЕ ПРИМИТИВОВ.

2.1 Потенциальные функции на множестве элементов сигналов.

2.1.1 Скалярное произведение векторных элементов сигналов.

2.1.2 Радиальные потенциальные функции на множестве векторов.

2.2 Потенциальные функции на конечном алфавите.

2.2.1 Марковская цепь на конечном алфавите и определяемая ею потенциальная функция.

2.2.1.1 Общий принцип формирования потенциальной функции на основе марковской цепи.

2.2.1.2 Специфика эргодической и обратимой марковской цепи.

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

2.2.2.1 Модель эволюции Маргарет Дэйхофф.

2.2.2.2 Положительно определенные подстановочные матрицы РАМ.

2.2.2.3 Положительно определенные подстановочные матрицы BLOSUM.

3 ВЕРОЯТНОСТНЫЙ ПРИНЦИП ФОРМИРОВАНИЯ ПОТЕНЦИАЛЬНЫХ ФУНКЦИЙ НА МНОЖЕСТВЕ СИГНАЛОВ И СИМВОЛЬНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ.

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

3.2 Модель случайного преобразования последовательностей.

3.2.1 Семейство двухэтапных случайных преобразований.

3.2.1.1 Случайная структура преобразования.

3.2.1.2 Преобразование, зависящее от структуры.

3.2.2 Основные предположения о модели случайного преобразования.

3.3 Общая структура потенциальной функции.

3.4 Частные виды потенциальных функций.

3.4.1 Потенциальные функции фиксированного и нефиксированного порядка.

3.4.2 Локальные и глобальные потенциальные функции.

3.4.3 Потенциальные функции для символьных последовательностей.

3.4.4 Потенциальные функции для сигналов.

3.5 Алгоритмы вычисления потенциальных функций.

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

3.5.2 Потенциальные функции нефиксированного порядка для символьных последовательностей.

3.5.3 Потенциальные функции нефиксированного порядка для сигналов.

3.5.4 Потенциальные функции фиксированного порядка.

4 ПРЕДСТАВЛЕНИЕ ГРУППЫ АМИНОКИСЛОТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ В ВИДЕ ВЕРОЯТНОСТНОГО ПРОФИЛЯ ИХ НАИБОЛЕЕ ПРАВДОПОДОБНОГО ПРАРОДИТЕЛЯ.

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

4.2 Локальная вероятностная модель происхождения группы последовательностей от общего прародителя заданной длины.

4.3 Оценка вероятностной модели прародителя.

4.3.1 Постановка задачи поиска наиболее правдоподобного общего прародителя заданной длины в виде его вероятностного профиля.

4.3.2 Итерационная процедура оценивания вероятностного профиля.

4.3.3 Вычисление апостериорных вероятностей на каждом шаге итерационной процедуры оценивания вероятностного профиля.

4.3.3.1 Процесс преобразования прародителя в формируемую последовательность как случайный процесс со скрытой марковской и условной наблюдаемой компонентами.

4.3.3.2 Априорные вероятностные свойства скрытого марковского процесса преобразования последовательностей.

4.3.3.3 Нахождение искомых апостериорных свойств скрытого марковского процесса.

5 ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ ПРЕДЛОЖЕННОГО МАТЕМАТИЧЕСКОГО АППАРАТА.

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

5.1.1 Потенциальные функции на множестве подписей.

5.1.1.1 Структура сигнала, порождаемого динамической подписью.

5.1.1.2 Множество потенциальных функций, используемых для верификации личности.

5.1.2 Обучение верификации личности.

5.1.2.1 Обучение по одной потенциальной функции: Метод опорных объектов

5.1.2.2 Обучение по конечному множеству потенциальных функций.

5.1.3 Экспериментальное исследование алгоритмов верификации личности.

5.1.3.1 Структура экспериментов.

5.1.3.2 Результаты экспериментов.

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

5.2.1 Задача установления гомологии белков.

5.2.2 Автоматическая классификация белков методом ^-средних, адаптированным для потенциальных функций.

5.2.3 Структура экспериментов.

5.2.4 Результаты экспериментов.

5.3 Экспериментальное исследование процедуры поиска общего прародителя группы последовательностей.

5.3.1 Модельные эксперименты.

5.3.2 Эксперименты на реальных данных.

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

Введение диссертации (часть автореферата) на тему «Потенциальные функции для анализа сигналов и символьных последовательностей разной длины»

Сигналы и символьные последовательности являются наиболее распространенными видами организации данных.

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

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

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

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

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

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

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

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

Что же касается символьных последовательностей, то подавляющее большинство публикаций на эту тему ориентировано на анализ биологических полимеров, в частности, аминокислотных последовательностей белков. Именно этот вид символьных последовательностей находится в центре внимания в данной диссертации. В современной биохимии общепринятым способом измерения сходства аминокислот являются подстановочные матрицы РАМ (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 наименований.

Заключение диссертации по теме «Теоретические основы информатики», Сулимова, Валентина Вячеславовна

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. В данной работе доказано, что меры сходства аминокислот РАМ и ВЬО-8ИМ, общепринятые в современной биоинформатике, основаны на одной и той же модели эволюции аминокислот, разработанной Маргарет Дэйхофф, и по своей структуре являются потенциальными функциями.

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Сулимова, Валентина Вячеславовна, 2009 год

1. Plamandon R., Srihari S. N. On-line and off-line handwriting recognition: A comprehensive survey // IEEE Trans. Pattern Recognition and Machine Intelligence, 2000, Vol. 22, pp. 107131.

2. Kholmatov, A., Yanikoglu, В.: Biometric authentication using online signatures // Proc. ISCIS, Springer LNCS-3280, 2004, pp. 373 380.

3. Martens R., Claesen L. On-line signature verification by dynamic time-warping // IEEE: ICPR, 1996, pp. 38-42.

4. Колядин Д.В. Анализ динамических кривых применительно к задаче верификации рукописной подписи // Сборник трудов 11-й всероссийской конференции Математические методы распознавания образов, 2003, с. 330 332.

5. J. Richiardi, Н. Ketabdar, A. Drygajlo. Local and global feature selection for on-line signature verification // Proceedings of the Eighth International Conference on Document Analysis and Recognition (ICDAR'05), Seoul, South Korea, 2005, 625-629.

6. Сулимова B.B., Моттль B.B. Идентификация личности по динамике подписи методом опорных векторов// Труды международной научной конференции ММТТ-16, Ростов-на-Дону, 2003г, т.4, С.23-25.

7. Feng Н., Wah С.С. Online signature verification using a new extreme points warping technique // Pattern Recognition Letters, 2003, Vol. 24, pp. 2943-2951.

8. Zhang D., Jain A.K. Searching for an Optimal Reference System for On-Line Signature Verification Based on (x, y) Alignment // ICBA 2004, LNCS 3072, pp. 519-525, 2004.

9. Ту Дж., Гонсалес P. Принципы распознавания образов. М.: МИР, 1978, 401с.

10. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976, 511 с. .

11. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. М.: Наука, 1974,415 с.

12. Патрик Э. Основы теории распознавания образов. М.: Сов. радио, 1980, 408 с.

13. Загоруйко Н.Г. Прикладные методы анализа данных и знаний. Новосибирск: Изд-во Ин-та математики, 1999, 270 с.

14. Martens R., Claesen L. Dynamic programming optimisation for on-line signature verification // Proceedings of the Fourth International Conference on Document Analysis and Recognition (ICDAR'97), Ulm, Germany, 1997, Vol. 2, pp. 653-656.

15. Chu S.,Keogh E., Hart D., Pazzani M. Iterative deeping dynamic time warping for time series. // IEEE International Conference of Data Mining. Maebashi City. Japan, 2002.

16. Дмитриев Д.А., Сулимова B.B., Моттль B.B. Измерение попарного несходства подписей для идентификации личности // Сборник трудов международной конференции ММТТ-16, 2003, т.4, с. 216-218.

17. Hansheng Lei , Bingyu Sun. A Study on the Dynamic Time Warping in Kernel Machines // Proceedings of the 2007 Third International IEEE Conference on Signal-Image Technologies and Internet-Based System, 2007, pp. 839-845.

18. W. A. Chaovalitwongse and P. M. Pardalos. On the time series support vector machine using dynamic time warping kernel for brain activity classification // Springer Science+Business Media, Inc., 2008, pp.125-138.

19. D. DeCoste and B. Scholkopf. Training invariant support vector machines //Machine Learning, 46(1/3):161, 2002.

20. Bahlmann C., Haasdonk B., and Burkhardt H. On-line Handwriting Recognition with Support Vector Machines— A Kernel Approach // Proc. of the 8th IWFHR, 2002, pp. 49-54.

21. B. Haasdonk and D. Keysers. Tangent distance kernels for support vector machines // Proc. of the 16th ICPR, 2002.

22. Shimodaira, H., Noma, K., Nakai, M. Dynamic time-alignment kernel in Support Vector Machine. //Advances in Neural Information Processing Systems 14, Vol. 2. MIT Press, Cambridge, MA, 2002, pp. 921-928.

23. Pekalska E., Paclic P., Duin R. A Generalized Kernel Approach to Dissimilarity-based Classification //Journal of Machine Learning Research 2,2001, 175-211.

24. Hong-Wei Ji and Zhong-Hua Quan. Signature Verification Using Wavelet Transform and Support Vector Machine //Lecture Notes in Computer Science. Volume 3644/2005, 2005, pp. 671-678.

25. Lavi Shpigelman, Yoram Singer, Rony Paz, and Eilon Vaadia. Spikernels: Predicting arm movements by embedding population spike rate patterns in inner-product spaces //Neural Computation, vol. 17, no. 3, 2005, pp. 671-690.

26. Corinna Cortes, Patrick Haffner, and Mehryar Mohri, Rational kernels: Theory and algorithms // JMLR, vol. 5, 2004, pp. 1035-1062.

27. Eichhorn, J. Applications of Kernel Machines to Structured Data: PhD thesis / Eichhorn, J. Berlin, 2007.

28. K. R. Sivaramakrishnan, K. Karthik, and C. Bhattachaiyya. Kernels for large margin time-series classification // Neural Networks, IJCNN 2007, International Joint Conference, 2007, pp. 2746-2751.

29. Vapnik V. Statistical Learning Theory. Wiley, Chichester, GB, 1998.

30. Kholmatov, A., Yankolu, B. Identity Authentication Using Improved On-line Signature Verification Method // Pattern Recognition Letters, vol. 26, no. 15, 2005, pp. 2400-2408.

31. Bousquet, O.; Pez-Cruz, F. Kernel methods and their applications to signal processing. // 2003 IEEE International Conference. Acoustics, Speech, and Signal Processing, Proceedings. (ICASSP '03). vol.4, 2003, IV- 860-3.

32. N. Smith and M. Gales. Speech recognition using SVMs //Advances in Neural Information Processing Systems. /T. Dietterich, S. Becker, and Z. Ghahramani editors.volume 14. MIT Press, 2002.

33. L. Ralaivola, F. d'Alche-Buc. Dynamical Modeling with Kernels for Nonlinear Time Series Prediction, //Advances in Neural Information Processing Systems, /L. Saul eds, MIT Press, 2004.

34. Yoon, H.S.; Lee, J.Y.; Yang, H.S. An online signature verification system using hidden Markov model in polar space. Frontiers in Handwriting Recognition 2002 // Proceedings. Eighth International Workshop, 2002, pp. 329 333.

35. Haussler, D. Convolution kernels on discrete structures. Technical Report UCSC-CRL-99-10, UC Santa Cruz, 1999.

36. Watkins, C. Dynamic alignment kernels //Advances in Large Margin Classifiers /А. J. Smola, P. L. Bartlett, B. Sch'olkopf and D. Schuurmans eds. MIT Press, Cambridge, MA, 2000, pp. 3950.

37. Clark A. Learning morphology with pair hidden markov models // Proceedings of the Student Workshop at ACL 2001, Toulouse, July 2001.

38. V. Wan and S. Renals, Evaluation of kernel methods for speaker verification and identification, // Proc. ICASSP 2002, Orlando, FL, 2002.

39. M. Cuturi, J. P. Vert, O. Birkenes, and T. Matsui. A Kernel for Time Series Based on Global Alignments. Proc. // ICASSP, 2007, pp. 413-416.

40. Гельфанд M.C. Апология биоинформатики //Биофизика, 2005, том 50, № 4, с. 752-766.

41. Needleman S.B., Wunsch C.D. A general method applicable to the search for similarities in the amino-acid sequence of two proteins //Journal of Molecular Biology: 48, 1970, pp. 443-53.

42. Smith T.F., Waterman M.S. Identification of common molecular subsequences // Journal of Molecular Biology: 147, 1981, pp. 195-197.

43. 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 search programs // Nucleic Acids Research, 25: 1997, pp. 3389-3402.

44. Pearson W.R. Flexible sequence similarity searching with the FASTA3 program package // Methods Mol. Biol.: 132, 2000, pp.l85-219.

45. Sankoff D. and Kruskal J., Eds. Time warps, string edits, and macromolecules: The theory and practice of sequence comparison // CSLI Publications, Stanford, 1999.

46. Joachims T. Learning to Align Sequences: A Maximum-Margin Approach, 2003.

47. Kernel Methods in Computational Biology / B. Scholkopf, K. Tsuda and J.-P. Vert. eds. MIT Press, 2004.

48. T. Hofmann, B. Scholkopf, and A. J. Smola. Kernel methods in machine learning // Ann. Statist. Volume 36, Number 3, 2008, pp.1171-1220.

49. A. Ben-Hur, C. S. Ong, S. Sonnenburg, B. Scholkopf and G. Riitsch. Support Vector Machines and Kernels for Computational Biology // PLoS Comput Biol. 2008 October; 4(10).

50. Bernhard Sch'olkopf and Alexander J. Smola. Learning with Kernels: Support Vector Machines, Regularization , Optimization, and Beyond. MIT Press, Cambridge, MA, 2002.

51. Sonnenburg S, Ra" tsch G, Rieck K. Large scale learning with string kernels. /Bottou L3 Chapelle O, DeCoste D, Weston J, eds. Large scale kernel machines MIT Press., 2007, pp. 73 104.

52. Zhang, S.-W., Pan, Q., Zhang, H.-C., Zhang, Y.-L., and Wang, H.-Y. Classification of protein quaternary structure with support vector machine //Bioinformatics, 2003, 19(18), pp. 2390— 2396.

53. T. Hofmann, B. Schôlkopf, and A. J. Smola Kernel methods in machine learning //Ann. Statist. Volume 36, Number 3, 2008, pp. 1171-1220.

54. Gert R. G. Lanckrietl, Tijl De Bie3, Nello Cristianini4, Michael I. Jordan2 and William Stafford Noble5. A statistical framework for genomic data fusion //Bioinformatics, Vol. 20 no. 16, 2004, pp. 2626-2635.

55. Kuang R., le E., Wang Ke and Kai, Siddiqi M., Freund Y., Leslie C. Profile-Based String Kernels for Remote Homology Detection and Motif Extraction. CSB, 2004, pp. 152-160.

56. Leslie, C. S., Eskin, E., Cohen, A., Weston, J., and Noble, W. S. Mismatch, string kernels for discriminative protein classification //Bioinformatics, 2004, 20(4), pp. 467—476.

57. Tsuda K, Kawanabe M, Ra" tsch G, Sonnenburg, S Mu" lier K. A new discriminative kernel from probabilistic models //Neural Computation 14, 2002, pp. 2397-2414.

58. Wang, M., Yang, J., Liu, G.-P., Xu, Z.-J., and Chou, K.-C. Weighted-support vector machines for predicting membrane protein types based on pseudo-amino acid composition //Protein Eng. Des. Sel., 17(6), 2004, pp. 509-516.

59. L. Liao and W. S. Noble. Combining pairwise sequence similarity and support vector machines for remote protein homology detection // Proceedings of the Sixth Annual International. Conference on Computational Molecular Biology, pp. 225-232, 2002

60. Ben-Hur, A. and Brutlag, D. Remote homology detection: a motif based approach //Bioinformatics, 19(Suppl. 1), 2003, pp. 26-33.

61. Kondor,R.I. and Lafferty,J. Diffusion kernels on graphs and other discrete input spaces. /Sammut,C. and Hoffmann,A. eds // Proceedings of the International Conference on Machine Learning. Morgan Kaufmann, San Francisco, CA, 2002, pp. 315-322.

62. Vert, J.-P., Saigo, H., and Akutsu, T. Local alignment kernels for biological sequences /Sch'olkopf, B., Tsuda, K., and Vert, J. editors. Kernel Methods in Computational Biology -MIT Press, 2004, pp. 131-154.

63. Qiu J., Hue, M., Ben-Hur A., Vert J.-P., Noble W. S. A structural alignment kernel for protein structures //Bioinformatics: 23(9), 2007, pp. 1090-1098.

64. Sun L., Ji S., Ye J. Adaptive diffusion kernel learning from biological networks for protein function prediction //BMC Bioinformatics: 9,2008, 162.

65. Durbin, R., Eddy, S., Krogh, A., and Mitchison, G. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, 1998.

66. Cuturi M., Vert. J.-P. A mutual information kernel for sequences. Neural Networks // Proc. of IEEE Int. Joint Conference, 3,2004, pp. 1905-1910.

67. Cuturi, M. and Vert, J.-P. The context-tree kernel for strings // Neural Network, 2005.

68. Jaakkola, T. S., Diekhans, M., and Haussler, D. Using the Fisher kernel method to detect remote protein homologies // Proceedings of the Seventh International Conference on Intelligent Systems for Molecular Biology, 1999, pp. 149-158.

69. Vert, J.-P., Thurman, R., and Noble, W. S. Kernels for gene regulatory regions // Adv. Neural. Inform. Process Syst., 2006.

70. Tsuda, K., Kin, Т., and Asai K. Marginalized kernels for biological sequences //Bioinformatics, 2002, vol.18, pp. 268-275.

71. A. Chervonenkis, A.J. Gammerman, I.A. Shalimuradov and V.V. Solovyev. Sequence Alignment Kernel for recognition of promoter regions //Bioinformatics 19, 2003, pp. 1964-1971.

72. Rangwala H., Karypis G. Profile-based direct kernels for remote homology detection and fold recognition//Bioinformatics: 21(23), 2005, pp. 4239-4247.

73. Thome J.L., Kishino H., Felsenstein J. An evolutionary model for maximum likelihood alignment of DNA sequences //Journal of Molecular Evolution, 33, 1991, pp. 114-124.

74. Miklos I., Lunter G.A., Holmes I. A "long indel" model for evolutionary sequence alignment //Molecular Biology and Evolution: 21(3), 2004, pp. 529-540.

75. Miklos I., Novak A., Satija R., Lyngso R., Hein J. Stochastic models of sequence evolution including insertion-deletion events // Statistical methods in medical research: 29, 2008.

76. Metzler, D. Statistical alignment based on fragment insertion and deletion models // Bioinformatics; 19, 2003, pp. 490-499.

77. Seeger, M. Covariance kernels from bayesian generative models // Adv. Neural Inform. Process. Syst., volume 14,2002, pp. 905-912.

78. Duin R.P.W, De Ridder D., Tax D.M.J. Experiments with a featureless approach to pattern recognition//Pattern Recognition Letters, vol. 18, no. 11-13, 1997, pp. 1159-1166.

79. Mottl V.V., Sulimova V.V., Tatarchuk A.I. Multy-kernel approach to on-line signature verification // Proceedings of the Eighth IASTED International Conference on Signal and Image Processing, held August 14-16, 2006, Honolulu, Hawaii, USA, pp. 448-453

80. Айзерман M.A., Браверман Э.М., Розоноэр Л.И. Метод потенциальных функций в теории обучения машин. М.: Наука, 1970, 384 с.

81. Duin R.P.W, De Ridder D., Tax D.M.J. Featureless classification // Proceedings of the Workshop on Statistical Pattern Recognition, Prague, June 1997, pp.37-42.

82. Vapnik V. Statistical Learning Theory. John-Wiley & Sons, Inc. 1998.

83. Mercer T. Functions of positive and negative type and their connection with the theory of integral equations // Trans. London. Philos. Soc., 1999, A, 209, 415-416.

84. Моттль B.B. Метрические пространства, допускающие введение линейных операций и скалярного произведения. //ДАН, 2003, том 67, №1.

85. Berg С., Christensen J. and Ressel P. Harmonic analysis on semigroups: Theory of positive definite and related functions. Springer, 1984.

86. Vanschoenwinkel В., Manderic B. Substitution matrix based kernel functions for protein secondary structure prediction // Proceedings of the 2004 International Conference on Machine Learning and Applications. Decemberl6-18, 2004, pp. 388 396.

87. Wu F., Oslon В., Dobbs D., Honavar V. Comparing kernels for predicting protein binding sites from amino acid sequence //Newral Netwarks, 2006, IJCNN'OC, pp. 1612-1616.

88. Henikoff S., Henikoff J. Amino acid substitution matrices from protein blocks // Proc. Natl. Acad. Sci., 1992, 10915-10919.

89. Altschul S.F. The Statistics of Sequence Similarity Scores, http://www.ncbi.nlm.nih.gov/ BLAST/tutorial/Altschul-1 .html.

90. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. М.: Наука, 1974.

91. Gotoh О. An improved algorithm for matching biological sequences //Journal of Molecular Biology, 1982, pp. 705-708.

92. Attwood Т.К. The PRINTS database: a resource for identification of protein families. // Brief Bioinformatics, 3, 2002, pp. 252-263.

93. Rost B. at al. PHD-an automatic server for protein secondary structure prediction. // Computational applications in biosciences. 10, 1994, pp. 53-60.

94. Goebel U. at al. Correlated mutations and residue contacts in proteins. // Proteins, 18, 1994, pp. 309-317.

95. Шлезингер M. И. О самопроизвольном различении образов // Сб. Читающие автоматы Киев, Наукова думка, 1965.

96. Моттль В.В., Мучник И.Б. Скрытые марковские модели в структурном анализе сигналов М.: Физматлит, 1999, 352 с.

97. Ю4.Вапник B.H. Восстановление зависимостей по эмпирическим данным М.: Наука, 1979, 447 с.

98. Юб.Моттль B.B., Середин О.С., Красоткина О.В. Комбинирование потенциальных функций при восстановлении зависимостей по эмпирическим данным //Искусственный интеллект -2'2004, с. 134-139.

99. SVC 2004: First International Signature Verification Competition. URL: http://www.cs.ust.hk/ svc2004/index.html.

100. H.-W. Ji, Z.-H.Quan. Signature verification using wavelet transform and support vector machine. ICIC 2005, Springer-Verlag Berlin Heidelberg 2005, Part 1, LNCS 3644, pp.671-678.

101. Kaufman, L., Rousseeuw, P. J. Finding Groups in Data. Wiley, New York, 1990.

102. Mirkin B. Clustering for Data Mining: A Data Recovery Approach. Chapman and Hall/CRC, 2005.

103. Virus Database at University College London (VIDA). URL: http://www.biochem.ucl.ac.uk/ bsm/virusdatabase/VIDA3/VIDA.html

104. McGeoch, DJ, Rixon, FJ, and Davison, AJ: Topics in herpesvirus genomics and evolution // Virus Research 2006, 117, pp. 90-104.

105. Smith TF, Waterman MS. Identification of Common Molecular Subsequence //Journal of Molecular Biology, 147: 1981, pp. 195-197.

106. Altschul SF, Gish W, Miller W, Myers EW, Lipman DJ. Basic local alignment search tool //Journal of Molecular Biology 215 (3): 1990, pp. 403^10.