×

DNA models and algorithms for NP-complete problems. (English) Zbl 0921.68028

Summary: A goal of research on DNA computing is to solve problems that are beyond the capabilities of the fastest silicon-based supercomputers. Adleman and Lipton present exhaustive search algorithms for 3Sat and 3-coloring, which can only be run on small instances and, hence, are not practical. In this paper, we show how improved algorithms can be developed for the 3-coloring and independent set problems. Our algorithms use only the DNA operations proposed by Adleman and Lipton, but combine them in more powerful ways and use polynomial preprocessing on a standard computer to tailor them to the specific instance to be solved. The main contribution of this paper is a more general model of DNA algorithms than that proposed by Lipton. We show that DNA computation for NP-complete problems can do more than just exhaustive search. Further research in this direction will help determine whether or not DNA computing is viable for NP-hard problems. A second contribution is the first analysis of errors that arise in generating the solution space for DNA computation. \(\copyright\) Academic Press.

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68P10 Searching and sorting

Keywords:

DNA computing
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adleman, L. M., Molecular computation of solutions to combinatorial problems, Science, 266, 1021-1024 (1994)
[3] Amos, M.; Gibbons, A.; Hodgson, D., Research Report (January 1996)
[4] Beigel, R.; Eppstein, D., 3-coloring in time \(O^n\), Proc. 36th Symposium on Foundations of Computer Science (1995), IEEE Computer Society Press: IEEE Computer Society Press Los Alamitos, p. 444-453 · Zbl 0938.68940
[5] Boneh, D.; Dunworth, D.; Lipton, R. J.; Sgall, J., Technical Report (1995)
[6] Fodor, S. P.; Read, J. L.; Pirrung, M. C.; Stryer, L.; Lu, A. T.; Solas, D., Light-directed, spatially addressable parallel chemical synthesis, Science, 251, 767-773 (1991)
[7] Knuth, D. E., Mariages stables et leurs relations avec d’autres problèmes combinatoires (1976), Presses Univ. Montreal · Zbl 0358.68057
[8] Grimmett, G. R.; Stirzaker, D. R., Probability and Random Processes (1992), Oxford Univ. Press: Oxford Univ. Press Oxford · Zbl 0759.60002
[9] Harary, F., Graph Theory (1969), Addisson-Wesley: Addisson-Wesley Reading · Zbl 0797.05064
[10] Lipton, R. J., DNA solution of hard combinatorial problems, Science, 268, 542-548 (1995)
[11] Motwani, R.; Raghavan, P., Randomized Algorithms (1995), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0849.68039
[12] Pease, A. C.; Solas, D.; Sullivan, E. J.; Cronin, M. T.; Holmes, C. P.; Fodor, S. P., Light-directed oligonucleotide arrays for rapid DNA sequence analysis, Proc. Natl. Acad. Sci. USA, 91, 5022-5026 (1994)
[13] Pinelis, I., An approach to inequalities for the distributions of infinite-dimensional martingales, Probability in Banach Spaces (1992), Birkhäuser: Birkhäuser Basel, p. 128-134 · Zbl 0793.60016
[14] Schiermeyer, I., Solving 3-satisfiability in less than \(1.579^n\), Proc. 6th Workshop on Computer Science Logic (1993), Springer-Verlag: Springer-Verlag New York/Berlin, p. 379-394 · Zbl 0788.68066
[15] Sury, B., Sum of the reciprocals of the binomial coefficients, Europ. J. Combin., 14, 351-353 (1993) · Zbl 0783.05002
[16] Williams, D., Probability with Martingales (1991), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0722.60001
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.