Содержание

1 Введение. Нанобиология в нанонауке................................................. 4

2 Две сверхзадачи нанонауки.................................................................. 5

2.1 Проблема гигантских усилений......................................................... 5

2.2 Проблема взаимодействия иерархических уровней.......................... 6

3 Нанобиология в масштабах................................................................... 7

4 Применение идей синергетики в нанонауке....................................... 7

4.1 Парадигма диссипативных структур................................................. 8

4.2 Парадигма динамического хаоса....................................................... 9

4.3 Парадигма сложности...................................................................... 11

5 Клетка – квантовый компьютер?...................................................... 11

5.1 На каком уровне находится «сознание»?........................................ 11

5.2 Нейронные сети и формальные нейроны........................................ 12

5.3 Гипотеза Хамероффа-Пенроуза....................................................... 13

5.4 Проблемы и идеи............................................................................. 16

6 ДНК-вычисления и ДНК-компьютеры.............................................. 16

6.1 Пределы роста.................................................................................. 16

6.2 Путь к ДНК-вычислениям................................................................ 18

6.3 Базовые операции ДНК-вычислений............................................... 18

6.4 Опыт Л. Эдлмана. Поиск гамильтонова пути на графе................... 21

6.5 Опыт Э. Шапиро. Конечный автомат на ДНК................................ 23

6.6 Задел в молекулярных вычислениях. Проблемы и идеи................. 24

6.6.1 Парадигма ДНК-вычислений. Внешнее оправдание................ 25

6.6.2 Два пути развития парадигмы ДНК-вычислений.................... 26

6.6.3 Создание эмулятора ДНК-вычислителя................................... 26

6.6.4 Создание языка программирования высокого уровня для ДНК-вычислителя.................................................................................. 27

6.6.5 Создание банка задач и алгоритмов для ДНК-вычислителя... 28

6.6.6 Среда разработки программ для ДНК-вычислителя............... 28

Список литературы................................................................................. 29

1 Введение. Нанобиология в нанонауке

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

         Сегодня у нас с вами есть замечательная возможность начать обширный круг исследований не с критики существующих теорий и не с проверки их в эксперименте, а с удивления перед фактами, причины которых хочется установить. В этой области у нас нет удовлетворительных физических теорий, разработаны только первые инструменты эмпирического исследования, нет многих необходимых математических моделей, но накоплена богатая феноменология. Речь идет об исследованиях живого вещества в масштабе 10^-9м, или в наномасштабе. Именно в этом масштабе природа «программирует» основные характеристики веществ, явлений и процессов [1].

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

         История нанонауки начинается с лекции Р. Фейнмана, прочитанной в канун 1960 г. на обеде Американского физического общества [2]. Прежде всего, Фейнман обращает наше внимание на чудеса биологических систем (он имеет в виду клетки), говоря об огромной плотности записи информации в этих системах и о сложных процессах обработки информации. Фейнман говорит о миниатюризации компьютеров, возможности создания наноструктур путем постепенного уменьшения, возможности манипулирования отдельными атомами, перспективах работы с квантовыми уровнями энергии. Миниатюризация компьютеров произошла, мы уже учимся манипулировать отдельными атомами. Пришел черед квантовых уровней энергии?

         Одним из идеологов нанотехнологии стал К.Э. Дрекслер [3]. Его книга, выпущенная в 1986 г., содержит идеи молекулярных вычислений, идеи самосборки наноконструкций, нанокомпьютеров, а также большое количество идей применения нанотехнологии в науке о материалах, космосе, медицине, экологии. Кроме того, книга содержит и анализ возможных рисков, связанных с применением нанотехнологии.

         В настоящее время большая часть сверхминиатюрных устройств создается при помощи технических, а не биологических принципов. При дальнейшем уменьшении систем, наделение их необходимой функциональностью будет затруднено,  в то время как в биологических системах многие технические задачи успешно решаются при помощи молекулярных двигателей и других внутриклеточных функциональных систем [1,с.160]. Специалисты прогнозируют создание гибридных наномеханических объектов, на основе биологических систем и неорганических устройств.

         В настоящее время решаются проблемы переноса генной информации внутрь клеток. Идеальным решением данной проблемы было бы использование наночастиц ДНК с заданным набором параметров. Это позволило бы создать новые методики введения генов in vivo, т.е. в живом объекте (в отличие от in vitro – вне живого оргнизма, в пробирке).

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

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

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

         Итак, один из мотивов, побуждающих нас к изучению живого вещества в наномасштабе – это мотив технологический.

         Существуют еще по меньшей мере два столь же весомых мотива: первый из них озвучен Р. Пенроузом [4], а второй – C. Хамероффом [5]. Первый заключается в том, что создание современной картины мира требует проверки гипотезы об объективной квантовой редукции, а второй – в том, что современная нейронаука исчерпала возможности парадигмы мозга как молекулярно-химической машины для объяснения механизмов работы сознания.

         В основу настоящей работы положен доклад на семинаре «Математическое моделирование процессов в наномасштабе» 22.03.2005 г. [6].

