*119249*

Биологические науки/

11.биоинженерия и биоинформатика

 

К.т.н. Ростовцев В.С., аспирант Новокшонов Е.В.

Вятский государственный университет, Россия

 

Принципы кодирования и обработки импликативных правил на базе ДНК-цепочек

 

Одним из основных направлений развития современных ЭВМ является переход от архитектуры, ориентированной на обработку данных, к архитектуре, ориентированной на обработку знаний. Обработка знаний - это одна из сфер применения искусственного интеллекта, предполагающая использование компьютером знаний, которыми владеет человек, для решения проблем и принятия решений. Важную роль в обработке знаний играет логический вывод (ЛВ) .

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

Одно из направлений исследований в области ДНК-вычислений разрабатывает способы адаптации и интерпретации классических вычислительных задач, процедур и методов в терминах ДНК-вычислений [2, 3].

Переборный характер задачи во многом обуславливает проблемы эффективного выполнения ЛВ на ЭВМ [4] . Классические методы ЛВ, такие как метод резолюций, основываются на последовательных принципах, основным недостатком которых является низкая производительность. В связи с этим в последнее время постоянно предлагаются новые разработки параллельных методов и машин логического вывода (МЛВ), позволяющих реализовать высокоскоростную обработку знаний. Примерами таких разработок могут служить [5, 6] .

Массовый перебор становится осуществим благодаря следующим двум свойствам молекул ДНК [7]:

• массированный параллелизм цепочек ДНК;

• комплементарность Уотсона-Крика.

Рассмотрим пример простейшего логического вывода в терминах ДНК-операций [2]. Рассмотренный в работе метод вывода является реализацией элементарного правила вывода modus ponendo ponens (MP) , которое утверждает, что из формул X и X → Y выводима формула Y (из истинности X и X → Y следует истинность Y) .

 

1. Применение Modus pones

 

Несмотря на простоту правила MP, многие известные методы вывода опираются на этот закон логики. В частности, правило вывода Девиса и Патнема, позволяющее из дизъюнктов X и X ∨ Y получить дизъюнкт Y, является прямым применением данного закона. Принцип резолюции Дж. Робинсона представляет собой расширение правила MP на случай произвольных дизъюнктов с любым числом литералов. В основе метода деления дизъюнктов лежит правило предположения, в соответствии с которым для того, чтобы вывести из секвенции 1 → X ∨ Y секвенцию 1 → Y , необходимо доказать, что X → 0 (1 → X). Правило предположения также использует закон MP, но в его обратном прочтении [5] .

Как показано в [3] основным этапом решения любой задачи с помощью моделей ДНК-цепочек является выбор (или разработка алгоритма), основанного на свойcтвах ДНК. Для того что бы понять как может быть построен ДНК-алгоритм ЛВ по правилу MP рассмотрим пример с простой базой знаний (БЗ).

Пусть известны два факта B и D, а база знаний содержит семь импликативных правил:  1) A → F;  2) C → ~E; 3) ~E → B; 4) D → C; 5) A → D; 6) B → C; 7) C → A. Для примера, используем целевую формулу F. На указанных исходных данных возможны два варианта процесса ЛВ, различающихся признаками успешного завершения вывода.

Первый вариант предполагает наличие известной целевой формулы вывода, а задача ЛВ заключается в решении вопроса: является ли указанная целевая формула выводимой из известных фактов и БЗ? Признаком удачного завершения вывода в данном случае будет появление на некотором шаге вывода целевой формулы. Стоит отметить, что данная формулировка задачи ЛВ является основой структуры программ декларативного логического языка программирования ПРОЛОГ [8]. Семантически данный вариант ЛВ является процедурой подтверждения гипотезы.

Для второго варианта ЛВ не указывается целевая формула, и, как следствие, задача ЛВ заключается в построение некоторого набора формул логически следующих из известных фактов и БЗ. В предельном варианте выводятся все возможные следствия. При такой постановке задачи условием завершения ЛВ может служить или выполнение заданного числа шагов ЛВ или стабильность множества известных фактов. Под стабильностью множества известных фактов, в данном случае, подразумевается отсутствие приращения мощности множества в течение нескольких шагов ЛВ.

Таблица 1 иллюстрирует оба варианта ЛВ на описанной выше БЗ с использованием стратегии "поиск в ширину". Отметим ключевые моменты схемы ЛВ приведенной в таблице 1.

