摘要
权编码方法是DNA计算中一个重要且有挑战性的问题.设计了一种新的用于表示赋权图中边权的DNA编码方案,给出了用该方案求解中国邮递员问题的DNA算法,并利用Markov链分析了DNA算法中生成各种路径的随机过程.对于任一赋权图G=(V,E),首先通过边到点映射把它转换为广义边图G′=(V′,E′).图G的每条边ei被分别映射为图G′的一个顶点v′i.若G中ei与ej邻接,则连接G′中v′i和v′j.若G中vi为奇顶点,则在与vi关联的边对应的G′的顶点上添加自环.用于编码顶点v′i的DNA串si的长度等于边ei的权值.用于编码边v′iv′j的DNA串sij为si的后半部分与sj的前半部分并置后的逆补.所提出的DNA编码方案具有易于编码、易于推广且错误率低的特点.该工作可提高DNA计算中表示和处理数值的能力,扩展DNA计算求解最优化问题的范围.
Weight encoding method is an important but challenging issue in DNA computing. A new DNA encoding scheme to represent weights on a weighted graph is devised in this paper and a corresponding DNA algorithm for the Chinese postman problem is proposed using the encoding scheme. The random procedure of generating various paths in the DNA algorithm is analyzed by means of Markov chain. For any weighted graph G = （ V, E）, it is firstly converted into its general edge graph G＇ = （ V＇, E＇） through mapping from edges to vertices. Each edge ei in G is mapped as a vertex v＇i in G＇, and the vertices v＇i and v＇j in G＇ are linked if ei and ej are adjacent in G. If vi in G is an odd degree vertex, the self-loops are added to the vertices in G＇ which are mapped from the edges linked to vi , The length of DNA strand si, which is used to encode vertex v＇i, is equal to the value of weight on edge ei. The DNA strand sij, which is used to encode edge v＇iv＇j, is the reverse complement of the second half of si and the first half of sj. The proposed DNA encoding scheme has characteristics of easy encoding, easy generalizing and low error rate. This work improves the capability of representing and dealing with data and extends the range of solving numerical optimization problems in DNA computing.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2007年第6期1053-1062,共10页
Journal of Computer Research and Development
基金
国家自然科学基金项目(60573024)
国家重大基础研究前期研究专项基金项目(2005cca04500)~~
关键词
DNA计算
权编码方法
算法
组合优化
广义边图
中国邮递员问题
DNA computing
weight encoding method
algorithm
combinatorial optimization
general edge graph
Chinese postman problem
