ПРОГРАММИРОВАНИЕ, 2014, No 6, с. 3-11
- ТЕОРЕТИЧЕСКИЕ ВОПРОСЫ ПРОГРАММИРОВАНИЯ
У V 681.32
МОДЕЛИРОВАНИЕ ИСКУССТВЕННОЙ БИОЛОГИЧЕСКОЙ КЛЕТКИ В МЕЛКОЗЕРНИСТОЙ СТРУКТУРЕ
© 2014 г. С.М. Ачасова
Институт вычислительной математики и математической геофизики СО РАН 630090 Новосибирск, проспект Академика Лаврентьева, 6 E-mail: achasova@ssd.sscc.ru Поступила в редакцию 28.01.2013
Предлагаются две модели искусственной биологической клетки, построенные в мелкозернистой структуре, которые могут быть элементами вычислительных устройств, имитирующих свойства живых организмов - рост, самовоспроизведение, самовосстановление. Модели разработаны на основе Алгоритма параллельных подстановок - пространственной модели мелкозернистых параллельных алгоритмов и архитектур. Искусственная биологическая клетка строится из генома, поданного на входную ленту. Результатом построения является модель искусственной биологической клетки, в которой записан фенотип в виде совокупности фиксированных данных и генотип в виде совокупности мобильных данных.
1. ВВЕДЕНИЕ
Джон фон Нейман ввел понятие клеточного автомата для представления и изучения логических моделей процессов самовоспроизведения [1]. Его целью было понять и описать на логическом уровне фундаментальные принципы и алгоритмы переработки информации, включенные в процессы самовоспроизведения, другими словами, выделить из природного процесса самовоспроизведения его логическую форму. Интересно заметить, что за несколько лет до открытия Уотсоном и Криком структуры ДНК в виде двойной спирали [2, 3] фон Нейман сформулировал необходимость существования одномерного описания (генома) для самовоспроизводящейся структуры, которое подается на входную ленту и затем порождает эту структуру в клеточно-автоматном пространстве. Подчеркнем, что это есть демонстрация свойства клеточного автомата как универсального конструктора. Кроме того, фон Нейман сформулировал принцип двойственного использования информации, которая подается на входную ленту, т.е. генома: информация должна служить программой для построения материнской структуры (трансляция ге-
нома) и должна быть скопирована в материнскую структуру (транскрипция генома) для того, чтобы далее могли быть порождены дочерние структуры.
Далее изучение самовоспроизведения было связано с петлей Лангтона [4, 5, 6]. Эта структура лишена свойства универсального конструктора и способна воспроизводить только саму себя. Первоначально это - прямоугольная петля, помещенная в двумерное клеточно-автоматное пространство и созданная на основе периодического излучателя, который является фрагментом клеточного автомата Кодда [7], в свою очередь, полученного путем упрощения автомата фон Неймана. Внутри материнской петли Лангтона циркулирует самоописание (геном) петли в виде последовательности состояний автомата. Одновременно с построением дочерней петли геном переписывается в нее, и эта петля затем порождает свою дочку. Петля Лангтона использовалась в качестве модели при проверке гипотез, относящихся к возникновению биологической жизни [8, 9, 10]. Петля наделялась способностью взаимодействовать с внешним наблюдателем [11]. Делались попытки создавать на основе петли "полезный
репликатор" [12, 13], т.е. клеточную структуру, которая вместе с построением копий выполняет некоторую вычислительную программу. При успешном развитии такого направления самовоспроизводящуюся структуру можно рассматривать как новую парадигму параллельных мелкозернистых алгоритмов и архитектур.
Тема статьи навеяна работами [14, 15, 16]. В них строится самовоспроизводящаяся петля нового типа (авторы называют ее искусственной биологической клеткой), которая, становясь компонентой искусственного мультиклеточного биологического организма, обеспечивает ему имитацию свойств живых организмов - рост, самовоспроизведение, самовосстановление. Искусственная биологическая клетка строится из генома, который подается на входную ленту. Результатом построения является модель, в которой записан фенотип в виде совокупности фиксированных данных и генотип в виде совокупности мобильных данных. Фенотип участвует в выполнении задания, предложенного искусственному биологическому организму, генотип способен порождать дочерние клетки.
В статье описаны две мелкозернистые модели искусственных биологических клеток - звезда, еж-1 и еж-2. Модели построены на основе Алгоритма параллельных подстановок (АПП) - системы моделирования пространственных мелкозернистых параллельных алгоритмов и архитектур - [17, 18]. Алгоритм параллельных подстановок, являясь расширенной парадигмой классического клеточного автомата, имеет по сравнению с КА новые свойства, усиливающие его функциональные и выразительные возможности. Эти свойства состоят в следующем. Допускается произвольный шаблон подстановки. В каждом такте одна подстановка может изменять состояния сразу нескольких клеток. Введен новый тип подстановки - функциональная подстановка, в ней новые состояния клеток являются функциями от состояний соседних клеток. Эти свойства АПП дают возможность строить лаконичное, легко обозримое и структурированное описание процесса построения мелкозернистых моделей искусственных биологических клеток. Опыт построения на основе АПП петли Лангтона представлен в [19, 20].
Для имитационного моделирования алгорит-
мов параллельных подстановок создана система моделирования мелкозернистых алгоритмов и структур Win ALT [21] (сайт системы Win ALT. -http://winalt.sscc.tu/) .
2. АЛГОРИТМ ПАРАЛЛЕЛЬНЫХ ПОДСТАНОВОК
В данной работе АПП функционирует в двумерном пространстве, разделенном на клетки (в смысле клеточно-автоматного пространства), и в дискретном времени. Каждая клетка может находиться в одном состоянии из набора возможных и изменять свое текущее состояние согласно локальному правилу или подстановке, в которой новое состояние клетки определяется ее текущим состоянием и состояниями клеток, входящих в шаблон подстановки. Подстановки могут иметь произвольный шаблон - геометрический образ в дискретном пространстве. Левая часть подстановки определяет условие применимости ее и состоит из двух частей - базы и контекста. Правая часть подстановки задает новые состояния клеткам базы. Состояния клеток своего контекста подстановка не изменяет. Новые состояния базовых клеток могут быть либо просто состояниями из множества возможных (тогда подстановка называется символьной), либо функциями от состояний клеток левой части подстановки (в этом случае подстановка называется функциональной). Все применимые в некотором такте дискретного времени подстановки выполняются одновременно. Поскольку в АПП допускается произвольный шаблон подстановки, то возможна ситуация, в которой одна и та же клетка оказывается в зоне применимости двух подстановок. Если эта клетка в обеих подстановках является контекстной, или в одной - контекстной, а в другой - базовой, то не возникает проблемы с изменением ее состояния. Не возникает проблемы и в том случае, когда клетка является базовой в обеих подстановках и ее новое состояние является одним и тем же в этих подстановках. Противоречие в применимости подстановок возникает, если состояние общей клетки изменяется двумя подстановками по-разному. Алгоритм параллельных подстановок должен содержать непротиворечивое множество подстановок. В [17, 18] сформулированы критерии непротиворечивости и даны способы про-
Рис. 1.
верки множества параллельных подстановок на непротиворечивость.
3. ИСКУССТВЕННАЯ БИОЛОГИЧЕСКАЯ КЛЕТКА ЗВЕЗДА
К сожалению, возникает терминологическая коллизия: один и тот же термин "клетка" применяется к биологической единице и к математической единице как элементу клеточно-автоматного пространства. Предлагается эту коллизию преодолеть следующим образом. Элемент клеточно-автоматного пространства или мелкозернистой структуры будем называть, как и принято, клеткой и прилагательное "клеточный" относить только к математической клетке. При упоминании искусственной биологической клетки будем пользоваться двумя названиями, данными здесь моделям искусственной биологической клетки, звезда и еж, или употреблять полное выражение искусственная биологическая клетка или немного усеченное искусственная клетка. Итак, в этом разделе будет представлен алгоритм параллельных подстановок STAR, с помощью которого строится искусственная биологическая клетка звезда.
Звезда строится из четырех полей, каждое поле представляет собою прямоугольник, составленный из четырех клеток, два соседних поля перпендикулярны друг другу (см. рис. 1). Искусственный геном для звезды состоит из восьми символов [С1 В 2 Ю 3 3 4|. Буквы символизируют собою управляющие флаги, которые необходимы для построения скелета искусственной клетки, для установления соединения между ее полями на север, восток, юг и запад. Цифры функциональные коды искусственной биологической клетки. К звезде подается два экземпля-
ра генома с тем, чтобы построить фенотип в виде множества фиксированных символов и генотип в виде множества мобильных символов.
На рис. 1 показана звезда в нулевом такте (t = 0), где клетки полей звезды пронумерованы, а также звезда в виде условного образа в финальном такте (t = 16), когда построение ее завершено. В третьих и четвертых клетках четырех полей звезды при t = 16 (клетки с крестами внутри) записан фенотип, в первых и вторых клетках полей циркулирует генотип.
Клетки мелкозернистой структуры, в которой строится звезда, могут находиться в одном из десяти состояний {С, 1, В, 2, Ю, 3,3, 4,0, О}. Восемь состояний - элементы генома, 0 - состояние покоя, в нем клетки находятся изначаль-
0
ся пустыми), О дополнительное управляющее состояние. Алгоритм параллельных подстановок STAR состоит из трех символьных подстановок и двух функциональных. На рис. 2(a) показаны шаблоны для функциональных подстановок. На рис. 2(6) показаны подстановки: в левой колонке символьные, в правой функциональные. На рис. 2(в) даны функции, используемые в функциональных подстановках.
В правых частях символьных подстановок черточки соответствуют клеткам контекста. Ради лаконичности мы посчитали целесо
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.