Без темы
<<  Вычисления по формулам Гадюка обыкновенная и не очень  >>
Вычисления с использованием ДНК
Вычисления с использованием ДНК
План доклада
План доклада
Что такое DNA Computing
Что такое DNA Computing
Перспективы ДНК-вычислений
Перспективы ДНК-вычислений
Биологический нанокомпьютер
Биологический нанокомпьютер
План доклада
План доклада
Молекула ДНК
Молекула ДНК
15
15
Ренатурация, денатурация
Ренатурация, денатурация
Дополнение цепочки ДНК
Дополнение цепочки ДНК
Удлинение цепочки ДНК
Удлинение цепочки ДНК
Укорочение молекул ДНК
Укорочение молекул ДНК
Разрезание молекулы ДНК
Разрезание молекулы ДНК
Сшивка молекул ДНК
Сшивка молекул ДНК
15
15
Модификация
Модификация
Полимеразная цепная реакция
Полимеразная цепная реакция
15
15
Секвенирование
Секвенирование
Гель-электрофорез
Гель-электрофорез
План доклада
План доклада
Эксперимент Эдлмана
Эксперимент Эдлмана
Алгоритм Эдлмана
Алгоритм Эдлмана
Кодирование объектов
Кодирование объектов
Эксперимент Шапиро
Эксперимент Шапиро
Конечный автомат Шапиро
Конечный автомат Шапиро
Представление состояний
Представление состояний
Остальные переходы, терминатор
Остальные переходы, терминатор
Схема опыта (1/3)
Схема опыта (1/3)
Схема опыта (2/3)
Схема опыта (2/3)
Схема опыта (3/3)
Схема опыта (3/3)
Эксперимент Винфри
Эксперимент Винфри
Построение ковра Серпинского
Построение ковра Серпинского
Кодирование плиток и результат
Кодирование плиток и результат
План доклада
План доклада
Parallel Filtering Model
Parallel Filtering Model
Определения (1/3)
Определения (1/3)
Определения (2/3)
Определения (2/3)
Определения+ (3/3)
Определения+ (3/3)
Алгоритм Эдлмана
Алгоритм Эдлмана
Плиточная модель
Плиточная модель
Теоретический базис
Теоретический базис
План доклада
План доклада
Задачи, решенные теоретически
Задачи, решенные теоретически
[re] Эксперимент Эдлмана
[re] Эксперимент Эдлмана
[re] Эксперимент Шапиро
[re] Эксперимент Шапиро
Программные средства: Namot
Программные средства: Namot
Программные средства: Xgrow
Программные средства: Xgrow
Открытые теоретические вопросы
Открытые теоретические вопросы
Подведем итоги
Подведем итоги
Вопросы
Вопросы
Использованный материал
Использованный материал

Презентация: «Вычисления с использованием ДНК». Автор: Sic. Файл: «Вычисления с использованием ДНК.ppt». Размер zip-архива: 1154 КБ.

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

содержание презентации «Вычисления с использованием ДНК.ppt»
СлайдТекст
1 Вычисления с использованием ДНК

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

Ростислав Чутков, гр. 244 Александр Петров, гр. 244

2 План доклада

План доклада

Введение Что такое DNA Computing? Перспективы ДНК-вычислений Элементарные операции с ДНК Эксперименты с ДНК Модели и попытки формализации Текущие результаты

15.10.2006

3 Что такое DNA Computing

Что такое DNA Computing

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

15.10.2006

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

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

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

15.10.2006

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

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

Будет способен хранить терабайты информации при объеме в несколько микрометров3. Возможность внедрения в клетку живого организма. Миллиарды операций в секунду при затратах энергии не более одной миллиардной доли ватта. Низкая стоимость “материалов”, использующихся для создания и обслуживания компьютера.

15.10.2006

6 План доклада

План доклада

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

15.10.2006

7 Молекула ДНК

Молекула ДНК

