Premium
Error‐resilient DNA computation
Author(s) -
Karp Richard M.,
Kenyon Claire,
Waarts Orli
Publication year - 1999
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199910/12)15:3/4<450::aid-rsa12>3.0.co;2-2
Subject(s) - algorithm , merge (version control) , computer science , computation , true quantified boolean formula , reduction (mathematics) , mathematics , parallel computing , geometry
The DNA model of computation, with test tubes of DNA molecules encoding bit sequences, is based on three primitives: Extract‐A‐Bit, which splits a test tube into two test tubes according to the value of a particular bit x , Merge‐Two‐Tubes, and Detect‐Emptiness. If perfect, these operations can test the satisfiability of any boolean formula in linear time. However, in reality the Extract operation is faulty and misclassifies some of the strands. We consider the following reduction problem: given an algorithm based on perfect Extract, Merge, and Detect operations, convert it to an algorithm that is correct with high probability even though the Extract operation is faulty. The fundamental problem in such a reduction is the simulation of a single highly reliable Extract operation. We determine the number of faulty Extract operations to simulate a highly reliable Extract operation, with matching upper and lower bounds (up to a constant factor). We then propose a reduction to convert any algorithm based on error‐free operations to an error‐resilient algorithm. In the case of simple n ‐variable boolean functions, Conjunction, Disjunction, and Parity, we prove that our error‐resilient algorithms are optimal. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 15, 450–466, 1999