| 梁冰,冯林.基于DNA计算的多维分配数据关联算法[J].高技术通讯(中文),2012,22(12): |
| 基于DNA计算的多维分配数据关联算法 |
| A multidimensional assignment data association algorithm based on DNA computing |
| 修订日期：2011-12-06 |
| DOI： |
| 中文关键词: DNA计算， 目标跟踪， 多维分配问题， 数据关联算法 |
| 英文关键词: DNA computing, target tracking, multidimensional assignment problem, data association algorithm |
| 基金项目:国家自然科学基金（61173163）和中央高校基本科研业务费专项资金（DUT11RC（3）54）资助项目 |
| 作者 | 单位 | | 梁冰 | 大连理工大学创新实验学院 大连 | | 冯林 | 大连理工大学创新实验学院 大连 |
|
| 摘要点击次数: 3325 |
| 全文下载次数: 2546 |
| 中文摘要: |
| 针对多目标跟踪中的多维分配数据关联这一NP难题，将DNA计算用于数据关联研究，利用DNA分子链生化反应的高度并行性，实现了基于DNA计算的多维分配数据关联算法。该算法利用包含限制性内切酶HaeIII回文序列的DNA分子链对观测视线进行编码，通过连接和退火操作获得所有目标关联组合，然后利用检测DNA发夹结构和凝胶电泳技术排除不满足约束条件的目标关联组合，筛选出多维分配数据关联的最优解。分析结果表明：基于DNA计算的多维分配数据关联算法所需的DNA分子链数即空间复杂度为O(nk!/(c m)!)，将多维分配问 |
| 英文摘要: |
| 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 combinations 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 remove 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 O(mn), where n and m are the sensor number and target number respectively, k is the target localization number. |
|
查看全文
查看/发表评论 下载PDF阅读器 |
| 关闭 |
