Теоретико-вероятностные и комбинаторные задачи теории кодирования ДНК-последовательностей тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

004600239

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В.ЛОМОНОСОВА

Воронина Анна Никитична

ТЕОРЕТИКО-ВЕРОЯТНОСТНЫЕ И КОМБИНАТОРНЫЕ ЗАДАЧИ ТЕОРИИ КОДИРОВАНИЯ ДНК-ПОСЛЕДОВАТЕЛЬНОСТЕЙ

01.01.05 — теория вероятностей и математическая статистика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Механико-математический факультет

На правах рукописи УДК 621.391.15

МОСКВА 2010

1 АП Р 2010

004600239

Работа выполнена на кафедре теории вероятностей механико-математического факультета Московского государственного университета имени М.В. Ломоносова.

Научный руководитель доктор физико-математических наук,

профессор

Дьячков Аркадий Георгиевич

Официальные оппоненты доктор физико-математических наук,

профессор

Гуревич Борис Маркович

кандидат физико-математических наук Виленкин Павел Александрович

Ведущая организация Институт Проблем

Передачи Информации РАН имени А. А. Харкевича

Защита диссертации состоится «9» апреля 2010 г. в 16 часов 45 минут на заседании диссертационного совета Д 501.001.85 при Московском государственном университете имени М.В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, механико-математический факультет, аудитория 16-24.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета (Главное здание, 14 этаж).

Автореферат разослан « 9 » марта 2010 г.

Ученый секретарь диссертационного совета Д 501.001.85 при МГУ, доктор физико-математических наук, профессор

И.Н. Сергеев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

