DNA缩短法计算模型求解最大独立集问题

提出了一种基于环形DNA缩短法的新型计算模型. 该模型可以求解n个顶点m条边的图的最大独立集. 算法的时间复杂度是O(n+m). 随着问题规模的增大, 计算所需的试管数量呈线性增长. 在计算模型的生物操作中, 有两个主要技术: DNA分子内环化和DNA长度逐步缩短. 结合反向PCR(聚合酶链式反应), 磁珠吸附和环化酶催化等多种方法, 在求解步骤中, DNA分子的结构在线性双链DNA(dsDNA)、线性单链DNA(ssDNA)和环形单链DNA之间进行循环变化. 利用环形DNA分子的结构特点, 在计算过程中避免了DNA分子间重组. 为了证实该DNA计算模型的可行性, 利用其求解了一个最大独立集问题的实例.     

DNA分子计算与DNA计算机的研究进展

生物分子计算与DNA计算机是计算机科学和分子生物学交叉产生的新兴领域. DNA计算机的特点是具有超强的并行运算能力和巨大的数据存储能力, 因而被认为有望解决电子计算机所面临的评价问题. 本文在介绍DNA计算机的基本概念基础上, 围绕DNA计算机的原理、计算模型和在多方面的应用等关键问题, 分析讨论了粘贴模型、剪接模型和等价检查模型等常用的DNA计算模型, 并对DNA计算机在NP问题、遗传分析与临床诊治、防伪和译码技术以及游戏与机器人等领域的研究进展和应用前景进行了探讨. 最后讨论了DNA计算机未来可能的发展方向.     

一类无约束优化算法的摄动理论

许多求解非线性规划问题的算法,首先是对严格凸二次函数的无约束优化问题来推导,然后再推广来求解非二次问题,具有约束的问题,并在数字计算机上实现.由于在极小值点附近,非二次函数可以通过对二次函数进行摄动来产生,因此这些算法推广到非二次函数时的计算过程,可以看成为求解二次函数过程的摄动.当研究求解具有约束的问题和在计算机上的     

广义本征值并行计算及在晶体能带中的应用

本文提出一个利用“黑匣子”思想并行求解高阶广义矩阵本征问题的分块消去迭代算法,并在国家智能计算机研究开发中心研制的大规模并行计算机曙光1000上成功地解算了非线性光学晶体电子结构计算中的1572阶复共轭对称矩阵偶的广义矩阵本征问题,应用于中国科学院福建物质结构研究所陈创天等人发现的LBO非线性光学晶体电子结构分析,使用能带方法完成了该晶体电子态的自治计算.我们对新算法进行了迭代过程收敛性、误差分析、并行设计、并行效率的分析研究与数值实验.     

为何女性更长寿?

新的研究发现,有一个进化中的"漏洞"可以解释为什么许多物种的雄性都比雌性的寿命短. 这个漏洞就在线粒体中,也就是人体细胞中产生能量的部分.线粒体有自己的DNA,与细胞核中的DNA是分离开的.几乎在所有的物种中,线粒体DNA都仅仅来自于母亲.根据最新的研究结果,这种直线遗传可能使一些有害的变异不断累积.一般来说,自然选择过程会使有害的变异尽量不会累积,以确保它们不会被遗传给后代.但是如果线粒体DNA中的变异只对男性有危害,而对女性没有危害,就没有什么机制会阻止母亲把这种变异遗传给子女.     

运行于磁珠表面的可编程DNA计算机

后基因组时代涌现出DNA操作技术一系列新的应用, 其中包括建立在DNA分子基础上的生物计算机. 至今还没有在固体表面实现基于自动机原理的DNA计算的相关报道. 本文描述了一种可编程的DNA计算装置——具有图灵机部分功能的有限自动机, 并且将计算过程转移到了固体表面. DNA计算机主要由DNA分子(输入分子, 输出状态检测分子和充当软件的状态转移分子等)、DNA限制性内切酶及连接酶和所需的缓冲液组成, 可以自动地解决计算问题. 将荧光标记在输入分子的5′端, 以便于动态跟踪监测反应过程中的各种中间产物. 这些工作具有如下的特点: (1) 成功地在磁珠表面实现了可编程的DNA计算机——有限状态自动机. (2) 通过毛细管电泳直接监测所有的DNA计算中间产物. DNA计算机的超大并行计算能力具有通过自动控制来得以实现的可行性, 为在不久的将来把大规模的DNA计算和功能基因组研究结合起来奠定了基础.     

