YIN Zhixiang, CUI Jianzhong, YANG Jing. Integer Programming Problem Based on Plasmid DNA Computing Model[J]. Chinese Journal of Electronics, 2017, 26(6): 1284-1288. doi: 10.1049/cje.2017.07.013
Citation: YIN Zhixiang, CUI Jianzhong, YANG Jing. Integer Programming Problem Based on Plasmid DNA Computing Model[J]. Chinese Journal of Electronics, 2017, 26(6): 1284-1288. doi: 10.1049/cje.2017.07.013

Integer Programming Problem Based on Plasmid DNA Computing Model

doi: 10.1049/cje.2017.07.013
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
  • 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.
  • loading
  • 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.
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (126) PDF downloads(251) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return