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

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

Предметный указатель

1-сплетение, 286

2-сплетение, 286

AFL, 107

полное, 107

Data Encryption Standard, 73,

82, 95

H-система, 313

k-простая, 332

взаимодействующая рас-

пределенная, 427

двухуровневая распреде-

ленная, 442

разделенная, 445

изменяющаяся во време-

ни, 451

простая, 323

расширенная, 313

программируемая, 358

развертывающаяся, 358

с глобальной мишенью,

351

с запрещающими кон-

текстами, 346

с локально развертыва-

ющимися правилами,

362

с локальными мишеня-

ми, 351

с мультимножествами,

380

с отображением годно-

сти, 355

с разрешающими кон-

текстами, 336

упорядоченная, 348

циклическая, 405

с самосплетением, 493

универсальная, 317, 390

H-схема, 288

рефлексивная, 402

с кластерами, 462

NP-полная задача, 55, 64

аденин (А), 16

алфавит, 104

аналог нуклеотида, 47

анти-AFL, 107, 493

библиотека, 77

блочная перетасовка, 154

бромистый этидий, 24

ВУ-система, 243

ограниченная, 259

универсальная, 264

вектор Париха, 104

вес (H-системы), 396

взаимодействие

по запросу, 129

по приказу, 129

водородная связь, 18

вставка, 242, 362

вычислительная полнота, 144

гель

агарозный, 25

полиакриламидный, 25

гибридизация, 27, 39

гомополимерный хвост, 41

грамматика

кондициональная, 126

матричная, 124

522 Предметный указатель

обобщенная полуконди-

циональная, 125

полукондициональная,

126

программируемая, 124

простая матричная, 126

слабо кондициональная,

126

случайно контекстная,

126

типа 0, 110

универсальная, 148

типа 1, 110

типа 2, 110

типа 3, 110

упорядоченная, 125

Хомского, 108

контекстная, 109

контекстно-свободная,

109

леволинейная, 110

линейная, 109

минимальная линей-

ная, 111

монотонная, 109

неукорачивающая, 109

праволинейная, 110

приведенная контекстно-

свободная , 110

регулярная, 110

чистая, 108

грамматическая система, 127,

414

кооперирующаяся распре-

деленная, 127, 450

параллельная взаимодей-

ствующая, 127, 414

сплетающая, 415

грамматическая схема, 148

гуанин (Г), 16

ДНК, см. дезоксирибонуклеи-

новая кислота, 15

двойная спираль, 18

дезоксирибоза, 15

дезоксирибонуклеиновая кис-

лота, 15

денатурация, 27

дескриптивная сложность, 116

дидезоксиферментный метод,

домино, 159

задача

о выполнимости, 63

о гамильтоновом пути, 54

о минимальном покры-

тии, 78

запоминающая цепочка, 73

запоминающий комплекс, 74

зеркальное отражение, 106

зонд, 25

иерархия Хомского, 110, 293

индекс, 117

интерпретация, 63

итерация Клини, 105

кодирование, 105

кольцевая строка, 398

комплементарность Уотсона–

Крика, 18, 89, 194

конечный автомат, 118, 132

двухголовочный, 201

детерминированный, 118

Уотсона–Крика, 195

1-ограниченный, 199

без состояний, 198

всефинальный, 198

двусторонний, 223

инициальный без состо-

яний, 216

Предметный указатель 523

префиксный, 224

простой, 199

реверсивный, 219

универсальный, 152, 231,

316

конъюнктивная нормальная

форма, 69

левая производная, 106

левое частное, 106

лемма о накачке

для контекстно-свобод-

ных языков, 113

для линейных языков, 113

для регулярных языков,

113

лемма о сохранении регуляр-

ности, 494

для H-схем, 298

лента Уотсона–Крика, 195

лигаза, 37

линейно ограниченный авто-

мат, 123

липкие концы, 37

магазинный автомат, 120

матрица, 28

машина Тьюринга, 85, 121, 132

генетическая, 88

детерминированная, 122

универсальная, 143

мгновенное описание машины

Тьюринга, 122

мера дескриптивной сложно-

сти, 116, 319

нетривиальная, 116

связная, 116

метилаза, 41

метод Сэнгера, см. дидезокси-

ферментный метод,

метод фильтрации, 26

множество длин, 104

множество совпадений, 136

молекула-мишень, 25

мономер, 15

морфизм, 105

нестирающий, 105

обратный, 106

ограниченный, 106

Уотсона–Крика, 57

мультимножество, 61, 379

мусор в ДНК, 265

направление (цепочки ДНК),

насечка, 38

нормальная форма, 111

Гефферта, 112

Куроды, 112

Пенттонена, 112

Хомского, 111

сильная, 111

нуклеаза, 30