求解析取范式永真性问题的一个近似快速算法

NP完全问题是一类在计算复杂性理论中被证明为较难求解的问题,这类问题中包含有很多在理论和实际中很有意义的问题。NP完全问题中的一个问题的对偶问题若存在快速(多项式意义下)的求解算法,则所有NP完全问题都有快速的求解算法。但目前人们还没有找到一个求解NP完全问题的真正快速算法,并且有迹象表明求解NP完全问题的真正快速算法是不存在的。本文针对一个典型的NP完全问题的对偶问题——析取范式永真性     

求解蛋白质折叠问题的拟人算法: 对PERM的改进

PERM(Pruned-Enriched-Rosenbluth Method)是目前文献中依格点模型求解蛋白质折叠问题的最高效算法. 给出了PERM算法的一种拟人解释, 对算法中的权重及预测值进行了拟人化的改进, 并对选择动作时不同情况下的权重计算公式进行了统一. 综合这些策略得到了改进的PERM算法——人口控制算法. 该算法在计算效率上有了明显的提高: 对当前文献中公认的最难的4个算例的计算都达到了最优解, 计算速度较PERM提高了几倍至几百倍. 对于这4个难例中的3个, 还找到了迄今为止文献中所没有的全新的最低能量构形.     

粘贴DNA计算机模型(Ⅱ): 应用

经典的粘贴DNA计算模型采用单、双链混合型DNA分子编码, 其生物操作具有无需DNA链的延伸、无需生物酶以及DNA链可重复使用等优点, 已经受到不同学科学者的关注. 在经典模型的基础上, 进行一定的扩展与完善, 必对DNA计算机的研究有良好的贡献. 基于此, 对粘贴DNA计算机模型进行了较为深入的研究: (1) 提出了基于粘贴模型的矩阵表达模型; (2) 对经典粘贴模型应用于图与组合优化等方面的研究成果给予综述, 诸如集合覆盖问题、图的顶点覆盖问题、图的Hamilton路与圈问题、图的团与独立集问题、图的生成树与Steiner树问题等; (3) 给出了基于粘贴模型的图的同构问题的算法.     

数值计算求解非线性动力方程

由于非线性动力方程中的外荷载或结构体系随时间发生改变,其解析解往往很难获得,需要采用数值算法进行求解.文章首先介绍了激励线性插值法、中心差分法、Newmark 的平均加速度法和线性加速度法的基本原理,随后给出了在Madab中编制的函数范例及各方法的动力响应求解结果.经与理论解比较,验证了所编制函数的正确性,可作为工程设计人员求解一般非线性动力响应问题的一条简便途径.     

可数状态马氏过程的瞬态解及其算法

有限状态马氏过程瞬态解(在时刻t,过程处于各状态的概率)的求解算法已有不少工作,如Grassmann,Gross和Miller,Reibman和Trivedi等.可数状态马氏过程的瞬态解算法却只有几种特殊的情形被讨论过,如Grassmann在初始时刻系统中无顾客的条件下,讨论了系统M|M|1的瞬时性态的求解算法;Zhang和Coyle在初始时刻过程处于1水平时,得到了拟生灭过程的瞬态解算法.本文则在任意初始条件下,研究一般可数状态马氏过     

Kuhn算法的单调性质

不动点算法已经表现为非线性问题数值解的有效方法。算法的进行,常常是以某个参数(高度)的变化为标志,计算向高层发展,直至达到精度要求。有时这种发展是“迂迴”的,上升一段,又倒退一点。这种对算法效率不利的现象,在文献中称为YO-YO行为。     

单纯形法的平均迭代次数

1984年,28岁的印度数学家卡马卡(N.Karmarkar)提出了求解线性规划问题的又一个多项式时间算法,成了继1979年苏联数学家哈奇扬在这方面首先提出多项式时间的椭球算法以后又一次轰动世界的一件大事。光阴荏苒,一晃就是几年过去了,这几年来,国内外不少人根据卡马卡算法编制了程序在计算机上试算了许多数例。其中一部分人发现大量的实际计算结果似乎表明:新的方法并不象原先有些人所期望的那么好,甚至对很多问题的计算并不比用丹齐克(G.B.Dantzig)在1947年所发明     

关于鞍点问题Uzawa型算法的收敛性

