کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
2076007 1544989 2014 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
DNA strand displacement system running logic programs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات مدل‌سازی و شبیه سازی
پیش نمایش صفحه اول مقاله
DNA strand displacement system running logic programs
چکیده انگلیسی

The paper presents a DNA-based computing model which is enzyme-free and autonomous, not requiring a human intervention during the computation. The model is able to perform iterated resolution steps with logical formulae in conjunctive normal form. The implementation is based on the technique of DNA strand displacement, with each clause encoded in a separate DNA molecule. Propositions are encoded assigning a strand to each proposition p, and its complementary strand to the proposition ¬p; clauses are encoded comprising different propositions in the same strand. The model allows to run logic programs composed of Horn clauses by cascading resolution steps. The potential of the model is demonstrated also by its theoretical capability of solving SAT. The resulting SAT algorithm has a linear time complexity in the number of resolution steps, whereas its spatial complexity is exponential in the number of variables of the formula.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Biosystems - Volume 115, January 2014, Pages 5–12
نویسندگان
, , ,