Устройство моделирования процесса суммирования положительных n-разрядных чисел, закодированных днк-цепочками

Полезная модель относится к вычислительной технике, а именно к устройствам моделирования на программируемых логических интегральных схемах биомолекулярных компьютеров, построенных на основе ДНК-цепочек, которые помещены в пробирки. Заявляемая модель состоит из блока кодирования/декодирования данных; двух регистров РгТ₁ и РгТ₂, моделирующих содержимое соответственно двух пробирок; блока формирования промежуточной суммы, моделирующего процесс выполнения биомолекулярных операций в первой пробирке; блока предварительной обработки разрядов данных, который моделирует процесс выполнения биомолекулярных операций во второй и третьей пробирках; блока параллельной выборки значений, моделирующего содержимое третьей пробирки. РгТ₁ соединен с входами/выходами блока кодирования/декодирования данных и с входами/выходами блока формирования промежуточной суммы. РгТ ₂ соединен с выходами блока кодирования/декодирования данных и блока формирования промежуточной суммы и с входом блока предварительной обработки разрядов данных. Блок предварительной обработки разрядов данных соединен с выходом РгТ₂, входом блока формирования промежуточной суммы и входом/выходом блока параллельной выборки значений.

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

Используемые понятия:

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

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

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

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

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

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

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

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

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

На фиг.1 представлена структурная схема устройства моделирования процесса суммирования n-разрядных чисел, закодированных ДНК-цепочками. Оно состоит из:

1. двунаправленной линии входных данных;

2. блока кодирования/декодирования данных (КД/ДД), который моделирует кодирование ДНК;

3. однонаправленной линии данных от КД/ДД к регистру РгТ₁;

4. однонаправленной линии данных от регистра РгТ₁ к КД/ДД;

5. регистра РгТ₁ (моделирует содержимое первой пробирки Ti);

6. однонаправленной линии данных от регистра РгТ₁ к блоку формирования промежуточной суммы;

7. однонаправленной линии данных от блока формирования промежуточной суммы к регистру РгТ₁;

8. блока формирования промежуточной суммы (БФПС - моделирует процесс выполнения биомолекулярных операций, осуществляемых в первой пробирке);

9. однонаправленной линии данных от КД/ДД к регистру РгТ₂;

10. регистра РгТ₂ (моделирует содержимое второй пробирки T ₂);

11. однонаправленной линии данных от БФПС к регистру РгТ₂;

12. однонаправленной линии данных от регистра РгТ₂ к блоку предварительной обработки разрядов данных;

13. однонаправленной линии данных от блока предварительной обработки разрядов данных к БФПС;

14. блока предварительной обработки разрядов данных (БПРД -моделирует процесс выполнения биомолекулярных операций, осуществляемых во второй пробирке перед помещением ДНК-цепочек из нее в третью пробирку То, и процесс выполнения биомолекулярных операций, осуществляемых в пробирке То);

15. однонаправленной линии данных от БПРД к блоку параллельной выборки значений;

16. однонаправленной линии данных от блока параллельной выборки значений к БПРД;

17. блока параллельной выборки значений (БПВ3-моделирует содержимое третьей пробирки То).

Основным элементом блока БПВЗ 17 является постоянное запоминающее устройство (ПЗУ), в котором хранятся закодированные ответы в выбранной системе счисления. Выборка данных осуществляется строками по их номерам. Номером является значение каждого закодированного разряда из пробирки РгТ ₂ 10.

В состав блока БПРД 14 входят две комбинационные схемы (КС1 и КС2) и блок управления этими схемами. Первый вход КС1 связан с первым выходом регистра 10. Второй вход КС1 связан с первым выходом блока 17. Таким образом, на вход первой КС могут поступать данные либо с блока 17, либо с регистра 10 (выбирается блоком управления). Данная схема моделирует присоединение номера разряда числа к каждому обрабатываемому разряду. Первый выход КС1 связан с первым входом КС2 и первым входом блока 17. Данная схема моделирует операцию разрезания по сайту узнавания. Первый выход КС2 соединен со вторым входом блока 8.

В состав блока 8 входят три комбинационные схемы (КС1, КС2, КС3). Первый вход КС1 соединен со вторым выходом регистра 5. Второй вход КС1 соединен с первым выходом блока 14. Данная схема моделирует операцию смешивания данных, закодированных в первой пробирке, и закодированных данных, выбранных из третьей пробирки, с образованием комплементарных связей. Первый выход КС1 соединен с первым входом КС2. Схема КС2 моделирует процесс отделения двойных ДНК-цепочек от одинарных ДНК-цепочек. Первый выход КС2 соединен с первым входом КС3. Схема КСЗ моделирует процесс выборки ДНК-цепочек, содержащих заданный маркер-разделитель переноса. Первый выход КСЗ соединен со вторым входом регистра 10.