В упрощенном виде молекулу (одинарную цепочку) ДНК можно считать последовательностью с элементами из алфавита {А, С, (7, Т}. ДНК-цепочки являются направленными, а их важнейшим свойством является способность разнонаправленных цепочек сращиваться в двойные спирали ДНК, или ДНК-дуплексы в процессе ДНК-гибридизации. Основой этого процесса является образование водородных связей между так называемыми комплементарными элементами ДНК-цепочек, а именно элементами А и Г, а также С и С. При этом прочность образовавшегося дуплекса определяется величиной, называемой энергией гибридизации и зависящей от числа образовавшихся водородных связей. Сопряженной к данной ДНК-цепочке называется ДНК-цепочка, полученная путем изменения направления исходной ДНК-цепочки и последующей замены всех элементов в ней на комплементарные. Известно, что максимальная энергия ДНК-гибридизации достигается при образовании дуплексов Ватсона-Крика, то есть дуплексов, состоящих из взаимно-сопряженных ДНК-цепочек.

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

В самом общем виде одну из основных задач теории кодирования можно описать следующим образом. Фиксируется некоторый д-ичный алфавит Лч = {0,..., д — 1} и рассматривается пространство д-ичных последовательностей длины п: А™ = {ж = (жх, ...,хп), Х{ € Лч}- Ко-

дом X называется некоторый набор таких последовательностей (кодовых слов) - подмножество X с А*. На множестве А" задается функция расстояния р{х,у), х,у 6 Как правило, на Л, также можно определить комплементарную р(х, у) функцию сходства. Говорят, что код X является кодом с расстоянием Б > О, если р(х, у) > Б для любых кодовых слов х ф у, х, у € X.

Пусть N(71, П) есть максимальный объем кода (то есть максимальное число кодовых слов в коде) с фиксированными расстоянием В и длиной кодовых слов п. Ставится задача исследования скорости кода Д(с?), то есть логарифмической асимптотики числа N(71, йп) при фиксированной доле расстояния с/ > 0 и растущей длине кодовых слов:

ад ^ ее 1оё«Л>о.

п->00 П

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

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

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

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

'Ф. Дж. Мак-Вильямс, Н. Дж. А. Слоэн, Теория кодов, исправмющих ошибки, Москва: Связь, 1979.

строен в работе Адлемана2 в 1994г. Вследствие относительной новизны данной области исследований устоявшихся канонов математического моделирования ДНК-цепочек и их взаимодействия между собой еще не сложилось. Основные принципы, однако, ясны: ДНК-цепочки могут быть представлены как последовательности из четверичного алфавита Ai = {0,1,2,3}. При этом основные свойства ДНК-цепочек, а также ограничения, вытекающие из потребностей биологических приложений, должны быть отражены в специальных требованиях к конструкции (определению) кода, а энергия ДНК-гибридизации сопоставляется соответствующей функции сходства на пространстве четверичных последовательностей А%. Первые попытки создания модели ДНК-кодов были предприняты в рамках уже хорошо изученной метрики Хэммин-га3,4. Специфика задачи учитывалась путем определения понятия пар взаимно сопряженных ДНК-последовательностей и наложения на код некоторых дополнительных условий.

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

Первая функция сходства, учитывающая особенности взаимодействия цепочек ДНК, была предложена в работах Дьячкова5 и Вилен-кина6 (здесь и далее, ссылаясь на работы, имеющие больше одного авторов, мы для краткости будем указывать в тексте только первого автора). Она была близка к сходству Хэмминга с тем отличием, что каждому типу совпадающих символов присваивался свой вес ги(а), а € Ai, в общей сумме, определяющей такое сходство.

Следующим шагом в эволюции моделей ДНК-кодов стало примене-

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, C. M. Korzelius, D. C. Englehart, D. C. 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 Ê000/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.

SII. А. Виленкин, "Асимптотические задачи комбинаторной теории кодирования и теории информации," Диссертация на соискание ученой степени к.ф.-м.н. Москва, МГУ им. М.В.Ломоносова. 2000.

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

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

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

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

7A. G. D'yacbkov, 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. Symp. Information Theory, Аделаида, Южная Австралия, Австралия, 2005, pp. 288-292.

nS. В. Needleman, С. D. Wunsch, "A general method applicable to the search for similarities in the amino-acid sequences of two proteins," J. Mol Biol, vol. 48, pp. 443453, 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. Также доступно на: http:// www.masoft.com.

14M. Bishop, A. Macula, T. Renz, SynDCode Suite, 2006.

Как уже отмечалось, рассматриваемая задача возникла при построении математических моделей некоторых экспериментов молекулярной биологии. ДНК-коды находят много новых применений в активно развивающихся направлениях науки, таких как определение функции генов15, самосборка наноструктур16, ДНК-программирование2,17, хранение информации18, ДНК-метки (DNA taggants)19 и другие.

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

Доступно на: http://syndcode.geneseo.edu/.

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. Peyghambaxian, "Information Storage and Retrieval using Macromolecules as Storage Media," Optical Data Storage Conference, Ванкувер, Канада, 2003.

19A. Macula, S. Gal, C. Andam, Т. 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-сходством, в пространстве д-ичных последовательностей; исследование вопроса о построении кодовых конструкций для ДНК-кодов, основанных на аддитивном стебельном 1-сходстве.

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

1. Получены две конструкции ДНК-кодов, основанных на аддитивном стебельном 1-сходстве. Найден максимальный объем ДНК-кодов, основанных на ад дитивном стебельном 1-сходстве, для случая фиксированного сходства.

2. Найдены явные формулы для выражения объема сфер для метрики, задаваемой аддитивным стебельным 1-сходством, в пространстве д-ичных последовательностей Ад, получены неасимптотические оценки для таких объемов сфер, а также асимптотические формулы для случая постоянного радиуса.

3. Сформулированы верхние и нижние оценки максимального объема ДНК-кодов, основанных на аддитивном стебельном 1-рас-стоянии, для случая постоянного расстояния (нулевой доли расстояния). Построены и исследованы верхние и нижние границы скорости ДНК-кодов, основанных на аддитивном стебельном 1-расстоянии.

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

5. С применением специального класса ДНК-ансамблей Фибоначчи построена нижняя граница скорости ДНК-кодов, основанных на неаддитивном стебельном ш-расстоянии.

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

с расстоянием (Варшамова-Гилберта, Хэмминга, Плоткина, Элайе-са, Синглтона), стандартных методов исследования логарифмической асимптотики, теорем о больших уклонениях для сумм независимых и зависимых случайных величин, методов выпуклого анализа. При доказательстве границы Варшамова-Гилберта для аддитивного стебельного ги-расстояния был разработан метод случайного кодирования на основе марковских цепей. Это потребовало развития новой техники доказательства теорем подобного рода. При вычислении явных формул для объемов сфер для метрики, задаваемой аддитивным стебельным 1-сходством, были применены комбинаторные методы подсчета числа д-ичных последовательностей специального вида, в частности, найдены рекуррентные уравнения и явные выражения для числа таких последовательностей. Для построения графиков границ скорости ДНК-кодов также были использованы некоторые численные методы.

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

Апробация работы Результаты диссертации неоднократно докладывались на Большом семинаре кафедры теории вероятностей мехмата МГУ (2008г. и 2009г., руководитель - член-корреспондент РАН А. Н. Ширяев), на семинаре по теории кодирования в Институте Проблем Передачи Информации РАН (2008г. и 2009г., руководитель -профессор Л. А. Бассалыго) и на семинаре по теории вероятностей и статистической физике в МГУ им. Ломоносова (2007г. и 2010г., руководитель - профессор Б.М. Гуревич). Полученные результаты были представлены на международном симпозиуме по алгебраической и комбинаторной теории кодирования АССТ-11 (Пампорово, Болгария, 2008), вошли в сборник трудов конференции 31-ой конференции молодых ученых и специалистов ИППИ РАН ИТиС'08.

Публикации По теме диссертации опубликовано 4 работы, список которых приведен в конце настоящего автореферата.

Структура и объем диссертации Диссертация состоит из списка обозначений, шести глав, разбитых на параграфы, списка литературы, содержащего 63 наименования, списка работ автора по теме диссертации и оглавления. Общий объем диссертации составляет 181 страницу.

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

Символом = будем обозначать равенство по определению. Отметим, что нумерация формул в настоящем автореферате не соответствует нумерации в диссертации.

Введем общие определения. Пусть [п] = {1,2, ...,гг} обозначает множество целых чисел от 1 до п. Пусть q — 2,4,... - произвольное фиксированное четное число, a Aq = {0,1,..., q - 1} - стандартный алфавит объема \Aq\ = q. Стандартный символ |uj ([и]) обозначает наибольшее (наименьшее) целое число < и (> и).

Определим, что для любого х s Ад комплементарным будет элемент х = (g — 1) — ж G Aq (при построении одного из примеров кодовых конструкций мы будем считать, что для любого i — 0,1,..., g/2 комплементарными являются элементы 2г и 2г + 1; понятно, что такое изменение не сказывается существенным образом на вводимой нами математической модели, а только изменяет порядок сопоставления алфавитов {А, С, G, Т} и Ai = {0,1,2,3}). Для последовательности х = (a-i,X2, • • •, хп) € Ад определим сопряженную к ней последовательность х = (х„,x„_i,... ,х2, Х\) & А".

Пусть w — w(a, b) >0, a,b & Ад, является весовой функцией такой, что

w(a,b) = w(b,a), a,beA. (1)

Условие (1) означает, что функция w(a,b) инвариантна относительно преобразования Ватсона-Крика.

Введем формальные определения рассматриваемых нами функций сходства.

Определение 3.1: Для двух произвольных g-ичных последовательностей х = (хих2, ■ ■ ■ ,х„) <Е Ад н у = (уит/г, • ■ •,Уп) G Anq длины

п, п > 2, число

п—1

зх{х,у) = где

¿=1

а}(х,у) = I1' 6СЛИ * = ^ = г £\п — 1], (2)

I 0, в остальных случаях,

называется аддитивным стебельным 1 -сходством между х я у.

Определение 5.1: Для двух произвольных д-ичных последовательностей X = (жь Х2, ■ • • , хп) £ И у = (у1, 7/2, ■ • • , Уп) £ А™ ДЛИНЫ тг, п > 2, число

п-1 1=1

^(а; -) А /ги(а' Ь)' еСЛИ Хг = У' = а> = Уг+1 = Ь> 1 [0, в остальных случаях,

называется аддитивным стебельным ю-сходством между х и у.

Для двух произвольных д-ичных последовательностей х = {хих2,..., хп) € и у = {ух, г/г, • • •, уп) € А^ символом

г = (гиг2,...,ге) £ Аед, ¿6 [гг],

обозначим общую подпоследовательность длины \г\ == I между а; и у, что означает, что существуют две ¿-последовательности целых чисел

1 < кг < к2 < ■ ■ ■ < кс < п, 1 < л < ]2 < ■ ■ • < М < п,

такие что ги = х^ - и £ Щ.

Определение 6.1: Пусть 2 < г < п - произвольные целые числа. ДНК г-последовательность а = (01,02,...,аг) £ Агч, называется общим блоком для последовательностей х и у (кратко, общим (х, у)-блоком) длины г, если последовательности хну (одновременно) содержат а как подпоследовательность, состоящую из г последовательных элементов ж и у.

Определение 6.2: Пусть 2 < I < п - некоторое целое число. Последовательность г — (г^, г2,..., £ Аед называется общей блоковой подпоследовательностью длины \г\ = (. между а: и у, если % является упорядоченным набором непересекающихся общих (ж, у)-блоков и длина каждого общего (х, у)-блока в этом наборе > 2. Пусть 2(х, у) обозначает множество всех общих блоковых подпоследовательностей

между х и у. Для любого г 6 2(х,у) обозначим через к(г,х,у), 1 < к(г,х,у) < \z\j2, минимальное число общих (х,у)-блоков, составляющих данную подпоследовательность г.

Определение 6.4: Пусть г € 2(х, у) имеет вид

к{г,х,у) к{г,х,у)

\г\ = £ 1Л = £

т= 1 т=1

где

4 ..., ) е^, т = 1,2,..., к(г, х, у),

является упорядоченным набором общих (ж, у)-блоков, составляющих г. Для ДНК-последовательностей х, у £ А" число

(Ф,®,1/) г„-1

называется неаддитивным стебельным ги-сходством между хну. Для постоянной весовой функции: из(а,Ь) = 1 для любых а, Ь 6 Ач -будем использовать обозначение у).

Пусть 5(х,у), х,у € Л™, обозначает произвольную стебельную функцию сходства для ДНК-последовательностей. Тогда соответствующее ей стебельное расстояние определяется по следующей формуле:

Ъ(х,у)±5(х,х)-5{х,у).

Пусть ж(1),х(2),...,х(Л0, где = (хг(з... €

А", з € [Щ, являются кодовыми словами д-ичного кода X — {х(1),х(2),...,х(Л0) длины п и объема Ы, где N — 2,4,... четно. Пусть Д 0 < Б < тах х), - произвольное положительное

число.

хеА»

Определение 1.1: Код X называется ДНК-кодом с расстоянием £> для стебельного сходства ¿>(х, у), если выполнены следующие два условия:

(г). Для любого индекса ] & [ТУ], найдется j' € [Л''], $ ф j, такой что

®(Л = Х(Л Ф Х(Л-

(и). Для любых ] ф ]', расстояние

V(x(j)fx(J'))>D. (3)

ДНК-коды длины п с расстоянием И, основанные на аддитивном стебельном 1-сходстве, будем кратко называть (л, £))х-кодами, соответствующие ДНК-коды, основанные на аддитивном стебельном иг-

сходстве, - (n, £>)ш-кодами, а ДНК-коды, основанные на неаддитивном стебельном -ш-сходстве, - (n, D) ^'-кодами. Такие же индексы будут использоваться и для всех прочих вводимых величин для различных функций сходства.

Обозначим через N(n,D) максимальный объем ДНК-кода, основанного на стебельном сходстве S{x,y). Для фиксированного параметра d > О число

ад а иd>0 (4)

n-Юо п

называется скоростью ДНК-кодов для доли расстояния d > 0.

Глава 2 В этой главе рассматривается вопрос построения кодовых конструкций для ДНК-кодов. Нами получены следующие 2 примера конкретных кодовых конструкций для аддитивного стебельного 1-сходства:

Теорема 2.1: 1. Если п = kq, где к — 1,3,5,... - нечетно, то код

X - Mq(n) = {х € Ag : Xi +----1- хп = 0 (mod q) }

является (п,2)\-кодом объема gn_1.

2. Если п = kq, где к = 2,4, б,... - четно, то код Mq(n) содержит подкод

M'q{n) = (ж£ A?lg :xi е Ад, £„-,•+i =Щ, г в [п/2] } , состоящий из самосопряженных слов, а код X — Mq{n) /A4'q(n) является (n,2)i-wdoM объема qn_1 — q"/2.

Пусть а обозначает примитивный элемент поля GF(4), а и,-, г 6 [пг] - переменные, на которых заданы многочлены, определяющие код Рида-Маллера первого порядка Й4(1, ш).

Теорема 2.2: Код Рида-Маллера первого порядка R4,(\,m) содержит 4т самосопряженных слов вида

т

а + Mi + biV2 -I-----b bmvm, где a 6 G.F(4) u^bi- a.

i=1

Остальные 4m+1 — 4m = 3 • 4m кодовых слов составляют ДНК-код объема N = 3 • 4m, длины п = Ат с аддитивным стебельным 1-расстоянием 3 • 4m_1. При этом если х = а + b\Vi + • • • + bmvm и

х — а3 + Ь\ь1 + • • • + Ь3пьт, то выполняются следующие равенства:

Щ = Ьи * € И,

т

а3 = а + а2 ^ Ь{ + 1.

г=1

Кроме того, для кодов с фиксированным сходством оказывается верно следующее утверждение:

Теорема 2.3: Пусть я Е [п — 2] - некоторое фиксированное положительное число. Если длина п ДНК-кода с аддитивным стебельным 1 -расстоянием Б = п — 5 — 1 удовлетворяет неравенству:

либо

з-(д2 + 2)(?2 + 1) , 1 , п > —--^--Ь 1 для четных я,

^ (?2 + 2)(5(д2 + 1)-1)+2д , 1 п > --—-—---Ь 1 для нечетных в,

то максимальный объем

N1(11,11- 5 - 1) = <?2.

В конце главы мы приведем также пример субоптимальной конструкции для ДНК-кодов, основанных на неаддитивном стебельном 1-сходстве (то есть неаддитивном стебельном ги-сходстве для постоянной весовой функции), из которого будет следовать следующий результат:

Теорема 2.4: Если п = 4т, т — 1,3,5,..., то

4П_1 А

2 < Л^>(п,2) < 4"-1.

Глава 3 В этой главе рассматриваются неасимптотические (ио расстоянию Б) задачи для ДНК-кодов, основанных на аддитивном стебельном 1-сходстве. Нами будут установлены основные свойства этой функции сходства, и в частности мы покажем, что аддитивное стебельное 1-сходство является метрикой в пространстве д-ичных последовательностей длины п, а объем сферы в такой метрике не зависит от ее центра и определяется только ее радиусом.

Определим с помощью рекуррентных соотношений следующие три типа последовательностей:

Ф) = (я - - 1) + (? - ~ 2), < > з, г = 1,2,3,

FK 1)^9-1,

с начальными условиями:

F?2(2)4 (5-1)2; ^(2)4g(g-l).

Кроме того, пусть № = (ti,t2,... ,tk), к — 1,2,..., обозначает упорядоченное множество к целых чисел. Для фиксированных целых s, 1 < s < п — 1, и к, 1 < к < min {s; f2^] }, введем множество:

т2 М) = <

: ii > 0, tjfc+i >0, U > 1, i = 2,3,... к,

к+1

J2 ti — n-(s + k) ¡=1

.

Мы получим следующие явные формулы для объемов сфер

8х(п,г) 'А \{уеЛпя : Рг(0,у) = г}|, 1 < г < п-1,

где 0 = (0,..., 0) € А^:

Теорема 3.1: Пусть п - некоторое целое число, п > 2. Если г = п — 1 « л > 3, то 39(п, п — 1) = ^(п). Если 1 < й < п - 3, то

тш{а;|^1}/ С к }

8,(п, п-1-5) = х; и _ 1 Е П *?(**«) •

*=1 \ / Г2(«Л) I ¿=2 J

Отсюда будут выведены неасимптотические оценки для объемов сфер:

Теорема 3.2: Для любых целых п, п > 2, и В, 1 < И < п — 2, м

£

fc=1 х

n-D - 2\ D-k + 2

fc- 1

7 + 1

D~2k+3

7-1

Р-2Л+3

<

M

iE

it=i \

< Sg(n,D) < fn-D-2\ iD-k + 2N

к

D-2k+3

(q- 1)в-*+17_1Х

7-1

ß-2fc+3

где

Асимптотические выражения для объема сферы при растущей длине кодовых слов п и постоянном радиусе Б имеют вид:

Теорема 3.3: Для любого четного положительного Б, Б — 2,4,..

8д(п,В) = П<11{<1~] ^ (1 + 5(1)), п —» оо;

для любого нечетного положительного Б, В — 1,3,...,

"1!

где (¡1 =

Теорема 3.3 позволяет получить следующие оценки максимального объема N1 (п, Б) ДНК-кодов, основанных на аддитивном стебельном 1-сходстве, для случая постоянного расстояния Б и растущей длины кодовых слов п:

Теорема 3.4: (Граница случайного кодирования) Для любого нечетного Б, Б — 3,5,..., максимальный объем (п,Б)1-кода удовлетворяет неравенству

Ъ(п,В) > ^ (1+и(1)), п-> оо,

а для любого четного Б, Б — 2,4,..., - неравенству

Теорема 3.5: (Граница Хэмминга) Для любого фиксированного В = 5,6,9,10,13,14,..., максимальный объем N(71, В)\ (п, Б)1-кода удовлетворяет неравенству

лГ1(п'п) - п*£-1)*(1+Ц1))'п а для любого фиксированного Б — 3,4,7,8, И, 12,... - неравенству

Теорема 3.6: (Граница Синглтона) Для любого целого п, п > О, и любого О € [1,п — 1] максимальный объем £>) {п,В)\-кода удовлетворяет неравенству

Глава 4 В данной главе изучаются границы скорости ДНК-кодов, основанных на аддитивном стебельном 1-сходстве. Применяя описанный в первой главе диссертации метод случайного кодирования для ДНК-кодов мы находим следующий аналог классической границы Варшамова-Гилберта:

Теорема 4.2: (Граница случайного кодирования). 1). Если 0 < (1 < (д2 — 1)/<?2, то скорость

ЯМ > Ьг{6) ^ тЫш*-/л(и)}, ^1(«)=1обгА1(и), (6)

и<0 *

1 + (д - + ^/[1 + (д - 1)^]2 - А(д - 1)9«(1 - <?) А 1(и) =---. (7)

2). Нижняя граница Ьх{д) > 0 при 0 < й < (д"1 — 1)/<72. Кроме того,

•^1(0) = 1 и Ьх = 0- При этом Ьх{й) является убывающей

\^)-выпуклой функцией и задается параметрическими уравнениями

Ьх(сI) = иц[(и) — /¿1 (и), ¿ = /¿[(и),

где Их(и), и < 0, обозначает производную функции ц\(и), определяемой (6)-(7).

Верхние границы представлены следующими аналогами классических теорем Плоткина, Хэмминга и Элайеса:

Теорема 4.1: (Граница Плоткина). Скорость

Ап1

ЯМ < ГМ = 1 - если 0 < й < 1 - 1/д2.

Теорема 4.3: (Граница Хэмминга). Если 0 < с! < то ско-

рость Ях((1) ДНК (п, йп)\-кодов удовлетворяет неравенству

ЯМ < ЬМ2),

где Ь\(й) определено в (6).

Теорема 4.4: (Граница Элайеса). Если 0 < ё < то скорость

ЯМ < Е1((1),

где верхняя граница £а(<2) задается при и < 0 и 0 < ё < (д2 — 1)/д2 параметрическими уравнениями

Г /.2

Ег((1) = (и) - р.1 (и), (1 =- (и)

д2-1] '

в которых функция Ц\{и), определена в (6)-(7).

Глава 5 В этой части диссертации изучается асимптотическое поведение максимального объема ДНК-кодов, основанных на аддитивном стебельном ш-сходстве, для случая произвольной весовой функции ги(а, Ь), а, Ь £ Лч.

Верхняя граница скорости Пи,(с1) дается аналогом классической границы Плоткина. Пусть р = {р(а,Ь), а,Ь е Ад} - произвольное совместное распределение вероятностей на множестве упорядоченных пар (а, Ь) е Ад, т.е.

У^ р(а,Ь) = 1, р(а,Ь) > 0 для любых а,Ь € Ая, а.ЬеЛ, а символы

Р1{а)= $>М)>0' Р1(6|а)4 ^М

ЬеА

Р1(а) '

р2(а)± ]Г>(М>0, й(Ь|а)=

¿¡X

обозначают соответствующие маргинальные и условные вероятности. При описании границ скорости Яш(сО будем рассматривать распределения р, для которых совпадают маргинальные вероятности, т.е. для любого а € Ач

М«) = р(а>= 52 Р.(Ь>а) = Рз(а) > 0 (8)

ьеа„ ЬеЛ,

. и, кроме того, функция р(а, Ь), как и весовая функция и)(а, Ь), является инвариантной относительно преобразования Ватсона-Крика, т.е.

р(а, Ь) = р(Ь,а) для любых а, Ь е Ач. (9)

Для фиксированной весовой функции и){а, Ь) введем величины Т„ ^ шах ЗД, Тт(р) ^ ^ {р(а,Ь)-р2(а,Ь))и](а,Ь). (10)

(8)~(9) а,бел

В конце главы 5 мы описываем итерационный метод решения выпуклой задачи максимизации (8)-(10), который можно применять при вычислении для функций аддитивного стебельного гу-сходства для приведенных в главе образцов весовой функции. Там же будет показано, что определение числа Тю равносильно определению

4 шах Г„(р),

(8)

поскольку для любой весовой функции Ъ), инвариантной относительно преобразования Ватсона-Крика, экстремальное распределение р, получаемое в качестве решения последней задачи максимизации, удовлетворяет также и условию (9).

Теорема 5.1: (Граница Плоткина). 1). Если й > Тш, то ^{д) = 0. 2). Скорость

