Коммивояжер применил к синтезу ДНК


Одна из забавных вещей в работе программиста заключается в том, что известные вам алгоритмы часто могут применяться неожиданным образом в областях, которые находятся в сфере компетенции других специалистов. Хороший пример — приложение коммивояжера к синтезу ДНК.

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

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

Избыточность кодонов является ключом к решению проблемы повторяющихся последовательностей. Все, что нам нужно сделать, это изменить кодоны, чтобы удалить повторы в ДНК, сохранив повторы в произведенном белке. Это то, что сделали ученые из Университета Дьюка, используя аналогию с задачей коммивояжера. Задача состоит в том, чтобы найти наименее повторяющуюся последовательность, которая все еще производит тот же самый белок.

Ашутош Чилкоти, профессор биомедицинской инженерии Тео Пилкингтона, объясняет:

«Я всегда думал, что есть потенциальное решение, что должен быть способ математически решить его. Я предлагал эту задачу аспирантам раньше, но никто не хотел заниматься ею, потому что это требует определенной комбинации математики высокого уровня информатика и молекулярная биология. Но Николас Танг был правильным парнем ».

Решение — вариант задачи «коммивояжер». Классический вопрос: учитывая карту с набором городов для посещения, каков самый короткий маршрут, который проходит в каждый город ровно один раз, прежде чем вернуться в исходный город? Однажды признанная проблемой коммивояжера, было найдено точное решение с использованием графов Де Брейна и современного смешанного целочисленного линейного программного решателя.

После замены частей генетического кода в повторяющихся рецептах белков исследователи смогли перемешать их достаточно для коммерческого синтеза. Темные полосы являются индикаторами 18-ти повторяющихся полипептидов, которые были успешно изготовлены.

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

Чилкоти и Тан в настоящее время работают над тем, чтобы сделать новую компьютерную программу доступной онлайн для всех, чтобы использовать ее через простую веб-форму, открывая новую область синтетической биологии для всех.


Добавить комментарий