Л.А.Лютикова, к.ф.-м.н.

НИИ ПМА КБНЦ РАН, г. Нальчик

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

Аннотация.

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

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

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

В молекулах ДНК имеется четыре базовых основания: аденин (A), гуанин (G), цитозин (C) и тимин (T), связанных друг с другом в цепочку.

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

A – 0 C – 1 G - 2 T - 3

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

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

К(х)=3-х

Таблица 1.

x	К(х)
0	3
1	2
2	1
3	0

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

Таблица 2. Re(x_1,x₂)

х1/х2	0	1	2	3
0	0	0	0	1
1	0	0	1	0
2	0	1	0	0
3	1	0	0	0

Обратный процесс, то есть разъединение двойной цепочки и получение двух одинарных цепочек, — денатурацией.

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

Задача распознавания образов имеет следующую формулировку:

Соответствие множества объектов характеризующим их признаков может быть представлено следующей таблицей:

Таблица 3.

x1 x2 x3…… .. xn	W
x1(w1) x2(w1) x3(w1) .. xn(w1) x1(w2) x2(w2) x3(w2) .. xn(w2) x1(wm) x2(wm) x3(wm) x n(wm)	w1 w2 . wm

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

- множество характеризуемых объектов.

Вид функции W = f(X) не задан. Требуется восстановить неизвестную зависимость по наблюдениям.

Каждый соответствующий признак x_j(w_j) в общем случае кодируется предикатом k_i-значности [0,1,2,3]

Для нахождения значения функции W= f(X) системе важно обращаться к базе знаний, которая по запросу выдаст w_j,, в случае если w_j принадлежит исследуемой предметной области, или объект (группу объектов), наиболее соответствующих данном запросу/

Для нахождения наиболее соответствующего заданному запросу объекта w_j, предлагается мследующий алгоритм:

Запрос формируется в виде комплементарной цепочки к исходному запросу.

Копируется необходимое количество цепочек запроса.

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

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

Литература:

1. Малинецкий Г.Г., Митин Н.А., Науменко С.А. Нанобиология и синергетика. Проблемы и идеи. ИПМ им. М.В.Келдыша РАН. Москва, 2005

2. Паун Г., Розенберг Г., Саломаа А. ДНК-компьютер. Новая парадигма вычислений. М.: Мир, 2004. 528 с.

3. Лютикова Л.А. Некоторые свойства операций логического дифференцирования и интегрирования дискретных k – значных функций // Materiały VIII Międzynarodowej naukowi-praktycznej konferencji «Dynamika naukowych badań - 2012». Volume 21. Matematyka: Przemyśl. Nauka i studia, 2012. С. 17 – 21.