11.биоинженерия и биоинформатика
К.т.н.
Ростовцев В.С., магистрант Смехова В.М.
Вятский государственный университет, Россия
Принципы разработки модуля базы
знаний и модуля логического вывода на базе ДНК-цепочек
Введение. Биокомпьютинг позволяет решать сложные вычислительные задачи,
используя методы, принятые в биохимии и молекулярной биологии, организуя
вычисления при помощи живых тканей, клеток, вирусов и биомолекул [1,2]. Настоящая работа посвящена некоторым аспектам применения новой
парадигмы вычислений на основе дезоксирибонуклеиновой кислоты (ДНК) для решения
одной из довольно известных проблем: а именно, проблемы реализации основных
модулей любой интеллектуальной системы- базы продукционных знаний и модуля
логического вывода с использованием ДНК-цепочек. В качестве нового способа
решения этой проблемы выбраны молекулы ДНК и алгоритмы, основанные на свойствах
этих молекул. Анисимов Д.В. из Санкт-Петербургского государственного
университета опубликовал статью «Решение проблемы дедукции с использованием свойств
ДНК», в которой детально рассмотрел математическую постановку задачи с
использованием молекул ДНК и алгоритмов, основанных на свойствах этих молекул.
Однако в ней отсутствуют сведения о принципах построения базы знаний и модуля
логического вывода.
Постановка задачи. Проблема реализации основных модулей (базы продукционных знаний и
модуля логического вывода с использованием ДНК-цепочек) любой интеллектуальной
системы состоит в том, чтобы из множества продукционных правил базы знаний
вывести заключение при наличии множества истинных условий (фактов) и возможного
конфликтного множества правил. Компьютерное моделирование
ДНК-алгоритмов позволяет имитировать опыты с ДНК-цепочками без применения
дорогостоящего лабораторного оборудования, предназначенного для биологических
исследований. По результатам компьютерных экспериментов возможна реализация интеллектуальной
системы на биомолекулярном уровне.
ДНК-метод. Предлагается решать данную задачу с помощью цепочек ДНК. Этот метод позволяет
сразу сгенерировать базу знаний, состоящую из продукционных правил,
закодированных ДНК-цепочками. Благодаря массовому параллелизму обработки ДНК-цепочек
логический вывод выполняется мгновенно. На данный момент наилучшим из возможных
способов решения этой задачи является обычный массовый перебор, который становится,
осуществим благодаря следующим двум свойствам молекул ДНК:
1. Массированный параллелизм цепочек ДНК. Эти цепочки
позволяют хранить в них информацию с высокой плотностью и имеют очень простой механизм
размножения.
2. Комплементарность Уотсона – Крика. Это свойство
позволяет комплементарным парам Аденин (А) – Тимин (Т), Гуанин (Г) – Цитозин
(Ц) при образовании двойных цепочек ДНК находить друг друга без стороннего
участия Здесь А, Т, Г, Ц являются основаниями нуклеотидов, из которых состоят
полимерные нити, образующие молекулу ДНК.
Решение
задачи. Для
формирования правил из ДНК-цепочек готовится строительный материал: факты в
виде специальных ДНК-цепочек, которые кодируются одинаковым числом нуклеотидов.
Продукционные правила также кодируются в виде ДНК-цепочек. Операции
повторяются, пока появляются в процессе логического вывода новые выведенные из
правил новые факты. В результирующей пробирке остаётся хотя бы одна цепочка ДНК
или пока не выполнится заданное количество итераций. Для обнаружения
ДНК-цепочки используется специальная операция, которая возвращает
значение истины, если данная пробирка содержит, по крайней мере, одну цепочку ДНК, в противном случае
возвращается значение ложь.
ДНК-алгоритм прямого логического
вывода состоит из следующих этапов:
1.
Генерация ДНК-цепочек
для кодирования фактов и правил.
2.
Определение сработавших ДНК-правил.
3.
Разрешение конфликтных
ситуаций при срабатывании нескольких ДНК-правил.
4.
Срабатывание правила при
наличии истинных фактов в условной части правила и добавление заключения этого правила в рабочую память.
Для этого необходимо выполнить отделение выведенного заключения (нового
истинного факта) и его добавление к
истинным фактам рабочей памяти.
5.
Повторение 2-4 пока
появляются новые выведенные факты (в результирующей пробирке имеется хотя бы
одна цепочка ДНК) или пока не выполнится заданное пользователем количество
итераций.
В начале в растворе получают цепочки ДНК,
кодирующие все правила, затем с полученными цепочками производятся необходимые
ДНК-операции.
Перед созданием ДНК-цепочек правил
необходимо подготовить строительный материал: факты и специальные ДНК-коды «у»
и «з». Они кодируются одинаковым числом нуклеотидов. При генерации ДНК-цепочек
правил каждый код факта в молекуле правила удлиняется специальным кодом «у»,
для отличия факта от положения его в условии и заключении (необходимо для
операции разделить). Факт, находящийся в заключение, удлиняется с двух сторон
специальным ДНК-кодом заключения «з» (необходимо для операции разрезать). На
рис.1 представлена структура ДНК-цепочки правила[1,2].
Рис.1 - Структура ДНК-цепочки продукционного правила
Для определения сработавших правил необходимо отделить молекулы правил, в которых не присутствуют известные факты. Это реализуется с применением операции разделить.
Операция «разделить» (или извлечь) - по данным пробирки N и
слову w над алфавитом {А, Ц, Г, Т} изготовить
две пробирки +(N,w)
и -(N,w)
такие, что +(N,w)
состоит из всех цепочек в N, содержащих w в качестве (последовательной) подстроки, a -(N.w)
состоит из всех цепочек в N, которые не
содержат w в качестве подстроки.
Для данной операции «разделить» используется микроскопический магнитный шарик диаметром порядка одного микрона. К нему притягиваются комплементарные ДНК-коды того или иного не заданного факта удлиненного специальной последовательностью «у», которые выполняют функцию пробы. Затем этот шарик помещается в пробирку с исследуемыми ДНК-цепочками — в результате к нему (за счет образования водородных связей между комплементарными группами) «притянутся» ДНК-цепочки, в которых присутствует комплементарный код факта. Далее шарик с отсортированными молекулами вынимается и помещается в новый раствор, из которого затем удаляется (при повышении температуры ДНК-молекулы отваливаются от шарика). Данная процедура (сортировка) повторяется последовательно для каждого не заданного факта, и в результате в пробирке останутся только те молекулы, в которых содержатся ДНК-коды всех известных фактов, а значит правила, закодированные данными молекулами, являются сработавшими.
Примениться могут
сразу несколько правил, выбирается
одно, наиболее подходящее по заданному критерию. В качестве критерия могут
выступать либо важность фактов, либо количество фактов в правиле.
Если критерием назначается важность факта, то при помощи операции разделить, получают цепочки с заданным фактом. При выборе критерия по количеству фактов, применяется операция гель-электрофорез.
Гель-электрофорез, используется для
разделения молекул ДНК по длине. Если молекулы поместить в гель и приложить
постоянное электрическое поле, то они будут двигаться по направлению к аноду,
причем более короткие молекулы будут двигаться быстрее. Используя данное
явление, можно реализовать сортировку ДНК-молекул по длине. Чем короче цепочка,
тем меньше фактов в ней.
Теперь у
сработавшего правила необходимо отделить заключения. Для этого необходимо
применить две операции разрезать
- все нити в S, имеющие подпоследовательность ab, разрезаются между a и b с помощью рестриктаз, двойные нити должны быть разделены, перед
тем как их разрезать. В первый раз а – специальная последовательность «у», b - специальная последовательность
«з». Второй раз а и b -
специальной последовательность «з».
За разрезание молекул ДНК внутри цепочки отвечают ферменты – эндонуклеазы, которые могут быть весьма избирательными в отношении того, что они разрезают, где они разрезают и как они разрезают. Сайт-специфичные эндонуклеазы – рестриктазы – разрезают молекулу ДНК в определенном месте, которое закодировано последовательностью нуклеотидов – сайтом узнавания. Разрез может быть прямым, или несимметричным и может проходить по сайту узнавания, или же вне сайта.
Чтобы отделить факты, находящиеся в
заключение правил, необходимо применить операцию «разделить по префиксу».
Операцию «разделить по префиксу (суффиксу)» - по данным пробирки N и
слову w, изготовить пробирку B(N,w) (соответственно E(N,w)), состоящую из всех цепочек в N, начало (соответственно конец) которых совпадает со
словом w. В качестве w
используется специальная маркерная последовательность «з».
За укорачивание молекул ДНК отвечают
ферменты – экзонуклеазы, которые
могут укорачивать одноцепочечные и двухцепочечные молекулы, с одного или с
обоих концов.
Операции повторяются, пока появляются
новые выведенные факты (в результирующей пробирке имеется хотя бы одна цепочка
ДНК) или пока не выполнится заданное пользователем количество итераций. Для
обнаружения ДНК-цепочки используется операция «обнаружить», которая возвращает
значение истины, если данная пробирка N содержит, по крайней мере, одну цепочку
ДНК, в противном случае возвратит значение ложь.
После успешных компьютерных экспериментов возможна
реализация модулей интеллектуальной системы на биомолекулярном уровне.
Литература:
1.
Паун, Г. ДНК-компьютер.
Новая парадигма вычислений. [Текст] / Паун Г., Розенберг Г., Саломаа А.; под
ред. М.В. Волкова. – Москва: Мир, 2003 - 528 с.
2.
Борн Д. ДНК-компьютеры
обретают логическое мышление [Электронный ресурс] / Денис Борн // 3D News:
сетевой журн. – 2009. – Режим доступа: http://www.3dnews.ru/news/dnk_komputeri_obretaut_ logicheskoe_mishlen