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

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

Тетуев Руслан Курманбиевич

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

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

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

003156542

Пущино - 2007

Работа выполнена в Институте математических проблем биологии РАН, в филиале кафедры ММП факультета ВМиК МГУ им М В Ломоносова

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

профессор Флоренц Федорович Дедус

Официальные оппоненты: доктор технических наук,

профессор

Цимбал Владимир Анатольевич кандидат физико-математических наук Сенько Олег Валентинович

Ведущая организация: Межведомственный Суперкомпьютерный Центр РАН, г Москва

Защита диссертации состоится №

2007г

в I о Ьр г _на заседании Диссертационного совета

Д002 017 02 Вычислительного центра им А А Дородницына РАН по адресу 119991, Москва, ГСП-1, ул Вавилова, дом 40

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

Автореферат разослан | ^ I . 2007 г

Ученый секретарь Диссертационного доктор физико-математических Совета Д002 017 02, '^¡/Ь у наук

Актуальность темы

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

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

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

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

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

Цель работы

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

В соответствии с поставленной задачей определены задачи диссертационной работы:

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

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

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

5 Решение задачи поиска тандемных повторов в геномах средствами разработанной системы аналитических преобразований

Постановка научной задачи

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

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

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

В ходе доказательств получены рекуррентные соотношения особого вида для полиномов Якоби, Гегенбауэра и функций Якоби, Гегенбауэра, Сони-на-Лагерра, Лагерра, Чебышева первого и второго рода, Эрмита Сформулирована и доказана Теорема об обратимости линейных операторов, а также сформулирована и доказана Лемма о суперпозиции линейных операторов

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

аналитически с помощью операторов дифференцирования высоких порядков

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

Реализован программный комплекс "SpectralRevisor", организующий локализацию участков тандемных повторов в ДНК последовательностях на основе вычисления и анализа некоторых первых производных от функций-профилей, построенных на данных генетических последовательностях Практическая значимость работы

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

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

О обнаружение и распознавание визуальных образов в реальном

времени на основе контурного восприятия; п) поиск тандемных повторов в сверхдлинных генетических последовательностях, таких, как геном человека = 3 млрд нуклеотидов итд

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

Апробация работы Результаты работы докладывались

на международной конференции

PRIA-7-2004, International Conference on Pattern Recognition and Image Analysis New Information Technologies, St Petersburg, Russia October 18-23, на международной летней школе

BGRS-2-2006, Biomformatics of the Genome Regulation and Structure, International Summer School for young scientists "Evolution, Systems Biology and High Performance Computing Biomformatics", Novosibirsk, Russia July 12-15,

на всероссийских конференциях

Математические Методы Распознавания Образов-11, Пущино, 20-26 ноября (2003), ММРО-12, Москва, 20-26 ноября (2005), ММРО-13, Пущино, 9-15 октября (2006), на всероссийских школах-конференциях

Путинских школах-конференциях молодых ученных «Биология - наука XXI века», секция «Математическая биология» (2004), (2006)

Публикации

По теме диссертации опубликовано 14 печатных работ, в том числе 8 тезисов конференций, 4 трудов международных конференций, 6 статей в научных журналах (в т ч. 4 в изданиях, рекомендованных ВАК), 1 учебное пособие, 1 препринт, 1 зарегистрированная программа для ЭВМ

Объем и структура диссертации

Диссертация состоит из введения, 5 глав, заключения, списка литературы и 2 приложений, изложена на 88 страницах Список литературы содержит 24 наименования Работа содержит 29 рисунков и 7 таблиц

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

ВВЕДЕНИЕ

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

ГЛАВА I. Аналитические преобразования над спектром

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

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

2 Аналитические преобразования спектра Постановка научной задачи

3 Ранние попытки разрешения задачи Матричный способ

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

ГЛАВА II. Быстрые аналитические преобразования над спектром

Вторая глава посвящена описанию основных этапов разработки нового вычислительного подхода в задаче аналитического преобразования функ-

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

Ниже приведем указанные теоремы и лемму без доказательств, а также пример применения метода спектрального каскада-диффузии

Теорема 1: Пусть /О) - некоторая функция пространства L2p(a,b) и {ç„(xj} - система ортогональных функций того же пространства, такая что

ЛГ+1 и=0

Пусть далее А( ) - некоторый линейный оператор, такой что А(/)еПр(а,Ь) и

N+q

W) = Хс>„«

Тогда если для каждого <р,м(х) существует рекуррентное соотношение вида

где Fn( )- линейная форма, d,q,p - const е N,

то существует алгоритм линейной временной сложности для вычисления коэффициентов разложения {с*} при известных {с„}

Теорема 2 (об обратимости линейных операторов) Пусть {<р„(х)} - некоторая система ортогональных функций пространства I?p(a,b) и А( ) -некоторый линейный оператор, определяющий преобразование A L2p(a,b)->I}p(a,b) Пусть далее А~'() - обратный оператор Тогда, если для каждого <р,м{х) существует рекуррентное соотношение вида

и для всякого <р„(х)

то для оператора А'1() также существуют рекуррентные соотношения вида

где Fn{ ), Fa( )-линейные формы, d,g,р = const eN

Лемма (о суперпозиции линейных операторов) Если для осуществления внутриспектральных преобразований функций, соответствующих линейным операторам F(f) и G(/), существуют алгоритмы линейной временной сложности, то для осуществления преобразований спектра, соответствующих линейному оператору A(J) = F(G(f)), также существует алгоритм линейной временной сложности

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

''О ртогои альные базисы

¡непрерывного аргумента)

Рекуррентные соотношения для оператора АЩ) ^ ■'

Ipte-fteb _ 2(я + g + l + l)__+_2(a-ß)__p{aJt) _

J " (2м + а + ß + \)(2п + а + ß-r2) **' &n+a+ß)(2n+a+ß + 2) '

___2(n + a)(n + ß)____рШ)

(2n + a + ß)(2n + a + ß + \){n-ra + ß]

\c;dx = f; ¡m *-с, + К.; \L.dx=-4., + Кl ШЛ =

