基于PNA的最大独立集问题的DNA计算模型

PNA-Based DNA Computing Model for Maximum Independent Set Problem

肤核酸(Peptide Nucleic Acid)是人工合成的拔酸(DNA)的类似物.PNA能够特异地、稳定地与DNA杂交以及其独特的性质,使得PNA广泛应用在分子生物学中.本文提出了一种基于PNA的最大独立集问题的DNA计算模型,利用单链PNA被逐步褪火到单链DNA分子上,解决了一个最大独立集问题的实例.该模型的解空间只有一种类型的DNA分子,计算经m步生物操作产生问题的解(其中m=|E(G)|),最后利用鞭子PCR(whiplash PCR)原理以及凝胶电泳读解.

Peptide nucleic acid is an artificial synthesized analogue of nature occurring DNA. Due to the capability that PNA can hybridize DNA with highly specificity and stability as well as its unique features, PNA finds widely applications in modern molecular biology. In this paper, DNA computing model based on PNA was proposed. We gradually annealed singlestranded PNA to single-stranded DNA molecules and solved an instance of maximum independent set （MIS） problem. Unlike previously reported DNA computing model, we began computation with single molecular variety, then after biological operations （m = ｜E（G）｜））, solutions to the given problem were generated. Finally, the solutions were subjected to readout operation, which is on the basis of Whiplash PCR followed by polyacrylamide gel electrophoresis.