Материал: ДНК наномеханические роботы и вычислительные устройства (Попов), 2008, c.210

a[i[1],t[1]]a[i[2],t[2]] … a[i[r],t[r]] :

1 ≤ i[1] < i[2] < … < i[r] ≤ n,

1 ≤ s[1] ≤ p[i[1]], 1 ≤ s[2] ≤ p[i[2]], … , 1 ≤ s[r] ≤ p[i[r]],

1 ≤ t[1] ≤ p[i[1]], 1 ≤ t[2] ≤ p[i[2]], … , 1 ≤ t[r] ≤ p[i[r]],

1 ≤ j[1] ≤ q[i[1]], 1 ≤ j[2] ≤ q[i[2]], … , 1 ≤ j[r] ≤ q[i[r]] },

Q[4] { aa[i[1],s[1]]b[i[1],j[1]]a[i[2],s[2]]b[i[2],j[2]] … a[i[r],s[r]]b[i[r],j[r]] =

aa[i[1],t[1]]a[i[2],t[2]] … a[i[r],t[r]] :

1 ≤ i[1] < i[2] < … < i[r] ≤ n,

r < n,

1 ≤ s[1] ≤ p[i[1]], 1 ≤ s[2] ≤ p[i[2]], … , 1 ≤ s[r] ≤ p[i[r]],

1 ≤ t[1] ≤ p[i[1]], 1 ≤ t[2] ≤ p[i[2]], … , 1 ≤ t[r] ≤ p[i[r]],

1 ≤ j[1] ≤ q[i[1]], 1 ≤ j[2] ≤ q[i[2]], … , 1 ≤ j[r] ≤ q[i[r]],

a ((Φ[1] … Φ[n] ) \ (Φ[i[1]] … Φ[i[r]]))+ } .

Множество Q[1] определяет изменения состояний узлов робота, не зависящие от текущих состояний других узлов. Множество Q[2] задает изменения состояний узлов,

которые возможны лишь в том случае, когда некоторые другие узлы находятся в подходящих состояниях. Системы Q[3] и Q[4] определяют изменения состояний узлов,

186

которые должны происходить синхронно. При этом множество Q[3] задает

синхронные изменения состояний узлов робота, не зависящие от текущих состояний других узлов. Соответственно множество Q[4] задает синхронные изменения состояний узлов, которые возможны лишь в том случае, когда некоторые другие узлы находятся в подходящих состояниях. Несложно проверить, что если для некоторого i, 1 ≤ i ≤ n,

слово w Ʃ+ содержит более одного вхождения букв из множества Φ[i], то в полугруппе S(R) слово w равно нулю. Кроме того, произвольное слово w Ʃ+ в

полугруппе S(R) представимо в виде

x[1]x[2] … x[n] 1,

где для любого i имеет место соотношение x[i] ( Φ[i] Ψ[i] )*. Отсюда вытекает, что произвольный элемент w полугруппы S(R) равен нулю или слову вида

x[1]x[2] … x[n],

где

x[1]x[2] … x[n] 1,

x[i] = y[i]z[i],

y[i] { 1 } Φ[i],

z[i] Ψ[i]*.

Такое представление элементов полугруппы S(R) будем называть каноническим. Для произвольной полугруппы S(R) по произвольному представлению элемента его каноническое представление может быть эффективно построено за полиномиальное время. Канонические представления ненулевых элементов полугруппы S(R) находятся

187

во взаимно однозначном соответствии с парами всевозможных состояний робота R и

потенциально применимых программ. Фактор-полугруппы полугруппы S(R),

получаемые добавлением некоторого множества определяющих соотношений Q,

определяют пространство состояний – действий робота R.

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

В рамках только что рассмотренной модели применительно к ДНК наномеханическим устройствам попарное различие узлов A[1], A[2], … , A[n] и систем команд b[i,1], b[i,2], … , b[i,q[i]] обусловлено необходимостью обозначить позиции нуклеотидов в устройстве, к которым применяются действия. Однако поскольку количество типов нуклеотидов ограничено, в любом достаточно большом устройстве нуклеотиды одного и того же типа должны повторяться многократно в различных местах. Поэтому многие команды, различающиеся в модели, будут совпадать на физическом уровне. Следовательно, имеет смысл рассмотреть соответствие между множеством формальных программ F и множеством реальных команд E, выполняемых на физическом уровне. Будем говорить, что элемент x из F находится в отношении ρ с

элементом y из E, если модельная команда x кодирует команду y. Рассмотрим частично упорядоченные множества (P(F), ) и (P(E), ) всех подмножеств множеств Fи E,

соответственно. Это множества всех формальных программ и всех программ физического уровня. Бинарный контекст (см. [148]) (F,E,ρ) индуцирует соответствие Галуа (f,g) между множествами (P(F), ) и (P(E), ), задаваемое отображениями

f : X x X { y : y F, x ρ y },

g : Y y Y { x : x E, x ρ y }.

188

Соответствие Галуа (f,g) индуцирует оператор замыкания

h = g f

на множестве (P(F), ) (см. [149]):

X h(X);

X Y h(X) h(Y);

h(h(X)) = h(X).

Пусть L – множество всех элементов (X,Y) из декартова произведения (P(F), ) и (P(E), ) таких, что h(X) = X и f(X) = Y. На множестве L рассмотрим бинарное отношение , задаваемое соотношением

(X[1],Y[1]) (X[2],Y[2]) X[1] X[2].

Пара (L, ) является полной решеткой и называется решеткой Галуа бинарного контекста (F,E,ρ) (см. [150]). Решетка Галуа задает сжимающее отображение множества

(P(F), ) на (P(E), ).

Применение моделей и алгоритмов классической робототехники дает возможность проводить тестирование отдельных элементов наносистем на макроуровне. В частности, для структурного моделирования нанорешеток и наноустройств могут быть эффективно применены результаты исследований по разработке моделей и алгоритмов для метаморфных (metamorphic) или самореконфигурующихся (self-reconfigurable) роботов (см. [151] – [166]). Для исследования алгоритмов управления движением наномеханических роботов представляют существенный интерес также алгоритмы неголономного управления

189

движением роботов (см. [167] – [185]) и алгоритмы вероятностного управления движением роботов (см. [186] – [204]).

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

(см., например, [205] – [209]), моделирования представления знаний (см., например,

[210] – [212]), разработки систем управления механическим движением (см., например,

[213] – [220]), создания графических симуляторов (см., например, [221] – [225]).

Литература

1.Garzon M., Drumwright E., Deaton R., Renault D. Virtual test tubes: a new methodology for computing // Proceedings of 7th International Symposium on String Processing and Information Retrieval. IEEE Computer Society Press, 2000. P.116121.

2.Garzon M., Oehmen C. Biomolecular computation in virtual test tubes // Lecture Notes in Computer Science 2340. 2002. P.117–128.

3.Garzon M.H., Blain D.R., Neel A.J. Virtual test tubes // Natural Computing. 2004.

6.Nishikawa A., Yamamura M., Hagiya M. Dna computation simulator based on abstract bases // Soft Computing. 2001. V.5. P.25–38.

7.Bois J.S., Venkataraman S., Choi H.M.T., Spakowitz A.J., Wang Z., Pierce N.A. Topological constraints in nucleic acid hybridization kinetics // Nucleic Acids Research. 2005. V.33. P.4090–4095.

8.Dirks R.M., Bois J.S., Schaeffer J.M., Winfree E., Pierce N.A. Thermodynamic analysis of interacting nucleic acid strands // SIAM Rev. 2007. V.49. P.65–88.

190