В ходе исследовательских работ биологами и математиками из университетов штатов Северная Каролина и Миссури была предпринята попытка использовать свойства ДНК для создания модели организации определенных вычислительных процессов. Ранее ученые пытались выяснить, подойдут ли молекулы ДНК для проектирования более компактных и эффективных методов хранения данных. В ходе нового исследования им предстояло ответить на вопрос, можно ли использовать бактерии E.сoli для нахождения эффективного алгоритма сортировки при решении известной задачи о подгоревших блинах.
"Блины" из ДНКa
Алгоритм сортировки представляет собой набор инструкций, с помощью которых программист вычислительной системы упорядочивает данные по определенному критерию. Задача о сортировке подгоревших блинов заключается в поиске алгоритма укладывания отдельных элементов множества в соответствии с их размерами. Обычно именно так повар выстраивает горку своих блинов, переворачивая отдельные ее элементы.
Сложность задачи о подгоревших блинах обусловлена еще и тем, что по завершении сортировки все блины должны лежать вверх строго определенной стороной. Предполагается, что одна сторона у каждого из блинов подгорела, а другая имеет отличный золотистый цвет. Поэтому в процессе сортировки, помимо размещения блинов крупного размера внизу, а маленького вверху хотелось бы еще, чтобы своей золотистой стороной все они смотрели вверх. Таким образом, цель разработки алгоритма решения задачи о подгоревших блинах заключается в том, чтобы путем переворачивания расположить все блины на тарелке золотистой стороной вверх в порядке возрастания их размеров, выполнив при этом минимальное количество операций.
В данном случае в качестве блинов выступали молекулы ДНК бактерий E.coli. По словам Кармеллы Хейнес, руководителя исследовательского проекта, молекулы ДНК бактерий позволяют относительно недорого организовать выполнение повторяющихся операций. При использовании реальных компьютеров - даже при условии организации серьезной параллельной обработки - для этого потребовались бы довольно серьезные вычислительные ресурсы.
Клетки дешевле
"Поскольку наша система оперирует живыми клетками, ее воспроизводство обходится значительно дешевле, - пояснила Хейнес. - В конце концов, клетки и без нас знают, как им следует делиться".
Сам эксперимент проводился следующим образом: после получения достаточного для выполнения работ числа клеток E.coli исследователи ввели в колонию гены бактерии Salmonella typhimurium. В результате молекулы ДНК E.coli начали менять свое положение случайным образом. Аналогичным образом укладывались на начальном этапе элементы стопки подгоревших блинов.
Одновременное случайное перемешивание миллионов бактерий позволяло с высокой степенью вероятности утверждать, что по крайней мере некоторое количество молекул ДНК выстроится в нужном порядке. Ученые определяли, какие именно ДНК упорядочены правильно, вводя в бактерию ген, который делал ее устойчивой к антибиотикам, после того как ДНК переворачивалась нужным образом. Затем клетки подвергались воздействию антибиотиков. Таким образом проверялась правильность решения задачи о подгоревших блинах отдельными клетками. Исследователи определяли минимальное число переворачиваний, необходимых для решения данной задачи, засекая время, в течение которого бактерия принимала нужное положение.
"Каждую минуту мы выбирали бактерию и начинали воздействовать на нее антибиотиками, наблюдая за тем, какие клетки выживут, - сообщила Хейнес. - Проделывая эту операцию через регулярные интервалы времени, мы искали момент, когда клетки решат стоящую перед ними задачу и выстроят ДНК в нужном порядке. Поскольку разработанная нами системами обладала свойствами массового параллелизма, это повышало шансы на удачный исход для отдельных элементов".
Теория и практика
Со стороны все это больше похоже на абстрактное решение абстрактной задачи, но Хейнес отметила, что "сортировка подгоревших блинов" имеет важное практическое значение для генетиков, которые пытаются понять процесс эволюции генома различных биологических видов. Поскольку многие виды генетически схожи, ученые могут использовать механизм сортировки задачи о подгоревших блинах, для того чтобы определить, например, сколько переворачиваний потребуется для превращения ДНК кошки в ДНК обезьяны.
"Предположим, вами выбраны два действительно схожих биологических вида, и вы хотите определить степень их связанности, - заметила Хэйнес. - Поскольку количество всевозможных способов упорядочения геномов в общем случае бесконечно, для того, чтобы понять эволюционные отношения, хотелось бы узнать, какое минимальное число операций потребуется для перехода от одного генома к другому".
А теперь давайте взглянем на вещи шире. Сегодня ученые прикладывают немало усилий к тому, чтобы понять, каким образом можно использовать ДНК для моделирования вычислительных процессов, и в будущем у них появится значительно больше проектов, напоминающих решение задачи о подгоревших блинах.
"Исследователи постоянно ищут новые способы использования природы ДНК, - отметила Хэйнес. - Я даже смутно припоминаю документ, в котором описывалось, каким образом следует использовать компоненты искусственной ДНК для игры в крестики-нолики".
[http://www.idgns.com/idgimage.nsf/0/F463FE426947BF0F002566260067673C]
.png)