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

Сулимова, Валентина Вячеславовна

автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Потенциальные функции для анализа сигналов и символьных последовательностей разной длины

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

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

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

ООЭ47ВЗЗВ

На правах рукописи

Сулимова Валентина Вячеславовна

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

Специальность 05.13.17 - Теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискаиие ученой степени кандидата физико-математических наук

Москва 2009

1 ^ О ИТ

003479936

Работа выполнена а Тульском государственном университете на кафедре автоматики и телемеханики

Научный руководитель

доктор технических наук, профессор Вадим Вячеславович Моттль Официальные оппоненты

доктор физико-математических наук Михаил Николаевич Устинин, доктор технических наук, профессор Леонид Моисеевич Местецкий

Ведущая организация Институт проблем управления РАН

Защита диссертации состоится « 29 » октября 2009 г. в 13 ч. на заседании диссертационного совета Д 002.017.02 в учреждении Российской академии наук Вычислительный центр им. АА. Дородницына РАН по адресу: 119333, г.Москва, ул. Вавилова, 40.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

Автореферат разослан « 29 » сентября 2009 г.

Ученый секретарь диссертационного совета доктор физико-математических наук

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Сигналы и символьные последовательности являются наиболее распространенными видами организации данных. Широко известны такие задачи, как задача распознавания подписей по их динамическим характеристикам (on-line signatures), речевых команд и слитной речи, биологических свойств и пространственной структуры полимерных молекул белков по составляющим их последовательностям над алфавитом двадцати существующих в природе аминокислот.

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

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

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

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

Что же касается символьных последовательностей, то подавляющее большинство публикаций на эту тему ориентировано на анализ биологических полимеров, в частности, аминокислотных последовательностей белков. Именно этот вид символьных последовательностей находится в центре внимания в данной диссертации. В современной биохимии общепринятым способом измерения сходства аминокислот являются подстано-во,чные матрицы РАМ (Point Accepted Mutation) и BLOSUM (BLock Substitution Matrix), которые в традиционной форме не являются потенциальными функциями. С этой точки зрения соответствующие способы построения потенциальных функций на множествах символьных последовательностей разной длины являются эвристическими.

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

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

Кроме того, несмотря на то, что дискретные сигналы и символьные последовательности имеют похожую структуру, в настоящее время не существует единого математического аппарата для их сравнения. Единственный корректный способ построения потенциальных функций на множестве сигналов разной длительности, предложенный французским ученым Ж.-Ф. Вертом, имеет ряд неестественных ограничений, дополнительно введенных по сравнению с аналогичным подходом, разработанным для символьных последовательностей.

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

Для разрешения первой проблемной ситуации относительно аминокислотных последовательностей белков в диссертации используется тот факт, что обе общепринятые меры сходства аминокислот, как РАМ, так и ВЬОЭиМ, численно выражают правдоподобие гипотезы об общем происхождении двух указанных аминокислот от одной неизвестной аминокислоты в результате двух независимых шагов эволюции. Такая двухместная функция на алфавите аминокислот всегда является потенциальной функцией по своей структуре. Практически используемые подстановочные матрицы РАМ и ВШБиМ не являются положительно определенными только в силу логарифмического представления результата, к тому же округленного до целого значения.

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

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

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

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

Задачи исследования. Для достижения поставленной цели в диссертации сформулированы и решены следующие задачи:

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

2. Построение потенциальных функций на множестве аминокислот на основе модели эволюции М. Дэйхофф.

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

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

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

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

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

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

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

Положения, выносимые на защиту

1. Семейство потенциальных функций на алфавите аминокислот, выражающее смысл общепринятых подстановочных матриц РАМ и ВШБиМ.

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-1000014-6563.

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

Апробация работы. Основные положения и результаты диссертации докладывались на конференциях: «Математические методы распознавания образов» (Пущино, 2003 г., Звенигород, 2005 г., Зеленогорск 2007 г.), «Распознавание образов и анализ изображений» (Санкт-Петербург, 2004), «Интеллектуализация обработки информации» (Алушта, Крым, 2004, 2006, 2008 гг.), «Обработка сигналов и изображений» (IASTED SIP-2006, Гонолулу, Гавайи, 2006 г.), «Международная конференция по распознаванию образов» (ICPR-2008, Флорида, США, 2008 г.), на семинарах партнеров по гранту INTAS «Принципы распознавания сигналов, символьных последовательностей и изображений на основе измерения их несходства» в Москве (2005 г.), в Гилдфорде, Великобритания (2005 г.), в Праге, Чехия (2006 г.) и Киеве, Украина (2007 г.), на семинаре по анализу данных, Биркбек колледж, Лондон, Великобритания, 2008 г., на Международном симпозиуме по исследованиям в области биоинформатики и ее приложениям ISBRA-2009, Флорида, США, 2009 г.

Публикации. По тематике исследований опубликовано 11 статей, в том числе 2 статьи в журналах, рекомендованных ВАК.

Структура и объем работы. Диссертация состоит из введения, 5 глав, основных выводов и списка литературы. Материал изложен на 121 страницах, содержит 22 рисунка, 6 таблиц и список литературы из 118 наименований.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

Во второй главе рассмотрены пути введения потенциальных функций на множестве примитивов те А, из которых формируются последовательности со = (ш,, / = 1,...,jV) .

