DNA芯片组技术及其在解决NP问题中的应用

    DNA-chip-group Technology and Its Application in Solving NP Problems

    • 摘要: 为了用DNA并行算法解决实际应用中的一个NP问题——图的四着色问题,基于先进的DNA计算理论、DNA芯片技术、数据库技术,提出了DNA芯片组技术的概念;通过解决一个极大平面图(包括外边界的中国地图)的四着色问题,阐述了DNA芯片组技术的具体操作步骤;对生化实验进行计算机模拟并对数据库进行分析与处理,得到了所有的可行着色方案,从而验证了DNA芯片组技术在解决NP问题中的巨大应用能力.

       

      Abstract: In order to solve a practical NP problem of map four-coloring by using DNA parallel algorithm, a concept of DNA-chip-group technology is proposed, which is based on advanced DNA computing theorem, DNA-chip technology and database technology.The operation steps of the DNA-chip-technology are introduced through solving a four-coloring problem of a maximal planer graph-map of China, which includes the outside part of the boundary as well as the inside ones.The computer simulation of the biochemical experiment, the analysis and processing on the database is carried out, and all of the correct coloring schemes are obtained.The powerful capability of application of the DNA-chip-group technology in solving NP problem is proved.

       

    /

    返回文章
    返回