中文摘要：

针对多目标跟踪中的多维分配数据关联这一NP难题，将DNA计算用于数据关联研究，利用DNA分子链生化反应的高度并行性，实现了基于DNA计算的多维分配数据关联算法。该算法利用包含限制性内切酶HaelII回文序列的DNA分子链对观测：视线进行编码，通过连接和退火操作获得所有目标关联组合，然后利用检测DNA发夹结；陶和凝胶电泳技术排除不满足约束条件的目标关联组合，筛选出多维分配数据关联的最优解。分析结果表明：基于DNA计算的多维分配数据关联算法所需的DNA分子链数即空间复杂度为O（nk!／（c-m）!），将多维分配问题的指数级复杂度降低到多项式复杂度O（mn），其中n为传感器数，m为目标数，k为目标定位点数。

英文摘要：

The DNA computing was applied to investigation of the data association, a NP-hard mathematical problem in multitarget tracking, and a multidimensional assignment data association algorithm was realized through utilizing the super parallelism of DNA computation. The algorithm uses the DNA molecular chains containing the palindromic sequence of the restriction endonuclease HaeIII to encode the observed sight lines. All target association combina- tions are obtained through the operation of connection and annealing. In order to select the optimal multidimensional data association solution, the techniques of DNA hairpin structure detection and gel electrophoresis are used to re- move the target association combinations that do not satisfy the constraints. The results of the theoretic analysis show that the DNA computation based multidimensional assignment data association algorithm needs the DNA molecular chain number of O（ nk !/（c - m） !） （the space complexity）, and decreases the time complexity from exponential to 0 （mn）, where n and m are the sensor number and target number respectively, k is the target localization number.