Первый вход первого регистра РгТ₁ 5 связан со вторым выходом блока кодирования/декодирования данных 2 посредством линии 3. Первый выход первого регистра РгТ₁ 5 соединен со вторым входом блока кодирования/декодирования данных 2 при помощи линии 4. Второй выход первого регистра РгТ₁ 5 соединен с первым входом БФПС 8 посредством линии 6. Второй вход первого регистра РгТ₁ 5 соединен с первым выходом БФПС 8 при помощи линии 7.

Первый вход второго регистра РгТ ₂ 10 связан с третьим выходом блока кодирования/декодирования данных 2 посредством линии 9. Первый выход регистра РгТ₂ 10 соединен с первым входом БПРД 14 с помощью линии связи 12. Второй вход регистра РгТ₂ 10 соединен со вторым выходом БФПС 8 посредством линии связи 11. Второй вход БФПС 8 соединен с первым выходом БПРД 14 при помощи линии 13. Второй выход блока 14 соединен с первым входом блока 17 посредством линии 15. Второй вход блока 14 соединен с первым выходом блока 17 с помощью линии 16.

Слагаемые по линии 1 поступают на первый вход блока кодирования/декодирования данных 2, где выполняется их кодирование однозначно соответствующими ДНК-цепочкам двоичными кодами. Далее закодированное первое слагаемое по линии 3 передается из блока кодирования/декодирования данных 2 в регистр 5. Закодированное второе слагаемое по линии 9 передается из блока кодирования/декодирования данных 2 в регистр 10. Затем первое слагаемое из регистра 5 передается в блок БФПС 8 по линии 6, а второе - из регистра 10 в блок 14 по линии 12. Далее второе слагаемое поступает на вход БПВЗ 17 по линии 15, где осуществляется выборка строк из ПЗУ. Затем выбранные данные поступают из блока 17 по линии 16 в блок 14, где к каждому из них добавляются коды номера разряда числа. Далее по линии 13 из блока 14 данные передаются в блок 8, где выполняются операции моделирования комплементарного соединения, разрезания по сайту узнавания и фильтрации по признаку наличия маркера-разделителя переноса. В случае, когда нет данных, отфильтрованных по признаку наличия переноса, тогда данные, получившиеся после "разрезания по сайту узнавания" передаются в регистр 5 из блока 8 по линии 7. Затем по линии 4 из регистра 5 передаются в блок кодирования/декодирования данных 2, где происходит их декодирование и выдача результата по линии 1. В случае, когда есть данные, отфильтрованные по признаку наличия переноса, тогда выполняется "разрезание по сайту узнавания" признака переноса и передача получившихся данных по линии 11 в регистр 10. Далее данные передаются по линии 12 в блок 14, где к ним присоединяются коды разрядов, а затем передаются по линии 15 в блок 17 для выборки. Процесс моделирования биомолекулярных операций в блоке 8 с последующей выборкой данных из блока 17 выполняется до тех пор, пока возникает признак наличия переноса.

При использовании предлагаемого способа возможно параллельное суммирование нескольких чисел. Для этого дополнительно необходимо добавить блоки РгТ₁, РгТ₂ и БФПС для каждой дополнительной пары слагаемых.

Источники информации

1. Rana Barua, Jonardan Misra Binary Arithmetic for DNA Computers // DNA Computing: 8th International Workshop on DNA Based Computers, DNA8, Sapporo, Japan, June 10-13, 2002, Revised Papers. - Springer-Verlag: London, UK. 2003. - pp.124-132.

1. Устройство моделирования процесса суммирования положительных n-разрядных чисел, закодированных ДНК-цепочками, состоящее из блока кодирования/декодирования данных, двух регистров РгТ ₁ и РгТ₂, моделирующих соответственно ДНК-цепочки, содержащиеся в первой и второй пробирках, блока формирования промежуточной суммы, моделирующего процесс выполнения биомолекулярных операций, осуществляемых в первой пробирке, блока предварительной обработки разрядов данных, моделирующего процесс выполнения биомолекулярных операций, осуществляемых во второй пробирке перед помещением ДНК-цепочек из нее в третью пробирку, и процесс выполнения биомолекулярных операций, осуществляемых в третьей пробирке, и блока параллельной выборки значений, моделирующего содержимое третьей пробирки; второй и третий выходы блока кодирования/декодирования данных соединены соответственно с первыми входами первого и второго регистров, второй вход блока кодирования/декодирования данных соединен с первым выходом первого регистра, первый вход блока формирования промежуточной суммы соединен со вторым выходом первого регистра, первый и второй выходы блока формирования промежуточной суммы соединены со вторыми входами первого и второго регистров соответственно, второй вход блока формирования промежуточной суммы соединен с первым выходом блока предварительной обработки разрядов данных, первый вход блока предварительной обработки разрядов данных соединен с первым выходом второго регистра, второй вход и второй выход блока предварительной обработки разрядов данных соединены соответственно с первым выходом и первым входом блока параллельной выборки значений.