2 Две сверхзадачи нанонауки

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

2.1 Проблема гигантских усилений

Борьба с вирусами и бактериями – большая часть всей современной медицины. Объекты размером не более 10 мкм оказывают существенное влияние на организм человека вплоть до прекращения его функционирования. В то же время, если представить себе человека в роли микрообъекта, то тогда он должен был бы оказывать влияние на космические объекты, вроде отдаленных планет и звезд. Сегодня нам трудно себе это представить, что свидетельствует о недостаточном понимании механизмов усиления в интервале масштабов 10^-9-1м.

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

Рис. 2.1 Опыт по прохождению пучка электронов через две щели

2.2 Проблема взаимодействия иерархических уровней

Эта проблема тесно связана с проблемой гигантских усилений.

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

3 Нанобиология в масштабах

Рис. 3.1 Наномир в масштабах

На рис. 3.1 A - атом углерода, 0.15 нм в диаметре, B – молекула аминокислоты аланин, состоящая из 13 атомов, 0.33 нм в диаметре, С – фрагмент молекулы ДНК, 2 нм в диаметре, D - молекула тубулина, 8 нм в длину,  E-  микротрубочка в разрезе, 25 нм в диаметре,  F -  аксон нервной клетки в разрезе, 1000 нм в диаметре, может содержать 100 микротрубочек и 1000 филаментов меньшего размера, G – животная клетка 100-1000 мкм, H  - нематод, маленький червь, состоящий из менее чем 1000 клеток, 170 мкм в «диаметре», 450 мкм в длину, I – четверть человеческого волоса и 50 нематодов, диаметр окружности 5 мм.

4 Применение идей синергетики в нанонауке

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

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

         По мнению специалистов, в области развития теории и моделей наномира, прогресс в последние годы достигался в основном путем использования более мощных компьютеров и компьютерных программ, и в гораздо меньшей мере за счет появления новых теоретических представлений и моделей [1,с. 48]. Поэтому, большой опыт, накопленный в синергетике по части моделирования процессов самоорганизации, именно в виде моделей и теоретических построений, представляется особенно важным для дальнейшего развития нанонауки.

         В истории развития синергетики выделяют три периода, или парадигмы исследований [7]. Рассмотрим вкратце, какие идеи каждой из парадигм могут быть использованы в нанонауке.

4.1 Парадигма диссипативных структур

         В работах, принадлежащих парадигме диссипативных структур, исследователям удалось изучить образование структур различного характера (временных, пространственных, пространственно-временных) в системах различной природы. Например, на рис. 4.1 показаны структуры, возникающие в классическом опыте Бенара – при нагревании слоя вязкой жидкости, а на рис. 4.2  – структуры, возникающие при обтекании жидкостью  цилиндра [8].

Рис. 4.1 Ячейки Бенара.

Рис. 4.2 Образование структур при обтекании жидкостью цилиндра (дорожка Кармана)

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

u_t = div (k₁ grad u ) + f(u,v)                                                                       (4.1)

v_t = div (k₂ grad v ) + g(u,v)

         Смысл переменных u и v, обычно, концентрации. Само понятие концентрации подразумевает усреднение на макромасштабах.

Модели этого класса не могут быть использованы непосредственно для моделирования систем в нанометровой шкале, однако, будучи согласованными с моделями более высоких уровней подробности описания, они обладают значительной предсказательной силой [9].

Заметим, что в биофизике представления о самоорганизации и диссипативных структурах используются давно и плодотворно. Однако, как правило, они доходят до микрометровых (10^-6м) пространственных масштабов.

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

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

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

4.2 Парадигма динамического хаоса

         Одной из ключевых идей парадигмы динамического хаоса стала идея о структурах, обладающих свойством самоподобия - фрактальных структурах [10]. Фрактальные структуры (рис. 4.4) имеют дробную хаусдорфову размерность, что означает, например, бесконечный периметр при конечной площади структуры, или бесконечную площадь структуры при конечном объеме.

С подобными примерами сверхкомпактной упаковки мы встречаемся на каждом шагу, например, так устроены наши легкие (их активная поверхность сравнима по площади с теннисным кортом). Одной из проблем молекулярной биологии является проблема сверхкомпактной упаковки молекулы ДНК (в типичной бактерии молекула ДНК в 10000 раз длиннее самой клетки)  [11].

Рис. 4.4 Фрагмент множества Жюлиа

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

         Еще одной идеей парадигмы динамического хаоса, которая может быть применена в нанонауке, является идея о том, что сложные структуры могут создаваться по весьма простым правилам. Это касается, в частности, различных систем логистических отображений и карт устойчивости для них (рис. 4.5, 4.6). (Карты устойчивости – это метод визуализации качественных особенностей динамических систем. В пространстве параметров для каждой точки вычисляется старший показатель Ляпунова, характеризующий динамику системы при заданном наборе параметров. Далее диапазону показателей Ляпунова ставится в соответствие цветовой диапазон).