Для случая сигналов, элементами которых являются, как правило, векторы действительных чисел ш, = х, = (х]-х?)Т е А = R", простейший путь введения потенциальной функции в R" основан на использовании естественных линейных операций в конечномерном линейном пространстве примитивов и полностью исчерпывается множеством скалярных произведений ц(ю',со") = ц(х',х") = x'rQx" в R", где Q - любая невырожденная матрица.

Однако так определенная потенциальная функция не является мерой сходства векторов х',х"е R", под которой естественно понимать некоторую величину, монотонно убывающую с увеличением евклидова расстояния p(x',x") = x,rQx'+ x"rQx* - 2x'rQx". Таким свойством обладают так называемые радиальные потенциальные функции1 ц(х',х*) = ехр(-ур2(х',х*)).

Пути введения потенциальных функций на множестве примитивов символьных последовательностей рассматриваются в данной диссертации только применительно к аминокислотным последовательностям белков, т.е. последовательностям над алфавитом аминокислот А = {а',...,ат), га = 20.

В качестве теоретической концепции сравнения аминокислот в диссертации принята вероятностная модель эволюции Маргарет Дэйхофф, называемая РАМ . Ее основным математическим понятием является понятие марковской цепи эволюции аминокислот в отдельно взятой точке цепи, определяемой матрицей переходных вероятностей 4* = (чКсс71 а1)) превращения аминокислоты а' в аминокислоту а' на следующем шаге эволюции. При этом предполагается, что эта марковская цепь представляет собой эрго-дический и обратимый случайный процесс, т.е. процесс, характеризующийся финальным распределением вероятностей 1«') = и удовлетворяющий условию

обратимости ¡,(а')ц1(а' | ос') = ¡;(aJ)i(/(a' | а').

Марковский процесс эволюции, наблюдаемый с любым шагом s, также является марковским процессом. Этот процесс определяется многошаговой матрицей Ч^,, =Ч'х...хЧ'

s

переходных вероятностей.

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

2 DayhoffM.O., Schwartz R.M., Orcutt B.C. A model for evolutionary change in proteins. In: Atlas for Protein Sequence and Struc-

ture (M.O. Dayhoff, ed.X 1978, Vol. 5, pp. 345-352.

Теорема 1. Двухместная функция над алфавитом аминокислот и нормированная на финальные вероятности функция

Д1„(а',аО = Ц„|(а',ау)/4(а,'Жа/) = Ч'11,(а/ |а')/$(«') = У,„(а' |ау )/«<*') (2)

являются потенциальными функциями для любой степени 5.

Утверждение этой теоремы используется в диссертации для математической интерпретации широко используемой в биоинформатике серии подстановочных матриц РАМ с разным значением эволюционного шага у, которые изначально имеют ту же структуру, что и функция {^(а'.а/), но используются традиционно в логарифмической форме

= 101од|0 Дм(а',ау) с последующим округлением до целых, что приводит к неизбежной потере свойств потенциальной функции.

В последующих главах диссертации для измерения сходства аминокислот используются именно исходные значения ^(а'.а') и ¡1и(а',а').

Обладая свойствами потенциальной функции на алфавите аминокислот А = {а',...,а'"}, т = 20, каждая из мер сходства ц|>|(а',а'') или ци(а',а') погружает его в гипотетическое двадцатимерное линейное пространство Д А. В качестве полного линейно независимого базиса удобно принять сам исходный алфавит, интерпретируемый как конечное подмножество точек. Совокупность, вообще говоря, воображаемых элементов линейного пространства а = естественно интерпретировать как некоторые «обобщенные» аминокислоты. В частности, если с' > 0 и = 1, то обобщенная аминокислота а имеет смысл вероятностной смеси реальных аминокислот с вектором вероятностей (с' ■ • • с™).

Еще один принципиально важный для современной биоинформатики результат, представленный во второй главе, касается соотношения двух наиболее популярных мер сходства аминокислот, выраженных семействами подстановочных матриц РАМ и ВЬОЭиМ.

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

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

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

Основная идея построения потенциальной функции

Пусть П есть множество всех конечных последовательностей со = (ю,, / = над

конечномерным линейным пространством примитивов со, е А. В частности, роль элементов последовательностей играют конечномерные векторы со, = х, = (х]---х")Т е А = А = К" в случае сигналов, и обобщенные аминокислоты е>, = а 1 = (с]---с")т е Ао> А в случае аминокислотных последовательностей.

Введем также специальные обозначения П„ = {ю = (со,, г = со, е А, N = л} для множества всех последовательностей длины п и Пг„ = {со = (<в„/ = 1,.со, еЛ^>п} для множества всех последовательностей длин не менее п.

Сходство двух последовательностей и'.о'еА будем оценивать значением правдоподобия гипотезы об их общем происхождении в результате двух независимых реализаций фиксированного случайного преобразования (ф„(са|Э), шеП) одной и той же неизвестной последовательности Э = (3,еД ; = 1,...,/г)еП„ей случайной конечной длины п с распределением г(л), играющей роль общего прототипа и случайно выбранной из конечномерного линейного пространства П„ с некоторым распределением (р„(Э), ЗеО„): £(«■»>•) = а(»)Ф.(«' 13)ф„(ш" 13)43. (3)

Теорема 2. При любом выборе распределения случайной длины общего прародителя г(п), семейства распределений {(р.(3), Э е П„), л = 1,2,...} и семейства условных распределений {(ф.(са 13), со е О), в е функция £(со',ш") является потенциальной функцией на £2.

Доказательство теоремы сводится к доказательству выполнения условий Мерсера1 и почти очевидно.

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

В качестве семейства случайных преобразований {(<?„(<» |3), юеП), ЭеП,} в диссертации рассматриваются только двухэтапные преобразования следующей структуры.

Этап 1. Всякая конечная последовательность непересекающихся интервалов

»1 Ч1

определяет структуру случайного преобразования последовательности-прародителя Э = (Э],...,Э>). Эту структуру будем называть односторонним выравниванием совокупности ее позиций (1,...,и) и позиций гипотетической формируемой последовательности (1,2,3,...). Счетное множество всех односторонних выравниваний будем обозначать Уп = {у = (у,,..., у,,)} , а распределение вероятностей на нем - <7„(у) > 0, V е К .

Этап 2. Для всякой структуры V е Уп определено случайное преобразование, зависящее от структуры г)„(га|Э,у)£0, причем г)„(ш|3,у) = 0 для всех последовательностей ш гПг(,

длины меньше у„, т.е [ г|„(ш|Эл) = 1. Таким образом, длина формируемой последовательности всегда оказывается больше или равной длине последовательности-прародителя, т.е. со е Пг„.

В итоге, случайное преобразование {(ф„(<о 13), ш е Ог„),3 еО„| есть смесь

Ф>|8) = ЕУ«и.?.Мт1>|Э,у). (5)

Ключевая и дополнительная подпоследовательности

Одностороннее выравнивание (4), определяющее структуру случайного преобразования последовательности-прародителя Э = (31,1 = 1,...,и)еА|1 в последовательность не меньшей длины о = (е>„/ = 1,...,Л^)еПг„, понимается как прямое перечисление интервалов V = в которые будут отображаться элементы (Э,,...,Э„) исходной последователь-

ности (рис. 1). Совокупность соответствующих фрагментов (»„ = (0^ ,.~,е>5) в формируемой последовательности ш= = будем называть ключевой подпоследовательностью ш„ = (т„, 1 = 1,..., и) в составе результирующей последовательности. Ключевая подпоследовательность может иметь любую длину, поскольку интервалы у, могут быть,

1 Mcrcer 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.

вообще говоря, сколь угодно длинными, т.е. ш, е П. Совокупность остальных позиций будем называть дополнительной подпоследовательностью «в, =(а>„/ = г г V,, / = 1 которая также может иметь любую длину Шу е Г!. Последовательность в целом есть объединение ключевой и дополнительной подпоследовательностей ю = ш„ и®, •

• — ключевая 01

подпоследовательность ( б )

О — дополнительная ^

подпоследовательность (¡я) / // / \ \\\\ о"

Ш "Г Ъ < К

Рисунок 1 - Структура преобразования последовательностей

Независимость ключевой подпоследовательности от дополнительной

Случайное преобразование г|п(<в|3,у), зависящее от структуры, построим как комбинацию двух независимых распределений вероятностей:

П„(а> 13,у) = п„(й„ 13,у)п(ш.), (6)

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

Независимость элементов последовательности-прародителя

В данной работе распределение (р„(3), в е П„) на множестве вариантов последовательности-прототипа Э = (9,е Д| = 1,...,л)еП„сП принятой длины п рассматривается как совокупность одинаковых независимых распределений ее элементов ¡;(9):

Аналогично, будем полагать, что для всех интервалов Т, в составе выравнивания у = (у1,...,у„) определены независимые элементарные случайные преобразования (тц((а„ еП^) исходного элемента Э, в соответствующий фрагмент формируемой

последовательности юи= (и. ,...,со_) длины | V, |. Соответственно, ключевая подпоследовательность фрагментов формируемой последовательности ¡3, = (<о„/ = 1,...,л) образована совокупностью таких независимых распределений

П.(»,|в.*) = ПнЧ,(®,1»1)- (8)

В свою очередь, каждое из этих преобразований представляет собой совокупность независимых одинаковых условных распределений ч'(й), 19,) :

= (9)

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

Каждая пара односторонних выравниваний у'=(у,\/ = 1,...,л)еК„ и у" =

(у",/ = 1.....п)еУ„ порядка п, определяющих структуры преобразований и в-хо",

Э е , со',и' б Пг„ определяет сквозное парное выравнивание того же порядка:

3.....ш

Наоборот, выравнивание те определяет пару односторонних выравниваний Множество парных выравниваний порядка п есть декартово произведение = Упу.Уя. Распределение вероятностей дп{\) на У„ образует распределение на \¥г:

9.М=ЯЛ<)ялу:)- (Ю)

Необходимо отметить, что не любые парные выравнивания могут определить пару последовательностей ш' и т" длин Ы' и М", а только такие, которые удовлетворяют условиям „ < Л" и у'„ < Ы". Множество таких допустимых парных выравниваний будем обозначать 1УвЮГ с IV». Распределение вероятностей на множестве допустимых выравниваний определим как

где, г(х) -распределение вероятностей длины заключительной части генерируемой последовательности, удовлетворяющее обычным требованиям г(т)^0, = ' иопРе" деляющее длину формируемой последовательности через длину ее заключительной части (Л^-у,,).

В терминах множества парных выравниваний и с учетом предположений (7)-(9) общая структура потенциальной функции (3) запишется в виде:

**»>■>=ХХ«)!^ | (1 о

где Ф(Ш>'М = !р^)гр:.) ЦПм^ПХ4^ 1^(П^КI- совместная плотность вероятности появления пары сравниваемых последовательностей, условная относительно парного выравнивания и-.

Конкретный вид потенциальной функции определяют, во-первых, распределение вероятностей г(л) на множестве значений длины последовательности-прародителя, во-вторых, распределение д„(у) на множестве односторонних выравниваний У„, определяющее распределение чп(у) и, в-третьих, элементарные распределения р,), ч/(со|Э) и 4(3). В дальнейшем, данные распределения г|(ш„), у(са 13) и ¡;(Э) будут отличаться для сигналов и символьных последовательностей. Этим и будет определяться различие между соответствующими двумя видами потенциальных функций.

Может оказаться целесообразным нормировать функции |■№) на произведе-

ние полных условных плотностей, получая нормированную потенциальную функцию:

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

Потенциальные функции фиксированного порядка п являются очень важным частным случаем функций (11) и (12), впервые предложенным в данной работе. Они могут быть получены путем такого выбора распределения г(п), что г(п) = 1 и г(к) = 0 для любых кФп. Такой выбор распределения г(п) означает предположение о том, что последовательность-прародитель 8 имела длину и. В этом случае потенциальная функция (11) будет иметь вид:

£>>") = Х,^,,.?„л,Л>У)Ф(ш;,.,Ш:. |уу)

В случае же, если нет основания для введения каких-либо предположений относительно длины скрытой последовательности-прародителя, то естественно в качестве рас-

9„(w) = Я.

*! ) (Ч ,K т у, J.....U" x

пределения r{n) выбрать несобственное «равномерное» распределение r(n) = const. В этом случае потенциальная функция (11) будет иметь вид:

К(а.',и') = YIX»^,,.I w)

Такая функция названа в данной работе потенциальной функцией абсолютно нефиксированного порядка.

Потенциальная функция называется локальной, если в сравнении пары последовательностей участвуют только их центральные части. Это означает, прежде всего, что распределение на множестве выравниваний <у„(w) полностью инвариантно к совместным сдвигам ключевых элементов

+ Д', v| + Д' 1 ( К + + Д'

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

z(t) пршшмается несобственное «равномерное» распределение Ц(ШУ)~ const и г(т) = const.

Потенциальная функция называется глобальной, если относительно распределения на множестве выравниваний i?„(w) не делается никаких специальных предположений и распределение не является безразличным:

где е А — некоторое распределение на множестве примитивов.

Для символьных последовательностей в данной работе рассматриваются как глобальные, так и локальные потенциальные функции в их нормированной форме, а также потенциальные функции фиксированного порядка. Во всех случаях распределение вероятностей g„(v) выберем таким образом, чтобы выполнялось условие: <7„(v)*0 только для таких односторонних выравниваний (4), для которых начало и конец каждого интервала v(, 1 = 1,...,л совпадают, т.е. v( =v,. =vf. Таким образом, одностороннее выравнивание, определяющее структуру случайного преобразования последовательности-прародителя 8 = (Э„< = 1,...,л)еП, в последовательность не меньшей длины ш = (о„/ = 1,...,//)бПг„, понимается как прямое перечисление позиций v = (v,,...,v„), в которые будут отображаться элементы исходной последовательности (рис. 2).

В главе 2 линейное пространство примитивов А, образующих символьные последовательности, рассмотрено как натянутое на исходный конечный алфавит Ас А. Распределение (/j„(8),SeQn) (7) на множестве вариантов последовательности-прототипа S=(3,6 А,

¡ = 1.....л)ей,£й принятой длины п в случае символьных последовательностей будем

рассматривать в пределах конечного алфавита символов ЗеЛсА, т.е. 4(9) = 0 при Э еЛ\А.

Ц удаления

V ™7Я \ У В OOOfOtOOIIOOf оо

подпоследовательность (а) \ \ / / У I I

5 W / замены

О-дополнительная У У / \\ I J У I/

подпоследовательность (w) , У У / \ \ са",0,* *,0, , 0 ,

v ' <0 0 • • О • О О О • О • О О V V r-> V "-<-'

i «i 'i У. вставки

Рисунок 2 — Структура преобразования символьных последовательностей

В частности, в качестве многократно повторяемых в выражении (11) распределений £(3) будем использовать финальное распределение в модели эволюции Дэйхофф, а в качестве условных распределений IЭ) - распределения, определяемые матрицей переходных вероятностей М. Дэйхофф превращения аминокислоты а' = 9 в аминокислоту а1 = т.

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

Нормированная глобальная потенциальная функция нефиксированного порядка на множестве символьных последовательностей имеет вид:

=WWII'«*., К.Ч.). (14>

где дм(ш",со') - потенциальная функция на множестве аминокислот (2) для шага эволюции s.

Нормированная локальная потенциальная функция нефиксированного порядка на множестве символьных последовательностей имеет вид:

(ь-)

Локальная потенциальная функция фиксированного порядка на множестве символьных последовательностей имеет вид:

А^^зи^мшы^к. к.) о6)

Для сигналов в данной работе рассматриваются только глобальные нормированные потенциальные функции. При той же формальной структуре одностороннего выравнивания, что и для символьных последовательностей v = (v„...,v„) (4), распределение вероятностей <7„(v) будем задавать так, чтобы с вероятностью 1 оно определяло полную сегментацию оси формируемого сигнала на я интервалов: v, =1, г> =vM+l, i = \,...,n.

При таком выборе распределения q„(y) формируемый сигнал о>=(ш„/ = 1,...,Лг) еПг„ полностью совпадает с ключевой последовательностью, состоящей из и сегментов to=5v =(ш ,/=1,...,л), в то время как дополнительная подпоследовательность всегда будет

пустой ¿5„ е П0. Соответственно, распределение т)(Ш„) теряет смысл, т.е. т[(ш,) = 1 для

Далее, поскольку сигналы, как правило, образованы последовательностями конечномерных векторов (о1 = х,=(х!-"х"')геЯт, то естественно выбрать распределение 4(3) в составе (11) и (13) в классе нормальных распределений с нулевым математическим ожиданием и независимыми идентичными компонентами:

5(3) = «у) = ^(у|0,ст21). (17)

Аналогично, условное распределение у(со 13) выберем в виде нормальной линейной модели

Ч/(а1Э) = Ч/(х|у) = ЛГ(х|у16г1). (18)

С учетом предположений (17) и (18) нормированная глобальная потенциальная функция нефиксированного порядка примет вид:

Й(ш>') = |>(и) X 9,(*)П(1/Л^(*и0,(а2 у^«'!). (19)

где =(х'.. и =(х* .....х^ )е - соответствующие фрагменты двух

сигналов, выделяемые/-И позицией парного выравнивания те, Шц ^ =(шуК( )-

К»1Р»

математическое ожидание появления фрагмента , условное относительно исходного фрагмента и Ук.1=1/(1/°2+К»1/5г) - Дисперсия апостериорного распределения /-го элемента неизвестного прародителя у(, относительно соответствующего фрагмента исходного сигнала %1ч.

Для сигналов естественно принять о2 ю, причем в этом случае только нормированная потенциальная функция имеет смысл.

Алгоритмы вычисления потенциальных функций рассмотрены в диссертации только для специального класса распределений вероятностей на множестве парных выравниваний д„(те), который, в то же время, является достаточно широким для практических приложений. Распределение д.(у*) = дт(у')д„(у") естественно выбирать зависящим только от длин локальных трансформаций осей сравниваемых последовательностей (удалений-вставок для символьных последовательностей или растяжений-сжатий для сигналов). Типичным является предположение, что случайные длины этих трансформаций являются независимыми, и имеют распределения вероятностей, монотонно убывающие с увеличением длины:

М,=1.

& М I а,Ь)к

ехр[-р(а + М;)], </, > 1, ^

где 40=^, = V. - у,.,, = = А^-V, - для символьных последовательностей и,

4 =у, -V, +1, ¿ = 1 ,...,п —для сигналов.

При этом если а = 0, то «стоимость» двух локальных трансформаций длин й, и с1] будет равна «стоимости» одной трансформации суммарной длины d¡ + dJ. Если же а >0, то один длинная трансформация будет более предпочтительной, чем несколько коротких, имеющих в сумме ту же длину.

Распределение <?„ (у) , определяющее <?„(\у) отличается для локальных и глобальных потенциальных функций. Так, для локальных потенциальных функций учитываются только трансформации в средней части <?„(у)сс]^^£Ц(у)| л,4), тогда как при глобальном сравнении учитываются все трансформации: д„(у) I а>Ь) ■

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

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

Пусть А - множество аминокислот и ш = {ш^ = (о/, еЛ,/ = 1,...,Л?у),} = 1,...,М} - анализируемая совокупность последовательностей. Основная гипотеза состоит в том, что все белки £5 получены независимо из некоторой общей аминокислотной последовательно-

сти-прародителя 3 = (3,,i = l,...,>;) известной длины л путем описанного в главе 3 моделью случайного преобразования. При этом предполагается, что элементы 9; были выбраны из алфавита аминокислот А независимо в соответствии с неизвестными наблюдателю распределениями вероятностей ß, = фл,к = \,...,т), 0 < ß^ < 1, Совокупность таких распределений ß = (ß,,...,ß„) соответствует принятому в биоинформатике понятию профиля последовательности. С учетом случайности выбора S функция правдоподобия для одного белка будет иметь вид:

4<ffl|P)«Z^9Mn.(®lß.v), где n.(«lß,v) = rLZ:,P.V«4. I«W)

Задачу поиска общего прародителя поставим как задачу оценивания последовательности распределений р = (Pi»-..,P„) по всей совокупности белков ш. Оценку будем производить максимизируя соответствующую функцию правдоподобия F(m \ ß):

f = arg max F(S | ß) = arg maxf]" <p(© s \ ß) = arg max Z", In (Z,^ 1«. (v)l- К ¡P.v))

В основу решения данной задачи положена итерационная EM-процедура, впервые предложенная М.И. Шлезингером в 1965 году, которая применима к широкому классу функций правдоподобия для вероятностных моделей со скрытыми параметрами. В данном случае в качестве такого скрытого параметра выступает выравнивание v.

Пусть на 5-м шаге получено приближение к искомому профилю последовательности-

прародителя ß* = (ß'.....ßü) и пусть найдено апостериорное распределение на множестве

выравниваний у-го белка p(v|oj;,ß'), vs^, в предположении, что ß' - истинный профиль исходной последовательности. Выберем ß"' по правилу:

ß"' = argmax£^£ve4p(v|o,,ß')ln^, |М (21)

Теорема 3. При определении ß"' в соответствии с (21) справедливо неравенство •F(ä|ß'+,)>F(ö|ß'), причем F(S|ß'+,) = F(S|ß') тогда и только тогда, когда Vp F((a I ß') = 0 для всех элементов прародителя i -1л.

Теорема 4. Задача (21) эквивалентна совокупности независимых задач для отдельных элементов профиля

РГ' = argmaxX",A(ß\ö)lnX:_,ß*v(a<01 а«>), где A,(ß\c>,) = ZÄ AF,*j) (22)

На.-А. »,«">

и p"(p',<aj) — апостериорная вероятность того, что i-й элемент последовательности-прародителя преобразуется в t-ю позицию j-го белка.

Решение задачи (22) очевидно. Компоненты элемента профиля ß'+' = (ß"1,~=ß£') являются решением системы линейных алгебраических уравнений с матрицей условных вероятностей эволюционного чередований аминокислот: Z:,[v(a(,,|a(i>)>;' =«„ / = и,«, Щ,

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

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

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

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

Пусть Q - множество всех объектов некоторой природы. В терминах потенциальной функции К(т',ш"), определенной на множестве объектов О' = {о>у,_/ = 1....Л/} с П и погружающей его в линейное пространство ПзПэй', решающее правило метода опорных векторов В.Н. Вапника для классификации объектов на два класса g = +l и g = -l может быть представлено в виде разделяющей гиперплоскости

y(e>)=W,m)+b>0->g = l y(e>)<0-+g = -l, (23)

полностью определяемой направляющем элементом ЭеП и смещением beR.

Направляющий элемент оптимальной разделяющей гиперплоскости может быть найден как линейная комбинация S = Х/х^о^А/01/ объектов обучающей совокупности с

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

Выбор смещения beR может быть осуществлен по-разному для обеспечения симметричного или несимметричного положения гиперплоскости и не представляет проблемы.

Распознавание по нескольким потенциальным функциям

В данной работе применяется принцип комбинирования потенциальных функций, идея которого впервые была предложена Мотглем В.В., Серединым O.G. и Красоткиной О.В1, а затем существенно развита А.И. Татарчуком и В.В. Мотглем. Данный подход позволяет автоматически в процессе адаптивного обучения выбирать потенциальную функцию, наиболее адекватную данным учителя.

Пусть К,(со',оз*), / = 1,...,п -потенциальные функции, определенные на множестве объектов о е П. Каждая из них погружает множество i2 в гипотетическое линейное пространство flcfip i = l,...,n. Удобно рассматривать их совместно как декартово произведение О = П, х...х = {5 =< со,,...,шя >: со,, e Ö,}. При этом решающее правило в комбинированном линейном пространстве Q удобно искать в виде:

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

«Л>у oIti}>oX.(»j-»№! (25)

На каждой итерации к коэффициенты находятся как решение задачи

обучения, имеющей структуру, аналогичную (24):

S^&i: (26)

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

Определение константы Ьк на каждой итерации не представляет сложности. Как правило, процесс сходится за 10-15 шагов.

Метод к -средних для автоматической классификации объектов на к классов

Пусть П =^(OjJ = 1,...,М} - множество объектов, которые необходимо разбить на к непересекающихся подмножеств П* ^фип^и.-.ис^, П'ПП," = 0, /',/ = 1,

Любая потенциальная функция К(ш',ш"), определенная на О* , погружает его в линейное пространство Осйсй'севклидовой метрикой

р:(ю',ю") = А'(оУ,ш') + К(т",(й")-2К(а',а ), о'ш'еП". (27)

Итерационная процедура метода к -средних заключается в поочередном выполнении на каждой (л +1) -й итерации двух шагов:

1) нахождение к фиксированных абстрактных центров по имеющемуся разбиению (П*с*>, I = 1,...,А:} по правилу Зр'=аг§гшп^] р2(со,,Э), что, с учетом (27) и

свойств дифференциала Фреше, позволяет найти явное выражение для центров

2) нахождение нового разбиения по найденным на данной итерации центрам:

п;(""= р2(м,,э;+1) = тт р2(са, ,Э,"')|,(=\,...,к. (28)

С учетом (27) и линейности К(<о',ш") относительно операции сложения, можно записать:

(29)

что, при подстановке в (28), позволяет избежать непосредственного вычисления абстрактных центров, минуя таким образом шаг 1. Критерием окончания итерационного процесса может служить стабилизация классификации.

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

На каждой /' -й итерации найдем реальный объект, максимально удаленный от центра

данных ф = (1/|П'|)^л'1(в;, феП: с, = ш^тах(р2(сояф)), причем с учетом (29) с, может

»,¿-1. м

быть найден без непосредственного вычисления абстрактного центра ф. К /-му классу будем относить объекты по правилу: П,'= {со^еП*:р2(шу,с,)<р2(о)у,ф),_/=1,...,|П"|}. Выделенные объекты временно удаляются из исходного множества П'=П'\П' и процесс повторяется без смены центра ф. В результате получаем разбиение {Ц",/ = 1,которое принимается в качестве начального приближения для метода к -средних. Анализ аминокислотных последовательностей

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

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

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

В данной работе приводится пример, когда другой частный случай, а именно, глобальная потенциальная функция нефиксированного порядка (14) дает лучшие результаты по сравнению с локальной потенциальной функцией (15).

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

В качестве базы для экспериментального исследования использовались аминокислотные последовательности вирусов простого герпеса из базы данных VIDA1, разделенные на три класса на основе анализа эволюции вирусов герпеса2. Данная классификация и результаты, полученные с использованием четырех различных мер сходства приведены на рисунке 4.

Классификация на основе

анализа эволюции вирусов герпеса2

Результат классификации

класс 1 (109 белков) функция glycoprotein H (семейства 12,42 и 531 >

класс 2 (76 белков) •ункция glycoprotein L :ем-ва 47, 50,114,296)

[ " зо......it. fffsgrai

класс 3 (48 белков) функция glycoprotein M (семейство 20)

Кластер 1 Кластер 2 Кластер 3 Кластер 4 Кластер 5 Кластер 6

1 52 II IS I 1 39 1 1 30 1 1 3, 1 Ы1 Г ' 48 ' i

Кластер 1 Кластер 2 Кластер 3 Кластер 4

1 50 I1151 1 39 HIB 1 30 II 31 II »11 1 • « И

1 Кластер 1 Кластер 2 Кластер 3 Кластер 4 Кластер 5

Il 52 ПП 1 39 1 1 30 II 31 In II |.23 1 1 25 1

1 Кластер 1 Кластер 2 Кластер 3

Il 52 И 39 |[ It] 1 30 II 30 -Il M II 1 « il

не вероятностной локальной меры BLAST3 (не ПФ)

не вероятностной глобальной меры Нидлмана-Вунша4 (не ПФ)

вероятностной локальной ПФ (14)

вероятностной глобальной ПФ (15) |

Рисунок 4 - Классификации белков на основе анализа эволюции вирусов герпеса и результаты

автоматической классификации

Из рисунка 4 видно, что только глобальная вероятностная потенциальная функция позволяет объединить в один класс белки, выполняющие одну и ту же функцию.

Поиск общего прародителя группы последовательностей

Эксперименты по исследованию процедуры поиска общего прародителя проводились на модельных и реальных данных. В приведенном на рис. 5 примере данные генерировались по следующей схеме. 1) Случайным образом была сгенерирована последовательность-прародитель длиной и = 20: S = (WFCNLPKALIVWPCNQIMAG). 2) На основе 9 были

сгенерированы анализируемые последовательности e>j,j = l.....30 путем добавления слева,

в центр и справа случайных последовательностей случайной длины.

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

1 Virus Database at University College London, http://www.biochem.ucl.ac.uk/ bsm/virus_database/VIDA3/VIDA.htmI

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

1 Allschul SF, Gish W, Miller W, Myers EW, Lipman DJ. Basic local alignment search tool. J Mol Biol 215 (3), 1990, pp. 403-410.

4 Needleman SB, Wunsch CD. A general method applicable to the search for similarities in the amino acid sequence of two proteins. J Mo! Biol 48 (3), 1970, pp. 443-530.

последовательности со,,у = 1,...,30 получены из него путем независимых случайных преобразований (5). Для полученного в данном случае вероятностного профиля характерно, что в каждой позиции 1 = 1 одна из аминокислот имеет вероятность, равную единице или близкую к ней. В связи с этим результат поиска общего прародителя может быть выражен буквально в виде последовательности ¿ = ^РСЫЬРКАЬ1У\\ФСЫС)1МАС), которая в данном случае абсолютно точно совпала с истинной последовательностью-прародителем О.

FPO «NtVtEHMFI \/ТН££

Т N KCCOSWE RSr«LC «пед LFP

o N\A^N»G<;HPTKVI.V.vc С О

WU?« хзм< S «"SDMLTTPFMGWVUO WT

fÑP

í.riH |'АА,Лр RíMsYT

VHYWiríWI САП« FTí F KNEVVSP YTHNAY DECR ©KWc FvbRETtJYKT'D

er f:;st cwíksa DGIEGÍ'FIGCVCG» <T 3MLF GSDQRGEHRIIRSNFTHC EKl.FVNOAAGND С DTIFAE D Wt.yVP LW С LSTASVMAvVF G PiGPLPClMWJTY

HPS

VI WLL OH F' PMAADF CV M И N WDT fiS

CNLFKAll V\f CNLPKA.I vvr с M Í.PKAÍJ CNÍ.PKAÍJ

vw сы и-чсли WFCNJ404.I V/FCNlPK/i.l W CN UPXALi WF CNLPCAU WFCN LPKAíJ WF С NI ¿.РКЛ .1 WF Chk.PKA.I WFCNí.PKAU

CN ■ Pk'A ( V\f С N L PKAí. ¡ WCN^KA-i WFCNLPKAU WFCN;.PK*¿.¡ WfCNLPfcAJ WF CNLPKAU WFCNUPKAÉJ WF CN .ЯКЛ.1 WF CN LPKAL' W CN LPKALf

CN LPKAU wfcnlpka:.!

WCNJ'iíA.I V6F С N LPKAL' WF CNLPKAÜ

V Vr-SN FMFVR 1f WMW «CYS

F G NR NID MWO T rV:Y KOF'F-HCROtvííS fíOl^S KfífFVt-: О Г Y YO lEENlE» KXVF PKFiO AS/«: PMMYPRC I fCCT'CNV MISGWNVPHB2.AECS MVfeO LCWDNPF KtVIvVK

KIGVLNWHS FNOPEEL VYYW AMOLAS И Г.МГ >F ÍÑM VT» МГ НРЛ<!!5ГГ FH k'YPA^UP

.WSeRRCt, MAfSWO JKH SOCLEPH FHKPFOWM ;HSRY HWKPVSL LAMHT ÍHIYSH TI

WHL3TCFSGW

w-1 -VWP i

W№¡ WP!

WPi

VWP;

VWPS

'vW;

>avp:

vWP; vWP; v/WPi ■■AVpi

4/WP:

VWP: W^P:

VWP:

V'WP:

Y\VP: v\VP: VWPí VWP i VWP W-/P vWP

VWP!

V.VP:

MvCHVIAG ГЛ<е©ИМАО

"noiíhag ;ko¡mag

5NOSMA© 2NQÍMAC SNGilMAG 5 NO ¡MAC 2NOIMA& ÍNOJM/aG ÍKíOIMAÍ? :: noü/AG

".K^JIMAA -ÍNQIVJAR ^NOÍMAO ÜNOIMAG :ivO!MAG L-NOJMAG ^"NQliVlAG lítvOSíHAG Г-NOÍMAG SIVSGÍMAG DKOfMAG 2NGÍM1AG

^KYSfMAG

KDSVKOD МТт^РЯТРЧТ GG

NOtYRfRLESTF OWKMCTTTI IR MVriCK SLVVt/AÜOGOQCY-CLC L"iNL

invsmsm;o

С H4A.SEi.CP COWITVI © №. we KHPkí-ífvDGS LLM'W'-ÍCA V T P PQHNTGEYkKWI-X- ЕС MF VCAING EYAY-SSSSM

N3

MAOKMY1TL C_AMLSI"'AHO (DlEHAí MYFFP H-JYHCKYUMC SÉRLYJMCG HF WND Eíít VG HMACLYT CS GTTSC OkM-íYPGSMCSDELW C-PM'SAD

LN

LH.W

найденный [—\ jjvv г- с n t р к ai i~] прародитель v

Рисунок 5 - Анализируемые последовательности и найденный общий прародитель

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

Рисунок 6 - Пространственные структуры белков 1ЬСК, 2Н8Н и ЮШ с выделенными на них найденными консервативными регионами

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

Каждая подпись вводится в компьютер непосредственно в процессе ее написания и оказывается представленной семикомпонентным дискретным сигналом ш = (х5,х=1,...,Л'), включающим такие компоненты, как координаты (X и У), угол наклона пера, угол поворота, усилие нажатия, скорость и ускорение (рис. 7).

я координата X координата У усилие нажатия поворот наклон

Рисунок 7 — Примеры подписей и их представления в виде многокомпонентных сигналов

Следует отметить, что формула (19) определяет целый класс потенциальных функций (ПФ) на множестве сигналов и априори не представляется возможным определить какая из них будет более адекватна данным учителя. В данном эксперименте используется 12 потенциальных функций (табл. 1), отличающихся друг от друга разными наборами компонент сигналов, учитываемых при сравнении и разными значениями параметра а = Ь (20), имеющего смысл штрафа на локальные растяжения и сжатия осей сравниваемых сигналов.

Таблица 1 - Множество используемых потенциальных функций (ПФ)

ПФ Подмножество компонент ПФ Подмножество компонент

а = 2 а = 4 а = 2 а = 4

к, координаты К* координаты, скорость, ускорение

к, углы наклона К9 координаты, углы наклона, усилие нажатия

к, <6 усилие нажатия К и все компоненты

В качестве базы для экспериментального исследования использовалась база Международного соревнования по верификации личности (8УС2004), содержащая 1600 подписей 40 человек, по 20 оригинальных подписей и 20 умышленных подделок для каждого человека. Данные для обучения и контроля для каждого автора приведены в таблице 2.

Таблица 2 - Данные для одного решающего правила

Обучающее множество Тестовое множество

5 оригинальных подписей 5 умышленных подделок 10x39 случайных подделок 15 оригинальных подписей 15 умышленных подделок 39 случайных подделок

Для каждого автора обучение и распознавание проводилось 13 раз: для каждой из потенциальных функций К) - Кп в соответствии с (24) и для комбинирования (25-26). В таблице 3 представлены результаты верификации. Из таблицы 3 видно, что процент ошибок, полученный с использованием комбинирования потенциальных функций, оказался меньше, чем для любой из потенциальных функций отдельно.

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

Таблица 3 - Результаты верификации личности по подписи

ПФ Ошибка, % Адекватна для* ПФ Ошибка,% Адекватна для* ПФ Ошибка,% Адекватна для*

0.65 6 человек К5 2.75 0 человек К, 0.58 6 человек

к, 1.01 9 человек кь 2.50 4 человек 0.76 3 человек

к, 5.58 0 человек К, 0.98 4 человек к„ 0.47 5 человек

к, 7.50 0 человек К, 1.41 2 человек Кп 1.01 1 человек

Ошибка при комбинировании потенциальных функций К, - Кп: 036%

Количество человек, для которых соответствующая ПФ была выбрана в результате

комбинирования

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЯ

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

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

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

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

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

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

БЛАГОДАРНОСТИ

Автор выражает благодарность фонду INTAS за предоставленную возможность стажировки в Биркбек колледже Университета Лондона в рамках гранта INTAS YSF PhD Fellowship, проф. Б.Г.Миркину за руководство данной стажировкой и прикладную задачу по анализу аминокислотных последовательностей, профессорам университета Ратгерс, Нью-Джерси, И.Б. Мучнику и К.А.Куликовскому за консультации по вопросам анализа белковых данных и плодотворное сотрудничество, студенту МФТИ H.A. Разину за помощь в проведении экспериментальных исследований, коллективу кафедры ATM Тульского государственного университета во главе с зав.каф. проф. A.A. Фомичевым за создание условий для работы, родителей и мужа за поддержку и терпение и особенно своему научному руководителю д.т.н. проф. В.В. Мотглю за неоценимую помощь на всех стадиях выполнения работы.

СПИСОК ОСНОВНЫХ ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

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

2. Моттль В .В., Сулимова В.В. Идентификация личности по динамике подписи методом опорных векторов. Сборник трудов мезвдународной конференции ММТТ-16,2003г, том 4, с.219-222.

3. Моттль В.В., Середин О.С., Сулимова В.В. Формирование потенциальных функций для беспризнакового распознавания сигналов и символьных последовательностей. Известия ТулГУ. Серия. Вычислительная техника. Информационные технологии. Системы управления. Т1. Вып.2. Информационные технологии. - Тула: ТулГУ, 2004, стр. 11-16.

4. Моттль В.В., Середин О.С., Сулимова В.В. Потенциальные функции для беспризнакового восстановления зависимостей на множествах сигналов и символьных последовательностей. Искусственный интеллект, 2'2004, стр. 140-144.

5. V. Mottl, О. Seredin, V. Sulimova. Mathematically correct methods of similarity measurement on sets of signals and symbolic sequences of different length. Pattern Recognition and Image Analysis, Vol.15, No. 1,2005, pp. 87-89.

6. Моттль B.B., Сулимова B.B., Татарчук А.И. Автоматический выбор наиболее информативных фрагментов в задачах распознавания сигналов разной длительности. Таврический вестник математики и информатики - № 1, 2006, стр. 109-115.

7. Сулимова В.В., Разин НА., Моттль В.В., Мучник И.Б. Множественное выравнивание совокупности аминокислотных последовательностей на основе вероятностной модели эволюции. Таврический вестник математики и информатики N 2,2008, pp. 202210.

8. V. Mottl, М. Lange, V. Sulimova, A. Yermakov. Signature verification based on fusion of on-line and off-line kernels. Proc. of 19-th International conference on Pattern Recognition (ICPR 2008), Florida, USA, December 2008.

9. Sulimova V., Mottl V., Kulikowski C., Muchnik I. Probabilistic evolutionary model for substitution matrices of РАМ and BLOSUM families. DIMACS Technical Report 2008-16, Rutgers University, 17 p., 2008.

ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2008/2008-16.pdf

10. Mirkin В., Sulimova V. Mottl V. Is protein sequence data sufficient for deriving homology groups? Extending DayhofFs model to sequences. Technical Report. School of Computer Science and Information Systems, Birkbeck, University of London, February 2009,23 p. http://www.dcs.bbk.ac.Uk//research/techreps/2009/bbkcs-09-01.pdf.

11. Sulimova V., Mottl V., Mirkin В., Muchnik I., Kulikowski C. A Class of Evolution-Based Kernels for Protein Homology Analysis: A Generalization of the РАМ Model. Proc. of 5th International Symposium on Bioinformatics Research and Applications, Nova Southeastern University, Ft. Lauderdale, Florida, USA, May 13-16,2009.

Жирным шрифтом выделены публикации в журналах, рекомендованных ВАК.

Все приведенные в статьях результаты исследований, кроме результатов экспериментов

в (7), получены лично автором. Все статьи, кроме (10), написаны лично автором с последующим участием соавторов в редактировании текста.

Подписано в печать:

29.09.2009

Заказ № 2612 Тираж -100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

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

ВВЕДЕНИЕ.

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 Эксперименты на реальных данных.

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

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

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

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

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

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

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

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

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

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

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

Что же касается символьных последовательностей, то подавляющее большинство публикаций на эту тему ориентировано на анализ биологических полимеров, в частности, аминокислотных последовательностей белков. Именно этот вид символьных последовательностей находится в центре внимания в данной диссертации. В современной биохимии общепринятым способом измерения сходства аминокислот являются подстановочные матрицы РАМ (Point Accepted Mutation) и BLOSUM (BLock Substitution Matrix), которые в традиционной форме не являются потенциальными функциями. С этой точки зрения соответствующие способы построения потенциальных функций на множествах символьных последовательностей разной длины являются эвристическими.

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

Кроме того, несмотря на то, что дискретные сигналы и символьные последовательности имеют похожую структуру, в настоящее время не существует единого математического аппарата для их сравнения. Единственный корректный способ построения потенциальных функций на множестве сигналов разной длительности, предложенный французским ученым Ж.-Ф. Вертом, имеет ряд неестественных ограничений, дополнительно введенных по сравнению с аналогичным подходом, разработанным для символьных последовательностей.

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

Для разрешения первой проблемной ситуации относительно аминокислотных последовательностей белков в диссертации используется тот факт, что обе общепринятые меры сходства аминокислот, как РАМ, так и ВЬОБЦМ, численно выражают правдоподобие гипотезы об общем происхождении двух указанных аминокислот от одной неизвестной аминокислоты в результате двух независимых шагов эволюции. Такая двухместная функция на алфавите аминокислот всегда является потенциальной функцией по своей структуре. Практически используемые подстановочные матрицы РАМ и ВЪОБЦМ не являются положительно определенными только в силу логарифмического представления результата, к тому же округленного до целого значения.