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

Подождите немного. Документ загружается.

ДНК-компьютер.

Новая парадигма вычислений.

Texts in Theoretical Computer Science

An EATCS Series

Editors: W. Brauer, G. Rozenberg, A. Salomaa,

G. Paun, G. Rozenberg, A. Salomaa

DNA Computing

New Computing Paradigms

With 76 Figures

Berlin • Heidelberg • New York • Bacelona • Budapest • Hong

Kong • London • Milan • Paris • Singapore • Tokyo

Г. Паун, Г. Розенберг, А. Саломаа

ДНК-компьютер.

Новая парадигма

вычислений

Перевод с английского Д. С. Ананичева, И. С. Киселевой,

О. Б. Финогеновой, под редакцией М. В. Волкова.

Москва «Мир» 2003

УДК 575

ББК 22.19+28.070

П21

Паун Г., Розенберг Г., Саломаа А.

ДНК-компьютер. Новая парадигма вычислений: Пер. с англ. —

М.:Мир, 2003.—528с., 76 ил.

ISBN 5-03-003480-3

Первая в мировой литературе книга по ДНК-вычислениям, написан-

ная авторитетнейшими европейскими специалистами в области компью-

терных наук; последний из авторов знаком читателям по переводам его

монографий «Жемчужины теории формальных языков» («Мир», 1986) и

«Криптография с открытым ключом» («Мир», 1996). Авторы раскрывают

новое перспективное направление на стыке компьютерных наук и моле-

кулярной биологии — двух дисциплин, претендующих на право считаться

главной наукой XXI века. В первой части книги на доступном уровне изло-

жены начала генетической инженерии, обсуждены экспериментальные и

теоретические основы ДНК-вычислений. Вторая часть книги носит более

специальный характер и содержит новые результаты теории формальных

языков, связанные с моделированием реальных процессов, происходящих

с молекулами ДНК в живых клетках.

Для специалистов по дискретной математике и компьютерным на-

укам, для молекулярных биологов и биохимиков, для аспирантов и

студентов университетов.

УДК 575

ББК 22.19+28.070

Издание осуществлено при финансовой поддержке

Российского фонда фундаментальных исследований

по проекту № 01-01-14047

Редакция литературы по математическим наукам

Translation from the English language edition:

DNA Computing. New Computing Paradigms

by Gh. P˘aun. G. Rozenberg, A. Salomaa

 Springer-Verlag Berlin Heidelberg, 1998

Springer-Verlag is a company in the

Bertelsmann Springer publishing group

ISBN 5-03-003480-3

 перевод на русский язык, «Мир», 2004

ISBN 3-540-64196-3 (англ.)

От редактора перевода

Мысль о том, что живая клетка, выполняя свои функции, пере-

рабатывает не только химические вещества, но и информацию,

возникла в треть ей четверти XX-го века, когда была раскры-

та роль ДНК как носителя генетического кода. Человек уже

давно использует живые клетки в качестве ми ниат юрных, но

весьма эффекти вных химических фабрик (вспомним хотя бы

о дрожжах). Можно ли создать из клеток столь же эффек-

тивные «фабрики вычислений»? Знаменитый опыт Эдлмана,

осуществленный в 1994 г., показал, что молекулы ДНК могут

решать вычислительные задачи, причем именно те, которые

представляют наибольшие трудности для традиционных элек-

тронных компьютеров. С этого момента и отсчитывается ко-

роткая пока история ДНК-вычислений.

Предлагаемая внимани ю читателя книга — перевод первой

в мирово й литературе монографии по ДНК-вычислениям, со-

зданной авторитетнейшими европейскими специалистами в об-

ласти компьютерных наук: Георгом Пауном, Гжегоржем Розен-

бергом и Арто Саломаа. (Имя последнего хорошо известно и в

нашей стране благодаря п ереводам двух других его моногра-

фий: «Жемчужины теории формальных языков» и «Крипто-

графия с открытым ключом».) Написанная «по горячим сле-

дам» крупными учеными, внесшими большой личный вклад

в развитие теории ДНК-вычислений, книга раскрывает перед

читателем совершенно новое многообещающее направление на

стыке компьютерных наук и молекулярной биологии — двух

дисциплин, каждая из которых не без оснований претендует

на право считаться главной наукой XXI века.

Книга делится на две части, первая из которых (включаю-

щая главы 1 и 2) доступна практически любому заинтересован-

ному читателю, поскольку не предполагает никаких предвари-

тельных знаний ни в обл асти биологии, ни в области компью-

терных наук. В действительности, глава 1 представляет собой

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

ДНК, которые лежат в основе генетической инженерии вооб-

6 От редактора перевода

ще и ДНК-вычислений в частности. Глава 2 содержит подроб-

ное описание и весьма содержательное обсуждение эксперимен-

тальных и теоретических основ ДНК-вычислений.

Вторая часть книги (главы 3–11) носит более специальный

характер и адресована главным образом читателю, интересую-

щемуся таким разделом компьютерных наук, как теория фор-

мальных языков. Здесь собрано большое число но вых резуль-

татов, проясняющих возможности различных моделей ДНК-

вычислений, инспирированных реальными процессами, проис-

ходящими с молекулами ДНК в живых клетках. Эта часть

более математизирована, и, хотя авторы приводят в главе 3

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

теории формальных языков, для понимания последующих глав

необходима, как минимум, определенная логическая культура.

Коллектив, работавший над переводом, признателен авто-

рам книги, проявившим большое вн имани е к этому проекту

и активно сотрудничавшим с нами на протяжении последних

трех лет. Благодаря такому сотрудничеству удалось выявить и

устранить ряд неточностей, вкравшихся в оригинал. Как п ра-

