Подходы теории кодирования к дизайну нуклеиновых кислот

Построение кода ДНК относится к применению теории кодирования к разработке систем нуклеиновых кислот для области вычислений на основе ДНК .

Введение

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

Область вычислений ДНК была основана в основополагающей статье Леонарда М. Адельмана. Его работа важна по ряду причин:

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

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

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

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

Определения

Код ДНК — это просто набор последовательностей в алфавите. ${\mathcal {Q}}=\{{\mathit {A}},{\mathit {T}},{\mathit {C}},{\mathit {G}}\}$.

Каждое пуриновое основание представляет собой дополнение Уотсона-Крика к уникальному пиримидиновому основанию (и наоборот) — аденин и тимин образуют комплементарную пару, как и гуанин и цитозин . Это сочетание можно описать следующим образом: ${\bar {A}}=T,{\bar {T}}=A,{\bar {C}}=G,{\bar {G}}=C$.

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

Основное внимание при кодировании ДНК уделялось созданию больших наборов кодовых слов ДНК с заданными свойствами минимального расстояния. Для этого заложим необходимую основу для дальнейшего движения.

Позволять ${\mathit {q}}={\mathit {q}}_{1}{\mathit {q}}_{2}\dots {\mathit {q}}_{n}$ быть длинным словом ${\mathit {n}}$ над алфавитом ${\mathcal {Q}}$. Для $1\leqslant i\leqslant j\leqslant n$, мы будем использовать обозначение ${\mathit {q}}_{[i,j]}$ для обозначения подпоследовательности ${\mathit {q}}_{i}{\mathit {q}}_{i+1}\dots {\mathit {q}}_{j}$. Кроме того, последовательность, полученная обращением ${\mathit {q}}$ будет обозначаться как ${\mathit {q}}^{R}$. Дополнение Уотсона-Крика или обратное дополнение q определяется как ${\mathit {q}}^{RC}={\mathit {{\bar {q}}_{n}}}{\mathit {{\bar {q}}_{n-1}}}\dots {\mathit {{\bar {q}}_{1}}}$, где ${\mathit {{\bar {q}}_{i}}}$ обозначает дополнения Уотсона-Крика пару оснований ${\mathit {q}}_{i}$.

Для любой пары длин- ${\mathit {n}}$ слова ${\mathit {p}}$ и ${\mathit {q}}$ над ${\mathcal {Q}}$, расстояние Хэмминга ${\mathit {d}}_{H}({\mathit {p}},{\mathit {q}})$ это количество позиций ${\mathit {i}}$ на котором ${\mathit {p}}_{i}\neq {\mathit {q}}_{i}$. Далее определим расстояние обратного Хэмминга как ${\mathit {d_{H}}}^{R}({\mathit {p}},{\mathit {q}})={\mathit {d}}_{H}({\mathit {p}},{\mathit {q}}^{R})$. Аналогично, расстояние Хэмминга с обратным дополнением равно ${\mathit {d}}_{H}^{RC}({\mathit {p}},{\mathit {q}})={\mathit {d}}_{H}({\mathit {p}},{\mathit {q}}^{RC})$. (где $RC$ означает обратное дополнение )

Еще одно важное соображение при проектировании кода, связанное с процессом гибридизации олигонуклеотидов, касается содержания GC последовательностей в коде ДНК. GC -контент , ${\mathit {w}}_{GC}({\mathit {q}})$, последовательности ДНК ${\mathit {q}}={\mathit {q}}_{1}{\mathit {q}}_{2}\dots {\mathit {q}}_{n}$ определяется как количество индексов ${\mathit {i}}$ такой, что ${\mathit {q}}_{i}\in \{G,C\}$. Код ДНК, в котором все кодовые слова имеют одинаковое GC-содержимое. $w$, называется постоянным кодом GC-содержимого .

