живые компьютеры

ШЕСТОЙ (6TH@MAIL.RU)

Хакер, номер #074, стр. 082

КАК ЗАСТАВИТЬ ДНК РАБОТАТЬ

АРТУР КЛАРК КАК-ТО СКАЗАЛ: «ЛЮБАЯ ДОСТАТОЧНО РАЗВИТАЯ ТЕХНОЛОГИЯ НЕОТЛИЧИМА ОТ МАГИИ». КОНЕЧНО, ТЕЛЕВИДЕНИЕ И АВТОМАТ КАЛАШНИКОВА ВПОЛНЕ СПОСОБНЫ ВСЕЛИТЬ СУЕВЕРНЫЙ УЖАС В СЕРДЦА, СКАЖЕМ, АБОРИГЕНОВ АВСТРАЛИИ, ДА И ТО МАЛОВЕРОЯТНО :). МЫ ЖЕ БУДЕМ ГОВОРИТЬ О ТЕХНОЛОГИИ, КОТОРАЯ ПОКАЖЕТСЯ ВОЛШЕБСТВОМ ДАЖЕ ПРОДВИНУТЫМ КОМПЬЮТЕРЩИКАМ – О ТЕХНОЛОГИИ ДНК-ВЫЧИСЛЕНИЙ

[магия IT.]

Старик зябко поежился, открыл один глаз и заговорил: «Существует три ступени посвящения в тайны вычислительных машин». Открыв второй глаз, он оглядел притихшую аудиторию и продолжал: «Адепты первой ступени пребывают в неведении относительно истинной природы сущего, ибо уверены, что кроме привычной им архитектуры IBM PC, ничто более не существует в мире. Только инициация во вторую ступень способна исцелить в человеке слепоту ума его, и, прозрев, внимает он дивной симфонии имен: PowerMac, SUN Spark, DEC Alpha... Но истинный свет ниспадет лишь на тех, кто познает тайну третьей ступени». Учитель повысил голос и воздел руки: «О, наивные, решающие задачу коммивояжера методом полного перебора! Внемлите словам моим, ибо я буду говорить о квантовых, аналоговых, химических и пептидных компьютерах!» Так говорил мой препод по нетрадиционным архитектурам :). Шучу, конечно, но факт неоспорим - при словах «не PC» все почему-то вспоминают Мак, а особо продвинутые говорят о нейронных/векторных процессорах. Но редко кто оказывается в курсе, что кроме привычных архитектур существуют разработки, переворачивающие все наши представления о компьютерах и заодно фон Неймана в гробу. Каждое из этих направлений – дело, которому не жалко посвятить и жизнь, что уж говорить о статье в журнале. Но и жизнь, и статья имеют свои пределы и границы, поэтому не будем растекаться мыслью по древу, а начнем разбираться в одном из удивительнейших IT-проектов нашего времени – ДНК-компьютерах.

[коммивояжер и ДНК.]

Так называемая задача коммивояжера заключается в нахождении оптимального маршрута, проходящего через заданные города так, что каждый город оказывается посещенным единожды. Существует масса вариантов решения этой задачи. Одни просты как «Hello World» на Бейсике, другие по части сложности могут поспорить с дизассемблированием в уме, скажем, Старкрафта :).

Но Леонард Эдлман, который, кстати, в свое время участвовал в разработке знаменитого алгоритма шифрования RSA, не искал ни легких, ни сложных путей, а пошел своей, особой дорогой, и в далеком 1994 году представил на суд общественности решение задачи коммивояжера, основанное на свойствах дезоксирибонуклеиновой кислоты – ДНК. Алгоритм предложенного им метода был таков:

1 Сгенерировать все возможные маршруты.

2 Выбрать те из них, которые начинаются и заканчиваются в нужных городах.

3 Выбрать из оставшихся те, которые включают нужное число городов.

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

«Да это же полный перебор!», - скажешь ты. И будешь прав. С алгоритмической точки зрения метод Эдлмана совершенно непримечателен. Но давай разберемся, как выполнялись вычисления в ходе этого эксперимента.

[шаг первый.]