вило, эти поправки никак не оговорены в тексте перевода; в

наибольшей степени они затрагивают главу 8.

Поскольку теория и прак тика ДНК-вычислений находятся

в стадии чрезвычайно быстрого роста, нам показалось целесо-

образным дополнить список ли тератур ы публикациями самых

последних лет, развивающими темы, представленные в книге.

Такие дополнения (никоим образом не претендующие на пол-

ноту) сделаны частью авторами, частью редактором перевода.

Отметим, что обширная и постоянно пополняемая аннотиро-

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

http://www.liacs.nl/home/pier/dna.html.

Глава 1 переведена И. С. Киселевой, ей же составлен глосса-

рий встречающихся в книге биохимических терминов. Главы 2

и 7–11 переведены О. Б. Финогеновой, главы 3–6 — Д. С. Ана-

ничевым. Верстка книги осуществлена А. А. Финогеновым.

М. В. Волков

Предисловие к русскому переводу

Перевод нашей книги на русский язык — большая честь и удо-

вольствие для нас, и мы приветст вуем наших новых читателей.

Мы хотим также поблагодарить профессора М. В. Волкова и

его сотрудников за работу над этим переводом.

За несколько лет, прошедших после выхода нашей книги,

интерес к молекулярным вычислениям и связанной с ними

деятельности постоянно рос. Наряду с теоретическими рабо-

тами развивала сь и лабораторная техника, приспособленная

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

ний. В Европе, Северной А мерике и Японии возникло много

новых исследовательских коллективов, работающих в области

молекулярных вычислений. Особенно активен Европейский

консорциум по молекулярным выч ислен иям

, который состоит

из групп, работающих в разных страна х и регулярно прово-

дящих о бщие встречи. Появился и японский перевод нашей

книги.

Несмотря на быстрое развитие области, мы полагаем, что

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

му обстоятельству, что ее материал составляют главным обра-

зом основы теории, на которых базируются дальнейшие иссле-

дования. Мы надеемся, что книга будет полезна и интересна

нашим новым читателям.

Георг Паун, Гжегорж Розенберг, Арто Саломаа

Таррагона, Лейден и Турку, август 2001

См. http://www.tucs.abo.fi/EMCC

Предисловие

Авторы весьма признательны многим своим друзьям и сотруд-

никам, вклад которых в изучение молекулярных вычислений

с позиций теории автоматов и формальных языков отражен в

настоящей книге. Их имена представлены в списке литературы,

и мы не будем повторять их здесь. Некоторые из этих коллег

прочитали предварительные версии ряда глав нашей книги и

предложили ряд модификаций, способствовавших ее улучше-

нию. За это мы благодарим Тома Хэда, Хэндрика Яна Хогебу-

ма, Винченцо Манка, Александру Матееску, Виктора Митра-

на, Андрея Пауна и Нике фан Фугта. О тдельной благодарно-

сти заслуживают наши друзья-биологи Ханс Кустерс и Паул

Савелкоул, просвещавшие нас в ходе многочисленных дискус-

сий. Ану Хейнимяки нарисовала иллюстрации для введения.

Мы с признательностью отмечаем квалифицированную под-

держку и оперативность издательства «Шпрингер» и, прежде

всего, доктора Ханса Вёсснера.

Георг Паун, Гжегорж Розенберг, Арто Саломаа

Лейден, июль 1998

Введение: суть молекулярных вычислений

От силикона к карбону, т. е. от кремния к углероду, от мик-

рочипов к молекулам ДНК — вот основная идея молекуляр-

ных вычислений. Органические молекулы могут перерабаты-

вать информацию, а значит, их можно испол ьзоват ь как аль-

тернативу цифровым микросхемам сегодняшних компьютеров.

У современных компьютерных технологий имеются очевид-

ные пределы миниатюризации. Уже давно осознано, что новый

решительный прорыв станет возможен только при переходе н а

молекулярный уровень. В результате могли бы появиться ком-

пьютеры, намного меньшие тех, которые производятся по ныне

существующим т ехнологи ям. Квантовые вычисления и моле-

кулярные вычисления — вот два недавних проявления этой об-

щей идеи. Наша книга посвящена молекулярным вычислениям.

Рис. 1. Современный компьютер.

Компьютеры имеют долгую историю. Механические уст-

ройства, предназначенные для упрощения вычислений, суще-

ствовали в течение многих веков. Наиболее ранним из тех

вычислительных инструментов, что сыграли важную роль в

развитии цивилизации, был абак, а сегодняшний электрон-

ный компьютер (рис. 1) завоевал настолько домин ирующие

позиции в современном обществе, что многое в нашей тепе-

решней жизни было бы просто невозможно без его помощи.

10 Введение

Рис. 2. Простейший ДНК-компьютер.

Рис. 3. Более сложный ДНК-компьютер.

Однако и у современных компьютеров есть свои « камни пре-

ткновения». Ввиду наличия многих непреодолимых для них

задач, представляется вероятным, что долгий путь развития

не закончится на компьютере, изображенном на рис. 1.

В будущем мы, возможно, увидим ДНК-компьютер. В ком-

пьютере, изображенном на рис. 2, пользователю приходится

выполнять все манипуляции с пробирками вручную.

Более продвинутая модель изображена на рис. 3. В ней

молекулярные вычисления комбинируются с электронными и

большинство операций с пробирками выполняется автомати-

чески, без вмешательства пользователя.

Чарльз Беббидж, знаменитый предтеча компьютерной эры,

в 1810–1820 гг. спроектировал автоматический калькулятор,

«Разностную машин у», а затем и более амбициозную «Ана-

литическую машину». Главным препятствием для реализации

этих проектов стало отсутствие аккуратно обработанных дета-