ад) < ад) 4 1 - 0 < й < Т„.

-¿и/

На множестве упорядоченных пар (а, Ь), а = (а\,а2,аз,а^ 6 Л^, Ь = (£>ъ Ь2, Ь3,64) е Ад, определим (д4 х д4)-матрицу Р^ = ||Р(Ь|а)|| с элементами

Р(Ь|а) = Р ((6ь Ъ2, Ъ3, Ь4) | (оь а2, а3, а4)) =

А (рКЫЫр^М&з), если Ь1 = а2иЬ3 = а4, 10, если Ь\ Ф а2 или 63 ф а4.

По заданным значениям весовой функции ю(а>Ь), а,Ь £ Ач, на множестве упорядоченных четверок Ъ £ Ад определим функцию

д ) 0, если 61 = 63, Ь2 = 64,

и(Ъ) = иЬиЬ2,Ь3М) = \ 1 " ' 41 (12)

1ги(оь о2), иначе.

Для матрицы (11) и функции (12) введем (д4 х д4)-матрицу Маркова

Ми(и, р) ^ ||Р(Ь|а) ди/"(Ь)||, а € А4д, Ь € и € М. (13)

Пусть для распределения р, определяемого условиями (8)-(9), дополнительно известно, что матрица переходных вероятностей (11) задает