Рис. 4.5 Карта устойчивости для                      Рис. 4.6. Карта устойчивости для

дискретной модели хищник-жертва                  логистического отображения с внешней силой

4.3 Парадигма сложности

         Среди основных направлений парадигмы сложности – анализ различных типов эволюции, описание и прогноз редких катастрофических событий, описание сложных необратимо развивающихся систем (организм, психика, экономика, биосфера и др.), моделирование элементов сознания, рефлексивных процессов.

         Можно привести следующий пример. Одним из основных разделов теоретической физики является статистическая механика. В ней отдельные частицы представляются часто шарами, имеющими массу, скорость, может быть заряд или спин. В экономике, в популяциях животных, в группах людей также имеют место статистические закономерности. Но сами взаимодействующие сущности – агенты – сложнее. Они могут оценивать окружение, собственное состояние или предисторию, могут оптимизировать, размножаться или вычислять. Но разве не так устроены клетки, обеспечивающие иммунный ответ? Этот класс моделей часто называют многоагентными системами, а исследование их статистических свойств, с легкой руки Дж. Фармера, вычислительной механикой.

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

         В частности, одной из важных идей этой парадигмы является сжатия информации (например, изображения), путем нахождения динамической системы вида  (4.2).

                                                                                                 (4.2)

5 Клетка – квантовый компьютер?

5.1 На каком уровне находится «сознание»?

Специалисты по нейрофизиологии утверждают [12], что понимание мозга как молекулярно-химической машины не дает нам возможности понять самого главного – каким образом возникают субъективные ощущения? Субъективные ощущения не вытекают из молекулярно-химического кода, а возникают, как нечто дополнительное к нему.

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

5.2 Нейронные сети и формальные нейроны

В конце 19 века итальянский нейрофизиолог К. Гольджи открыл метод окрашивания нервных тканей солями серебра. Применив этот метод, испанский ученый Рамон-и-Кахаль обнаружил тот факт, что мозг представляет собой совокупность отдельных нейронов, а не единую сеть нервных волокон.  Схематическое изображение нейрона представлено на рис.5.1.

Рис. 5.1 Схематическое изображение типичного нейрона

         С точки зрения динамики, отдельный «стандартный» нейрон оказался достаточно простым объектом: если сумма входных сигналов превышает некоторое пороговое значение, генерируется «стандартный импульс» (рис. 5.2).

Рис. 5.2 Потенциал действия в точке нейрона, расположенной на аксоне

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

         С мозгом, как с сетью нейронов, связаны две характерные цифры: мозг человека содержит около 10¹² нейронов, а максимальная скорость распространения нервного импульса оценивается в 100 м/c. Сравнение этих характерных величин с соответствующими величинами для элементов микропроцессора дает повод для удивления (у микропроцессора и скорость передачи сигнала и скорость срабатывания в миллион раз выше):

·        каким образом машина со столь медленной «элементной базой» способна выполнять сложные вычисления?

·        какие принципы организации памяти использует мозг?

Биологические системы, например, сообщества общественных насекомых,  обладают исключительно сложным поведением. Однако нервная система муравья содержит всего 8 нейронов.

Мозг человека представляет собой надежную систему из ненадежных элементов. К старости ряд структур мозга может терять до 30-40% клеток, не теряя существенных фрагментов воспоминаний и интеллектуальных способностей.

Из приведенных примеров становится ясно, что аппарата нейронных сетей недостаточно для описания сложного поведения биологических систем. Каким же будет следующий шаг в этом направлении?

5.3 Гипотеза Хамероффа-Пенроуза

Существует задача об отыскании набора геометрических фигур на плоскости (плиток), которыми Евклидова плоскость может быть покрыта только непериодическим образом.  В 1961 г. было показано, что невозможно создать алгоритм, который определяет, можно ли покрыть плоскость при помощи заданного набора плиток, или нет. Позже был предъявлен набор из 20426 плиток, которыми можно покрыть плоскость только непериодически. В дальнейшем количество плиток было сокращено сначала до 104, а затем и до 6, и, наконец, до двух (рис. 5.3).

Рис. 5.3 Плитки Пенроуза, которыми плоскость может быть заполнена только непериодическим образом

Интересен следующий факт: Р. Пенроуз [4, с.118] получил свой набор из 2-х плиток путем различных манипуляций разрезания и склеивания над набором Робинсона из 6 плиток. (К этим операциям мы еще вернемся в разделе о ДНК-вычислениях).

         Таким образом, решение задачи о покрытии плоскости плитками непериодическим образом служит подтверждением гипотезы Р. Пенроуза о невычислимости сознания [4]. Под невычислимостью в данном контексте понимается принципиальная невозможность предъявить машину Тьюринга для решения конкретной задачи. Однако, возможно, существуют принципиально другие типы вычислений?

         Поразительным открытием в области химии стало открытие квазикристаллов Al₇₂Ni₂₀Co₈. Рис. 5.4 показывает сравнение изображения структуры квазикристалла, полученного при помощи специального электронного микроскопа, с покрытием плоскости плитками Пенроуза [13].

