Введение
Глава 1. Обзор литературы 13
1.1. Выравнивание символьных последовательностей 13
1.1.1. Постановка задачи парного выравнивания символьных последовательностей 13
1.1.2. Использование динамического программирования при выравнивании последовательностей 16
1.1.3. Весовые матрицы замен 19
1.2. Базы данных эталонных выравниваний 20
1.2.1. Общие сведения 20
1.2.2. Обзор существующих баз данных 21
Глава 2. Эталонные выравнивания 24
2.1. База данных PREFAB-P 25
2.1.1. Общие сведения 25
2.1.2. Методика подготовки базы PREFAB-P -2 — Оглавление —
2.1.3. Структура базы данных PREFAB-Р 29
2.2. Модельные эталонные выравнивания 31
2.2.1. Общие сведения 31
2.2.2. Предварительные эксперименты 31
2.2.3. Общая схема построения набора модельных данных 32
2.2.4. Внесение мутаций-«замен» в символьные последовательности 34
Глава 3. Алгоритм и реализация 36
3.1. Исследование алгоритма Смита-Ватермана 36
3.1.1. Общие сведения 36
3.1.2. Методика проведения экспериментов 36
3.1.3. Результаты 37
3.2. Постановка новой задачи 38
3.2.1. Исключение параметра GEP 38
3.2.2. Формальная постановка задачи 40
3.3. Решение задачи построения набора выравниваний-кандидатов 40
3.3.1. Общие сведения 40
3.3.2. Алгоритм построения множества Парето-оптимальных выравниваний 42
3.3.3. Алгоритм выделения основных выравниваний 45
3.3.4. Оценка вычислительной сложности алгоритмов 46
3.4. Реализация 49
3.4.1. Общие сведения 49
3.4.2. Пользовательский интерфейс комплекса PARCA 50
3.4.3. Программный интерфейс комплекса PARCA 51
3.4.4. Детали реализации 54
3.5. Вспомогательные алгоритмы 55
3.5.1. Определение штрафа GOP для соответствующих выравниваний Смита-Ватермана 55
3.5.2. Выделение общей части основных выравниваний 58
Глава 4. Компьютерные эксперименты 67
4.1. Методика 67
4.1.1. Общие сведения 67
4.1.2. Построение выравниваний 67
4.1.3. Анализ полученных данных 69
4.2. Анализ модельных данных 69
4.3. Анализ выравниваний из PREFAB-P 70
4.4. Обсуждение результатов 72
Заключение 87
Список таблиц 89
Литература