цепь Маркова, удовлетворяющую условию Маркова М, а именно, что для любой пары состояний a, b € А* найдется такое целое т > 0, что Р™(а, Ь) > 0, то есть за т шагов можно перейти из состояния а в состояние Ь.

Символом \w(u, р), и € R, обозначим максимальное собственное значение матрицы (13), т.е. такое положительное собственное значение, что для любого другого ее собственного значения А абсолютная величина |А| < Xw(u, р). Число Xw(u, р) существует согласно теореме Перрона-Фробениуса.

Пусть величина определяется равенством:

Т* 4 щах Tw{р), (14)

(8)-(9),Л<

где Tw(р) определены в (10). Нижнюю границу скорости Rw(d) дает

Теорема 5.2: Для любого распределения вероятностей р, удовлетворяющего условиям (8)-(9) и условию Маркова М, и любой доли расстояния d, 0 < d < Tw(p): скорость

Rw(d) > Lw(d, p) = inf sup {uz - Ци,(и, p)},

0<z<d ыел

p) = \ogq\w(u, p),

где функция Lw(d, p) > 0 для любого d, 0 < d < Tw(p), и значение Lw{Tw{p),p) = 0.

Очевидно, теорема 5.2 означает, что справедливо

Следствие 5.1: (Граница Варшамова-Гилберта). Для любого d > 0 скорость

