计算机工程与科学
計算機工程與科學
계산궤공정여과학
COMPUTER ENGINEERING & SCIENCE
2007年
8期
55-57,98
,共4页
DNA计算%收缩背包问题%链接反应%凝胶电泳%DNA探针%放射自显影
DNA計算%收縮揹包問題%鏈接反應%凝膠電泳%DNA探針%放射自顯影
DNA계산%수축배포문제%련접반응%응효전영%DNA탐침%방사자현영
收缩背包问题是标准背包问题的一个扩展,其中背包的容量为所装物品数量的非增函数.本文提出了基于分子生物技术的求解收缩背包问题的DNA算法,首先将其约束条件进行分解;然后设计一系列与物品重量相对应的寡聚核苷酸片断及其链接模板,在链接酶的作用下将它们进行链接反应,生成代表任意物品组合的DNA链;再通过基本的生物操作筛选出可行解;最后比较各个可行解对应的目标函数值,进而得到最优解.
收縮揹包問題是標準揹包問題的一箇擴展,其中揹包的容量為所裝物品數量的非增函數.本文提齣瞭基于分子生物技術的求解收縮揹包問題的DNA算法,首先將其約束條件進行分解;然後設計一繫列與物品重量相對應的寡聚覈苷痠片斷及其鏈接模闆,在鏈接酶的作用下將它們進行鏈接反應,生成代錶任意物品組閤的DNA鏈;再通過基本的生物操作篩選齣可行解;最後比較各箇可行解對應的目標函數值,進而得到最優解.
수축배포문제시표준배포문제적일개확전,기중배포적용량위소장물품수량적비증함수.본문제출료기우분자생물기술적구해수축배포문제적DNA산법,수선장기약속조건진행분해;연후설계일계렬여물품중량상대응적과취핵감산편단급기련접모판,재련접매적작용하장타문진행련접반응,생성대표임의물품조합적DNA련;재통과기본적생물조작사선출가행해;최후비교각개가행해대응적목표함수치,진이득도최우해.