×

Error-resilient DNA computation. (English) Zbl 0931.68052

Summary: 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.

MSC:

68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
92D20 Protein sequences, DNA sequences
Full Text: DOI

References:

[1] Adleman, Science 266 pp 1021– (1994) · doi:10.1126/science.7973651
[2] Factoring: The DNA solution, Advances in Cryptography?Asiacrypt ’94 Proc, Lecture Notes in Computer Science, Springer, Berlin, 1994.
[3] ? A Universal molecular computer,? DNA-Based Computing, DIMACS Series on Discrete Mathematics and Theoretical Computer Science, and (Editors), American Mathematical Society, Providence, RI, 1995, Vol. 27, pp. 29-36.
[4] Beaver, Comput Biol 2(1) pp 1– (1995) · doi:10.1089/cmb.1995.2.1
[5] and ? Breaking DES using a molecular computer,? DNA-Based Computing, DIMACS Series on Discrete Mathematics and Theoretical Computer Science, and (Editors), American Mathematical Society, Providence, RI, 1995, Vol. 27, pp. 37-66. · doi:10.1090/dimacs/027/04
[6] Boneh, Discrete Appl Math 71 pp 79– (1996) · Zbl 0906.68071 · doi:10.1016/S0166-218X(96)00058-3
[7] Boneh, Proc 2nd Annual DIMACS Workshop on DNA Computing (1996)
[8] Feige, Proc 22nd ACM Symp on Theory of Computing pp 128– (1990)
[9] Lower bounds for the complexity for reliable boolean circuits with noisy gates, in Proc 32nd IEEE Symp Foundations of Computer Science, 1991, pp. 594-601.
[10] Kenyon, Random Struct Alg 5 pp 453– (1994) · Zbl 0811.68101 · doi:10.1002/rsa.3240050306
[11] Kenyon, Internat J Found Comput Sci 1 pp 1– (1990) · Zbl 0725.94014 · doi:10.1142/S0129054190000023
[12] Lipton, Science 268 pp 542– (1995) · doi:10.1126/science.7725098
[13] National Bureau of Standards, Data Encryption Standard, U.S. Department of Commerce, FIPS, pub. 46, January 1977.
[14] Nisan, SIAM J Comput 20 pp 999– (1991) · Zbl 0737.68028 · doi:10.1137/0220062
[15] Pippenger, Proc 26th IEEE Symp on Foundations of Computer Science pp 30– (1985)
[16] Reif, Proc 7th ACM Symp on Parallel Algorithms and Architecture (1995)
[17] and Reliable computation with noisy circuits and decisions trees?A general n log n lower bound, Proc 32nd IEEE Symp on Foundations of Computer Science, 1991, pp. 602-611.
[18] Rivest, J Comput Syst Sci 20 pp 396– (1980) · Zbl 0443.68043 · doi:10.1016/0022-0000(80)90014-8
[19] Rooss, Inform and Comput 131 pp 95– (1996) · Zbl 1077.68647 · doi:10.1006/inco.1996.0094
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.