JOURNAL OF LIGHT INDUSTRY

CN 41-1437/TS  ISSN 2096-1553

×
“关于规范使用生成式人工智能工具的启事

基于二维DNA分子tiler自组装求解最大团问题

冯婷 ,  张倩 ,  董亚非

downloadPDF
冯婷, 张倩, 董亚非. 基于二维DNA分子tiler自组装求解最大团问题[J]. 轻工学报, 2011, 26(4): 94-97. doi: 10.3969/j.issn.1004-1478.2011.04.022
引用本文: 冯婷, 张倩, 董亚非. 基于二维DNA分子tiler自组装求解最大团问题[J]. 轻工学报, 2011, 26(4): 94-97. doi: 10.3969/j.issn.1004-1478.2011.04.022
shu
FENG Ting, ZHANG Qian and DONG Ya-Fei. The solution to the maximum clique problem based on two-dimensional DNA tiles self-assemble[J]. Journal of Light Industry, 2011, 26(4): 94-97. doi: 10.3969/j.issn.1004-1478.2011.04.022
Citation: FENG Ting, ZHANG Qian and DONG Ya-Fei. The solution to the maximum clique problem based on two-dimensional DNA tiles self-assemble[J]. Journal of Light Industry, 2011, 26(4): 94-97. doi: 10.3969/j.issn.1004-1478.2011.04.022
shu

基于二维DNA分子tiler自组装求解最大团问题

  • 陕西师范大学 生命科学学院, 陕西 西安 710062;

  • 陕西师范大学 计算机科学学院, 陕西 西安 71006

    • 通讯作者: 董亚非

  • 基金项目: 国家自然科学基金项目(60970005)
    陕西师范大学2008年重点项目

  • 中图分类号: TP301

The solution to the maximum clique problem based on two-dimensional DNA tiles self-assemble

  • College of Life Sci., Shaanxi Normal Univ., Xi'an 710062, China;

  • College of Comp. Sci., Shaanxi Normal Univ., Xi'an 710062, China

    • Corresponding author: DONG Ya-Fei,
  • Received Date: 2011-05-06
    Available Online: 2011-07-15

    CLC number: TP301

  • 摘要: 针对常用算法在求解完全NP问题中最大团问题时,存在实验操作步骤过多、活体内不易操作以及环化效率不高等问题,设计了一种用二维DNA(k-臂DNA分子)结构来解决最大团问题的方法.该方法将二维DNA分子设计为分子tiler,通过二维DNA分子构建三维DNA图结构并建立计算模型,以减少解决问题所需的时间和步骤.该算法是求解最大团问题的一种可以降低复杂度的新算法,对DNA计算和DNA计算机的研究是一次有意义的实践.
    Abstract: Because there are some disadvantages of traditional algorithms in solving maximum clique problem-one of the NP complete problems,such as too many experimental steps,uneasiness to operate in vivo,and low cyclization efficiency,a 2D DNA(k-arm DNA molecule) structure was designed to solve the maximum clique problem.In order to reduce the time and steps required in resolving this problem,the method is that the 2D DNA molecular was designed as molecular tiles and the computation model was obtained by using the 3D DNA tiles to build the 3D DNA structure chart.This algorithm reduces the complexity of calculation for solving the maximum clique problem,and it is also a meaningful practice for DNA computing and DNA computer research.
    1. [1]

      张成,杨静,许进,等.缩短法计算模型求解最大独立集问题[J].科学通报,2009,54(24):3913.

    2. [2]

      崔光照,周君和,王延峰.DNA计算中的编码序列设计问题[J].郑州轻工业学院学报:自然科学版,2007,22(2/3):77.

    3. [3]

      Adleman L M. Molecular computation of solutions to com bination problems[J]. Science, 1994,266(11):1021.

    4. [4]

      Karp R M. Reducibility among combinatorial problems[C]//Proc of Complexity of Comp Comp, New York:Ple num Press, 1972:85-103.

    5. [5]

      Flor E N. A spatiotemporal data model for incorporating time in geographic information systems[D]. South Flori da:University of South Florida,2001.

    6. [6]

      周晓晓,白杨.关于最大团问题的一种新算法[J].电脑知识与技术,2008(8):708.

    7. [7]

      张社民,方刚.连通度问题的三维DNA结构进化算法[J].计算机工程与应用,2007,43(7):41.

    8. [8]

      Holliday R. Induced mitotic crossing-over in relation to genetic replication in synchronously dividing cells of Usti lago Maydis[J]. Genet Res, 1965(10):104.

    9. [9]

      Seeman N C, Wang H, Liu B, et al. The perils of polynu leotides:the experimental gap between the design and as sembly of unusual DNA structures[C]//Proc of 2nd An nual Meeting on DNA Based Computers. Washington DC:American Mathematicas Society, 1996:215-233.

    10. [10]

      Garzon M,Deaton R,Nino L F. et al. Genome encoding problem for DNA computing[C]//Proc of the 3rd DI MACS Workshop on DNA-based Computing. Washington DC:American Mathematicas Society, 1997:230-237.

    11. [11]

      张凯,耿修堂,肖建华,等.DNA编码问题及其复杂性研究[J].计算机应用研究,2008(11):3264.

    12. [12]

      孙伟,尤加字,江宏,等.纳米粒子标记DNA探针的制备与检测应用[J].中国卫生检验杂志,2005,15(8):1008.

    13. [13]

      Elghanian R,Storhoff J J, Mirkin C A. Selective colori metric detection of polynucleotides based on the distance-dependentoptical properties of goldnanoparticles[J]. Sci ence, 1997,277(5329):1078.

    14. [14]

      Alivisatos A P,Johasson K P,Peng X G,et al. Organiza tion of nanocrystal molecules' using DNA[J]. Nature, 1996,382(6592):609.

    15. [15]

      方刚,张社民,许进.连通度问题的三维DNA图结构解法[J].系统工程与电子技术,2006,28(1):l001

    1. [1]

      吴靖娜 , 林泽烨 , 苏筱 , 张任翔 , 陈晓婷 , 潘南 . 龙须菜渣纤维素/纳米纤维素及其水凝胶的制备和性能研究. 轻工学报, 2024, 39(6): 49-56. doi: 10.12187/2024.06.006

    2. [2]

      王春琼 , 刘凯 , 谢永辉 , 张轲 , 刘春明 , 张晓伟 , 孙浩巍 , 陈丹 . 烟草花叶病毒胶体金检测试纸条的制备与性能评价. 轻工学报, 2025, 40(1): 90-97. doi: 10.12187/2025.01.011

    3. [3]

      楚文娟 , 郭丽霞 , 程东旭 , 王红霞 , 崔廷 , 冯银龙 , 王建民 , 鲁平 . 基于K-means聚类及模糊判别的卷烟包灰性能综合评价方法. 轻工学报, 2024, 39(6): 93-100. doi: 10.12187/2024.06.011

  • 加载中
