Спектрально-аналитический метод поиска протяженных повторяющихся нуклеотидных последовательностей в геномах Пятков, Максим Иванович

Введение к работе

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

Сложность определения повторяющихся фрагментов нуклеотидных последовательностей тесно связана с мутационными процессами, происходящими в организме, благодаря которым происходят вставки, замены и делеции отдельных нуклеотидов, а иногда и целых участков ДНК. Большинство методов поиска повторяющихся последовательностей основано на алгоритмах, которые работают с нуклеотидной последовательностью как со строкой символов. В этом случае учет точечных мутаций является вычислительно сложной операцией. Для решения этой проблемы предлагаются различные подходы, при этом некоторые из них базируются на спектральных методах, где в основу положено быстрое преобразование Фурье (БПФ). Помимо того, что спектральные подходы, основанные на БПФ, только отчасти решают проблему учета мутаций, они также ограничены в плане масштабируемости вследствие однозначного соответствия получаемого спектра нуклеотидной последовательности. Данные подходы позволяют исследовать нуклеотидные последовательности длиной порядка до IO⁴ нуклеотидных пар (н. п.). Однако для решения отдельных задач в области эволюции и структурной геномики требуется работа с протяженными последовательностями на различных масштабах, включая хромосомы и полные геномы (порядка IO⁹ н. п.). При этом с накоплением информации о новых организмах все большую роль будет приобретать скорость обработки генетических текстов. Таким образом, в настоящее время является актуальной разработка программных инструментов, позволяющих быстро сравнивать протяженные нуклеотидные последовательности, выделяя при сравнении наиболее значимые участки.

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

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

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

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

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

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

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

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

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

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

Теоретическая и практическая значимость диссертационной работы определяется следующими положениями:

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

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

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

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

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

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

   1. Разработан метод поиска протяженных повторяющихся структур в нуклеотидных последовательностях, основанный на спектральном анализе пары кривых ОС-,ОА-содержания на разных масштабах и позволяющем выявлять различные типы повторяющихся структур (прямых, обратных, комплементарных, инвертированных).

   3. 5. 1. Предложены и реализованы алгоритмы, которые позволяют максимально использовать параллельность и векторизацию современных процессорных архитектур.

         2. На основе метода реализована процедура автоматического распознавания и поиска мегасателлитных повторов. На основе этой процедуры в хромосоме 17 кролика (Oryctolagus cuniculus) выявлен ранее неизвестный мегасател- литный повтор с длиной повторяющего фрагмента 2623 нуклеотида.

         Апробация работы. Результаты диссертационной работы были доложены на следующих конференциях: 13, 14, 15 Всероссийские конференции "Математические методы распознавания образов (ММРО)" (Зеленогорск, 2007; Суздаль, 2009; Петрозаводск, 2011); на 9-ой международной конференции "Распознавание образов и анализ изображений (РОАИ)" (Нижний Новгород, 2008); на II, III, IV Международных конференциях "Математическая биология и биоинформатика (ІСМВВ)" (Пущино, 2008, 2010, 2012); на 8 и 9 международных конференциях "Интеллектуализация обработки информации (ПОИ)" (Пафос, 2010; Будва, 2012); на 12, 14, 16 Международных пущинских школах-конференциях молодых ученых "Биология наука XXI века" (Пущино, 2008, 2010, 2012); на 12 и 13 Международных суперкомпьютерных конференциях "Научный сервис в сети интернет" (Новороссийск, 2010, 2011), а также на IV Летней школе по научным вычислениям (Москва, 2009). Работа получила второе место в межлабораторном конкурсе "Intel Software - продемонстрируй красоту решения" (Москва, 2009), является победителем конкурса "Intel Manycore Testing Lab" (2010) и победителем трех этапов конкурса "Эффективное использование GPU-ускорителей при решении больших задач" проводимого компанией Т-Платформы (Москва, 2011).

         Диссертационная работа была выполнена при поддержке грантов №07-01-00564-а, №08-01-12030-офи, №08-07-00353-а, №10-01-00609-а, №11-07- 00519-а, №11-07-00716-а.

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

         Публикации. По теме диссертации опубликовано 27 научных работ, в том числе: 2 в списках журналов рекомендованных ВАК; 1 методическое пособие; 2 электронные публикации; 22 в сборниках тезисов конференций.

         Объем и структура работы. Диссертация изложена на 94 страницах и состоит из введения, четырех глав, заключения и списка литературы. Список литературы состоит из 94 наименований. Работа содержит 24 рисунка, 6 таблиц.

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

         

         Поиск и исследование магнитных Вр-звезд Главной ПоследовательностиЯкунин Илья Андреевич

         

         Вычислительные методы на последовательности сеток Шайдуров Владимир Викторович

         

         Метод распознавания аминокислотных последовательностей в масс-спектрах пептидов для задач протеомикиЛютвинский Ярослав Игоревич

         

         Развитие акустических методов исследования неоднородных сред с использованием тестовых сигналов на основе М-последовательностиСтромков Александр Альбертович

         Методы поиска и улучшения экстремальных процессов в невыпуклых задачах оптимального управленияРозинова, Надежда Сергеевна

         Бозе-Эйнштейновские корреляции в области энергий V-мезонов. Анализ методов поиска СР-нарушения на В-фабрикахБлинов, Александр Евгеньевич

         

         Ньютоновские методы поиска особых решений нелинейных уравненийЕрина Мария Юрьевна

         

         Семантическая отладка программ методом поиска конкретных ошибок /приложение/ Черняховский Владимир Викторович

         

         Методы поиска точек равновесия в билинейной игре с ненулевой суммойДелавархалафи Али

         

         Методы поиска областей сложного поведения хаотических системЛогунов Максим Юрьевич