Rw(d) > Rw(d) 4 Lw{d,p).

Если 0 <d<T%1, то нижняя граница Rw(d) > 0, т.е. для любого d, 0 < d < , скорость B^id) > 0.

Если величины Tw и Т^ совпадают, то соответствующая весовая функция называется регулярной, и нерегулярной в противном случае. Из теоремы 5.1 и следствия 5.1 вытекает основной результат главы 5 о критической доле расстояния (п, dn)w-Kодов для регулярных весовых функций:

Следствие 5.2: Пусть w(a,b), а,Ь € Ад, - регулярная весовая функция. При 0 < d < Tw скорость Rw(d) > 0. Если d > Tw, то Rw(d) = 0. Другими словами, максимальный объем (п, dn)w-xodoe

возрастает экспоненциально с ростом п тогда и только тогда, ко-гдаО < <1< Тц,.

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

Глава 6 В последней главе работы мы получим нижнюю границу скорости четверичных ДНК-кодов, основанных на неаддитивном стебельном гу-сходстве для случая произвольной весовой функции т(а) 6), а,Ь € Л4.

Нам потребуются специальные классы (п, £))Н-кодов, называемые Ь-ансамблями Фибоначчи. Символ Ь будет обозначать любое подмножество Ь с «А2 2-блоков букв ДНК-алфавита Д4, замкнутое относительно преобразования сопряжения. Так, например, Ь = Ьк, к = 0,1,2,3,4,6,8, где

