ДНК-вычисления — это новая отрасль нетрадиционных вычислений , в которой вместо традиционных электронных вычислений используются аппаратные средства ДНК , биохимии и молекулярной биологии . Исследования и разработки в этой области касаются теории, экспериментов и приложений вычислений на ДНК. Хотя эта область первоначально началась с демонстрации компьютерного приложения Леном Адлеманом в 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 году Леонард Адлеман представил первый прототип ДНК-компьютера. ТТ-100 представлял собой пробирку, наполненную 100 микролитрами раствора ДНК. Ему удалось решить пример задачи о направленном гамильтоновом пути . [24] В эксперименте Адлемана гамильтонова проблема пути была реализована условно как « задача коммивояжера ». Для этого были созданы разные фрагменты ДНК, каждый из которых представлял собой город, который нужно было посетить. Каждый из этих фрагментов способен связываться с другими созданными фрагментами. Эти фрагменты ДНК были получены и смешаны в пробирке . За считанные секунды маленькие фрагменты образуют более крупные, представляющие различные маршруты путешествия. В результате химической реакции фрагменты ДНК, представляющие более длинные пути, были удалены. Останки являются решением проблемы, но в целом эксперимент длился неделю. [25] Однако текущие технические ограничения не позволяют оценить результаты. Таким образом, эксперимент не подходит для применения, но тем не менее является подтверждением концепции .
Первые результаты по этим проблемам были получены Леонардом Адлеманом .
В 2002 году Дж. Макдональд, Д. Стефанович и М. Стоянович создали ДНК-компьютер, способный играть в крестики-нолики против игрока-человека. [26] Калькулятор состоит из девяти ячеек, соответствующих девяти квадратам игры. Каждый контейнер содержит субстрат и различные комбинации ДНК-ферментов. Сам субстрат состоит из цепи ДНК, к которой на одном конце привита флуоресцентная химическая группа, а на другом конце — репрессорная группа. Флуоресценция активна только в том случае, если молекулы субстрата разрезаны пополам. Ферменты ДНК моделируют логические функции . Например, такая ДНК развернется, если ввести два конкретных типа цепи ДНК для воспроизведения логической функции И.
По умолчанию считается, что компьютер первым сыграл на центральной площади. Игрок-человек начинает с восьми различных типов цепей ДНК, соответствующих восьми оставшимся полям, в которые можно играть. Чтобы разыграть коробку номер i, игрок-человек складывает во все контейнеры нити, соответствующие входу #i. Эти нити связываются с определенными ферментами ДНК, присутствующими в бункерах, что приводит в одном из этих бункеров к деформации ферментов ДНК, которые связываются с субстратом и разрезают его. Соответствующая ячейка становится флуоресцентной, указывая, в какую коробку играет ДНК-компьютер. Ферменты ДНК распределены по контейнерам таким образом, чтобы гарантировать, что лучшее, чего может добиться игрок-человек, — это ничья, как в настоящих крестиках-ноликах.
Кевин Черри и Лулу Цянь из Калифорнийского технологического института разработали искусственную нейронную сеть на основе ДНК, которая может распознавать 100-битные рукописные цифры. Они достигают этого путем предварительного программирования на компьютере соответствующего набора весов, представленных молекулами веса различной концентрации, которые позже будут добавлены в пробирку, содержащую входные нити ДНК. [27] [28]
Одной из проблем вычислений на ДНК является их скорость. Хотя ДНК в качестве субстрата биологически совместима, т.е. ее можно использовать там, где кремниевая технология невозможна, скорость ее вычислений все еще очень низкая. Например, на выполнение схемы извлечения квадратного корня, используемой в качестве эталона в полевых условиях, потребовалось более 100 часов. [29] В то время как новые способы использования внешних источников ферментов сообщают о более быстрых и компактных цепях, [30] Chatterjee et al. продемонстрировал интересную идею в этой области по ускорению вычислений с помощью локализованных цепей ДНК. [31] Эта концепция в настоящее время изучается другими группами. [32] Эта идея, первоначально предложенная в области компьютерной архитектуры, была принята и в этой области. В компьютерной архитектуре очень хорошо известно, что если инструкции выполняются последовательно, их загрузка в кэш неизбежно приведет к повышению производительности, что также называется принципом локализации. Это связано с тем, что при использовании инструкций в быстрой кэш-памяти нет необходимости загружать их в основную память и из нее, что может быть медленным. Аналогичным образом, при локализованных вычислениях ДНК цепи ДНК, ответственные за вычисления, фиксируются на подложке, напоминающей макет, что обеспечивает физическую близость вычислительных ворот. Было показано, что такие методы локализованных вычислений на ДНК потенциально сокращают время вычислений на порядки.
Последующие исследования ДНК-вычислений привели к появлению обратимых ДНК-вычислений, что приблизило эту технологию на один шаг к вычислениям на основе кремния, используемым (например) в ПК . В частности, Джон Рейф и его группа из Университета Дьюка предложили два разных метода повторного использования вычислительных комплексов ДНК. В первом дизайне используются ворота дцДНК [33] , а во втором — шпильковые комплексы ДНК. [34] Хотя оба проекта сталкиваются с некоторыми проблемами (например, утечками реакций), это, по-видимому, представляет собой значительный прорыв в области вычислений на ДНК. Некоторые другие группы также пытались решить проблему повторного использования ворот. [35] [36]
В статье «Стратегия синтеза обратимых цепей на компьютерах ДНК» [37] представлены обратимые предложения с использованием реакций смещения цепи (SRD ) для реализации обратимых вентилей и цепей на компьютерах ДНК путем сочетания вычислений ДНК и методов обратимых вычислений. В данной статье также предлагается универсальная библиотека обратимых вентилей (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 . и ХПН . [48] Их автоматы оценивали экспрессию каждого гена, по одному гену за раз, и при положительном диагнозе затем выделяли одноцепочечную молекулу ДНК (оцДНК), которая является антисмысловой для MDM2 . MDM2 является репрессором белка 53 , который сам по себе является супрессором опухоли. [49] При отрицательном диагнозе было решено выпустить препарат, подавляющий положительный диагноз, вместо того, чтобы ничего не предпринимать. Ограничением этой реализации является то, что требуются два отдельных автомата, по одному для введения каждого лекарства. Весь процесс оценки до выпуска препарата занял около часа. Этот метод также требует присутствия переходных молекул, а также фермента FokI. Требование к ферменту FokI ограничивает его применение in vivo , по крайней мере, для использования в «клетках высших организмов». [50] Следует также отметить, что «программные» молекулы в этом случае могут быть использованы повторно.
Нанотехнология ДНК нашла применение в смежной области вычислений ДНК. Плитки ДНК могут быть спроектированы так, чтобы они содержали несколько липких концов с последовательностями, выбранными так, чтобы они действовали как плитки Ванга . Был продемонстрирован массив DX, сборка которого кодирует операцию XOR ; это позволяет массиву ДНК реализовать клеточный автомат , который генерирует фрактал , называемый прокладкой Серпинского . Это показывает, что вычисления могут быть включены в сборку массивов ДНК, расширяя их возможности за пределы простых периодических массивов. [51]
ДНК-вычисления — это форма параллельных вычислений , в которой используются преимущества множества различных молекул ДНК, чтобы одновременно опробовать множество разных возможностей. [52] Для решения некоторых специализированных задач ДНК-компьютеры быстрее и меньше, чем любой другой компьютер, созданный до сих пор. Более того, было продемонстрировано, что определенные математические вычисления работают на компьютере ДНК.
ДНК-вычисления не предоставляют никаких новых возможностей с точки зрения теории вычислимости , проблемы изучения которой решаемы вычислительно с использованием различных моделей вычислений. Например, если пространство, необходимое для решения задачи, растет экспоненциально с размером задачи ( задачи EXPSPACE ) на машинах фон Неймана , оно все равно растет экспоненциально с размером задачи на машинах ДНК. Для очень больших задач EXPSPACE необходимое количество ДНК слишком велико, чтобы это было практично.
Партнерство между IBM и Калифорнийским технологическим институтом было установлено в 2009 году с целью производства « ДНК-чипов ». [53] Группа Калифорнийского технологического института работает над производством этих интегральных схем на основе нуклеиновых кислот. Один из этих чипов может вычислять целые квадратные корни. [54] Компилятор написан [55] на Perl .
Низкая скорость обработки ДНК-компьютера (время отклика измеряется минутами, часами или днями, а не миллисекундами) компенсируется его способностью выполнять большое количество множественных параллельных вычислений. Это позволяет системе тратить такое же количество времени на сложные вычисления, как и на простые. Это достигается тем, что миллионы или миллиарды молекул одновременно взаимодействуют друг с другом. Однако анализировать ответы, данные ДНК-компьютером, гораздо сложнее, чем цифровым.
{{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка ){{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка ){{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )— Книга начинается с введения в вопросы, связанные с ДНК, основ биохимии, языка и теории вычислений, а затем переходит к продвинутой математической теории вычислений ДНК.