<ч/ * > Ч "Ч-s-J К 1 I Ч Л»1 Ч 3 1 « ч/, , 1\

J 2n J 2(й + 1) J 2/t +1

ГЛАВА III. Обшаи вычислительная схема для реализации быстры* спектральных преобразований

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

Пример: Пусть функция /(л) представлена рядом ортогональных полиномов Лагерра;

f(x) = 10/, (л) (х) + 6L,«

и требуется найти подобное же представление для результата применения оператора дифференцирования:

f\x) = СЦА + C[L(x) + + ,

если для полиномов Лагерра и оператора дифференцирования известно рекуррентное соотношение вида

LUx) = L-e(x)~L„(x).

Последнее соотношение приводит к двум фазам вычисления

где начальные табличные данные {с„} содержат значения

вИЮ,-5,-8, б], через {с;} - обозначены промежуточные значения, полученные в таблице {Cj после проведения спектрального каскада и -¡С*} - новая таблица, в которой ожидаются конечные коэффициенты представления.

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

{с;Из,-7,-2, б],

а после второй фазы получим искомые значения в виде

fc}=J7,2-6, о],

т.е.

/'(*) = 1L,(X}+ 2Щх)-Ы,{х) .

Если вспомнить что

4 = 1; = £, = )-2л + —; i, =l-3.v + — - —,

2 2 6

то полученный результат несложно проверить. Действительно:

/(*}= 1 Оих)- 51,(х)- 8£,(х)+(л) = 3 + 3.т + 5л-: -У; /'(х) = 11,0) + гц(х)- 61,(л) = З + Юг-ЗГ.

ГЛЛВЛ IV. Обобщения алгебры спектральных преобразований

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

1. Быстрые нелинейные спектральные преобразования.

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

3. Сверхбыстрые спектральные преобразование - вычисления на системах с параллельной архитектурой. Векторизация и конвейеризация вычислений.

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

Быстрые спектральные преобразования для систем классических ортогональных полиномов дискретного аргумента являются естественным обобщением алгебры спектральных преобразований на случай использования полиномов Хана (Гана), Мейкснера, Шарльс, Кравчука и Чебышсва дискретного аргумента (схема ниже). Перечисленные полиномы являются решениями разностного аналога гипергеометрического уравнения.