ДНК состоит из гуанина, аденина, тимина и цитозина. Знать, что это такое, вовсе не обязательно: для нас представляет интерес то, что эти элементы располагаются в цепи ДНК в определенном порядке, который и кодирует генную информацию. Для удобства названия элементов сокращают до первых букв – G, A, T и C, которые и представляют базис системы счисления ДНК-компьютера. Таким образом, первый пункт алгоритма Эдлмана выполняется очень просто – достаточно закодировать названия городов в последовательности вида GTCATAG, а потом сформировать все возможные маршруты, соединив все цепочки ДНК между собой. Обычная комбинаторика и никакого мошенничества :). Возможно, у тебя возник вопрос: ну, хорошо, закодировали мы Ставрополь в цепочку GTCA, но где взять ДНК именно с такой структурой? Можно, конечно, перебрать гены десятка миллионов людей, найти нужную и «вырезать». Но обычно поступают проще. Современная молекулярная биология располагает ДНК-синтезатором – аппаратом, который позволяет создавать любые цепочки ДНК с минимумом затрат. Как видно, с этого момента привычная технология окончательно уступает место магии.

[шаг второй.]

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

[шаг третий.]

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

[шаг четвертый.]

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

[итого.]

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

[перспективы.]

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

Еще одна проблема ДНК-вычислений заключается в том, что все используемые технологии – синтез ДНК, ПЦР, гелевый электрофорез, АП - не гарантируют 100% соответствия ожиданиям. Работая в столь тонкой области, какой является молекулярная биология, этого следовало бы ожидать. Да, ошибка, даже если и произойдет, будет чрезвычайно мала. И даже если переменная цикла в твоей программе неожиданно уменьшиться или увеличиться на жалкую единичку, последствия могут быть катастрофическими. Но и здесь технология не стоит на месте: вводятся новые методы коррекции ошибок, совершенствуются сами методики.

[DNA-future.]

Будущее ДНК-компьютеров пока еще смутно различимо в тьме грядущих дней. Возможно, надежды энтузиастов не оправдаются, и такие машины станут лишь игрушкой десятка чудаков, не желающих отдавать свое детище на растерзание жестокому миру. Возможно, нас ждет невиданный доселе прорыв в области IT, и сложнейшие задачи, сегодня требующие вычислительной мощности десятка супермашин, завтра будут возложены на плечи ДНК-компьютеров размером с банку пива. Возможно все. Но одно можно сказать точно. Технология ДНК-вычислений – это открытие. Впервые в поисках решения своих низменных и мирских задач, какой является, например, задача коммивояжера, человек забрался так далеко в запретную область. Чем все это кончится? Увидим.

1000000000000 КОМПЬЮТЕРОВ В КАПЛЕ ВОДЫ

В 2001 ГОДУ УЧЕНЫЕ ИЗ ИЗРАИЛЬСКОГО ИНСТИТУТА ВЕЙЗМАНА РАЗРАБОТАЛИ КОМПЬЮТЕР НАСТОЛЬКО МАЛЫХ РАЗМЕРОВ, ЧТО В КАПЛЕ ВОДЫ ИХ ПОМЕСТИЛСЯ БЫ ЦЕЛЫЙ ТРИЛЛИОН. В СВОЕЙ РАБОТЕ УСТРОЙСТВО ПОЛАГАЕТСЯ НА СВОЙСТВА ДНК И РАЗЛИЧНЫХ ЭНЗИМОВ (ЭНЗИМ – ЭТО ВЫСОКОУМНОЕ НАЗВАНИЕ ФЕРМЕНТА. КАК ПРОТЕИН – ЭТО БЕЛОК, ТАК ЭНЗИМ – ФЕРМЕНТ. – ПРИМ. ЛОЗОВСКОГО). В 2005 ГОДУ ТА ЖЕ КОМАНДА ПОД РУКОВОДСТВОМ ЭХУДА ШАПИРО УСОВЕРШЕНСТВОВАЛА РАЗРАБОТКУ: ТЕПЕРЬ ИХ КОМПЬЮТЕР РАБОТАЕТ В 50 РАЗ БЫСТРЕЕ, И ЕМУ УЖЕ НЕ НУЖЕН ВНЕШНИЙ ИСТОЧНИК ЭНЕРГИИ, В КАЧЕСТВЕ КОТОРОГО ИМ УДАЛОСЬ ИСПОЛЬЗОВАТЬ САМУ ДНК. КНИГА РЕКОРДОВ ГИННЕСА ПРИСУДИЛА УСТРОЙСТВУ ШАПИРО ЗВАНИЕ САМОГО МАЛЕНЬКОГО БИОЛОГИЧЕСКОГО КОМПЬЮТЕРА В МИРЕ.

ДНК НА СЛУЖБЕ ДНК