Процесс ЛВ представляет собой итерационный алгоритм, каждая итерация которого состоит из двух этапов:

• выбора из БЗ правила, на основании известных фактов;

• формирования (выделения из сработавших правил) новых знаний (доказанных фактов).

Вывод завершился после заданного числа шагов (7) равного количеству правил в БЗ. За эти семь шагов сработали все правила и выведены все возможные факты.

Использовалась стратегия поиска "сначала в ширину", то есть вновь выводимые факты не использовались для активизации правил, до тех пор пока была возможность активировать ранее известными фактами хотя бы одно ещё не использованное правило.

 

Таблица 1 – Шаги логического вывода

№ шага

Факт

Правило

Результат

Множество известных фактов в конце шага

1

B

№6 B → C

C

B,C,D

2

C

№2 C → ~E

~E

B,C,D,~E

3

C

№7 C → A

A

A,B,C,D,~E

4

E

№3 ~E → B

B

A,B,C,D,~E

5

A

№1 A → F

F

A,B,C,D, ~E, F

6

A

№5 A → ~D

~D

A,B,C,D,~D,~E, F

7

D

№4 ~D → C

C

A,B,C,D,~D,~E, F

 

Если рассматривать только формулировку задачи ЛВ с указанной целевой формулой, то ЛВ завершился бы на пятом шаге, но при этом выводимый факт D остался бы недоказанным.

Выведенный на 6 шаге факт ~D противоречит ранее известному факту D, таким образом, система “БЗ + факты B и D” является противоречивой. Правила №1 и №5 зависят от факта A, а порядок их выполнения не регламентирован.  Таким образом, возможно использование другой последовательности правил ЛВ, которая привела бы к противоречию до вывода факта F.

Процесс вывода строился по классической последовательной схеме, при которой на каждом шаге ЛВ использовалось только одно правило. При этом известные факты, например, на втором шаге позволяли активировать сразу два правила (№2 и №7) , в результате использования, которых можно было получить два новых доказанных факта, то есть развертывание ЛВ "в пространстве" может значительно ускорить процесс вывода и снять необходимость разрешения конфликтного множества.

Четвертый шаг вывода не принес никаких новых знаний в смысле истинности фактов, так как факт B был известен изначально.

Из указанных особенностей примера следует:

• для организации процесса вывода необходима процедура сопоставления известных фактов и посылок правил БЗ;

• при классической последовательной схеме работы МЛВ стабильность множества известных фактов не гарантирует, что выведены все возможные заключения, и, следовательно, данный признак не может служить однозначным условием окончания ЛВ;

• для определения факта достижения цели вывода необходимо иметь процедуру обнаружения заданного факта среди известных;

• независимо от постановки задачи ЛВ, необходимо иметь процедуру проверки непротиворечивости системы “БЗ + факты”;

• развертывание выполнения ЛВ "в пространстве" по аналогии с развертыванием алгоритмов в аппаратуре, а не во времени является предпочтительным.

 

2. Кодирование фактов и правил

 

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

Из определения операции ренатурации вытекают следующие требования к кодированию цепочками ДНК отдельных фактов в РП и фактов в составе правил БЗ:

• кодирование всего правила в целом должно обладать асимметрией, в смысле однозначной идентификации направления правила;

• коды фактов должны быть уникальными в пределах множества всех возможных литералов, используемых в БЗ;

• для поиска сработавших правил, факты рабочей памяти должны быть закодированы кодами комплементарными по отношению к кодам заключений правил – поисковыми кодами фактов (ПКФ);

• кодирование фактов должно гарантировать, отсутствие подцепочек комплементарных ПКФ на стыках посылки и заключения правила;

• коды фактов в заключении должны отличаться от кодов фактов в посылке правила.

Описанные выше требования диктуют необходимость кодирования множества фактов по принципу различия [9]. Каждому факту необходимо сопоставить два кода: основной код факта (ОКФ) и ПКФ. ОКФ будет использоваться только в посылках правил. ПКФ – цепочка комплементарная основному коду факта.  Для упрощения процедуры формирования новых фактов на основании сработавших правил можно кодировать заключения правил поисковыми кодами. Такой подход позволяет заменить секвенирование новых фактов с последующим формированием из поискового представления, операцией укорочения. ПКФ будет использоваться в заключениях правил, будет представлять известный факт в РП и использоваться для поиска известного факта в посылках правил.

 

