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

Остальные рефераты » 4 Применение идей синергетики в нанонауке 7 Скачать

Содержание

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).


ut = div (k1 grad u ) + f(u v) (4.1)

vt = div (k2 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 Потенциал действия в точке нейрона расположенной на аксоне

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

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

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

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

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

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

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

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

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

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

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

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

Поразительным открытием в области химии стало открытие квазикристаллов Al72Ni20Co8. Рис. 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 Зависимость числа примесей в основаниях транзисторов от времени


Из графика видно что если на заре компьютерной эры было необходимо 1011 электронов для хранения одного бита информации то сегодня это уже около 104. По словам того же Г. Мура мы приближаемся к технологическому пределу который не позволит в дальнейшем уменьшать размеры элементной базы. Предел этот составляет 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 вершины – vin и vout.

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

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

Шаг 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. В опыте Э. Шапиро использовались искусственные молекулы ДНК синтезированные специально для эксперимента.

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

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


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


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

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

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

Страницы: 1 2