Разработка методов и средств статистического моделирования биотехнологических процессов

Студент-дипломник: ________________________ / _______________ /

Руководитель проекта: ________________________ / _______________ /

Рецензент: ________________________ / _______________ /

Заведующий кафедрой №12: ________________________ / _______________ /

Москва 2013

АННОТАЦИЯ

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

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

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

В главе 2 обсуждаются принципы разрабатываемого метода поиска молекулярно-генетических маркеров. Дается обоснование условиям поиска и критериям отбора результатов. Вводится понятие критерия оценки приоритетности использования праймеров для изучения ДНК-полиморфизма – TVmax. Приводится описание реализации на языке Си алгоритмов поиска праймеров на основе полногеномных последовательностей по заданному префиксу, виртуальной ПЦР и сортировки полученных праймеров в порядке снижения их приоритетности для использования в ПЦР. Дается оценка производительности алгоритма виртуальной ПЦР по результатам профилирования. Описывается реализация на Си следующих алгоритмов поиска подстроки в строке: примитивного алгоритма, алгоритма Кнута-Морриса-Пратта, алгоритма Бойера-Мура, турбо-алгоритма Бойера-Мура, алгоритма Чжу-Такаоки, алгоритма GRASPM, алгоритма быстрого поиска, алгоритмов сдвига-или и Карпа-Рабина, а также ассемблерные реализации примитивного алгоритма и алгоритма Кнута-Морриса-Пратта. Приводятся результаты сравнения быстродействия этих алгоритмов, с библиотечной функцией strstr. Описывается принцип распараллеливания циклического участка алгоритма виртуальной ПЦР на основе технологии Open Multi-Processing.

В главе 3 описываются условия проведения тестирования программ по разработанным алгоритмам на примере поиска праймеров для выявления полиморфизма у растения Arabidopsis thaliana (L.) Дается характеристика объекта исследования. Описываются условия поиска и полученные результаты.

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

В приложении представлен полный текст исходного кода программ на языке Си по разработанным алгоритмам: первичного поиска праймеров, поиска теоретических ПЦР-фрагментов по найденным праймерам и отбора оптимальных праймеров. Также представлены листинги всех алгоритмов поиска подстроки, используемых в работе, и алгоритма сортировки с использованием 2-3 дерева.

ОГЛАВЛЕНИЕ

1. Аналитический обзор литературы.. 8

1.1. Молекулярно-генетические маркеры.. 8

1.1.1. Требования, предъявляемые к молекулярным маркерам.. 8

1.1.2. Анализ полиморфизма с помощью ПЦР.. 9

1.2. Стандартные форматы представления биологических последовательностей. 19

1.2.1. Формат FASTA.. 19

1.2.2. Формат FASTQ.. 22

1.2.3. Формат GenBank. 23

1.3. Биоинформационное программное обеспечение. 23

1.3.1. Программное обеспечение Vector NTI. 24

1.3.2. Программное обеспечение UGENE.. 26

1.3.3. Программное обеспечение Primer Express. 28

1.3.4. Программное обеспечение OLIGOPrimer Analysis Software. 28

1.3.5. Программное обеспечение Visual Cloning 2000. 28

1.3.6. Программное обеспечение DnaSP.. 31

Выводы к первой главе. 31

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

2.1. Обоснование выбора условий поиска и критериев сортировки праймеров. 33

2.2. Приведение исходных данных к виду удобному для проведения поиска. 37

2.2.1. Преобразование исходного формата FASTA.. 38

2.2.2. Корректировка возможных ошибок и недопустимых значений входных данных 39

2.3. Способы представления промежуточных данных и результатов эксперимента. 40

2.4. Алгоритм первичного поиска праймеров. 41

2.5. Сортировка массива праймеров с использованием 2-3 дерева. 42

2.6. Алгоритм поиска теоретических ПЦР-фрагментов по найденным праймерам.. 45

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

2.6.2. Обзор алгоритмов точного поиска подстроки в строке. 49

2.6.2.1. Примитивный алгоритм.. 50

2.6.2.2. Алгоритм Кнута-Морриса-Пратта. 51

2.6.2.3. Реализация примитивного алгоритма поиска на ассемблере. 53

2.6.2.4. Реализация алгоритма Кнута-Морриса-Пратта на ассемблере. 55

2.6.2.5. Алгоритм Бойера-Мура. 58

2.6.2.6. Турбо-алгоритм Бойера-Мура. 63

2.6.2.7. Алгоритм Чжу-Такаоки. 65

2.6.2.8. Алгоритм GRASPM... 67

2.6.2.9. Алгоритм быстрого поиска. 68

2.6.2.10. Алгоритм сдвига-или. 69

2.6.2.11. Алгоритм Карпа-Рабина. 71

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

2.7. Автоматическое распараллеливание цикла for. 74

2.8. Алгоритм отбора оптимальных праймеров. 78

Выводы ко второй главе. 79

3. Отработка программ по разработанным алгоритмам на примере поиска праймеров для растения Arabidopsis thaliana (L.) 81

3.1. Характеристика объекта исследования. 81

3.2. Входные данные и условия поиска. 81

3.3. Анализ результатов поиска. 82

Выводы к третьей главе. 85

ЗАКЛЮЧЕНИЕ.. 86

СПИСОК ЛИТЕРАТУРЫ... 88

ПРИЛОЖЕНИЕ.. 94

Исходный код программы преобразования формата FASTA на Си. 94

Исходный код программы первичного поиска праймеров на Си. 95

Исходный код программы сортировки с использованием 2-3 дерева на Си. 97

Исходный код программы поиска теоретических ПЦР-фрагментов по найденным праймерам на Си 105

Исходный код программы поиска теоретических ПЦР-фрагментов по найденным праймерам с распараллеленным циклом на Си. 118

Исходный код программы отбора оптимальных праймеров на Си. 131

Исходный код ассемблерной реализации примитивного алгоритма. 133

Исходный код ассемблерной реализации алгоритма Кнута-Морриса-Пратта. 134

ВВЕДЕНИЕ

Разнообразие организмов обусловлено изменчивостью последовательностей ДНК и влиянием факторов среды. Генетическая изменчивость значительна, и каждый организм данного вида, за исключением клонов, несет уникальные последовательности ДНК. ДНК-варианты являются следствием мутаций, происходящих вследствие замены одного нуклеотида (однонуклеотидный полиморфизм – single nucleotide polymorphisms, SNP), вставок или потерь фрагментов ДНК разной длины (от одного до нескольких тысяч пар нуклеотидов), а также дупликаций или инверсий фрагментов ДНК.

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

• Оценка генеалогических связей;

• Идентификация сортов растений и пород животных;

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

• Оценки изменчивости как внутри популяции, так и между различными популяциями;

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

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

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

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

· Определить входные данные и условия поиска;

· Разработать алгоритмы, позволяющие осуществлять подбор праймеров для ПЦР;

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

· Провести тестирование разработанных алгоритмов на реальном объекте исследований.