Solving the independent set problem by sticker based DNA computers

作     者：Hassan Taghipour Ahad Taghipour Mahdi Rezaei Heydar Ali Esmaili 

作者机构：Department of Computer Engineering Faculty of Engineering Isfahan University Isfahan Iran Department of Pathology Tabriz University of Medical Sciences Tabriz Iran Department of Theoretical Physics and Astrophysics Tabriz University Tabriz Iran 

出 版 物：《American Journal of Molecular Biology》 (美国分子生物学期刊（英文）)

年 卷 期：2012年第2卷第2期

页      面：153-158页

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：Parallel Computing Sticker Based DNA Computers Independent Set Problem NP-Complete Problem 

摘      要：In this paper, the sticker based DNA computing was used for solving the independent set problem. At first, solution space was constructed by using appropriate DNA memory complexes. We defined a new operation called “divide and applied it in construction of solution space. Then, by application of a sticker based parallel algorithm using biological operations, independent set problem was resolved in polynomial time.