基于DNA自组装模型解决图的最小顶点覆盖问题

在分析最小顶点覆盖问题特点的基础上,以5个顶点的图为例,将最小顶点覆盖问题转化为可满足性问题,简化问题的操作难度。再根据DNA自组装的自发性和并行性等优势,通过建立DNA自组装模型解决可满足性问题,从而解决图的最小顶点覆盖问题。相对于传统算法,本算法只应用了凝胶电泳技术,大大的降低了操作难度和误差。     

图的最小顶点覆盖的粘贴DNA计算模型

本文在对经典粘贴模型以及全信息化的粘贴DNA计算模型的基本方法进行充分讨论的基础上,提出一种用粘贴DNA计算模型解决图的最小顶点覆盖问题的新方案,将数学问题的求解同并行生物操作有效结合.     

图的最小顶点覆盖问题的链置换模型

针对DNA计算解决最小顶点覆盖覆盖问题,采用对空解的数据池进行解的删除操作,找出解的补集,重而获得问题的最优解。在链置换的基础上,代替酶的作用,提高了实验的效率,节省时间,此算法独特新颖,简单可靠。     

逼近4正则图的最小顶点覆盖问题的难解性(英文)

证明了逼近4正则图的最小顶点覆盖问题在某个常数因子内是计算难解的.相似地,对于5正则图、6正则图等的最小顶点覆盖问题,这个结论也成立.已知逼近3正则图的最小顶点覆盖问题在某个常数因子内是计算难解的,文章扩展了这个结果到4正则图情况,用K-归约证明这个结果,给出了一个从3正则图的最小顶点覆盖问题到4正则图的最小顶点覆盖问题的K-归约.     

0-1整数规划问题的DNA四面体步行者计算模型

DNA折纸术是一种新型的自组装方法,广泛应用于DNA计算中。基于DNA折纸术设计了一个DNA四面体步行者,并将DNA四面体步行者应用于求解0-1整数规划问题。通过DNA四面体步行者的行走,来找出所有可能解。最后,通过DNA四面体步行者所携带的纳米金颗粒的个数来判断是否是0-1整数规划问题的可行解。该模型求解错误率低,具有很强的可控性和实用性。     

图的最小顶点覆盖问题的质粒DNA计算模型

给出了图的最小顶点覆盖问题的质粒DNA算模型及其实现算法．算法的时间复杂性是O(q),编码最小覆盖问题所需的核苷酸片段种类为n,其中n,q分别是图的规模和边数．在算法中,所用酶的种类也等于图的规模．而且,算法不需要复杂的单链DNA自身退火反应和PCR扩增．     

最短路径问题的DNA算法

最短路径问题是在一个带权图的两个顶点之间找出一条具有最小权和路径的问题,它是图论中一个经典的NP完全问题,用电子计算机需要指数级的时间内才能得到解决,本文基于分子生物技术并利用Adleman-Lipton模型给出最短路径问题的DNA算法,这个DNA算法理论上能在多项式的时间内解决这个NP完全问题。具体地对个城市的最短路径问题,首先将它视为一个具有顶点和边的图,并将顶点,边分别用DNA链编码表示,边的方向通过顶点的编码获得;再将这些DNA链投放在试管中进行生物化学反应,利用DNA计算的高效并行性,通过基本的生物实验操作最后得到最短路径问题的解,其过程的复杂度为O(n)。该算法的创新之处在于表示城市和路径的DNA链长度的设计以及在操作中巧妙的消除了路径途经城市数目不同的影响,能使我们在合理小的范围内寻找最短路径问题的解,较大地简化了问题的复杂度。     

次模函数近似算法求最小弱顶点覆盖

求给定无向图的最小弱顶点覆盖是一个NP困难问题,只能通过研究此问题的近似算法来求解。本文从基本圈出发,定义了一个次模函数,利用次模函数理论来得到一个最小弱顶点覆盖问题的近似解,且近似度为1+ln(d-1),其中d为图的顶点最大度。     

基于DNA粘贴模型求解最小集合覆盖问题

运用DNA计算模式中基于粘贴运算的粘贴模型求解最小集合覆盖问题.在粘贴模型中,用存储复合体来表示子集,并利用粘贴运算的巨大并行性,可以有效地求解最小集合覆盖问题.举例说明了基于DNA粘贴模型求解最小集合覆盖问题的过程.     

最小顶点覆盖问题的一个近似算法

最小顶点覆盖是图论中的一个重要概念，它是一个NP难的问题．给出了一个求解最小顶点覆盖的近似算法，与现有算法相比具有更优的性能比。     

DNA 稳定的银纳米簇用于检测端粒酶活性研究

摘要: 目的 建立利用 DNA 稳定的银纳米簇检测端粒酶活性的方法。方法 利用合成的寡核苷酸序列能稳定银纳米的特点,在强还原剂硼氢化钠存在下还原银离子得到具有良好荧光特性的银纳米簇。结果 利用端粒酶活性能够延伸 5' － ( TTAGGG) n － 3'的特性,以及含有 G 碱基的 DNA 序列靠近银纳米簇合成模板时,合成的银纳米簇的荧光明显提升特性建立端粒酶活性检测的方法。结论 合成了以寡核苷酸为模板的银纳米簇并对其荧光特性进行表征,建立了 DNA 稳定的银纳米簇用于检测端粒酶活性的方法。     

固定顶点的树划分问题

 考虑了2个固定顶点的树划分问题,即固定k个顶点的最小和树划分问题和固定k个顶点的最小最大树划分问题,我们得到如下结果:①利用Greedy技巧,得到固定k个顶点的最小和树划分问题的最优多项式算法;②证明了固定k个顶点的最小最大树划分问题是NP-难的,并利用①的结果给出了固定k个顶点的最小最大树划分问题的一个k-近似算法.     