матрица Обобщенная Адамара ${\mathit {H}}\equiv {\mathit {H}}(n,\mathbb {C} _{m})$ это ${\mathit {n}}$ $\times$ ${\mathit {n}}$ квадратная матрица с элементами, взятыми из множества ${\mathit {m}}$корни единства, $\mathbb {C} _{m}=\{e^{-2\pi {\mathit {i}}{\mathit {l}}/{\mathit {m}}}\mid l=0,\dots ,m-1\}$, что удовлетворяет ${\mathit {H}}{\mathit {H}}^{*}$ = ${\mathit {n}}{\mathit {I}}$. Здесь ${\mathit {I}}$ обозначает единичную матрицу порядка ${\mathit {n}}$, а * означает комплексное сопряжение. Мы будем заниматься только делом ${\mathit {m}}={\mathit {p}}$ для какого-то премьера ${\mathit {p}}$. Необходимое условие существования обобщенных матриц Адамара. ${\mathit {H}}({\mathit {n}},\mathbb {C} _{p})$ это что ${p}|{n}$. Матрица экспоненты , $E({\mathit {n}},\mathbb {Z} _{p})$, из ${\mathit {H}}({\mathit {n}},\mathbb {C} _{p})$ это ${\mathit {n}}\times {\mathit {n}}$ матрица с записями в ${\mathit {Z}}_{p}=\{0,1,2,\dots ,{\mathit {p}}-1\}$, получается заменой каждой записи $(e^{-2\pi {\mathit {i}}l/{\mathit {m}}})$ в ${\mathit {H}}({\mathit {n}},\mathbb {C} _{p})$ по показателю степени ${\mathit {l}}$.

Элементы матрицы показателей Адамара лежат в поле Галуа. ${\text{GF}}(p)$, а его векторы-строки составляют кодовые слова того, что будет называться обобщенным кодом Адамара.

Здесь элементы ${\mathit {E}}$ лежать в поле Галуа ${\text{GF}}(p)$.

По определению обобщенная матрица Адамара ${\mathit {H}}$ в стандартной форме имеет только 1 с в первой строке и столбце. $({\mathit {n}}-1)\times ({\mathit {n}}-1)$ квадратная матрица, образованная оставшимися элементами $H$ называется ядром ​ ${\mathit {H}}$, и соответствующая подматрица матрицы экспонент ${\mathit {E}}$ называется ядром конструкции. Таким образом, за счет исключения нулевого первого столбца возможны циклические обобщенные коды Адамара, кодовые слова которых являются векторами-строками выколотой матрицы.

Кроме того, строки такой матрицы экспоненты удовлетворяют следующим двум свойствам: (i) в каждой из ненулевых строк матрицы экспоненты каждый элемент $\mathbb {Z} _{p}$ появляется постоянное число, ${\mathit {n}}/{\mathit {p}}$, раз; и (ii) расстояние Хэмминга между любыми двумя строками равно ${\mathit {n}}({\mathit {p}}-1)/{\mathit {p}}$.

Недвижимость У

Позволять ${\mathit {C_{p}}}=\left\{1,x,x^{2},\ldots ,x^{p-1}\right\}$ — циклическая группа, порожденная ${\mathit {x}}$, где $x=\exp(2\pi ij/p)$ это сложный примитив $p$корень единства, и $p>2$ является фиксированным простым числом. Далее, пусть ${\mathit {A}}=(x^{a_{i}})$, ${\mathit {B}}=(x^{b_{i}})$ обозначим произвольные векторы над $\mathbb {C} _{p}$ которые имеют длину ${\mathit {N}}=pt$, где ${\mathit {t}}$ является положительным целым числом. Определите набор разностей между показателями ${\mathit {Q}}=\{a_{i}-b_{i}\mod p:i=1,2,\ldots ,N\}$, где ${\mathit {n_{q}}}$ кратность элемента ${\mathit {q}}$ из ${\text{GF}}(p)$ который появляется в ${\mathit {Q}}$.

