An O(1.414\+n) Volume Molecular Solutions for the Exact Cover Problem on DNA-Based Supercomputing

Li Kenli; Liu Jie; Yang Lei; Liu Wenbin

Journal of Computer Research and Development > 2008 > 45(10): 1782-1788.

Li Kenli, Liu Jie, Yang Lei, Liu Wenbin. An O(1.414\+n) Volume Molecular Solutions for the Exact Cover Problem on DNA-Based Supercomputing[J]. Journal of Computer Research and Development, 2008, 45(10): 1782-1788.

Citation:

PDF (740 KB)

An O(1.414\+n) Volume Molecular Solutions for the Exact Cover Problem on DNA-Based Supercomputing

1(College of Computer and Communication, Hunan University, Changsha 410082) 2(College of Computer Science and Engineering, Wenzhou University, Wenzhou, Zhejiang 325027)

More Information

Published Date: October 14, 2008

Graphical Abstract

Abstract

Abstract

The scalability problem in DNA computer has been one of the important research areas in DNA computing. According to the requirement of the DNA parallel computing for exact cover problem, a DNA model for good scalability is proposed, which is based on the biological operations in the Adleman-Lipton model and the solution space of stickers in the sticker-based model by simultaneously taking the method of fluorescence labeling and the technique of gel electrophoresis into the model. Based on this model, a DNA-based algorithm for the exact cover problem, by making use of the strategem of divide-and-conquer, is also proposed which consists of three sub-algorithms: Init(), IllegalRemove(), and ParallelSeacher(). Compared with by far the best molecular algorithm for the exact cover problem with n variables and m sets in which O(2\+n) DNA strands are used, this algorithm can solve the same problem only using O(1.414\+n) DNA strands on the condition of not varying the time complexity. Therefore, the cardinal number of the exact cover problem that can be theoretically resolved in a test tube may be enlarged from 60 to 120, and thus the proposed algorithm is an improved result over the past researches.
- DNA computer,
- NP-complete problem,
- exact cover problem,
- divide and conquer,
- DNA super-computing

FullText(HTML)

References (0)

[1]	Zheng Han, Wang Ning, Ma Xinzhu, Zhang Hong, Wang Zhihui, Li Haojie. Point Cloud Scene Flow Propagation Update Method Based on Neighborhood Consistency[J]. Journal of Computer Research and Development, 2023, 60(2): 426-434. DOI: 10.7544/issn1000-1239.202110745
[2]	Zhang Rui, Li Jintao. A Survey on Algorithm Research of Scene Parsing Based on Deep Learning[J]. Journal of Computer Research and Development, 2020, 57(4): 859-875. DOI: 10.7544/issn1000-1239.2020.20190513
[3]	Lin Xin, Tian Xin, Ji Yi, Xu Yunlong, Liu Chunping. Scene Graph Generation Based on Shuffle Residual Context Information[J]. Journal of Computer Research and Development, 2019, 56(8): 1721-1730. DOI: 10.7544/issn1000-1239.2019.20190329
[4]	Li Zhen, Tian Junfeng, and Yang Xiaohui. Dynamic Trustworthiness Evaluation Model of Software Based on Checkpoint's Classification Attributes[J]. Journal of Computer Research and Development, 2013, 50(11): 2397-2405.
[5]	Xie Zhao, Ling Ran, and Wu Kewei. Incremental Learning Towards Scene Features in Independent Subspace[J]. Journal of Computer Research and Development, 2013, 50(11): 2287-2294.
[6]	Wang Hongxin, Yang Deli, Jiang Nan, Ma Hui. An Online Mobile Payment Model with Simplified Terminal Authentication[J]. Journal of Computer Research and Development, 2013, 50(2): 291-301.
[7]	Qin Lei, Gao Wen. Scene Image Categorization Based on Content Correlation[J]. Journal of Computer Research and Development, 2009, 46(7): 1198-1205.
[8]	Wu Lingda, Gao Yu, and Wei Yingmei. A Survey of Interactive Rendering of Large-Scale and Complex Scenes[J]. Journal of Computer Research and Development, 2007, 44(9): 1579-1587.
[9]	Mao Chengying and Lu Yansheng. A Simplified Method for Generating Test Path Cases in Branch Testing[J]. Journal of Computer Research and Development, 2006, 43(2): 321-328.
[10]	Pu Jiantao and Zha Hongbin. Research on Visibility for Large-Scale and Complex Scenes[J]. Journal of Computer Research and Development, 2005, 42(2): 236-246.