ДНК-КОМПЬЮТЕРЫ МОГУТ ПОМОЧЬ И В ДЕЛЕ РАСШИФРОВКИ ПОКА ЕЩЕ НЕ ИЗУЧЕННЫХ ФРАГМЕНТОВ ДНК ЖИВЫХ ОРГАНИЗМОВ. ПЕРВЫМ В МИРЕ ДНК-КОМПЬЮТЕРОМ, РАЗРАБОТАННЫМ СПЕЦИАЛЬНО ДЛЯ ЭТОЙ ЗАДАЧИ, ЯВЛЯЕТСЯ OLYMPUS, СОЗДАННЫЙ ЯПОНСКОЙ КОМПАНИЕЙ OLYMPUS OPTICAL В 2002 ГОДУ. ЭХУД ШАПИРО, ОДИН ИЗ ВЕДУЩИХ ЭКСПЕРТОВ ПО ДНК-КОМПЬЮТЕРАМ ВО ВСЕМ МИРЕ, СЧИТАЕТ, ЧТО «НЕСМОТРЯ НА ТО, ЧТО СЕГОДНЯ НАШИ МАШИНЫ МОГУТ РАБОТАТЬ ЛИШЬ С ИСКУССТВЕННО СИНТЕЗИРОВАННЫМИ ДНК, НЕДАЛЕК ТОТ ДЕНЬ, КОГДА В КАЧЕСТВЕ ОСНОВЫ МЫ СМОЖЕМ ИСПОЛЬЗОВАТЬ ЛЮБЫЕ ДНК». УЖЕ СЕЙЧАС СУЩЕСТВУЮТ МОДЕЛИ, В КОТОРЫХ ВСЕ ФУНКЦИИ ОБРАБОТКИ ДАННЫХ, А ТАКЖЕ ВВОД И ВЫВОД ИНФОРМАЦИИ ВЫПОЛНЯЮТСЯ ИСКЛЮЧИТЕЛЬНО ПОСРЕДСТВОМ МОЛЕКУЛ ДНК.

ЧТО ПОЧИТАТЬ

ТИП: WWW

http://en.wikipedia.org/wiki/DNA_computing

просто чтобы въехать в тему + хорошие ссылки в конце

http://users.aol.com/ibrandt/dna_computer.html

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

http://users.aol.com/ibrandt/discover_article.html

забавный комикс, объясняющий основные принципы ДНК-вычислений

http://www.dnaancestryproject.com

не совсем по теме, но не упомянуть не мог. За $119 здесь проанализируют твою генную информацию и выведут твое генеалогическое древо. Вдруг ты потомок Чингизхана?

ЛЮБАЯ ДОСТАТОЧНО РАЗВИТАЯ ТЕХНОЛОГИЯ НЕОТЛИЧИМА ОТ МАГИИ

ДНК СОСТОИТ ИЗ ГУАНИНА, АДЕНИНА, ТИМИНА И ЦИТОЗИНА

ИНАЧЕ ГОВОРЯ, НАМ НУЖЕН КАКОЙ-ТО ФИЛЬТР, ПРОПУСКАЮЩИЙ ДНК ОПРЕДЕЛЕННОЙ ДЛИНЫ, И ОТСЕИВАЮЩИЙ ВСЕ ОСТАЛЬНЫЕ. ЭДАКИЙ IF НА МОЛЕКУЛЯРНОМ УРОВНЕ

ИСПОЛЬЗУЕМЫЙ ПРИЕМ ПОД НАЗВАНИЕМ AFFINITY PURIFICATION, ОЧЕНЬ НАПОМИНАЕТ ПРИНЦИП ДЕЙСТВИЯ ИГРУШЕЧНОЙ РЫБАЛКИ, В КОТОРУЮ Я, НАПРИМЕР, С УДОВОЛЬСТВИЕМ ПОИГРАЛ БЫ И СЕЙЧАС

ДЛЯ СПРАВКИ: В ОДНОМ КУБИЧЕСКОМ САНТИМЕТРЕ МОЖЕТ ПОМЕСТИТЬСЯ ОКОЛО ДЕСЯТИ ТРИЛЛИОНОВ МОЛЕКУЛ ДНК, СПОСОБНЫХ ХРАНИТЬ 10 ТЕРАБАЙТ ДАННЫХ

ВОЗМОЖНО, НАС ЖДЕТ НЕВИДАННЫЙ ПРОРЫВ В ОБЛАСТИ IT, И ЗАДАЧИ, СЕГОДНЯ ТРЕБУЮЩИЕ ВЫЧИСЛИТЕЛЬНОЙ МОЩНОСТИ ДЕСЯТКА СУПЕРМАШИН, ЗАВТРА БУДУТ ВОЗЛОЖЕНЫ НА ПЛЕЧИ ДНК-КОМПЬЮТЕРОВ РАЗМЕРОМ С БАНКУ ПИВА