Рис. 5.4 Структура квазикристалла (слева) и покрытие плоскости плитками (справа)

         Еще одной важной гипотезой Р. Пенроуза стала гипотеза об объективной квантовой редукции: существует некоторый объективный физический процесс, который воздействует на редукцию квантового состояния. Проектируется эксперимент в космических масштабах, который позволит проверить эту гипотезу. Однако существует гипотеза C. Хамероффа о том, что объективная редукция играет важную роль и в механизмах работы сознания, в процессах, происходящих в наномасштабе во внутренних структурах клетки [5].

         Нервная ткань состоит из отдельных нейронов. Каждая нервная клетка имеет важную внутреннюю структуру – цитоскелет, состоящий из микротрубочек. Микротрубочки представляют собой полые трубки, состоящие из белковых молекул – тубулинов (рис. 5.5).  Каждый тубулин (рис. 5.6) представляет собой два полых шарика и содержит около 440 аминокислот. Тубулин может существовать в двух пространственных конфигурациях -  конформациях α и β. Переключение между конформациями осуществляется путем перехода всего лишь одного электрона, и занимает время около 10^-9с. Гипотеза С. Хамероффа заключается в том, что, во-первых, нервная клетка сама по себе – это сложнейшая система обработки информации, во-вторых, цитоскелет клетки – это и есть вычислительная система клетки, и, в-третьих, элементарными операциями в этой системе являются квантовые зацепления состояний отдельных молекул-тубулинов и редукция этих состояний – переключение между конкретными конформациями.

Рис. 5.5 Тубулин – строительная единица цитоскелета клетки. Увеличение масштаба

         На рис.5.5 А – С – иммунофлюорисцентная маркировка строительных блоков микротрубочек клетки – тубулинов (увеличение масштаба), D-F – структура микротрубочек, показана белковая молекула-димер, компонента микротрубочек; G-H – α- и β- мономеры тубулина  [14].

Рис.5.6 Тубулин                                                           Рис. 5.7 Две конформации молекулы тубулина

         Тубулин имеет размер 8 нм, поэтому процессы обработки информации в цитоскелете клетки, которые управляются конформационными переключениями, являются ключевыми для современной нанотехнологии. Создание моделей в этой области крайне необходимо.

         Из гипотезы С. Хамероффа вытекает то, что клетка – это квантовый компьютер. В своих работах Хамерофф предлагает схему квантового вычислителя, основанного на механизме объективной редукции и переключениях между конформациями тубулинов [15].

5.4 Проблемы и идеи

Таким образом, на текущий момент не ясны механизмы обработки информации внутри клетки, не ясны механизмы извлечения и использования результатов.

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

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

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

6 ДНК-вычисления и ДНК-компьютеры

Способность молекул ДНК к регулируемой и высокоорганизованной сборке делает их идеальным материалом для нанотехнологий [1,с.159]. Молекулы ДНК уже применяются для сборки двухмерных структур.

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

6.1 Пределы роста

В 1975г. один из основателей Intel Г. Мур сделал прогноз о том, что количество транзисторов на кристалле процессора будет увеличиваться в два раза каждые 18 месяцев. Несмотря на свой фантастический характер, этот прогноз сбывается в течение 30 лет. Размеры элементов процессора уменьшаются и уменьшаются. На рис. 6.1 представлен график зависимости числа примесей в основаниях транзисторов от времени (можно считать, что этот график показывает количество электронов, необходимых для хранения одного бита информации).

Рис. 6.1 Зависимость числа примесей в основаниях транзисторов от времени

Из графика видно, что, если на заре компьютерной эры было необходимо 10¹¹ электронов для хранения одного бита информации, то сегодня это уже около 10⁴. По словам того же Г. Мура, мы приближаемся к технологическому пределу, который не позволит в дальнейшем уменьшать размеры элементной базы. Предел этот составляет 30 нм.

         С другой стороны, как утверждают специалисты по параллельным вычислениям [16] на основе сравнения двух процессоров – EDSAC (1949 г.) и PA-8700 (2000 г.) (рис. 6.2), за счет усовершенствования технологии (уменьшения процессорных элементов) производительность компьютеров повысилась в 1500  раз, а за счет усовершенствования архитектуры, в частности применения элементов параллелизма – в 1 000 000 раз.

Рис. 6.2 Сравнение процессоров EDSAC и PA-8700

Самый мощный компьютер на сегодня – это BlueGene/L, содержащий 32768 процессоров Power 4. Его пиковая производительность  - 91750 ГФлопс, максимальная, достигнутая на тесте Linpack: 70720 ГФлопс [17]. Несмотря на наличие столь мощных вычислительных систем, мы не умеем решать многих необходимых задач, с которыми справляются системы обработки информации в клетках.

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

         Возможно, настало время поиска новой парадигмы вычислений, первые контуры которой уже намечаются.        

6.2 Путь к ДНК-вычислениям

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

·        Открытие комлементарности оснований ДНК Э. Чарграфом в 1950 г.

·        Открытие двойной спирали ДНК Д. Уотсоном и Ф. Криком в 1953 г.

·        Создание теории самовоспроизводящихся автоматов Дж. фон Нейманом в 1957 г.

·        Расшифровка генетического кода М. Ниренбергом и Г. Матэем в 1965 г.

·        Первый эксперимент по вычислениям на ДНК Л. Эдлмана в 1994 г.

·        Реализация конечного автомата на ДНК Э. Шапиро в 2001 г.

6.3 Базовые операции ДНК-вычислений

         Мы привыкли к тому, что любой алгоритм для цифровой ЭВМ эквивалентен соответствующей машине Тьюринга. В области ДНК-вычислений мы имеем дело с совершенно другим аппаратом: молекулами ДНК и операциями над ними. Молекула ДНК (рис. 6.3) представляет собой двойную ленту, составленную из четырех оснований: А (аденин), Т (Тимин), Г (гуанин), Ц (цитозин).

Рис. 6.3 Молекула ДНК под электронным микроскопом

Нуклеотид с тиминовым основанием (рис. 6.4) состоит из 34 атомов.  Диаметр двойной спирали ДНК – 2нм, расстояние между соседними парами оснований – 0.34 нм. Полный оборот двойная спираль делает через 10 пар. ДНК простейших типов вирусов содержит всего несколько тысяч звеньев, бактерий – несколько миллионов,  а высших организмов – миллиарды [18]: ДНК млекопитающих содержит  пар нуклеотидов, птиц -, пресмыкающихся - , насекомых - , высших растений - б бактерий - , вирус папилломы -  [19, с.138].

Фосфат

Рис. 6.4 Строение нуклеотида с тиминовым основанием

         Комплементарность оснований заключается в том, что образование водородной связи возможно только для пар А-Т и Г-Ц (рис. 6.5). Этот же рисунок иллюстрирует операции ренатурации и денатурации. Ренатурация – это соединение двух одинарных цепочек ДНК за счет спаривания комплементарных оснований. Денатурация – разъединение одинарных цепочек. Денатурация и ренатурация происходят при нагревании и охлаждении раствора с ДНК. Плавление ДНК происходит в диапазоне температур 85-95◦C. Некоторые катализаторы позволяют понизить температуру процесса.

Рис. 6.5 Комплементарность, ренатурация, денатурация

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

         Удлинение цепочки ДНК происходит при воздействии на исходную молекулу ферментов – полимераз (рис. 6.6).

Рис. 6.6 Удлинение и укорочение

         За укорочение и разрезание молекул ДНК отвечают ферменты – нуклеазы. Различают эндонуклеазы и экзонуклеазы. Экзонуклеазы осуществляют укорочение молекулы ДНК с концов (рис. 6.6), эндонуклеазы же разрушают внутренние фосфодиэфирные связи в молекуле ДНК (рис. 6.7). Эндонуклеазы могут быть весьма избирательными в отношении того, что они разрезают, где они разрезают и как они разрезают. Сайт-специфичные эндонуклеазы – рестриктазы – разрезают молекулу ДНК в определенном месте, которое закодировано последовательностью нуклеотидов – сайтом узнавания.

Рис. 6.7 Разрезание

         Сшивка - операция, обратная операции разрезания, происходит под воздействием ферментов – лигаз (рис. 6.7)

         Часто возникает необходимость модифицировать молекулы ДНК, например, для того, чтобы исключить из какой-либо операции. В живой клетке рестриктазы играют роль защитников от агрессии – например, в клетке бактерии, рестриктазы разрушают ДНК вируса-агрессора. Чтобы собственная ДНК не подверглась разрезанию, она модифицируется. Существует несколько типов модифицирующих ферментов – метилазы, фосфатазы и т.д.  Метилаза имеет тот же сайт узнавания, что и соответствующая рестриктаза. При нахождении нужной молекулы, метилаза модифицирует участок с сайтом так, что рестриктаза уже не сможет идентифицировать эту молекулу (рис. 6.8).

Рис. 6.8 Модификация

         Иногда необходимо увеличить количество определенных фрагментов ДНК. Это делается при помощи метода полимеразной цепной реакции (К. Маллис). Этот метод позволяет получить миллионы копий желаемой молекулы, даже если начать всего лишь с одного ее экземпляра (рис. 6.9).