Молекула ДНК – двойная лента, составленная из четырех оснований: А (аденин), Т (тимин), Г (гуанин), Ц (цитозин). Диаметр двойной спирали ДНК – 2нм Расстояние между соседними парами оснований – 0.34 нм ДНК вирусов содержит ~1000 звеньев ДНК млекопитающих – до 1010 звеньев

Молекула ДНК под электронным микроскопом

15.10.2006

8 15

15

10.2006

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

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

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

Ренатурация – это соединение двух одинарных цепочек ДНК за счет связывания комплементарных оснований.

Денатурация – разъединение двойной цепочки и получение двух одинарных цепочек.

15.10.2006

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

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

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

Одноцепочечной матрицы, которая определяет добавляемую цепочку по принципу комплементарности Праймера (двухцепочечный участок) Свободных нуклеотидов в растворе

15.10.2006

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

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

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

Таким образом можно конструировать произвольную цепь ДНК ?

15.10.2006

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

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

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

Экзонуклеазы могут укорачивать одноцепочечные молекулы и двухцепочечные, с одного конца или с обоих.

15.10.2006

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

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

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

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

Эндонуклеазы разрушают внутренние фосфодиэфирные связи в молекуле ДНК.

15.10.2006

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

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

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

“Липкие концы” соединяются вместе с образованием водородных связей. Лигазы служат для того, чтобы закрыть насечки, т.е. способствовать образованию в нужных местах фосфодиэфирных связей.

Фосфодиэфирные связи много прочнее, чем водородные

15.10.2006

15 15

15

10.2006

16 Модификация

Модификация

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

Существует несколько типов модифицирующих ферментов – метилазы, фосфатазы и т.д.

Метилаза имеет тот же сайт узнавания, что и соответствующая рестриктаза. При нахождении нужной молекулы, метилаза модифицирует участок с сайтом так, что рестриктаза уже не сможет идентифицировать эту молекулу.

15.10.2006

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

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

(а) Нагреваем до температуры кипения воды (б) Охлаждаем до 55o C (в) Снова нагреваем до 70-72o C

Возможно применение ферментов, сдвигающих температурные границы.

15.10.2006

Ие

18 15

15

10.2006

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

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

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

15.10.2006

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

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

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

Если молекулы поместить в гель и приложить постоянное электрическое поле, то они будут двигаться по направлению к аноду, причем молекулы меньшей длины будут двигаться быстрее.

Молекулы ДНК имеют отрицательный заряд Иногда применяют маркировочные молекулы

15.10.2006

21 План доклада

План доклада

Введение Элементарные операции с ДНК Эксперименты с ДНК Эдлмана ? гамильтонов путь Э. Шапиро ? конечный автомат Э. Винфри ? ковер Серпинского Модели и попытки формализации Текущие результаты

15.10.2006

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

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

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

>> Построив эффективную реализацию метода Эдлмана, мы научимся решать NP-полные задачи за полиномиальное время.

Leonard Adleman

15.10.2006

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

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

Вход. Ориентированный граф G с n вершинами, среди которых выделены 2 вершины – vin и vout Шаг 1. Породить большое количество случайных путей в G Шаг 2. Отбросить все пути, которые не начинаются с vin или не заканчиваются на vout Шаг 3. Отбросить все пути, которые не содержат точно n вершин Шаг 4. Для каждой из n вершин v отбросить пути, которые не содержат v Выход. Да, если есть хоть один путь, нет – в противном случае.

15.10.2006

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

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

Каждая вершина графа кодируется последовательностью 20 нуклеотидов. Для ребер код комплементарен конкатенации вторых 10 нуклеотидов вершины-источника и первых 10 нуклеотидов вершины-назначения.

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

15.10.2006

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

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

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

>> Научившись создавать конечные автоматы на ДНК, мы перенесем все классические решения задач на новую молекулярно-электронную архитектуру

Ehud Shapiro

15.10.2006

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

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

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

S0, a ? S1 S0, b ? S0 S1, a ? S0 S1, b ? S1

15.10.2006

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

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

