基于DNA计算的层次图聚类算法

为解决使用DNA计算图聚类问题,提出一种基于DNA计算的层次图聚类算法。在分裂层次聚类中,使用DNA分子对图中顶点、边进行编码,在试管中并行产生最小生成树,根据给定阈值,通过切割树枝得到聚类结果。在凝聚聚类中使用DNA计算产生哈密尔顿路径,通过寻找最短哈密尔顿路径得到聚类结果。实验结果验证了该算法的可行性。     

旅行商问题的DNA算法

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

基于概念模型的个性化搜索引擎研究

在对用户兴趣模型探讨的基础上,提出了一种基于概念的用户兴趣模型,用于区别用户兴趣的大小.讨论了基于链接的查询聚类算法,并针对该算法的不足提出了一种基于概念的聚类算法,该算法根据用户兴趣模型建立查询-概念二分图,然后计算图中查询顶点间的概念相似度,并将概念相似度最高的查询顶点进行合并以实现聚类.设计实现了一个基于Web数据挖掘的个性化搜索引擎系统,对系统的个性化查询进行了测试,并对比分析了链接聚类和概念聚类的实验结果.     

DNA逻辑计算模型的研究现状与展望

DNA计算因其优异的计算能力已经成为当前研究热点,DNA逻辑计算模型是DNA计算体系与运算实现的重要依托。按应用技术将现有DNA逻辑计算模型进行分类：基于链置换的DNA逻辑计算模型、基于核酶的DNA逻辑计算模型、基于G-quadruplex的DNA逻辑计算模型、基于DNA自组装的逻辑计算模型、基于其他分子技术和分子材料的DNA逻辑计算模型。首先阐述了DNA逻辑计算的研究背景和研究目的以及现阶段在生物分子检测、疾病诊断、多因素分析和生物成像等领域的应用并简述其相关概念;然后梳理各DNA逻辑计算模型的研究历史和现状,分析各类逻辑计算模型所应用的分子操控技术和分子材料以及优缺点和应用前景;最后归纳总结DNA逻辑计算领域当前研究热点和发展前景,为未来提出全新的计算方式奠定基础,为信息、医疗等领域提供更好的服务。     

基于环形DNA分子的一种求解最大集团的计算模型

文中提出了一种基于环形DNA分子的新型计算模型.该模型的核心构成包括环形DNA分子,链霉亲和素包被的磁珠及环化酶.通过应用该模型解决了一个5个顶点的最大团问题,证明了该模型的可行性.在整个计算过程中,真解的搜索是借助于磁珠和环化酶,DNA分子结构在线性和环形之间相互转化.环形DNA分子的应用极大地减少了计算所需的时间和空间,算法的时间和空间复杂度均为O(n+m).对于解决一个n个节点的最大团问题,这种算法和枚举型算法相比,在搜索过程中所需试管数较少,只需n+1个试管,而利用枚举型算法则需要2n个试管.另外,文中构建的非枚举型初始解空间大大提高了DNA计算机的存储和计算能力.在将来,这种新型的DNA计算模型或许会成为一种解决某些NP完全问题的有效工具.     

基于定位的数据聚类新算法

针对现有聚类算法计算复杂度普遍较高的问题,提出了一种基于定位的方法。该算法采用空间定位的方法将数据对象映射到特征空间中,并利用空间立方体的某些特殊顶点定位任一数据点;通过计算数据点与空间立方体顶点群的距离差异,完成聚类过程。在电信数据集上的实验结果表明,算法的时间复杂度降至O(N)级别。     

基于蚁群优化聚类算法的DNA序列分类方法

针对目前聚类算法在分析DNA序列数据时的低效性和分类精度低问题,提出一种基于蚁群优化聚类算法（ACOC）的DNA序列分类方法,在密度函数中加入自适应感应量并应用模拟退火中的α-适应量的冷却策略,采用DNA序列分布特征对DNA序列进行特征提取,并将pearson相关系数引入蚁群聚类算法作为相似性度量。在EMBL-DNA数据库中4个数据集上进行性能测试,与统计聚类和k-means算法的比较表明,该方法具有一定的时间和精度的优越性,适于解决大规模DNA序列数据分类问题。     

求解0-1规划问题的DNA计算模型(英文)

DNA计算是以DNA分子作为数据的一种新型计算模式．在DNA计算中首要面对的问题是编码问题．文中提出了一种双编码方法,利用这种编码方法可以使得在DNA计算的读解过程类似于DNA测序过程,容易实现自动化操作．基于该编码方法所建立的DNA计算模型可用于求解0-1规划问题,只需4次PCR反应即可读取问题的可行解．与其他DNA计算模型相比,该模型具有操作简单、易于实现的优点．     

三维模型面片链码表示方法

将三维模型的三角面片表示与基于体素的链码技术相结合,提出一种基于体素的三维模型面片链码表示方法.首先对三维模型进行基于体素空间的切分,将获得的面片顶点归一化在体素顶点上,构造基于体素三角面片的模型表示;然后依据构造的体素三角面片间连接边与第3顶点的位置关系定义面片链码的数据结构;再根据连接边的类型和方向计算层次三角面片法向量的大小和方向;最后通过逐层遍历体素内归一化的三角面片,获得三维模型的面片链码表示.相应地,给出了面片链码的解码方法.文中比较了面片链码与其他三维模型压缩算法的压缩效率和时间开销,计算了不同体素粒度切分的三维模型与被切分的原始模型之间以及与体素切分模型具有同级别面片数量的原始模型之间的误差,结果表明,该方法能够有效地表达三维模型.     

