Special Issue: Advances in Parallel and Distributed Computational ModelsNo Access

PROCEDURES FOR COMPUTING THE MAXIMUM WITH DNA

Department of Computer Science and Electronics, Kyushu Institute of Technology, 680-4 Kawazu, Iizuka, Fukuoka 820-8502, Japan

Search for more papers by this author

SATOSHI KAMIO

Department of Computer Science and Electronics, Kyushu Institute of Technology, 680-4 Kawazu, Iizuka, Fukuoka 820-8502, Japan

Search for more papers by this author

, and

AKIKO TAKEHARA

Department of Computer Science and Electronics, Kyushu Institute of Technology, 680-4 Kawazu, Iizuka, Fukuoka 820-8502, Japan

Search for more papers by this author

https://doi.org/10.1142/S0129054107004796Cited by:1 (Source: Crossref)

Abstract

In recent works for high performance computing, computation with DNA strands, that is, DNA computing, has considerable attention as one of non-silicon based computing. In this paper, we propose three procedures for computing the maximum of n binary numbers of m bits, which are represented with O(mn) DNA strands. The first procedure computes the maximum of the binary numbers in O(m) steps using O(n) kinds of DNA strands. The second and third procedures also compute the maximum in O(log n) and O(1) steps using O(mn) and O(mn²) kinds of DNA strands, respectively.

Keywords:

References

L. M. Adleman, Science 266, 1021 (1994), DOI: 10.1126/science.7973651. Crossref, Web of Science, Google Scholar
L. M. Adleman, Scientific American 279(2), 54 (1998). Crossref, Web of Science, Google Scholar
E. B. Baum and D. Boneh , Running dynamic programming algorithms on a DNA computer , Proceedings of the Second Annual Meeting on DNA Based Computers ( 1996 ) . Google Scholar
E. Dekel and S. Sahni, Operations Research 31(1), 24 (1983). Crossref, Web of Science, Google Scholar
P. Frisco, Romanian Journal of Information Science and Technology ROMJIST 2(3), 113 (2000). Google Scholar
A. G. Frutoset al., Nucleic Acids Research 25(23), 4748 (1997), DOI: 10.1093/nar/25.23.4748. Crossref, Web of Science, Google Scholar
A. Fujiwara, K. Matsumoto and W. Chen, International Journal of Foundations of Computer Science 15(3), 461 (2004), DOI: 10.1142/S0129054104002546. Link, Web of Science, Google Scholar
F. Guarnieri, M. Fliss and C. Bancroft, Science 273(5272), 220 (1996), DOI: 10.1126/science.273.5272.220. Crossref, Web of Science, Google Scholar
V. Gupta, S. Parthasarathy and M. J. Zaki, Arithmetic and logic operations with DNA, Proceedings of the 3rd DIMACS Workshop on DNA Based Computers (1997) pp. 212–220. Google Scholar
H. Hug and R. Schuler, DNA-based parallel computation of simple arithmetic, Proceedings of the 7th International Meeting on DNA Based Computers (DNA7) (2001) pp. 159–166. Google Scholar
R. J. Lipton, Science 268, 542 (1995), DOI: 10.1126/science.7725098. Crossref, Web of Science, Google Scholar
R. B. Merrifield, Journal of the American Chemical Society 85, 2149 (1963), DOI: 10.1021/ja00897a025. Crossref, Web of Science, Google Scholar
Q. Ouyanget al., Science 278, 446 (1997), DOI: 10.1126/science.278.5337.446. Crossref, Web of Science, Google Scholar
G. Pǎun , G. Rozeberg and A. Salomaa , DNA computing ( Springer-Verlag , 1998 ) . Crossref, Google Scholar
Z. F. Qiu and M. Lu, Arithmetic and logic operations for DNA computers, Proceedings of the Second IASTED International conference on Parallel and Distributed Computing and Networks (1998) pp. 481–486. Google Scholar
Z. F. Qiu and M. Lu, Take advantage of the computing power of DNA computers, Proceedings of the Third Workshop on Bio-Inspired Solutions to Parallel Processing Problems, IPDPS 2000 Workshops (2000) pp. 570–577. Google Scholar
J. H. Reif, Algorithmica 25(2-3), 142 (1995), DOI: 10.1007/PL00008272. Crossref, Web of Science, Google Scholar
Y. Shiloach and U. Vishkin, Journal of Algorithms 2(1), 88 (1981), DOI: 10.1016/0196-6774(81)90010-9. Crossref, Web of Science, Google Scholar
A. Suyamaet al., Computational Molecular Biology (2000) pp. 12–13. Google Scholar
H. Yoshida and A. Suyama. Solution to 3-SAT by breadth first search. American Mathematical Society, pp. 9–22, 2000 . Google Scholar