WeChat 点击查看大图
计量
  • PDF下载量:  27
  • 文章访问数:  1295
  • 引证文献数: 0
文章相关
  • 通讯作者:  董亚非,
  • 收稿日期:  2011-05-06
  • 刊出日期:  2011-07-15
通讯作者: 陈斌, bchen63@163.com
  • 1. 

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

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索
冯婷, 张倩, 董亚非. 基于二维DNA分子tiler自组装求解最大团问题[J]. 轻工学报, 2011, 26(4): 94-97. doi: 10.3969/j.issn.1004-1478.2011.04.022
引用本文: 冯婷, 张倩, 董亚非. 基于二维DNA分子tiler自组装求解最大团问题[J]. 轻工学报, 2011, 26(4): 94-97. doi: 10.3969/j.issn.1004-1478.2011.04.022
shu
FENG Ting, ZHANG Qian and DONG Ya-Fei. The solution to the maximum clique problem based on two-dimensional DNA tiles self-assemble[J]. Journal of Light Industry, 2011, 26(4): 94-97. doi: 10.3969/j.issn.1004-1478.2011.04.022
Citation: FENG Ting, ZHANG Qian and DONG Ya-Fei. The solution to the maximum clique problem based on two-dimensional DNA tiles self-assemble[J]. Journal of Light Industry, 2011, 26(4): 94-97. doi: 10.3969/j.issn.1004-1478.2011.04.022
shu

基于二维DNA分子tiler自组装求解最大团问题

    通讯作者: 董亚非
  • 陕西师范大学 生命科学学院, 陕西 西安 710062;
  • 陕西师范大学 计算机科学学院, 陕西 西安 71006
  • 收稿日期: 2011-05-06
  • 网络出版日期: 2011-07-15
基金项目:  国家自然科学基金项目(60970005)陕西师范大学2008年重点项目

摘要: 针对常用算法在求解完全NP问题中最大团问题时,存在实验操作步骤过多、活体内不易操作以及环化效率不高等问题,设计了一种用二维DNA(k-臂DNA分子)结构来解决最大团问题的方法.该方法将二维DNA分子设计为分子tiler,通过二维DNA分子构建三维DNA图结构并建立计算模型,以减少解决问题所需的时间和步骤.该算法是求解最大团问题的一种可以降低复杂度的新算法,对DNA计算和DNA计算机的研究是一次有意义的实践.

English Abstract

参考文献 (15) 相关文章 (3)

目录

/

返回文章

网站版权 © 轻工学报编辑部

地址：河南省郑州市科学大道136号邮编：450001

本系统由北京仁和汇智信息技术有限公司开发 技术支持： info@rhhz.net