基于Tile自组装模型的最大匹配问题算法研究

doi:10.3969/j.issn.0372-2112.2015.02.009

电子学报 ›› 2015, Vol. 43 ›› Issue (2): 262-268.DOI: 10.3969/j.issn.0372-2112.2015.02.009

基于Tile自组装模型的最大匹配问题算法研究

周旭^1,2, 周炎涛^2,3, 李肯立², 欧阳艾嘉², 潘果²

1. 嘉兴学院数理与信息工程学院, 浙江嘉兴 314001;
2. 湖南大学信息科学与工程学院, 湖南长沙 410082;
3. 湖南大学电气与信息工程学院, 湖南长沙 410082

收稿日期:2013-09-18 修回日期:2014-04-22 出版日期:2015-02-25
- 通讯作者:
- 周炎涛
- 作者简介:
- 周旭 女,1983年生于江苏宿迁,湖南大学博士研究生,研究方向为DNA计算和并行计算. E-mail:zhouxu2006@126.com
- 基金资助:
- 国家自然科学基金重点项目 (No.61133005); 国家自然科学基金 (No.61173013,No.61202109); 湖南省杰出青年基金 (No.12JJ1011); 浙江省教育厅科研计划项目 (No.Y201226110); 湖南省科技厅科技计划项目 (No.2013GK3082,No.2014GK3043); 湖南省教育厅项目 (No.08D092,No.13C333)

Efficient Maximum Matching Problem Algorithms in the Tile Assembly Model

ZHOU Xu^1,2, ZHOU Yan-tao^2,3, LI Ken-li², OUYANG Ai-jia², PAN Guo²

1. College of Mathematics and Information Engineering, Jiaxing University, Jiaxing, Zhejiang 314001, China;
2. College of Information Science and Engineering, Hunan University, Changsha, Hunan 410082, China;
3. College of Electrical and Information Engineering, Hunan University, Changsha, Hunan 410082, China

Received:2013-09-18 Revised:2014-04-22 Online:2015-02-25 Published:2015-02-25
- Supported by:
- Key Program of National Natural Science Foundation of China (No.61133005); National Natural Science Foundation of China (No.61173013, No.61202109); Excellent Youth Foundation of Hunan Province (No.12JJ1011); Project of Scientific Research Project of Zhejiang Education Department (No.Y201226110); Science and Technology Project of Department of Science and Technology of Hunan Provicne (No.2013GK3082, No.2014GK3043); Program of Hunan Education Department (No.08D092, No.13C333)

摘要/Abstract

摘要：

Tile自组装模型作为一种重要的DNA计算模型,在解决NP问题时展现出了巨大优势.文中针对现有最大匹配问题DNA计算算法实验操作复杂,错误率高的缺点,提出了一种基于Tile自组装模型的最大匹配问题新算法.算法所需的Tile分子种类为O(mn),所需生物操作数为O(1),计算时间为O(m),计算空间复杂度为O(mn)(其中m为边数,n为顶点数,且O(m)=O(n²)).与现有的最大匹配问题DNA计算算法相比,本算法不仅可靠性更好,而且更具可操作性.

关键词: DNA计算, Tile自组装模型, 最大匹配问题, NP完全问题, 并行计算

Abstract:

The tile self-assembly model is an important DNA computing model.It's useful for handling the NP problem.Currently,when using the DNA computing to solve the maximum matching problem,it will be hard to experiment and easy to make mistakes.Therefore,based on the tile self-assembly model,a new algorithm for the maximum matching problem is designed.The present algorithm needs O(mn) types of tile molecular,its bio-operation is O(1),the computing time is O(m) and space complexity is O(mn) (where m is the number of edges,n is the number of vertices, O(m)=O(n²)). Compared to the existed algorithms,the proposed algorithm is effectiveness and correctness.

Key words: DNA computing, Tile self-assembly model, maximum matching problem, NP-complete problem, parallel computing

中图分类号:

周旭, 周炎涛, 李肯立, 等. 基于Tile自组装模型的最大匹配问题算法研究[J]. 电子学报, 2015, 43(2): 262-268.

ZHOU Xu, ZHOU Yan-tao, LI Ken-li, et al. Efficient Maximum Matching Problem Algorithms in the Tile Assembly Model[J]. Acta Electronica Sinica, 2015, 43(2): 262-268.

参考文献

