Элементы теории формальных языков и автоматов

Лекции 21-24.

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

Краткое содержание раздела:

Понятие формального языка. Цепочки ДНК как языки над 4-буквенным алфавитом. Операции над языками. Понятие конечного автомата. Детерминированные и недетерминированные автоматы. Распознавание языков автоматами. Регулярные языки. Представление регулярных языков КДА (теорема Клини).

Машина Тьюринга как модель алгоритма. Вычисление на машине Тьюринга. Вычислимые функции. Тезис Черча. Рекурсивно-перечислимые и рекурсивные языки.

Понятие формальной грамматики. Задание языков с помощью грамматик. Виды грамматик. Контекстно-свободные языки. Контекстно-зависимые языки. Иерархия Хомского. Примеры.

Литература: [14] гл. 1-3, 5, [9].

Задачи: [3] №№ 10.1.1 (б, д), 10.1.2, 10.1.9 (а, в), 10.1.10 (а), 10.2.3 (а), 10.2.4 (в).

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

Основы молекулярных вычислений.

Лекции 25-30.

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

Краткое содержание раздела:

Обсуждение возможности: применение двух основных феноменов – массового параллелизма цепочек ДНК и комплементарности Уотсона-Крика. Строение ДНК. Дезоксирибонуклеотиды. Азотистые основания. Строение РНК. Способы соединения нуклеотидов. Комплементарность Уотсона-Крика. Измеряемые характеристики. Измерение длины молекулы ДНК. «Выуживание» из раствора с молекулами ДНК известных молекул. Операции над ДНК: Разделение и соединение цепочек ДНК. Использование ферментов для проведения операций с молекулами ДНК. Удлинение ДНК. Укорочение ДНК. Разрезание ДНК. Сшивка ДНК. Операции над ДНК: Модификация нуклеотидов ДНК; размножение ДНК, полимеразная цепная реакция. Секвенирование. Эксперименты по решению сложных вычислительных задач: опыт Эдлмана решения задачи о поиске гамильтонова пути в графе; алгоритм Липтона решения задачи выполнимости пропозициональных формул. Стикерная модель молекулярных вычислений. Основанный на этой модели алгоритм взлома криптосистемы DES. Определение стикера. Операции с ДНК, используемые в данной модели.

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

Литература: [12], гл. 1-2, [17] гл. 1, 5.

 

 

Применение молекулярных компьютеров в медицине.

Лекция 31.

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

Краткое содержание раздела:

Компьютеры из ДНК. От моделей к молекулам. Создание молекулярного конечного автомата. Применение молекулярных компьютеров в медицине.

Литература: [4].

 

Вычисления в живых клетках.

Лекция 32.

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

Краткое содержание раздела:

Вычисления в живых клетках. Биологическая сторона процесса сборки генов. Структура генов. Математические модели сборки генов у ресничных: внутримолекулярная и межмолекулярная модели.

Литература: [8], [18].