Integer Programming Problem Based on Plasmid DNA Computing Model

YIN Zhixiang; CUI Jianzhong; YANG Jing

doi:10.1049/cje.2017.07.013

Volume 26 Issue 6

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2017 > 26(6): 1284-1288

YIN Zhixiang, CUI Jianzhong, YANG Jing, “Integer Programming Problem Based on Plasmid DNA Computing Model,” Chinese Journal of Electronics, vol. 26, no. 6, pp. 1284-1288, 2017, doi: 10.1049/cje.2017.07.013

Citation:

YIN Zhixiang, CUI Jianzhong, YANG Jing, “Integer Programming Problem Based on Plasmid DNA Computing Model,” Chinese Journal of Electronics, vol. 26, no. 6, pp. 1284-1288, 2017, doi: 10.1049/cje.2017.07.013

Citation:

PDF( 213 KB)

Integer Programming Problem Based on Plasmid DNA Computing Model

doi: 10.1049/cje.2017.07.013

1.
School of Mathematics and Big Data, Anhui University of Science and Technology, Huainan 232001, China;
2.
Huainan Union University, Huainan 232001, China

Funds: This work is supported by the National Natural Science Foundation of China (No.61672001).

More Information

Corresponding author: YANG Jing (corresponding author) was born in 1980, PH.D., associate professor. Her research interests include combinatorial optimization and DNA computer, graph theory, and protein structure prediction. (Email:jyangh82@163.com)
Received Date: 2014-04-12
Rev Recd Date: 2015-07-02
Publish Date: 2017-11-10

Abstract

Abstract

A DNA algorithm by operating on plasmids was presented to solve a special integer programming, a typical hard computing problem. The DNA algorithm employed double-stranded molecules to encode variables of 0-1 programming problem, the encoded DNA molecules were inserted into circular plasmids as foreign DNA molecules. Followed by, a series of enzymatic treatments to plasmids were performed in order to find feasible solutions to the given problem. The final optimum was obtained by applying founded feasible solutions to object function. Compared with other DNA algorithms of integer programming problem, the proposed algorithm is simple, error-resistant, above all, feasible. Our work clearly showed the distinct advantages of plasmid DNA computing model when solving integer related programming problem.
- DNA computing,
- 0-1 programming,
- Plasmid

FullText(HTML)

References(16)

References

L.M. Adleman, "Molecular computation of solutions to combinatorial froblems", Science, Vol.266, pp.1021-1024, 1994.

S. Roweis, E. Winfree, R. Burgoyne, et al., "A stickerbased model for DNA computation", Journal of Computational Molecular Cell Biology, Vol.5, No.4, pp.615-629, 1998.

C. Mao, T.H. LaBen, J.H. Relf, et al., "Logical computation using algorithmic self-assembly of DNA triple-crossover molecules", Nature, Vol.407, No.6803, pp.493-496, 2000.

C. Zhen, Y.F. Huang, J. Xu, et al., "Algorithm of elliptic cure Diffe-Hellman key exchange based on DNA tile self-assembly", Journal of Computional and Theoretical Nanoscience, Vol.7, No.5, pp.856-861, 2010.

L. Qian and E. Winfree, "Scaling up digital circuit computation with DNA strand displacement cascades", Science, Vol.332, No.6034, pp.1196-1201, 2011.

W.L. Chang, M. Guo and M.H. Ho, "Fast parallel molecular algorithms for DNA-based computation:Factoring integers", IEEE Transactions on Nanobioscience, Vol.4, No.2, pp.149-163, 2005.

W.G. Li and Y.S. Ding, "A microfluidic systems-based DNA algorithm for solving special 0-1 integer programming problem", Applied Mathematics and Computation, Vol.185, No.2, pp.1160-1170, 2007.

X.L. Wang, Z. Bao, J. Hu, et al., "Solving the SAT problem using a DNA computing algorithm based on ligase chain reaction", Biosystems, Vol.91, No.1, pp.117-125, 2008.

H.Y. Zhang and X.Y. Liu, "A CLIQUE algorithm using DNA computing techniques based on closed-circle DNA sequences", Biosystems, Vol.105, No.1, pp.73-82, 2011.

Z.C. Wang, Y. Zhang, W. Zhou, et al., "Solving traveling salesman problem in the Adleman-Lipton model", Applied Mathematics and Computation, Vol.219, No.4, pp.2267-2270, 2012.

W.L. Chang, K.Y. Lin, J.C. Chen, et al., "Molecular solutions of the RSA public-key cryptosystem on a DNA-based computer", The Journal of Supercomputing, Vol.61, No.3, pp.642-672, 2012.

Z.C. Wang, D. Huang, H. Meng, et al., "A new fast algorithm for solving the minimum spanning tree problem based on DNA molecules computation", Biosystems, Vol.114, No.1, pp.1-7, 2013.

T. Head, "Computing with DNA by operating on Plasmids", BioSystemsm, Vol.57, No.2, pp.87-93, 2000.

T. Murakami and Y. Sunada, "Plasmid DNA gene therapy by electroporation:Principles and recent advances", Current Gene Vol.11, No.6, pp.447-56, 2011.

M. Carbone, P. Gromov and E. Prusinkiewicz, "Circular suggestions for DNA computing", Pattern Formation in Biology, Vision and Dynamics, World Scientific, Singapore London, pp.1-59, 2000.

W.Y. Chung, C.P. Chu and K.R. Wu, "Molecular solutions to the binary integer programming problem based on DNA computation", Biosystems, Vol.83, No.1, pp.56-66, 2006.

Relative Articles

Supplements(0)

Cited By

Proportional views