Содержание к диссертации
Введение
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
- Математическая формализация и общие определения
- Объем ДНК-кодов для фиксированного сходства
- Неасимптотические оценки объема сферы
- Критическая доля расстояния (n, dn)w -кодов для примеров 1.2 и 1.3
Введение к работе
Актуальность темы В диссертации исследуются теоретико-вероятностные и комбинаторные задачи теории кодирования, возникающие в приложениях молекулярной биологии при рассмотрении экспериментов, существенно использующих специальные свойства молекул ДНК (а также РНК и некоторых других).
В упрощенном виде молекулу (одинарную цепочку) ДНК можно считать последовательностью с элементами из алфавита {А, С, G, Т}. ДНК-цепочки являются направленными, а их важнейшим свойством является способность разнонаправленных цепочек сращиваться в двойные спирали ДНК, или ДНК-дуплексы в процессе ДНК-гибридизации. Основой этого процесса является образование водородных связей между так называемыми комплементарными элементами ДНК-цепочек, а именно элементами А и Т, а также С и G. При этом прочность образовавшегося дуплекса определяется величиной, называемой энергией гибридизации и зависящей от числа образовавшихся водородных связей. Сопряженной к данной ДНК-цепочке называется ДНК-цепочка, полученная путем изменения направления исходной ДНК-цепочки и последующей замены всех элементов в ней на комплементарные. Известно, что максимальная энергия ДНК-гибридизации достигается при образовании дуплексов Ватсона-Крика, то есть дуплексов, состоящих из взаимно-сопряженных ДНК-цепочек.
В биологических экспериментах, использующих свойство ДНК-гибридизации, возникновения кроссгибридизации - то есть сращивание ДНК-цепочек, не являющихся взаимно-сопряженными, - следует избегать, так как она приводит к ошибкам в результатах опытов. Следовательно, желательно формирование таких наборов одинарных ДНК-цепочек [ДНК-ансамблей), что при заданных температурных (энергетических) условиях эксперимента только энергия гибридизации между сопряженными ДНК-цепочками будет достаточна для формирования устойчивых дуплексов, а кроссгибридизация будет невозможна. Это обстоятельство, наряду с другими предпосылками, привело к пониманию, что возникающие в таких биологических экспериментах ДНК-ансамбли, с математической точки зрения, могут быть естественным образом интерпретированы как специальный вид кодов.
В самом общем виде одну из основных задач теории кодирования можно описать следующим образом. Фиксируется некоторый д-ичный алфавит Aq = {0,..., q — 1} и рассматривается пространство д-ичных последовательностей длины п: А = {х = (х\,..., хп), Х{ Є Aq}. Ко-
дом X называется некоторый набор таких последовательностей (кодовых слов) - подмножество А: X С А. На множестве А задается функция расстояния р(х,у), ж, у Є А. Как правило, на А также можно определить комплементарную р(х,у) функцию сходства. Говорят, что код X является кодом с расстоянием D > 0, если р(х, у) > D для любых кодовых слов х = у, ж, у Є X.
Пусть N(n, D) есть максимальный объем кода (то есть максимальное число кодовых слов в коде) с фиксированными расстоянием D и длиной кодовых слов п. Ставится задача исследования скорости кода R(d): то есть логарифмической асимптотики числа N(n,dn) при фиксированной доле расстояния d > 0 и растущей длине кодовых слов:
, ч л — lg„ N(n,dn)
R(d) = lim -^—— -, d>0.
П-^СХ) fi
На сегодняшний день эта задача все еще не имеет окончательного решения, а основные достижения состоят в построении верхних и нижних границ скорости кодов. Следует, кроме того, отметить, что основным направлением исследования было изучение данных вопросов для так называемого расстояния Хэмминга1, которое определяется как число несовпадающих позиций между двумя g-ичными последовательностями.
Вторым важным направлением исследований является поиск кодовых конструкций, обладающих параметрами, близкими к теоретически достижимым, либо какими-то специальными свойствами, в зависимости от предполагаемых приложений. Здесь не существует общей теории построения кодов, а каждый пример конструкции уникален, причем обычно существует лишь для весьма узкого диапазона параметров кода.
Задача исследования указанной проблематики для "нехэммингов-ских" функций расстояния и сходства изучена слабо, главным образом в связи с отсутствием до последнего времени практической потребности в результатах такого рода.
Рассматриваемые нами постановки возникли из некоторых прикладных вопросов молекулярной биологии и ДНК-программирования. Принято считать, что первый пример практического алгоритма, позволяющего эффективно решать математическую задачу (так называемую "задачу почтальона") методами ДНК-программирования был по-
1Ф. Дж. Мак-Вильяме, Н. Дж. А. Слоэн, Теория кодов, исправляющих ошибки, Москва: Связь, 1979.
строен в работе Адлемана2 в 1994г. Вследствие относительной новизны данной области исследований устоявшихся канонов математического моделирования ДНК-цепочек и их взаимодействия между собой еще не сложилось. Основные принципы, однако, ясны: ДНК-цепочки могут быть представлены как последовательности из четверичного алфавита Лі = {0,1,2,3}. При этом основные свойства ДНК-цепочек, а также ограничения, вытекающие из потребностей биологических приложений, должны быть отражены в специальных требованиях к конструкции (определению) кода, а энергия ДНК-гибридизации сопоставляется соответствующей функции сходства на пространстве четверичных последовательностей Л!\. Первые попытки создания модели ДНК-кодов были предприняты в рамках уже хорошо изученной метрики Хэммин-га3'4. Специфика задачи учитывалась путем определения понятия пар взаимно сопряженных ДНК-последовательностей и наложения на код некоторых дополнительных условий.
Этот подход, однако, никак не учитывал особенностей взаимодействия цепочек ДНК и в дальнейшем исследования пошли по пути разработки функции сходства, наиболее близко к действительной ситуации моделирующей реальные принципы гибридизации цепочек ДНК, с одной стороны, и поддающейся математическому изучению, с другой.
Первая функция сходства, учитывающая особенности взаимодействия цепочек ДНК, была предложена в работах Дьячкова5 и Вилен-кина6 (здесь и далее, ссылаясь на работы, имеющие больше одного авторов, мы для краткости будем указывать в тексте только первого автора). Она была близка к сходству Хэмминга с тем отличием, что каждому типу совпадающих символов присваивался свой вес w(a), а Є A±, в общей сумме, определяющей такое сходство.
Следующим шагом в эволюции моделей ДНК-кодов стало примене-
2L. Adleman, "Molecular Computation of Solutions to Combinatorial Problems," Science, vol. 266. pp. 1021-1024, 1994.
3A. Marathe, A. E. Condon, R. M. Corn, "On combinatorial DNA design," J. Сотр. Biol, vol. 8, pp. 201-219, 2001.
4V. V. Rykov, A. J. Macula, С M. Korzelius, D. С Englehart, D. С Torney, P. S. White, "DNA sequences constructed on the basis of quaternary cyclic codes," в Proc. of the 4th World Multiconference on Systematics, Cybernetics, and Informatics, SCI 2000/ISAS 2000, Орландо, Флорида, 2000.
5A. G. D'yachkov, D. C. Torney, "On similarity codes," IEEE Trans. Inform,. Th., vol. 46, n. 4, pp. 1558-1664, 2000.
6П. А. Виленкин, "Асимптотические задачи комбинаторной теории кодирования и теории информации," Диссертация на соискание ученой степени к.ф.-м.н. Москва, МГУ им. М.В.Ломоносова. 2000.
ниє неаддитивной функции, так называемого сходства выпадений . Здесь сходство между двумя ДНК-цепочками определяется как длина наибольшей общей подпоследовательности (элементы которой стоят на любых, не обязательно одинаковых, позициях в этих ДНК-цепочках). Такой подход позволяет учесть возможные на практике сдвиги цепочек друг относительно друга и образование петель на одинарных цепочках (так называемую вторичную структуру ДНК-дуплекса).
Еще один вариант определения сходства можно найти в работе Дьячкова 2005 г.8. Сходство между двумя ДНК-цепочками, называемое сходством блоков, в этом случае определялось как длина общей блочной подпоследовательности, то есть такой, что любые два ее соседние элемента либо одновременно являются соседними, либо одновременно разделены в исходных ДНК-цепочках.
Наиболее продвинутой биологической моделью, позволяющей с максимальной точностью вычислить энергию гибридизации ДНК-цепочек, на сегодняшний день считается так называемая модель "ближайшего соседа"9. В общих чертах, согласно этой теории, энергия гибридизации может быть рассчитана как сумма термодинамических весов всех образовавшихся при гибридизации стеблей. Стебель формируется, когда два последовательных основания (элемента) одной ДНК-цепочки связываются с двумя последовательными основаниями второй цепочки; термодинамические веса разных видов (в зависимости от вида входящих в него видов оснований) стеблей известны заранее из постановочных экспериментов.
Таким образом, как мы видим, "хорошая" функция сходства для ДНК-кодов должна зависеть не от числа совпадающих символов в ДНК-последовательностях, а от количества совпадающих стеблей, или блоков длины 2 в этих последовательностях. В настоящей работе мы исследуем три функции сходства, построенные с учетом этого ключевого принципа модели "ближайшего соседа" (подробнее о них можно прочитать во второй части настоящего автореферата).
7А. G. D'yachkov, P. L. Erdos, A. J. Macula, V. V. Rykov, D. С. Torney, С. S. Tung, P. A. Vilenkin, P. S. White, "Exordium for DNA Codes," J. Comb. Optimization, vol. 7, n. 4, pp. 369-379, 2003.
8A. Г. Дьячов, П. А. Виленкин, И. К. Исмагилов, Р. С. Сарбаев, А. Макула, Д. Торни, С. Уайт, "О ДНК кодах," Проблемы Передачи Информации, т. 41, н. 4, с. 57-77, 2005.
9К. J. Breslauer, R. Frank, Н. Blocker, L. A. Markey, "Predicting Duplex DNA Stability from the Base Sequence," Proc. National Academy of Sciences USA, vol. 83, pp. 3746-3750, 1986.
Требуемые на практике ДНК-ансамбли, таким образом, могут рассматриваться как коды с расстоянием для специальной функции расстояния, комплементарной соответствующей "стебельной" функции сходства. При этом, исходя из практических соображений, эти коды должны состоять из пар взаимно-сопряженных ДНК-последовательностей и не должны содержать самосопряженных кодовых слов. Такие коды мы называем ДНК-кодами. Отметим, что указанное ограничение является достаточно специфичным и накладывает дополнительные условия как при исследовании асимптотических границ скорости кодов, так и при поиске конкретных кодовых конструкций.
Для всех изучаемых нами функций сходства мы будем интересоваться поведением скорости ДНК-кодов, а для аддитивного стебельного 1-сходства также построим два примера кодовых конструкций.
Отметим, что существуют и другие направления исследований ДНК-последовательностей методами теории кодирования. Так, например, в работе Миленкович10 изучается вопрос о построении ансамблей ДНК-цепочек, с вероятностью, близкой к единице (эмпирически), исключающих самогибридизацию, то есть образование склеек внутри одной цепочки.
В целом, существенное внимание уделяется практическим алгоритмам решения конкретных задач, как например, алгоритмы определения длины наибольшей общей подпоследовательности между двумя цепочками ДНК11. Разрабатываются комбинаторные, эвристические, биологические методы нахождения ДНК кодов - их можно найти, например, в работах Кадерали12 и многих других авторов, программные решения для генерирования ДНК-кодов предложили Андронеску13, Бишоп14 и другие исследователи.
10О. Milenkovic, N. Kashyap, "DNA Codes that Avoid Secondary Structures," в Proc. 2005 IEEE Int. Syw,p. Information Theory, Аделаида, Южная Австралия, Австралия, 2005, pp. 288-292.
US. В. Needleman, С. D. Wunsch, "A general method applicable to the search for similarities in the amino-acid sequences of two proteins," J. Мої. Biol., vol. 48, pp. 443-453, 1970.
12L. Kaderali, A. Deshpande, J. Nolan, P. White, "Primer-design for multiplexed genotyping," Nucleic Acids Res., vol. 31, pp. 1796-1802, 2003.
13M. Andronescu, R. Aguirre-Hernandez, A. Condon, et al., "RNAsoft: a suite of RNA secondary structure prediction and design software tools Nucleic Acids Res., vol. 31, pp. 3416-3422, 2003. Также доступно на: .
14M. Bishop, A. Macula, T. Renz, SynDCode Suite, 2006.
Как уже отмечалось, рассматриваемая задача возникла при построении математических моделей некоторых экспериментов молекулярной биологии. ДНК-коды находят много новых применений в активно развивающихся направлениях науки, таких как определение функции генов15, самосборка наноструктур16, ДНК-программирование2'17, хранение информации18, ДНК-метки (DNA taggants)19 и другие.
Данная область исследований является сравнительно новой и бурно развивающейся, и единой устоявшейся модели ДНК-кодов как математического объекта на сегодняшний день нет. Отметим, однако, что для указанных приложений интерпретация требуемых ДНК-ансамблей как специального вида кодов с заданным минимальным расстоянием для некоторой нетипичной функции сходства возникает совершенно естественным образом. Предлагаемые нами функции сходства, в отличие от предыдущих примеров, учитывают ключевой принцип вычисления энергии гибридизации в модели "ближайшего соседа". Особо укажем, что адекватность рассматриваемой нами модели лишний раз подтверждается тем обстоятельством, что идеологически она совпадает с биологическими определениями ДНК-кодов, данными, например, в работе Кадерали12, и отвечает принципам, на которых построены прототипы ДНК-алгоритмов вычисления комбинаторных задач высокой сложности2'17. Таким образом, задача изучения ДНК-кодов является актуальной и востребованной, а предлагаемые в диссертации математические модели позволяют с наибольшей на сегодняшний день точностью описывать возникающие в приложениях биологические объекты.
Доступно на: .
15R. Eason, N. Pourmand, W. Tongprasit, et al., "Characterization of synthetic DNA bar codes in Saccharomyces cerevisiae gene-deletion strains PNAS, vol. 101, pp. 11046— 11051, 2004.
16M. Valignat, O. Theodoly, J. Crocker, et al., "Reversible self-assembly and directed assemblyof DNA-linked micrometer-sized colloids," PNAS, vol. 102, pp. 4225-4229, 2005.
17Q. Ouyang, P. D. Kaplan, S. Liu, A. Libchaber, "DNA solution of the maximal clique problem," Science, vol. 278, pp. 446-449, 1997.
18M. Mansuripur, P. K. Khulbe, S. M. Kuebler, J. W. Perry, M. S. Giridhar, N. Peyghambarian, "Information Storage and Retrieval using Macromolecules as Storage Media," Optical Data Storage Conference, Ванкувер, Канада, 2003.
19A. Macula, S. Gal, С Andam, T. E. Renz, M. A. Bishop, "PCR nonadaptive group testing of DNA libraries for biomolecular computing and taggant applications," Discrete Mathematics, Algorithms and Applications, vol. 1, n. 1, pp. 59-69, 2009.
Цель работы К основным целям настоящей диссертации относятся: изучение асимптотического поведения максимального объема ДНК-кодов для трех стебельных функций сходства; вычисление объемов сфер для метрики, задаваемой аддитивным стебельным 1-сходством, в пространстве g-ичных последовательностей; исследование вопроса о построении кодовых конструкций для ДНК-кодов, основанных на аддитивном стебельном 1-сходстве.
Научная новизна Основные результаты диссертации являются новыми и состоят в решении следующих задач для специального класса кодов - ДНК-кодов - для трех различных функций сходства на пространстве g-ичных последовательностей:
Получены две конструкции ДНК-кодов, основанных на аддитивном стебельном 1-сходстве. Найден максимальный объем ДНК-кодов, основанных на аддитивном стебельном 1-сходстве, для случая фиксированного сходства.
Найдены явные формулы для выражения объема сфер для метрики, задаваемой аддитивным стебельным 1-сходством, в пространстве g-ичных последовательностей Л1 получены неасимптотические оценки для таких объемов сфер, а также асимптотические формулы для случая постоянного радиуса.
Сформулированы верхние и нижние оценки максимального объема ДНК-кодов, основанных на аддитивном стебельном 1-рас-стоянии, для случая постоянного расстояния (нулевой доли расстояния). Построены и исследованы верхние и нижние границы скорости ДНК-кодов, основанных на аддитивном стебельном 1-расстоянии.
Разработан метод случайного кодирования с применением цепей Маркова. Опираясь на него, построены и исследованы верхние и нижние границы скорости ДНК-кодов, основанных на аддитивном стебельном ^-расстоянии.
С применением специального класса ДНК-ансамблей Фибоначчи построена нижняя граница скорости ДНК-кодов, основанных на неаддитивном стебельном ^-расстоянии.
Методы исследования Результаты диссертации получены с использованием различных методов построения границ скорости кодов
с расстоянием (Варшамова-Гилберта, Хэмминга, Плоткина, Элайе-са, Синглтона), стандартных методов исследования логарифмической асимптотики, теорем о больших уклонениях для сумм независимых и зависимых случайных величин, методов выпуклого анализа. При доказательстве границы Варшамова-Гилберта для аддитивного стебельного ^-расстояния был разработан метод случайного кодирования на основе марковских цепей. Это потребовало развития новой техники доказательства теорем подобного рода. При вычислении явных формул для объемов сфер для метрики, задаваемой аддитивным стебельным 1-сходством, были применены комбинаторные методы подсчета числа g-ичных последовательностей специального вида, в частности, найдены рекуррентные уравнения и явные выражения для числа таких последовательностей. Для построения графиков границ скорости ДНК-кодов также были использованы некоторые численные методы.
Теоретическая и практическая ценность Диссертация носит теоретический характер. Полученные результаты и разработанные техники исследования кодов могут представлять интерес для специалистов, занимающихся теоретико-вероятностной и комбинаторной теорией кодирования, и, кроме того, могут быть использованы для некоторых практических задач молекулярной биологии.
Апробация работы Результаты диссертации неоднократно докладывались на Большом семинаре кафедры теории вероятностей мехмата МГУ (2008г. и 2009г., руководитель - член-корреспондент РАН А.Н.Ширяев), на семинаре по теории кодирования в Институте Проблем Передачи Информации РАН (2008г. и 2009г., руководитель -профессор Л. А. Бассалыго) и на семинаре по теории вероятностей и статистической физике в МГУ им. Ломоносова (2007г. и 2010г., руководитель - профессор Б. М. Гуревич). Полученные результаты были представлены на международном симпозиуме по алгебраической и комбинаторной теории кодирования АССТ-11 (Пампорово, Болгария, 2008), вошли в сборник трудов конференции 31-ой конференции молодых ученых и специалистов ИППИ РАН ИТиС'08.
Публикации По теме диссертации опубликовано 4 работы, список которых приведен в конце настоящего автореферата.
Структура и объем диссертации Диссертация состоит из списка обозначений, шести глав, разбитых на параграфы, списка литературы, содержащего 63 наименования, списка работ автора по теме диссертации и оглавления. Общий объем диссертации составляет 181 страницу.
Математическая формализация и общие определения
В этом разделе мы формализуем описанную в предыдущем разделе конструкцию. Представляя ДНК-цепочки как четверичные последовательности, мы определим для них операцию сопряжения последовательностей, введем специальную стебельную функцию сходства. Будет показано, каким образом энергия гибридизации ДНК-цепочек представляется с помощью этой функции сходства и как формализуется понятие ДНК-кодов. Мы обсудим специфику вводимой математической модели по сравнению с классической, основанной на сходстве Хэмминга, и то, как это влияет на применяемые методы и техники доказательства. Наконец, мы сформулируем, решением каких задач мы будем интересоваться в данной работе. Символ = обозначает равенство по определению, [?г] = {1, 2,... ,п} обозначает множество целых чисел от 1 до п . Пусть q — 2,4,... - произвольное фиксированное четное число и Ап — {0,1,...,д — 1} - стандартный алфавит объема \Aq\ = q. Стандартный символ \и\ (\и\) обозначает наибольшее (наименьшее) целое число и ( и). Как уже было сказано выше, мы можем рассматривать ДНК-цепочки как последовательности с элементами (буквами) из алфавита {А, С, G, Т} . Для удобства изложения, будем считать, что ДНК-последовательности состоят из элементов множества А± = {0,1,2,3} , вводя соответствие: В некоторых главах данной работы мы ограничимся рассмотрением только этого ансамбля, в других — рассмотрим более общий случай алфавита Aq . Понятие комплементарное оснований в ДНК-цепочках мы формализуем, вводя операцию сопряжения на рассматриваемом алфавите: В общем случае можно считать, например, что для любого х Є Aq комплементарным будет элемент х = (q — 1) — х Є Aq . В некоторых случаях оказывается удобным опреде лить пары комплементарных элементов следующим образом: для любого г = О,1,..., q/2 комплементарные элементы определяются как 2г = 2г + 1 и 2г + 1 = 2г . Для последовательности х = (хг,Х2,-. ,хп-і,хп) Є Д определим сопряженную к ней последовательность ж = (жп,жп_і,... ,х2,хі) Є А, называемую также ее преобразованием Ватсона-Крпка. Если у = х, то х = у для любого х Є А1 . Если а; = х , то ж называется самосопряженной последовательностью. Если х ф х , то пара (ж , х) называется парой взаимно сопряженных последовательностей. Пусть w = w(a, b) 0, а, Ъ Є Aq , является весовой функцией такой, что
Условие (1.2) означает, что функция w(a,b) инвариантна относительно преобразования Ватсона-Крика. Пример 1.1: Простейшим примером является постоянная весовая функция w = w(a,b) = 1, т.е. условие (1.2) для которой, очевидно, выполняется. Изучению ДНК-кодов для такой весовой функции будут посвящены Главы (3)-(4). Пример 1.2: Пусть q = 4 . Рассмотрим пример весовой функции для посимвольного сходства, предложенного в работе [13]. Для любых о, b Є А+ = {0,1,2,3} определим Такой выбор значений весовой функции, для которой выполняется условие (1.2), отражает тот факт, что отношение числа водородных связей между основаниями А — Т (или, в нашем случае, 0 — 3) к числу водородных связей между С — G (1 — 2) равно 2:3. Пример 1.3: Пусть q = 4. Пример значений w(a, b), также удовлетворяющих условию (1.2) и В основе моделирования энергии гибридизации ДНК-последовательностей лежит понятие о стебельной функции сходства, формальное определение которой мы дадим ниже. В диссертации мы рассмотрим ДНК-коды, основанные на трех различных стебельных функциях сходства. В главах 3-4 мы изучим простейшее аддитивное сходство, соответствующее случаю постоянной весовой функции. В главе 5 речь пойдет об аддитивном сходстве для произвольной весовой функции (1.2). Глава 6 посвящена анализу случая неаддитивной весовой функции, которая, в отличие от предыдущих, позволяет учесть все виды дуплексов, изображенные на рис. 1.3. В любом случае, все три эти функции сходства основаны на подсчете весов допустимых стеблей, то есть совпадающих блоков длины 2 , состоящих из соседних символов сравниваемых последовательностей. В данном разделе будем использовать обозначение S(x, у), х, у Є А , для произвольной сюбелыюй функции сходства для ДНК-последовательностей. Само моделирование построено на следующем соответствии: Покажем, каким образом описанные нами ранее свойства энергии гибридизации (х,у) отражаются на стебельной функции сходства. Согласно свойству Е1, мы должны получить Это равенство всегда будет выполняться в силу выбора весовой функции (1.2), инвариантной относительно преобразования Ватсона-Крика. Согласно свойству Е2, что будет верно для любой разумным образом заданной функции сходства и в частности для рассматриваемых нами стебельных функций сходства, что мы покажем в соответствующих разделах работы. Согласно свойству ЕЗ, что будет верно в силу симметричности стебельной функции сходства (это свойство мы докажем в соответствующих разделах работы) и свойства инвариантности (1.2) весовой функции. Скажем несколько слов о специфике рассматриваемой нами аддитивной стебельной функции сходства.
Классическое сходство Хэмминга Н(х,у) между двумя последовательностями х,у Є .Д определяется как число совпадающих позиций: Аддитивное стебельное 1-сходство Si(x,y) между двумя последовательностями х, у Є А определяется уже не числом совпадающих элементов, но числом совпадающих стеблей: I 0, иначе. Это огличие оказывается существенным. Хотя общие принципы получения границ объема кода (см. Задачу 2 ) остаются теми же, нам приходится коренным образом обновить инструментарий, позволяющий эти принципы превратить в конкретные методы доказательств. Укажем лишь, чю для получения так называемой границы случайного кодирования в классическом случае достаточно рассматривать случайные последовательности с независимыми элементами. В случае аддитивного стебельного сходства, для получения в определенном смысле адекватной границы, нам пришлось использовать ансамбли случайных последовательностей, конструируемых как цепи Маркова со стационарной матрицей перехода и стационарным начальным распределением специального вида. Насколько известно автору, этот подход применен в теории кодирования впервые. Поскольку решение задач типа Задачи 1 в целом не имеет общих принципов и состоит в нахождении конкретных конструкций, в основе каждой из которых лежит уникальная идея построения кода, то изменение функции сходства предполагает либо попытки оценить новое сходство между словами в уже известных кодовых конструкциях, либо поиски кардинально новых типов кодов. Что касается неаддитивного сходства, то такие функции, основанные на совпадении символов, - сходство вставок-выпадений, блоковое сходство, — были исследованы в работах [6]-[8], [17].
И снова, исследование стебельного сходства, формальное определение которого мы приведем в разделе 1.4, подразумевает существенные изменения во всех известных - притом немногочисленных - принципах и методах получения границ объема кода и кодовых конструкций. Отметим, что в работе применяются ДНК-ансамбли специального вида, которые мы назвали ДНК-ансамблями Фибоначчи, польза от использования которых определяется спецификой стебельной функции сходства. Кроме функции сходства, нам потребуется также и функция расстояния Т (х,у), х, у Є Д . Мы будем определять ее следующим образом:
Объем ДНК-кодов для фиксированного сходства
Докажем следующий результат о максимальном объеме (п, D)х -кодов для случая фиксированного сходства, то есть для кодов с расстоянием D = п — s — 1 для некоторого фиксированного конечного положительного s . двумя различными способами. С одной стороны, рассмотрим все стебли (блоки длины 2) (xi(u), х-2(и)), и Є [1, ІУ]. Максимальное количество различных стеблей среди них- q2; пусть, без ограничения общности, первые j стеблей: (xi(u),X2{u)), и Є [l,j], j q2 , - все попарно различны и это максимальный такой набор попарно различных стеблей. Следовательно, если N j , то каждый из остальных N — j N — q2 стеблей (xi(u), Х2(и)), и Є [j + 1, Л "] будет совпадать с некоторым стеблем из первого указанного множества.
Таким образом, Аналогичным образом проведем рассуждение для всех позиций і Є [2, п — 1] и стеблей (xi(u),xi+i(u)) , uE[l,N], и получим С другой стороны, согласно определению ДНК-кода Объединяя это неравенство и (2.14), получим (2.11). Заметим теперь, что для п = 2 +1, L = 1,2,..., сходство 5і(ж(«), ж(и)) всегда четно для любого выбора и Є [1, N] . В самом деле, если для некоторого г Є [1, п — 1] то и Поэтому Si (ж (u), ж (it)) 2 ls/2\ = s — 1 для любого u Є [l,iV] для нечетных s. Пусть, без ограничения общности, х(и + N/2) = х(и), и Є [1, N/2]. Теперь мы можем уточнить оценку и формула (2.12) доказана. Если же п = 2t, t = 1,2,..., - четное, то пусть из кодовых слов х(и), и Є [N/2], ровно к, к JV/2, кодовых слов содержат самосопряженные стебли на позициях I и t + 1, то есть ровно для к индексов и Є [N/2] будет выполняться (xt(u),xt+i(u)) = (xt+\(u), Xt(u)). Тогда для всех остальных пар взаимно сопряженных кодовых слов аддитивное стебельное 1-сходство между ними четно и для нечетных 5 = 1,3,... Следовательно, оценивая как и в случае нечетных длин п, получим С другой стороны, рассмотрим множество всех "центральных" стеблей кодовых слов из X, как это было сделано в начале доказательства: {(хг(и),хг+і(и)), и Є [l,iV]}. Среди них содержится ровно 2к самосопряженных стеблей и N — 2к пар взаимно сопряженных стеблей. Если к q, то вклад самосопряженных стеблей в общую сумму для сходства составляет к . Если к q , то вклад этих стеблей составляет к + А(к — q).
Среди пар взаимно самосопряженных стеблей найдется не более N — 2k—(q2 — q) попарно различных стеблей. Следовательно, вклад в общую сумму для сходства этой части "центральных" стеблей составит N — 2к — (q2 — q). Таким образом, рассуждая как и прежде, в случае к q придем к неравенству: 2.5 доказана. В неравенствах (2.11)-(2.12) возьмем N = q2 + 2, тогда они примут вид: Иначе говоря, для любого расстояния D = п — s — 1, такого что оно отличается от длины кода п только на константу s + 1, объемы соответствующего ДНК (п,п — s — 1)і-кода, большие чем q2 , могут быть достигнуты лишь при малых значениях длины кода п . Таким образом, мы доказали Следствие 2.2: Максимальный объем ДНК-кодов, основанных на аддитивном стебельном 1 -сходстве, с расстоянием D — п — s — 1, таким что оно отличается от длины кода п только на константу s + 1, и длиной кодовых слов то есть для длин кода п 9 максимальный объем кода Ni(n, п — 2) =. q2 = 4. Кроме того, отметим, что лемма 2.5 задает границу для максимального объема кода Ni(n, п — s — 1) для случая фиксированного s и растущего п : Следствие 2.3 Указанные в (2.11)-(2.12) границы можно рассматривать как функции от длины кода п. Вычисляя производные этих функций, получим, что граница (2.11) достигает минимума но п при
Неасимптотические оценки объема сферы
Используя общий метод решения линейных рекуррентных соотношений с постоянными коэффициентами [60], можно получить следующие явные формулы для вычисления чисел F q(t), 1 = 1,2,3: (3.15) (3.16) (3.17) (3.18) Следовательно, выражение под знаком суммы в (3.13) может быть ограничено как: к к 44- - (1 - сз/З 1) П (1 - /?« ) (1 - с3/ ) F3 ) П ( ) Фы) г=2 г=2 cic D-fc+1 (1 + сз/З 1) П (1 + ) (1 + tfc+1) , г=2 где мы учли, что 2 ti = п— (s + к) = D — к + 1. г=1 Для исследования нижней границы этой величины проведем следующие рассуждения. Для любых фиксированных целых х у t 0 и положительного а покажем, что {1-а/Зх)(1-а/Зу) {1-а/Зх+1)(1-а/Зу ь), где /3 была введена в (3.19). В самом деле, легко видеть, что (1 - aftx) (1 - a (Iу) - (1 - af]x+t) (1 - а(Зу ) = = 1 + а2(Зх+У -а(рх + ру)-1- а2рх+у + а (px+t + Ру 1) = а {(Г" + /5У" - /3х - /3у) = а [/? (/? - 1) - )9»- (/5 - 1) ] = а (/5х - /?"- )( - 1) О, так как /3 1. В частности, это неравенство будет выполняться для а = 1 и а = с-л к Поэтому, если фиксировать Y1 « = т: к—l m D — к + 1,то г=2 к min (1 - с3/ ) Ц (1 - /3 ) (1 - Сз +0 = t(fc+l) . U=m г=2 1=2 = (1 - c3ft) (1 - c3ftD k+ m) (1 - /3)k 2 (1 - T-fc 2) . Найдем теперь минимум выражения (і — c3ftD h+1 m) (і — /Зт-к 2) по всем т, к — 1 т D-k + І. Обозначим f(x) = (і - c3ftD-k+l x) (і - ftx k+2) . Тогда f (x) = \п/Зоф-к+1-х (1 - р -к+2) - \nftftx k+2 (1 - сгр-к+1-х) = = 1пу0 (сз/З0" 1-" - /T-fc+2) = In/3 fiO-k+i-x (Сз _ -«+1) _ Поскольку /с — 1 ж ) — АгЧ-1, то 2А; - D - 1 2ж - D + 1 D-2k + 3. Учитывая, что 1 к miii {n — D — 1, [- ] } , окончательно оценим 1 - 2х- D + l D + l при различных значениях к. Так как D 1, то величина 2ж — D + 1 может принимать как положительные, так и отрицательные (при D 2) значения, причем выходит в область положительных значений при росте х . Вспоминая, что с3 = ft = ft1 (и имея в виду, что ft 1), можем сделать вывод, что производная / (ж) положительна при малых х и отрицательна при х + - Следовательно, искомый нами минимум достигается в точке т = к — 1, либо в точке т = D — к + 1. Прямые вычисления: f(k -1) = (1- c3ftD 2k+2) (1 - ft) , f(D -к+ 1) = (1- c3) (1 - ftD 2k ) , показывают, что значения /(ж) в этих точках совпадают, так как сз = ft . Таким образом, в окончательном виде нижняя оценка выражения под знаком суммы в (3.13) примет форму: Wn fo) ( "-!) 4ck XD-k (l-C3)4l-ft)k-2 (l-ftD 2k ) = i=1 D-k+1 -,-(fc+l) , -. \ D-2k+3 / 1\D-2fc+3 7+1 \ /7-1 где 7 была введена в (3.18).
Рассуждая совершенно аналогичным образом в отношении верхней оценки указанного произведения чисел Fq(t), і = 1,2,3, t 0, придем к неравенству ( і)П № ( +i) - 41+ (1+/ --2 (l+ -2fc+3) = i=2 НЇ-ІГ Т"1 + D-2fc+3 + 7-1 D-2fc+3 Пользуясь равенством T2(n-l-D,fc) = D-k + 2 к окончательно получим Теорема 3.2: Для любых целых п, п 2, и D, 1 D п — 2, м fc E(nTflr2HD- + 2)to-i)— - it=i fc-1 + D-2fc+3 7-1 -2fc+3 Sg(n,D) M fc ЕГ Г2)(а" +2)(«-ч 7 7 + D-2fe+3 7-1 D-2ifc+3 где 7 была определена в (3.18), а М = min {п — ) — 1; [- ] } Кроме того, для любого п, п 2, с4ж (1-с5/3 ) S,(n,n-1) с4ж (1 + с5/3 ), где С4 и С5 бшш определены в (3.15), а 0 была определена в (3.19). Рассмотрим теперь случай случай фиксированного радиуса D при растущем п\ D = const при п — оо . Теорема 3.3: ДУШ любого четного положительного D, D = 2, 4,... , ,1)) = , (1+ (1)), п — оо; (3.20) для любого нечетного положительного D, D = 1,3,... , (di + 2)ndl(g-l)dl+1 S,(n,D) = (1 + о(1)), n- oo, di! (3.21) г е d! = [f J . Доказательство теоремы 3.3: В формуле (3.13) заменим s = n — 1 — D: min{n-l-D; [ ±i]} / fe N S,(n, Л) = ["k-l) E W П ( ) ( -і) (3-22) fc=l T2(n-1-D,fc) і i=2 J Понятно, что для любого п 3D + 4 min {п — 1 — D; [Ар] } = [Ар] Заметим, что t(fc+1) : h 0, tk+i 0, 1, г = 2,3,... к, T2(n-1-D,k) = { k+i J2ti = D-k + l г=1 (3.23) ±2ti = D-k + l I i=l ) Это, в свою очередь, означает, что сумма r2(n-l-D,Jt) I г=2 (3.24) {h — ifc+i — 0, t2 — t-A — — th — 1} , D + l 1, ) = 2,4,.... не зависит от п. Таким образом, при определении асимптотически главного слагаемого в сумме (3.22) нам необходимо учитывать только множитель (Т Г ) - Очевидно, наибольшая степень п будет достигаться при к = [Ар] Но при четных D = 2,4,... для такого выбора к сумма (3.24) соответствует случаю, когда число ненулевых элементов равно числу ящиков (см. теорему 3.1) между блоками нулей. Другими словами, D + l ПІп-1-D, T2[n-l-D, При к — [Ар] и нечетных D — 1,3,... сумма (3.22) соответствует случаю, когда число ненулевых элементов на единицу превосходит число ящиков между блоками нулей. Таким образом, D + l T2(n-1-D, = ((111...10), (0211...10), (01211...10), ... (01...1120), (011... 11)}, D + l 2 ) = D + l 2 T2[n-1-D, + 1, ) = 1,3,.... Следовательно, для к = [Ар] при вычислении суммы (3.24) потребуется использовать только начальные условия (3.8) и при четных = 2,4,... она равна Е { (ОП ( ) ( ")} = = ( 3(o))2( (i))fc_1 = (9-i)r bl а при нечетных D = 1, 3,. T2(n-l-D,\ ]) I г=2 .fc-1 . ,, ,ч /лі/ \2/п9/-,х\»;-2 = 2 (0)Fq3(l) (Ffr)) -1 + (к - 1) ( J(0)) ( ДО) W = = 2- (9-1)-(9- 1) + ( "!)(?-I)2 (?-l)fc-2=([ lIj+ l) (-1) -Наконец, при D = 2,4,... и n — oo ГР+1" S,(n, Д) = ± (П D_ - 2) І F l} П ( 0 ( !) і = fc=l / T2(n-1-D,k) К i=2 J T2(n-1-D,fc) = (m:Dfa"1)m" (1+ (1)) = [m-i]!fa"1)m" (1+ (1))- (3-25) Аналогичным образом, для D = 1, 3,... ип-Язо Se(n, D) = 2 [V4ll-1]! (1 + ВД) (3 26) С очевидної! заменой [- 1] — 1 = 1"" ] = d\ из равенства (3.25) сразу получим (3.20), а из равенства (3.26) - формулу 3.21. Теорема 3.3 доказана.
Пример 3.2: Применяя формулу (3.21), получим S,(n,3) = 3ra(g- 1)2(1 + ЭД), n- oo, что согласуется с точной формулой, полученной в примере 3.1. Замечание 3.1: Важно отметить, что, как следует из формул (3.20)-(3.21), полученных в теореме 3.3, объемы сфер при D = 2t и D = 2t + 1, t — 1,2,... , имеют одинаковую степень при п в главном члене асимптотики. Это означает, в частности, что для фиксированного радиуса D и растущей длины п объем шара в пространстве А при четных D асимптотически эквивалентен объему сферы наибольшего радиуса, входящей в этот шар, а при нечетных D — сумме объемов сферы наибольшего радиуса и сферы на единицу меньшего радиуса. Введем распределения вероятностей pF(n,D) = Щ -, PF(n,D) ±У2РР(П,Г), D = 0,1,..-, -1- (3-27) Если х и у — независимые случайные последовательности длины п с независимыми элементами, равновероятно выбираемыми из множества А, то вероятности (3.27) могут быть интерпретированы как На рис. 3.1 приведен график распределения рр(п, D) для n = 10, 20, ЗО, 50, 70 . Из теоремы 3.1 и теоремы 3.3 сразу получим Следствие 3.1: Для любого четного D = 2,4,... вероятность PF -"" Ге-1- 1» п — со; (3.29) для любого нечетного D — 1,3,. Я ! п — со, (3.30) Замечание 3.2: Аналогичное распределение вероятностей для метрики Хэммин-га является хорошо известным биномиальным расиределением для вероятности успеха р = - . Если обозначить через Бып(п, г) объем сферы радиуса г в пространстве .А в метрике Хэмминга, то при
Критическая доля расстояния (n, dn)w -кодов для примеров 1.2 и 1.3
Переходя к пределу в (5.18) при п — со и принимая во внимание (5.27), получаем неравенство d TW , что противоречит тому, что данное число d Tw . 2). Выберем произвольное число d, 0 d Tw , и рассмотрим произвольный (n,dn)w-код X объема N. Так как все кодовые слова в X различны, то N qn . Зафиксируем произвольное целое число т, 1 т logg N п , т.е. qm N. Очевидно, что существует q -ичная последовательность длины т , являющаяся началом М N/qm кодовых слов X. Из условия (гг) определения 5.3 вытекает, что "хвосты" данных М слов образуют некоторый код длины {п — т) со стебельным расстоянием D = dn . Для параметров "хвостового" кода имеет место неравенство (5.18), т.е. n-m dn(l- -jT-1 или m n-dn(l- — )T-\ (5.28) Положим т = \logq(N/\ogqN)] log, N. Тогда М N/qm = \ogqN и (5.28) означает, что log, N n-dn(l- —!- Л Г"1 + log, log, N. (5.29) Если Bw(d) = 0, то (5.12) очевидно. Если Rw(d) 0, то разделив (5.29) на п и учитывая неравенство п log, iV , можем написать log„iV / 1 \ . log log iV - — \-d[\--—- rjL+ 7 дг 5-30 п V bg, ivy w \ogqN Если в (5.30) положить iV = Nw(n, dn) и перейти к пределу при п — со , то в силу (5.27), придем к справедливости неравенства (5.12). Теорема 5.1 доказана. Пусть х = (хі,х2,...,хп) Є Aq и у = (уі,у2,...,у„) Є Aq - независимые одинаково распределенные стационарные случайные последовательности, построенные как цепи Маркова с начальным распределением рі(а), а Є Aq, и матрицей перехода pi(oa) , а, Ъ Є Aq , для которых выполнены условия (5.7)-(5.8), т.е. для любого г Є [п — 1] и любой последовательности (аі, аг,..., а,, а,+і) Є Л 1"1 вероятности Рт{х1 = ttl} = Рг{У1 = Ql} 4 Рі(аі), (5.31) Рг{.т1+і = аг+і \xb = au...,xi = ax} = Рг{жг+1 = аг \хг = аг} = рі(агП\аг), (5.32) Рг{уг+і = агП\уг = Ог,...,уі = аі} = Рг{уг+1 = аг+1 \уг = аг} = рі(огцаг). (5.33) Далее символами х = (ж , жп_і,..., жі) и j/ = (у , у„_і,..., уї) при доказательстве теоремы 5.2 будем обозначать соответствующие сопряженные случайные последовательности. Лемма 5.2: Обратная последовательность (жп,ж„_ь... . Жі) является цепью Маркова с матрицей перехода р2(оо) , a, b Є Aq, а сопряженная последовательность х есть цепь Маркова с распределением вероятностпей (5.31)-(5.33), т.е. для любого і Є [п — 1] и любой последовательности (аг, аг+\,..., ап) Є А г+1 условная вероятность Рг{х г = аг\х { = а1+и... ,ж„" = ап} = Рг{ж = агж Т = аг+і} = р2(аГ1\а1+і) = рі(аг\аг+і). Доказательство леммы 5.2:
Используя определение условной вероятности и свойства (5.11), получаем Рг і -і 1 ї\Тг = Ог, Жг__і = 0,_j-i, . . . , Хп — On J Т\хг — ОгЖг+1 — ai+\) і х ті — anj — ff f 7 1 _ _ і " гг(%і — a, 11,..., xn — an) Prj n = an\xn-i = an-\i , жг = a%\ Рг{ж„_і = an_i,...,тг 11 = о,-ц,хг = a,} Рг{жп = а„жп_і = an_i,... ,) = №(0,10,11) =Рі(а1\а1+і) Лемма 5.2 доказана. С помощью обозначений из определений (5.2)-(5.3) введем случайные величины О, ЄСЛИ Хг = ум Хг+і = yl+i, = 0=, У) = ге[п-1]. (5.34) w(xl,xl+i), иначе, Тогда аддитивное стебельное w-расстояние Т ш(х, у), задаваемое (5.2)-(5.3), есть сумма га-1 2 ш(я, У) = J2 0 Vw(x, у) (n - l)w, (5.35) i=l где w = max гу(а, 6). Из (5.31)-(5.34) следует, что для каждого і Є [п— 1] и г , 0 v w a,bAq вероятность ( Y2 Pi(a)Pi(b\a), если г = О, pr w = } = К (а,Ь)єА2я Pi(a)pi(b\a) J2 Pi(c)Pi(d\c), если г; = го (а, 6), а,ЬєЛ,. Поскольку рі(а)рі(Ьо) = р(а, b), то Y Р2(а, b), если г» = О, Pr{ = v} = { {атЛ" (5.36) р(а,Ь) 53 P(cid), если v = w(a,b), a,b Є Aq. Символом Ery будем обозначать среднее значение случайной величины г/. Из (5.36) получаем, что для любого г Є [п — 1] среднее значение. ЕЛ: U v РГ« = V}= J2 w b a ь)р d) = v=0 {а,Ь)ф{с4) = 2 w(a, b)p(a, b)p(c, d) - w(a b)p(a 6MC d) = (a,b),(c,d)A% (a,6)=(c,d) = 2 w(a,b)p(a,b) Yl p(c,d)- ]P w(a,b)p2(a,b) = = J2 (p(a, b) - p2(a, b))w(a, b) - Tw(p), (а,Ь)єА где мы воспользовались обозначением (5.9). Поэтому, в силу леммы 5.2 и определения (5.35), 71-1 EVw{x, у) = EVw(x,lj) = J2 Щ" = (n-l)Tw(p). (5.37) г=1 Для значений параметра D , О D (п — 1) Tw(p), рассмотрим вероятности Л,(п,Др) РГ{Ї Ш(:Е,І) }, (5.38) Pw{n,D,p) = Pr{X w(x,y) D} = Pv\vw(x, ) )}. (5.39) Второй знак равенства в (5.39) вытекает из леммы 5.2. Используя метод случайного кодирования для ДНК кодов, описанный в главе 1, придем к нижней границе для максимального объема Nw (и, D). Эта граница означает, что для любого распределения р = {р(а, Ь), а, Ь, Є Aq} , удовлетворяющего условиям (5.7) - (5.8), величина 1/2-Рш(п,Др) Nw(n,D) 2- Pw{n,D, р) Положим к = [п/2\ и определим числа
Похожие диссертации на Теоретико-вероятностные и комбинаторные задачи теории кодирования ДНК-последовательностей