2.1 Разделитель посылки и заключения

 

Относительно большой алфавит цепочек ДНК ({A, T, G,C}) позволяет выделить специальные символы для разделения посылок и заключений, что упрощает кодирование непосредственно фактов. Выделение разделительных символов обеспечивает асимметрию кода привила и гарантирует некомплементарность ПКФ и участка правила на границе "посылка-заключение". С точки зрения математической модели ДНК-вычислений [2] комплементарные пары A-T и G-C равноправны. Следовательно, любая из них может быть выбрана для организации разделителей. Например, используем в качестве разделителей символы A и T. A будет ограничителем конца посылки, а T будет использоваться для обозначения начала заключения. При этом символы ограничители будут входить в состав кодов фактов. Таким образом, код факта-посылки в правиле всегда будет заканчиваться символом A, код факта-заключения в правиле будет начинаться с символа T. В таком случае граница "посылка-заключение" идентифицируется в коде правила последовательностью PATO.

C другой стороны, длина границы "посылка-заключение" не зависит от длин ОКФ и ПКФ. Она имеет постоянное значение – два нуклеотида, независимо от общей длины кода правила. Очевидно, что длина информационной части ОКФ и ПКФ, практически, в любой задаче будет значительно превосходить длину границы. Поэтому, выбор конкретной пары символов в качестве разделителей оказывает значительное влияние на количественное соотношение различных нуклеотидов в кодах фактов и правил и их вторичных структур.

Известно, что количественное соотношение различных нуклеотидов в цепочках влияет на стабильность их вторичных структур, а так же оказывает влияние на некоторые операции, выполняемые над цепочками в пробирках [9]. Обычно, для оценки отношения количества пар нуклеотидов с различными типами водородных связей (A-T и G-C) используется характеристика цепочки, известная как GC-доля (GC-content). GC-доля выражается в процентах как отношение количества нуклеотидов G и С или пар, образованных нуклеотидами G и С, к общей длине цепочки. Так же известно, что увеличение GC-доли означает увеличение стабильности вторичных структур ДНК [9].

Не трудно заметить, что при выборе в качестве разделителей символов G и С,  GC-доля по определению не может превышать 50%, а с увеличением размерности задачи будет линейно убывать. Таким образом, точность результатов отдельных ДНК-операций и всего ЛВ в целом будут уменьшаться с ростом размерности задачи.  Выбор же в качестве разделителей нуклеотидов A и T, напротив, является гарантией того, что значение GC-доли в любой задаче будет не менее 50%. С ростом размерности задачи  значение GC-доли будет увеличиваться, а следовательно, будет увеличиваться и точность результатов ДНК-операций.

 

2.2 Коды фактов и правил

 

Код любого факта как в составе кода правила, так и отдельно в виде отдельного ПКФ должен содержать информационную часть, которая бы обеспечивала уникальность кода и префикс(постфикс) – разделительный символ.

Информационная часть кода правила должна обеспечивать уникальность кода факта среди всего множества возможных литералов, то есть код факта должен позволять однозначно идентифицировать как положительное, так и отрицательное вхождение любого атома в формулу. Так как символы A и T используются для разделителей, то требуемая длина информационной части кода факта может быть рассчитана следующим образом:

Z =] log2(2n)[= 1+]log2(n)[,                        (1)

где Z – длина информационной части кода факта;

]x[ – операция округления числа x в сторону большего целого;

n – количество различных атомарных формул в БЗ.

Для приведенного примера длина информационной части кодов по формуле (1) составляет: Z = 1+]log2(6)[= 4. Информационную часть кодов посылок (ОКФ) можно выбирать произвольно при условии соблюдения описанных ранее требований. Информационная часть ПКФ должна быть комплементарна информационной части кодов посылок. Если ПКФ имеет вид: PTZ4Z3Z2Z1O, где Zi ∈ {G, C}. Тогда код правила с фактом-посылкой, которому соответствует указанный ПКФ, можно описать структурой: PX1X2X3X4ATX5X6X7X8O, где Xi – символ комплементарный Zi.

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

 Таблица 2 – Основные и поисковые коды фактов

№

Литерал

ОКФ

ПКФ

1

A

PGGGGAO

PTCCCCO

2

B

PGGGCAO

PTGCCCO

3

C

PGGCGAO

PTCGCCO

4

D

PGGCCAO

PTGGCCO

5

E

PGCGGAO

PTCCGCO

6

F

PGCGCAO

PTGCGCO

7

~F

PCGCGAO

PTCGCGO

8

~E

PCGCCAO

PTGGCGO

9

~D

PCCGGAO

PTCCGGO

10

~C

PCCGCAO

PTGCGGO

11

~B

PCCCGAO

PTCGGGO

12

~A

PCCCCAO

PTGGGGO

 

2.3 Введение фиктивных атомов

 

В БЗ представленной кодами вида PX1X2X3X4ATX5X6X7X8O возможно возникновение исключительной ситуации, связанной с представлением отношения эквивалентности между фактами. Отношение A ↔ B в виде импликативных правил, пригодных для использования в MP, можно записать следующим образом: A → B и → A. Коды этой пары правил, составленные с учетом всех вышеперечисленных требований, будут иметь вид: PX1X2X3X4ATX5X6X7X8O и PZ8Z7Z6Z5ATZ4Z3Z2Z1O.

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

Для того что бы избежать нежелательного взаимодействия кодов правил A → B и B → A можно либо изменить принципы кодирования фактов, либо произвести модификацию исходной БЗ – заменить одно из правил его неявным представлением.

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

Конфликт кодов правил A → B и B → A может быть разрешен введением в БЗ атома K. Атом K не имеет семантического значения, поэтому называется фиктивным. Используя свойство транзитивности импликации можно представить исходные правила A → B и B → A тремя правилами, задающими взаимное следствие исходных фактов через транзитный фиктивный атом K:A→B, B →K, K → A. Такая модификация сохраняет взаимосвязь между фактами A и B, но изменяет код одного из исходных правил и добавляет код одного нового правила. Коды трех правил, полученные в результате модификации, некомплементарны между собой и не могут вступить во взаимодействие при ренатурации БЗ с фактами РП.

Атом K не имеет значения, поэтому может быть проигнорирован при интерпретации БЗ и результатов ЛВ. Но его обработка (кодирование и использование в операциях ЛВ) должна выполняться точно так же, как и обработка всех остальных фактов.

 

2.4 Автоматическое построение кодов

 

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

Для определения таких правил рассмотрим кодирование, приведенное в таблице 2. В процессе анализа выявляются определенные закономерности, связывающие коды положительных и отрицательных литералов, а так же коды фактов и ПКФ. Перечислим их.

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

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

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

Опираясь на перечисленные закономерности, требования к кодам, способ введения разделителей и расчета длины информационной части кодов фактов достаточно просто сформулировать эффективный алгоритм кодирования фактов и правил для задачи ЛВ по правилу MP.

 

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

 

Для того, чтобы начать обработку знаний, необходимо на основе схемы кодирования создать объекты модели ДНК-вычислений – пробирки, описывающие базу знаний и множество известных в некоторый момент времени фактов – аналог РП МЛВ. Воспользуемся для описания пробирок

и операций над ними специальным языком DNACL [3].

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

В виду того, что в любой реакции теоретически могут участвовать не все цепочки, кратности правил и фактов в пробирках должны обеспечивать высокую вероятность требуемых реакций. Для этого кратности должны быть значительно больше числа правил в БЗ. Для сокращения записи примеров принята кратность всех фактов и всех правил равная 14, однако, при организации реальных вычислений следует указывать кратности, в несколько раз превосходящие количество правил M.

Таким образом, пробирка, выполняющая роль РП, перед началом процесса ЛВ будет иметь вид: _RP:=(['PCATTTO'-14]['PCAATTO'-14]), пробирка описывающая базу знаний: _BZ:=(['PAAAAGCATATO'-14][ 'PAATAGCAATAO'-14]['PTATTGCATTTO'-14][ 'PTTAAGCTATTO'-14][ 'PAA AAGCTTAAO'-14]['PAAATGCTATTO'-14]['PAATAGCTTTTO'-14]) .

 

 

 

 

3.1 Поиск активных правил и их обработка

 

При кодировании был заложен принцип поиска правил, для выполнения которых существуют известные факты в РП, на основе ренатурации одинарных цепочек в двойные. Для того чтобы ОКП и ПКФ вступили во взаимодействие, их следует поместить в одну пробирку с помощью функции UNION, выполнить ренатурацию, а затем выделить из пробирки получившиеся двойные цепочки, которые представляют собой сработавшие правила. Использованный способ кодирования позволяет выполнить выделение двойных цепочек операцией RS, указав в качестве искомой подстроки двойную цепочку единичной длины: C_DV:=( 'PAO', 'OTP') . Запишем данные действия на языке DNACL:

_tmp:=UNION(_BZ, _RP); // сливаем БЗ и РП_

tmp:=RENATN(_N3); // отмечаем сработавшие правила

_tmp1 :=RS(tmp, с_DV); // выделяем сработавшие правила

_BZ:=RSNOT(tmp, с_DV); // то что не сработало, будет новой БЗ.

Выполнение этих действий приведет к тому, что в пробирке _BZ окажется БЗ,из которой исключены все сработавшие правила, а в переменной_tmp1 будут сохранены все сработавшие правила (двойные цепочки) и только они.

Далее необходимо выделить из сработавших правил новые знания  доказанные факты. Сработавшее правило является двойной цепочкой специального вида: один её конец, соответствующий посылке, ровный, а второй, соответствующий заключению, липкий. Структура такой цепочки выглядит следующим образом:

'PX1X2X3X4ATZ5Z6Z7Z8O'

'OZ1Z2Z3Z4T_ _ _ _P'.

Нетрудно заметить, что последовательность комплементарных пар нуклеотидов в этой цепочке точно соответствует посылке, а одинарная цепочка на липком конце соответствует заключению в структуре правила. То есть, выделить новый факт из сработавшего правила можно, выполнив отсечение пар нуклеотидов с ровного конца цепочки, используя функцию RED3, а массовое отсечение можно реализовать функцией RED3N. После выделения новых фактов, естественно, следует обновить состояние РП, то есть пробирку _RP, добавив в ней вновь полученные знания. На языке DNACL процесс выделения заключений и обновление _RP записывается следующим образом:

_tmp1:=RED3N(_tmp1 , 5); // отсекаем 5 пар нуклеотидов с ровного конца

_RP:=UNION(_RP, _tmp1); // обновляем РП.

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

 

 

3.2 Обнаружение факта достижения цели вывода

 

Если процесс вывода реализуется по первому варианту, то есть указана цель вывода, то , до начала вывода кроме _BZ и _RP, необходимо также задать цепочку, ей кодирующую. Пробирка _RP содержит известные факты в форме поисковых кодов, поэтому для того чтобы использовать в поиске ренатурацию, необходимо указать цель в виде обычного кода литерала, а не его ПКФ.

Цель вывода должна описываться отдельной пробиркой, а определение факта достижения цели можно выполнить по аналогии с поиском активных правил.

C другой стороны, для поиска отдельного факта, можно использовать и операцию разделения по суффиксу (RS) , в этом случае цель должна быть описана в том в виде, в котором она должна появиться в РП, то есть в виде ПКФ. Использование операции RS для поиска позволяет описать цель ЛВ, используя объект модели ДНК-вычислений значительно более простой нежели пробирка – одинарную цепочку.  Таким образом, цель ЛВ:  _GOAL:= 'PTCGTGO'.

В результате выполнения функции RS в случае если целевой факт ещј не выведен, будет сформирована пустая пробирка, а если искомый факт присутствует в _RP, то результирующая пробирка будет с некоторой кратностью содержать единственную цепочку ПКФ целевой формулы. Проверку наличия цепочек в пробирке выполняет функция NOTNULL. Таким образом, на языке DNACL проверка факта вывода целевой формулы запишется следующим образом:

_tmp1:=RS(_RP, _GOAL) ; // ищем цель среди доказанных фактов

IF NOTNULL(_tmp1) THEN // если пробирка не пуста, то цель доказана

// конец

ELSE

// ещё шаг ЛВ

ENDIF.

3.3 Проверка стабилизации множества фактов

 

В процессе ЛВ может возникнуть ситуация при которой цель вывода ещё не достигнута, но выполнение новых шагов вывода не приводит к формированию новых знаний, то есть поставленная цель не выводима из известных фактов и БЗ. Чтобы избежать бесконечного ЛВ после каждого шага следует выполнять проверку стабильности (неизменности) множества известных фактов. Подобная проверка может использоваться и для завершения ЛВ, когда не задана целевая формула.

Описанные выше методы выделения активных правил и их последующей обработки гарантируют применение всех возможных правил одновременно, поэтому для проверки стабилизации множества известных фактов достаточно выяснить изменилось ли содержимое пробирки _RP в результате последнего шага вывода. Выявить появление новых фактов в пробирке _RP можно сравнив её состав до и после обновления с помощью функции CMPSN:

_tmp1:=RED3N(_tmp1, 5) ; // отсекаем 5 пар нуклеотидов с ровного конца

_tmp2:=_RP; // сохраняем состояние РП до обновления

_RP:=UNION(_RP, _tmp1) ; // обновляем РП

IF CMPSN(_tmp2, _RP) THEN // сравниваем то что было и то что стало

// если ничего не изменилось, то нет смысла что то ещј делать, конец

ELSE

// если что-то добавилось, то попробуем ещј что нибудь вывести  выполним ещё шаг ЛВ

ENDIF.

 

3.4 Проверка непротиворечивости известных фактов

 

Непротиворечивость является весьма важным свойством знаний, в основном, в силу того, что в классической логике доказуемость противоречия означает, что становится "доказуемым" все что угодно и понятие доказательства теряет смысл. При этом непротиворечивость базы знаний, обычно обеспечивается при создании и обновлении БЗ и не контролируется непосредственно в процессе вывода.

С одной стороны, процесс формирования представления знаний в терминах ДНК-вычислений предполагает наличие уже сформированной БЗ и, если известно, что при её составлении непротиворечивость контролировалась, то можно вообще отказаться от процедуры проверки в процессе ЛВ на цепочках ДНК.

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

Для выполнения проверки можно использовать принцип комплементарного поиска, который использовался в процедурах выделения активных правил и определения факта достижения цели вывода. В частности, до начала процесса вывода можно сформировать пробирку, содержащую маркеры противоречий – одинарные цепочки специального вида, которые способны ренатурировать одновременно с обоими кодами контрарных литералов одного атома, хранящимися в РП. Обозначим пробирку с маркерами противоречий константой c _PROTIV.

В _RP известные факты представлены поисковыми кодами. В соответствии с заложенными при кодировании фактов принципами, ПКФ контрарных литералов имеют вид: PЕX1X2X3X4O и PTZ1Z2Z3Z4O, а коды соответствующих фактов: PZ4Z3Z2Z1AO и PX4X3X2X1AO, где Xi – символ комплементарный Zi. Таким образом, цепочка, полученная простой конкатенацией кодов контрарных литералов может использоваться в качестве маркера противоречия для заданного атома: PZ4Z3Z2Z1AX4X3X2X1AO.

Однако, способность маркера ренатурировать с каждым из ПКФ контрарных литералов диктует необходимость проверки факта одновременной ренатурации с обоими ПКФ. Такую проверку можно выполнить с помощью поиска уникальной последовательности нуклеотидов, образование которой возможно только в случае ренатурации маркера ошибки с обоими ПКФ контрарных литералов. Рассмотрим три варианта ренатурации маркера ошибки с ПКФ:

1) PZ4Z3Z2Z1AX4X3X2X1AO

    OX4X3X2X1T_ _ _ _ P;