нуклеотид, 16

ОПМ, см. обобщенная после-

довательная маши на,

118

ОПМ-отображение, 92

область Уотсона–Крика, 157

обобщенная последовательная

машина, 118

λ-свободная, 118

детерминированная, 118

Уотсона–Крика, 214

олигонуклеотид, 30

операция

включить, 77

обнаружить, 61, 98

очистить, 77

524 Предметный указатель

разделить, 61, 76, 98

по длине, 62, 98

по префиксу (суффик-

су), 62

размножить, 61, 98

слить, 61, 76, 98

опыт Эдлмана, 54

основание (часть ДНК), 15

основная лемма об универ-

сальности (для H-

схем), 304

отжиг, 27, 98

частичный, 241

ПЦР, см. полимеразная цеп-

ная реакция, 44

переписывающая система, 108

перетасовка, 90, 106

пиримидин, 16

плавление, 98

погрешность, 95

подстановка, 105

подстрока, 104

полимер, 15

полимераза, 27

полимеразная цепная реак-

ция, 44, 379

полу-AFL, 107

последовательный преобразо-

ватель, 118

правая производная, 106

правило сплетения, 287

правое частное, 106

праймер, 28

префикс, 104

приписывание, 104

проекция, 105

произведение, 105

пурин, 16

РНК, см. рибонуклеиновая

кислота, 17

радиус (H-схемы), 296

регулируемое перепи сывание ,

124

редактирование РНК, 242

ренатурация, 27

рестриктаза, 33

рибоза, 17

рибонуклеиновая кислота, 17

сайт узнавания, 34

сахар (часть ДНК), 15

секвенирование, 47

сентенциальная форма, 109

синтаксический моноид, 113

система Линденмайера, 94,

114

детерминированная, 115

размножающая, 115

расширенная, 115

табличная, 115

система Поста, 493

система репликаций, 473

однородная, 474

простая, 474

система со склейкой, 162

односторонняя, 164

простая, 164

простая регулярная, 186

регулярная, 164

с ограниченной задерж-

кой, 163

склейка, 160

ограниченная, 161

слабое кодирование, 105

сплетение, 286, 287

двойное, 374

итеративное, 297

неитеративное, 287

Предметный указатель 525

стикер, 73

стикерная модель, 73

суффикс, 104

сшивка, 37

прямых концов, 39

тезис Черча–Тьюринга, 85, 92,

132

теорема

Майхилла–Нероуда, 113

Париха, 113

Хомского–Шютценберже,

114, 140

тимин (Т), 16

точечная мутация, 242, 362

трио, 107

удаление, 362

удаления, 242

универсальность, 144

урацил (У), 17

фермент, 27

модифицирующий, 41

фосфат (часть ДНК), 15

фосфодиэфирная связь, 18

функция роста, 116, 491

цитозин (Ц), 16

экзонуклеаза, 30

электрофорез, 22, 98

эндонуклеаза

рестрикционная, 33

язык

Дика, 114

перетасованных копий,

89, 139, 167, 208

перетасованных отраже-

ний, 141

перетасованных полуко-

пий, 142

перетасованных полуот-

ражений, 143

полулинейный, 105, 253

регулярный, 106

рекурсивно перечисли-

мый, 110

строго локально тестиру-

емый, 329

Оглавление

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

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

Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

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

1 Как устроена ДНК и как с ней работают 15

1.1 Строение ДНК . . . . . . . . . . . . . . . . . . . . . . . . 15

1.2 Операции над ДНК . . . . . . . . . . . . . . . . . . . . . 26

1.3 Секвенирование . . . . . . . . . . . . . . . . . . . . . . . 47

1.4 Комментарии к библиографии . . . . . . . . . . . . . . . 51

2 Начала молекулярных вычислений 53

2.1 Опыт Эд лм ана . . . . . . . . . . . . . . . . . . . . . . . . 53

2.2 Как решить задачу о выполнимости и взломать крип-

тосистему DES? . . . . . . . . . . . . . . . . . . . . . . . 63

2.3 Переосмысление парадигмы вычислений . . . . . . . . . 85

2.4 ДНК-вычисления:надежды и предостережения . . . . . 94

2.5 Комментарии к библиографии . . . . . . . . . . . . . . . 100

3 Введение в теорию формальных языков 103

3.1 Основные понятия: грамматики, автоматы, граммати-

ческие системы . . . . . . . . . . . . . . . . . . . . . . . 103

3.2 Характеризации рекурсивно перечислимых языков . . 132

3.3 Универсальные машины Тьюринга и грамматик и

типа 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

3.4 Комментарии к библиографии . . . . . . . . . . . . . . . 155

4 Системы со склейкой 156