Рис. 6.9 Полимеразная цепная реакция

         Еще одной интересной операцией является операция сплетения (рис. 6.10). Две молекулы ДНК разрезаются, а затем полученные половинки сшиваются между собой.

Рис. 6.10 Сплетение

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

6.4 Опыт Л. Эдлмана. Поиск гамильтонова пути на графе

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

Для решения задачи был применен следующий алгоритм:

Вход. Ориентированный граф G с n вершинами, среди которых выделены

2 вершины – v_in и v_out.

Шаг 1. Породить большое количество случайных путей в G.

Шаг 2. Отбросить все пути, которые не начинаются с v_in или не закан-чиваются на v_out.

Шаг 3. Отбросить все пути, которые не содержат точно n вершин.

Шаг 4. Для каждой из n вершин v отбросить пути, которые не содержат v.

Выход. Да, если есть хоть один путь, нет – в противном случае.

Рис. 6.11 Граф в опыте Эдлмана

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

Рис. 6.12 Кодирование ребер и вершин в опыте Эдлмана

6.5 Опыт Э. Шапиро. Конечный автомат на ДНК

Опыт, осуществленный в 2001 г. группой Э. Шапиро [20] принципиально отличается от опыта Эдлмана тем, что и «исходные данные», и «программа» описываются молекулами ДНК, в то время как в опыте Эдлмана «программа» - это, по большому счету, последовательность реакций, задаваемых человеком.

В опыте Э. Шапиро был реализован конечный автомат, т.е. система, состоящая из множества состояний, алфавита, начального состояния, множества заключительных состояний и функции переходов. Данный автомат изображен на рис. 6.13. Автомат может находиться в двух состояниях – S0 и S1. Алфавит автомата состоит из двух символов – a и b. На вход автомату подается последовательность символов a и b. Автомат отвечает на вопрос – четное или нечетное количество символов b содержится во входной последовательности. Автомат может отвечать на 765 подобных «вопросов». Программирование автомата заключается в задании функции переходов, которой соответствует набор стрелок на рис. 6.13. И переходам, и состояниям, и входной последовательности в опыте Шапиро отвечают молекулы ДНК.

Рис. 6.13 Конечный автомат в опыте Э. Шапиро

         Логическая схема опыта изображена на рис. 6.14. Основная идея заключается в следующем: входная последовательность кодируется цепочкой ДНК.  Цепочка разрезается некоторым специальным образом при помощи рестриктазы Fok1 для того, чтобы к ней могла прилипнуть молекула, соответствующая одному из переходов автомата. Молекула-переход прилипает, происходит сшивание при помощи лигазы. Затем снова происходит разрезание при помощи рестриктазы Fok1, и прилипание следующего перехода. По окончании вычислений к молекуле – результату прилипает одна из молекул – меток. Естественно, молекулы, отвечающие за переходы, заданы так, чтобы работать в соотвествии со схемой автомата на рис. 6.13. В опыте Э. Шапиро использовались искусственные молекулы ДНК, синтезированные специально для эксперимента.

В опыте одновременно работали 10¹² автоматов с одинаковым «программным обеспечением». Входные данные, в принципе, для автоматов могут быть различными. «Вычислительная мощность» составляла 10⁹ переходов в секунду с вероятностью больше, чем 99,8%.

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

Рис. 6.14 Схема опыта Э. Шапиро

6.6 Задел в молекулярных вычислениях. Проблемы и идеи

Менее чем за 10 лет в области молекулярных вычислений появилось более 1000 публикаций [22]. Появилась также первая монография [11]. В публикациях обсуждаются первые эксперименты по молекулярным вычислениям, повторяются опыты Эдлмана. Например, проведен опыт по нахождению количества гамильтоновых путей на графе. Обсуждаются алгоритмы, которые могут быть реализованы на ДНК-вычислителях.

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

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

6.6.1 Парадигма ДНК-вычислений. Внешнее оправдание

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

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

В наше время огромные вычислительные усилия затрачиваются на этапе поиска веществ с нужными свойствами, например, лекарственных препаратов. Определяется множество молекул-кандидатов, затем это множество сужается при помощи расчетов. На каждом следующем этапе проводятся более подробные исследования. Данный подход приводит к успеху, однако не решает задачу синтеза нужного вещества. Например, при поиске лекарства от рака было проверено около 200000 веществ. В результате было найдено одно (!) вещество – таксол - яд, содержащийся в малых количествах в коре тиса. Синтез этого вещества не дешевле, чем извлечение его из натурального сырья, а в нем оно содержится в слишком малых количествах [26].

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

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

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

6.6.2 Два пути развития парадигмы ДНК-вычислений

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

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

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

Развитие парадигмы ДНК-вычислений, кроме развития теории, распадается на следующие важнейшие практические задачи:

·        Создание эмулятора ДНК-вычислителя.

·        Разработка языка программирования высокого уровня для ДНК-вычислителя.

·        Создание банка задач и алгоритмов для ДНК-вычислителя.

·        Создание среды разработки программ для ДНК-вычислителя.

Рассмотрим эти задачи более подробно.

6.6.3 Создание эмулятора ДНК-вычислителя

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

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

         Основные требования к эмулятору ДНК-вычислителя:

·        Возможность имитации экспериментов биологами, максимальный учет запросов биологов на этапе составления требований к эмулятору. (Как следствие, использование по максимуму реальных представлений о проведении эксперимента).

·        Расширяемость: возможность добавления новых ферментов, новых приемов проведения эксперимента.

·        Максимальная доступность для исследователей: независимый от платформы проект в открытом коде.

·        Возможность выполнения программ, написанных на языке высокого уровня для ДНК-вычислителя.

         Следует отметить (принимая во внимание второй путь), что употребление слов «эмулятор», «байт-код», «программа» и других терминов компьютерных наук нужно считать условным, чтобы избежать переноса смыслов.

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

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

6.6.4 Создание языка программирования высокого уровня для ДНК-вычислителя

Простейшие алгоритмы, такие как алгоритм Эдлмана, записываются на одной странице и представляют собой запись на некотором псевдоалгоритмическом языке. Но даже в этих простейших случаях необходимы дополнительные разъяснения о том, каким образом происходит перевод задачи с языка, например, теории графов, в термины последовательностей ДНК, т.е. формализованное описание алгоритма не является исчерпывающим. В более сложных случаях, таких как, например, задаче о выполнимости пропозициональных формул [11, с. 63], описание алгоритма занимает уже с десяток страниц, причем объяснение по большей части происходит неформализованным образом, т.е. «на словах». Первым шагом при создании языка высокого уровня должна быть попытка формализации записи алгоритмов для ДНК-вычислителя. Далее (согласно первому пути), необходима интенсивная работа по формализации ДНК-операций в привычных терминах (уже начатая авторами монографии [11]), создание синтаксиса языка высокого уровня на основе накопленного в этой области опыта (в том числе создания макроязыков и библиотек для параллельного программирования), затем создание инструментальных средств, с максимальным привлечением существующих разработок в области грамматик и трансляторов. Вместе с тем следует двигаться и по второму пути, выявляя внутренние особенности новой парадигмы вычислений (преимущественно путем анализа новых экспериментов биологов и экспериментов с эмулятором ДНК-вычислителя).

Отдельным вопросом, требующим разработки, является вопрос об организации памяти на ДНК. Первые шаги в этой области уже сделаны: разработана стикерная модель ДНК-вычислений, которая, по сути, представляет собой память с произвольным доступом [11, с.73], есть работы по ассоциативной и иерархической памяти на ДНК [27,28].

6.6.5 Создание банка задач и алгоритмов для ДНК-вычислителя

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

Это позволит:

·        Обеспечить единство области.

·        Ускорить разработку эмулятора, языка и средства разработки.

·        Поддерживать необходимую долю второго пути в общем потоке исследований (который отталкивается от задач).

·        Отслеживать прогресс в области.

·        Быстрее перейти к практическому использованию.

6.6.6 Среда разработки программ для ДНК-вычислителя

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

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

         Разработаны система трансляции грамматик в последовательности ДНК [31], системы генерации цепочек ДНК с нужными характеристиками [30, 32], версии эмуляторов ДНК-вычислителя [29, 33, 34, 35].

Список литературы

1.     Нанотехнология в ближайшем десятилетии. Прогноз направления исследований. /Под ред. М.К. Роко, Р.С. Уильямса и П. Аливисатоса. Пер. с англ. – М.: Мир, 2002 – 292с., ил.

2.     Фейнман Р.Ф. Внизу полным-полно места: приглашение в новый мир физики. // Рос. хим.ж., 2002 , т.XLVI, № 5, http://www.zyvex.com/nanotech/feynman.html

3.     Дрекслер К.Э. Машины создания. Грядущая эра нанотехнологии.// http://filosof.historic.ru/books/item/f00/s00/z0000328.

4.     Пенроуз Р. Новый ум короля: О компьютерах, мышлении и законах физики: Пер. с англ. /Общ.ред. В.О.Малышенко. – М.: Едиториал УРСС, 2003. – 384с.

5.     Hameroff Stuart R. Ultimate computing. Biomolecular Consciousness  and NanoTechnology. // Elsevier Science Publishers В.V., 1987.

6.     Малинецкий Г.Г., Митин Н.А., Науменко С.А. Нанобиология и синергетика. Проблемы и идеи. Демонстрация к докладу на семинаре «Математическое моделирование процессов в наномасштабе».
//http://www.keldysh.ru/departments/dpt_17/gmalin/pr.htm.

7.     Малинецкий Г.Г., Потапов А.Б. Современные проблемы нелинейной динамики. Изд. 2-е, исправл. и доп.. М.:Едиториал УРСС, 2002. -360с.