2) PZ4Z3Z2Z1AX4X3X2X1AO

  O_ _ _ _Z4Z3Z2Z1TP;

3) PZ4Z3Z2Z1AX4X3X2X1AO

  OX4X3X2X1TZ4Z3Z2Z1TP.

Варианты 1 и 2 – ренатурация маркера с одним ПКФ. Цепочки такого вида образуются если в РП существует только один из литералов контрарной пары. Третий вариант – результат ренатурации маркера с двумя ПКФ, цепочки такого вида образуются если в РП одновременно существуют оба контрарных литерала – доказаны противоречащие друг другу факты.

Третья цепочка может быть выделена по уникальной подпоследовательности TZ4. Подстрока уникальна в силу следующих причин. Во-первых, символ T не используется коде маркера ошибки, то есть, поиск производится по ПКФ. А во-вторых, наличие одного из символов {G,C} с 5'(P) стороны от символа T возможно, только если два ПКФ образуют одинарную цепочку, комплементарную маркеру. Таким образом, наличие в пробирке, полученной в результате ренатурации маркеров ошибок с фактами РП, цепочек содержащих подцепочки PGTO или PCTO указывает на тот факт, что в РП одновременно существуют оба контрарных литерала, то есть множество доказанных фактов содержит противоречие. Вся процедура проверки на языке DNACL записывается следующим образом:

c_GT:=PGTO;

c_CT:=PCTO;

_tmp:=UNION(_RP, c_PROTIV);

_tmp:=RENATN(_tmp);

_tmp1 :=RS(_tmp, с_GT) ;

_tmp:=RS(_tmp, с_CT) ;

//пробирки не пусты только если есть противоречия

IF NOTNULL(_tmp) OR NOTNULL(_tmp1)

// конец, вывод завершен неудачно, так как доказаны противоречивые факты

ELSE

// ЛВ можно продолжать

ENDIF.

 

Заключение

 

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

• массовый параллелизм обработки знаний;

• наличие процедуры контроля непротиворечивости выводимых фактов;

• возможность организации прямого и обратного логического вывода по одним и тем же принципам и с использованием одного варианта кодирования фактов;

• использование достаточно коротких цепочек ДНК;

• наличие алгоритма кодирования фактов и правил.

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

По-видимому, такой подход с использованием массового параллелизма операций можно считать дальнейшим развитием стратегии "в ширину". С другой стороны, в предложенном методе количество шагов ЛВ, необходимое для доказательства цели, равно минимальному количеству шагов ЛВ,  использующего стратегию "в глубину". Таким образом, разработанный метод объединяет достоинства обеих стратегий поиска.

Разработанная процедура контроля непротиворечивости множества известных (доказанных) фактов позволяет в любой момент времени (на любом шаге вывода) гарантировать отсутствие неоднозначности получаемых знаний. Для полной проверки непротиворечивости системы (БЗ + исходные факты) не требуется отдельных процедур. Такая проверка может быть выполнена описанной программой, если ЛВ запускается без указания цели. Кроме того, наличие такой процедуры позволяет смягчить требования, предъявляемые к предобработке, исходной БЗ – база знаний на входе метода, в общем случае, может быть противоречивой и это не приведет в выводу недостоверных фактов. Точнее, противоречивость БЗ будет обнаружена в процессе применения правил и вывод закончится неудачно. Стоит отметить, что при проверке непротиворечивости используется массовый параллелизм цепочек ДНК и, следовательно, такая проверка требует значительно меньшего количества операций по сравнению с классическими методами, применяемыми при подготовке (предобработке) БЗ.

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

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