Вектор ${\mathit {Q}}$ Говорят, что он удовлетворяет свойству U тогда и только тогда, когда каждый элемент ${\mathit {q}}$ из ${\text{GF}}(p)$ появляется в ${\mathit {Q}}$ точно ${\mathit {t}}$ раз ( ${\mathit {n_{q}}}=t,q=0,1,\ldots ,p-1$)

Следующая лемма имеет принципиальное значение при построении обобщенных кодов Адамара.

Лемма. Ортогональность векторов по ${\mathit {C_{p}}}$ – Для фиксированных простых чисел ${\mathit {p}}$, произвольные векторы ${\mathit {A}},{\mathit {B}}$ длины ${\mathit {N}}=pt$, элементы которого взяты из ${\mathit {C_{p}}}$, ортогональны, если вектор ${\mathit {Q}}$ удовлетворяет свойству U , где ${\mathit {Q}}$ это совокупность различий $\mod {\mathit {p}}$ между показателями Адамара, связанными с ${\mathit {A}},{\mathit {B}}$.

М-последовательности

Позволять ${\mathit {V}}$ быть произвольным вектором длины ${\mathit {N}}$ элементы которого находятся в конечном поле ${\text{GF}}(p)$, где $p$ является простым числом. Пусть элементы вектора $V$ составляют первый период бесконечной последовательности $a(V)$ который является периодическим периода $N$. Если $N$ является наименьшим периодом для создания любой подпоследовательности, последовательность называется M-последовательностью или максимальной последовательностью наименьшего периода, полученной путем циклической перестановки $N$ элементы. Если всякий раз, когда элементы $V$ переставляются произвольно, чтобы получить $V^{*}$, последовательность $a(V^{*})$ является M-последовательностью, то последовательность $a(V)$ называется М-инвариантным . Следующие теоремы представляют собой условия, обеспечивающие М-инвариантность . В сочетании с определенным свойством однородности полиномиальные коэффициенты, эти условия дают простой метод, с помощью которого можно построить комплексные матрицы Адамара с циклическим ядром.

Цель здесь — найти циклическую матрицу ${\mathit {E}}={\mathit {E_{c}}}$ чьи элементы находятся в поле Галуа ${\text{GF}}(p)$ и чья размерность $N=p^{n}-1$. Ряды ${\mathit {E}}$ будут ненулевыми кодовыми словами линейного циклического кода $K$, тогда и только тогда, когда существует полином $g(x)$ с коэффициентами в $\mathrm {GF} (p)$, который является собственным делителем ${\mathit {x^{N}-1}}$ и который генерирует $K$. Чтобы иметь $N$ ненулевые кодовые слова, $g(x)$ должен иметь степень $N-n$. Далее, чтобы сформировать циклическое ядро ​​Адамара, вектор (коэффициентов) $g(x)$ при работе с циклическим сдвигом операция должна иметь период $N$и векторная разность двух произвольных строк ${\mathit {E}}$ (дополненный нулем) должен удовлетворять условию равномерности Батсона: ранее называлось Свойство U. Одно необходимое условие для $N$-периодичность – это $x^{N}-1=g(x)h(x)$, где $h(x)$ неприводим моник ​ . Подход здесь заключается в замене последнего требования условием, что коэффициенты вектора $[0,g(x)]$ равномерно распределены по ${\text{GF}}(p)$, т.е. каждый остаток $0,1,\ldots ,p-1$ появляется одинаковое количество раз (Свойство U). Доказательство того, что этот эвристический подход всегда создает циклическое ядро, приведено ниже.

Примеры построения кода

Построение кода с использованием сложных матриц Адамара

Алгоритм построения

