Любой маршрут проезда по этим городам по таким дорогам может быть воспроизведен в нитях ДНК, соединяющихся во всех случаях, когда одна дорога входит в город, а другая выходит из него.
Например, у города А может быть метка ATGTACCA, у города B – GGTCCACG, а у города C – TCGACCGG. Тогда дороге из А в B будет соответствовать нить
ATGTACCACCAGGTGC,
ATGTACCACCAGGTGC,
а дороге из B в C – нить
GGTCCACGAGCTGGCC.
GGTCCACGAGCTGGCC.
Восемь последних оснований первой из этих дорог могут соединиться с восемью первыми основаниями второй, что показывает, что маршрут, позволяющий попасть из города А в город C, существует.
Эта система прекрасна тем, что такие нити ДНК можно приобретать в больших количествах в коммерческих лабораториях. Адлеман заказал достаточное количество материала для исследования сети из 7 городов, а затем просто разложил нити по пробиркам. Нити принялись за параллельную обработку информации: они начали соединяться, создавая множество разных маршрутов обхода сети. Разумеется, многие из этих маршрутов нарушали правило, запрещающее посещать города больше одного раза. Но Адлеман понимал, что тот маршрут, который он ищет, должен представлять собой нить ДНК, длина которой равна
8 (город отправления) + 6 × 8 (для каждой дороги) + 8 (город назначения).
8 (город отправления) + 6 × 8 (для каждой дороги) + 8 (город назначения).
Для отбора таких нитей и проверки присутствия в их последовательностях всех городов годилась процедура, сходная с генетической дактилоскопией.
Хотя весь этот процесс занял больше недели, он открыл интересные перспективы: возможность использования биологических структур для создания машин, способных эффективно производить параллельную обработку информации. Для измерения количества молекул в пробирке химики используют единицу под названием «моль». Но один моль вещества содержит чуть более 6 × 1023 молекул[134]. Адлеман считает, что использование предельно малых биологических объектов может стать шорткатом к решению предельно больших вычислительных задач.
Не исключено, что природа уже преуспела в этом. Оказывается, один странный организм, относящийся к классу собственно слизевики, довольно хорошо умеет находить самые рациональные маршруты передвижения по карте. Это слизевик
Группа исследователей из Оксфорда и Саппоро решила задать своему слизевику следующую задачу: найти кратчайший маршрут среди овсяных хлопьев, разложенных так же, как расположены станции железнодорожной сети Токио и его окрестностей. У инженеров ушли целые годы на разработку наиболее рациональной схемы соединения городов. А на что способен слизевик?