Abstract: Biochemical reaction theory based DNA computation is of the massive inherent parallelism，so compared to silicon computer，DNA computer has most superiority out and away on NP problems.This paper proposes a new DNA algorithm of minimal vertex covering problem based surface by using the method of fluorescence labeling.The DNA molecules of the solution space are fixed on the solid carrier，and then get the all solutions of minimal vertex covering problem by the biochemical actions.The new algorithm utilizes the fluorescence-quenching technique，and can get all of the feasible solutions through investigating fluorescence.Analyses show that，the new algorithm has some good characteristics such as simple coding and encoding，low error rate.

Key words: DNA computing, surface-based fashion, solution space, vertex covering

摘要： 基于生化反应原理的DNA计算具有强大的并行运算能力，DNA计算机在求解NP问题上存在着硅计算机无法比拟的先天的优越性。采用荧光标记的策略，给出了一种新的图的最小顶点覆盖问题的DNA表面计算模型。该模型首先将问题解空间的DNA分子固定在固体载体上，然后通过进行相应的生化反应来求得图的最小顶点覆盖问题的所有解。新算法利用荧光猝灭技术，通过观察荧光来排除非解，具有编码、解读简单和错误率低的特点。

关键词: DNA计算, 表面方式, 解空间, 顶点覆盖