A Molecular Computing Model for Maximal Clique Problem Using Circular DNA Length Growth

摘要：

A novel DNA computing model based on circular DNA length growth (CDLG) is developed to solve a maximal clique problem (MCP) with n-vertices. The time complexity of biological operations required is O(n+m) (m is the number of edges of the complementary graph), and the space complexity is O (n+m). The main feature of this model is using circular single-stranded DNA (c-ssDNA) to implement the computation on the nano-scale. By the CDLG method, the target DNA molecules will grow in length just when they satisfy the conditions. To verify the algorithm, a small paradigm is calculated by the nano-scale DNA computing model. The computing achievement by circular DNA demonstrates the potential ability of DNA computing to solve NPcomplete problems.

关键词： DNA computing Maximal clique problem Circular DNA length growth NP-complete problem Algorithm complexity

作者: Jing Yang Jin Xu

作者单位: Institute of Software, School of Electronics Engineering and Computer Science, Peking University Key laboratory of High Confidence Software Technologies, Ministry of Education, Beijing, China

会议类型: 国际会议

会议名称: 2012 International Conference on Measurement,Information and Control(2012测量、信息与控制国际会议 ICMIC2012)

会议地点: 哈尔滨

会议语种:英文

页码: 558-562

在线出版日期: 2012-05-18（万方平台首次上网日期，不代表论文的发表时间）