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

Введение 3
1 Основные понятия и подходы 5
1.1 Постановка задачи исследования 5
1.1.1 Задача поиска точных соответствий 6
1.1.2 Задача поиска неточных соответствий 6
1.1.3 Задача сравнения символьных последовательностей 8
1.2 Обзор литературы 8
1.3 Основные понятия, используемые при построении нового алгоритма сравнения символьных последовательностей 11
1.3.1 Понятие свёртки двух функций 11
1.3.2 Дискретное преобразование Фурье и его свойства 13
1.3.3 Быстрое преобразование Фурье 15
2 Описание алгоритма 17
2.1 О преобразовании символьных последовательностей 17
2.2 Почему вместо вычисления свёртки последовательностей {а0;...,an} и {b0; ..., bk} можно перемножать многочлены с коэффициентами {а0,..., an}и {bk;...,b0}? 18
2.3 Способ вычисления свёртки 19
3 Вычислительные эксперименты 21
3.1 Выбор тестовых последовательностей 21
3.2 Результаты экспериментов со случайными последовательностями . . 21
3.2.1 Последовательности, не имеющие совпадающих участков 21
3.2.2 Последовательности с искусственно внедрёнными совпадениями . 23
3.3 Результаты экспериментов с реальными последовательностями ... 25
3.4 Последовательности с неточными совпадениями 26
3.5 Проблема локализации 27
3.6 Обсуждение 29
Заключение 33
Список использованных источников 34
Купить

Задача поиска повторов или общих подпоследовательностей в символьных последовательностях является одной из классических задач математики и информатики. Она имеет большое количество различных приложений во многих областях современной науки, в том числе и в области биоинформатики. Наиболее значимой здесь является задача организации быстрого и эффективного сравнения больших (длиной до 1012 символов) последовательностей, представляющих собой цепочки ДНК. Кроме этого, также очень важно уметь осуществлять быстрый поиск по образцу в таких обширных массивах данных. Несмотря на заметный прогресс в этом направлении, достигнутый в основном благодаря развитию вычислительной техники, обе эти задачи далеки от окончательного решения.
В настоящее время большинство алгоритмов, так или иначе решающих эту задачу, базируются на идее выравнивания (alignment). Суть выравнивания в том, что мы каким-то образом находим в сравниваемых последовательностях общее «ядро», а затем расширяем его до тех пор, пока не накопится слишком много ошибок. Выравнивание является исторически первым методом, получившим широкое распространение, однако при этом обладающее рядом существенных недостатков, к которым относятся
1) расходимость метода и следовательно его неспособность сравнивать последовательности длиннее l~ 104, и
2) произвол в выборе штрафных функций, который не может быть устранён формальными методами.
Целью настоящей работы является разработка и программная реализация нового метода сравнения символьных последовательностей, основанного на преобразовании символьных последовательностей в цифровые и работе с ними, на примере генетических текстов, а также его тестирование и расширение.
Основная идея данного метода принадлежит доктору физико-математических наук, профессору Владимиру Викторовичу Шайдурову.
Для достижения указанной цели были поставлены следующие задачи.
1. Анализ научной литературы по теме выпускной работы.
2. Разработка метода сравнения символьных последовательностей, основывающегося на вычислении функции свёртки двух полиномов и использовании быстрого преобразования Фурье.
3. Реализация разработанного алгоритма на языке C#, отладка и тестирование программы.
4. Проведение серии вычислительных экспериментов с целью определения пределов применимости разработанного метода и его алгоритмической реализации.
5. Проведение серии вычислительных экспериментов на реальных генетических текстах с целью сравнения с иными распространёнными приложениями, использующимися для сравнения и поиска в последовательностях.
Работа состоит из введения, трех глав, заключения и списка цитируемой литературы. В первой главе содержится постановка задачи данной работы, вводятся основные понятия и описываются подходы к решению поставленной проблемы. Вторая глава содержит подробное описание разработанного алгоритма. В третьей главе приведены результаты вычислительных экспериментов на различных типах входных данных, а также ведётся обсуждение полученных результатов и возможных путей развития метода. Список литературы состоит из 30 источников.
Особая благодарность доктору физико-математических наук, профессору Михаилу Георгиевичу Садовскому за биологическую постановку задачи, полезные обсуждения и помощь в освоении предметной области, а также Игорю Анатольевичу Боровикову из EADP Data and AI, Electronic Arts in Redwood Shores, Калифорния, США за стимулирующий интерес к работе.
Купить