1.构造求解椭圆型变分不等式的数值算法有两种途径:第一种途径是将微分方程数值解法(例如SOR法,ADI法,多网格法等)加以改造,第二种途径则是直接采用最优化计算方法。在解最简单的典型椭圆变分不等式——障碍问题时,第一种途径十分有效。而在解约     

图的二分问题唯一全局最优解实例与骨架计算复杂性

骨架分析是近年来理论计算机科学研究的热点, 对于NP-难解问题的启发式算法设计具有重要意义. 由于骨架计算复杂性研究十分困难, 现有的骨架分析方法多采用实验统计手段. 针对现有方法中存在的骨架规模小的缺陷, 给出图的二分问题GBP(graph bi-partitioning problem)的唯一全局最优解实例构造算法, 有效提高了骨架的规模. 同时, 利用该算法从理论上证明了寻找GBP问题的完整骨架属于NP-难解问题, 即在P≠NP的假设下, 不存在多项式时间的算法可以确保得到GBP问题的完整骨架. 本文的工作拓广了骨架计算复杂性研究的范围, 所提出的唯一全局最优解实例构造算法对于NP-难解问题启发式算法设计亦具有较高的参考价值.     

计算机代数及其应用

何谓 CA 计算机代数(Computer Algebra,简称CA)是计算机科学百花园中的一枝新蕾,它又称为计算机公式处理或符号处理等。它与通常大家所熟悉的数值计算不同,数值计算的目的是在于更有效地使用计算机,以求得各类数学问题的满足一定精度的数值解;而CA是研究使用计算机对公式直接进行处理的理论、算法和系统的计算机科学的一个分支,利     

一种图顶点着色DNA计算机模型

设计了一种专门用于求解图顶点着色的DNA计算机. 该计算机的主体是由一个可变温度的聚丙烯酰胺凝胶电泳构成. 可变温度的电泳由3部分组成, 分别为“解链区”、“非解区”和“解区”. 它们对应的可控温度分别为T_m1, T_m2和T_m3. 本文介绍了该计算机的基本结构与基本原理, 给出了存储库的构建方法, 特别讨论了编码问题, 并成功地对5个顶点的图给出了系统的生物操作与生化实验.     

协同快速退火演化算法识别蛋白质家族模体

将快速退火演化算法(fast annealing evolutionary algorithm, FAEA)与协同方法相结合, 提出了一种用于求解高维的全局优化问题的新方法——协同快速退火演化算法(cooperative fast annealing coevolutionary algorithm, CFACA). 首先将高维的解空间分解成多个一维的子空间, 再在每个子空间里利用单个独立的FAEA搜索该子空间里的最优子解, 最后将各子解结合在一起, 即构成了原来问题的一个解. 基准函数测试的结果表明, CFACA算法具有更快的收敛速度. 进一步用CFACA算法提取EGF蛋白质家族的模体, 正确识别率达到67.0%, 所提取的模体与蛋白质功能位点数据库PROSITE中的结果相吻合.     

自组装DNA/纳米颗粒分子逻辑计算模型

将AuNP 自组装聚合色变与DNA 计算相结合, 构建了纳米分子逻辑计算模型. 使用了DNA 自组装、DNA/AuNP 结合和AuNP 聚合色变等关键技术方法. 利用DNA 自组装结构变化,通过DNA/AuNP 聚合色变反应, 实现了简单逻辑运算功能. 在此基础上, 构建了求解简单集合运算的DNA/AuNP 计算模型, 对多重输入的简单集合运算进行了逻辑运算. 最后, 进一步拓展该分子逻辑运算模型的应用, 结合分子检测技术, 对H1N1 病毒基因进行检测.     

基于线性自组装的DNA减法模运算

使用线性自组装方法, 提出了两个非负二进制整数减法模运算的DNA算法. 对于两个表示为n位的二进制数A与B, 算法给出A-B在模2n情况下的运算结果. 算法中包含反应被减数与减数大小关系的扩展借位信息, 从而在计算前不必对A与B的大小关系进行预分类. 结果反应链中包含运算结果、每一步借位信息、参与运算的数值、判断被减数与减数大小的标志位等信息. 算法充分利用DNA反应的并行特性, 在给定两个被减数集与减数集时, 可进行两个集合的减法模运算的并行计算. 算法的可行性基于已知的DNA算法实验. 算法具有良好的自发反应特性, 避免了人工操作随运算数值位数增长的情况, 对于计算位数n, 在本算法中参与反应的单链库规模为O(n), 生物操作复杂度为常数.