¿0-0, ¿1 ±{ТА}, Ь2 = {ТА,АТ}, и = {ТА,АТ,АА,ТТ},

и

¿з = {ТА, АА, ТТ}, Ь6 4 {ТА, АТ,АА, ТТ, Ав, СТ}, Ь8 4 {ТА, АТ, АА, ТТ, Ав, СТ, в А, ТС}. Пусть DNA{n, Ь) (коротко, [п, Ь]) обозначает множество (ансамбль) всех ДНК-последовательностей длины п, которые не содержат стеблей из Ь. Такое множество [п,Ь], очевидно, замкнутое относительно преобразования сопряжения, называется Ь-ансамблем Фибоначчи. Обозначим через Ах(п) = |[п, объем множества [п, Ь].

Определение 6.8: Пусть В) обозначает максимальный

объем ДНК (п, £>)(1> -кодов X С ОИА{п,Ь) для постоянной весовой функции ш(а, Ь) ~ 1 для любых а, Ь € Аа- Если доля расстояния ¿> 0 есть некоторое фиксированное число, то

д Пт

п->оо 72

называется скоростью ДНК кодов для Ь-ансамбля Фибоначчи.

В главе 6 для множеств Ь\, Ь2 и будут найдены верхние оценки следующего типа (для множеств и верны аналогичные оценки более сложного вида, как показано в конце главы):

А£» < Сгп [1 + ша"], г — 1,2,4.

Пусть

PL ± log4Г, p'L £ Iog4 C3(1 + wa2)(1+a;Q)r

Для L-ансамблей Фибоначчи мы получим следующую нижнюю границу скорости Rb(d):

Теорема 6.1: Для любой доли расстояния 0 < d < di, скорость Ri(d) удовлетворяет, неравенству

RL{d) > RL{d) = (1 - d)pL ~ EL{d) > О,

где

Еь{и) 4 max EL{v,u),

0<u<min{u, 1—u}

El{v,u) = -p'L - v + (l-u)/i4 (j-^) + 2 и hi

h4(u) = -u log4 и - (1 - и) log4(l — и)

и di, 0 < di < 1, является единственным на интервале (0; 1) корнем уравнения R^d) — 0, или (1 — d)pi = Ei{d).

Пусть

d{w) = max {wL ■ di}, wL = min w(a, b).

L

Применение ансамблей Фибоначчи для случайного кодирования вкупе с результатом теоремы 6.1 позволяет существенно улучшить нижнюю границу скорости R^w\d.) ДНК-кодов, основанных на неаддитивном стебельном го-сходстве, что отражено в

Теорема 6.2: Если 0 < d < d(w), то скорость ДНК (n,dn)№-кодов RM{d) > 0 и верна нижняя граница

RW(d) > R{w){d) = max

0 <d<d{w).

Введенные в главе 5 весовые образцы будут классифицированы в зависимости от того, какой ансамбль Фибоначчи позволяет получить экспоненциально растущие коды для наибольшего интервала значений доли расстояния d для данного образца.

Автор выражает глубокую благодарность своему научному руководителю, доктору физико-математических наук, профессору Аркадию Георгиевичу Дьячкову за постановку задач, постоянное внимание и помощь в работе.

Работы автора по теме диссертации

[1] А. Г. Дьячков, А. Н. Воронина, "ДНК-коды для аддитивного стебельного сходства," Проблемы Передачи Информации, т. 45, н. 2, стр. 56-77, 2009.

Дьячкову А. Г. принадлежит метод случайного кодирования для ДНК-кодов (неравенство (48)) и доказательство теоремы 3. Остальные результаты принадлежат Ворониной А. Н.

[2] А. Н. Воронина, "Об объёмах сфер для стебельного расстояния," Проблемы Передачи Информации, т. 46, и. 1, стр. 9-19, 2010.

[3] A. G. D'yachkov, А. N. Voronina, "DNA Codes Based on Stem Hamming Similarity," Proc. 11th Int. Workshop Algebraic and Combinatorial Coding Theory, Пампорово, Болгария, 2008, стр. 85-91.

Дьячкову А. Г. принадлежит метод случайного кодирования для ДНК-кодов (предложение 1). Остальные результаты принадлежат Ворониной А. Н.

[4] А. Г. Дьячков, А. Н. Воронина, "ДНК-коды, основанные на весовом стебельном сходстве Хэмминга," Сборник трудов ИТиС'08, Геленджик, Россия, 2008, стр. 316-320.

Дьячкову А. Г. принадлежит метод случайного кодирования для ДНК-кодов (предложение 1). Остальные результаты принадлежат Ворониной А. Н.