Рассмотрим унитарный неприводимый полином $h(x)$ над ${\text{GF}}(p)$ степени ${\mathit {n}}$ иметь подходящего компаньона $g(x)$ степени $N-n$ такой, что $g(x)h(x)=x^{N}-1$, где вектор $[0,g(x)]$ удовлетворяет свойству U. Для этого требуется только простой компьютерный алгоритм деления в столбик. ${\text{GF}}(p)$. С $h(x)|x^{N}-1$, идеал, порожденный $g(x)\mod (x^{N}-1)$ это циклический код ${\mathit {K}}$. Более того, свойство U гарантирует, что ненулевые кодовые слова образуют циклическую матрицу, каждая строка периода $N$ при циклической перестановке, которая служит циклическим ядром матрицы Адамара $H(p,pn)$. Например, циклическое ядро ​​для $H(3,9)$ результаты от товарищей $h(x)=x^{2}+x+2$ и $g(x)=x^{6}+2x^{5}+2x^{4}+2x^{2}+x+1$. Коэффициенты $g$ указать, что $\{0,1,6\}$ набор относительных разностей, $\mod 8$.

Теорема

Позволять ${\mathit {p}}$ быть простым и ${\mathit {N}}+1={\mathit {pn}}$, с ${\mathit {g}}(x)$ монический полином степени ${\mathit {N}}-{\mathit {n}}$ расширенный вектор коэффициентов которого $C=[{\mathit {c}}_{0},{\mathit {c}}_{1},\ldots ,{\mathit {c}}_{N-1}]$ являются элементами ${\text{GF}}(p)$. Предположим, выполнены следующие условия:

1. вектор $C=[{\mathit {c}}_{0},{\mathit {c}}_{1},\dots ,{\mathit {c}}_{N-1}]$ удовлетворяет свойству U, и
2. $g(x)h(x)=x^{N}-1$, где $h(x)$ – унитарный неприводимый полином степени $n$.

Тогда существует p -арный линейный циклический код ${\bar {K}}$ размера блока $N$, такой, что расширенный код $K=[0,{\bar {K}}]$ - матрица экспоненты матрицы Адамара $H(p,p_{n})=xK$, с $x=e^{2\pi i/p}$, где ядро $H$ является циклической матрицей.

Доказательство:

Сначала обратите внимание, что $g(x)$ моник и делит $x^{N}-1$ со степенью $N-n$. Теперь нам нужно показать, что матрица $E_{c}$ строки которого представляют собой ненулевые кодовые слова, составляют циклическое ядро ​​некоторой комплексной матрицы Адамара. $H$.

При условии ${\mathit {C}}$ удовлетворяет свойству U, все ненулевые остатки ${\text{GF}}(p)$ в C. лежать Циклически переставляя элементы $C$, мы получаем искомую матрицу показателей ${E_{c}}$ где мы можем получить каждое кодовое слово в ${E_{c}}$ путем замены первого кодового слова. (Это связано с тем, что последовательность, полученная циклической перестановкой $C$ является M-инвариантом.)

Мы также видим, что увеличение каждого кодового слова ${E_{c}}$ добавление начального нулевого элемента дает вектор, который удовлетворяет свойству U. Кроме того, поскольку код линеен, $\mod p$ векторная разность двух произвольных кодовых слов также является кодовым словом и, таким образом, удовлетворяет U. свойству Следовательно, векторы-строки расширенного кода ${\mathit {K}}$ образуют показатель Адамара. Таким образом, ${\mathit {xK}}$ является стандартной формой некоторой комплексной матрицы Адамара ${\mathit {H}}$.

Таким образом, из приведенного выше свойства мы видим, что ядро ${\mathit {E}}$ представляет собой циркулянтную матрицу, состоящую из всех $N={\mathit {p}}^{k}-1$ циклические сдвиги его первой строки. Такое ядро ​​называется циклическим ядром, где в каждом элементе $\mathbb {Z} _{p}$ появляется в каждой строке ${\mathit {E}}$ точно $(N+1)/p={\mathit {p}}^{k-1}$ раз, а расстояние Хэмминга между любыми двумя строками в точности равно $(N+1)(p-1)/p=(p-1)p^{k-1}$. ${\mathit {N}}$ ряды ядра ${\mathit {E}}$ сформировать код постоянной композиции , состоящий из ${\mathit {N}}$ циклические сдвиги некоторой длины ${\mathit {N}}$ над съемочной площадкой $\mathbb {Z} _{p}$. Расстояние Хэмминга между любыми двумя кодовыми словами в $\mathbb {Z} _{p}$ является $(p-1){\mathit {p}}^{k-1}$.