求一般图的最小顶点覆盖集问题的混合贪婪算法

现有的求一般图的最小顶点覆盖集近似算法或者近似比较高,或者为降低复杂度限制了图的规模,或者算法搜索过程中盲目性大.根据顶点的度特点及贪婪法的思想,提出了邻接度数、覆盖边等主要概念,并在此概念的基础上设计了混合贪婪算法.该算法设计思路清晰,容易理解,易于编程实现,且在最坏情况下的时间复杂度为O(|V|2),执行效果较好,性能近似比不大于4/3,接近已知的可能的近似比下界1.166 6,低于2005年认为最低的近似比1.361,是图的最小顶点覆盖问题算法的一个较好的补充.     

基于批分离实验的最大独立集问题DNA算法

根据解决最大独立集问题的需要,讨论了简化的粘贴模型,该模型只由单链DNA的存储链和分离板组成.以分离实验为基础提出了批分离实验和生化操作过程,该实验可以快速分离存储链.基于批分离实验设计了最大独立集问题的DNA算法,并给出其生化实现过程:先形成所有顶点子集的初始解空间;接着用批分离实验对每个顶点进行检测,筛选全部满足不相邻要求的顶点子集,从而得到全部独立集;然后通过电泳实验得到全部最大独立集;最后通过检测实验输出实验结果.讨论并证明了算法的正确性和复杂性,算法的操作次数是线性的,通过仿真实验说明了算法的有效性和可行性.     

DNA与CdS-NH2纳米粒子的相互作用研究

采用荧光光谱、紫外光谱(UV-vis)、圆二色谱(CD)、透射电镜(TEM)、原子力显微镜(AFM)、琼脂糖凝胶电泳等技术研究Cd S-NH2-EcoRI复合物与DNA的相互作用.研究发现:Cd S-NH2纳米粒子与p BR322DNA结合后会延迟EcoRI的酶切反应.DNA的曲率和纳米粒子的粒径都是影响结合作用的因素,曲率较大的环状DNA比线性DNA能更好地与纳米粒子结合,小粒径的Cd S-NH2纳米粒子则更易结合到DNA上.并研究了DNA与Cd S-NH2纳米粒子之间的作用机理.     

近完美匹配全覆盖点

利用匹配理论中的Gallai-Edmonds结构定理,首先得到了在一个有近完美匹配的图中判定一个顶点为近完美匹配全覆盖点的充要条件,然后对每一个顶点都为近完美匹配全覆盖点的图类给出了一个刻画.同时,也给出了一种构造这类图的方法.     

分层算法求解竞赛图上的最小弱顶点覆盖

竞赛图上的弱顶点覆盖问题是一个NP困难问题,本文先定义了竞赛图上的势加权函数,然后利用分层技术给出了一个求解竞赛图最小弱顶点覆盖问题的近似算法,并证明了此近似算法的近似度为3     

氨基硅烷修饰的荧光磁性复合纳米粒子的合成

以共沉淀法制备得到了Fe_3O_4磁性纳米粒子,以溶胶-凝胶法得到了包裹罗丹明6G的氨基硅烷修饰的荧光磁性复合纳米粒子(Fe_3O_4/R6G)@SiO_2-APTES,以动态光散射法(DLS)测定了复合纳米粒子的水合粒径,以IR光谱、荧光光谱等手段对得到的复合纳米粒子进行了表征,并以琼脂糖凝胶电泳研究了(Fe_3O_4/R6G)@SiO_2-APTES对DNA的损伤行为。研究结果表明这类氨基硅烷修饰的荧光磁性复合纳米粒子在水中具有很好的分散性和稳定性,且有良好的生物相容性,有望成为一种新的抗癌药物载体。     

Pythagorean模糊信息系统属性约简的图论方法

信息系统中,属性约简是知识发现问题的一个研究热点,能达到发掘并简化知识的目的。目前已有很多利用辨识矩阵来进行属性约简的研究,但是当数据维数较大时,算法复杂度往往很大。利用加权欧几里得距离来定义二元关系及辨识矩阵,利用信息系统的约简与生成图的最小顶点覆盖等价的关系,将辨识矩阵求解约简的问题转化为求解生成图中最小顶点覆盖的问题,并给出了Pythagorean模糊信息系统中属性约简的算法;在此基础上,利用基于加权欧几里得距离的相似关系,定义了Pythagorean模糊决策信息系统的辨识矩阵,并给出了用最小顶点覆盖的方法求约简算法,最后利用实例验证了算法的有效性。     

一种新型DNA纳米结构的构建与结晶

DNA三角形纳米结构的拐角是由DNA同源重组中的Holliday基序构成的.为进一步研究DNA三角形纳米结构,对其拐角截断并引入黏性末端到其基序上,使其能够自组装成为一种新型DNA纳米结构.对该DNA纳米结构进行凝胶电泳分析,发现其迁移速率要比DNA三角形迁移速率小.在这种没有扭曲张力的情况下,该基序只是自组装形成一个二聚体结构,而不是三聚体结构(DNA三角形).对该新型DNA纳米结构进行结晶,并合成得到了硒代核酸,同时也得到了较高质量的硒代单晶,以帮助相位测定.希望对其晶体结构进行测定研究,以便发现该新型DNA纳米二聚体结构和该Holliday基序组装的三维结构,从而更深入地认识DNA纳米材料的组装规律.