История и методология информатики и вычислительной техники. Парфенов П.С. - 73 стр.

UptoLike

ВУЗ: 

Университет ИТМО | Санкт-Петербург

Составители: 

Рубрика: 

75
помощи полимеразно-цепной реакции в миллионах экземплярах, синтез
цепочек нуклеотидов и определение их последовательности.
Основные надежды, которые возлагались на область ДНК-
вычислений, были связаны с высочайшим параллелизмом и плотностью
хранения информации – в одной пробирке может содержаться более 10
15
нуклеотидов (т.е. более петабайта информации) и может идти
одновременно более 10
12
реакций, которые длятся от нескольких секунд
до нескольких минут.
История ДНК-вычислений начинается с 1994 года, когда Леонард
Эдлман (США) применил ДНК-вычисления для решения задачи
коммивояжера на примере с 7 городами, соединенными 14 рейсами
(поскольку метод предусматривал перебор всех возможных вариантов,
то увеличение сложности потребовало бы гигантских количеств
биологического материала). Эдлман синтезировал олигонуклеотиды
(короткие одноцепочечные молекулы ДНК), кодирующие каждый город
и маршрут между ними в виде последовательности нуклеотидов так, что
половинки фрагментов «рейсов» были комплементарны городам,
которые они связывали, а фрагмент «город» мог связать два фрагмента
«рейса». Например, Атланта кодируется как ТГААЦГТЦ, Бостон – как
ТЦГГАЦТГ, а рейс Атланта-Бостон – как ГЦАГТЦГГ. Тогда три
фрагмента могут объединиться в цепочку, поскольку половина ГЦАГ
фрагмента рейса комплементарна фрагменту ЦГТЦ «Атланта», а вторая
половина рейса TЦГГ – фрагменту AГЦЦ «Бостону» (рис. 4.9) [4.14].
Рис. 4.9. Эксперимент Эдлмана. Города и рейсы между ними закодированы
комплементарными последовательностями нуклеотидов.
При синтезе образовывалась цепочка ДНК, соответствующая
последовательному перемещению по городам. «Щепотка» молекул ДНК,
содержащая около 10
14
фрагментов, кодирующих города и рейсы, при
растворении в пробирке примерно за секунду синтезировала триллионы
разнообразных цепочек, среди которых был и правильный путь.
Следующие несколько дней заняла фильтрация «неправильных» цепочек
– которые не начинались и не заканчивались фрагментами,
соответствующими местам старта и финиша, в которых повторялись
фрагменты, длина которых не соответствовала числу 7 и т.д.
Эксперимент Эдлмана дал начало модели параллельной
фильтрации, в которой множество всевозможных решений получается на
первом шаге за счет того, что все взаимодействующие молекулы ДНК

Страницы