Из теоремы, объясненной выше, можно вывести следующее. (Для более подробного чтения читатель отсылается к статье Хэнга и Кука. ) Позволять ${\mathit {N}}={\mathit {p}}^{\mathit {k}}-1$ для ${p}$ премьер и ${k}\in \mathbb {Z} ^{+}$. Позволять $g(x)=c_{0}+c_{1}x+c_{2}x^{2}+\dots +c_{N-k}x^{N-k}$ быть моническим полиномом над $\mathbb {Z} _{p}$, степени N − k такая, что ${\mathit {g}}({\mathit {x}}){\mathit {h}}({\mathit {x}})={\mathit {x}}^{N}-1$ над $\mathbb {Z} _{p}$, для некоторого унитарного неприводимого полинома ${\mathit {h}}({\mathit {x}})\in \mathbb {Z} _{p}[{\mathit {x}}]$. Предположим, что вектор $({c}_{0},{c}_{1},\ldots ,{c}_{N-k},{c}_{N-k+1},\ldots ,{c}_{N-1})$, с ${\mathit {c}}_{i}=0$ для (N − k) < i < N, обладает тем свойством, что содержит каждый элемент $\mathbb {Z} _{p}$ такое же количество раз. Затем ${\mathit {N}}$ циклические сдвиги вектора ${\mathit {g}}=({\mathit {c}}_{0},{\mathit {c}}_{1},\ldots ,{\mathit {c}}_{N-1})$ образуют ядро ​​матрицы экспонент некоторой матрицы Адамара.

Коды ДНК с постоянным GC-содержанием, очевидно, могут быть построены из кодов с постоянной композицией (код с постоянной композицией в k-арном алфавите обладает тем свойством, что количество вхождений k символов в кодовом слове одинаково для каждого кодового слова). $\mathbb {Z} _{p}$ путем сопоставления символов $\mathbb {Z} _{p}$ к символам алфавита ДНК, ${\mathcal {Q}}=\{{\mathit {A}},{\mathit {T}},{\mathit {C}},{\mathit {G}}\}$. Например, используя код композиции циклической константы длиной ${\mathit {3}}^{k}-1$ над $\mathbb {Z} _{3}$ гарантированное доказанной выше теоремой и полученным свойством, и используя отображение, которое принимает $0$ к ${\mathit {A}}$, $1$ к ${\mathit {T}}$ и $2$ к ${\mathit {G}}$, получаем код ДНК ${\mathcal {D}}$ с ${\mathit {3}}^{k}-1$ и GC-содержание ${\mathit {3}}^{k-1}$. Четко ${\mathit {d_{H}}}=2.{\mathit {3}}^{k-1}$ и фактически с тех пор ${\mathit {\bar {G}}}={\mathit {C}}$ и нет кодового слова в ${\mathcal {D}}$ не содержит символа ${\mathit {C}}$, у нас также есть ${\mathit {d}}_{H}^{RC}({\mathcal {D}})\geq 3^{k-1}$. Это суммируется в следующем следствии.

Следствие

Для любого ${\mathit {k}}\in \mathbb {Z} ^{+}$, существуют коды ДНК $\mathbb {D}$ с ${3}^{k}-1$ кодовые слова длины ${3}^{k}-1$, постоянное содержание GC ${3}^{k-1}$, ${\mathit {d}}_{H}^{RC}(\mathbb {D} )\geq {3}^{k-1}$ и в котором каждое кодовое слово представляет собой циклический сдвиг фиксированного кодового слова генератора ${\mathit {g}}$.

Каждый из следующих векторов генерирует циклическое ядро ​​матрицы Адамара. $H(p,p^{n})$ (где ${\mathit {N}}+1={\mathit {p^{n}}}$, и ${\mathit {n}}=3$ в этом примере):

