A new approach to advance the DNA computing Academic Article uri icon


  • It has been evidenced that DNA computing can solve those problems which are currently intractable on even the fastest electronic computers. The algorithm design for DNA computing, however, is not straightforward. Both a significant knowledge of the DNA molecule and a strong background in computer engineering are required to develop efficient DNA computing algorithms. The existing models based on which a few DNA computing algorithms were developed are not sufficiently powerful and robust to attract potential users. In this paper, a new DNA computing model is introduced based on which new algorithms are developed to solve the 3-Coloring problem. These new algorithms are presented as vehicles for demonstrating the advantages of the new model, and they can be expanded to solve other NP-complete problems. Our new algorithms can significantly speed up computation and therefore achieve a better time performance. Furthermore, with the given resource, our algorithms can solve problems of much greater size as compared to existing DNA computing algorithms. In addition, the error rate can be greatly reduced by applying our new algorithms. All of the advantages provided by the new model make DNA computing very efficient and attractive in solving computational intense problems. 2003 Elsevier B.V. All rights reserved.

published proceedings

  • Applied Soft Computing

author list (cited authors)

  • Qiu, Z. F., & Lu, M. i.

citation count

  • 8

complete list of authors

  • Qiu, Zhiquan Frank||Lu, Mi

publication date

  • September 2003