8.     Хакен Г. Синергетика. М.: Мир, 1980.

9.     Еленин Г.Г. Нанотехнологии, наноматериалы, наноустройства. // Новое в синергетике: Взгляд в третье тысячелетие. – М.: Наука, 2002. – 478с., ил.

10. Мандельброт Б. Фрактальная геометрия природы. – Москва: Институт компьютерных исследований, 2002, 656с.

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

12. Базян А.С. Восприятие, кодирование и переработка информации мозгом. // Доклад на семинаре по проблемам работы мозга в МВТУ им. Баумана, 23.03.2005.

13. K. Saitoh, K. Tsuda, M. Tanaka and A. P. Tsai, "Structural Study of Al₇₂Ni₂₀Co₈ Decagonal Quasicrystal by High-angle Annular Dark-field Image method", Japanese Journal of Applied Physics, Vol.36 (1997).

14. Hameroff, S. Microtubules – Nature’s Quantum Computers?
//www.quantumconsciousness.org/presentations/microtubules.html.

15. Hameroff S. Orchestrated Objective Reduction of Quantum Coherence in Brain Microtubules: The "Orch OR" Model for Consciousness.

16. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – Спб.: БХВ-Петербург, 2002 – 608с.: ил.

17. www.top500.org.

18. Франк-Каменецкий М.Д. Век ДНК – М.: КДУ, 2004 – 240с, ил.

19.  Вилли К, Детье В. Биология. (Биологические процессы и законы) Пер. с англ. М.: Мир, 1975.

20.  Shapiro E. Programmable and autonomus computing machine made of biomolecules//Letters to nature, vol 414,  22 november 2001.

21.  Shapiro E. A mechanical Turing machine: blueprint for a biomolecular computer.

22. A bibliography of Molecular Computation and Splicing Systems // http://www.dcs.ex.ac.uk/~pf201/dna.html.

23.  Mucic, R.C., J.J.Storhoff, C.A.Mirkin, and R.L.Letsinger. 1998. DNA-directed synthesis of binary nanoparticle network materials. Journal of the American Chemical Society 120:12674-12675.

24. Alivisatos, A.P.,K.P.Johnsson, X.G.Peng.T.E.Wilson,C.J.Loweth,M.Bruchez, and P.G.Schultz, 1996. Organization of nanocrystal molecules using DNA. Nature 382:609-611.

25. Braun, E. Y.Eichen, U.Sivan. and G.Ben Yoseph. 1998.DNA-templated assembly and electrode attachment of a conducting silver wire. Nature 391:775-778.

26. Садовский, А.С. Таксол – молекула надежды. //Химия и жизнь, 2004 г., №7.

27.  S. Kashiwamura, M. Yamamoto, A. Kameda, T. Shiba, and A. Ohuchi. Hierarchical DNA memory based on nested PCR. Poster paper at the 8th International Workshop on DNA-Based Computers, DNA 2002, Sapporo, Japan, 10-13 June 2002.

28. E. B. Baum. Building an associative memory vastly larger than the brain. Science, 268:583--585, April 28, 1995.

29.  G. Ciobanu and D. Paraschiv. P-system software simulator. Fundamenta Informaticae, 49, 2001.

30.  R. Deaton, J. Chen, H. Bi, and J. A. Rose. A software tool for generating non-crosshybridizating libraries of DNA oligonucleotides. Poster paper at 8th International Workshop on DNA-Based Computers, DNA 2002, Sapporo, Japan, 10-13 June 2002.

31.  U. Feldkamp, W. Banzhaf, and H. Rauhe. A DNA sequence compiler. Poster at 6th International Workshop on DNA-Based Computers, DNA 2000, Leiden, The Netherlands, June 2000.

32.  U. Feldkamp, S. Saghafi, and H. Rauhe. DNAsequencegenerator - a program for the construction of DNA sequences.

33.  C. Graciani-Diaz, F.J. Martin-Mateos, and M.J. Perez-Jimenez. Specification of adleman's restricted model using an automated reasoning system: Verification of lipton's experiment. Lecture Notes in Computer Science, 2509:126--136, 2002.

34. T. Hinze, U. Hatnik, and M. Sturm. An object oriented simulation of real occurring molecular biological processes for DNA computing and its experimental verification. // N. Jonoska and N. C. Seeman, editors. DNA Computing: 7th International Workshop on DNA-Based Computers, DNA7, Tampa, FL, USA, June 10-13, 2001. Revised Papers, volume 2340. Springer Verlag, Berlin, Heidelberg, New York, 2001., pages 1--13.

35.  Alexander J. Hartemink, Tarjei S. Mikkelsen, and David K. Gifford. Simulating biological reactions: A modular approach. // E. Winfree and D. K. Gifford, editors. DNA Based Computers V, volume 54 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 1999, pages 111--121.