Ракитин Александр Георгиевич
аспирант кафедры информатизации образования, Российский государственный педагогический университет им. А.И. Герцена г. Санкт-Петербург
funcalll@rambler.ru  

О компьютерной реализации опыта Эдлмана на платформе 1С

Аннотация
Одним из первых опытов, проведенных в лаборатории на цепочках ДНК, позволяющим решить задачу о поиске гамильтонового пути в графе, был опыт, проведенный Л. Эдлманом (1994).  При помощи интерпретатора ДНК на базе языка 1С, появляется возможность демонстрации решения задачи поиска гамильтонового пути в графе.

Ключевые слова
Биокомпьютеры, опыт Эдлмана, операции над цепочками ДНК, интерпретатор ДНК-вычислений 

В 1994 г. Л. Эдлман провел опыт в лаборатории, позволяющий доказать, при помощи цепочек ДНК, наличие гамильтонового пути в графе. Граф является гамильтоновым в том случае, если существует такой путь, из начальной вершины в конечную вершину, который проходит через каждую вершину ровно один раз. Л. Эдлман приводит пример графа с 4-мя вершинами и 6-ю дугами [1]. Вершины символизируют города: Атланта, Бостон, Чикаго и Детройт. Дуги символизируют наличие прямого рейса на самолете. Вершины закодированы цепочками ДНК, состоящими из 8 нуклеотидов. Пути также состоят из 8 нуклеотидов, где первые 4 нуклеотида являются последними 4-мя нуклеотидами вершины, откуда исходит дуга, а вторые 4 нуклеотида являются первыми 4-мя нуклеотидами вершины, куда приходит дуга (см. рис.1).

Рис.1. Схема опыта Эдлмана 

Очевидно, что в данном примере гамильтонов путь существует (он единственный): Атланта-Бостон-Чикаго-Детройт. Поиск такого пути будет выполнен по следующему алгоритму:

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

2. Провести операцию «ренатурация» для получения ДНК цепочек, которые содержат всевозможные пути.

3. Выбрать только те ДНК цепочки, которые имеют длину, соответствующую длине всех вершин.

4. Поочередно выбирать из пробирки те ДНК цепочки, которые содержат каждую из вершин;

5. Проверить наличие ДНК цепочек в пробирке.

В том случае, если после шага 5, в пробирке остались цепочки ДНК, то можно говорить, что гамильтонов путь в графе найден. 

Покажем реализацию опыта Эдлмана в интерпретаторе ДНК вычислений на базе языка 1С[2]. Для демонстрации опыта необходимо создать текстовый файл в формате "txt" (воспользоваться кодировкой "Unicode"). Файл должен иметь следующую структуру:

1. Краткую информацию по командам с интерпретатором.

2. Описание задачи и визуальное представление графа.

3. Последовательности цепочек ДНК и цепочки комплементарные им, которыми кодируются вершины и дуги.

4. Операции над ДНК цепочками (с комментариями).

Приведём пример файла: 

Рис.2. Моделирование опыта Эдлмана 

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

Следует отметить, что полный опыт Эдлмана нет возможности воспроизвести в ДНК интерпретаторе, на современных компьютерах, из-за большого количества возможных комбинации соединения цепочек ДНК. Рисунок, отображающий граф в оригинальном опыте, представлен на рисунке 3. Эдлман для кодирования вершин и дуг использовал цепочки ДНК, состоящие из 20 нуклеотидов, граф с 7-ю вершинами и множеством дуг.

Рис. 3. Граф, отображающий опыт Эдлмана 

Таким образом, компьютерная реализация опыта Эдлмана, может быть проведена за приемлемое время на современных компьютерах с графом, состоящим примерно из 5-ти вершин и 5-ти дуг, где ДНК кодирующие вершины и дуги, состоят из 8-ми нуклеотидов.  

Проведение данных опытов позволяет использовать интерпретатор ДНК вычислений на базе языка 1С, для обучения студентов неклассическим методам вычислений. 

Литература:

1. Adleman L.M. Computing with DNA, Scientific American, August 1998, p. 34-41.

2. Ракитин А.Г. Интерпретатор языка пробирок для ДНК-вычислений. / А.Г. Ракитин, Т.С. Стефанова, М.В. Швецкий // Научное мнение. – 2013. – № 10. – С. 214-219.

Рекомендовано к публикации:
М.В. Швецкий, доктор педагогическтх наук, научный руководитель работы
А.А.Ахаян, доктор педагогических наук, член Редакционной Коллегии

Публикуется при поддержке "Программы Штоля - 2014" по содействию публикации результатов исследований в области педагогической науки

_____

Aleksandr G. Rakitin
Postgraduate student,  Department of informatization in education, Al.Herzen State Pedagogical University of Russia, St.Petersburg
funcalll@rambler.ru

On the computer implementation of Adleman’s experiment on the 1C platform

One of the first of experiments conducted on DNA chains, which helps us to solve a problem of searching a Hamilton path in a graph, was an experiment of L. Elderman (1994). A new solution which demonstrating an opportunity of searching a Hamilton path in a graph appears with a help of DNA interpreter based on "1C".

Keywords
BIO-computers, operations over strands of  DNA, Adleman’s experiment, interpretation program of  DNA computing 

Literatura

1. Adleman L.M. Computing with DNA, Scientific American, August 1998, p. 34-41.

2. Rakitin A.G. Interpretator yazyka probirok dlya DNK-vychislenij. / A.G. Rakitin, T.S. Stefanova, M.V. Shveckij // Nauchnoe mnenie. – 2013. – № 10. – S. 214-219.