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]	Li Song, Cao Wenqi, Hao Xiaohong, Zhang Liping, Hao Zhongxiao. Collective Spatial Keyword Query Based on Time-Distance Constrained and Cost Aware[J]. Journal of Computer Research and Development, 2025, 62(3): 808-819. DOI: 10.7544/issn1000-1239.202330815
[2]	Wei Junyu, Zhang Guangyan, Chen Junchao. Data-Pattern-Aware Low-Cost Cloud Log Storage Systems[J]. Journal of Computer Research and Development, 2023, 60(11): 2442-2452. DOI: 10.7544/issn1000-1239.202330178
[3]	Lu Min, Huang Yalou, Xie Maoqiang, Wang Yang, Liu Jie, Liao Zhen. Cost-Sensitive Listwise Ranking Approach[J]. Journal of Computer Research and Development, 2012, 49(8): 1738-1746.
[4]	Wang Weizheng, Kuang Jishun, You Zhiqiang, Liu Peng. A Low-Power and Low-Cost BIST Scheme Based on Capture in Turn of Sub-Scan Chains[J]. Journal of Computer Research and Development, 2012, 49(4): 864-872.
[5]	Xiao Fangxiong, Huang Zhiqiu, Cao Zining, Yuan Min, and Zhang Junhua. Describing and Cost Analyzing of Web Services Composition Using PPA[J]. Journal of Computer Research and Development, 2009, 46(5): 832-840.
[6]	Zhao Jia, Han Jun, Zeng Xiaoyang, and Han Lin. A Two-Dimensional Parity-Based Concurrent Error Detection Method for AES Against Differential Fault Attack and Its VLSI Implementation[J]. Journal of Computer Research and Development, 2009, 46(4): 593-601.
[7]	Tong Yuanman, Wang Zhiying, Dai Kui, and Lu Hongyi. A DPA and HO-DPA Resistant Implementation of AES[J]. Journal of Computer Research and Development, 2009, 46(3): 377-383.
[8]	Liu Zhenglin, Han Yu, Zou Xuecheng, and ChenYicheng. Power Analysis Attacks Against AES Based on Maximal Bias Signal[J]. Journal of Computer Research and Development, 2009, 46(3): 370-376.
[9]	He Xiaoyang and Wang Yasha. Model-Based Methods for Software Cost Estimation[J]. Journal of Computer Research and Development, 2006, 43(5): 777-783.
[10]	Wu Min, Zeng Xiaoyang, Han Jun, Ma Yongxin, Wu Yongyi, and Zhang Guoquan. A Low Cost RSA Chip Design Based on CRT[J]. Journal of Computer Research and Development, 2006, 43(4): 639-645.