В ходе исследовательских работ биологами и математиками из университетов штатов Северная Каролина и Миссури при помощи бактерий E.Coli удалось решить классическую математическую задачу о сортировке подгоревших блинов.
«Блины» из ДНК
Эта задача заключается в поиске алгоритма укладывания отдельных элементов множества в соответствии с их размерами. Обычно именно так повар выстраивает горку своих блинов, переворачивая отдельные ее элементы.
Сложность задачи о подгоревших блинах обусловлена еще и тем, что по завершении сортировки все блины должны лежать вверх строго определенной стороной. Предполагается, что одна сторона у каждого из блинов подгорела, а другая имеет отличный золотистый цвет. Поэтому в процессе сортировки помимо размещения блинов крупного размера внизу, а маленького вверху хотелось бы еще, чтобы своей золотистой стороной все они смотрели вверх. Таким образом, цель разработки алгоритма решения задачи о подгоревших блинах заключается в том, чтобы путем переворачивания расположить все блины на тарелке золотистой стороной вверх в порядке возрастания их размеров, выполнив при этом минимальное количество операций.
В данном случае в качестве блинов выступали молекулы ДНК бактерий E.coli. По словам Кармеллы Хэйнес, руководителя исследовательского проекта, молекулы ДНК бактерий позволяют относительно недорого организовать выполнение повторяющихся операций. При использовании реальных компьютеров — даже при условии организации серьезной параллельной обработки — для этого потребовались бы достаточно серьезные вычислительные ресурсы.
Теория и практика
«Поскольку наша система оперирует живыми клетками, ее воспроизводство обходится значительно дешевле, — пояснила Хэйнес. — В конце концов, клетки и без нас знают, как им следует делиться».
Сам эксперимент проводился следующим образом: после получения достаточного для выполнения работ числа клеток E.coli исследователи ввели в колонию гены бактерии Salmonella typhimurium. В результате молекулы ДНК E.coli начали менять свое положение случайным образом. Аналогичным образом укладывались на начальном этапе элементы стопки подгоревших блинов.
Одновременное случайное перемешивание миллионов бактерий позволяло с высокой степенью вероятности утверждать, что по крайней мере некоторое количество молекул ДНК выстроится в нужном порядке. Ученые определяли, какие именно ДНК упорядочены правильно, вводя в бактерию ген, который делал ее устойчивой к антибиотикам, после того как ДНК переворачивалась нужным образом. Затем клетки подвергались воздействию антибиотиков.
Таким образом проверялась правильность решения задачи о подгоревших блинах отдельными клетками. Исследователи определяли минимальное число переворачиваний, необходимых для решения данной задачи, засекая время, в течение которого бактерия принимала нужное положение.
Со стороны все это больше похоже на абстрактное решение абстрактной задачи, но Хэйнес отметила, что «сортировка подгоревших блинов» имеет важное практическое значение для генетиков, которые пытаются понять процесс эволюции генома различных биологических видов. Поскольку многие виды генетически схожи, ученые могут использовать механизм сортировки задачи о подгоревших блинах, для того чтобы определить, например, сколько переворачиваний потребуется для превращения ДНК кошки в ДНК обезьяны.
«Предположим, вами выбраны два действительно схожих биологических вида, и вы хотите определить степень их связанности, — заметила Хэйнес. — Поскольку количество всевозможных способов упорядочивания геномов в общем случае бесконечно, для того чтобы понять эволюционные отношения, хотелось бы узнать, какое минимальное число операций потребуется для перехода от одного генома к другому».