[1] ZhangF,Cao J,Hwang K,et al.Ordinal optimized scheduling of scientific workflows in elastic compute clouds[A].Proc 3rd IEEE International Conference on Cloud Computing Technology and Science,2011[C].Athens:IEEE,2011.9-17.
[2] ZhangX Y,Wang S,Niu Y Y,et al.Tissue P systems with cell separation:attacking the partition problem[J].Science China Information Sciences,2011,54(2):293-304.
[3] Adleman L M.Molecular computation of solutions to combinatorial problems[J].Science,1994,266(11):1021-1024.
[4] 俞洋,陆建华,王东方,等.基于DNA/RNA的逻辑门与逻辑运算[J].科学通报,2013,58(2):131-140. Yu Yang,Lu Jian-hua,Wang Dong-huang,et al.DNA/RNA based logic gates and computing[J].Chinese Science Bulletin,2013,58(2):131-140.(in Chinese)
[5] 李菲,许进.一种新型DNA自组装磁珠光电检测系统及其在DNA计算机研制中的应用[J].计算机学报,2013,36(9):1826-1833. Li Fei,Xu Jin.A new photoelectric DNA-Detection platform with assembled magnetic beads and its application on DNA computer[J].Chinese Journal of Computers,2013,36(9):1826-1833.(in Chinese)
[6] Winfree E.Algorithmic self-assembly of DNA[D].Pasadena:California Institute of Technology,1998.
[7] Seeman N C.DNA nanotechnology:Novel DNA constructions[J].Annual Review of Biophysics and Bio-molecular Structure,1998,27(1):225-248.
[8] Brun Y.Effective 3-SAT algorithms in the tile assembly model[J].Natural Computing,2012,11(2):209-229.
[9] 吴帆,李肯立.基于自组装的N皇后问题DNA计算算法[J].电子学报,2013,41(11):2174-2180. Wu Fan,Li Ken-li.An algorithm in tile assembly model for N queen problem[J].Acta Electronica Sinica,2013,41(11):2174-2180.(in Chinese)
[10] 李肯立,罗兴,吴帆,等.基于自组装模型的最大团问题DNA计算算法[J].计算机研究与发展,2013,50(3):666-675. Li Ken-li,Luo Xin,Wu Fan,et al.An algorithm in tile assembly model for maximum clique problem[J].Journal of Computer Research and Development,2013,50(3):666-675.(in Chinese)
[11] 陈治平,李小龙,等.最佳匹配问题的DNA表面计算模型[J].计算机研究与发展,2005,42(7):1241-1246. Chen Zhi-ping,Li Xiao-long,et al.A surface-based DNA algorithm for the perfect matching problem[J].Journal of Computer Research and Development,2005,42(7):1241-1246.(in Chinese)
[12] 周旭,李肯立,乐光学,等.一种最大匹配问题DNA计算算法[J].计算机研究与发展,2011,48(11):2147-2154. Zhou Xu,Li Ken-li,Yue Guang-xue,et.al.A volume molecular solution for the maximum matching problem on DNA-based computing[J].Journal of Computer Research and Development,2011,48(11):2147-2154.(in Chinese)
[13] MaX J,Lombardi F.Synthesis of tile sets for DNA self-assembly[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2008,27(5):963-967.

[1]	袁海英, 曾智勇, 成君鹏. 面向灵活并行度的稀疏卷积神经网络加速器[J]. 电子学报, 2022, 50(8): 1811-1818.
[2]	田春生, 陈雷, 王源, 王硕, 周婧, 张瑶伟, 庞永江, 周冲, 马筱婧, 杜忠, 薛钰. 面向FPGA的布局与布线技术研究综述[J]. 电子学报, 2022, 50(5): 1243-1254.
[3]	王卫杰, 胡少亮, 郑宇腾, 赵振国, 周海京. 并行预处理有限元方法及其在系统级封装结构电磁模拟中的应用[J]. 电子学报, 2021, 49(1): 58-63.
[4]	刘公绪, 史凌峰, 辛东金. 基于FPGA的零误差大数阶乘算法的设计与实现[J]. 电子学报, 2019, 47(5): 1180-1184.
[5]	王卫杰, 陈晓洁, 周海京. 基于区域分解的大规模并行有限元快速算法[J]. 电子学报, 2019, 47(3): 741-747.
[6]	杨林峰, 胡桂莉, 张晨, 张振荣. 基于CPU-GPU协同并行内点算法求解结构化非线性规划[J]. 电子学报, 2019, 47(2): 382-389.
[7]	曲志坚, 陈宇航, 李盘靖, 刘晓红, 李彩虹. 基于多算子协同进化的自适应并行量子遗传算法[J]. 电子学报, 2019, 47(2): 266-273.
[8]	冯晓, 戴紫彬, 蔡路亭, 李伟. 基于Amdahl定律扩展的多核处理器性能模型研究[J]. 电子学报, 2017, 45(6): 1424-1430.
[9]	卞琛, 于炯, 英昌甜, 修位蓉. 并行计算框架Spark的自适应缓存管理策略[J]. 电子学报, 2017, 45(2): 278-284.
[10]	王艳钗, 张会, 董亚非. DNA纳米颗粒共聚体在图的连通度问题中的应用[J]. 电子学报, 2016, 44(7): 1561-1566.
[11]	潘卫国, 何宁, 薛健, 吕科, 翟锐, 代双凤. 海量超声数据体可视化研究[J]. 电子学报, 2016, 44(2): 472-478.
[12]	徐红, 黄朝耿, 宋洪波, 周志光, 李刚. 并行计算的全通数字滤波器结构[J]. 电子学报, 2015, 43(10): 2034-2039.
[13]	王勇献, 张理论, 车永刚, 徐传福, 刘巍, 程兴华. 结构网格CFD应用程序在天河超级计算机上的高效并行与优化[J]. 电子学报, 2015, 43(1): 36-44.
[14]	吴帆, 李肯立. 基于自组装的N皇后问题DNA计算算法[J]. 电子学报, 2013, 41(11): 2174-2180.
[15]	杨玉星;王世英. Ménage问题的一种粘贴DNA算法[J]. 电子学报, 2012, 40(4): 751-755.

基于Tile自组装模型的最大匹配问题算法研究

Efficient Maximum Matching Problem Algorithms in the Tile Assembly Model

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics