全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...
电子学报  2015 

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

DOI: 10.3969/j.issn.0372-2112.2015.02.009, PP. 262-268

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

Full-Text   Cite this paper   Add to My Lib

Abstract:

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

References

[1]  吴帆,李肯立.基于自组装的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)
[2]  李肯立,罗兴,吴帆,等.基于自组装模型的最大团问题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)
[3]  陈治平,李小龙,等.最佳匹配问题的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)
[4]  周旭,李肯立,乐光学,等.一种最大匹配问题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)
[5]  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.
[6]  Seeman N C.DNA nanotechnology:Novel DNA constructions[J].Annual Review of Biophysics and Bio-molecular Structure,1998,27(1):225-248.
[7]  Brun Y.Effective 3-SAT algorithms in the tile assembly model[J].Natural Computing,2012,11(2):209-229.
[8]  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.
[9]  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.
[10]  Adleman L M.Molecular computation of solutions to combinatorial problems[J].Science,1994,266(11):1021-1024.
[11]  俞洋,陆建华,王东方,等.基于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)
[12]  李菲,许进.一种新型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)
[13]  Winfree E.Algorithmic self-assembly of DNA[D].Pasadena:California Institute of Technology,1998.

Full-Text

Contact Us

[email protected]

QQ:3279437679

WhatsApp +8615387084133