Вычисления с использованием ДНК ростислав Чутков, гр. 244




НазваниеВычисления с использованием ДНК ростислав Чутков, гр. 244
Дата конвертации30.01.2013
Размер445 b.
ТипДоклад


Вычисления с использованием ДНК

  • Ростислав Чутков, гр. 244

  • Александр Петров, гр. 244


План доклада

  • Введение

    • Что такое DNA Computing?
    • Перспективы ДНК-вычислений
  • Элементарные операции с ДНК

  • Эксперименты с ДНК

  • Модели и попытки формализации

  • Текущие результаты



Что такое DNA Computing?

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

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



Перспективы ДНК-вычислений

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

      • новые алгоритмы
      • возможность исследования процессов массового параллелизма
  • Новые методы синтеза веществ и объектов на молекулярном уровне.

  • Технологические преимущества; возможность создания «биологического нанокомпьютера».



«Биологический нанокомпьютер»

  • Будет способен хранить терабайты информации при объеме в несколько микрометров3.

  • Возможность внедрения в клетку живого организма.

  • Миллиарды операций в секунду при затратах энергии не более одной миллиардной доли ватта.

  • Низкая стоимость “материалов”, использующихся для создания и обслуживания компьютера.



План доклада

  • Введение

  • Элементарные операции с ДНК

    • Методы изменения цепи ДНК
    • Полимеразная цепная реакция
    • Способы “считывания” информации
  • Эксперименты с ДНК

  • Модели и попытки формализации

  • Текущие результаты



Молекула ДНК

  • Молекула ДНК – двойная лента, составленная из четырех оснований: А (аденин), Т (тимин), Г (гуанин), Ц (цитозин).

  • Диаметр двойной спирали ДНК – 2нм

  • Расстояние между соседними парами оснований – 0.34 нм

  • ДНК вирусов содержит ~1000 звеньев

  • ДНК млекопитающих – до 1010 звеньев





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

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



Дополнение цепочки ДНК

  • Дополнение цепочки ДНК происходит при воздействии на исходную молекулу ферментов – полимераз. Для работы полимеразы необходимо наличие:



Удлинение цепочки ДНК

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



Укорочение молекул ДНК

  • За укорочение и разрезание молекул ДНК отвечают ферменты – нуклеазы. Различают эндонуклеазы и экзонуклеазы. Экзонуклеазы осуществляют укорочение молекулы ДНК с концов:



Разрезание молекулы ДНК

  • Сайт-специфичные эндонуклеазы – рестриктазы – разрезают молекулу ДНК в определенном месте, которое закодировано последовательностью нуклеотидов – сайтом узнавания.



Сшивка молекул ДНК

  • Сшивка - операция, обратная операции разрезания, происходит под воздействием ферментов – лигаз.





Модификация

  • Модификация используется для того, чтобы рестриктазы не смогли “найти” определенный сайт и не разрушили молекулу.



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





Секвенирование

  • Секвенирование – это определение последовательности нуклеотидов в ДНК. Для секвенирования цепочек различной длины применяют различные методы. При помощи метода праймер-опосредованной прогулки удается на одном шаге секвенировать последовательность в 250-350 нуклеотидов.

  • После открытия рестриктаз стало возможным секвенировать длинные последовательности по частям.



Гель-электрофорез

  • Гель-электрофорез используется для разделения молекул ДНК по длине.



План доклада

  • Введение

  • Элементарные операции с ДНК

  • Эксперименты с ДНК

    • Эдлмана ― гамильтонов путь
    • Э. Шапиро ― конечный автомат
    • Э. Винфри ― ковер Серпинского
  • Модели и попытки формализации

  • Текущие результаты



Эксперимент Эдлмана

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

  • Обозначил технику, которая, в дальнейшем послужила основой для создания модели параллельной фильтрации.



Алгоритм Эдлмана

  • Вход. Ориентированный граф G с n вершинами, среди которых выделены 2 вершины – vin и vout

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

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

  • Шаг 3. Отбросить все пути, которые не содержат точно n вершин

  • Шаг 4. Для каждой из n вершин v отбросить пути, которые не содержат v

  • Выход. Да, если есть хоть один путь, нет – в противном случае.



Кодирование объектов

  • Каждая вершина графа кодируется последовательностью 20 нуклеотидов.

  • Для ребер код комплементарен конкатенации вторых 10 нуклеотидов вершины-источника и первых 10 нуклеотидов вершины-назначения.



Эксперимент Шапиро

  • «Исходные данные», и «программа» могут описываться молекулами ДНК.

  • Первый шаг на пути к созданию «биологического нанокомпьютера».



Конечный автомат Шапиро

  • В опыте Э. Шапиро был реализован конечный автомат, который может находиться в двух состояниях – S0 и S1 и отвечает на вопрос – четное или нечетное количество символов а содержится во входной последовательности символов a и b.



Представление состояний



Остальные переходы, терминатор



Схема опыта (1/3)



Схема опыта (2/3)



Схема опыта (3/3)



Эксперимент Винфри

  • Локальные правила определяют глобальную структуру. Под вычислением здесь понимается создание этой структуры.

  • Возможно использовать локальные правила для синтеза различных поверхностей при помощи ДНК.



Построение ковра Серпинского

  • В опыте используются 4 плитки, которые соответствуют правилам таблицы истинности для оператора XOR.

  • Начальный слой укладывается из плиток типа Т-00. Затем плитки укладываются по направлению снизу вверх.



Кодирование плиток и результат



План доклада

  • Введение

  • Элементарные операции с ДНК

  • Эксперименты с ДНК

  • Модели и попытки формализации

    • Модель параллельной фильтрации
    • Плиточная модель
    • Операции в терминах теории формальных языков
  • Текущие результаты



Parallel Filtering Model

  • Соответствует прямому перебору в классической парадигме вычислений.

  • Реализуется в три стадии:

    • Генерация всех вариантов.
    • Параллельный отсев (в несколько стадий) всех неудовлетворительных вариантов.
    • Расшифровка решения.


Определения (1/3)

  • Пробирка – это мультимножество слов (конечных строк) над алфавитом {А, Ц, Г, Т}.

  • Слить. Образовать объединение (в смысле мультимножеств) двух заданных пробирок.

  • Размножить. Изготовить две копии данной пробирки.

  • Обнаружить. Возвратить значение истина, если данная пробирка N содержит по крайней мере одну цепочку ДНК, иначе - ложь.



Определения (2/3)

  • Разделить (или Извлечь). По данным пробирке N и слову w над алфавитом {А, Ц, Г, Т} изготовить две пробирки +(N,w) и –(N,w) такие, что +(N,w) состоит из всех цепочек в N, содержащих w в качестве (последовательной) подстроки, а –(N,w) состоит из всех цепочек в N, которые не содержат w в качестве подстроки.

  • Разделить по длине. По данным пробирке N и целому числу n, изготовить пробирку L (N, ≤n), состоящую из всех цепочек из N длины не больше n.



Определения+ (3/3)

  • Разделить по префиксу (суффиксу). По данным пробирке N и слову w, изготовить пробирку B (N,w) (соответственно E (N,w)), состоящую из всех цепочек в N, начало (соответственно конец) которых совпадает со словом w.



Алгоритм Эдлмана

  • ввести (N)

  • N ← B (N, s0) // выделить все цепочки, которые начинаются с вершины s0

  • N ← E (N, s6) // выделить все цепочки, которые кончаются на s6

  • N ← L (N, ≤140) // выделить все цепочки не длиннее 140

  • Для i от 1 до 5 выполнить N ← + (N,si) // для каждой из вершин от s1 до s5 выделить только те цепочки, которые содержат данную вершину

  • Result = обнаружить (N) // true если осталась хоть одна цепочка, false – в противном случае.



Плиточная модель

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

  • Локальные правила взаимодействия клеток будут определяться их формой.



Теоретический базис

  • Все работы, относящиеся к проблеме покрытия (Ванга, Бергера, Робинсона, Пенроуза).

  • Работы Э. Винфри, направленные на получение нужных структур на практике.

  • Работы по теории клеточных автоматов с «квадратными клетками».



План доклада

  • Введение

  • Элементарные операции с ДНК

  • Эксперименты с ДНК

  • Модели и попытки формализации

  • Текущие результаты

    • Решенные задачи
    • Ограничения в экспериментах
    • Программные средства


Задачи, решенные теоретически



[re] Эксперимент Эдлмана

  • В ДНК-компьютере Эдлмана оптимальный маршрут обхода отыскивался всего для 7 вершин графа… … за одну неделю!

  • Нахождение обхода 200 вершин потребовало бы количество ДНК, большее… … веса всей нашей планеты!



[re] Эксперимент Шапиро

  • Автомат Шапиро не сравним по сложности с любым сколь угодно полезным автоматом.

  • Автомат не может ответить более чем на 756 вопросов о четности количества символов a.

  • Модель автомата детерминирована, но ведет себя он как вероятностный (из-за естественных ошибок) => Необходимость создания дополнительных контролирующих схем / молекул.



Программные средства: Namot

  • Nucleic Acid MOdeling Tool

  • Графическое средство работы с молекулярными структурами.

  • Позволяет составлять структуры из атомов, задавать связи в трехмерном пространстве, строить последовательности молекулярных операций.



Программные средства: Xgrow

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



Открытые теоретические вопросы

  • Какой класс задач поддается решению при помощи ДНК?

  • Какие алгоритмы можно построить по известной конечной структуре, и как это делать?

  • Как использовать локальное взаимодействия для получения полезных глобальных структур?

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



Подведем итоги

  • Вычисления на ДНК – новая развивающаяся область науки на границе молекулярной биологии и Computer Science.

  • Главные преимущества вычислений на ДНК – высочайшая скорость и неограниченный параллелизм.

  • Поставлено несколько экспериментов, доказывающих оправданность теоретических предположений.

  • Текущие практические результаты пока оставляют желать лучшего, теория все еще развита слабо.



План доклада

  • Введение

  • Элементарные операции с ДНК

  • Эксперименты с ДНК

  • Модели и попытки формализации

  • Текущие результаты



Использованный материал

  • Малинецкий Г.Г., Науменко С.А. Вычисления на ДНК.

  • Adleman L.M., Molecular Computation of Solutions to Combinatorial Problems .

  • Istvan Katsanyi. Molecular Computing Solutions of some Classical Problems.

  • Robin Varghese. Implementing models of DNA computing.



Похожие:

Вычисления с использованием ДНК ростислав Чутков, гр. 244 iconЛекция молекулярно-генетический и клеточный уровни организации жизни. Генетический материал и его характеристики. Репликация ДНК.
Олекулярный уровень) структура биополимера; репликация ДНК как матричный процесс: инициация, элонгация, терминация. Репликация ДНК...
Вычисления с использованием ДНК ростислав Чутков, гр. 244 iconХромосома бактерий ДНК в виде двойной спирали
В клетках не бывает чистой ДНК. На всех этапах клеточного цикла молекулы ДНК связаны с белками. При этом ДНК (190 см) упаковывается...
Вычисления с использованием ДНК ростислав Чутков, гр. 244 iconМодуль 7: mdx вычисления на кубе и в измерениях Вычисления: mdx-сценарии
Все вычисления, выполняемые на основе куба или измерения, хранятся в одном месте: mdx-сценарии (mdx-script)
Вычисления с использованием ДНК ростислав Чутков, гр. 244 iconПравилам Чаргаффа
Первичную структуру ДНК составляет последовательность чередования нуклеотидов в полинуклеотидной цепи. Днк, выделенные из разных...
Вычисления с использованием ДНК ростислав Чутков, гр. 244 iconИспользованием мутаций, т е. селекцией, люди начали заниматься задолго до Дарвина и Менделя
Были разработаны методы генной инженерии отрасли молекулярной биологии конструирование in vitro (вне живого организма) новых функционально...
Вычисления с использованием ДНК ростислав Чутков, гр. 244 iconИстория развития и многообразие калькуляторов Содержание
России для автоматизации вычислений были счеты. Этот "народный калькулятор" продержался на рабочих местах кассирш в магазинах вплоть...
Вычисления с использованием ДНК ростислав Чутков, гр. 244 iconДнк-овые и рнк-овые вирусы
Поэтому бактериофаги идут «на хитрость». Зацепившись особыми нитями за поверхность бактерии, фаг «проедает» особым белком ее оболочку...
Вычисления с использованием ДНК ростислав Чутков, гр. 244 iconСтруктура нуклеиновых кислот и атф
К является носителем кода, который управляет химизмом всего живого, а двойная спираль молекулы ДНК стала одним из самых известных...
Вычисления с использованием ДНК ростислав Чутков, гр. 244 iconГенетически модифицированные организмы- аргументы за и против Занятие курса «Тайны живой природы»
Ученые Френсис Крик и Джеймс Уотсон разработали модель структуры ДНК и опубликовали рисунок ее двойной спирали в журнале "Natur"....
Вычисления с использованием ДНК ростислав Чутков, гр. 244 iconЛекции дезоксирибонуклеиновая кислота (днк) носитель генетической информации
Дезоксирибонуклеиновая кислота (днк) носитель генетической информации 1868 г. Иоганн Мишер
Разместите кнопку на своём сайте:
hnu.docdat.com


База данных защищена авторским правом ©hnu.docdat.com 2012
обратиться к администрации
hnu.docdat.com
Главная страница