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

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Государственное образовательное учреждение

высшего профессионального образования

«Уральский государственный университет им. А. М. Горького»

Математико-механический факультет

Кафедра алгебры и дискретной математики

Методические указания к курсу

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

Авторы-составители

доктор физ.-мат. наук,

профессор

Волков М.В.

Прибавкина Е.В.

Руководитель ИОНЦ «Физика

в биологии и медицине»

____________ Бабушкин А.Н.

(подпись)
__________

(дата)

Екатеринбург

2007
Курс «Основы молекулярных вычислений» читается на математико-механическом факультете в 6-м семестре и является курсом по выбору, обязательным для студентов, специализирующихся по профилю «Математическая биология и биоинформатика».

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

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

Курс разработан в рамках инновационного проекта Уральского государственного университета, направление «Физика в биологи и медицине».

СОДЕРЖАНИЕ

Введение 5

1. Научное содержание курса и его значение 5

2. Место курса в системе подготовки студентов математико-механического факультета 5

3. Структура курса 6

1. Строение молекулы ДНК и ее измеряемые характеристики 7

2. Операции над ДНК. 7

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

3. Опыт Эдлмана. 9

4. Модели и алгоритмы. 9

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

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

6. Сборка генов у ресничных. 13

Вопросы к зачету по курсу «Основы молекулярных вычислений»: 15

Рекомендуемая литература (основная) 17

Рекомендуемая литература (дополнительная) 17

Введение

1. Научное содержание курса и его значение

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

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

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

2. Место курса в системе подготовки студентов математико-механического факультета

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

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

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

3. Структура курса

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

Строение и операции над ДНК.

1. Строение молекулы ДНК и ее измеряемые характеристики

Лекции 1-2.

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

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

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

Строение ДНК. Дезоксирибонуклеотиды. Азотистые основания. Строение РНК. Способы соединения нуклеотидов. Комплементарность Уотсона-Крика. Измерение длины молекулы ДНК. Гель-электрофорез. «Выуживание» из раствора с молекулами ДНК известных молекул.

Литература: [3] гл. 1, стр. 15-26.

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

Лекции 3-5.

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

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

Разделение и соединение цепочек. Гибридизация. Использование ферментов при манипуляциях с ДНК. Удлинение, укорочение ДНК. Разрезание, сшивка ДНК. Модификация нуклеотидов. Размножение ДНК – полимеразная цепная реакция. Секвенирование.

Литература: [3], гл. 1, стр. 26-53.

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

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

3. Опыт Эдлмана.

Лекция 6.

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

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

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

Литература: [3] гл. 2, стр. 53-63, [4] гл. 5, стр. 112-117.

4. Модели и алгоритмы.

Лекции 7-12.

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

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

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

Модель параллельной фильтрации. Использование феномена массового параллелизма цепочек ДНК.

Алгоритм Липтона решения задачи выполнимости пропозициональных формул. Интерпретация входных данных задачи в терминах цепочек ДНК. Описание используемых в алгоритме Липтона операций.

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

Стикерная модель. Стикеры. Запоминающие комплексы. Операции с запоминающими комплексами. Использование стикерной модели при решении задачи о минимальном покрытии. Взлом криптосистемы DES с помощью стикерной модели.

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

Литература: [3] гл. 2, стр. 63-85, [4] гл. 3, стр. 46-60; гл. 5, стр. 110-145.

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

Лекции 13-14.

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

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

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

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

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

6. Сборка генов у ресничных.

Лекции 15-18.

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

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

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

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

Литература: [2], [4] гл. 6, стр. 150-156, [5].

Вопросы к зачету по курсу «Основы молекулярных вычислений»:

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