Подписано в печать 0ii.03.20f0 Формат 60x90 1/16. Усл. печ. л. /б Тираж {2.0 экз. Заказ /3*

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета МГУ имени М.В.Ломоносова

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

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.

Глава 2.31

1.4.

Глава 3.33

1.4.

Глава 4.36

1.4.

Глава 5.37

1.4.

Глава 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 Неасимптотические задачи для аддитивного стебельного - сходства 73

3.1 Аддитивное стебельное 1-сходство и его основные свойства.74

3.2 Вычисление объемов сфер.76

3.3 Неасимптотические оценки объема сферы.80

3.4 Асимптотика объема сферы.83

3.5 Объем ДНК-кода для фиксированного расстояния.87

4 Границы скорости ДНК-кодов для аддитивного стебельного -сходства 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 Границы скорости ДНК-кодов для аддитивного стебельного w -сходства 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

5.5.1 Анализ таблиц 5.1-5.8 для аддитивного стебельного w -расстояния.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 Граница случайного кодирования для ДНК (n, 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

1. Ф. Дж. Мак-Вильямс, Н. Дж. А. Слоэн, Теория кодов, исправляющих ошибки, Москва: Связь, 1979.

2. R. G. Gallager, Information Theory and Reliable Communication, New York: J. Wiley, 1968. Перевод на русский язык: Р. Галлагер, Теория информации и надежная связь, Москва: Советское радио, 1974.

3. Э. Берлекемп, Алгебраическая теория кодирования, Москва: Мир, 1971.

4. Е. F. Assmus, Jr., J. D. Key, Designs and Their Codes, Cambridge: Cambridge University Press, 1992.

5. В. И. Левенштейн, "Двоичные коды с исправлением выпадений, вставок и замещений символов," Докл. Акад. Наук СССР, т. 163. п. 4. с. 845-848, 1965.

6. В. И. Левенштейн, "Элементы теории кодирования," в кн. Дискретная математика и математические вопросы кибернетики, Москва: Наука, 1974, с. 207-305.

7. V. I. Levenshtein, "Efficient Reconstruction of Sequences from Their Subsequences or Supersedences," J. Comb. Th., Ser. A, vol. 93, pp. 310-332, 2001.

8. V. Dancik, "Expected Length of Longest Common Subsequences," Ph.D. thesis, Univ. of Warwick, UK, 1994.

9. J. Yin, "A combinatorial construction for perfect deletion-correcting codes," Designs, Codes, and Cryptography, vol. 23, n. 1, pp. 99-110, 2001.

10. P. P. Варшамов, Г. M. Тененгольц, "Код, исправляющий одиночные несимметричные ошибки," Автоматика и телемеханика, т. 26, и. 2, с. 288-292, 1965.

11. N. Sloane, "On single-deletion-correcting codes," IEEE Trans. Inform. Theory, 2002.13| A. G. D'yachkov, D. C. Torney, "On similarity codes," IEEE Trans. Inform. Th., vol. 46, n. 4, pp.1558-1664, 2000.

12. A. G. D'yachkov, D. C. Torney, P. A. Vilenkin, P. S. White, "Reverse-Complement Similarity Codes for DNA Sequences," тезисы симпозиума ISIT-2000, Сорренто, Италия, 2000, с. 330.

13. A. G. D'yachkov, P. L. Erdos, A. J. Macula, V. V. Rykov, D. C. Torney, C. S. Tung, P. A. Vilenkin, P. S. White, "Exordium for DNA Codes," J. Comb. Optimization, vol. 7, n. 4, pp. 369-379, 2003.

14. А. Г. Дьячов, П. А. Виленкин, И. К. Исмагилов, Р. С. Сарбаев, А. Макула, Д. Торни, С. Уайт, "О ДНК кодах," Проблемны Передает Информации, т. 41, н. 4, с. 57-77, 2005.

15. A. G. D'yachkov, A. J. Macula, Т. Е. Renz, P. A. Vilenkin, I. К. Ismagilov, "New Results on DNA Codes," в Proc. 2005 IEEE Int. Symp. Information Theory, Аделаида, Южная Австралия, Автралия, 2005, с. 283-288.

16. А. Г. Дьячов, П. А. Виленкин, И. К. Исмагилов, Р. С. Сарбаев, А. Макула, Д. Торни, С. Уайт, "Письмо в редакцию," Проблемы Передачи Информации, т. 42, н. 2, с. 109109, 2006.

17. М. A. Bishop, A. G. D'yachkov, A. J. Macula, Т. Е. Renz, V. V. Rykov, "Free Energy Gap and Statistical Thermodynamic Fidelity of DNA Codes," Journal of Computational Biology, vol. 14, n. 8, pp. 1088-1104, 2007.

18. П. А. Виленкин, "Асимптотические задачи комбинаторной теории кодирования и теории информации," Диссертация на соискание ученой степени к.ф.-м.н. Москва, МГУ им. М.В.Ломоносова. 2000.

19. A. Marathe, А. Е. Condon, R. М. Corn, "On combinatorial DNA design," J. Сотр. Biol., vol. 8, pp. 201-219, 2001.

20. О. Milenkovic, N. Kashyap, "New Constructions of Codes for DNA computing," в Proc. 2005 International Workshop on Coding and Cryptography (WCC 2005), Берген, Норвегия, 2005, стр. 204-213.

21. R. Dirks, J. Bois, J. Schaeffer, et al., "Thermodynamic analysis of interacting nucleic acid strands," SI AM Rev., vol. 49, pp. 65-88, 2007.

22. J. SantaLucia, "A unified view of polymer, dumbbell, and oligonucleotide DNA nearest-neighbor thermodynamics," Proc. National Academy of Sciences USA, vol. 95, pp. 14601465,1998.

23. J. SantaLucia, D. Hicks, "The thermodynamics of DNA structural motifs," Annu. Rev. Biophys. Biomol. Struct., vol. 33, pp. 415-440, 2004.

24. M. 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. Также доступно на: http:// www.rnasoft.com.

25. R. 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.

26. M. Shortreed, S. Chang, D. Hong, "A thermodynamic approach to designing structure-free combinatorial DNA word sets Nucleic Acids Res., vol. 33, pp. 4965-4977, 2005.

27. D. Tulpan, M. Andronescu, S. Chang, et al., "Thermodynamically based DNA strand design Nucleic Acids Res, vol. 33, pp. 4951-4964, 2005.

28. L. Kaderali, "Selecting target specific probes for DNA arrays," Master's Thesis, Informatics, U. Koln, 2001.

29. S. B. Needleman, C. D. Wunsch, "A general method applicable to the search for similarities in the amino-acid sequences of two proteins," J. Mol. Biol., vol. 48, pp. 443-453, 1970.

30. T. F. Smith, M. S. Waterman, "Identification of common molecular subsequences," J. Mol. Biol., vol. 147, pp. 195-197, 1981.

31. M. Bishop, A. Macula, T. Renz, SynDCode Suite, 2006. Доступно на: http://syndcode.geneseo.edu/.

32. J. Chen, R. Deaton, M. Garzon, "Characterization of Non-crosshybridizing DNA Oligonucleotides Manufactured in vitro," Natural Computing vol. 5, n. 2, pp. 165-181, 2006.

33. L. Kaderali, A. Deshpande, Л. Nolan, P. White, "Primer-design for multiplexed geno-typing," Nucleic Acids Res., vol. 31, pp. 1796-1802, 2003.

34. R. Penchovsky, J. Ackermann, "DNA library design for molecular computation," J. Compxit. Biol., vol. 10, pp. 215-229, 2003.

35. M. Mansuripur, P. K. Khulbe, S. M. Kuebler, J. W. Perry, M. S. Giridhar, N. Pey-ghambarian, "Information Storage and Retrieval using Macromolecules as Storage Media," Optical Data Storage Conference, Ванкувер, Канада, 2003.

36. H. Cai, P. White, D. Torney, et al., "Flow cytometry-based minisequencing: a new platform for high throughput single nucleotide polymorphism scoring," Genomics, vol. 66, pp. 135— 143, 2000.

37. D. Fish, M. Home, R. Searles, et al., "Multiplex SNP Discrimination," Biophysical Journal, vol .92, pp. 89-92, 2007.

38. M. Valignat, O. Theodoly, J. Crocker, et al., "Reversible self-assembly and directed assembly of DNA-linked micrometer-sized colloids," FN AS, vol. 102, pp. 4225-4229, 2005.

39. P. Hardenbol, J. Baner, M. Jain, et al., "Multiplexed genotyping with sequence-tagged molecular inversion probes," Nat. BiotechnoL, vol. 6, pp. 673-678, 2003.

40. E. K. Nordberg, "YODA: selecting signature oligonucleotides," Bioinformatics, vol. 21, n. 8, pp. 1365-1370, 2005.

41. X. Li, Z. He, J. Zhou, "Selection of optimal oligonucleotide probes for microarrays using multiple criteria, global alignment and parameter estimation," Nucleic Acids Res., vol. 33, n. 19, pp. 6114-6123, 2005.

42. R. Braich, N. Chelyapov, Johnson, et al., "Solution of a 20-Variable 3-SAT problem on a DNA computer," Sciencexpress, vol. 296, pp. 499-502, 2002.

43. J. Rose, R. Deaton, A. Suyama, "Statistical thermodynamic analysis and design of DNA-based computers," Natural Computing, vol. 3, pp. 443-359, 2004.

44. L. Adleman, "Molecular Computation of Solutions to Combinatorial Problems," Science, vol. 266. pp. 1021-1024, 1994.

45. Q. Ouyang, P. D. Kaplan, S. Liu, A. Libchaber, "DNA solution of the maximal clique problem," Science, vol. 278, pp. 446-449, 1997.

46. К. Sakamoto, Н. Gouzu, К. Komiya, D. Kiga, S. Yokoyama, T. Yokomori, M. Hagiya, "Molecular computation by DNA hairpin formation," Science, vol. 288, pp. 1223-1226, 2000.

47. S. Tsaftaris, A. Katsaggelos, T. Pappas, E. Papoutsakis, "DNA Computing from a Signal Processing Viewpoint," IEEE Signal Processing Magazine, pp. 100-106, 2004.

48. A. Macula, S. Gal, C. Andam, Т. E. Renz, M. A. Bishop, "PCR nonadaptive group testing of DNA libraries for biomolecular computing and taggant applications," Discrete Mathematics, Algorithms and Applimtions, vol. 1, n. 1, pp. 59-69, 2009.

49. В. H. Тутубалин, Теория вероятностей и случайных процессов, Москва: Издательство МГУ, 1992.

50. A. Dembo, О. Zeitouni, Large Deviations Techniques and Applications, Boston, MA: Jones and Bartlett, 1993.

51. Э. Рейнгольд, Ю. Нивергельт, H. Део, Комбинаторные алгоритмы. Теория и практика, Москва: Мир, 1980.

52. P. J. Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, UK, 1994.

53. D. T. Tang, L. R. Bahl, "Block Codes for a Class of Constrained Noiseless Channels," Inform, and Control, v. 17, n. 5, pp. 436-461, 1970.

54. Handbook of combinatorics, edit. R. L. Graham, M. Grotschel, L. Lovasz, v. 2, MIT Press, 1995.Работы автора по теме диссертации

55. А. Г. Дьячков, А. Н. Воронина, "ДНК-коды для аддитивного стебельного сходства," Проблемы Передачи Информации, т. 45, н. 2, стр. 56—77, 2009.

56. А. Н. Воронина, "Об объч,мах сфер для стебельного расстояния," Проблемы Передачи Информации, т. 46, н. 1, стр. 9-19, 2010.

57. A. G. D'yachkov, А. N. Voronina, "DNA Codes Based on Stem Hamming Similarity," Proc. 11th Int. Workshop Algebraic and Combinatorial Coding Theory, Памнорово, Болгария, 2008, стр. 85-91.

58. А. Г. Дьячков, А. Н. Воронина, "ДНК-коды, основанные на весовом стебельном сходстве Хэмминга," Сборник трудов ИТиС'08, Геленджик, Россия, 2008, стр. 316-320.