$g^{(1)}=(22201221202001110211210200)$;

$g^{(2)}=(20212210222001012112011100)$.

Где, ${g(x)}=a_{0}+a_{1}x+\dots +a_{n}x^{n}$.

Таким образом, мы видим, как из таких генераторов можно получить коды ДНК путем отображения ${0,1,2}$ на ${A,T,G}$. Фактический выбор отображения играет важную роль в формировании вторичной структуры кодовых слов.

Мы видим, что все такие отображения дают коды с практически одинаковыми параметрами. Однако фактический выбор отображения оказывает сильное влияние на вторичную структуру кодовых слов. Например, иллюстрированное кодовое слово было получено из ${g^{(1)}}$ через отображение $0-A;1-T;2-G$, а кодовое слово ${g^{(2)}}$ было получено от того же генератора ${g^{(1)}}$ через отображение $0-G;1-T;2-A$.

Построение кода с помощью двоичного сопоставления

Возможно, более простой подход к построению/проектированию кодовых слов ДНК — это использование двоичного отображения, рассматривая проблему проектирования как задачу построения кодовых слов в виде двоичных кодов. т.е. сопоставить алфавит кодового слова ДНК ${\mathcal {Q}}$ на набор двоичных слов длиной 2 бита, как показано: ${\mathit {A}}\to 00$, ${\mathit {T}}\to 01$, ${\mathit {C}}\to 10$, ${\mathit {G}}\to 11$.

Как мы видим, первый бит бинарного изображения четко определяет, к какой дополнительной паре он принадлежит.

Позволять ${\mathit {q}}$ быть последовательностью ДНК. Последовательность ${b(q)}$ полученное применением приведенного выше отображения к ${\mathit {q}}$, называется бинарным образом ${\mathit {q}}$.

Теперь позвольте $b(q)={\mathit {b}}_{0}{\mathit {b}}_{1}{\mathit {b}}_{2}\dots {\mathit {b}}_{2n-1}$.

Теперь пусть подпоследовательность $e(q)={\mathit {b}}_{0}{\mathit {b}}_{2}\dots {\mathit {b}}_{2n-2}$ называть четной подпоследовательностью ${b(q)}$, и $o(q)={\mathit {b}}_{1}{\mathit {b}}_{3}{\mathit {b}}_{5}\ldots {\mathit {b}}_{2n-1}$ называть нечетной подпоследовательностью ${b(q)}$.

Так, например, для $q=ACGTCC$, затем, $b(q)=001011011010$.

Затем $e(q)=011011$ и $o(q)=001100$.

Определим четную составляющую как ${\mathcal {E}}({\mathcal {C}})=\{e(x):x\in {\mathcal {C}}\}$и нечетный компонент как ${\mathcal {O}}({\mathcal {C}})=\{o(x):x\in {\mathcal {C}}\}$.

При таком выборе бинарного картирования содержание GC в последовательности ДНК ${\mathit {q}}$ = Вес Хэмминга ${e(q)}$.

Следовательно, код ДНК ${\mathcal {C}}$ является постоянным кодовым словом GC-содержимого тогда и только тогда, когда его четный компонент ${\mathcal {E}}({\mathcal {C}})$ представляет собой код постоянного веса.

Позволять ${\mathcal {B}}$ быть двоичным кодом, состоящим из $M$ кодовые слова длины ${\mathit {n}}$ и минимальное расстояние ${d_{\min }}$, такой, что ${\mathit {c}}\in {\mathcal {B}}$ подразумевает, что ${\mathit {\bar {c}}}\in {\mathcal {B}}$.

Для ${\mathit {w}}>0$, рассмотрим подкод постоянного веса ${\mathcal {B_{\mathit {w}}}}=\{u\in {\mathcal {B}}:{\mathit {w_{H}}}(u)={\mathit {w}}\}$, где ${w_{H}(\cdot )}$ обозначает вес Хэмминга. Выбирать ${\mathit {w}}>0$ такой, что ${\mathit {n}}\geq {\mathit {2w}}+\lceil {\mathit {d_{\min }}}/2\rceil$, и рассмотрим код ДНК, ${\mathcal {C}}_{w}$, со следующим выбором его четных и нечетных компонентов:

${\mathcal {E}}=\left\{a{\bar {b}}:a,b\in {\mathcal {B}}_{w}\right\}$, ${\mathcal {O}}=\left\{ab^{RC}:a,b\in {\mathcal {B}},a<_{lex}b\right\}$.

Где $<_{lex}$ обозначает лексикографическое упорядочение. $a<_{lex}b$ в определении ${\mathcal {O}}$ гарантирует, что если $ab^{RC}\in {\mathcal {O}}$, затем $ba^{RC}\notin {\mathcal {O}}$, так что отдельные кодовые слова в ${\mathcal {O}}$ не могут быть обратными дополнениями друг друга.

Код ${\mathcal {E}}_{w}$ имеет ${\left\vert {\mathcal {B}}_{w}\right\vert }^{2}$ кодовые слова длины $2n$ и постоянный вес $n$.

Более того, ${\mathit {d_{H}}}({\mathcal {E}}_{w}\geq {\mathit {d_{\min }}})$ и ${\mathit {d_{H}}}^{R}({\mathcal {E}}_{w}\geq {\mathit {d_{\min }}})$ (это потому что ${\mathcal {B}}_{w}$ является подмножеством кодовых слов в ${\mathcal {B}}$).

Также, ${\mathit {d_{H}}}(a{\bar {b}},d^{RC}c^{R})={\mathit {d_{H}}}(a,d^{RC})+{\mathit {d_{H}}}({\bar {b}},c^{R})={\mathit {d_{H}}}(a,d^{RC})+{\mathit {d_{H}}}(c,b^{RC})$.

Обратите внимание, что $b$ и $d$ оба имеют вес ${\mathit {w}}$. Это означает, что $b^{RC}$ и $d^{RC}$ иметь вес ${\mathit {n-w}}$.

И из-за ограничений по весу ${\mathit {w}}$, мы должны иметь для всех $a,b,c,d\in {\mathcal {B}}_{w}$, ${\mathit {d_{H}}}(a{\bar {b}},d^{RC}c^{R})\geq 2\lceil {\mathit {d_{\min }}}/2\rceil \geq {\mathit {d_{\min }}}$.

Таким образом, код ${\mathcal {O}}$ имеет $M(M-1)/2$ кодовые слова длины $2n$.

Из этого мы видим, что ${d_{H}}(({\mathcal {O}}))\geq {d_{\min }}$ (поскольку кодовые слова компонентов ${\mathcal {(}}O)$ взяты из ${\mathcal {B}}$).

Сходным образом, ${d_{H}^{RC}}(({\mathcal {O}}))\geq {d_{\min }}$.

Следовательно, код ДНК

${\mathcal {C}}=\bigcup _{w=d_{\min }}^{w_{\max }}{\mathcal {C}}_{w}$

с ${w_{\max }}=({n}-\lceil d_{\min }/2\rceil )/2$, имеет ${\frac {1}{2}}M(M-1)\sum _{w=d_{\min }}^{w_{\max }}\left\vert {A_{w}}^{2}\right\vert$ кодовые слова длины $2{\mathit {n}}$, и удовлетворяет ${\mathit {d_{H}}}({\mathcal {B}})\geq {\mathit {d_{\min }}}$ и ${\mathit {d_{H}}}^{RC}({\mathcal {B}})\geq {\mathit {d_{\min }}}$.

Из приведенных выше примеров можно задаться вопросом, каким может быть будущий потенциал компьютеров на основе ДНК?

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

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

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

См. также

• Теория кодирования
• Биоинформатика
• Биокомпьютеры
• Вычислительный ген

Внешние ссылки

• Курс Атри Рудры в Государственном университете Нью-Йорка, Буффало