📄Работа №167489
Тема: ИСПОЛЬЗОВАНИЕ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ И СВЁРТОЧНЫХ ФУНКЦИЙ ДЛЯ СРАВНЕНИЯ НУКЛЕОТИДНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ
Характеристики работы
Тип работы
Бакалаврская работа
Предмет
Математика
Объем:
40 листов
Год:
2020
Просмотров:
67
4620
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Введение 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
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, Калифорния, США за стимулирующий интерес к работе.
В настоящее время большинство алгоритмов, так или иначе решающих эту задачу, базируются на идее выравнивания (alignment). Суть выравнивания в том, что мы каким-то образом находим в сравниваемых последовательностях общее «ядро», а затем расширяем его до тех пор, пока не накопится слишком много ошибок. Выравнивание является исторически первым методом, получившим широкое распространение, однако при этом обладающее рядом существенных недостатков, к которым относятся
1) расходимость метода и следовательно его неспособность сравнивать последовательности длиннее l~ 104, и
2) произвол в выборе штрафных функций, который не может быть устранён формальными методами.
Целью настоящей работы является разработка и программная реализация нового метода сравнения символьных последовательностей, основанного на преобразовании символьных последовательностей в цифровые и работе с ними, на примере генетических текстов, а также его тестирование и расширение.
Основная идея данного метода принадлежит доктору физико-математических наук, профессору Владимиру Викторовичу Шайдурову.
Для достижения указанной цели были поставлены следующие задачи.
1. Анализ научной литературы по теме выпускной работы.
2. Разработка метода сравнения символьных последовательностей, основывающегося на вычислении функции свёртки двух полиномов и использовании быстрого преобразования Фурье.
3. Реализация разработанного алгоритма на языке C#, отладка и тестирование программы.
4. Проведение серии вычислительных экспериментов с целью определения пределов применимости разработанного метода и его алгоритмической реализации.
5. Проведение серии вычислительных экспериментов на реальных генетических текстах с целью сравнения с иными распространёнными приложениями, использующимися для сравнения и поиска в последовательностях.
Работа состоит из введения, трех глав, заключения и списка цитируемой литературы. В первой главе содержится постановка задачи данной работы, вводятся основные понятия и описываются подходы к решению поставленной проблемы. Вторая глава содержит подробное описание разработанного алгоритма. В третьей главе приведены результаты вычислительных экспериментов на различных типах входных данных, а также ведётся обсуждение полученных результатов и возможных путей развития метода. Список литературы состоит из 30 источников.
Особая благодарность доктору физико-математических наук, профессору Михаилу Георгиевичу Садовскому за биологическую постановку задачи, полезные обсуждения и помощь в освоении предметной области, а также Игорю Анатольевичу Боровикову из EADP Data and AI, Electronic Arts in Redwood Shores, Калифорния, США за стимулирующий интерес к работе.
✅ Заключение
В ходе выполнения данной работы все поставленные задачи были выполнены, а цель достигнута.
1. Разработан метод сравнения символьных последовательностей, основанный на вычислении свёртки двух полиномов, построенных на базе данных последовательностей, и использовании быстрого преобразования Фурье.
2. Написана компьютерная программа, реализующая данный метод, проведено её тестирование и отладка на большом классе входных последовательностей.
3. Проведены серии вычислительных экспериментов на специально сгенерированных последовательностях с целью определения пределов применимости разработанного метода и его алгоритмической реализации.
4. Проведены серии вычислительных экспериментов на реальных генетических последовательностях для сравнения с другими распространёнными инструментами, использующимися для сравнения и поиска в последовательностях.
Апробация работы. Основные результаты работы докладывались на следующих конференциях и семинарах:
1) XXVIII Всероссийском семинаре «Нейроинформатика, её приложения и анализ данных», Красноярск, 3-5 октября 2019 г.;
2) Международной молодёжной научной конференции «Проспект Свободный — 2020», Красноярск, 24 апреля 2020 г.;
3) 1-ом Сибирском научном семинаре по технологиям анализа данных и приложениям (The 1st Siberian Scientific Workshop on Data Analysis Tech-nologies with Applications, SibDATA-2020), Красноярск, 10 июня 2020 г;
4) 8-ой Международной рабочей конференции по биоинформатике и биоинженерии (8th International Work-Conference on Bioinformatics and Biomedical Engineering, IWBBIO 2020), Гранада (Испания).
Основные результаты выпускной квалификационной работы опубликованы в:
1) A. Molyavko, V. Shaidurov, Eu. Karepova, M. Sadovsky Highly Parallel Convolution Method to Compare DNA Sequences with Enforced In/Del and Mutation Tolerance // LNBI, 2020, vol.12108, pp.472-481;
2) В.В. Шайдуров, А. А. Молявко, А. А. Поплаухин, А. И. Аксенова, М. Г. Садовский. Об одном алгоритме поиска общих подпоследовательностей с неточным совпадением (включая вставки и выпадения) на основе свёрточных функций и быстрого преобразования Фурье // Материалы XXVIII Всероссийского семинара Нейроинформатика, её приложения и анализ дан-ных, Красноярск, 2019, с.138-144.
1. Разработан метод сравнения символьных последовательностей, основанный на вычислении свёртки двух полиномов, построенных на базе данных последовательностей, и использовании быстрого преобразования Фурье.
2. Написана компьютерная программа, реализующая данный метод, проведено её тестирование и отладка на большом классе входных последовательностей.
3. Проведены серии вычислительных экспериментов на специально сгенерированных последовательностях с целью определения пределов применимости разработанного метода и его алгоритмической реализации.
4. Проведены серии вычислительных экспериментов на реальных генетических последовательностях для сравнения с другими распространёнными инструментами, использующимися для сравнения и поиска в последовательностях.
Апробация работы. Основные результаты работы докладывались на следующих конференциях и семинарах:
1) XXVIII Всероссийском семинаре «Нейроинформатика, её приложения и анализ данных», Красноярск, 3-5 октября 2019 г.;
2) Международной молодёжной научной конференции «Проспект Свободный — 2020», Красноярск, 24 апреля 2020 г.;
3) 1-ом Сибирском научном семинаре по технологиям анализа данных и приложениям (The 1st Siberian Scientific Workshop on Data Analysis Tech-nologies with Applications, SibDATA-2020), Красноярск, 10 июня 2020 г;
4) 8-ой Международной рабочей конференции по биоинформатике и биоинженерии (8th International Work-Conference on Bioinformatics and Biomedical Engineering, IWBBIO 2020), Гранада (Испания).
Основные результаты выпускной квалификационной работы опубликованы в:
1) A. Molyavko, V. Shaidurov, Eu. Karepova, M. Sadovsky Highly Parallel Convolution Method to Compare DNA Sequences with Enforced In/Del and Mutation Tolerance // LNBI, 2020, vol.12108, pp.472-481;
2) В.В. Шайдуров, А. А. Молявко, А. А. Поплаухин, А. И. Аксенова, М. Г. Садовский. Об одном алгоритме поиска общих подпоследовательностей с неточным совпадением (включая вставки и выпадения) на основе свёрточных функций и быстрого преобразования Фурье // Материалы XXVIII Всероссийского семинара Нейроинформатика, её приложения и анализ дан-ных, Красноярск, 2019, с.138-144.
ИЛИ
Поиск аналога
📕 Список литературы
🖼 Скриншоты
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.