DNA计算中的数据与计算模型

对DNA计算的通用性及单链、双链、粘性末端、发夹、质粒、k-臂DNA分子等各种数据作了简单介绍,并对基于DNA分子结构特性和基于DNA计算机研制过程两个方面的DNA计算模型进行了分析对比。针对各种不同的DNA数据及特性,提出了混合DNA计算模型的研究思路,并从不同角度论述了混合DNA计算模型的可行性。     

图的最大团与最大独立集粘贴DNA计算模型

粘贴模型(stickermodel)是DNA计算中一个很重要的模型.其主要原理就是采用单双链混合型DNA分子进行编码,其优点在于在生物操作过程中不需要DNA链的延伸,不需要生物酶的作用以及DNA链可重复使用等,因此引起了来自不同学科的学者们的广泛关注与兴趣.文中提出了一种求解图的最大团问题的DNA计算模型,该模型采用了两种基本并行计算处理思想,一种是将图分解成小的子图来处理的并行思想;另一种是进行并行生物操作.     

连通度问题的三维DNA结构进化算法

针对求连通度这一难解问题,提出了三维DNA图结构进化算法。并提出了一种由k-臂DNA分子构建的图结构。在所述方法中3、4臂DNA分子的顶点构造块被选择性地用来构建一些不同的图结构。然后通过凝胶电泳分离,图的连通度便可确定。并且通过引入进化算法的思想,避免了解空间的穷举。     

基于DNA粘附子模型的并行乘法算法

提出了一种基于DNA计算的粘附子模型的并行乘法算法,该算法首先将两个二进制数相乘转变成根据被乘数对乘数进行一系列的移位相加。将被乘数与乘数编码在同一条存储链上,通过组合、分离、设置、清除等四种运算计算出积的值。由于表示输出的DNA链的结构与表示输入的DNA链的结构相同,因此表示输出的DNA链无需做任何改变,就能在后面的运算中重复使用。该算法不仅能用于整数乘法中,还可以很方便地推广到包含小数的乘法运算及多个因数参与的乘法运算中。该算法的突出优点是充分发挥了DNA计算内在的并行计算性,如果参与乘法运算的因数的个数相等,则计算多组乘法运算与计算一组乘法运算所需的时间相同,并且多组乘法运算能从同一个试管内开始。     

Solving the minimum bisection problem using a biologically inspired computational model

The traditional trend of DNA computing aims at solving computationally intractable problems. The minimum bisection problem (MBP) is a well-known NP-hard problem, which is intended to partition the vertices of a given graph into two equal halves so as to minimize the number of those edges with exactly one end in each half. Based on a biologically inspired computational model, this paper describes a novel algorithm for the minimum bisection problem, which requires a time cost and a DNA strand length that are linearly proportional to the instance size.     

一种新的粗糙Leader聚类算法

聚类是数据挖掘领域重要的研究方向.在众多的聚类算法中,Leader算法运用很广泛,但Leader算法没有考虑到聚类分析中内在的不确定性.对Leader算法做了相应改进,加入了粗糙集和粒计算的思想,使其能够处理聚类中固有的不确定性,得到更合理的聚类结果.最后,通过实验证明了该算法的优越性.     

大型数据库中基于邻域连接的层次聚类算法

提出了一种基于邻域连接的层次聚类算法HANL,该算法首先采用分割的方法将数据集划分为若干个子簇,通过对子簇间的连接的分析,建立子簇间的连接构成图,图中带权的边代表了子簇间的连接紧密度。合并连接紧密度高的结点,得到最后的聚类结果。该算法适用于高维数据集,能够对任意形状的簇进行聚类,无论对于数值属性的数据库还是分类属性的数据库都是一个有效的聚类方法。同时这种方法聚类速度快,效率高,具有良好的伸缩性。     

Improving the design of sequences for DNA computing: A multiobjective evolutionary approach

Designing oligonucleotide strands that selectively hybridize to reduce undesired reactions is a critical step for successful DNA computing. To accomplish this, DNA molecules must be restricted to a wide window of thermodynamical and logical conditions, which in turn facilitate and control the algorithmic processes implemented by chemical reactions. In this paper, we propose a multiobjective evolutionary algorithm for DNA sequence design that, unlike preceding evolutionary approaches, uses a matrix-based chromosome as encoding strategy. Computational results show that a matrix-based GA along with its specific genetic operators may improve the performance for DNA sequence optimization compared to previous methods.     

Sticker systems with complex structures

 In this paper, we propose a variant of sticker systems which uses molecules with complex structures. Since the original sticker systems (Paun et al. (1998) [2, 8]) working on double strands of DNA have been studied as a formal model for self-assembly in DNA computing, we extend the sticker systems to working on more complex (higher-order) structures of DNA molecules. The advantage of sticker systems with complex structures is that augmented with weak codings we can obtain the characterization of recursively enumerable languages by using only sticking (hybridization) operations for complex molecules, while the usual sticker systems require more complicated operations such as the simultaneous use of couples of dominoes or coherent computations besides morphisms.     

基于高斯分布的簇间距离计算方法

凝聚的层次聚类算法是一种性能优越的聚类算法,该算法通过不断合并距离相近的簇最终将数据集合划分为用户指定的若干个类别。在聚类的过程中簇间距离计算的准确性是影响算法性能的重要因素。本文提出一种新的基于高斯分布的簇间距离的计算方法,该方法通过簇自身的大小、密度分布等因素改进算法的计算准确性,在不同文本集合上与现有的簇间距离计算方法进行了对比实验,实验结果表明该方法有效地改进了层次聚类算法的性能。