15.10.2006

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

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

Символ-терминатор и финальное состояние ?

15.10.2006

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

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

15.10.2006

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

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

15.10.2006

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

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

15.10.2006

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

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

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

15.10.2006

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

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

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

15.10.2006

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

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

Набор плиток в опыте по получению ковра Серпинского ?

? Соответствие двумерных плиток молекулам ДНК

Результирующая структура под атомно-силовым микроскопом ?

15.10.2006

35 План доклада

План доклада

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

15.10.2006

36 Parallel Filtering Model

Parallel Filtering Model

Соответствует прямому перебору в классической парадигме вычислений. Реализуется в три стадии: Генерация всех вариантов. Параллельный отсев (в несколько стадий) всех неудовлетворительных вариантов. Расшифровка решения.

15.10.2006

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

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

Пробирка – это мультимножество слов (конечных строк) над алфавитом {А, Ц, Г, Т}. Слить. Образовать объединение (в смысле мультимножеств) двух заданных пробирок. Размножить. Изготовить две копии данной пробирки. Обнаружить. Возвратить значение истина, если данная пробирка N содержит по крайней мере одну цепочку ДНК, иначе - ложь.

15.10.2006

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

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

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

15.10.2006

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

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

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

В приведенных терминах стадия фильтрации в опыте Эдлмана может быть описана “программой”, которая начинает свою работу после того, как произошло сшивание всех нужных молекул и в пробирке N образовалось множество всех возможных путей в графе G. Каждый из олигонуклеотидов si, 0 ? i ? 6, имеет длину 20.

15.10.2006

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

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

ввести (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 – в противном случае.

15.10.2006

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

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

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

Автомат будет дискретным, и к нему применимо понятие шага.

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

15.10.2006

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

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

Все работы, относящиеся к проблеме покрытия (Ванга, Бергера, Робинсона, Пенроуза). Работы Э. Винфри, направленные на получение нужных структур на практике. Работы по теории клеточных автоматов с «квадратными клетками».

15.10.2006

43 План доклада

План доклада

Введение Элементарные операции с ДНК Эксперименты с ДНК Модели и попытки формализации Текущие результаты Решенные задачи Ограничения в экспериментах Программные средства

15.10.2006

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

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

Задача

Год решения

Поиск гамильтонова пути в графе

1994

Достижимость пропозициональных формул

1994

3-раскраска графа

1995

Quantified Boolean formulae

1995

Indendent Set

1996

Задача о рюкзаке

1996

Задача изоморфизма с подграфом

1996

Задача о клике

1996

MAX-CNF SAT

1996

Задача о выполнимости для схем

1996

(3-2) System

1997

Shortest common superstring

1998

Bounded Post correspondence

2000

15.10.2006

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

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

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

Поэтому, например, компания IBM сразу предпочла сфокусироваться на других идеях альтернативных компьютеров, таких как углеродные нанотрубки и квантовые компьютеры.

15.10.2006

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

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

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

15.10.2006

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

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

Nucleic Acid MOdeling Tool Графическое средство работы с молекулярными структурами. Позволяет составлять структуры из атомов, задавать связи в трехмерном пространстве, строить последовательности молекулярных операций.

15.10.2006

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

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

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

Процесс моделирования синтеза структуры «ковер Серпинского» ?

15.10.2006

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

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

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

15.10.2006

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

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

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

15.10.2006

51 Вопросы

Вопросы

План доклада

Введение Элементарные операции с ДНК Эксперименты с ДНК Модели и попытки формализации Текущие результаты

15.10.2006

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

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

Малинецкий Г.Г., Науменко С.А. Вычисления на ДНК. 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.

15.10.2006

«Вычисления с использованием ДНК»
http://900igr.net/prezentacija/matematika/vychislenija-s-ispolzovaniem-dnk-237930.html
cсылка на страницу

Без темы

359 презентаций
Урок

Математика

71 тема
Слайды
900igr.net > Презентации по математике > Без темы > Вычисления с использованием ДНК