Слайд 22
Для того чтобы сгенерировать все возможные маршруты достаточно поместить в пробирку все необходимые и заранее заготовленные ингредиенты, то есть ДНК-молекулы, соответствующие всем возможным перелетам, и ДНК-молекулы, соответствующие всем городам. Но вместо того, чтобы применять одинарные ДНК-цепочки, соответствующие названиям городов, необходимо использовать комплементарные им ДНК-цепочки, то есть вместо ДНК-цепочки ACTT GCAG, соответствующей Атланте, будем применять комплементарную ДНК-цепочку TGAA CGTC и т.д., поскольку ДНК-код города и комплементраный код абсолютно равноправны.
Далее все эти молекулы (достаточно буквально щепотки, которая будет содержать порядка 1014 различных молекул) помещаем в воду, добавляем ферменты, буквально через несколько секунд получаем все возможные маршруты.
Слайд 23
Процесс образования цепочек ДНК, соответствующих различным маршрутам, происходит следующим образом. Рассмотрим, к примеру, цепочку GCAG TCGG, отвечающую за перелет Атланта — Бостон. Вследствие высокой концентрации различных молекул, данная цепочка обязательно встретится с комплементарной ДНК-цепочкой AGCC TGAC, соответствующей Бостону. Поскольку группы TCGG и AGCC комплементарны друг другу, то за счет образования водородных связей эти цепочки сцепятся друг с другом Теперь образовавшаяся цепочка неминуемо встретится с ДНК-цепочкой ACTG GGCT, соответствующей авиаперелету Бостон — Чикаго, и поскольку группа ACTG (первые четыре основания в этой цепочке) комплементарна группе TGAC (последние четыре основания в комплементарном коде Бостона), то ДНК-цепочка ACTG GGCT присоединится к уже образовавшейся цепочке. Далее к этой цепочке таким же образом присоединится ДНК-цепочка, соответствующая городу Чикаго (комплементарный код), а затем и цепочка авиаперелета Чикаго — Детройт.
Процесс образования маршрута показан на рис.
Мы рассмотрели пример образования только одного маршрута (причем это именно гамильтонов маршрут). Аналогичным образом получаются и все остальные возможные маршруты (например, Атланта — Бостон — Атланта — Детройт). Важно, что все маршруты формируются одновременно, то есть параллельно. Причем время, требуемое для создания всех возможных маршрутов в данной задаче и всех маршрутов в задаче с 10 или 20 городами, абсолютно одинаково (лишь бы хватило исходных ДНК-молекул). Собственно, именно в параллельном алгоритме ДНК-вычислений и заключается основное преимущество в сравнении с фон-неймановской архитектурой.
Итак, в пробирке образованы ДНК-молекулы, соответствующие всем возможным маршрутам. Однако это еще не решение задачи — нам необходимо выделить ту единственную ДНК-молекулу, которая отвечает за гамильтонов маршрут. Поэтому на следующем этапе необходимо отобрать молекулы, соответствующие маршрутам, начинающимся в Атланте и заканчивающимся в Детройте.
Слайд 24
Для этого используется полимеразная цепная реакция (PCR), в результате которой создается множество копий только тех ДНК-цепочек, которые начинаются с кода Атланты и заканчиваются кодом Детройта.
Для реализации полимеразной цепной реакции применяются два прайма: GCAG и GGCT. Процесс копирования ДНК-модекул, начинающихся с ДНК-кода Атланты и заканчивающихся ДНК-кодом Детройта, показан на рис. 14.
Отметим, что в присутствии праймов GCAG и GGCT будут копироваться и те ДНК-молекулы, которые начинаются с ДНК-кодов Атланты, но не заканчиваются ДНК-кодом Детройта (под действием прайма GCAG), а также ДНК-молекулы, которые заканчиваются ДНК-кодом Детройта, но не начинаются с ДНК-кода Атланты (под действием прайма GGCT). Понятно, что скорость копирования таких молекул будет гораздо ниже скорости копирования ДНК-молекул, начинающихся с ДНК-кода Атланты и заканчивающихся ДНК-кодом Детройта. Следовательно, после PCR-реакции мы получим преобладающее количество ДНК-молекул в форме регулярной двойной спирали, соответствующих маршрутам, начинающимся в Атланте и заканчивающимся в Детройте.