ДНК-вычисления — это новая отрасль нетрадиционных вычислений , которая использует ДНК , биохимию и оборудование молекулярной биологии вместо традиционных электронных вычислений . Исследования и разработки в этой области касаются теории, экспериментов и приложений ДНК-вычислений. Хотя изначально эта область началась с демонстрации вычислительного приложения Леном Адлеманом в 1994 году, сейчас она расширилась до нескольких других направлений, таких как разработка технологий хранения данных, [1] [2] [3] наномасштабных методов визуализации, [4] [5] [6] синтетических контроллеров и реакционных сетей, [7] [8] [9] [10] и т. д.
Леонард Адлеман из Университета Южной Калифорнии первоначально разработал эту область в 1994 году. [11] Адлеман продемонстрировал доказательство концепции использования ДНК как формы вычисления, которая решила проблему семиточечного гамильтонова пути . Со времени первых экспериментов Адлемана произошел прогресс, и было доказано, что различные машины Тьюринга могут быть построены. [12] [13]
С тех пор эта область расширилась в нескольких направлениях. В 1995 году идея памяти на основе ДНК была предложена Эриком Баумом [14], который предположил, что огромное количество данных может храниться в крошечном количестве ДНК из-за ее сверхвысокой плотности. Это расширило горизонт ДНК-вычислений в область технологии памяти, хотя демонстрации in vitro были сделаны почти через десятилетие.
Область ДНК-вычислений можно отнести к категории подобласти более широкой области ДНК-нанонауки, начатой Недом Симаном примерно за десятилетие до демонстрации Лена Адлемана. [15] Первоначальная идея Неда в 1980-х годах заключалась в построении произвольных структур с использованием самосборки ДНК снизу вверх для приложений в кристаллографии. Однако она трансформировалась в область структурной самосборки ДНК [16] [17] [18] , которая по состоянию на 2020 год является чрезвычайно сложной. Самоорганизующиеся структуры от нескольких нанометров в высоту до нескольких десятков микрометров в размере были продемонстрированы в 2018 году.
В 1994 году группа профессора Симана продемонстрировала ранние структуры решетчатой ДНК, используя небольшой набор компонентов ДНК. В то время как демонстрация Адлемана показала возможность компьютеров на основе ДНК, конструкция ДНК была тривиальной, поскольку по мере роста числа узлов в графе число компонентов ДНК, требуемых в реализации Адлемана, будет расти экспоненциально. Поэтому специалисты по информатике и биохимики начали изучать сборку плиток, где целью было использовать небольшой набор нитей ДНК в качестве плиток для выполнения произвольных вычислений при росте. Другие направления, которые были теоретически исследованы в конце 90-х, включают безопасность и криптографию на основе ДНК, [19] вычислительную мощность систем ДНК, [20] память и диски ДНК, [21] и робототехнику на основе ДНК. [22]
До 2002 года Лила Кари показала, что операции ДНК, выполняемые путем генетической рекомбинации в некоторых организмах, являются полными по Тьюрингу. [23]
В 2003 году группа Джона Рейфа впервые продемонстрировала идею шагающего робота на основе ДНК, который перемещался по траектории, похожей на робота, следующего по линии. Они использовали молекулярную биологию в качестве источника энергии для шагающего робота. С момента этой первой демонстрации было продемонстрировано большое разнообразие шагающих роботов на основе ДНК.
В 1994 году Леонард Адлеман представил первый прототип ДНК-компьютера. TT-100 представлял собой пробирку, заполненную 100 микролитрами раствора ДНК. Ему удалось решить пример задачи направленного гамильтонова пути . [24] В эксперименте Адлемана задача гамильтонова пути была реализована нотацией как « задача коммивояжера ». Для этой цели были созданы различные фрагменты ДНК, каждый из которых представлял город, который нужно было посетить. Каждый из этих фрагментов способен связываться с другими созданными фрагментами. Эти фрагменты ДНК были получены и смешаны в пробирке . В течение нескольких секунд маленькие фрагменты образуют более крупные, представляющие различные маршруты путешествий. С помощью химической реакции фрагменты ДНК, представляющие более длинные маршруты, были устранены. Остатки являются решением проблемы, но в целом эксперимент длился неделю. [25] Однако текущие технические ограничения не позволяют оценить результаты. Поэтому эксперимент не подходит для применения, но, тем не менее, он является доказательством концепции .
Первые результаты по этим проблемам были получены Леонардом Адлеманом .
В 2002 году Дж. Макдональд, Д. Стефанович и М. Стоянович создали ДНК-компьютер, способный играть в крестики-нолики против человека. [26] Калькулятор состоит из девяти ячеек, соответствующих девяти квадратам игры. Каждая ячейка содержит субстрат и различные комбинации ферментов ДНК. Сам субстрат состоит из цепи ДНК, к которой на одном конце привита флуоресцентная химическая группа, а на другом конце — группа репрессора. Флуоресценция активна только в том случае, если молекулы субстрата разрезаны пополам. Ферменты ДНК имитируют логические функции . Например, такая ДНК развернется, если ввести два определенных типа цепей ДНК для воспроизведения логической функции И.
По умолчанию компьютер считается первым, кто ходит в центральном квадрате. Игрок-человек начинает с восьми различных типов цепочек ДНК, соответствующих восьми оставшимся полям, которые могут быть сыграны. Чтобы сыграть в поле номер i, игрок-человек высыпает во все ячейки цепочки, соответствующие входу #i. Эти цепочки связываются с определенными ферментами ДНК, присутствующими в ячейках, что приводит в одной из этих ячеек к деформации ферментов ДНК, которые связываются с субстратом и разрезают его. Соответствующая ячейка становится флуоресцентной, указывая, в каком поле играет ДНК-компьютер. Ферменты ДНК распределяются между ячейками таким образом, чтобы гарантировать, что лучшее, чего может достичь игрок-человек, — это ничья, как в настоящей игре в крестики-нолики.
Кевин Черри и Лулу Цянь из Калтеха разработали искусственную нейронную сеть на основе ДНК, которая может распознавать 100-битные рукописные цифры. Они достигли этого, программируя на компьютере заранее с соответствующим набором весов, представленных различными концентрациями весовых молекул, которые позже будут добавлены в пробирку, содержащую входные нити ДНК. [27] [28]
Одной из проблем ДНК-вычислений является ее скорость. Хотя ДНК как субстрат биологически совместима, т. е. ее можно использовать там, где кремниевая технология не может, ее скорость вычислений все еще очень низкая. Например, схема квадратного корня, используемая в качестве эталона в полевых условиях, заняла более 100 часов. [29] В то время как новые способы с внешними источниками ферментов сообщают о более быстрых и компактных схемах, [30] Чаттерджи и др. продемонстрировали интересную идею в этой области для ускорения вычислений с помощью локализованных ДНК-схем, [31] концепция, которая далее изучается другими группами. [32] Эта идея, хотя изначально была предложена в области компьютерной архитектуры, была принята и в этой области. В компьютерной архитектуре очень хорошо известно, что если инструкции выполняются последовательно, их загрузка в кэш неизбежно приведет к высокой производительности, также называемой принципом локализации. Это связано с тем, что с инструкциями в быстрой кэш-памяти нет необходимости переставлять их в основную память и из нее, что может быть медленно. Аналогично, в локализованных ДНК-вычислениях цепи ДНК, отвечающие за вычисления, фиксируются на подложке, похожей на макетную плату, что обеспечивает физическую близость вычислительных вентилей. Такие локализованные ДНК-вычислительные методы показали, что потенциально сокращают время вычислений на порядки.
Последующие исследования ДНК-вычислений привели к появлению обратимого ДНК-вычисления, приблизив технологию на один шаг к кремниевым вычислениям, используемым в (например) ПК . В частности, Джон Рейф и его группа в Университете Дьюка предложили два различных метода повторного использования вычислительных комплексов ДНК. Первый проект использует вентили dsDNA, [33] тогда как второй проект использует комплексы ДНК-шпилек. [34] Хотя оба проекта сталкиваются с некоторыми проблемами (такими как утечки реакции), это, по-видимому, представляет собой значительный прорыв в области ДНК-вычислений. Некоторые другие группы также пытались решить проблему повторного использования вентилей. [35] [36]
Используя реакции смещения нитей (SRD), в статье "Стратегия синтеза обратимых цепей на ДНК-компьютерах" [37] представлены обратимые предложения по реализации обратимых вентилей и цепей на ДНК-компьютерах путем объединения ДНК-вычислений и методов обратимых вычислений. В этой статье также предлагается универсальная библиотека обратимых вентилей (URGL) для синтеза n-битных обратимых цепей на ДНК-компьютерах со средней длиной и стоимостью построенных цепей лучше, чем у предыдущих методов.
Существует несколько методов построения вычислительного устройства на основе ДНК, каждый из которых имеет свои преимущества и недостатки. Большинство из них строят базовые логические вентили ( И , ИЛИ , НЕ ), связанные с цифровой логикой , на основе ДНК. Некоторые из различных баз включают ДНКзимы, дезоксиолигонуклеотиды , ферменты и обмен опорными точками.
Наиболее фундаментальной операцией в ДНК-вычислениях и молекулярном программировании является механизм смещения нитей. В настоящее время существует два способа выполнения смещения нитей:
Помимо простых схем смещения нитей, ДНК-компьютеры также были построены с использованием концепции обмена опорной точкой. [28] В этой системе входная цепь ДНК связывается с липким концом , или опорной точкой, на другой молекуле ДНК, что позволяет ей смещать другой сегмент цепи из молекулы. Это позволяет создавать модульные логические компоненты, такие как вентили И, ИЛИ и НЕ и усилители сигналов, которые могут быть связаны в произвольно большие компьютеры. Этот класс ДНК-компьютеров не требует ферментов или каких-либо химических возможностей ДНК. [38]
Полный стек для ДНК-вычислений выглядит очень похожим на традиционную компьютерную архитектуру. На самом высоком уровне язык программирования общего назначения типа C выражается с помощью набора сетей химических реакций (CRN). Это промежуточное представление транслируется в проектирование ДНК на уровне домена, а затем реализуется с помощью набора цепей ДНК. В 2010 году группа Эрика Уинфри показала, что ДНК может использоваться в качестве субстрата для реализации произвольных химических реакций. Это открыло путь к проектированию и синтезу биохимических контроллеров, поскольку выразительная сила CRN эквивалентна машине Тьюринга. [7] [8] [9] [10] Такие контроллеры потенциально могут использоваться in vivo для таких приложений, как предотвращение гормонального дисбаланса.
Каталитическая ДНК ( дезоксирибозим или ДНКзим) катализирует реакцию при взаимодействии с соответствующим вводом, таким как соответствующий олигонуклеотид . Эти ДНКзимы используются для построения логических вентилей, аналогичных цифровой логике в кремнии; однако ДНКзимы ограничены 1-, 2- и 3-входовыми вентилями без текущей реализации для оценки операторов в серии.
Логический вентиль ДНКзима изменяет свою структуру, когда он связывается с соответствующим олигонуклеотидом, и флуорогенный субстрат, с которым он связан, отщепляется. Хотя можно использовать и другие материалы, большинство моделей используют субстрат на основе флуоресценции, поскольку его очень легко обнаружить, даже на пределе одной молекулы. [39] Затем можно измерить количество флуоресценции, чтобы определить, произошла ли реакция. ДНКзим, который изменяется, затем «используется» и не может инициировать никаких других реакций. Из-за этого эти реакции происходят в таком устройстве, как реактор с непрерывным перемешиванием, где старый продукт удаляется и добавляются новые молекулы.
Два часто используемых ДНКзима называются E6 и 8-17. Они популярны, потому что позволяют расщеплять субстрат в любом произвольном месте. [40] Стоянович и Макдональд использовали ДНКзимы E6 для создания машин MAYA I [41] и MAYA II [42] соответственно; Стоянович также продемонстрировал логические вентили с использованием ДНКзима 8-17. [43] Хотя было показано, что эти ДНКзимы полезны для построения логических вентилей, они ограничены необходимостью наличия металлического кофактора для функционирования, такого как Zn 2+ или Mn 2+ , и, таким образом, бесполезны in vivo . [39] [44]
Конструкция, называемая петлей-стеблем , состоящая из одной нити ДНК с петлей на конце, представляет собой динамическую структуру, которая открывается и закрывается, когда часть ДНК связывается с частью петли. Этот эффект был использован для создания нескольких логических вентилей . Эти логические вентили были использованы для создания компьютеров MAYA I и MAYA II , которые в некоторой степени могут играть в крестики-нолики . [45]
ДНК-компьютеры на основе ферментов обычно имеют форму простой машины Тьюринга ; существует аналогичное оборудование в форме фермента и программное обеспечение в форме ДНК. [46]
Бененсон, Шапиро и коллеги продемонстрировали ДНК-компьютер, использующий фермент FokI [47], и расширили свою работу, показав автоматы, которые диагностируют и реагируют на рак простаты : недостаточная экспрессия генов PPAP2B и GSTP1 и повышенная экспрессия PIM1 и HPN . [48] Их автоматы оценивали экспрессию каждого гена, по одному гену за раз, и при положительном диагнозе затем высвобождали одноцепочечную молекулу ДНК (ssDNA), которая является антисмысловой для MDM2 . MDM2 является репрессором белка 53 , который сам по себе является супрессором опухоли. [49] При отрицательном диагнозе было решено выпустить супрессор препарата с положительным диагнозом вместо того, чтобы ничего не делать. Ограничением этой реализации является то, что требуются два отдельных автомата, по одному для введения каждого препарата. Весь процесс оценки до высвобождения препарата занял около часа. Этот метод также требует наличия переходных молекул, а также фермента FokI. Необходимость в ферменте FokI ограничивает применение in vivo , по крайней мере, для использования в «клетках высших организмов». [50] Следует также отметить, что молекулы «программного обеспечения» могут быть повторно использованы в этом случае.
ДНК-нанотехнология была применена в смежной области ДНК-вычислений. Плитки ДНК могут быть разработаны так, чтобы содержать несколько липких концов с последовательностями, выбранными так, чтобы они действовали как плитки Вана . Был продемонстрирован массив DX, сборка которого кодирует операцию XOR ; это позволяет массиву ДНК реализовать клеточный автомат , который генерирует фрактал , называемый салфеткой Серпинского . Это показывает, что вычисления могут быть включены в сборку массивов ДНК, расширяя его область действия за пределы простых периодических массивов. [51]
ДНК-вычисления — это форма параллельных вычислений , которая использует преимущества множества различных молекул ДНК, чтобы одновременно опробовать множество различных возможностей. [52] Для некоторых специализированных задач ДНК-компьютеры быстрее и меньше, чем любой другой компьютер, созданный до сих пор. Кроме того, было продемонстрировано, что определенные математические вычисления работают на ДНК-компьютере.
ДНК-вычисления не предоставляют никаких новых возможностей с точки зрения теории вычислимости , изучение которой позволяет решать проблемы вычислительно с использованием различных моделей вычислений. Например, если пространство, необходимое для решения проблемы, растет экспоненциально с размером проблемы ( проблемы EXPSPACE ) на машинах фон Неймана , оно все еще растет экспоненциально с размером проблемы на ДНК-машинах. Для очень больших задач EXPSPACE требуемый объем ДНК слишком велик, чтобы быть практичным.
Партнерство между IBM и Caltech было создано в 2009 году с целью производства « ДНК-чипов ». [53] Группа Caltech работает над производством этих интегральных схем на основе нуклеиновых кислот. Один из этих чипов может вычислять целые квадратные корни. [54] Компилятор был написан [55] на Perl .
Низкая скорость обработки ДНК-компьютера (время отклика измеряется в минутах, часах или днях, а не в миллисекундах) компенсируется его потенциалом для выполнения большого количества множественных параллельных вычислений. Это позволяет системе тратить одинаковое количество времени на сложные вычисления, как и на простые. Это достигается тем, что миллионы или миллиарды молекул взаимодействуют друг с другом одновременно. Однако анализировать ответы, выдаваемые ДНК-компьютером, гораздо сложнее, чем цифровым.
{{cite web}}: CS1 maint: архивная копия как заголовок ( ссылка ){{cite web}}: CS1 maint: архивная копия как заголовок ( ссылка ){{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )— Книга начинается с введения в вопросы, связанные с ДНК, с основ биохимии, теории языка и вычислений, а затем переходит к углубленной математической теории ДНК-вычислений.