Литература

1. В. И. Минкин. Молекулярные компьютеры [Текст] / В.И.Минкин // Химия и жизнь-XXI век. – 2004. – №2.

2. В. С. Ростовцев. Моделирование ДНК-систем и их прикладное применение: учебное пособие [Текст] / В. С. Ростовцев. – Киров: Издательство ВятГУ, 2010.

3. В. С. Ростовцев. Инструментальная система моделирования базовых ДНК-операций: учебное пособие [Текст] / В. С. Ростовцев, Е. В. Новокшонов. –  Киров: Издательство ВятГУ, 2010.

4. В. А. Вишняков. Аппаратно-программные средства процессоров логического вывода [Текст] / В. А. Вишняков, Д. Ю. Буланже, О. В. Герман. –  М.: Радио и связь, 1991.

5. Д. А. Страбыкин. Организация машин параллельного логического вывода: Учебное пособие для вузов [Текст] / Д. А. Страбыкин. – Киров: Издательство ВятГУ, 1999.

6. М. Н. Томчук. Метод и система логического вывода модифицируемых заключений [Текст]: Диссертация на соискание ученой степени кандидата наук/ Пензенский государственный университет. – Пенза, 2009.

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

8. Дж. Mалпас. Реляционный язык Пролог и его применение: Пер. с англ. /Под редакцией В.Н. Соболева. [Текст] / Дж. Mалпас. – М.: Наука, 1990.

9. J. Sager. Designing Nucleotide Sequences for Computation: A Survey of Constraints / J. Sager, D. Stefanovic // DNA Computing - 11th International Workshop on DNA Computing, DNA11 London, ON, Canada, June 6-9, 2005, volume 3892 of  Lecture Notes in Computer Science – NY.: Springer, 2005.