有向图k边导出子图的DNA粘贴算法

作     者：朱维军 徐朝辉 张海宾 杨卫东 ZHU Weijun;XU Zhaohui;ZHANG Haibin;YANG Weidong

作者机构：郑州大学信息工程学院河南郑州450001 河南工业大学粮食信息处理与控制教育部重点实验室河南郑州450001 西安电子科技大学计算机学院陕西西安710071 

基　　金：国家自然科学基金青年基金资助项目(61003079 61202099) 国家自然科学基金主任基金资助项目(61250007) 国家自然科学基金委员会-河南省人民政府人才培养联合基金资助项目(U1204608) 中国博士后科学基金资助项目(2012M511588) 教育部博士点基金资助项目(20100203120012) 中央高校基本科研业务费资助项目(K5051203019) 

出 版 物：《西安电子科技大学学报》 (Journal of Xidian University)

年 卷 期：2013年第40卷第5期

页      码：175-180页

摘      要：针对经典计算的有向图k边导出子图生成算法时间复杂度较高问题,提出了一种在脱氧核糖核酸粘贴机上运行的子图生成算法.首先,以粘贴系统提供的标准生化元操作为算法使用的基本元算子,并使用元操作所产生的生化结果的图论解释作为元算子的最小语义单元;其次,使用包括顺序、循环等在内的程序控制结构,设计一定的逻辑方式把元算子组织起来,以计算有向图导出子图.复杂度分析表明,新算法可在线性时间生成所有子图.仿真实验结果表明,与经典算法相比,新算法在理想条件下大幅降低了子图生成时间.

主 题 词：有向图 脱氧核糖核酸 时间复杂度 粘贴系统 

学科分类：0710[理学-生物科学类] 0808[工学-自动化类] 0809[工学-计算机类] 07[理学] 08[工学] 071007[071007] 0812[工学-测绘类] 081202[081202] 

核心收录：

D　O　I：10.3969/j.issn.1001-2400.2013.05.028

馆 藏 号：203130383...