Теоретико-вероятностные и комбинаторные задачи теории кодирования ДНК-последовательностей

• Автор: Воронина, Анна Никитична
• Шифр специальности: 01.01.05
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 181 с. : ил.

Список обозначений

В настоящей работе используется следующая система обозначений. Нумерация определений, утверждений, формул и рисунков начинается заново в каждой главе, и перед каждым номером ставится номер соответствующей главы. Таким образом, формулы в главе 1 будут иметь номера (1.1), (1.2) и т.д. При этом различные типы утверждений имеют независимую нумерацию, например: теорема 1.1, теорема 1.2, лемма 1.1 и т.д.

Конец доказательства обозначается символом □

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

Общие обозначения

равенство по определению множество целых чисел {1, 2

стандартный д-ичпый алфавит (0,1

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

последовательность, сопряженная к х

и>(а, Ь) весовая функция на множестве нар А2Ч
3(х, у) произвольная стебельная функция сходства на
0(х, у) произвольная стебельная функция расстояния на А™
X = ||зд(и)|| произвольный ДНК-код, г £ [гг], и £ [IV], длины п и объема N
а:(у) у'-тое кодовое слово кода X
N(71, О) максимальный объем ДНК-кода длины п с расстоянием Л

скорость ДНК-кода для доли расстояния й > О математические ожидание £
Обозначения к главе
{А,С,в,Т} 10 ДНК-оенования: аденин (Л), цитозин (С), гуанин (б), тимидин (Т)
£(х, у) 11 энергия гибридизации ДНК-цепочек ж и у
X 10 ДНК-цепочка, сопряженная к цепочке х
Н(х, у) 21, (1.4) сходство Хэмминга
Ы(х,у) 21, (1.4) индикатор равенства элементов ж, и /д
РЛп,В) 26, (1.7) вероятность того, что расстояние между случайной последовательностью и € А™ и ее сопряженной и меньше О
Р2(П,0) 26, (1.7) вероятность того, что расстояние между двумя случайными последовательностями и, V £ А” меньше В
Обозначения к главе
5(х,у) 51, (2.1) аддитивное стебельное 1 -сходство между ж и у
4(Х>У) 51, (2.1) индикатор равенства г -тых стеблей хну
Щя'.,у) 51, (2.2) а/ущтивное стебельное 1 -расстояние между хну
>?’(*, у) 51, (2.2) индикатор неравенства г -тых стеблей хну
(п, £>)г -код 52, (2.4) ДНК-код длины п с аддитивным стебельным 1 -расстоянием
N71,0) 52 максимальный объем (п, О) а
Мя(п) 52 д -ичный код с проверкой на четность, подмножество А"
сад 54 ноле Галуа порядка р
Р(г, тп) 55 множество многочленов от тп переменных порядка < г, заданных на в(4), с коэффициентами и значениями в ОТг(4)
Яа (г, тп) 56 код Рида-Маллера над GF(4) г-ого порядка длины 4га
<5(1)(ж,у) 69 неаддитивное стебельное 1 -сходство между ж и у
Т>Рх, у) 69 неаддитивное стебельное 1 -расстояние между хну
(п, Б)Р -код 69 ДНК-код длины п с нсадцитивным стебельным
1-расстоянием Б N(71, Б) 69 максимальный объем (п,
В(х,у) 70 блоковое сходство между хну
(п, Б)*3 -код 70 ДНК-код длины п с блоковым расстоянием Б
Ыв(п,Б) 70 максимальный объем (п, Б)в
Обозначения к главе
5х(х,1/) 74, (3.1) аддитивное стебельное 1-сходство между х и у
з}(х,у) 74, (3.1) индикатор равенства г -тых стеблей х и у
Т>{х,у) 74, (3.2) аддитивное стебельное 1-расстояние между хну
вя(п,г) 76 объем сферы радиуса г в метрике Т>г в пространстве А"
Вч(п,г) 105, (4.45) объем шара радиуса г в метрике Б1 в пространстве А™
О 76 элемент (0,0

упорядоченное множество к целых чисел Т(з,к) 77, (3.9) множество | : и >2, и = 3 + &
Г "" к11
Т2(в,к) 77, (3.10) множество | >0, и > 1, и = п — (.% + к) >
во (п,г) 78 сфера с центром в точке 0 радиуса г в А" в метрике Б1
Рр(п,Б) 85,(3.27) распределение вероятностей
Рр{п,Б) 85,(3.27) функция распределения
РпП{Б) 86 биномиальное распределение вероятностей
(п, ИД-код 87 ДНК-код длины п с аддитивным стебельным 1-расстоянием Б
Ых(п,Б) 87 максимальный объем (п, Л) 1-кода
Обозначения к главе
${х,у) 92, (4.1) аддитивное стебельное 1-сходство между х и у
з}(х,у) 92, (4.1) индикатор равенства *-тых стеблей хну
Т>{х,у) 92, (4.2) аддитивное стебельное 1-расстояние между хну

л . Г п . ГО +11
= ішп <п- В- 1; —

у -Ь

7 > 1-
Кроме того, для любого п, п> 2,
с4 ж* ( 1 - с5 /3') < 8,(п, п - 1) < с4 Xі ( 1 + с5 /3‘) ,

* (д +1) + /(д — і)(д + з)
І'Д ' ' . 1 - —— / и ч
2/(д- і)(д + з)
с5 = (д + 1) ~ л/(д — г)(д + 3) > о
уДя ~ 1)(? + з) + (? +1)
х л ? —1 + л/(д —3 )( + з)
А у/д + З— /д — 1 /<7 + о + /<7
> 0.
Асимптотические выражения для объема сферы при растущей длине кодовых слов п и постоянном радиусе В имеют вид:
Теорема 3.3: Для любого четного полоэюителъного В , В = 2,4

8,(71, В) = — (1 + 0(1)) , п-> оо;
для любого нечетного положительного В, Г) = 1,3
„ч (ф +2)пёиа- 1)+1 , =, ч,
8,(тг, В) = — (1 + о(1)) , п -> оо,
где (іі
Теорема 3.3 позволяет получить следующие оценки максимального объема Лгі (п, В) ДНК-кодов, основанных на аддитивном стебельном 1 -сходстве, для случая постоянного расстояния В и растущей длины кодовых слов п:
Теорема 3.4: (Граница случайного кодирования) Для любого нечетного В, В = 3,5
Мп’ * АпЦд-іу* + ®(1)) ’ П “* °°’