Введение
1 Введение, постановка задачи и результаты 9
1.1 Биологическая мотивация 9
1.1.1 Последовательности ДНК и их свойства 10
1.1.2 Описание эксперимента 13
1.1.3 Постановки задач 16
1.2 Математическая формализация и общие определения 18
1.2.1 Весовая функция для ДНК-стеблей 19
1.2.2 Стебельное сходство ДНК-последовательностей 20
1.2.3 ДНК-коды, основанные на стебельном сходстве 23
1.2.4 Постановки задач 25
1.3 Метод случайного кодирования для ДНК-кодов 26
1.4 Основные результаты диссертации 29
1.4.1 Глава 2 31
1.4.2 Глава 3 33
1.4.3 Глава 4 36
1.4.4 Глава 5 37
1.4.5 Глава 6 40
1.5 Исторический обзор 43
2 Конструкции ДНК-кодов для стебельного расстояния 50
2.1 Обозначения и определения 50
2.2 Кодовые конструкции для ДНК-кодов, основанных на аддитивном стебельном 1-сходстве 52
2.2.1 ДНК-коды с проверкой на четность 52
2.2.2 Коды Рида-Маллера первого порядка 54
2.3 Объем ДНК-кодов для фиксированного сходства 62
2.4 Субоптимальные ДНК-коды, основанные на неаддитивном стебельном w-сходстве 68
3 Неасимптотические задачи для аддитивного стебельного 1 -сходства 73
3.1 Аддитивное стебельное 1-сходство и его основные свойства 74
3.2 Вычисление объемов сфер 76
3.3 Неасимптотические оценки объема сферы 80
3.4 Асимптотика объема сферы 83
3.5 Объем ДНК-кода для фиксированного расстояния 87
4 Границы скорости ДНК-кодов для аддитивного стебельного 1 -сходства 91
4.1 Обозначения, определения и примеры 91
4.2 Формулировки результатов 93
4.3 Доказательство теоремы 4.1 94
4.4 Доказательство теоремы 4.2 98
4.4.1 Граница случайного кодирования 98
4.4.2 Вычисление явного вида границы 100
4.5 Доказательства теорем 4.3 и 4.4 105
5 Границы скорости ДНК-кодов для аддитивного стебельного ш-сходства 110
5.1 Обозначения, определения и примеры 111
5.2 Формулировки результатов 113
5.2.1 Границы скорости Rw(d) 113
5.2.2 Критическая доля расстояния (n, dn)w -кодов для примеров 1.2 и 1.3 116
5.3 Доказательство теоремы 5.1 118
5.4 Доказательство теоремы 5.2 120
5.4.1 Граница случайного кодирования 120
5.4.2 Нижняя оценка границы случайного кодирования 125
5.5 Анализ весовых образцов, основанный на критерии критической доли расстояния 126
180
5.5.1 Анализ таблиц 5.1-5.8 для аддитивного стебельного ги-расстояния 128
5.5.2 Выводы 131
5.6 Решение задачи максимизации (5.7)-(5.10) 132
6 Границы скорости ДНК-кодов для неаддитивного стебельного w-сходства 135
6.1 Обозначения и определения 136
6.2 Границы случайного кодирования 140
6.2.1 ДНК-коды для ансамблей Фибоначчи 140
6.2.2 Об объемах L -ансамблей Фибоначчи 143
6.2.3 Граница случайного кодирования для L -ансамбля Фибоначчи 144
6.2.4 Граница случайного кодирования для ДНК (п, dn)^ -кодов 146
6.3 Анализ весовых образцов, основанный на критерии критической доли расстояния 147
6.3.1 Анализ таблиц 5.1-5.8 для неаддитивного стебельного w -расстояния 149
6.3.2 Выводы 150
6.4 Доказательство теоремы 6.1 150
6.4.1 Общая схема доказательства 150
6.4.2 Доказательство леммы 6.2 153
6.4.3 Доказательство леммы 6.3 155
6.4.4 Доказательство леммы 6.4 159
6.5 Обобщение теоремы 6.1 162
6.5.1 Верхние границы для решений линейных рекуррентных уравнений 162
6.5.2 Граница случайного кодирования для L -ансамблей в общем случае 169
Литература 172
Работы автора по теме диссертации 178