4.1 Операция склеивания . . . . . . . . . . . . . . . . . . . . 156

4.2 Системы со склейкой: классификация . . . . . . . . . . 162

4.3 Выразительная сила систем со склейкой . . . . . . . . . 167

4.4 Представления регулярных и линейных языков . . . . 177

4.5 Характеризации рекурсивно перечислимых языков . . 181

4.6 Дальнейшие результаты о регулярных системах . . . . 185

4.7 Комментарии к библиографии . . . . . . . . . . . . . . . 193

Оглавление 527

5 Автоматы Уотсона–Крика 194

5.1 Конечные автоматы Уотсона–Крика . . . . . . . . . . . 195

5.2 Соотношения между WK-семействами . . . . . . . . . . 200

5.3 Характеризации рекурсивно перечислимых языков . . 208

5.4 Конечные преобразователи Уотсона–Крика . . . . . . . 213

5.5 Дальнейшие варианты конечных автоматов Уотсона–

Крика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216

5.6 Автоматы Уотсона–Крика с памятью Уотсона–Крика . 223

5.7 Универсальные автоматы Уотсона–Крика . . . . . . . . 231

5.8 Комментарии к библиографии . . . . . . . . . . . . . . . 240

6 Системы вставки и удаления 241

6.1 Вставка и удалени е в контексте ДНК . . . . . . . . . . 241

6.2 Характеризации рекурсивно перечислимых языков . . 243

6.3 Односимвольные системы вставки и удаления . . . . . 258

6.4 Использование только вставки . . . . . . . . . . . . . . 266

6.5 Комментарии к библиографии . . . . . . . . . . . . . . . 280

7 Системы сплетения 281

7.1 От ре комбинации ДНК к операции сплетения . . . . . 282

7.2 Неитеративное сплетение как операция над языками . 286

7.3 Итеративное сплетение как операция над языками . . . 297

7.4 Выразительная сила расширенных H-систем . . . . . . 312

7.5 Простые H-системы . . . . . . . . . . . . . . . . . . . . . 323

7.6 Комментарии к библиографии . . . . . . . . . . . . . . . 330

8 Универсальность и конечные H-системы 333

8.1 От 1-сп ле тени я к 2-сплетению . . . . . . . . . . . . . . 333

8.2 Разрешающие и запрещающие контексты . . . . . . . . 336

8.3 Языки-мишени . . . . . . . . . . . . . . . . . . . . . . . . 350

8.4 Программируемые и развертывающиеся с исте мы . . . . 357

8.5 H-системы, основанные на двойном сплетении . . . . . 373

8.6 Мультимножества . . . . . . . . . . . . . . . . . . . . . . 379

8.7 Результаты об универсальности . . . . . . . . . . . . . 389

8.8 Комментарии к библиографии . . . . . . . . . . . . . . . 396

9 Сплетение циклических строк 398

9.1 Варианты операции сплетения для циклических строк 398

9.2 Еще один вариант и его возможности . . . . . . . . . . 403

9.3 Комментарии к библиографии . . . . . . . . . . . . . . . 413

528 Оглавление

10 Распределенные H-системы 414

10.1 Сплетающие грамматические системы . . . . . . . . . . 414

10.2 Взаимодействующие распределенные H-системы . . . . 427

10.3 Двухуровневые распределенные H-системы . . . . . . . 441

10.4 Распределенные H-системы, изменяющиеся во времени 450

10.5 Классы вычислительно полных H-систем . . . . . . . . 459

10.6 Комментарии к библиографии . . . . . . . . . . . . . . . 459

11 И вновь о сплетении 461

11.1 Ограниченное сплетение. Неитеративный случай . . . . 461

11.2 Системы репликаций . . . . . . . . . . . . . . . . . . . . 472

11.3 Комментарии к библиографии . . . . . . . . . . . . . . . 493

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

Глоссарий биохимических терминов 518

Предметный указатель 521

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

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

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

Зав. редакцией академик В. И. Арнольд

Зам. зав. редакцией А. С. Попов

Ведущий редактор М. В. Волков

Художник М. М. Иванов

Технический редактор Е. В. Денюкова

Оригинал-макет подготовлен А. А. Финогеновым в пакете

X 2

с использованием кирилических шрифтов семейства LH

Лицензия ЛР 010174 от 20.05.97 г.

Подписано к печати . Формат 60 × 90 1/16

Печать офсетная. Объем 16, 5 бум. л. Усл.-печ. л. 33.

Уч.-изд. л. 00. Изд. 1/9824. Тираж 2000 экз. Заказ

Издательство «Мир»

Министерство РФ по делам печати,

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

107996, ГСП, Москва, 1-й Рижский пер., 2.

Диапозитивы изготовлены

Отпечатано с готовых диапозитивов