一、A surface-based DNA algorithm for the minimal vertex cover problem（论文文献综述）
韩英杰[1]（2020）在《基于DNA计算模型的计算树逻辑模型检测算法研究》文中研究指明计算树逻辑（Computation Tree Logic,CTL）模型检测是形式化方法研究的热点,是保证系统正确性的重要手段之一。DNA计算是以DNA分子和生物酶为材料,以生化操作为计算手段的一种生物计算模式。开展CTL模型检测的DNA计算方法研究,不仅可以利用DNA分子的超高存储容量和DNA计算的强大并行优势解决模型检测状态空间爆炸问题,而且对推动DNA计算机的研发和应用具有重要意义。自图灵奖获得者Emerson教授提出“DNA模型检测”问题以来,针对CTL模型检测问题,非自治、自治和细胞内算法仍没有解决,现有算法存在不能提供反例、不能检测带过去算子的CTL公式（CTLP）、因使用核酸酶导致的鲁棒性弱以及反应材料不可复用等问题。针对上述问题,本文深入研究了基于非自治、自治和细胞内DNA计算模型的CTL模型检测算法,完成的主要工作和创新点如下:1)提出了基于非自治DNA计算模型的CTL模型检测算法——AM-CTLMC。设计了待检测系统模型的编码方案,构建了系统模型运行路径的生成算法,给出了CTL基本公式、一般公式和CTLP公式的模型检测算法,仿真实验结果验证了算法的正确性。AM-CTLMC解决了现有算法在系统模型不满足CTL公式时不能提供反例的问题,同时,能够对现有算法无法检测的CTL一般公式和CTLP公式实施检测,提升了检测能力,算法执行过程中不使用核酸酶,提升了鲁棒性,保证了反应材料的可复用性。2)提出了基于自治DNA计算模型的CTL模型检测算法——基于分子信标的算法（MB-CTLMC）和基于长度-编码自动机的算法（LEA-CTLMC）。给出了待检测系统模型的DNA编码方案,分别构建了CTL基本公式的分子信标和长度-编码自动机的编码方案,设计了系统模型运行路径与CTL基本公式的分子自组装环境,给出了基于分子信标和长度-编码自动机的CTL模型检测自组装算法,仿真实验和生物实验结果验证了算法的正确性。CTL模型检测的分子自组装算法解决了现有算法鲁棒性弱和反应材料不可复用的问题,同时,由于可编程性和通用性,LEA-CTLMC在实现时序逻辑模型检测方面具有可扩展性。3)提出了基于细胞内DNA计算模型的CTL模型检测算法——IN VIVO-CTLMC。设计了系统模型运行路径的信使核糖核酸分子编码方案,构建了CTL基本公式有限状态自动机的转运核糖核酸分子编码方案,给出了CTL基本公式的模型检测算法,通过将路径的信使核糖核酸分子和CTL公式的转运核糖核酸分子插入到质粒,再将质粒转染到大肠杆菌细胞中,利用大肠杆菌活体细胞内自治的蛋白质合成机制实现了模型检测,并对算法的正确性进行了证明。该算法解决了目前缺乏细胞内CTL模型检测算法的问题,为基因疾病的早期诊断及分子层面的治疗探索了动态、智能、精确的方法。4)提出了基于机器学习的DNA分子杂交有效性分析方法,解决了生物仿真平台分析DNA分子杂交有效性效率低的问题。构建了DNA分子杂交有效性分析数据集,经初步实验选定了梯度提升树、逻辑回归、支持向量机和随机森林四种机器学习算法,采用数据集训练并生成了四种分类器,综合性能指标选出最佳的分类器——基于梯度提升树的分类器。与生物仿真平台的对比实验结果表明,基于梯度提升树分类器方法的F1值比生物仿真平台的F1值下降了0.1,但分析效率提升了142,013倍,且分析时间不会随参与杂交的DNA分子种类增加发生数量级的变化。该方法解决了生物仿真平台分析DNA分子杂交有效性效率低的问题,为DNA分子杂交有效性分析提供了可供选择的工具。
张春露[2]（2018）在《链置换模型的若干问题研究》文中进行了进一步梳理近几年DNA计算作为一门新的交叉学科正逐渐发展起来,DNA计算是一种以模拟生物分子DNA的结构为手法,通过相应的生物技术来进行运算的一种新方法,利用DNA计算模型为背景和DNA的大量存储能力和高度并行性设计新一代计算机。所以DNA计算机也是一种利用DNA建立的一种完整信息技术形式,以编码后的DNA序列为运算对象,运用生物分子学的操作,获得最后目标DNA链,解决所求问题的生物计算机。DNA计算的基本思想是:用分子生物技术解决计算机难题,使运算过程可控操作。DNA计算模型包括粘贴模型、质粒模型、双链DNA模型等。目前作为研究热点之一的DNA信息处理领域的DNA计算技术具有并行性好,能耗低,可保存性高等优点,因此,它已被应用于各种复杂的计算问题。DNA纳米技术的新兴领域也发展迅速,其中DNA链置换的方法因自诱导,灵敏,准确,操作简单而备受关注。本文介绍了一种基于DNA链置换的生物计算方法,它是一种无需人工干预的计算方法。该模型能够使用逻辑公式在连接范式中执行迭代解析步骤。该方法的实现基于DNA链置换技术,每个子句编码在一个单独的DNA分子命题中,被编码为每个命题和它的互补链对应命题子句被编码在同一条链中的不同命题。该模型允许通过级联解析步骤运行由霍恩子句组成的逻辑程序。该模型的潜力也体现在其求解SAT的理论能力上,结果的SAT算法在求解步骤的数量上具有线性时间复杂度,而其空间复杂度在公式的变量数上是呈指数级增加的。本文总结了DNA计算中DNA链置换的最新发展的五个方面:（1）级联电路;（2）催化反应;（3）逻辑计算;（4）表面上的DNA计算;（5）基于由链置换引导的纳米颗粒的逻辑计算。本次研究首先介绍了几种目前计算领域所涉及的新兴生物技术,重点介绍了本研究涉及的技术,然后利用链置换技术解决最大匹配问题、小顶点覆盖问题及邮递员问题。第一,以DNA计算为研究背景,讨论DNA计算的研究意义和发展前景。第二,对于已给图形中所有的边集,找出图中任意两条边没有共同顶点的最大边集,这是一个是NP完全问题,求解这种问题的算法模拟把数学问题转换到DNA链上,对所给图中的每一条边采用DNA的特点进行编码,而在相应的生物操作中,利用链置换技术把目标链分离出来,这条链表示解。通过实验操作,给出基于链置换的最大匹配问题的解决方式,验证此算法有效可行。第三,本文针对DNA计算解决最小顶点覆盖覆盖问题,采用对表示空解的数据池进行解的删除操作,找出解的补集,重而获得问题的最优解。在链置换的基础上,代替酶的作用,提高了实验的效率,节省时间,此算法独特新颖,简单可靠。第四,组合优化中典型的背包问题是非常重要的NP问题,针对0-1背包问题,本文采用把数学问题转换到DNA链上的算法,对给定物品的体积和价值分别进行编码,不加入连接酶的情况下,根据DNA链的W-C原理,将所需的DNA链分别用一条短链连接,并在反应过程中,加入外源链,得到满足约束条件的物品组合,利用链置换技术及相应的生物操作删除外源DNA链,以及最终链的分离,给出基于链置换的0-1背包问题的计算方式,提出的算法有效可行。第五,将邮递员的行走路线用图论的语言来描述,本文采用把数学问题转换到DNA链上的算法,对给定图G中的每条边进行编码,并编码出连接的DNA链,生成问题的解的DNA链,及相应的生物操作把最终链分离,得出问题的解。第六,本文对DNA编码方法进行设计,并设计一种用6个顶点求解的中国邮递员问题的算法,证明提出的DNA计算方式的算法有效可行。
巩成艳[3]（2018）在《自组装纳米颗粒探针在DNA计算中的应用》文中研究指明DNA计算突破传统计算的概念,是把DNA分子作为存储数据和运算媒介的新型计算模型。它使用生物分子作为计算材料,由于DNA分子具有高度并行性、高存储、易操作等优点,因此DNA计算是一门非常有发展潜力的新型学科。科学技术不断发展,专家们努力对其构建DNA分子模型、设计实现算法和生化试验研究,使其能够解决需要大量计算的复杂问题如图论中的NP完全问题。DNA分子是具有代表性的纳米尺度的物质。随着纳米技术的快速发展,在具体工作中,作用不同而且结构多样的分子器件以及具备多种结构的微元件被迫切需要。尤其是DNA分子的纳米颗粒多聚体的结构研究受到越来越多的科学家的关注,纳米颗粒与生物大分子等组装的纳米结构,功能多样,具有重要的研究价值。本文首先具体阐述了 DNA计算的背景、工作原理、常用的生物操作以及在DNA计算发展过程中出现的常见模型,然后还详细介绍了金纳米颗粒的相关基础知识。在这些理论知识基础上,本文给出了一种基于自组装纳米颗粒探针的DNA计算方法,解决了典型NP完全问题。该方法将问题中所有可能的变量组合编码为自组装纳米颗粒探针的识别区域。通过增加互补的变量链,所有可能的解决方案是在目标序列杂交后并行生成的。所以我们可以比较和分析可行解,找出最优解。与传统的DNA计算模型不同,本文应用了纳米技术和DNA计算理论。最大的特点是方便制备和检测灵敏,使得该模型的可靠性非常高,并且还具有成本更低,巨大的并行性,非凡的信息密度和操作可控性的优势。所以这个新方法推动了 DNA计算在某些方面的发展。
张春露,殷志祥[4]（2018）在《图的最小顶点覆盖问题的链置换模型》文中研究说明针对DNA计算解决最小顶点覆盖覆盖问题,采用对空解的数据池进行解的删除操作,找出解的补集,重而获得问题的最优解。在链置换的基础上,代替酶的作用,提高了实验的效率,节省时间,此算法独特新颖,简单可靠。
巩成艳,殷志祥,赵鑫月[5]（2017）在《基于自组装纳米颗粒探针的最小顶点覆盖问题的DNA计算模型》文中认为DNA自组装技术为DNA计算的发展带来了一些新的启发。目前,解决各种NP完全问题的方法有多种多样的计算模型,其中有些是非常有用的,可以解决复杂的NP完全问题。在本文中,在自组装纳米颗粒探针的基础上,介绍了关于最小顶点覆盖问题的一种新的DNA计算模型。将给定问题的变量0或1所有可能的组合,编码在自组装纳米探针的识别区,通过靶序列的杂交来判断其可行解。相对于传统的DNA计算模型,该模型具有方便、灵敏、稳定性高的优点。
吴帆[6]（2017）在《基于生化反应的典型约束可满足问题求解算法研究》文中研究指明约束可满足问题,广泛存在于科学研究和工程实践中。如人力资源配置问题、农作物布局优化问题、工程设计方案优化问题和资源分配优化问题等,都属于约束可满足问题。这类问题的特点是在特定的约束条件下,寻找问题的解。此类问题的解决往往能带来很高的社会或经济价值。目前还没有高效的精确求解算法,由于这类问题通常可约化为典型的约束可满足问题,如最小顶点覆盖问题。因此可对典型约束可满足问题进行深入的理论研究,以寻找问题求解的新思路和新方法。如何求解约束可满足问题是研究约束可满足问题的核心。对于最小顶点覆盖等典型约束可满足问题,当问题规模较大时,传统的电子计算机求解算法很难实现精确求解。基于生化反应的DNA计算,是一种非传统的高性能计算方法。它具有高度的并行性,并行操作数目超过1018,能在多项式时间内精确求解NP难问题。这为约束可满足问题的精确求解提供了新的思路和方法。另外,受自然界生化反应的启发,科学家提出了化学反应优化算法,研究发现,该方法在近似求解NP问题时,往往能跳出局部极值的限制,比遗传算法、禁忌算法等启发式算法具有更加良好的分布性。基于此,通过分析基于生化反应的DNA计算和化学反应优化算法特征,本文研究了利用DNA计算和化学反应优化智能算法来求解典型约束可满足问题的关键技术,提出了若干相关算法,研究表明这些算法表现出了良好的性能和扩展性。论文的主要研究工作如下:提出了一种基于分治法的N皇后问题DNA计算算法（1）N皇后问题是一种典型的约束可满足问题。研究表明,基于粘贴模型求解该问题的DNA计算算法,可以在多项式时间内精确求解此问题,但参与反应的DNA链数是指数级的,这将导致求解过程中误解率较高,难以求解大规模问题的求解计算等问题。针对这些问题,本文提出了一种结合分治法,基于扩展粘贴模型来求解N皇后问题的DNA计算算法。通过算法分析和模拟实验表明:本算法的DNA链数是亚指数级的,将DNA链数从O（n"）减少至O（nn/2）,同时减少生物操作数,降低了误解率,测试试管数由所需的O（n）减少至O（1）。（2）提出了一种基于DNA自组装模型来求解最小顶点覆盖问题的DNA计算算法。尽管基于扩展粘贴模型,利用分治法可以以亚指数的DNA链数求解N皇后问题,但由于参与生化反应的是DNA单链分子,其误解率依然较高。为此,本文提出了一种基于DNA自组装模型来求解最小顶点覆盖问题的DNA计算算法。自组装模型是近年DNA计算领域提出的一种计算模型,具有降低问题求解过程中生化操作和生化解误解率等优点。本文描述了编码方案、问题求解算法以及进行了模拟实验。实验表明,本算法能快速精确求解出最小顶点覆盖问题。同时算法通过减少计算过程中操作步骤数,降低了生化解的错误率,提高了生化解的准确性,算法的生化实验复杂度低,具有良好的易操作性。（3）提出一种利用连接分子与自组装模型求解N皇后问题的DNA计算算法最小顶点覆盖问题的约束条件单一。针对具有多约束条件下的N皇后问题,本文研究了基于自组装模型的DNA计算算法。N皇后问题具有四个约束条件,即棋盘行、列和两个对角线上不能存在皇后冲突。本文通过设计连接分子,巧妙地利用它将多个约束条件组合在一起从而实现了基于自组装模型的N皇后问题求解DNA计算算法。模拟实验表明,本方法是有效的,且具有良好的扩展性。算法使用的tiles分子块种类为Θ（2n）,生化操作复杂性为Θ（1）,其中n为皇后的个数。（4）提出了 一种基于混合CRO求解N皇后问题的算法利用DNA计算在多项式时间内可以精确求解典型约束可满足问题,其实质是利用DNA计算的巨大并行性并利用穷举方法从而实现求解计算,参与计算的DNA分子链数或tiles分子数是指数级或亚指数级的。尽管许多科学家也提出了许多改善生化反应中产生错误解的方法,然而,针对规模较大的问题求解时,目前DNA计算依然无法将误解率减少到可以接受的水平。智能启发式算法依然是约束可满足问题一种高效的近似求解算法。化学反应优化算法是近年提出来的一种智能启发式算法,该算法能避免搜索陷入局部最优,具有提高问题搜索空间的优点,局部最优搜索是基于贪婪法的快速搜索算法,该算法具有收敛速度快等优点。因此本文将这两个算法融入到一起,设计了混合CRO算法来求解N皇后问题。实验分析表明,跟其它启发式算法相比,本算法具有良好的分布性和收敛速度,能提高N皇后问题求解的效率。
郭洪敏[7]（2016）在《最小顶点覆盖问题的几种DNA算法研究》文中研究表明传统的计算机由于其自身存储量和计算能力的有限,已经不能满足日益发展的科学形势。1994年,Adleman探索性的将现代生物技术与DNA操作技术结合起来,成功解决了具有七个节点的有向赋权图的哈密尔顿路径问题（Hamilton path problem）,从此打开了生物计算的大门,让DNA分子作为一种新型的计算机硬件成为可能。而DNA分子由于具有传统计算机无法比拟的海量存储量和高度的计算并行性,使得其在密码学,数学,计算机等领域得到了广泛的青睐。本文将具体阐述DNA计算的研究背景、DNA分子结构、DNA分子操作过程等基本理论,并且对DNA分子操作过程中的初始编码问题进行了具体的分析,包括初始编码问题的基本概念,初始编码的约束条件和具体的编码方法；还将简单介绍一些常用的DNA计算模型（剪接模型、分子信标、质粒DNA模型以及DNA自组装模型等）的基本操作原理及优缺点。此外,本文将具体介绍最小顶点覆盖问题、可满足性问题、线性规划问题的基本概念,并巧妙的将复杂的最小顶点覆盖表转化为形式简便的0-1规划问题和可满足性问题,这也是本文的创新之处。并在此基础上,结合DNA自组装模型、质粒DNA模型,给出基本算法和具体生物操作过程,具有一定研究意义。
白雪[8]（2014）在《DNA计算在层次聚类算法中的研究与应用》文中研究指明DNA计算是一种以DNA分子作为反应介质并利用生物操作技术实现数理运算的新型计算模式，其开创性地将问题域映射为特定编码的DNA序列，通过一系列生化反应从初始数据池中获得符合筛选条件的最优组合。随着社会信息化水平的不断提高，人们越来越需要从海量数据中发现有价值的信息和知识，使得数据挖掘这一年轻而充满生机的领域受到了国内外研究学者的极大关注。作为数据挖掘中的一项重要分支，聚类分析就是把物理或抽象的样本集合划分成相似的对象类的过程，其中层次聚类方法对数据点进行分层操作，以此形成一棵以簇为节点的树，在计算机工程、图像处理、现代生物学等许多领域有着广泛的应用。凭借DNA计算具备的并行性、低耗性等优势，本文将其引入层次聚类算法，借助全新的混合DNA模型在保证聚类质量的同时有助于数据集规模和运算速度的进一步扩大和提高，主要研究内容包括以下两个方面：一是提出了基于粘贴和2-臂DNA模型的SHCDM算法，把二维平面中利用最小距离完成迭代操作的单连接层次聚类问题转化为在赋权无向完全图中寻找最小生成树的优化问题，并通过给定阈值影响反应终止时的输出结果。该算法充分利用了两种模型固有的双链结构，在纳米金标识技术的帮助下使最优解的产生与识别过程具有较强的可操作性和应用弹性。鉴于传统的聚类分析方法在进行簇与簇的合并时仅考虑了成对点间的紧密程度而忽视了从全局的角度收集样本的领域信息，需要添加新的限制属性，借助“链接”的概念使两对象的共同近邻数参与相关性的度量，根据基于Adleman与三链DNA模型的HCLDM算法优先将链接数大、关联度高的数据点聚为一类，由此体现分类属性层次聚类过程的中心思想，也成为本课题的第二个研究重点。值得注意的是，算法中尝试使用核蛋白细状体与待提取的DNA片段形成稳定的三螺旋结构，有效地避免了错配现象的发生，并且通过Adleman模型一次性构造可行解空间，在很大程度上提高了反应效率、降低了误解率。除此之外，随着互联网的飞速发展，电子商务作为一种崭新的在线交易模式将对我省社会经济及广大消费者产生巨大影响，同时也使传统实体企业面临巨大的机遇和挑战。面对我省中小企业电子商务推广过程中显现出的不平衡性，可以利用SHCDM算法把发展水平相似的企业视为一个整体，结合问卷调查有针对性地制定改进措施。不仅如此，群体内部成员可以借此机会组成战略联盟实现优势互补，共同寻找适合该企业类型的电子商务发展方式与盈利模式。对于目前多数社交网络平台应用的好友推荐机制，本文借助HCLDM算法对其进行优化，将相关度比较密切的用户聚为一类，进一步丰富了使用者的人脉资源，增强了好友间交流渠道的灵活性，有助于满足网民对于无界化沟通的迫切需求。从仿真实验可知，两种DNA算法均具可行性，并且依照测评函数和实际背景选出的聚类结果较好地解决了以上两种应用问题。
赵洪超[9]（2013）在《DNA计算在支配集与电梯调度问题中的研究与应用》文中研究指明1994年，Adleman博士运用生化试验的方法解决了一个包含7个顶点的Hamilton路径问题，开创了DNA计算研究的新领域。DNA计算是一种新的计算模式，它以基于生物酶的生化操为计算工具，以DNA分子为计算的对象，计算过程由一系列生物实验构成。与传统的电子计算机相比，DNA计算在并行计算、信息存储与耗能方面都具有相当大的优势，尤其是DNA计算与生俱来的高度并行计算能力使得它在解决众多棘手的非线性问题和NP问题上表现出了巨大的潜力，众多的研究成果表明，很多借助电子计算机需要指数量级计算才能解决的NP问题，DNA计算在多项式的计算步骤内就能解决。如今，DNA计算在诸如化学、计算机科学、分子生物学、物理学和数学等众多领域内引发了研究的热潮，很多优秀的学术成果纷纷涌现了出来，DNA计算也形成了比较系统的知识体系，但是现在DNA计算尚未成熟，很多理论方面的问题有待解决，生物实验技术也仅仅停留在实验的水平，尚未表现出任何实用价值，然而现阶段对其理论和应用方面的研究仍然有着十分重要意义。本文在首章描述了相关背景后，第二章重点介绍了DNA计算的基础理论知识，包括DNA分子的结构与性质，DNA计算中的生化操作，DNA计算的原理以及本文理论的核心部分——DNA计算模型，其中的Adleman模型和粘贴模型是后文DNA算法的模型基础。后续两章以DNA计算为工具，将其用于解决两类问题：支配集问题和电梯调度问题。第三章研究了如何运用DNA计算解决支配集问题。支配集问题属于NP困难问题，在数学、图论和计算机科学等多个领域内都有着广泛的应用，很多实际问题在一定程度上也可以归结为支配集问题。经过多年的发展，支配集问题衍生出了众多的子问题，本文选取其中三个子问题：最小支配集问题、完全支配集问题和domatic partition问题作为研究对象，以基于粘贴模型为基础的DNA算法予以解决。为证明算法的有效性，作者编写了java程序模拟DNA算法的执行过程，并以小规模的图例作为求解对象进行模拟实验，最终实验得出的结果证明本文的算法切实是有效可行的。第四章讨论了DNA计算用于解决一类应用问题——电梯调度问题。将电梯调度问题抽象模型化处理之后可以看出，该问题本质上是图论的问题，目的在于求解多个图中的最短“和路径”。本文以DNA计算中Adleman模型为基础，在改进编码方法的基础上，提出了一种新的求解电梯调度问题的DNA算法，该算法在一定程度上克服了原DNA算法编码效率低下的问题。文中运用改进的DNA算法求解一个小规模的电梯调度问题算例，结果证明了算法的可行性。
李庆燕[10]（2013）在《DNA计算在两类困难问题上的研究》文中研究表明DNA计算是以编码携带遗传信息的DNA序列和与之有关的一些生物酶等为最基本物质,运用生物操作来实现并行信息处理的一种新型的分子水平上的生物计算方式。1994年,Adleman首先提出DNA计算的方法来解决NP-完全问题,对NP-完全问题的计算提供了一种新方法。此后学者们不断地研究利用DNA分子或者是其它生物分子来进行计算过程,并取得了令人瞩目的成果。DNA计算的主要思想是：利用DNA分子特有的双螺旋结构及碱基互补配对性质,把需要解决的问题编码并映射成相应的DNA链,通过生物酶的参与形成数据池,然后按照一系列的实验步骤把待解决问题的原始数据经过运算高度并行地映射成DNA分子链的可控制的生化过程,再利用现代分子生物技术检测所需要的运算结果。本文从DNA计算的基础理论问题出发,研究了DNA计算模型及其在解决两类困难问题上的应用。详细研究内容的安排如下：本文讨论了文中用到的质粒DNA计算模型和闭环DNA计算模型。质粒DNA计算模型是一种以闭环状质粒作为基础的DNA计算模型,在该模型中被用到的质粒具有一段特殊的DNA插入序列,全部的片断确定在对应的限制性内切位点,运用剪切及粘贴的生物操作执行计算过程。闭环DNA计算模型与质粒DNA计算模型有许多异同点,闭环DNA计算模型具有更大的研究价值和更广的应用范围。基于质粒DNA计算模型,给出了求解图的最小顶点覆盖问题的DNA算法。该算法通过合适的编码以及基本的生物操作完成解的生成及最终解的分离。基于闭环DNA计算模型和其主要的生物化学实验,介绍了求解最大加权独立集问题的闭环DNA算法。该算法首先通过适当的编码以及多次删除实验获得所有独立集,再用其它实验手段得到图的最大加权独立集。
二、A surface-based DNA algorithm for the minimal vertex cover problem（论文开题报告）
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
三、A surface-based DNA algorithm for the minimal vertex cover problem（论文提纲范文）
（1）基于DNA计算模型的计算树逻辑模型检测算法研究（论文提纲范文）
| 摘要 |
| Abstract |
| 1 绪论 |
| 1.1 研究背景及意义 |
| 1.2 国内外研究现状 |
| 1.2.1 DNA计算 |
| 1.2.2 CTL模型检测 |
| 1.2.3 基于DNA计算模型的CTL模型检测算法 |
| 1.3 研究内容 |
| 1.4 组织结构 |
| 2 相关知识 |
| 2.1 DNA计算及DNA模型 |
| 2.1.1 DNA组成和DNA计算的本质 |
| 2.1.2 DNA计算的基本思想和主要特点 |
| 2.1.3 DNA计算模型 |
| 2.1.4 细胞内计算 |
| 2.1.5 生物仿真平台 |
| 2.2 CTL模型检测 |
| 2.2.1 CTL的语法和语义 |
| 2.2.2 CTL模型检测的基本原理 |
| 2.2.3 CTL模型检测算法 |
| 2.3 本章小结 |
| 3 基于非自治DNA计算模型的CTL模型检测算法 |
| 3.1 Adleman模型 |
| 3.2 基于Adleman模型的CTL模型检测算法 |
| 3.2.1 系统模型编码及运行路径的生成算法 |
| 3.2.2 CTL基本公式的模型检测算法 |
| 3.2.3 CTL一般公式的模型检测算法 |
| 3.2.4 系统模型编码及逆运行路径的生成算法 |
| 3.2.5 CTLP公式的模型检测算法 |
| 3.3 时间复杂度分析 |
| 3.4 仿真实验 |
| 3.4.1 编码及有效性分析 |
| 3.4.2 杂交验证 |
| 3.5 对比分析与讨论 |
| 3.6 本章小结 |
| 4 基于自治DNA计算模型的CTL模型检测算法 |
| 4.1 基于分子信标的CTL模型检测算法 |
| 4.1.1 分子信标 |
| 4.1.2 算法设计 |
| 4.1.3 仿真实验及结果分析 |
| 4.2 基于长度-编码自动机的CTL模型检测算法 |
| 4.2.1 长度-编码自动机 |
| 4.2.2 算法设计 |
| 4.2.3 生物实验及结果分析 |
| 4.3 对比分析与讨论 |
| 4.4 本章小结 |
| 5 基于细胞内DNA计算模型的CTL模型检测算法 |
| 5.1 细胞内的有限状态自动机模型 |
| 5.2 细胞内CTL模型检测算法 |
| 5.3 仿真模拟及证明 |
| 5.4 对比分析与讨论 |
| 5.5 本章小结 |
| 6 CTL模型检测的DNA分子杂交有效性分析方法 |
| 6.1 NUPACK分析DNA分子杂交有效性存在的问题 |
| 6.2 基于机器学习的DNA分子杂交有效性分析方法 |
| 6.2.1 DNA分子杂交有效性分析数据集 |
| 6.2.2 采用的机器学习算法 |
| 6.2.3 方法原理 |
| 6.3 实验及结果分析 |
| 6.3.1 实验目的与平台 |
| 6.3.2 实验过程 |
| 6.3.3 评价指标 |
| 6.3.4 实验结果及分析 |
| 6.4 本章小结 |
| 7 总结与展望 |
| 7.1 总结 |
| 7.2 展望 |
| 参考文献 |
| 个人简历、在校期间发表的学术论文及研究成果 |
| 致谢 |
（2）链置换模型的若干问题研究（论文提纲范文）
| 摘要 |
| Abstract |
| 绪论 |
| 1.1 DNA计算产生的背景 |
| 1.1.1 DAN计算目前存在的困难 |
| 1.1.2 DNA计算目前存在的困难 |
| 1.1.3 DNA计算的应用领域以及研究方向 |
| 1.2 论文的研究背景及选题意义 |
| 1.2.1 研究背景 |
| 1.2.2 选题意义 |
| 1.3 国内外现状综述 |
| 1.4 论文的研究内容 |
| 第二章 DNA计算模型的理论基础 |
| 2.1 DNA分子结构 |
| 2.2 DNA计算原理 |
| 2.2.1 DNA操作技术 |
| 第三章 DNA链置换 |
| 3.1 DNA链置换反应 |
| 3.2 DNA链置换的逻辑门运算 |
| 3.2.1 与非门设计 |
| 第四章 链置换模型的若干问题研究 |
| 4.1 最大匹配问题 |
| 4.1.1 最大匹配问题概念 |
| 4.1.2 DNA链置换算法 |
| 4.1.3 DNA链置换的算法步骤实现 |
| 4.1.4 总结 |
| 4.2 最小顶点覆盖问题 |
| 4.2.1 最小顶点覆盖 |
| 4.2.2 DNA链置换算法 |
| 4.2.3 DNA链置换算法分析 |
| 4.2.4 案例分析 |
| 4.2.5 总结 |
| 4.3 背包问题 |
| 4.3.1 链置换技术 |
| 4.3.2 背包问题 |
| 4.3.3 生物算法 |
| 4.3.4 案例分析 |
| 4.3.5 总结 |
| 4.4 邮递员问题的DNA计算模型 |
| 4.4.1 引言 |
| 4.4.2 DNA计算模型 |
| 4.4.3 生物算法 |
| 4.4.4 案例分析 |
| 4.4.5 总结 |
| 第五章 结论与展望 |
| 5.1 结论 |
| 5.2 展望 |
| 参考文献 |
| 致谢 |
| 作者简介及读研期间主要科研成果 |
（3）自组装纳米颗粒探针在DNA计算中的应用（论文提纲范文）
| 摘要 |
| Abstract |
| 1 绪论 |
| 1.1 DNA计算的研究现状 |
| 1.2 DNA计算的原理 |
| 2 DNA基本理论知识 |
| 2.1 DNA分子结构 |
| 2.2 DNA计算的生物操作 |
| 2.2.1 DNA分子的变性和复性 |
| 2.2.2 DNA分子的复制 |
| 2.2.3 DNA分子的连接 |
| 2.2.4 DNA分子的延伸 |
| 2.2.5 DNA链的外切和内切 |
| 2.3 常用的DNA计算模型 |
| 2.3.1 表面DNA计算模型 |
| 2.3.2 DNA粘贴模型 |
| 2.3.3 DNA剪接模型 |
| 2.3.4 分子信标模型 |
| 2.3.5 DNA自组装模型 |
| 3 DNA自组装纳米技术 |
| 3.1 引言 |
| 3.2 金纳米颗粒 |
| 3.2.1 金纳米 |
| 3.2.2 金纳米颗粒的简介 |
| 3.2.3 金纳米颗粒的合成方法 |
| 3.2.4 金纳米颗粒的表面修饰 |
| 3.2.5 金纳米颗粒的应用 |
| 3.3 金纳米颗粒DNA探针 |
| 4 用DNA自组装纳米颗粒探针模型解决全错位排列问题 |
| 4.1 全错位排列问题的数学模型 |
| 4.2 全错位排列问题的DNA计算模型 |
| 4.3 生物操作 |
| 4.4 复杂度分析 |
| 4.5 结论 |
| 5 用DNA自组装纳米颗粒探针模型解决最小顶点覆盖问题 |
| 5.1 图的最小顶点覆盖问题 |
| 5.1.1 图的最小顶点覆盖定义 |
| 5.1.2 算法步骤 |
| 5.2 自组装纳米颗粒探针的最小顶点覆盖问题的DNA计算模型 |
| 5.3 实例分析 |
| 5.4 复杂度分析 |
| 5.5 结论 |
| 6 结论 |
| 参考文献 |
| 致谢 |
| 作者简介及读研期间主要科研成果 |
（4）图的最小顶点覆盖问题的链置换模型（论文提纲范文）
| 0 引言 |
| 1 最小顶点覆盖 |
| 2 DNA链置换算法 |
| 3 DNA链置换算法分析 |
| 4 案例分析 |
| 5 结语 |
（5）基于自组装纳米颗粒探针的最小顶点覆盖问题的DNA计算模型（论文提纲范文）
| 1 图的最小顶点覆盖问题 |
| 1.1 图的最小顶点覆盖定义 |
| 1.2 算法步骤 |
| 2 自组装纳米颗粒探针的最小顶点覆盖问题的DNA计算模型 |
| 2.1 纳米金颗粒探针 |
| 2.2 生物操作 |
| 3 实例分析 |
| 4 结论 |
（6）基于生化反应的典型约束可满足问题求解算法研究（论文提纲范文）
| 摘要 |
| Abstract |
| 第1章 绪论 |
| 1.1 论文研究背景与目的 |
| 1.2 约束可满足问题研究现状 |
| 1.2.1 约束可满足问题定义 |
| 1.2.2 典型问题与求解方法 |
| 1.3 生化反应计算研究现状 |
| 1.3.1 DNA计算研究现状 |
| 1.3.2 化学反应优化算法 |
| 1.4 本文主要研究内容 |
| 1.5 本文的组织结构 |
| 第2章 相关研究 |
| 2.1 引言 |
| 2.2 DNA计算 |
| 2.2.1 DNA分子结构 |
| 2.2.2 DNA计算工作原理 |
| 2.2.3 DNA计算的特点 |
| 2.2.4 DNA计算模型 |
| 2.3 启发式智能算法 |
| 2.3.1 基于单个解的智能算法 |
| 2.3.2 局部最优搜索 |
| 2.3.3 基于种群的智能算法 |
| 2.3.4 化学反应优化算法 |
| 2.4 小结 |
| 第3章 基于分治的N皇后问题DNA算法 |
| 3.1 引言 |
| 3.2 DNA计算扩展模型 |
| 3.3 基于分治的N皇后问题DNA计算算法 |
| 3.3.1 算法框架 |
| 3.3.2 问题编码 |
| 3.3.3 初始解空间生成器 |
| 3.3.4 冲突解删除算法 |
| 3.3.5 并行搜索算法 |
| 3.3.6 N皇后问题DNA算法 |
| 3.3.7 算法性能分析 |
| 3.4 模拟实验与分析 |
| 3.5 小结 |
| 第4章 基于自组装的最小覆盖问题分子算法 |
| 4.1 引言 |
| 4.2 DNA自组装计算模型 |
| 4.2.1 DNA tile分子 |
| 4.2.2 自组装计算模型的数学描述 |
| 4.2.3 自组装模型的主要生化操作 |
| 4.3 最小顶点覆盖问题的DNA算法 |
| 4.3.1 最小顶点覆盖问题 |
| 4.3.2 最小顶点覆盖问题的DNA算法框架 |
| 4.3.3 DNA tile分子块的设计 |
| 4.3.4 算法步骤 |
| 4.4 算法证明与分析 |
| 4.5 算法实例与仿真实验 |
| 4.5.1 Tile分子设计 |
| 4.5.2 问题求解 |
| 4.5.3 仿真实验 |
| 4.6 小结 |
| 第5章 基于自组装的N皇后问题DNA算法 |
| 5.1 引言 |
| 5.2 DNA自组装计算模型 |
| 5.2.1 DNA Tile二维平面结构 |
| 5.2.2 自组装计算模型的数学描述 |
| 5.3 自组装N皇后问题的DNA算法 |
| 5.3.1 N皇后问题的DNA计算算法框架 |
| 5.3.2 DNA tile分子块的设计 |
| 5.3.3 算法步骤 |
| 5.4 算法分析 |
| 5.5 仿真实验 |
| 5.5.1 Tile分子设计 |
| 5.5.2 问题求解 |
| 5.5.3 仿真实验 |
| 5.6 小结 |
| 第6章 基于局部最优搜索的N皇后问题混合CRO算法 |
| 6.1 引言 |
| 6.2 问题编码与算法框架 |
| 6.2.1 问题编码 |
| 6.2.2 适应度函数 |
| 6.2.3 算法框架 |
| 6.3 N皇后问题混合CRO算法 |
| 6.3.1 初始解空间的生成 |
| 6.3.2 混合CRO反应操作 |
| 6.4 实验与分析 |
| 6.4.1 实验平台与参数 |
| 6.4.2 实验结果分析 |
| 6.5 小结 |
| 总结与展望 |
| 参考文献 |
| 致谢 |
| 附录A 攻读学位期间发表的学术论文目录 |
| 附录B 攻读学位期间主持或参研的项目目录 |
（7）最小顶点覆盖问题的几种DNA算法研究（论文提纲范文）
| 摘要 |
| Abstract |
| 1 绪论 |
| 1.1 生物计算的背景 |
| 1.2 DNA计算基本思想 |
| 1.3 本文结构 |
| 2 DNA生物计算 |
| 2.1 DNA分子结构 |
| 2.2 DNA分子操作 |
| 2.2.1 DNA分子的变性与复性 |
| 2.2.2 DNA链的自我复制 |
| 2.2.3 DNA链的内切和外切 |
| 2.2.4 DNA分子的连接 |
| 2.3 DNA分子的编码 |
| 2.3.1 DNA编码问题 |
| 2.3.2 DNA编码的约束条件 |
| 2.3.3 DNA编码方法 |
| 3 DNA计算模型 |
| 3.1 DNA粘贴模型 |
| 3.2 DNA剪接模型 |
| 3.3 质粒DNA模型 |
| 3.4 分子信标 |
| 3.5 DNA自组装模型 |
| 4 基本理论介绍 |
| 4.1 最小顶点覆盖问题 |
| 4.2 可满足性问题 |
| 4.3 0-1规划问题 |
| 5 最小顶点覆盖问题的DNA自组装算法研究 |
| 5.1 最小顶点覆盖问题的转化 |
| 5.2 最小顶点覆盖的DNA自组装算法 |
| 5.2.1 可满足性问题基本算法 |
| 5.2.2 生物操作步骤 |
| 5.3 实例分析 |
| 5.4 本章小结 |
| 6 基于质粒DNA模型的MVCP研究 |
| 6.1 MVCP的质粒DNA算法 |
| 6.1.1 将最小顶点覆盖问题转化成0-1规划问题 |
| 6.1.2 算法设计 |
| 6.2 实例分析 |
| 6.3 本章小结 |
| 总结和展望 |
| 参考文献 |
| 致谢 |
| 作者简介及读研期间主要科研成果 |
（8）DNA计算在层次聚类算法中的研究与应用（论文提纲范文）
| 目录 |
| 摘要 |
| Abstract |
| 第1章 绪论 |
| 1.1 研究背景及意义 |
| 1.2 国内外研究现状综述 |
| 1.2.1 DNA 计算的研究进展 |
| 1.2.2 层次聚类算法的研究进展 |
| 1.3 论文的研究内容与创新点 |
| 1.3.1 论文主要内容与安排 |
| 1.3.2 论文创新点 |
| 第2章 DNA 计算的基本模型和生物操作 |
| 2.1 DNA 的分子结构 |
| 2.2 DNA 计算的基本模型 |
| 2.2.1 Adleman 模型 |
| 2.2.2 粘贴模型 |
| 2.2.3 三链 DNA 模型 |
| 2.2.4 k-臂 DNA 模型 |
| 2.2.5 其他 DNA 模型 |
| 2.3 DNA 计算的基本生物操作 |
| 2.3.1 DNA 分子的变性与杂交 |
| 2.3.2 DNA 分子的连接与混合 |
| 2.3.3 DNA 链的复制 |
| 2.3.4 DNA 分子的提取 |
| 2.3.5 DNA 链长度的测量 |
| 2.3.6 DNA 序列的测定 |
| 2.4 本章小结 |
| 第3章 基于粘贴和 2-臂 DNA 模型的单连接层次聚类算法 |
| 3.1 基本思想 |
| 3.1.1 单连接层次聚类算法简介 |
| 3.1.2 问题域的转化 |
| 3.2 DNA 编码设计 |
| 3.3 基于粘贴和 2-臂模型的 DNA 算法实现 |
| 3.3.1 生物算法伪代码 |
| 3.3.2 生物操作步骤 |
| 3.4 算法分析与讨论 |
| 3.4.1 算法复杂度比较 |
| 3.4.2 聚类结果测评 |
| 3.5 本章小结 |
| 第4章 基于 Adleman 和三链 DNA 模型的分类属性层次聚类算法 |
| 4.1 基本思想 |
| 4.1.1 分类属性层次聚类算法简介 |
| 4.1.2 问题域的转化 |
| 4.2 DNA 编码设计 |
| 4.3 基于 Adleman 和三链模型的 DNA 算法实现 |
| 4.3.1 生物算法伪代码 |
| 4.3.2 生物操作步骤 |
| 4.4 算法分析与讨论 |
| 4.4.1 算法复杂度比较 |
| 4.4.2 聚类结果测评 |
| 4.5 本章小结 |
| 第5章 层次聚类 DNA 算法的应用研究 |
| 5.1 单连接 DNA 算法在电子商务企业划分中的应用 |
| 5.1.1 电子商务企业划分问题 |
| 5.1.2 DNA 计算模型的建立和算法模拟 |
| 5.1.3 仿真实验与分析 |
| 5.2 分类属性 DNA 算法在社交网络好友推荐中的应用 |
| 5.2.1 社交网络好友推荐问题 |
| 5.2.2 DNA 计算模型的建立和算法模拟 |
| 5.2.3 仿真实验与分析 |
| 5.3 本章小结 |
| 第6章 总结与展望 |
| 参考文献 |
| 攻读学位期间的论文发表及项目参与情况 |
| 致谢 |
（9）DNA计算在支配集与电梯调度问题中的研究与应用（论文提纲范文）
| 摘要 |
| Abstract |
| 第一章 绪论 |
| 1.1 研究的背景与意义 |
| 1.1.1 研究背景 |
| 1.1.2 研究的意义 |
| 1.2 国内外研究现状 |
| 1.3 本文主要研究内容 |
| 1.3.1 DNA 计算理论知识 |
| 1.3.2 基于改进的粘贴模型求解最小支配集问题 |
| 1.3.3 基于改进的粘贴模型求解完全支配集问题 |
| 1.3.4 基于粘贴模型求解 domatic partition 问题 |
| 1.3.5 基于 Adleman 模型求解电梯调度问题 |
| 1.4 本文的创新点 |
| 1.5 本文的组织结构 |
| 第二章 DNA 计算基础理论 |
| 2.1 DNA 分子的结构与性质 |
| 2.2 DNA 计算中的生化操作 |
| 2.3 DNA 计算中的编码问题 |
| 2.4 DNA 计算的原理 |
| 2.5 DNA 计算模型 |
| 2.5.1 Adleman 模型 |
| 2.5.2 粘贴模型 |
| 2.5.3 改进的粘贴模型 |
| 2.6 本章小结 |
| 第三章 基于粘贴模型的支配集问题的研究 |
| 3.1 支配集问题概述 |
| 3.2 基于粘贴模型求解最小支配集问题的 DNA 算法 |
| 3.2.1 编码 |
| 3.2.2 算法的实现 |
| 3.2.3 算法分析 |
| 3.2.4 实验模拟 |
| 3.3 基于粘贴模型求解完全支配集的 DNA 算法 |
| 3.3.1 编码 |
| 3.3.2 算法的实现 |
| 3.3.3 算法分析 |
| 3.3.4 算法模拟 |
| 3.4 基于粘贴模型求解 DOMATIC PARTITION 问题的 DNA 算法 |
| 3.4.1 编码 |
| 3.4.2 算法的实现 |
| 3.4.3 算法分析 |
| 3.4.4 实验模拟 |
| 3.5 本章小结 |
| 第四章 基于 ADLEMAN 模型的电梯调度问题研究与应用 |
| 4.1 电梯调度问题模型 |
| 4.1.1 电梯调度问题概述 |
| 4.1.2 电梯调度问题的图论模型 |
| 4.1.3 电梯调度实例 |
| 4.2 基于 ADLEMAN 模型的 DNA 编码 |
| 4.3 基于 ADLEMAN 模型求解电梯调度问题的 DNA 算法 |
| 4.3.1 算法的实现步骤 |
| 4.3.2 算法详细描述 |
| 4.3.3 算法分析 |
| 4.4 实验对比论证 |
| 4.4.1 论文实例 |
| 4.4.2 本文算法求解 |
| 4.5 本章小结 |
| 第五章 结论与展望 |
| 5.1 全文总结工作 |
| 5.2 未来展望 |
| 参考文献 |
| 致谢 |
| 攻读硕士学位期间发表的论文和参与的项目 |
| 附录一 |
| 附录二 |
| 附录三 |
（10）DNA计算在两类困难问题上的研究（论文提纲范文）
| 摘要 |
| Abstract |
| 1 引言 |
| 1.1 DNA计算产生的背景及优势 |
| 1.2 DNA计算的基本原理 |
| 1.3 DNA计算的研究现状和进展 |
| 1.4 DNA计算主要的研究内容及面临的问题 |
| 1.5 本文的主要研究内容 |
| 2 DNA计算的相关分子生物基础 |
| 2.1 DNA分子的结构 |
| 2.2 DNA计算中常用的分子操作 |
| 2.3 DNA计算的实现方式 |
| 2.4 本章小结 |
| 3 DNA计算模型 |
| 3.1 质粒DNA计算模型 |
| 3.1.1 质粒DNA分子 |
| 3.1.2 质粒DNA计算的生物学模型 |
| 3.1.3 质粒DNA计算模型的数学表达 |
| 3.1.4 讨论 |
| 3.2 闭环DNA计算模型 |
| 3.2.1 闭环DNA分子及模型 |
| 3.2.2 闭环DNA计算模型的基本生化实验 |
| 3.2.3 讨论 |
| 3.3 本章小结 |
| 4 图的最小顶点覆盖问题的质粒DNA算法 |
| 4.1 引言 |
| 4.2 最小顶点覆盖问题 |
| 4.2.1 问题概述 |
| 4.2.2 实例描述 |
| 4.2.3 DNA算法步骤 |
| 4.2.4 算法实现过程 |
| 4.3 本章小结 |
| 5 最大加权独立集问题的闭环DNA算法 |
| 5.1 引言 |
| 5.2 最大加权独立集问题描述 |
| 5.3 DNA算法步骤 |
| 5.4 算法实现过程 |
| 5.5 算法实例 |
| 5.6 本章小结 |
| 6 总结与展望 |
| 6.1 全文总结 |
| 6.2 进一步研究方向 |
| 参考文献 |
| 致谢 |
| 作者简介及攻读硕士学位期间发表的论文 |
四、A surface-based DNA algorithm for the minimal vertex cover problem（论文参考文献）
- [1]基于DNA计算模型的计算树逻辑模型检测算法研究[D]. 韩英杰. 郑州大学, 2020(02)
- [2]链置换模型的若干问题研究[D]. 张春露. 安徽理工大学, 2018(12)
- [3]自组装纳米颗粒探针在DNA计算中的应用[D]. 巩成艳. 安徽理工大学, 2018(02)
- [4]图的最小顶点覆盖问题的链置换模型[J]. 张春露,殷志祥. 佳木斯大学学报(自然科学版), 2018(02)
- [5]基于自组装纳米颗粒探针的最小顶点覆盖问题的DNA计算模型[J]. 巩成艳,殷志祥,赵鑫月. 长春师范大学学报, 2017(12)
- [6]基于生化反应的典型约束可满足问题求解算法研究[D]. 吴帆. 湖南大学, 2017(06)
- [7]最小顶点覆盖问题的几种DNA算法研究[D]. 郭洪敏. 安徽理工大学, 2016(08)
- [8]DNA计算在层次聚类算法中的研究与应用[D]. 白雪. 山东师范大学, 2014(08)
- [9]DNA计算在支配集与电梯调度问题中的研究与应用[D]. 赵洪超. 山东师范大学, 2013(09)
- [10]DNA计算在两类困难问题上的研究[D]. 李庆燕. 安徽理工大学, 2013(05)