Список обозначений
В настоящей работе используется следующая система обозначений. Нумерация определений, утверждений, формул и рисунков начинается заново в каждой главе, и перед каждым номером ставится номер соответствующей главы. Таким образом, формулы в главе 1 будут иметь номера (1.1), (1.2) и т.д. При этом различные типы утверждений имеют независимую нумерацию, например: теорема 1.1, теорема 1.2, лемма 1.1 и т.д.
Конец доказательства обозначается символом и.
Ниже приводится список наиболее важных обозначений, используемых в работе. Для каждого из них (кроме общих) указана страница, на которой вводится данное обозначение. Там, где это возможно, приводится номер <1>ормулы , а также дается краткое пояснение.
Общие обозначения
х
X
равенство но определению множество целых чисел {1,2,..., п}
стандартный </-ичмый алфавит {0,1,..., г/ - 1} , г/ = 2.4.... - четное
множество последовательностей {ж = (Жі,х'2,.... хп) : ж, Є Ач, г € [п]}
целая часть снизу действительного числа и
целая часть сверху действительного числа и
элемент, комплементарный к х
последовательность, сопряженная к ж
ш(а,Ь) весовая функция на множестве пар А2
У) произвольная стебельная функция сходства на AJ
Р{х,у) произвольная стебельная функция расстояния на Aq
X = ||xj(u)|| произвольный ДНК-код, г G [п], и G [iV], длины п и объема N
x[j) j -тос кодовое слово кода X
jV(n, D) максимальный объем ДНК-кода длины п с расстоянием D
т
ЕС
скорость ДНК-кода для доли расстояния (I > и математические ожидание £
Обозначения к главе 1
[А,С,С. Т) 10 ДНК-основания: адснин (Л), цитозин (С), гуанин (О),
тимидин (Т)
энергия гибридизации ДНК-ценочек х и у ДНК-цспочка, сопряженная к цепочке х
11
X 10
Н{х,у) 21, (1.4)
Ь(х,у) 21, (1.4)
Р.(п, О) 26, (1.7)
Р2{П,Р) 26, (1.7)
последовательностью и € А7! и ее сопряженной И меньше Б вероятность того, что расстояние между двумя случайными последовательностями и, V 6 А” меньше О
Обозначения к главе 2
^\{х,у) 51, (2.1) аддитивное стебельное 1 -сходство между х и у
51, (2-0 индикатор равенства г-тых стеблей х и у
?Мя,2/) 51, (2.2) аддитивное стебельное 1 -расстояние между хну
»//(*» у) 51, (2.2) индикатор неравенства г-тых стеблей хну
(н, О), -код 52, (2-4) ДИК-код длины п с аддитивным стебельным 1-расстоянием
А^л, Б) 52 максимальный обьем (п, ОД-кода
М,,{п) 52 (\ -ичный коде проверкой на четность, подмножество А”
С Г(р) 54 поле Галуа порядка р
И7 (тут) 55 множееггво многочленов от т переменных порядка < г, заданных на С/7'(4), с коэффициентами и значениями в вУ(‘
1?4(г,т) 56 код Рида-Маллера над ОБ(А) г-ого порядка длины 4т
5(1)(х,?/) 69 неаддитивное стебельное 1 -сходство между хну
Т>Ы(х, у) 69 неаддитивное стебельное 1 -расстояние между хну 3
(п,2))(1)-код 69 ДНК-код длины п с нсдчдитивным стебельным
1-расстоянием Р N^(4,1)) 69 максимальный объем (п,0)^-кода
$°{х,у) 70 блоковое сходство меж,ду х и у
(п, £>)^-код 70 ДНК-код длины п с блоковым расстоянием И
Л^(п, О) 70 максимальный объем (п,О)0-кода
Обозначения к главе 3
<Si(x, у) 74, (3.1) аддитивное стебельное 1-сходство между х и у
s}(x,y) 74, (3.1) индикатор равенства г-тых стеблей х и у
X>i(ж, 2/) 74, (3.2) аддитивное стебельное 1-расстояние между х и у
Sg(n, г) 76 объем сферы радиуса г в метрике Т>х к пространстве А”
Bq(n,r) 105, (4.45) объем шара радиуса г в метрике Рх в пространстве А”
0 76 элемент (0,0,... ,0) 6 А”
77 упорядоченное множество к целых чисел
Т\[з, к) 77, (3.9) множество | : U>2, X) Ц — 6 -f
T2[s,k) 77, (3.10) множество | : t\,tk+i > 0, U >1, Y^U = ti — (я-Ь/с) |
S0(n,r) 78 cc|>epa с центром в точке О радиуса г в Л" в метрике Т>х
pF(n, Р) 85, (3.27) распределение вероятностей
PF{n, D) 85, (3.27) функция распределения
Pnin(D) 86 биномиальное распределение вероятностей
(п. ОД-код 87 ДНК-код длины п с аддитивным стебельным 1-расстоянием D
N1(71,0) 87 максимальный объем (n, jD)i-кода
Обозначения к главе 4
(ж, 2/) 92, (4.1) аддитивное стебельное 1 -сходство между хну
з}(хуУ) 92, (4.1) индикатор равенства г-тых стеблей хну
Р\{х, у) 92, (4.2) аддитивное стебельное 1-расстояние между хну
4
П1(х,у) 92, (4.2) индикатор неравенства г-тых стеблей х и у
(п, ОД-код 92, (4.3) ДНК код длины п с аддитивным стебельным 1-расстоянием Г)
NMD) 93 максимальный объем (гг, £>)х-кода
Ri(d) 93, (4.4) скорость (гг, г/п)х-кода дня доли расстояния в.> §
Vi (d) 93, (4.5) граница Плоткина для скорости (гг, с//г) 1 -кодов
Li(d) 93, (4.6) граница Варшамова-Гилберта для скорости (п, г/ц)х -кодов
EM 94, (4.10) граница Элайеса скорости (п, г/п)х -кодов
Vi 98, (4.25) случайная величина у}{х,у) для случайных х и у
P}(n, D) 99, (4.27) вероятность Рг|х>1(ж,ж) < £>} дчя случайного х
PM D) 99, (4.28) вероятность Рг {V] (ж, ?/) < £>} для случайных х и у
EM 99, (4.29) логарифмическая асимптотика 1и:роятности Р2* (п, Нп)
IMb) 101, (4.35) функция Д(а,Ь) = 1 — аЬ, а}Ь €Е {0,1}
мм 102, (4.36) матрица Маркова цепи Маркова ёг
Ai(u) 93, (4.7) максимальное собственное значение матрицы МДд)
иМ 93, (4.6) логарифм К^АДи)
S7(n,r) 105 объем с<[)сры радиуса г в метрике в пространстве Ад
&q(n, r) m cs in о i—< объем шара радиуса г в метрике Т)х в пространстве Ад
Обозначения к главе 5
£ш(®>2/) 111,(5.2) аддитивное стебельное ю-сходство между хну
111,(5.2) аддитивное стебельное w-сходство между
г-ми стеблями хну Vw(x,y) 112,(5.3) аддитивное стебельное w-расстояние между хну
т1?{х,у) 112,(5.3) аддитивное стебельное w -расстояние между
г-ми стеблями х и у (гг, D)w -код 113,(5.5) ДНК-код длины п с аддитивным стебельным
w -расстоя н нем D N„(71, D) 113 максимальный объем (гг, D)w -кода
IlrV(d) 113, (5.6) скорость (гг, dn)w -кода дчя доли расстояния d > О
р ИЗ распределение вероятностей р(а, Ь) на множестве Ад
5
р|(«) 114
Р г(«) 114
/>1(6|а) 114
/>2(6|л) 114
та р) 114, (5.9)
Т„ 114, (5.9)
'гМ л м 115, (5.16)
ъм 114, (5.12)
Ьш((1у р) 116, (5.17)
В:М 116
чГ 121, (5.34)
ш 122
ь 125, (5.48)
/,„(«,6, С,(1) 115, (5.14)
М,„(и, р) 115, (5.15)
Аи-(и,р) 115
Рш(«» р) 116, (5.17)
ш(а, Ь) 127
128, (5.51)
и 130, (5.52)
вероятность 52 р(а, Ь)
ЬС-4,
вероятность 52 р(^>а)
Ь<£Л„
условная вероятность р(а,6)/р!(а) условная вероятность р(Ь, о)//>2 (а) сумма 52 (р(а, 6) - р1 («, 6)) ш (а,
а,6с-47
с условием Маркова
(??., п?77.)ш-кодов с распределением р
граница Варшамона-Гилберта скорости (11,(1и)го-кодов
максимальный вес пары ив Л*
в других случаях
матрица Маркова цени Маркова & для распределения максимальное собственное значение матрицы Мг1,(гг, р) логарифм 1оёч Ли,(д. р) относительные веса для пар (а, Ь) е А?.
Обозначения к главе 6
(ж, у) -блок 136 общий блок последовательностей ж и у
2(ж,у) 137 множество общих блоковых подпоследовательностей
между ж и у
к(г,х,у) 137 м и ни мальное число общих (ж, у) -блоков в г
5«(х,у) 137,(6.1) неаддитивное стебельное 1 -сходство между ж и у
б
S(w)[x,y) 138,(6.3) неаддитивное стебельное w -сходство между хну
T>w{x,y) 140,(0.9) неаддитивное стебельное 1 -расстояние между х и у
Т>^(х, у) 139,(0.6) неаддитивное стебельное ш-расстояние между х и у
(n,D)(l)-код 140,(0.10) ДНК-код длины п с неаддитивным стебельным
1 -расстоянием D
(п, Р)^-код 139 ДНК-код длины п с неаддитивным стебельным
w -расстоянием D N^l\n,D) 139 максимальный объем (п, £))^-кода
ЛГ(®)(п, D) 140 максимальный объем (n, D)^ -кода
R^w\d) 140,(6.11) скорость (n,dn)^ -кода для доли расстояния d > 0
L 140 подмножество Aq , замкнутое относительно сопряжения
А) 141, (6.12) пустое множество 0
Li 141, (6.12) множество {ТА1}
Lo 141, (6.12) множество {ТА, АТ]
Ьз 141, (6.13) множество {ТА, АА,ТТ]
L\ 141,(6.12) множество {ТА, АТ, АЛ, ТТ}
Ьь 141, (6.13) множество {ТА, АТ, АЛ, ТТ, AG, СТ)
Ls 141,(6.13) множество {TA,AT,AA,TT,AG,CT,GA,TC}
DNA{n,L) 141 ансамбль Фибоначчи с длиной кодовых слов п для
множества L (кратко, [n, Ц )
АДп) 141 объем множества DNА{п, L)
Njt(n,D) 141 максимальный размер ДНК (п, £>)(1^-кодов X С DNA{n, L)
Rr.(d) 141,(6.14) скорость ДНК-кодов для L-ансамбля Фибоначчи
и доли расстояния d > 0 wL 141, (6.15) минимальный вес нары из Aq\L
RiXd) 145, (6.29) граница случайного кодирования для DNA(n, L) -ансамбля
d/y 145 критическая доля расстояния для DNA(п, L) -ансамбля
RM(d) 146 граница случайного кодирования для ДНК (n, dn)M -кодов
d(w) 146,(6.33) критическая доля расстояния для ДНК (n,dn)^ -кодов
w(a,b) 147 относительные веса дня нар (a, b) € Aq
Pyl\n,D\L) 151 вероятность Рг{^^(и,П) > n — D} для случайного и € А?
P^\n,D\L) 151 вероятность 1>г{5^1^(и, v) > п —/)}} для
случайных и, v £ Л.?
7
[п, Ь\а 165 последовательности х 6 [гс, Ц , такие что х„ = а
[л> Ца,ь 165 последовательности х £ [гг, X], такие что = а и хп = Ь
8
ч
Глава 1
Введение, постановка задачи и результаты
В настоящей главе мы опишем задачу, возникшую из потребностей молекулярной биологии, которая приводит к кодам специального вида, являющихся объектом изучения теории кодирования ДНК-последовательностей.
В разделе 1.1 мы приводим необходимые сведения из молекулярной биологии и описываем реальный эксперимент, из которого и возникает рассматриваемая задача. В разделе 1.2 будут сделаны некоторые общие предположения, используемые в математической модели рассматриваемого явления. Там же обсуждается специфика сформулированной математической задачи по сравнению с классически рассматриваемой в теории кодирования. Раздел 1.3 посвящен описанию важного для нашего случая метода случайного кодирования для ДНК-кодов, который будет использоваться далее во всех главах работы. В разделе 1.4 мы приведем краткую сводку основных результатов диссертации. Последний раздел 1.5 посвящен историческому обзору предшествующих работ но данной тематике, также мы упомянем о параллельных направлениях исследований в этой области и скажем о возможных теоретических и практических приложениях полученных результатов.
1.1 Биологическая мотивация
Здесь мы расскажем о биологических предпосылках, из которых возникла рассматриваемая нами математическая модель, и приведем описание разработанного в диссертации П. А. Виленкина [21] и опубликованного в [17] примера реального биологического эксперимента, где эта модель может найти свое применение.
9
1.1.1 Последовательности ДИК и их свойства
В упрощенном виде молекулу (одинарную цепочку) ДНК можно считать цепочкой из элементов, называемых основаньями. Существует четыре типа оснований: аденип (Л), цитозин (С), 'гуанин ((7) и тпмидин (Т). Внутренняя структура этой молекул!.! однозначно определяет ее направление, так что один конец данной цепочки называется ее началом, а другой - окончанием. Таким образом, молекулы ДНК могут быть адекватным образом представлены как конечные слова в четверичном алфавите Л.\ — {А,С,С,Т}. Такие слова мы будем называть ДНК-последоватслъиостями, или ДНК-цепочками.
Важнейшим свойством молекул ДНК является способность противоположно направленных ДНК-цеиочек сращиваться друг с другом и образовывать двойную молекулу ДНК, или ДНК-дуплекс. Процесс образования ДНК-дуплекса называется ДНК-гибридизацией. Сращивание происходит за счет образования водородных связей между комплементарными основаниями в разных ДИК-цеиочках, расположенными друг напротив друга. Основание /1 является комплементарным к основанию Т, а основание С - к С? и наоборот.
ДНК-цепочка х, сопряженная к данной ДНК-цеиочке х, называется по-другому ее преобразованием Ватсопа-Крнка и получается изменением направления этой ДНК-цепочки и последующей заменой всех букв в ней на комплементарные к ним. Например, ДНК-цепочки (ААСС) и (ССТТ) являются взаимно сопряженными. При сращивании двух взаимно сопряженных ДНК-цеиочек возникает дуплекс, называемый дуплексом Ватсона-Крика. При этом все основания одной цепочки соединяются с соответствующими комплементарными основаниями в другой цепочке. Кроссгибридизация ДНК-цеиочек происходит, когда дуплекс образуется из несопряжеиных ДНК-цеиочек. Кроссгибридизация происходит не всегда, но такая возможность существует.
На рис. 1.1 изображен пример дуплекса. На нем используются стандартные для молекулярной биологии обозначения 5' и 3' для начала и окончания цепочек соответственно (для большей наглядности мы также пометили направления в цепочках стрелками). В данном примере соединились две пары оснований " А —Т" и три нары оснований "С — С!|. Остальные четыре пары оснований не комплементарны, так что они не сращиваются.
Каждый ДПК-дунлекс характеризуется своей стабильностью. При образовании дуплекса (т. е. водородных связей) выделяется некоторая энергия. Для того, чтобы расплавить данный дуплекс на две отдельные цепочки (т. е. разорвать эти связи), необходимо
10
Рис. 1.1. Дуплекс, образованный
ДНК-цеиочкими длины 10 х = AACGTGGCA и у = CACCAGGTA
3'
3'
Рис. 1.2. Дуплексы, образованные ДНК-цепочкями х = ЛССС, у = GGAT, и их сопряженными х = GGCT, у = АТСС
затратить такую же энергию. Соответственно, чем большей будет величина этой энергии, тем более прочной (стабильной) будет рассматриваемый ;іунлекс. В биологии такая энергия называется энергий гибридизации ДНК-дунлекеа, а се величина зависит от числа образовавшихся водородных связей. Энергию гибридизации для двух ДНК-нослсдователыюстсй х и у будем обозначать через £(х,у).
Считается, что наилучишм образом на сегодняшний день энергию гибридизации описывает так называемая модель ’’ближайшего соседа", впервые предложенная в работе |2б|. Покажем на примере из 1.1, каким образом в рамках данной модели предлагается вычислять эту величину. Для ДНК-цепочек х = AACGTGGCA и у — CACCAGGTA найдем все стебли (блоки длины 2), состоящие из 2 соседних оснований цепочки х, соединившихся с 2 соседними основаниями цепочки у . В данном случае в это будут стебли (АС) — [GT), (TG)-(CA) л (GG)-(CC), где слева указаны 2 соседних основания цепочки х , а справа - у. Далее, из некоторых заранее проведенных экспериментов, известны термодинамические веса всех таких стеблей, состоящих из 2 сцепленных цепочек длины 2, каждая из которых является преобразованием Ватсона-Крика второй цепочки. Для того, чтобы вычислить энергию гибридизации ДНК-дуплскса, надо сложить термодинамические веса всех образовавшихся стеблей. Более подробно с моделью "ближайшего соседа" можно познакомиться в работах [26|-[30].
Обратим внимание на следующие две важные особенности указанной модели:
1) Энергия гибридизации зависит не просто от числа водородных связей, образовавшихся в процессе гибридизации, но от числа образовавшихся стеблей. Во-первых, это означает, что такие сцепленные основания, "соседи" которых не образовали водородных связей, ничего не добавляют к энергии гибридизации. Во-вторых, при подсчете энергии гибридизации нам недостаточно знать, сколько и каких оснований образовали связи (сколько оснований А, С, G и Т цепочки х сцепились с комплементарными основаниями в цепочке у ), также необходимо представлять и их взаимное
11
3' 5' з' У II 3'
1ДтП7.Е1=ч г ПШЦ-н »’ ТП~Г тлтп^
3' 5' 3' 5' .У
Г./
Рис. 1.3: Базовые конфигурации ДНК-дуплоксов: нормальное; расположение, сдвиг, нетля
расположение.
2) Хоти в нашем примере ДНК-цепочки сцепились основаниями, стоящими на "комплементарных" позициях (на второй в х и второй с конца в у, на третей в х и третьей с конца в //, и т.д.), это не является общим правилом. Основания одной цепочки могут сцепляться с комплементарными основаниями второй, слоящими на любых позициях, с единственным условием, что образовавшиеся связи не должны пересекаться. Иными словами, допустимыми являются все ситуации, отраженные на рис. 1.3.
Отметим, что физические свойства ДНК-цсиочек определяют следующие свойства, которым удовлетворяет функция £(х, у):
Е1) Очевидно, что функция должна быть симметрична:
£(х,у) = £(у,х).
Е2) Поскольку сращивание ДНК-цсиочек происходит за счет образования водородных связей между комплементарными основаниями, то наиболее стабильными будут являться .дуплексы Ватсона-Крика. Иными словами, для любой фиксированной ДНК-цепочки х наибольшая энергия гибридизации £(х,у) достигается для ДНК-цепочки х, являющейся преобразованием Ватсона-Крика ДНК-цепочки х :
у) < £{х,х) для любого у.
ЕЗ) Кроме того, энергия гибридизации ДНК-ценочек х и у должна быть равна энергии гибридизации ДНК-ценочек х и у:
£{х,у) = £(§,'£),
поскольку и та, и другая пара ДНК-цепочек сцеилены одинаковыми основаниями, расположенными в одинаковой очередности. Различие состоит только в том, что
12
порядок следования этих основании противоположен, и если какое-либо сцепленное основание принадлежит последовательности х, то соответственное основание для второй пары принадлежит последовательности у и наоборот (см. рис. 1.2).
1.1.2 Описание эксперимента
В биологических приложениях, использующих свойство ДПК-гибридизации, возникновение кроссгибридизации нежелательно, поскольку оно ведет к появлению ошибок в результатах опытов. Возникает задача построения максимальных по объему ансамблей одинарных ДНК-цепочек, таких что кроссгибридизация в одном ансамбле невозможна. Иначе говоря, энергия гибридизации между любыми двумя кесоиряжеиными ДНК-ценочками в ансамбле должна быть ниже установленного порога, соответствующего предполагаемой температуре плавления в заданных условиях эксперимента. Ансамбли, удовлетворяющие данным требованиям и состоящие из пар взаимно сопряженных ДНК-цеиочск, т.с. инвариантные относительно преобразования Ватсона-Крика, могут быть названы четверичными ДНК-кодами (как формализуется это понятие, мы расскажем ниже в следующем разделе). На сегодняшний день предложены различные комбинаторные, эвристические и биологические методы нахождения ДНК-кодов, разработаны программные алгоритмы для пх генерирования.
Расскажем об одном типичном примере |21| применения ДНК-кодов. Предположим, что мы имеем N/2, где N четно, образцов, каждый из которых состоит из большого числа некоторых одинаковых молекулярных объектов. Требуется провести некоторый эксперимент над всеми данными образцами. Можно рассмотреть их независимо, и тогда необходимо выполнить N/2 экспериментов. Но если каждый из них является дорогостоящим, то можно поступить следующим образом: объединить все образцы и провести один эксперимент со всей полученной субстанцией. После этого необходимо выделить из данной массы некоторое количество экземпляров объектов каждого типа, чтобы проанализиро-вать результаты эксперимента. Схематически этот процесс изображен на рис. 1.4.
Для решения подобных задач можно использовать молекулы ДНК в качестве меток. Выберем N/2 последовательностей ДНК х(1),.... х(Л|Т/2) € А” для некоторого п > 1, которые назовем собственными метками, а также N/2 последовательностей ?/(1),..., у (N/2) <= А", которые назовем адресными метками. Современная технология позволяет сгенерировать любую заданную ДНК-ценочку, а также создать любое колнче-
13
Рис. 1.4: Модель эксперимента
стпоее копий (клонов). Пользуясь данной возможностью, мы для каждого і = I,..., N/2 сгенерируем большое количество цепочек ж(і) и присоединим к каждому объекту В 1-М образце но одной цепочке, в результате чего все объекты во всех образцах оказываются помеченными соответствующими собственными метками. Затем образцы смешиваются, и над ними проводится эксперимент, который, как мы предполагаем, не оказывает воздействия на метки.
Для последующего разделения объектов мы используем адресные метки. Возьмем некоторую пластинку (чип), на которой выделим N/2 областей, отделенных друг от друга. Для каждого числа j = 1,..., N/2 сгенерируем большое количество экземпляров метки У и) 11 присоединим их к у'-й области на чипе. Затем поместим чин в имеющуюся смесь образцов. В результате возникает ситуация, схематически изображенная на рнс. 1.5.
Каждая пара последовательностей может сцепиться друг с другом (кроме неподвижных адресных меток). В частности, любая собственная метка х(г) может образовать ДНК-дуплекс с любой адресной меткой у(з), и таким образом г-й объект окажется закрепленным на у'-й области на чипе. Поскольку имеется большое число объектов каждого типа, а также большое число адресных меток каждого тина, то в итоге на каждой области чипа окажется закреплено много экземпляров каждого объекта.
Далее предположим, что известно, каким образом в данных условиях эксперимента энергия гибридизации £(х, у) каждой пары ДНК-ценочск хну соотносится с уровнем
14
©ч У(1)у т(1) • • х(1) •у(1) У(2) [2) (5и(ДГ) •••••••• * 4 • (2) (5и*о •«(2) у(Л|)|||у(^
Область 1 Область 2 Область N
Рис. 1.5: Смесь образцов с собственными метками и чин с адресными метками
£(*(Л»У(Й)
£(*(*), У (Л)
©
у О'
у О'
! *(7)
@
у О'
ж(Д0
Область ?
Рис. 1.6: Схема отделении объектов -го чина на соответствующей области чипа
15
температуры Т, минимально необходимым для плавления ДНК-дуплекса, образованного х и у. Пусть имеется некоторый порог Е и энергетический разрыв АЕ > О, причем для каждого значения выполнено неравенство > Е + АЕ, а для каждого
значения I Ф .7 выполнено неравенство £(х(г), 2/С?)) < Е. Если смесь нагреть до температуры, соответствующей некоторому уровню энергии гибридизации в интервале от Е до Е + АЕ, то все "посторонние" ДНК-дунлексы заведомо расплавятся, после чего для каждого у ~ 1,...,Дг/2 в области у останутся только объекты у-го тина (см. рис. 1.6) (такие ДНК-дунлексы заведомо сохранятся). Таким образом задача будет решена.
Мы также рассматриваем следующее дополнительное условие: не только величины £(х1,у3) должны быть меньше Е для всех г ^ .7, но также и величины £(хих3) для всех г и j (в том числе и при i — j). Это требование основано на том, что собственные метки могут образовывать дуплексы друг с другом, и если они окажутся достаточно стабильными, то в смеси окажется слишком мало (или даже не останется совсем) свободных объектов соответствующих типов, которые могут быть отделены от остальных.
Очевидно, что это последнее требование влечет за собой условие, что метки .т, и у3 должны быть различны дня всех значений г и у . Также но смыслу задачи очевидно, что метки одного типа с различными номерами не должны совпадать, т. е. хх ф х3 и yi Ф у3 для всех г ф j. Таким образом, все N рассматриваемых меток должны быть попарно различны.
1.1.3 Постановки задач
Из данного выше описания эксперимента вытекают следукйцие задачи.
Задача 1. Задано пороговое значение энергии гибридизации Е > 0. Требуется построить /V, где N фиксировано условиями эксперимента, различных ДНК-цеиочек (меток) х(1),..., ж(/У/2), 3/(1),..., у(N/2) , таких что £(х(г), у(г)) > Е + АЕ для всех значений ?, £(х(1),у(])) < Е для всех г ф j, и £{х{1), ж(у)) < Е для всех г и
Задача 2. Задано число оснований п в ДНК-метках и пороговое значение энергии гибридизации Е > 0. Необходимо выяснить, какое максимальное число различных образцов можно будет тестировать одновременно, используя ДНК-метки заданной длины. Иными словами, требуется найти максимальное N, такое что для набора из N ДНК-мсток ж(1),.. •, х(Ы/2), 2/(1),..., у(М/2) € А” будет выполняться условие: £{х(г), 2/(0) >
16
- Київ+380960830922