基于二维DNA分子tiler自组装求解最大团问题

摘要

针对常用算法在求解完全NP问题中最大团问题时,存在实验操作步骤过多、活体内不易操作以及环化效率不高等问题,设计了一种用二维DNA(k-臂DNA分子)结构来解决最大团问题的方法.该方法将二维DNA分子设计为分子tiler,通过二维DNA分子构建三维DNA图结构并建立计算模型,以减少解决问题所需的时间和步骤.该算法是求解最大团问题的一种可以降低复杂度的新算法,对DNA计算和DNA计算机的研究是一次有意义的实践.