/ Пслннаиы ч«йыш»»» 1 . (дне*р« чоп> 1 ¡иуы»ктэ |

У:-;

Ортогональные базисы

(дискретного

/' Полнномва льные ортогональные Влэисы

ЛГ

Базисы классических

ортогональных полиномов

Полиномы Мейкснера

В—!—

Таблица 1 Соответствие некоторых преобразовании функций и операций над коэффициентами разложения по полиномам Кравчука.

N Преобразования функций Операции над коэффициентами разложения

1 / = «/1 с„ =« с*

2 /-Л+/2 с - с*+с** ^п ^ит п

3 / = /{ сп ** Сп+1

4 сп ~ с*п~\

5 Сп = Уп+1^п+1+ Pn.Cn +ап-\Сп-\

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

/оо = {У;*72«)

(=0

(функции представлены рядами по полиномам Кравчука)

ГЛАВА V. Применение быстрых спектральных преобразований

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

Задача 1. Применение в задачах распознавания визуальных образов

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

А X

/Г

В таких случаях распознавание визуального образа можно рассматривать лишь как распознавание контура объекта. Далее считаем, что контур объекта фактически является замкнутой кривой на плоскости, которая может быть представлена в параметрическом виде как пара функций: (.¥((.), Y(i,)).

UftS 1С,))

л=0

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

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

ь

Ы^х'у' + х'у'Ж

а

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

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

Координаты центра масс контура

т

хс = <Й,

о

Г

о

Площадь, ограниченная контуром

о о

Периметр контура

г _

ы Ух'2 (0+/2(*)<й

о

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

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

Ш'л^.-

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

Задача 2. Применение в задачах биоинформатики

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

После того, как в молекулярной биологии стало возможно решение задачи секвенирования, целью которой является однозначное описание линейной структуры ДНК молекулы в виде текстовой последовательности из четырех букв (А - аденина, Т - тимина, в - гуанина, С - цитозина), широко начали развиваться методы анализа генетических последовательностей, производимые посредством ЭВМ.

Известно, что ДНК молекулы подвержены многочисленным мутациям Множественное последовательное дублирование части ДНК (тандемные повторы) - одни из мутаций, которые можно обнаружить в ходе численного анализа генетической последовательности

agcaTTAGGCTTAGGCTTAGGCTTAGGCcgaa 1_ ;ч_/ч__у

1ГЛССС — илтия

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

** ~ + * ¡и*-!

j tlJ^l ^цл

agcaTTAGGCTTTCGCTAGGCTTTAGCCcga

, v у ,ч___+ вставка

- изъятие

TIA ООС - яютт

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

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

а скользящее окно

—у W

т G с a; G; с

V j j j

Y Y Y

G С Ж Т Т С.

/о Л h

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

Результатом тестовых запусков программного комплекса стало обнаружение множества действительных тандемных повторов генома бактерии Staphylococcus haemolitycus Среди множества выявленных подтвержденных фрагментов имеются ряд повторов, обнаруженных ранее Однако, как и ожидалось на ранних стадиях основания проекта, были выявлены новые фрагменты, ранее не известные Как правило, новые обнаруженные повторы искаженны мутациями и требуют на стадии проверки (стадия 7) приме-

нения сторонних программ множественного выравнивания (С1ш1а1 и др) Пример одного из таких, ранее не известных повторов представлен ниже

**** * * * * * * * ***

2586040- -АСАТАС--ССАв--вАСОА-СТТТТА-САТСА--СССАААА

2586073 : ТАСАТТТТА-САСТ-вААААОССА--А-вА-САТ--ТСАА-в

2586106. --САТТАТТ-вААТ--АТТ--СТв-ТАА-АСХЗАТСАССАААО

2586139• ТТС-ТАААААТАТТТТААСААССЮТАТТТА--АТ-ЭТ-----

2586172 --С-ТАА-ТССААА--АТСААССААСА-вААТАТАТТСАА--

2586205- - -САААА---вААТ--АТСААСвААСА-СААААСССАСАА-в

2586238 Т-СА-АС---вААА---ТС-ССТАТТАТОАССвСАСССАААО

Обнаруженный фрагмент тандемных повторов (после множественного выравнивания)

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

№

Описание стадии процесса

Схематическое описание

Загрузка фрагмента изучаемого генома из сети Internet (базы данных Genbank, Emboss, Entrez и ДР)

БАНКИ ДНК

Перевод текстового генетического фрагмента в функциональное пространство- вычисление «профиля» фрагмента (ОС-состав)

JaAa^-

Представление профиля в виде ортогонального ряда - перевод в пространство коэффициентов разложения {С,}

Осуществление преобразований I пространстве коэффициентов разложения, соответствующих дифференцированию профиля

{Сп} -ИО

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

{С.}

{с:>

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

А В,

7. ! 1роверка на наличие тандемных повторов во фрагменте генетической последовательности, соответствующем максимуму функционала опенки периодичности Профиля Л, 3, 1 [. ялССААССАдсоиап;«... |

8, После успешного множественною выравнивания осуществляется занесение подтвержденных тан-демных повторов в банк данных БАНК тандемны* повтори ■ 1

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

Зарегистрирована программа для ЭВМ "БреагаШеумог", осуществляющая спектральный анализ данных на предмет обнаружения и локализации неточных периодов в сигналах

ПРИЛОЖЕНИЯ

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

ВЫВОДЫ

1 Создана система правил для аналитических преобразований сигналов, представленных рядами через классические ортогональные полиномы -алгебра спектральных преобразований

2 Задача контурного распознавания визуальных объектов разрешена на основе аналитического вычисления инвариантных признаков контуров

3 Задача поиска тандемных повторов в геномах разрешена на основе аналитической оценки степени «периодичности» профилей

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1 Ф Ф Дедус, Л.И Куликова, А Н Панкратов, Р К Тетуев Классические ортогональные базисы в задачах аналитического описания и обработки информационных, сигналов, Москва, издательский отдел факультета ВМК им Ломоносова, 2004

2 ФФ Дедус, ЛИ Куликова, С А Махортых, Н.Н Назипова, АН Панкратов, РК Тетуев Аналитические методы распознавания повторяющихся структур в геномах Доклады Академии Наук 2006, том 411, №5, с 599-602

3 Ф Ф Дедус, Л И Куликова, С А Махортых, Н Н Назипова, А Н Панкратов, Р.К Тетуев, Распознавание структурно-функциональной организации генетических последовательностей, ТРУДЫ ВМК МГУ 2007, №2

4 R К Tetuev, Recognition of Lines Detected m the Image Plane on the Basis of the Generalized Spectral-Analytical Method, Pattern Recognition and Image Analysis, Vol 15, No 2,2005, pp 334-337

5 R К Tetouev, Contour Recognition Based on Spectral Methods Solution of the Problem of Choice of the Start-Pomt, Pattern Recognition and Image Analysis, Vol 17, No 2,2007,pp 227-235

6 P К Тетуев, Ф Ф Дедус, Классические ортогональные полиномы Применение в задачах обработки данных, препринт, М 11-й ФОРМАТ, 2007, 60 с

7 РК. Тетуев "Аналитическое описание зашумленных исходных сигналов по функциям Сонина-Лагерра и получение их первых производных" Математические Методы Распознавания Образов-11, Пущино, 20-26 ноября, 2003

8 Ruslan Tetuev "About Curves Recognition Based on Generalized Spectral-Analytical Method" 7-th International Conference on Pattern Recognition And Image Analysis New Information Technologies, St Petersburg, Russia October 18-23,2004

9 Р К Тетуев "Вычисление некоторых геометрических характеристик плоских кривых на основе спектральных методов" Математические Методы Распознавания Образов-12, Москва, 20-26 ноября, 2005

10 Ruslan Tetuev, Florencz Dedus, Lyudmila Kuhkova, Sergey Makhor-tikh, Anton Pankratov, Nafisa Nazipova "Analytical methods m problems of recognition the structural and functional organization of genetic sequences", The 2006 BGRS (Biomformatics of the Genome Regulation and Structure) International Summer School for young scientists "Evolution, Systems Biology and High Performance Computing Biomformatics", Novosibirsk, Russia July 12-15,2006

11 P К. Тетуев, Ф. Ф Дедус, JI И Куликова, С А Махортых, H H. Назипова, А Н. Панкратов "Аналитические методы в проблемах распознавания структурно-функциональной организации генетических последовательностей" Математическая Биология и Биоинформатика, Пущино, 9-15 октября 2006

12 Р К Тетуев, Ф.Ф. Дедус, H H Назипова, С А Махортых, ЛИ. Куликова, А H Панкратов, M M. Ольшевец Свидетельство Роспатента об официальной регистрации программы для ЭВМ №2007611639 «Спектральный анализ данных, поиск неточных периодов в сигналах «Spectral Revisor»

Подписано в печать 13 09 2007 г Исполнено 14 09 2007 г Печать трафаретная

Заказ № 712 Тираж 100 экз

Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш, 36 (495) 975-78-56 www autoreferat ru

ВВЕДЕНИЕ.

ГЛАВА I Аналитические преобразования над спектром.

1.1 Общие свойства классических ортогональных систем.

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

1.3 Предпосылки к развитию новых методов спектральной обработки.

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

1.5 Задача поиска методов быстрых спектральных преобразований.

1.6 Ранние попытки решения задачи. Матричный способ.

ГЛАВА II Быстрые аналитические преобразования над спектром.

2.1 Достаточное условие существования быстрых алгоритмов спектрального преобразования.

2.2 Классические ортогональные полиномы.

2.3 Быстрые преобразования для оператора вида A(f) = xf(x). Лемма о суперпозиции линейных операторов.

2.4 Быстрые преобразования для операторов вида A(f) = f(x)/x. Теорема обратимости линейных операторов.

2.5 Быстрые преобразования для оператора дифференцирования.

2.6 Быстрые преобразования для оператора интегрирования.

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

ГЛАВА III Общая вычислительная схема для реализации быстрых спектральных преобразований.

3.1 Определение спектрального каскада и диффузии.

3.2 Метод спектрального каскада и диффузии.

3.3 Пример применения метода каскада-диффузии.

3.4 Сравнительный анализ результатов расчетов и основных характеристик алгоритмов.

ГЛАВА IV Обобщения алгебры спектральных преобразований.

4.1 Быстрые нелинейные спектральные преобразования.

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

4.3 Сверхбыстрые спектральные преобразования на системах с параллельной архитектурой вычислений.

ГЛАВА V Применение быстрых спектральных преобразований.

5.1 Применение в задачах распознавания образов.

5.2 Применение в задачах биоинформатики.

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

Актуальность темы

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

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

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

• матричное представление функций в виде массива дискретных значений, изначально оказалось наиболее естественным для ЭВМ представлением и наиболее удобным для реализации большинства арифметических операций над функциями;

• было предложено немало численных методов для осуществления более сложных, аналитических преобразований. С возникновением ЭВМ эти методы получили развитие и распространение. Явным преимуществом таких подходов явилась простота вычислений и скорость - обычно затраченное вычислительное время и объемы требуемой памяти были пропорциональны величине массива данных;

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

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

Спектральное представление сегодня широко применяется, но большей частью для передачи, хранения и анализа данных, изначально полученных в виде массивов значений функций. Трудно переоценить влияние спектрального представления функций на развитие современной прикладной математики, однако на практике спектральное представление довольно редко используется для проведения определенных аналитических преобразований функций. В случае необходимости приходилось восстанавливать функцию в виде массива значений, а затем, проведя требуемые преобразованиями численно, снова «вернуть» функцию в спектральное представление. Однако, такая ситуация на наш взгляд не оправдана и как показано ранее, в ряде работ [111, 106], тем не менее, существует принципиальная возможность осуществления аналитических преобразований, при использовании лишь самих спектральных представлений функций или, иначе, их спектральных преобразований.

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

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

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

Вышеописанное положение демонстрирует потребность в создании альтернативного простого и точного прикладного математического аппарата для осуществления быстрых спектральных преобразований функций, соответствующих ряду основных аналитических преобразований функций и групп их суперпозиций. В качестве ортогональных систем в работе рассмотрен каждый базис из семейства классических ортогональных полиномов (JIareppa, Якоби, Эрмита, Лежандра, Сонина-Лагерра, Гегенбауэра, Чебышева первого и второго рода) и некоторые основные модификации этих базисов. В главе IV показано, что без нарушения общности основные вычислительные схемы легко переносятся на случай применения классических ортогональных полиномов дискретного аргумента: Хана, Мейкснера, Шарлье, Кравчука и Чебышева.

Цель работы

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

В соответствии с поставленной задачей определены задачи диссертационной работы:

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

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

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

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

5. Решение задачи поиска тандемных повторов в геномах средствами разработанной системы аналитических преобразований.

Постановка научной задачи

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

Научная новизна

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

Сформулирована и доказана Теорема о достаточном условии существования алгоритма быстрого спектрального вычисления.

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

В ходе доказательств получены рекуррентные соотношения особого вида для полиномов Якоби, Гегенбауэра и функций Якоби, Гегенбауэра, Сонина-Лагерра, Лагерра, Чебышева первого и второго рода, Эрмита.

Сформулирована и доказана Теорема об обратимости линейных операторов, а также сформулирована и доказана Лемма о суперпозиции линейных операторов.

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

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

Реализован программный комплекс "SpectralRevisor", организующий локализацию участков тандемных повторов в ДНК последовательностях на основе вычисления и анализа некоторых первых производных от функций-профилей, построенных на данных генетических последовательностях.

Практическая значимость работы

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

2) Показано, что для сложных преобразований функции, являющихся группой более простых, возможно построение единой вычислительной схемы, составленной на основе объединения соответствующих элементарных схем. При этом, многие частные вычисления в узлах выстраиваемой общей схемы, как показано в работе, могут быть произведены одновременно. Это позволит дополнительно ускорить алгоритмы при реализации на ЭВМ с параллельной архитектурой исполнения команд, что в свою очередь позволит применять данный подход в задачах, сопряженных с необходимостью сверхбыстрой обработки данных: i) обнаружение и распознавание визуальных образов в реальном времени на основе контурного восприятия; ii) поиск тандемных повторов в сверхдлинных генетических последовательностях, таких, как геном человека = 3 млрд. нуклеотидов и т.д.

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

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

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

Под полиномами Сонина-Лагерра в диссертационной работе понимаются обобгценные полиномы Лагерра. Подобная терминология впервые предложена авторами работы [111] и введена на основании [127].

выводы

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

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

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

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

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

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

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

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

В качестве основных выводов диссертационной работы автор видит следующее:

1. Создана система правил для аналитических преобразований сигналов, представленных рядами через классические ортогональные полиномы -алгебра спектральных преобразований.

2. Задача контурного распознавания визуальных объектов разрешена на основе аналитического вычисления инвариантных признаков контуров.

3. Задача поиска тандемных повторов в геномах разрешена на основе аналитической оценки степени «периодичности» профилей.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Ф.Ф.Дедус, Л.И.Куликова, А.Н.Панкратов, Р.К.Тетуев. Классические ортогональные базисы в задачах аналитического описания и обработки информационных, сигналов, Москва, издательский отдел факультета ВМК МГУ им.Ломоносова, 2004.

2. Ф.Ф. Дедус, Л.И. Куликова, С.А. Махортых, Н.Н. Назипова, А.Н.Панкратов, Р.К. Тетуев Аналитические методы распознавания повторяющихся структур в геномах. Доклады Академии Наук 2006, том 411, №5, с. 599-602.

3. Ф.Ф. Дедус, Л.И. Куликова, С.А. Махортых, Н.Н. Назипова, А.Н. Панкратов, Р.К. Тетуев, Распознавание структурно-функциональной организации генетических последовательностей, ТРУДЫ ВМК МГУ 2007, №2.

4. R. К. Tetuev, Recognition of Lines Detected in the Image Plane on the Basis of the Generalized Spectral-Analytical Method, Pattern Recognition and Image Analysis, Vol. 15, No. 2, 2005, pp. 334-337.

5. R. K. Tetouev, Contour Recognition Based on Spectral Methods. Solution of the Problem of Choice of the Start-Point, Pattern Recognition and Image Analysis, Vol. 17, No. 2, 2007, pp. 227-235.

6. Р.К. Тетуев, Ф.Ф. Дедус, Классические ортогональные полиномы. Применение в задачах обработки данных, препринт, М.: 11-й ФОРМАТ, 2007, 60 с.

7. Р.К. Тетуев "Аналитическое описание зашумленных исходных сигналов функциями Сонина-Лагерра и получение их первых производных" Математические Методы Распознавания Образов-11, Пущино, 20-26 ноября, 2003.

8. Ruslan Tetuev "About Curves Recognition Based on Generalized Spectral-Analytical Method" 7-th International Conference on Pattern

Recognition And Image Analysis: New Information Technologies, St. Petersburg, Russia October 18-23, 2004.

9. Р.К.Тетуев "Вычисление некоторых геометрических характеристик плоских кривых на основе спектральных методов" Математические Методы Распознавания Образов-12, Москва, 2026 ноября, 2005.

10. Ruslan Tetuev, Florencz Dedus, Lyudmila Kulikova, Sergey Makhortikh, Anton Pankratov, Nafisa Nazipova "Analytical methods in problems of recognition the structural and functional organization of genetic sequences", The 2006 BGRS (Bioinformatics of the Genome Regulation and Structure) International Summer School for young scientists "Evolution, Systems Biology and High Performance Computing Bioinformatics", Novosibirsk, Russia July 12-15, 2006.

11. P. К. Тетуев, Ф. Ф. Дедус, JI. И. Куликова, С. А. Махортых, Н. Н. Назипова, А. Н. Панкратов "Аналитические методы в проблемах распознавания структурно-функциональной организации генетических последовательностей" Математическая Биология и Биоинформатика, Пущино, 9-15 октября 2006.

12. Р.К. Тетуев, Ф.Ф. Дедус, Н.Н. Назипова, С.А. Махортых, Л.И. Куликова, А.Н. Панкратов, М.М. Олыневец Свидетельство Роспатента об официальной регистрации программы для ЭВМ №2007611639 «Спектральный анализ данных, поиск неточных периодов в сигналах «SpectralRevisor».

ЗАКЛЮЧЕНИЕ В качестве достаточного условия реализуемости быстрых спектральных преобразований предложено «слабое» условие существования рекуррентных соотношений особого вида. Данное предположение сформулировано в диссертационной работе в виде теоремы и доказано.

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

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

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

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

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

1.Andreas de Vries "Algorithms and Data Structures", VorlesungWirt-schaftsinformatik, 2005.

2. Andreas Solymosi and Ulrich Grude. Grundkurs Algorithmen und Datenstrukturen in Java. Vieweg, Braunschweig Wiesbaden, 2002.

3. Arbter K., Snyder W. E., Burkhardt H., and Hirzinger G. Application of Affine-Invariant Fourier Descriptors to Recognition of 3-D Objects. IEEE Trans. Pattern Analy. Machine Intell., 12:640 647, 1990.

4. Armin P. Barth. Algorithmik fur Einsteiger. Vieweg, Braunschweig Wiesbaden, 2003.

5. Arun Krishnan, Francis Tang «Exhaustive whole-genome tandem repeats search» Bioinformatics vol. 20 issue 16 no. 16, pages 27022710, Oxford University Press, 2004.

6. Becker, S. (1996). "Mutual information maximization: Models of cortical self-organization." Network: Computation in Neural Systems 7(1): 7-31.

7. Ben-Dor, A., Shamir, R. and Yakhini, Z. (1999). "Clustering gene expression patterns." J Comput Biol 6(3-4): 281-97.

8. Benson G. (1999) Tandem repeats finder: a program to analyze DNA sequences, Nucl. Acids Res., V. 27, issue 2, pp. 573-580.

9. Benson,G. (1995) A space efficient algorithm for finding best scoring non-overlapping alignments. Theor. Comput. Sci., 145, 357-369.

10. Benson,G. (1997) Sequence alignment with tandem duplication. J. Comput. Biol., 4, 351-367.

11. Berriz, G.F., King, O.D., Bryant, В., Sander, C. and Roth, F.P. (2003). "Characterizing gene sets with FuncAssociate." Bioinformatics 19(18): 2502-2504. Clustering Genes using Gene Expression and Text Literature Data

12. Bickel, S. and Tobias, S. (2004). Multi-View Clustering. Proceedings of the Fourth IEEE International Conference on Data Mining (ICDM'04).

13. Alferez Ronald and Wang Yuan-Fang, Geometric and Illumination Invariants for Object Recognition, Department of Computer Science, University of California, 1998.

14. Bozdech, Z., Llinas, M., Pulliam, B.L., Wong, E.D., Zhu, J.C. and DeRisi, J.L. (2003). "The transcriptome of the intraerythrocytic developmental cycle of Plasmodium falciparum." Plos Biology 1(1): 85-100.

15. Britenkov A.K., Pankratov A.N. Stable Algorithms of Adaptive Approximation for Acoustic Signals Description by Orthogonal Polynomials// Physics of Wave Phenomena, 2004, Vol.12, №3, pp.168-174

16. Саппу John, "A Computational Approach to Edge Detection," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 8, no. 6, pp. 679-698, November 1986.

17. Chaussabel, D. and Sher, A. (2002). "Mining microarray expression data by literature profiling." Genome Biol 3(10): RESEARCH0055.

18. Chiang, J.H. and Yu, H.C. (2003). "MeKE: discovering the functions of gene products from biomedical literature via sentence alignment." Bioinformatics 19(11): 1417-1422.

19. Collins,F.S. et al. (2003) The Human Genome Project: lessons from large-scale biology. Science, 300, 286-290.

20. Collins,J.R., Stephens,R.M., Gold,В., Long,В., Dean,M. and Burt,S.K. (2003) An exhaustive DNA micro-satellite map of the human genome using high performance computing. Genomics, 82, 10-19.

21. Djukova E.V., Inyakin A.S., and Peskov N.V. Methods of Combinatorial Analysis in Synthesis of Efficient Recognition Algorithms // Pattern Recognition and Image Analysis, 2003. V. 13. № 2. P. 426.

22. Donald E. Knuth. The Art of Computer Programming. 1. Fundamental Algorithms. Addison-Wesley, Reading, 3rd edition, 1997.

23. Donald E. Knuth. The Art of Computer Programming. 3rd Sorting and Searching. Addison-Wesley, Reading, 3rd edition, 1998.

24. Eisen, M.B., Spellman, P.T., Brown, P.O. and Botstein, D. (1998). "Cluster analysis and display of genome-wide expression patterns." Proceedings of the National Academy of Sciences of the United States of America 95(25): 14863-14868.

25. EH Saber, and A. Murat Tekalp, "Region-Based Shape Matching for Automatic Image Annotation and Query-by-Example" Journal of visual communication and image representation, Vol. 8, No. 1, March, pp. 3-20,1997.

26. Fleischmann, W., Moller, S., Gateau, A. and Apweiler, R. (1999). "A novel method for automatic functional annotation of proteins." Bioinformatics 15(3): 228-233.

27. Frazier,M.E. et al. (2003) Realizing the potential of the genome revolution: the genomes to life program. Science, 300, 290-293.

28. Friedhelm Padberg. Elementare Zahlentheorie. Spektrum Akademischer Verlag, Heidelberg Berlin, 2nd edition, 1996.

29. Fu,Y.H. et al. (1992) An unstable triplet repeat in a gene related to myotonic muscular dystrophy. Science, 255, 1256-1258.

30. Getz, G., Levine, E. and Domany, E. (2000). "Coupled two-way clustering analysis of gene microarray data." Proc Natl Acad Sci USA 97(22): 12079-84.

31. Gibbons, F.D. and Roth, F.P. (2002). "Judging the quality of gene expression-based clustering methods using gene annotation." Genome Research 12(10): 1574-1581.

32. Glenisson, P., Antal, P., Mathys, J., Moreau, Y. and De Moor, B. (2003). "Evaluation of the vector space representation in text-based gene clustering." Рас Symp Biocomput: 391-402.

33. Glenisson, P., Mathys, J. and De Moor, B. (2004). "Meta-Clustering of Gene Expression Data and Literature-based Information." SIGKDD Explorations 5(2): 101-112.

34. Gravano, L., Garcia-Molina, H. and Tomasic, A. (1999). "Gloss: Text-source discovery over the internet." ACM Transactions on Database Systems 24(2): 229-264.

35. Groult,R., Leonard,M. and Mouchard,L. (2002) Evolutive tandem repeats using Hamming distance. In Proceedings of 27th Symposium on Mathematical Foundations of Computer Science, Warsaw, Poland, August 2002, Springer, pp. 292-304.

36. Groult,R., Leonard,M. and Mouchard,L. (2003) Speeding up the detection of evolutive tandem repeats. In Proceedings of The Prague Stringology Conference '03.

37. Groult,R., Leonard,M. and Mouchard,L. (2004) Speeding up detection of evolutive tandem repeats. Theor. Сотр. Sci., 310, 309-328.

38. ISO/IEC JTC1/SC29/WG11, Coding of Moving Pictures and Audio: MPEG-4 Video Verification Model version 18.0, JTC1/SC29/WG11 N3908, Pisa, January 2001.

39. Jain, A.K. and Dubes, R.C. (1988). Algorithms for clustering data, Prentice Hall.

40. Jenssen, Т.К., Laegreid, A., Komorowski, J. and Hovig, E. (2001). "A literature network of human genes for high-throughput analysis of gene expression." Nat Genet 28(1): 21-8.

41. Joint Video Team of ISO/IEC MPEG and ITU-T VCEG, Joint Final Committee Draft (JFCD) of Joint Video Specification (ITU-T Rec. H.264 | ISO/IEC 14496-10 AVC), JVTD157, Australia, July 2002.

42. Kannan,S.K. and Myers,E.W. (1996) An algorithm for locating regions of maximum alignment score. SIAM J. Comput., 25, 648-662.

43. Kasturi J. and Acharya R. (2004). Clustering of diverse genomic data using information fusion Proceedings of the 2004 ACM symposium on Applied computing Nicosia, Cyprus ACM Press: 116-120

44. Katti,M.V. et al. (2000) Amino acid repeat patterns in protein sequences: their diversity and structural-functional implications. Protein Sci., 9, 1203-1209.

45. Kiranyaz S., Caglar K., Guldogan O., and Karaoglu E„ "MUVIS: A Multimedia Browsing, Indexing and Retrieval Framework", Proc. of Third International Workshop on Content Based Multimedia Indexing, CBMI2003, Rennes, France, 22-24 September 2003.

46. Kiranyaz S., Ferreira M. and Gabbouj M. "A novel feature extraction method based on segmentation over edge field for multimedia indexing and retrieval", Institute of Signal Processing, Tampere University of Technology, Tampere, Finland.

47. Kitada,H. et al. (1996) Multiple alignment of biological sequences containing tandem repeats. Genome Inform., 7, 276-277.

48. Kober V.I., M. G. Mozerov, J. Alvarez-Borrego and I. A. Ovseyevich. Nonlinear Image Processing with an Adaptive Structural Element // Pattern Recognition and Image Analysis, 2003. V. 13. No. 3. P. 476.

49. Kolpakov,R et al. (2003) mreps: Efficient and flexible detection of tandem repeats in DNA. Nucleic Acids Res., 31, 3672-3678.

50. Kolpakov,R. and Kucherov,G. (2003) Finding approximate repetitions under Hamming distance. Theor. Com. Sci., 303, 135-156.

51. Korotkov E.V., Korotkova M.A. (1995) Latent periodicity of DNA sequences from some human gene regions, DNA Seq., V.5, pp.353358.

52. Korotkov E.V., Korotkova M.A., Kudryashov N.A. (2003) Information decomposition method to analyze symbolical sequences. Phys. Lett. A, 312: 198-210

53. Kotel'nikov I.V. Algorithmic Models for Solving Pattern Recognition Problems 11 Pattern Recognition and Image Analysis, 1999. V. 9. № 1. P. 7.

54. Kurtz,S., Choudhuri,J.V., Ohlebusch,E., Schleiermacher,C., Stoye,J. and Giegerich,R. (2001) REPuter: the manifold applications of repeat analysis on a genomic scale. Nuclei с Acids Res., 29,4633^1642.

55. Landau,G.M. and Schmidt,J.P. (1993) An algorithm for approximate tandem repeats. In Proceedings of the. 4th Annual Symposium on Combinatorial Pattern Matching, Lecture Notes in Computer Science, Springer-Verlag, Vol. 648, pp. 120-133.

56. Landau,G.M. and Vishkin,U. (1989) Fast parallel and serial approximate string matching. J. Algorithm., 10,157-169.

57. Landau,G.M. et al. (1998) Incremental string comparison. SIAM J. Comput., 27, 557-582.

58. Landau,G.M. et al. (2001) An algorithm for approximate tandem repeats. J. Comput. Biol., 8, 1-18.

59. Landau,G.M., Schmidt,J.P. and Sokol,D. (2001) An algorithm for approximate tandem repeats. J. Сотр. Biol., 8, 1-18.

60. Lempel A., Ziv J. (1976) On the Complexity of Finite Sequences. IEEE Transactions on Information Theory, V.IT-22, 75.

61. Levenshtein,V.I. (1966) Binary codes capable of correcting, deletions, insertions and reversals. Soviet Phys. Dokl., 10, 707-710.

62. Main,M.G. and Lorentz,R.J. (1984) An 0(n logn) algorithm for finding all repetitions in a string. J. Algorithm., 422^432.

63. Moore G.E. (1965) Cramming more components onto integrated circuits, Electronics Magazine, V. 38, no. 8, pp. 114-117.

64. Noe L., Kucherov G. (2004) Improved hit criteria for DNA local alignment, BMC Bioinformatics, V. 5, 149 (http://www.biomedcentral.eom/1471-2105/5/149).

65. Ralf Hartmut Guting. Datenstrukturen und Algorithmen. B.G. Teubner, Stuttgart, 1997.

66. Raychaudhuri, S., Chang, J.T., Imam, F. and Altman, R.B. (2003). "The computational analysis of scientific literature to define and recognize gene expression clusters." Nucleic Acids Research 31(15): 4553-4560.

67. Raychaudhuri, S., Chang, J.T., Sutphin, P.D. and Altman, R.B. (2002). "Associating genes with gene ontology codes using a maximum entropy analysis of biomedical literature." Genome Research 12(1): 203-214.

68. Robert Sedgewick. Algorithmen in C. Addison-Wesley, Bonn, 1992. 89

69. Roberts, R.J. (2001). "PubMed Central: The Gen-Bank of the published literature." Proc Natl Acad Sci U S A 98(2): 381-2.

70. Roth, F.P., Hughes, J.D., Estep, P.W. and Church, G.M. (1998). "Finding DNA regulatory motifs within unaligned noncoding sequences clustered by whole-genome mRNA quantitation." Nature Biotechnology 16(10): 939-945.

71. Sagot,M. and Myers,E.W. (1998) Identifying satellites in nucleic acid sequences. In Second Annual International Conference on Research in Computational Molecular Biology (RECOMB).ACM Press, New York, pp. 234-242.

72. Schmidt,J.P. All highest scoring paths in weighted grid graphs and their application to finding all approximate repeats in strings. SI AM J. Comput., 27,972-992.

73. Sergunin S.Yu., Kvashnin K.M., and M.I. Kumskov M.I. Image Representation in the Recognition Problem on the Basis of Symbol Marking of Its Singular Points // Pattern Recognition and Image Analysis, 2003. V. 13. № 1. P. 170.

74. Sharma D, Issac B, Raghava GPS, Ramaswamy R (2004) Spectral Repeat Finder (SRF): identification of repetitive sequences using Fourier transformation. Bioinformatics, 20(9): 1405-1412

75. Sokol Dina, Benson Gary and Tojeira Justin «Tandem repeats over the edit distance» Vol. 23 ECCB, pages e30-e35, Oxford University Press, 2006.

76. Stephen C. Kleene. Turing's Analysis of Computability, and Major Applications of It'. In Rolf Herken, editor, The Universal Turing Machine. A Half-Century Survey, Wien, 1994. SpringerVerlag.

77. Stolovitzky,G., Gao,Y., Floratos,A. and Rigoutsos,I. (2001) Tandem repeat detection using pattern discovery, with applications to identification of yeast satellites. Technical Report RC 21508. IBM T. J. Watson Research Center, Cambridge.

78. Tamames, J., Ouzounis, C., Casari, G., Sander, C. and Valencia, A. (1998). "EUCLID: automatic classification of proteins in functional classes by their database annotations." Bioinformatics 14(6): 542-543.

79. Tanabe, L., Scherf, U., Smith, L.H., Lee, J.K., Hunter, L. and Weinstein, J.N. (1999). "Med-Miner: an Internet text-mining tool forbiomedical information, with application to gene expression profiling." Biotechniques 27(6): 1210-4, 1216-7.

80. Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms.

81. Thomas Ottmann and PeterWidmayer. Algorithmen und Datenstrukturen. Spektrum Akademischer Verlag, Heidelberg Berlin, 4rd edition, 2002.

82. Turing Machine. A Half-Century Survey, pages 207-235. Springer-Verlag, Wien, 1994.

83. Ukkonen,E. (1983) On approximate string matching. In Proceedings of the International Conference Foundations of Computation Theory, Lecture Notes in Computer Science 158, Springer-Verlag, pages 487-495.

84. Volker Heun. Grundlegende Algorithmen. Vieweg, Braunschweig Wiesbaden, 2000.

85. Watson J.D., Crick F.H.C. (1953) Molecular Structure of Deoxypentose Nucleic Acids. Nature, V. 171, p. 737.

86. Wexler,Y., Yakhini,Z„ Kashi,Y. and Geiger,D. (2004) Finding approximate tandem repeats in genomic sequences. In Proceedings of the 8th Annual Conference on Research in Computational Molecular Biology (RECOMB).

87. William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery. Numerical Recipes in С++. The Art of Scientific Computing. Cambridge University Press, Cambridge, 2nd edition, 2002.

88. Wirth N. Algorithmen und Datenstrukturen. B.G. Teubner, Stuttgart Leipzig, 1999.

89. Yang Chengyong, Zeng Erliang, Li Tao, and Narasimhan Giri, Clustering Genes using Gene Expression and Text Literature Data,

90. Bioinformatics Research Group (BioRG), School of Computer Science, Florida International University, Miami, Florida

91. Александров A.A. и др. (1990) Компьютерный анализ генетических текстов, М.:Наука, 264 с.

92. Бейтман Г., Эрдейи А., «Вычисление трансцендентных функций», том 2, Главная редакция физико-математической литературы, М. 1966 г., с. 156-223

93. Бухберг Б., Калме Ж., Калтофен Э., Коллинз Дж., Лауэр М., Лафон Ж., Лоос Р., Минньотт М., Нойбюзер Й., Норманн А., Уинклер Ф., Я. Ван Хюльзен, «Компьютерная алгебра: Символьные и алгебраические вычисления» Пер. с англ. М.: Мир, 1986. - 392 с.

94. Гасфилд Д. (2003) Строки, деревья и последовательности в алгоритмах. СПб.: Невский проспект, с. 225. (Dan Gusfield (1997) Algorithms on String, Trees, and Sequences University of California, Davis, P. 255).

95. Горбань A.H., Миркес E.M., Попова Т.Г., Садовский М.Г. (1993) Новый подход к изучению статистических свойств генетических последовательностей. Биофизика, Т. 38, Вып. 5, с. 762-767.

96. Горелик А.Л., Скрипкин В.А. Методы распознавания. М.: Высш. шк., 1977.

97. Дедус Ф.Ф. Аналитическое представление экспериментальных данных и их обработка. Кибернетика и вычислительная техника. Вып.74, «Наукова думка», Киев, 1987.

98. Дедус Ф.Ф., Гальченко А.А., Малахов В.Н. и др. Разработка методов и аппаратуры помехоустойчивого преобразования информации. Отчет по НИР. Номер гос. регистрации 76047147. Пущино: НИВЦ АН СССР, 1982.

99. Дедус Ф.Ф., Куликова Л.И., Панкратов А.Н., Тетуев Р.К. «Классические ортогональные базисы в задачах аналитического описания и обработки информационных сигналов», М., Факультет ВМиК МГУ им. М.В. Ломоносова, 2004 г.

100. Дедус Ф.Ф., Махортых С.А., Устинин М.Н., Дедус А.Ф., «Обобщенный спектрально-аналитический метод обработки информационных массивов», М., Машиностроение, 1999 г.

101. Джунгурова О.С. «Реализация некоторых операций над отрезками ортогональных рядов полиномов Кравчука», Математические методы распознавания образов: 12 я Всероссийская конференция: Сборник докладов. М.: МАКС Пресс, 2005.-500 с.

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

103. Загоруйко Н.Г. Методы распознавания и их применение. М.: Сов. радио, 1972.

104. Гук М. Процессоры Pentium II, Pentium Pro и просто Pentium -СПб: Питер Ком, 1999. 288 с.

105. Качмаж С., Штейнгауз С. «Теория ортогональных рядов», М.: Физматгиз, 1958 г.

106. Колмогоров А.Н. (1987) Теория информации и теория алгоритмов. М.: Наука, 213 с.

107. Кропотов А.И., «Николай Яковлевич Сонин», Л., Наука, 1967 г.

108. Курант Р., Гильберт Д. Методы математической физики, т. 1, М.-Л., Гостехиздат, 1951.

109. Математический энциклопедический словарь (гл. редактор Ю. В. Прохоров), М.: Советская энциклопедия, 1988 г.

110. Махортых С.А., Панкратов А.Н. О спектральном разложении нерегулярных кривых. В кн. Доклады I Всероссийской конференции «Спектральные методы обработки информации в научных исследованиях» («Спектр - 2000»), М.: Алеф, 2000, 4446.

111. Натансон И.П. «Теория функций вещественной переменной» изд. 2, М.: Гостехиздат, 1957 г.

112. Никифоров А.Ф., Уваров В.Б., «Специальные функции математической физики», М., Наука, 1978 г.

113. Никифоров А.Ф., Суслов С.К., Уваров В.Б. Классические ортогональные полиномы дискретной переменной. // М.: Наука. 1985.216 с.

114. Новикова Д.А., Поволоцкий А.В. «Формулы для преобразования функций в пространстве коэффициентов разложения по базису полиномов Чебышева второго рода» М.: Сборник статей молодых ученных ВМиК МГУ, 2007, выпуск №4, с. 1-8.

115. Панкратов А.Н., «О реализации алгебраических операций над рядами ортогональных функций», Журнал вычислительной математики и математической физики, 2004, с. 2121-2127.

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

117. Семенюк В. В. «Современные методы и стандарты экономного кодирования видеоинформации», Санкт-Петербург, специально для http://www.compression.ru, 2002.

118. Толстов Г.П. «Ряды Фурье», изд. 2, М.: Физматгиз, 1960 г. 390 с.

119. Трикоми Ф. «Дифференциальные уравнения», Изд. 2-е, М.: Едиториал УРСС, 2003. 352 с.

120. Фу К.С. Последовательные методы в распознавании образов и обучении машин-М.: Наука, 1971.

121. Фу К.С. Структурные методы в распознавании образов. М.: Мир, 1977.

122. Чебышев П.Л. «Вопросы о наименьших величинах, связанных с приближенным представленных функций», том 2., М.-Л., 1947 г., с. 151-235.

123. Шеннон К. (1963) Работы по теории информации и кибернетике. М.: Иностранная литература, 243 с.