特殊0-1整数规划问题的DNA芯片模型研究

发布时间：2018-03-19 13:44

  本文选题：DNA计算　切入点：0-1整数规划　出处：《安徽理工大学》2017年硕士论文　论文类型：学位论文

【摘要】：自从Adleman博士将DNA序列信息和分子生物学技术相结合解决了有向Hamilton路径问题[1]以来,DNA计算为生物计算开辟了一片新天地,并且凭借其高度并行性、高存储、低耗能等优势而备受专家学者关注。随后,不少研究人员将DNA计算与遗传算法、模糊系统、神经网络等计算方法相结合,开辟了计算的新思路。许多学者将DNA计算应用于求解图与组合优化问题,先后提出了不同的DNA计算模型,解决了 3-SAT问题[2]、最大团问题[3～6]、最小顶点覆盖问题[7]、图顶点着色问题[8]等[9、10]。0-1规划问题是整数规划的特殊形式,是运筹学中的一个重要问题,其应用广泛,如指派问题、选地问题等均可视为0-1规划。解决该问题的常见算法有穷举法、隐枚举法、分支定界法等,但各个算法均存在优缺点,目前为止还没有哪种算法可以一劳永逸。近年来,有不少学者针对一些特殊的整数规划问题,先后提出了相应的DNA计算模型。部分组合优化问题(特别是NP-完全问题)和一些可满足性问题,一般都能转化为0-1整数规划问题。DNA芯片操作简单可行、并行性高,能有效避免实验操作及人为因素对计算结果造成的误差,实现计算过程自动化,提高了计算效率和可行解的准确性。因此DNA芯片在DNA计算乃至生物计算领域的优势得天独厚,有望成为新型生物计算芯片。文章首先对DNA计算相关的生物操作加以介绍,简单阐述DNA结构以及DNA计算的基本思想。其次,介绍0-1规划问题、特殊整数规划问题的几种DNA计算模型,并对其算法和思想加以对比分析。然后,对现有算法加以改进,融合分子生物技术和DNA芯片,利用荧光标记对一类特殊0-1整数规划问题提出了新的计算模型。最后,对论文进行总结,指出改进后的优点和仍需解决的问题。
[Abstract]:......
【学位授予单位】：安徽理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O221.4

【相似文献】

相关期刊论文 前10条

1 董江林;解整数规划问题的新方法——三步法[J];上海机械学院学报;1985年03期

2 黎青松,周双贵,杜文;用群论方法求解整数规划问题的初步探讨[J];西南交通大学学报;2000年04期

3 郭伟,席裕庚;一类瓶颈多选择整数规划问题及其求解[J];控制理论与应用;2002年02期

4 宿伟玲,郑丕谔,李彤;非线性两级整数规划问题的最优化方法[J];天津大学学报;2003年04期

5 谭瑛,高慧敏,曾建潮;求解整数规划问题的微粒群算法[J];系统工程理论与实践;2004年05期

6 宿伟玲,郑丕谔,李彤;一类非线性两级整数规划问题的全局优化方法[J];系统科学与数学;2005年03期

7 刘昌贵;但斌;;应用正弦型拓展函数求解整数规划问题[J];数学的实践与认识;2010年01期

8 邢振宇;周楠;李永彬;;基于特征列算法的0-1整数规划问题[J];西南民族大学学报(自然科学版);2011年06期

9 赵宁;宓为建;王东胜;;用于求解0-1型整数规划问题的新算法研究[J];运筹与管理;2012年05期

10 王平;0—1型整数规划问题的求解方法[J];太原重型机械学院学报;1991年03期

相关会议论文 前2条

1 滕春贤;李磊;田广悦;李皓白;;一类非线性两级整数规划问题的全局优化方法[A];中国运筹学会第六届学术交流会论文集（下卷）[C];2000年

2 左小德;孙先锦;王惠芬;胡东波;梁云;;“一维下料”问题研究[A];全国青年管理科学与系统科学论文集第5卷[C];1999年

相关硕士学位论文 前5条

1 朱建鹏;特殊0-1整数规划问题的DNA芯片模型研究[D];安徽理工大学;2017年

2 邢振宇;基于吴特征列算法的整数规划问题[D];电子科技大学;2012年

3 朱凯;多个约束变为一个约束的整数规划问题的新算法[D];江西师范大学;2006年

4 袁婷;模糊概率分布下随机整数规划问题的研究[D];华北电力大学;2012年

5 乐鹏;CB割平面在整数规划问题中的一种应用及一类连续化算法[D];重庆大学;2012年

，

本文编号：1634530