Подходы теории кодирования к дизайну нуклеиновых кислот - Википедия - Coding theory approaches to nucleic acid design

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

Вступление

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

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

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

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

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

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

Определения

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

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

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

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

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

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

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

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

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

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

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

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

Свойство U

Позволять ${ displaystyle { mathit {C_ {p}}} = {1, x, x2, ..., xp-I}}$ - циклическая группа, порожденная ${ displaystyle { mathit {x}}}$, куда ${ Displaystyle х = ехр (2 пи j / р)}$ сложный примитив ${ displaystyle p}$корень единства, и ${ displaystyle p}$ > ${ displaystyle 2}$ фиксированное простое число. Далее, пусть ${ Displaystyle { mathit {A}} = (х ^ {а_ {я}})}$, ${ Displaystyle { mathit {B}} = (х ^ {b_ {я}})}$ обозначать произвольные векторы над ${ Displaystyle { mathit {C_ {p}}}}$ которые имеют длину ${ displaystyle { mathit {N}} = pt}$, куда ${ displaystyle { mathit {t}}}$ положительное целое число. Определите набор различий между показателями ${ displaystyle { mathit {Q}} = {{ mathit {a_ {i}}} - { mathit {b_ {i}}} mod { mathit {p}}: i = 1,2 ,. .., N}}$, куда ${ displaystyle { mathit {n_ {q}}}}$ это кратность элемента ${ displaystyle { mathit {q}}}$ из ${ Displaystyle { mathit {GF (p)}}}$ который появляется в ${ displaystyle { mathit {Q}}}$.^[4]

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

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

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

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

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

Цель, изложенная в заголовке этой статьи, - найти циклическую матрицу ${ Displaystyle { mathit {E}} = { mathit {E_ {c}}}}$ элементы которого находятся в поле Галуа ${ Displaystyle { mathit {GF (p)}}}$ и чье измерение ${ Displaystyle { mathit {N = p ^ {n} -1}}}$. Ряды ${ displaystyle { mathit {E}}}$ будут ненулевыми кодовыми словами линейного циклического кода ${ displaystyle K}$, тогда и только тогда, когда существует полином ${ Displaystyle { mathit {г (х)}}}$ с коэффициентами в ${ Displaystyle { mathit {GF (p)}}}$, который является собственным делителем ${ Displaystyle { mathit {х ^ {N} -1}}}$ и который порождает ${ displaystyle K}$.Чтобы иметь${ displaystyle N}$ ненулевые кодовые слова, ${ Displaystyle { mathit {г (х)}}}$ должен иметь степень ${ displaystyle { mathit {N-n}}}$. Далее, чтобы сгенерировать циклическое ядро ​​Адамара, вектор (коэффициентов) ${ Displaystyle { mathit {г (х)}}}$ при работе с циклическим сдвигом должен иметь период ${ Displaystyle { mathit {N}}}$, а векторная разность двух произвольных строк ${ displaystyle { mathit {E}}}$ (дополненный нулем) должен удовлетворять условию однородности Бутсона,^[5] ранее назывался Недвижимость U.Одно необходимое условие для ${ displaystyle N}$-периодичность заключается в том, что ${ Displaystyle { mathit {х ^ {N} -1}} = { mathit {г (х) ч (х)}}}$, куда ${ Displaystyle { mathit {ч (х)}}}$ является моник несводимый над.^[6]Подход здесь заключается в замене последнего требования условием, чтобы коэффициенты вектора ${ Displaystyle [0, { mathit {г (х)}}]}$ быть равномерно распределенным по ${ Displaystyle { mathit {GF (p)}}}$, каждый остаток ${ displaystyle 0,1, ..., p-1}$ появляется столько же раз (Свойство U). Этот эвристический подход был успешным во всех опробованных случаях, и ниже приводится доказательство того, что он всегда дает циклическое ядро.

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

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

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

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

Теорема

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

(1) вектор ${ displaystyle { mathit {C}} = [{ mathit {c}} _ {0}, { mathit {c}} _ {1}, ..., { mathit {c}} _ {N -1}]}$ удовлетворяет свойству U объяснено выше,

(2) ${ Displaystyle { mathit {г (х) час (х) = xN-1}}}$, куда ${ Displaystyle { mathit {ч (х)}}}$ является моническим неприводимым многочленом степени ${ displaystyle { mathit {n}}}$, гарантируем наличие p-ary, линейный циклический код ${ displaystyle { mathit { bar {K}}}}$: размер блока ${ Displaystyle { mathit {N}}}$, так что расширенный код ${ displaystyle { mathit {K}} = [0, { mathit { bar {K}}}]}$ - показатель Адамара для матрицы Адамара ${ Displaystyle { mathit {Н (р, р_ {п}) = хК}}}$, с ${ Displaystyle { mathit {х = е ^ {2 пи я / р}}}}$, где ядро ${ Displaystyle { mathit {H}}}$ - циклическая матрица.

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

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

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

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

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

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

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

Следствие

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

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

${ Displaystyle { mathit {г ^ {(1)}}}}$ = ${ displaystyle (22201221202001110211210200)}$;

${ Displaystyle { mathit {г ^ {(2)}}}}$ = ${ displaystyle (20212210222001012112011100)}$.

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

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

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

2. Создание кода с помощью двоичного отображения

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

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

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

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

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

Так, например, для ${ displaystyle { mathit {q}}}$ = ${ displaystyle ACGTCC}$, тогда, ${ Displaystyle { mathit {b (q)}}}$ = ${ displaystyle 001011011010}$.

${ Displaystyle { mathit {е (д)}}}$ тогда будет = ${ displaystyle 011011}$ и ${ Displaystyle { mathit {о (д)}}}$ = ${ displaystyle 001100}$.

Определим даже компонент в качестве ${ Displaystyle { mathcal {E}} ({ mathcal {C}}) = {е (x): x in { mathcal {C}} }}$, и нечетный компонент в качестве ${ displaystyle { mathcal {O}} ({ mathcal {C}}) = {o (x): x in { mathcal {C}} }}$.

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

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

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

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

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

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

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

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

Также, ${ displaystyle { 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})}$.

Обратите внимание, что ${ displaystyle b}$ и ${ displaystyle d}$ оба имеют вес ${ displaystyle { mathit {w}}}$. Отсюда следует, что ${ displaystyle b ^ {RC}}$ и ${ displaystyle d ^ {RC}}$ иметь вес ${ Displaystyle { mathit {н-ш}}}$.

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

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

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

По аналогии, ${ Displaystyle { mathit {d_ {H} ^ {RC}}} ({ mathcal {(}} O)) geq { mathit {d_ {min}}}}$.

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

${ Displaystyle { mathcal {C}} = bigcup _ {{ mathit {w}} = d_ {min}} ^ { mathit {w_ {max}}} { mathcal {C}} _ ​​{w} }$

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

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

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

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

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

Смотрите также

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

Рекомендации

1. ^ Адлеман, Л. (1994). «Молекулярное вычисление решений комбинаторной задачи» (PDF). Наука. 266 (5187): 1021–4. CiteSeerX  10.1.1.54.2565. Дои:10.1126 / science.7973651. PMID  7973651. Архивировано из оригинал (PDF) на 2005-02-06. Получено 2010-05-04.
2. ^ ^{а б} Mansuripur, M .; Хульбе, П.К .; Kuebler, S.M .; Perry, J.W .; Giridhar, M.S .; Пейгамбарян, Н. (2003). «Хранение и поиск информации с использованием макромолекул в качестве носителей». Серия технических сборников оптического общества Америки.
3. ^ Миленкович, Ольгица; Кашьяп, Навин (14–18 марта 2005 г.). О разработке кодов для ДНК-вычислений. Международный семинар по кодированию и криптографии. Берген, Норвегия. Дои:10.1007/11779360_9.
4. ^ ^{а б c d е} Кук, К. (1999). «Полиномиальное построение комплексных матриц Адамара с циклическим ядром». Письма по прикладной математике. 12: 87–93. Дои:10.1016 / S0893-9659 (98) 00131-1.
5. ^ Адамек, Иржи (1991). Основы кодирования: теория и приложения кодов с исправлением ошибок, с введением в криптографию и теорию информации. Чичестер: Вайли. Дои:10.1002/9781118033265. ISBN  978-0-471-62187-4.
6. ^ Цирлер, Н. (1959). «Линейные повторяющиеся последовательности». J. Soc. Indust. Appl. Математика. 7: 31–48. Дои:10.1137/0107003.
7. ^ «Пакет вторичной структуры Венской РНК».

внешняя ссылка

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