基于DNA计算的聚类算法研究
|
摘要
DNA计算作为较新兴的跨学科技术在理论和技术上已经有了很大的进展,在解决NP问题上有着很大的优势。它把数学和生物有机的结合起来,用生物工具来解答数学问题,其本质就是利用大量不同的核酸分子杂交,产生类似某种数学计算过程的组合的结果,并对其进行筛选来完成。
随着当今信息化产业的发展迅速,大量的信息需要进行数据分析,聚类分析发挥着重要的作用。许多聚类算法都与图有关,最典型的是层次聚类、网格聚类和图聚类。
本课题把聚类中的数据对象转化成为图中的节点,那么簇的生成就转化为节点的组合问题,进而把善于解决组合问题的DNA计算应用到聚类中去,在DNA计算应用中是新的尝试,也为聚类分析提供了新的思路和方法。
本文的研究内容如下:
(1)利用面向对象方法学分析并描述DNA计算的相关概念和技术。
(i)有关DNA计算的概念类图,包括各种类型的DNA分子类图。通过分析DNA分子不同类型之间的关系以及转化过程,建立它们之间的相互转化关系类图。通过该类图可以明确某类型DNA分子是由另外哪种DNA分子在什么条件下转化而来的;
(ii)通过分析基本生化操作的过程,建立关于杂交、连接、聚合、退火和电泳等常用生化操作的顺序图。利用顺序图可以清楚的了解生物反应的全过程,并可以应于计算机的模拟程序设计,为将来的计算机模拟实验提供基础。
DNA计算的面向对象描述与建模不仅可以为计算机模拟生化反应提供编程基础,还可以从计算机科学的角度了解DNA计算的基本概念和相关技术,为DNA计算与软计算的结合提供支持。
(2)利用DNA计算进行聚类。
(i)论文分析了聚类问题的本质,将其转化为可以采用DNA计算解决的组合优化问题或者图论问题。对于样本数据对象的聚类就是一种样本数据的组合方式,这种组合方式保证了类内的样本数据之间的相似度高,而类之间的样本数据相似度低,DNA计算可以获得关于样本数据的所有组合,然后再通过生化反应从中提取出最优的聚类结果。论文还在第三章建立了聚类算法的DNA计算过滤模型和粘贴模型,过滤模型是在Adleman最小模型的基础上建立的,是最常用,也是最简单、易实现的DNA计算模型。粘贴模型现在最常应用于图论问题,因此可以应用于由图论问题表示的聚类分析。论文提出了一种新的思路:将网格转化为“米字图”,在“米字图”中求得候选节点的聚类,进而在理论上证明了将该问题转化为哈密尔顿问题的可行性,证明了DNA计算进行网格聚类的可行性和正确性。
(ii)论文提出了基于DNA计算的层次聚类算法。在第四章中把层次聚类转化为最小生成树的问题,从而利用DNA计算来解决该问题。提出了聚类算法的DNA计算过滤模型和粘贴模型,同时给出了基于过滤模型的编码方案和生化反应设计。
(iii)论文把DNA计算应用到网格聚类方法中。把单元格缩小为一个节点,网格的特殊结构就变成一种特殊的“米字图”。在五章中论文提出了基于“米字图”的过滤模型和粘贴模型,并给出了基于过滤模型的四种不同的编码方案和生物实验设计。这四种编码方案利用节点、边、坐标的不同组合,各有其优点和应用性,但在给出的通用过滤模型下都是可用的,可以使用同一个DNA计算算法,而生物实验又是有区别的,因为生物实验需要根据不同的编码方案设计不同生物操作细节。粘贴模型的建立增加了网格聚类使用DNA计算机的可能,在芯片化和生物技术成熟后将得到更为广泛的应用。
(iv)第六章关于DNA计算的图聚类中的应用。主要包括利用聚类技术解决图像聚类问题,对图进行分割。提出了利用k-medoids算法进行图像分割的DNA过滤模型,并给出了编码方案和生物实验设计。该编码方案根据将图像中的像素点看作是样本数据点,灰度值看作是样本数据点的属性,设定一定的灰度值作为聚类的质心,利用k-medoids的思想将坐标表示的像素点和与质心灰度值的差进行组合,得到节点链和质心链,将其放入试管中参与DNA计算反应。由于DNA存储能力和并行反应特性,在处理大量数据集时比计算机会更加有效率,该算法在面对图像的百万级像素时将显现非常大的优势。
(3)第七章在已提出的基于DNA计算的聚类理论思想的基础上,进一步通过实验来证明其可行性和效果。
(i)通过计算机模拟整个生化反应过程。实验基于节点和边编码方案的网格聚类,通过模拟连接反应获得所有可能解,再通过模拟生物实验将聚类结果解出。该模拟程序完全按照DNA计算的生物实验原理,生成所有可能解,该实验将花费大量的时间,因此聚类的数据量较小,但可以证明编码方案的可行性和DNA计算算法的正确性。
(ii)利用并行计算算法模拟整个生化反应过程。由于并行反应时DNA计算的巨大优势,所以实验将连接反应分配到每个DNA分子链上进行,该程序运行所获得的运算时间就是包含最多节点的簇的聚类时间。该实验从并行反应的角度验证了DNA计算的并行优势,并应用于规模较大,形状较复杂的数据集中,聚类效果同原聚类算法相同,而计算时间要比串行和原聚类时间少。
(iii)建立模型来证明其可行性。采用坐标的编码方式,并改进了DNA连接过程的扫描方式,提高了计算机的模拟速度,实现起来较为简单。本实验可以很好的证明理论思想的可行性,并应用于较复杂的样本数据点。在该实验中给出了一种模拟扫描邻居节点的方法,该方法既可以节省扫描时间,又可以避免非解和重复链的生成。
(iv)与原有的CLIQUE算法做了比较,发现程序的运算时间只与候选节点的数量和结构有关,如果样本数据点较为紧密,那么运算时间小,如果分散则运算时间长。聚类效果上和原有的聚类算法没有任何差别。与Bakar提出的基于DNA计算的聚类算法比较,由于网格聚类的优势,使得聚类时间大大缩短,并且编码设计上也具有一定的优势。
(4)给出了一套生物实验过程,包括编码设计方案、生物实验算法以及生物实验过程。详细描述了如何利用DNA计算进行聚类分析的生化实验操作步骤,并得到的预期效果。
(4)算法复杂度的讨论分为两个方面:一个是在计算机模拟的基础上对基于DNA计算的聚类算法进行了复杂度的讨论,在计算机编程基础上,讨论按照计算机编程的思想分析DNA计算的时间复杂度;另一个是DNA计算算法的复杂度讨论,讨论了生化实验的消耗和反应时间。
(5)论文还给出了一种生成符合热力学约束条件的DNA短链的遗传算法,用于模拟实验。该算法可以生成较短的一定数量的符合热力学约束条件的DNA单链分子,可用于计算机模拟实验和真正的生物实验中。
(6)论文在第八章将DNA计算应用到三种不同的领域中,分别是山东省17城市的区域划分、乳腺癌患者的术后情况和图像分割处理。采用层次聚类的方法对山东省的17个城市进行了聚类,通过模拟DNA计算获得了聚类结果,可以将17个城市划分为三个零售商的区域,区域内的城市会有一条最短路径相连,对物流和区域运输都是有益的。利用网格聚类对UCI提供的真实医学数据集进行了聚类,该数据是三维数据,首先将数据降到二维,利用DNA计算获得二维聚类结果,在取交集得到三维的聚类结果。将DNA计算应用到图像分割中,处理了车牌辨识和手写辨识两幅图片,并利用k-medoids算法对有背景的手写辨识进行了三类分割,将图像分割为背景、黑色和白色,更能清楚的辨识重要信息。
论文提出的新的基于DNA计算的聚类算法研究,为聚类算法研究提供新的工具,同时为DNA计算开辟新的应用邻域。随着数据库的越来越庞大,数据挖掘在数据存储和处理速度等方面都提出了更高的要求,由于DNA计算的海量存储特性及其计算的并行性,在解决聚类问题方面有着极大的潜力,不论在生物信息领域,还是数据挖掘领域都有着重要意义。论文遗憾之处没有进行生物实验,但所提出的模型、算法和编码设计都是建立在原有的模型和生物实验的基础上的,依据原有模型的正确性说明论文中提出的理论是可行的,并且在理论方面和计算机模拟方面都得到的证明和验证。
DNA computing has been applied in broad fields such as graph theory, finite state problems and combinatorial problem. DNA computing approaches are more suitable used to solve many combinatorial problems because for the vast parallelism and high-density storage. Most clustering algorithms exhibit polynomial or exponential complexity. The problem becomes even far more challenging when the number of clusters is unknown and the data set become huge. The appearance of DNA computing provides an interesting and viable alternative. The clustering is the combinational problem of the patterns. DNA computing is suitable to solve clustering problem considering the patterns as the vertexes in a graph. The researching content is as follow:
(1) Using objected-oriented method to analysis the DNA computing.
(i) The class programs about DNA molecular and bio-chemical operations are given. The DNA molecular class program contains many different sorts DNA molecular and their relationship. Though analysis the characters of the different DNA molecular, we can know how the DNA molecular can change to another sort DNA molecular.
(ii) Though analysis the bio-chemical operations, many sequence programs are given. These sequence programs are about the bio-chemical such as ligation, hybridization, annealing, disnaturing, gel- electrophoresis. We can use these sequence programs to know the whole processing bio-chemical reactions and apply these models to the programming during simulation in silicon computer.
(2) The research about clustering algorithms based on DNA computing.
(i) We analysis the basic idea of the clustering algorithm and change the clustering problem to the combinational problem or the graph theory problem. The clustering result is a combination of the patterns. This combinational method can ensure that the similarity of the patterns in a same group is very high and the distance between two groups is very long. DNA computing can get all possible combinations of the patterns. Then we can separate the optimal clustering result from these DNA strands. The sticker model is given including its algorithm. This DNA model can use the any clustering problem. We change the grid-based clustering algorithm into a special graph clustering algorithm. This kind of graph has a special structure and it is easy to encoding the DNA strands. For proving the feasible of this algorithm, we change the clustering problem to the Hamilton circle problem. Theoretically, this algorithm is feasible.
(ii) In the research of the hierarchical clustering based on DNA computing, we change the hierarchical clustering algorithm to the MST problem and use DNA computing to execute clustering. We gave a basic model and a sticker model for hierarchical clustering. According to the model’s algorithm we suppose an encoding method and the design to the bio-chemical reactions.
(iii) Research about the grid-based clustering using the DNA computing. We consider the cell into a vertex in a graph. Each vertex in a special graph has eight neighboring vertexes and the axes have relationship between the neighboring vertexes. So we stated four encoding strategies. These encoding methods use the combinations of the DNA segments of the vertexes, the edge and the axes. Each method has its characters. The basic model can be used for any encoding method, but the bio-chemical experiments are different. Because these experiments are designed based on the different DNA strands. The sticker model is built with an example.
(iv) DNA computing is applied in the graph clustering. In this thesis, we use DNA computing to solve the image segmentation problem. The clustering algorithm usually is used in the image segmentation problem. We gave a sticker model and algorithm to solve the image segmentation using k-medoids algorithm. The pixel point can be considered to the patterns during the clustering. The grey level can be considered as the attribute of the patterns. So the image segmentation problem just is the clustering problem with two given gray level, such as white and black. The encoding method is based on the k-medoids algorithm. The combinational DNA strand is composed by the vertex DNA segment and medoid DNA segment. The vast density storage and parallels of the DNA computing will be meaningful in front of the million level images.
(3) The feasible experiment with the synthetic data. We gave three experiments to prove the feasible of the DNA computing model and encoding strategy.
(i) Simulation the real process of the bio-chemical reactions. We use silicon computer to simulate the whole process of the DNA computing. Get all possible combinations of the vertexes and separate the useful result in the test tube. This experiment will cost large time and space because it will generate the entire possible combinational double-stranded DNA molecular. So we gave a small dataset for this experiment. The feasibility of the DNA computing model and algorithm is proved.
(ii) Using the parallel algorithm to simulate the DNA computing. The experiment can simulate the parallel reactions of the DNA computing like in the test tube. So the time will be saved. We use the large dataset and complex geometry graph fro this experiment.
(iii) Build a mathematic model to simulate the process of the clustering based on DNA computing. Improve the scan method during the ligation reaction and increase the speed of the simulation. This neighboring vertex scan method can induce the generation of the errors and duplicate DNA strands. The complex geometry graph is used in this experiment and we get the good clustering result.
(iv) The simulation programming is compared with the CLIQUE algorithm. We find that the calculating time is related with the number of the candiate vertexes. If the patterns are density, the time is small, and if the patterns are loose, the time is large. The result is the same as the old clustering algorithm.
(4) Discussing of the complexity of the time during the simulation in silicon computer.
(5) A genetic algorithm for generating the DNA strand is given in this thesis. Designing DNA strands is one of the most practical and important research topic in DNA computing. An improved genetic algorithm for designing of the equal-length single-stranded DNA sequences is proposed, especially for the short DNA sequences needed in the DNA computing experiment. This algorithm can satisfy certain combinatorial and thermodynamic constraints such as GC content constraint, Hamming distance constraint and similar constraint. It can generate the good short DNA sequences quickly by giving up the bad sequences in every generation. Finally, through analysis the experiment data, two functions are given to estimate the number of the DNA sequences satisfied GC content constraint and Hamming distance constraint.
(6) We use DNA computing to solve three real problems. One is the geographic division of the Shandong province with 17 cities. We design the DNA computing model and algorithm to cluster the 17 cities into three groups. The basic idea used MST algorithm. The other experiment is to use the real data from UCI. And in the third experiment, the DNA computing is applied in the image segmentation of the plate and writing image.
DNA computing is a new techniques for the clustering algorithm and the clustering algorithm is a new application field for the DNA computing. With increasing the database, the requirement of the storage and computing speed is higher and higher. The appearance of the DNA computing is meaningful the clustering problems. Although there is no real bio-chemical experiment in the lab, the model and the encoding stagy are both based on the old model and algorithm. So the feasibility and validity are not necessary to worry about. Factually, in the thesis we gave a theory proving and experiment to support the models.
随着当今信息化产业的发展迅速,大量的信息需要进行数据分析,聚类分析发挥着重要的作用。许多聚类算法都与图有关,最典型的是层次聚类、网格聚类和图聚类。
本课题把聚类中的数据对象转化成为图中的节点,那么簇的生成就转化为节点的组合问题,进而把善于解决组合问题的DNA计算应用到聚类中去,在DNA计算应用中是新的尝试,也为聚类分析提供了新的思路和方法。
本文的研究内容如下:
(1)利用面向对象方法学分析并描述DNA计算的相关概念和技术。
(i)有关DNA计算的概念类图,包括各种类型的DNA分子类图。通过分析DNA分子不同类型之间的关系以及转化过程,建立它们之间的相互转化关系类图。通过该类图可以明确某类型DNA分子是由另外哪种DNA分子在什么条件下转化而来的;
(ii)通过分析基本生化操作的过程,建立关于杂交、连接、聚合、退火和电泳等常用生化操作的顺序图。利用顺序图可以清楚的了解生物反应的全过程,并可以应于计算机的模拟程序设计,为将来的计算机模拟实验提供基础。
DNA计算的面向对象描述与建模不仅可以为计算机模拟生化反应提供编程基础,还可以从计算机科学的角度了解DNA计算的基本概念和相关技术,为DNA计算与软计算的结合提供支持。
(2)利用DNA计算进行聚类。
(i)论文分析了聚类问题的本质,将其转化为可以采用DNA计算解决的组合优化问题或者图论问题。对于样本数据对象的聚类就是一种样本数据的组合方式,这种组合方式保证了类内的样本数据之间的相似度高,而类之间的样本数据相似度低,DNA计算可以获得关于样本数据的所有组合,然后再通过生化反应从中提取出最优的聚类结果。论文还在第三章建立了聚类算法的DNA计算过滤模型和粘贴模型,过滤模型是在Adleman最小模型的基础上建立的,是最常用,也是最简单、易实现的DNA计算模型。粘贴模型现在最常应用于图论问题,因此可以应用于由图论问题表示的聚类分析。论文提出了一种新的思路:将网格转化为“米字图”,在“米字图”中求得候选节点的聚类,进而在理论上证明了将该问题转化为哈密尔顿问题的可行性,证明了DNA计算进行网格聚类的可行性和正确性。
(ii)论文提出了基于DNA计算的层次聚类算法。在第四章中把层次聚类转化为最小生成树的问题,从而利用DNA计算来解决该问题。提出了聚类算法的DNA计算过滤模型和粘贴模型,同时给出了基于过滤模型的编码方案和生化反应设计。
(iii)论文把DNA计算应用到网格聚类方法中。把单元格缩小为一个节点,网格的特殊结构就变成一种特殊的“米字图”。在五章中论文提出了基于“米字图”的过滤模型和粘贴模型,并给出了基于过滤模型的四种不同的编码方案和生物实验设计。这四种编码方案利用节点、边、坐标的不同组合,各有其优点和应用性,但在给出的通用过滤模型下都是可用的,可以使用同一个DNA计算算法,而生物实验又是有区别的,因为生物实验需要根据不同的编码方案设计不同生物操作细节。粘贴模型的建立增加了网格聚类使用DNA计算机的可能,在芯片化和生物技术成熟后将得到更为广泛的应用。
(iv)第六章关于DNA计算的图聚类中的应用。主要包括利用聚类技术解决图像聚类问题,对图进行分割。提出了利用k-medoids算法进行图像分割的DNA过滤模型,并给出了编码方案和生物实验设计。该编码方案根据将图像中的像素点看作是样本数据点,灰度值看作是样本数据点的属性,设定一定的灰度值作为聚类的质心,利用k-medoids的思想将坐标表示的像素点和与质心灰度值的差进行组合,得到节点链和质心链,将其放入试管中参与DNA计算反应。由于DNA存储能力和并行反应特性,在处理大量数据集时比计算机会更加有效率,该算法在面对图像的百万级像素时将显现非常大的优势。
(3)第七章在已提出的基于DNA计算的聚类理论思想的基础上,进一步通过实验来证明其可行性和效果。
(i)通过计算机模拟整个生化反应过程。实验基于节点和边编码方案的网格聚类,通过模拟连接反应获得所有可能解,再通过模拟生物实验将聚类结果解出。该模拟程序完全按照DNA计算的生物实验原理,生成所有可能解,该实验将花费大量的时间,因此聚类的数据量较小,但可以证明编码方案的可行性和DNA计算算法的正确性。
(ii)利用并行计算算法模拟整个生化反应过程。由于并行反应时DNA计算的巨大优势,所以实验将连接反应分配到每个DNA分子链上进行,该程序运行所获得的运算时间就是包含最多节点的簇的聚类时间。该实验从并行反应的角度验证了DNA计算的并行优势,并应用于规模较大,形状较复杂的数据集中,聚类效果同原聚类算法相同,而计算时间要比串行和原聚类时间少。
(iii)建立模型来证明其可行性。采用坐标的编码方式,并改进了DNA连接过程的扫描方式,提高了计算机的模拟速度,实现起来较为简单。本实验可以很好的证明理论思想的可行性,并应用于较复杂的样本数据点。在该实验中给出了一种模拟扫描邻居节点的方法,该方法既可以节省扫描时间,又可以避免非解和重复链的生成。
(iv)与原有的CLIQUE算法做了比较,发现程序的运算时间只与候选节点的数量和结构有关,如果样本数据点较为紧密,那么运算时间小,如果分散则运算时间长。聚类效果上和原有的聚类算法没有任何差别。与Bakar提出的基于DNA计算的聚类算法比较,由于网格聚类的优势,使得聚类时间大大缩短,并且编码设计上也具有一定的优势。
(4)给出了一套生物实验过程,包括编码设计方案、生物实验算法以及生物实验过程。详细描述了如何利用DNA计算进行聚类分析的生化实验操作步骤,并得到的预期效果。
(4)算法复杂度的讨论分为两个方面:一个是在计算机模拟的基础上对基于DNA计算的聚类算法进行了复杂度的讨论,在计算机编程基础上,讨论按照计算机编程的思想分析DNA计算的时间复杂度;另一个是DNA计算算法的复杂度讨论,讨论了生化实验的消耗和反应时间。
(5)论文还给出了一种生成符合热力学约束条件的DNA短链的遗传算法,用于模拟实验。该算法可以生成较短的一定数量的符合热力学约束条件的DNA单链分子,可用于计算机模拟实验和真正的生物实验中。
(6)论文在第八章将DNA计算应用到三种不同的领域中,分别是山东省17城市的区域划分、乳腺癌患者的术后情况和图像分割处理。采用层次聚类的方法对山东省的17个城市进行了聚类,通过模拟DNA计算获得了聚类结果,可以将17个城市划分为三个零售商的区域,区域内的城市会有一条最短路径相连,对物流和区域运输都是有益的。利用网格聚类对UCI提供的真实医学数据集进行了聚类,该数据是三维数据,首先将数据降到二维,利用DNA计算获得二维聚类结果,在取交集得到三维的聚类结果。将DNA计算应用到图像分割中,处理了车牌辨识和手写辨识两幅图片,并利用k-medoids算法对有背景的手写辨识进行了三类分割,将图像分割为背景、黑色和白色,更能清楚的辨识重要信息。
论文提出的新的基于DNA计算的聚类算法研究,为聚类算法研究提供新的工具,同时为DNA计算开辟新的应用邻域。随着数据库的越来越庞大,数据挖掘在数据存储和处理速度等方面都提出了更高的要求,由于DNA计算的海量存储特性及其计算的并行性,在解决聚类问题方面有着极大的潜力,不论在生物信息领域,还是数据挖掘领域都有着重要意义。论文遗憾之处没有进行生物实验,但所提出的模型、算法和编码设计都是建立在原有的模型和生物实验的基础上的,依据原有模型的正确性说明论文中提出的理论是可行的,并且在理论方面和计算机模拟方面都得到的证明和验证。
DNA computing has been applied in broad fields such as graph theory, finite state problems and combinatorial problem. DNA computing approaches are more suitable used to solve many combinatorial problems because for the vast parallelism and high-density storage. Most clustering algorithms exhibit polynomial or exponential complexity. The problem becomes even far more challenging when the number of clusters is unknown and the data set become huge. The appearance of DNA computing provides an interesting and viable alternative. The clustering is the combinational problem of the patterns. DNA computing is suitable to solve clustering problem considering the patterns as the vertexes in a graph. The researching content is as follow:
(1) Using objected-oriented method to analysis the DNA computing.
(i) The class programs about DNA molecular and bio-chemical operations are given. The DNA molecular class program contains many different sorts DNA molecular and their relationship. Though analysis the characters of the different DNA molecular, we can know how the DNA molecular can change to another sort DNA molecular.
(ii) Though analysis the bio-chemical operations, many sequence programs are given. These sequence programs are about the bio-chemical such as ligation, hybridization, annealing, disnaturing, gel- electrophoresis. We can use these sequence programs to know the whole processing bio-chemical reactions and apply these models to the programming during simulation in silicon computer.
(2) The research about clustering algorithms based on DNA computing.
(i) We analysis the basic idea of the clustering algorithm and change the clustering problem to the combinational problem or the graph theory problem. The clustering result is a combination of the patterns. This combinational method can ensure that the similarity of the patterns in a same group is very high and the distance between two groups is very long. DNA computing can get all possible combinations of the patterns. Then we can separate the optimal clustering result from these DNA strands. The sticker model is given including its algorithm. This DNA model can use the any clustering problem. We change the grid-based clustering algorithm into a special graph clustering algorithm. This kind of graph has a special structure and it is easy to encoding the DNA strands. For proving the feasible of this algorithm, we change the clustering problem to the Hamilton circle problem. Theoretically, this algorithm is feasible.
(ii) In the research of the hierarchical clustering based on DNA computing, we change the hierarchical clustering algorithm to the MST problem and use DNA computing to execute clustering. We gave a basic model and a sticker model for hierarchical clustering. According to the model’s algorithm we suppose an encoding method and the design to the bio-chemical reactions.
(iii) Research about the grid-based clustering using the DNA computing. We consider the cell into a vertex in a graph. Each vertex in a special graph has eight neighboring vertexes and the axes have relationship between the neighboring vertexes. So we stated four encoding strategies. These encoding methods use the combinations of the DNA segments of the vertexes, the edge and the axes. Each method has its characters. The basic model can be used for any encoding method, but the bio-chemical experiments are different. Because these experiments are designed based on the different DNA strands. The sticker model is built with an example.
(iv) DNA computing is applied in the graph clustering. In this thesis, we use DNA computing to solve the image segmentation problem. The clustering algorithm usually is used in the image segmentation problem. We gave a sticker model and algorithm to solve the image segmentation using k-medoids algorithm. The pixel point can be considered to the patterns during the clustering. The grey level can be considered as the attribute of the patterns. So the image segmentation problem just is the clustering problem with two given gray level, such as white and black. The encoding method is based on the k-medoids algorithm. The combinational DNA strand is composed by the vertex DNA segment and medoid DNA segment. The vast density storage and parallels of the DNA computing will be meaningful in front of the million level images.
(3) The feasible experiment with the synthetic data. We gave three experiments to prove the feasible of the DNA computing model and encoding strategy.
(i) Simulation the real process of the bio-chemical reactions. We use silicon computer to simulate the whole process of the DNA computing. Get all possible combinations of the vertexes and separate the useful result in the test tube. This experiment will cost large time and space because it will generate the entire possible combinational double-stranded DNA molecular. So we gave a small dataset for this experiment. The feasibility of the DNA computing model and algorithm is proved.
(ii) Using the parallel algorithm to simulate the DNA computing. The experiment can simulate the parallel reactions of the DNA computing like in the test tube. So the time will be saved. We use the large dataset and complex geometry graph fro this experiment.
(iii) Build a mathematic model to simulate the process of the clustering based on DNA computing. Improve the scan method during the ligation reaction and increase the speed of the simulation. This neighboring vertex scan method can induce the generation of the errors and duplicate DNA strands. The complex geometry graph is used in this experiment and we get the good clustering result.
(iv) The simulation programming is compared with the CLIQUE algorithm. We find that the calculating time is related with the number of the candiate vertexes. If the patterns are density, the time is small, and if the patterns are loose, the time is large. The result is the same as the old clustering algorithm.
(4) Discussing of the complexity of the time during the simulation in silicon computer.
(5) A genetic algorithm for generating the DNA strand is given in this thesis. Designing DNA strands is one of the most practical and important research topic in DNA computing. An improved genetic algorithm for designing of the equal-length single-stranded DNA sequences is proposed, especially for the short DNA sequences needed in the DNA computing experiment. This algorithm can satisfy certain combinatorial and thermodynamic constraints such as GC content constraint, Hamming distance constraint and similar constraint. It can generate the good short DNA sequences quickly by giving up the bad sequences in every generation. Finally, through analysis the experiment data, two functions are given to estimate the number of the DNA sequences satisfied GC content constraint and Hamming distance constraint.
(6) We use DNA computing to solve three real problems. One is the geographic division of the Shandong province with 17 cities. We design the DNA computing model and algorithm to cluster the 17 cities into three groups. The basic idea used MST algorithm. The other experiment is to use the real data from UCI. And in the third experiment, the DNA computing is applied in the image segmentation of the plate and writing image.
DNA computing is a new techniques for the clustering algorithm and the clustering algorithm is a new application field for the DNA computing. With increasing the database, the requirement of the storage and computing speed is higher and higher. The appearance of the DNA computing is meaningful the clustering problems. Although there is no real bio-chemical experiment in the lab, the model and the encoding stagy are both based on the old model and algorithm. So the feasibility and validity are not necessary to worry about. Factually, in the thesis we gave a theory proving and experiment to support the models.
引文
[1] Han, J.,M. Kamber, Data Mining: Concepts and Techniques, Second Edition[M]. 2007, Singapore: Elsevier.
[2] Kaufman, L.,P.J. Rousseeuw, Finding groups in data: an introduction to cluster analysis[M]. 2008, New York, USA: John Wiley &Sons.
[3] T.Ng, R.,J. Han. Efficient and effective clustering method for spatial data mining[C]. in Proceedings of the International Conference on Very Large Data Bases. 1994. Santiago,Chile.
[4] Zhang, T., R. Ramakrishnan,M. Livny. BIRCH: An efficient data clustering method for very large databases[C]. in Proceedings of the 1996 ACM SIGMOD international conference on Management of data. 1996. Montreal, Canada: ACM: p. 103-114.
[5] Guha, S., R. Rastogi,K. Shim. CURE: An efficient clustering algorithm for large databases[C]. in Proceedings of the 1998 ACM SIGMOD international conference on Management of data. 1998. Seattle, WA: ACM: p. 73-84.
[6] Guha, S., R. Rastogi,K. Shim. Rock:A robust clustering algorithm for categorical attributes[C]. in Proceedings of International Conference on Data Engineering. 1999. Sydney, Australia: p. 512-521.
[7] Karypis, G., E.-H. Han,V. Kumar, Chameleon: hierarchical clustering using dynamic modeling[J]. Computer 2002. 32(9): p. 68-75.
[8] Ester, M., et al. A density-based algorithm for discovering clusters in large spatial databases[C]. in Proceedings of the International Conference on Knowledge Discover and Data Mining. 1996. Portland, OR: AAAI: p. 226-231.
[9] Ankerst, M., et al. OPTICS: Ordering points to identify the clustering structure[C]. in Proceedings of the 1999 ACM SIGMOD international conference on Management of data. 1999. Philadelphia,PA: ACM: p. 49-60.
[10] Hinneburg, A.,D. A.Keim. An efficient approach to clustering in large multimedia databases with noise[C]. in Proceedings of the 1998 International Conference Knowledge Discovery and Data Mining. 1998. New York,USA: AAAI: p. 58-65.
[11] Wang, W., J. Yang,R. Muntz. STING:A statistical information grid approach to spatial data mining[C]. in Proceedings of the International Conference on Very Large Data Bases. 1997.Athens,Greece: p. 186-195.
[12] Sheikholeslami, G., S. Chatterjee,A. Zhang. WaveCluster: A multiresolution clustering approach for very large spatial databases[C]. in Proceedings of the 24th VLDB Conference. 1998. New York,USA: p. 428-439.
[13] Agrawal, R., et al. Automatic subspace clustering of high dimensional data for data mining applications[C]. in Proceedings of the 1998 ACM SIGMOD international conference on Management of data 1998: SIGMOD'98: p. 94-105.
[14] Adleman, L.M., Molecular Computation of Solutions to Combinatorial Problems[J]. Science, 1994. 266(5187): p. 1021-1024.
[15] Lipton, R.J., DNA solution of hard computational problems[J]. Science, 1995. 268(5210): p. 542-545.
[16] Ouyang, Q., et al., DNA solution of the maximal clique problem[J]. Science, 1997. 278(5337): p. 446-9.
[17] T.Head, et al., Computing with DNA by operating on plasmids[J]. Biosystems, 2000. 57(2): p. 87-93.
[18] D.Faulhammer, et al. Molecular computation: RNA solutions to chess problems[C]. in Proceedings of the Natl Acas. Sci. 2000. Princeton,USA: p. 1328-1330.
[19]郭晓娟,刘晓霞,李晓玲,层次聚类算法的改进及分析[J].计算机应用与软件, 2005. 25(6): p. 243-244.
[20]龙真真, et al.,一种改进的Chameleon算法[J].计算机工程, 2009. 35(20): p. 189-191.
[21] Goil, S., H. Nagesh,A. Choudhary, MAFIA: Efficient and Scalable Subspace Clustering for Very Large Data Sets. 1999, Center for Parallel and Distributed Computing
[22] Cheng, C., A.W. Fu,Y. Zhang. Entropy-based subspace clustering for mining numberical data[C]. in Proceedings of the 5th ACM SIGKDD international conference on Knowledge discovery and data mining 1999. New York, USA: p. 84-93.
[23] Rickard, J.T., R.R. Yager,W. Miller, Mountain clustering on non-uniform grids using P-tree[J]. Fuzzy optimization and decision making, 2005. 4: p. 87-102.
[24] Hinneburg, A.,D.A. Keim. Optimal Grid-Clustering: Towards Breaking the Curse of Dimensionality in High-Dimensional Clustering[C]. in Proceedings of the 25th International Conference on Very Large Databases. 1999. Edinburgh, Scotland: Morgan Kaufmann: p.506-517.
[25] Aggarwal , C.C., et al. Fast algorithms for projected clustering[C]. in Proceedings of the ACM SIGMOD Conference. 1999. Philadelphia,PA: p. 61-72.
[26] Aggarwal, C.C.,P.S. Yu. Finding generalized projected clusters in high dimensional spaces[C]. in Proceedings of the 2000 ACM SIGMOD international conference on Management of data 2000. Dallas, Texas,USA: ACM.
[27]冯兴杰,黄亚楼,带约束条件的聚类算法研究[J].计算机工程与应用, 2005. 7: p. 12-15.
[28]陈卓,孟庆春,一种基于网络和密度凝聚点的快速聚类算法[J].哈尔滨工业大学学报, 2005. 27(12): p. 1654-1657.
[29] Nagesh, H.S., A. Choudhary,S. Goil, A Scalable Parallel Subspace Clustering Algorithm for Massive Data Sets in 2000 International Conference on Parallel Processing. 2000, IEEE Computer Society: Toronto, Canada. p. 477
[30]冯永, et al.,一种有效的并行高维聚类算法[J].计算机科学, 2005. 32(3): p. 216-218.
[31] T.Zahn, C., Graph-Theoretical Methods for Detecting and Describing Gestalt Clusters[J]. IEEE Transactions on Computers, 1971. C-20(1): p. 68-86.
[32] Wu, Z.,Y.R. Leah, An optimal graph theoretic approach to data clustering theory and its application to image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1993. 15(11): p. 1101-1113.
[33] Gamiol, J.C., S.J. Belongie,S. Majumdar. Normalized cuts for spinal MRI segmentation[C]. in Proceedings of CARS. 2002. France, Paris.
[34] Zhuykov, A.,L. Sarycheva, Cluster analysis of territories by the totality of ecological and socioeconomic indices[J]. Geoscience and Remote Sensing Symposim, 2001. 4: p. 1971-1972.
[35] Reif, J.H., Paradigms for Biomolecular Computation, in First International Conference on Unconventional Models of Computation J.C.a.M.J.D. C.S.Calude, Editor. 1998, Unconverntional Models of Computation, DMTCS Series,Springer-Verlag: Auckland,New Zealand. p. 72-93.J.C.a.M.J.D. C.S.Calude
[36] Guarnieri, F.,C. Bancrof, Use of a horizontal chain reactionfor DNA-based addition, in Discrete Mathematics and Theoretical Computer Science. 1999, DIMACS. p. 105-116
[37] Guainieri, F., M. Fliss,C. Bancroft, Making DNA Add[J]. Science, 1996. 273(5272): p. 220-223.
[38] Orlian, M., F. Guarnieri,C. Bancroft, Parallel primer extension horizontal chain reactions as a paradigm of parallel DNA-based computation, in DIMACS:Series in Discrete Matematics and Theoretical Computer Science. 1998, DMIACS Workshop on DNA Based Computers. p. 142-158
[39] H.Leete, T., et al., Bit Operations Using a DNA Template, in Proceedings of the Third DIMACS Workshop on DNA-based Computers. 1997, University of Rochester. Computer Science Department: Philadephia, USA. p. 159-366
[40] Gupta, V., S. Parthasarathy,M.J. Zaki, Arithmetic and logic operations with DNA in 3rd DIMACS Workshop on DNA-based Computers. 1997, University of Rochester. Computer Science Department: Philadelphia,USA. p. 212-232
[41] Qiu, Z.F.,M. Lu. Arithmetic and logic operations with DNA computers[C]. in Proceedings of the Second IASTED International Conference on Parallel and Distributed Computing and Networks. 1998. Australia: p. 481-486.
[42] Wasiewicz, P.,J. J.Mulawka, Adding numbers with DNA, in 2000 IEEE International Conference on Systems, Man,and Cybernetics. 2000, IEEE Press: Nashville,TN. p. 265-270
[43] Barua, R., et al., Binary Arithmetic for DNA Computers,DNA Computing[A]. 2003, Springer Berlin / Heidelberg. p. 124-132.
[44] H.LaBean, T., E. Winfree,J. H.Reif, Experimental progress in computation by self-assembly of DNA tilings, in In 5th DIMACS Workshop on DNA Based Computers. 2000: Rhode Island. p. 123-140
[45] Hug, H., R. Schuler,A.T. Informatik. DNA-based parallel computation of simple arithmetic[C]. in Proceedings of the 7th International Meeting on DNA Based Computers. 2001. Berlin: Springer: p. 159-166.
[46] Bakar, R.B.A.,J. Watada, Biological Clustering Method for Logistic Place Decision Making[J]. Knowledge-Based Intelligent Information and Engineering Systems, 2008(5179): p. 136-143.
[47] Rooss, D.,K.W. Wagner, On the Power of DNA Computing[J]. Information and Computation, 1996. 131: p. 95-109.
[48] Csuhaj-Varjú, E., et al. DNA computing based on splicing: universality results[C]. in Proceedings of the First Annual Pacific symposium on Biocomputing 1996. Hawaii: WorldScience Publication: p. 179-190.
[49] Kari, L., et al., DNA computing, sticker systems, and universality[J]. Acta Informatica, 1998. 35(5): p. 401-420.
[50] P?un, G., On the splicing operation[J]. Discrete Applied Mathematics, 1996. 70(1): p. 57-59.
[51] P?un, G., DNA computing based on splicing: university results[J]. Theoretical Computer Science, 2000. 231(2): p. 275-296.
[52] Ferretti, C.,S. Kabayashi, DNA splicing systems and post systems[J]. Pacific Symposium on Biocomputing, 1996: p. 288-299.
[53] P?un, G., G. Rozenberg,A. Salomaa, Computing by splicing[J]. Theoretical Computer Science, 1996. 168(2): p. 321-336.
[54] Arita, M., M. Hagiya,A. Suyama. Joining and Rotating Data with Molecules[C]. in Processings of 1997 IEEE International Conference on Evolutionary Computation. 1997. Indinapolis,USA: p. 243-248.
[55] P?un, G.,G. Rozenberg, Sticker systems[J]. Theoretical Computer Science, 1998. 204(1-2): p. 183-203.
[56] Ceterchi, R., Cut and paste languages[J]. Grammars, 1999. 2(3): p. 179-188.
[57] Daley, M., et al. Circular contextual insertions/deletions with applications to biomolecular computataions[C]. in String Processing and Information Retrieval Symposium, 1999 and International Workshop on Groupware. 1999. Cancun, Maxico: p. 47-54.
[58] Kari, L. DNA computing based on insertions and deletions[C]. in Proceedings of the conference conceptual tools for understanding dynamics in biological systems. 1996. London: p. 89-95.
[59] Kari, L. From micro-soft to bio-soft: computing with DNA[C]. in Proceedings of bio-comuting and emergent computers. 1997. Sweden: World Scientific Publishing: p. 146-164.
[60] Beaver, D., Computing with DNA[J]. Journal of Computational Biology, 1995. 2(1): p. 1-7.
[61] D.Smith, W., DNA computers in vitro and vivo[A], in DNA based Computers, R. J.Lipton and E. B.Baum, Editors. 1996, American Mathamtical Society: Princeton. p. 121-147.
[62] Winfree, E., On the computation power of DNA annealing and ligation, in Discrete mathmatics and Theoretical Computer Science. 1995, American Methematical Society. p.199-221
[63] Winfree, E., et al., Design and self-assembly of two-dimensional DNA crystals [J]. Nature, 1998. 394: p. 539-544.
[64] Winfree, E., X. Yang,N. C.Seeman, Universal computation via self-assembly of DNA: Some theory and experiments, in Series in Discrete mathematics and Theoretical Computer Science. 1996, DIMACS Workshop. p. 191-223
[65]Baum, E.B., Building an associative memory vastly larger than the brain[J]. Science, 1995. 268: p. 583-585.
[66] Bach, E., et al. DNA models and algorithm for NP-complete problems[C]. in Proceedings of the 11th Annual IEEE Conferences on Computational Complexity(CCC'96). 1996. Philadelphia, PA: p. 290.
[67] Landweber, L.F.,L. Kari, The evolution of cellular computing: nature's solution to a computational problem[J]. Biosystems, 1999. 52(1): p. 3-13.
[68] Sakamoto, K., et al., Molecular Computation by DNA Hairpin Formation[J]. Science, 2000. 288: p. 1223-1227.
[69] Liu, Q., et al., DNA computing on surfaces[J]. Nature, 2000. 403: p. 175-179.
[70] Roweis, S., et al., A sticker-based model for DNA computation[J]. J Comput Biol, 1998. 5(4): p. 615-29.
[71] Jonoskaa, N., S.A. Karlb,M. Saito, Three dimensional DNA structures in computing[J]. Biosystems, 1999. 52(1-3): p. 143-53.
[72]许进,张雷, DNA计算机原理、进展及难点(I):生物计算系统及其在图论中的应用[J].计算机学报, 2003. 26(1): p. 1-11.
[73]许进,黄布毅, DNA计算机:原理、进展及难点(II)计算机“数据库”的形成——DNA分子的合成问题[J].计算机学报, 2005. 28(10): p. 1583-1591.
[74]许进, et al., DNA计算机原理、进展及难点(III):分子生物计算中的数据结构与特性[J].计算机学报, 2007. 30(6): p. 869-880.
[75]许进, et al., DNA计算机原理、进展及难点(IV):论DNA计算机模型[J].计算机学报, 2007. 30(6): p. 881-893.
[76] Ren, L., Y. Ding,S. Shao, DNA bio-soft computing and its application to intelligent control systems[J]. Shanghai Jiaotong University(English version), 1999. E-2(2): p. 97-103.
[77]丁永生,任立红,邵世煌, DNA计算与软计算[J].系统仿真学报(增刊), 2011. 13: p. 198-201,213.
[78]丁永生,邵世煌,任立红, DNA计算与软计算[M]. 2002,北京:科学出版社.
[79]陈仲民,基于DNA计算模型的数据加密与解密[J].计算机与数字工程, 2007. 35(12): p. 86-92.
[80]姚小枝,黄杨,以DNA为载体的信息隐藏方法研究[J].计算机应用于软件, 2008. 25(3): p. 235-248.
[81]张勋才, et al.,基于自组装DNA计算的RSA密码系统破译方案[J].系统工程与电子技术, 2010. 32(5): p. 1094-1099.
[82] Gao, L.,J. Xu, DNA solution of vertex cover problem based on sticker model[J]. Chinese Journal of Computers, 2002. 11(2): p. 280-284.
[83]刘文斌, et al.,最大匹配问题的DNA表面计算模型[J].电子学报, 2003. 31(10): p. 1496-1499.
[84]李源,方辰,欧阳颀,最大集团问题的DNA计算机进化算法[J].科学通报, 2004. 49(5): p. 439-443.
[85]王淑栋,许进,董亚非,图的最小顶点覆盖问题的面上DNA解法[J].小型微型计算机系统, 2004. 25(2): p. 242-244.
[86]周康,同小军,刘文斌,排课表问题的闭环DNA计算模型的算法[J].计算机应用于, 2007. 27(4): p. 991-993.
[87]周康,同小军,许进,基于闭环DNA模型的八皇后问题算法[J].计算机工程与应用, 2007. 43(6): p. 4-6,13.
[88]周康, et al.,最短路问题的闭环DNA算法[J].系统工程与电子技术, 2008. 30(3): p. 556-560.
[89]周康, et al.,集合覆盖问题闭环DNA算法[J].华中科技大学学报(自然科学版), 2010. 38(2): p. 21-25.
[90]周康,同小军,许进,基于闭环DNA的指派问题算法[J].计算机科学, 2007. 34(12): p. 211-213.
[91]周康, et al.,基于闭环DNA计算的最大独立集问题的算法[J].计算机工程, 2008. 34(4): p. 40-44.
[92]刘毅,宋玉阶,收缩背包问题的DNA算法[J].计算机工程与科学, 2007. 29(8): p. 55-57.
[93] Bakar, R.B.A.,J. Watada. A DNA Computing Approach to Cluster-Based Logistic Design[C]. in Proceedings of the 2nd International Conference on Innovative Computing, Information and Control (2007). 2007. Kumamoto: p. 383-383.
[94] Bakar, R.B.A.,J. Watada, A Biologically Inspired Computing Approach to Solve Cluster-Based Determination of Logistic Problem [J]. Biomedical Soft Computing and Human Sciences, 2008. 13(2): p. 59-66.
[95] Bakar, R.B.A., J. Watada,W. Pedrycz, DNA approach to solve clustering problem based on a mutual order[J]. BioSystems, 2008(91): p. 1-12.
[96] Bakar, R.B.A., J. Watada,W. Pedrycz. A DNA computing approach to data clustering based on mutual distance order[C]. in 9th Czech-Japan Seminar (2006). 2006: p. 139-145.
[97] Kim, I.,J. Watada, Decision making with an interpretive structural modeling method using a DNA-based algorithm[J]. IEEE Trans Nanobioscience, 2009. 8(2): p. 181-91.
[98] Kim, I.,J. Watada. A DNA-Based Clustering Method Based on Statistics Adapted to Heterogeneous Coordinate Data[C]. in International Conference on Complex, Intelligence and Software Intensive Systems(2009). 2009: p. 892-897.
[99] Kim, I., J. Watada,J.-Y. Wu, A DNA Encoding Method to Determine and Sequence All Cliques in a Weighted Graph, in 2009 Fourth International Conference on Innovative Computing, Infomation and Control. 2009. p. 1532-1537
[100]王延峰,DNA计算中的编码理论与方法研究[D],116华中科技大学.2007: p. 116.
[101]Ogihara, M.,A. Ray, The minimum DNA computation model and its computational power, in Technical Report. 1997, Department of Computer Science: New York,USA
[102]Ignatova, Z., I. Martinez-Perez,k.-H. Zimmermann, DNA computing Models[M]. 2008: Springer.
[103] Deaton, R., et al. Good Encodings for DNA-based Solutions to Combinatiorial Problems[C]. in 2nd Annual Meeting on DNA Based Computers(1996). 1996. Princeton University: p. 159-171.
[104] Deaton, R., et al. Genetic Search of Reliable Encodings for DNA-based Computation[C]. in Proceedings of the First Annual Conference on Genetic Programming (1996). 1996. Memphis.
[105]Baum, E.B., DNA sequences useful for computation[M]. Princeton University. 1999.
[106]Frutos, A.G., et al., Demonstration of a word design strategy for DNA computing on surfaces[J]. Nucleic Acids Research, 1997. 25: p. 4748-4757.
[107]Garzon, M.,R. Deaton, Codeword design and information encoding in DNA ensembles[J]. Natural Computing, 2004. 3: p. 253-292.
[108]Feldkamp, U., H. Rauhe,W. Banzhaf, Software Tools for DNA Sequence Design[J]. Computer Science, 2003. 4(153-171).
[109]Zhang, K., et al., Improved taboo search algorithm for designing DNA sequences, in Progress in Natural Science. 2008. p. 623-627
[110]崔光照,张勋才,王延峰, DNA计算中编码序列的优化设计方案[J].计算机应用研究, 2007. 24(7): p. 195-201.
[111]张凯, et al.,基于汉明距离的DNA编码约束研究[J].计算机工程与应用, 2008. 44(14): p. 42,52,62.
[112]朱翔鸥,刘文斌,孙川, DNA计算编码研究及其算法[J].电子学报, 2006. 34(7): p. 1169-1174.
[113]Adleman, L.M., Computing with DNA[J]. Science American, 1998.
[114]Aili, H.,Z. Daming, DNA Computing Model for the Minimum Spanning Tree Problem[J]. Eighth International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC'06), 2006: p. 372-377.
[115]Andritsos, P., Data Clustering Techniques. 2002, University of Toronto: Toronto
[116]Arita, M., et al. Improving Sequence Design for DNA Computing[C]. in Proceedings of Genetic and Evolutionary Computation Conference 2000. 2000: Morgan Kaufmann: p. 875-882.
[117]Barreto, S., et al., Using clustering analysis in a capacitated location-routing problem[J]. European Journal of Operational Research, 2006. 179(3): p. 968-977.
[118]Batista, R.B., A. Boukerche,A.C.M.A.d. Melo, A parallel strategy for biological sequence aligment in restricted memory space[J]. Journal of Parallel and Distributed Computing, 2008. 68: p. 548-561.
[119]Benenson, Y., et al., An autonomous molecular computer for logical control of gene expression[J]. Nature, 2004. 429(6990): p. 423-9.
[120]Benenson, Y., et al., Programmable and autonomous computing machine made of biomolecules[J]. Nature, 2001. 414(6862): p. 430-4.
[121]Blain, D., et al., Development, evaluation and benchmarking of simulation software for biomolecule-based computing[J]. Natural Computing, 2004. 3: p. 427-442.
[122]Braich, R.S., et al., Solution of a 20-Variable 3-SAT Problem on A DNA Computer[J]. Science, 2002. 296: p. 499-502.
[123]Brandes, U., M. Gaertler,D. Wagner, Experiment on graph clustering algorithm, in In 11th Europ. Symp. Algorithms. 2001, Springer-Verlag. p. 568-579
[124]Chang, W.-L., M. Ho,M. Guo, Constructing Bio-molecular Databases on a DNA-based Computer[J]. CoRR, 2007. abs/0712.1863.
[125]Chen, J., et al., DNA computing implementing genetic algorithms, in DIMACS Workshop on Evolution as Computation. 1999, Princeon University. p. 39-51
[126]Deaton, R., et al., A DNA based implementation of an evolutionary search for good encodings for DNA computation, in IEEE International Conference on Evolutionary Computation 1997. 1997: Indianapolis, IN, USA. p. 267-271
[127]Ezziane, Z., DNA computing: applications and challenges[J]. Nanotechnology, 2005. 17: p. 27-39.
[128]Flake, G.W., R.E. Tarjan,K. Tsioutsiouliklis, Graph Clustering and Minimum Cut Trees[J]. Internet Mathematics, 2004. 1(4): p. 385-408.
[129]Freund, R.,F. Freund, Test tube systems with controlled applications of rules, in 1997 IEEE International Conference on Evolutionary Computation, . 1997: Indianapolis, IN,USA. p. 237-242
[130]Grady, L., Space Variant Computer Vision: A Graph Theoretic Approach[M]. 2004: Boston University.
[131]Guangwu, L., et al., Algorithm of graph isomorphism with three dimensional DNA graph strucutres[J]. Progress in Natural Science, 2005. 15(2): p. 181-184.
[132]H.Garzon, M., N.Jonoska,S. A.Karl, The bounded complexity of DNA computing[J]. Biosystems, 1999. 52(1-3): p. 63-72.
[133]Head, T., Splicing schiemes and DNA [J]. Nanotechnology, 1992. 1: p. 335-342.
[134]Hsieh, S.-Y.,M.-Y. Chen, A DNA-based solution to the graph isomorphism problem using Adleman-Lipton model with stickers[J]. Applied Mathematics and Computation, 2008. 197: p. 672-686.
[135]Hsieh, S.-Y., C.-W. Huang,H.-H. Chou, A DNA-based graph encoding scheme with its applications to graph isomorphism problems[J]. Applied Mathematics and Computation, 2008. 203: p. 502-512.
[136]Ibrahim, Z., Towards Solving Weighted Graph Problems by Direct-Proportional Length-Based DNA 2004, IEEE Computational Intelligence Society (CIS)
[137]Ibrahim, Z., et al., A New Readout Approach in DNA Computing Based on Real-Time PCR with TaqMan Probes,DNA Computing[A]. 2006, Springer Berlin / Heidelberg. p. 350-359.
[138]Ibrahim, Z., Y. Tsuboi,O. Ono, Direct-Proportional Length-Based DNA Computing for Shortest Path Problem [J]. International Journal of Computer Science and Applications, 2004. 1(1): p. 46-60.
[139]Jain, A.K., M.N. Murty,P.J. Flynn, Data Clustering : Areview[J]. ACM Computing Surveys, 1999. 31(3): p. 265-323.
[140]Jiejun, W.,X. Chuanpei, Test generation for combinational circuits based on DNA computing in 9th International Conference on Electronic Measurement & Instruments, 2009. ICEMI '09. 2009, IEEE Beijing, China. p. 4-650 - 4-653
[141]Jin, X.,Z. Lei, DNA Computer Principle, Advances and Difficulties (I): Biological Computing System and Its Applications to Graph Theory[J]. Chinese Journal of Computers, 2003. 26(1): p. 1-11.
[142]Jain, A.K., M.N. Murty,P.J. Flynn, Data Clustering : Areview[J]. ACM Computing Surveys, 1999. 31(3): p. 265-323.
[143]Kari, L.,G. Thierrin, Contextual insertions/deletions and computability[J]. Information and Computation, 1996. 131(1): p. 47-61.
[144]Kim, S.Y., J.W. Lee,J.S. Bae, Effect of data normalization on fuzzy clustering of DNA microarray data[J]. BMC Bioinformatics, 2006. 7: p. 134.
[145]Lee, J.Y., et al. Efficient initial pool generation for weighted graph problems using parallel overlap assembly[C]. in Preliminary Proceedings of the Tenth International Meeting on DNA Based Computers. 2004: Springer-Verlag: p. 357-364.
[146]Lingqiang, P., et al., Solid phase based DNA solution of the coloring problem[J]. Progress in Natural Science, 2004. 14(5): p. 459-462.
[147]Liu, X.,H. Liu, Spatial Cluster Analysis Based on Evolutionary DNA ComputingTechnique, in 3rd International Conference on Bioinformatics and Biomedical Engineering , 2009. . 2009. p. 1-4
[148]Liu, X.,H. Zhang, Spiking DNA neural trees with applications to conceptual design, in 2011 15th International Conference on Computer Supported Cooperative Work in Design. 2011. p. 276-280
[149]Lu, X., et al. Gene cluster algorithm based on most similarity tree[C]. in Proceedings of the Eighth International Conference on High-Performance Computing in Asia-Pacific Region (HPCASIA'05). 2005: p. 656.
[150]Makrogiannis, S., G. Economou,S. Fotopoulos, Segmentation of color images using multiscale clustering and graph theoretic region synthesis[J]. IEEE Transactions on Systems,Man and Sybernetics, 2005. 35(2): p. 224-234.
[151]Malic, J., S. Belongise,T. Leung, Contour and texture analysis for image segmentation[J]. International Journal of Computer Vision, 2000. 5(1): p. 7-27.
[152]Marathe, A., A.E. Condon,R.M. Corn, On Combinational DNA word design[J]. Discrete Mathematics and Theoretical computer Science, 2000. 54: p. 75-89.
[153]Razzazi, M.,M. Roayaei, Using sticker model of DNA computing to solve domatic partition,kernel and induced path problems[J]. Information and Computation, 2011. 181: p. 3581-3600.
[154]Rooss, D., Recent Developments in DNA-Computing, in 27th International Symposium on Multiple-Valued Logic (ISMVL '97). 1997, IEEE Computer Society: Antigonish. p. 3-9
[155]Roweis, S.,E. Winfree, On the reduction of errors in DNA computation[J]. J Comput Biol, 1999. 6(1): p. 65-75.
[156]Royer, L., et al., Unraveling Protein Networks with Power Graph Analysis[J]. PLoS Computation Biology, 2008. 4(7): p. e1000108.
[157]Rozen, D.E., S. McGrew,A. D.Ellington, Molecular computing: Does DNA compute?[J]. Current Biology, 1996. 16: p. 254-257.
[158]Schaeffer, S.E., Graph Clustering[J]. Computer Science Review, 2007. 1: p. 27-64.
[159]Sekhar, G.P.R., DNA Computing-Graph Algorithms[J].
[160]Sezgin, M.,B. Sankur, Survey over image thresholding techniques and quantiative performance evaluation[J]. Journal of Electronic Iamge, 2004. 13(1): p. 146-165.
[161]Shi, J.,J. Malik. Nomalized Cuts and Image Segmentation[C]. in Proceedins of IEEE Conference on Computer Vision and Pettern Recognition. 1997: p. 731-737.
[162]Shi, L., S. Olafsson,N. Sun, New parallel randomized algorithms for the traveling salesman problem[J]. Computer and Operation Research 1999. 26: p. 371-394.
[163]Shi, N.-Y.,C.-P. Chu, A molecular solution to the hitting-set problem in DNA-based supercomputing[J]. Information Sciences, 2010. 180: p. 1010-1019.
[164]Shiu, H.J., et al., Data hiding methods based upon DNA sequences[J]. Information Sciences, 2010. 180: p. 2196-2208.
[165]Su, X.,L. M.Smith, Demonstration of an universal surface DNA computer[J]. Nucleic Acids Research, 2004. 32(10): p. 3115-3123.
[166]Vlachos, T.,A.G. Constantinides, Graph theoretical approach to color picture segmentation and contour classification[J]. Communications,Speech and Vision, 1993. 140(1): p. 36-45.
[167]Wang, B., et al., Design of DNA Sequence Based on Improved Genetic Algorithm Advanced Intelligent Computing Theories and Applications. With Aspects of Theoretical and Methodological Issues[A]. 2008, Springer Berlin / Heidelberg. p. 9-14.
[168]Wang, S.,J. Siskund, Image segmentation with ratio cut[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003. 25(6): p. 675-690.
[169]Wang, X., et al., Solving the SAT problem using a DNA computing algorithm based on ligase chain reaction[J]. BioSystems, 2008. 91: p. 117-125.
[170]Watada, J., et al. DNA Computing Approach to Optimal Decision Problems[C]. in Proceedings of 2004 IEEE International Conference on Fuzzy Systems. 2004: p. 1579-1584.
[171]Xue, J.,X. Liu, Applying DNA computation to clustering in graph, in 2nd International Conference on Artificial Intelligence, Management Science and Eelctronic Commerce. 2011. p. 986-989
[172]Yamamoto, M., et al., DNA Solution of the Shortest Path Problem by Concentration Control[J]. Genome Informatics, 2000. 11: p. 466-467.
[173]Yin, Z.,J. Zhang, DNA computing in the graph theory[J]. Systems Engineering and Electronics, 2007. 29(7): p. 1159-1163.
[174]Zauner, K.-P., et al., Parallel computing with DNA: Toward the anti-universalmachine,Parallel Problem Solving from Nature:PPSN IV[A]. 1996, Springer Berlin / Heidelberg. p. 696-705.
[175]Zhang, H.,X. Liu. A Data Streams Clustering Algorithm Using DNA Computing Techniques[C]. in 2009 Joint Conferences on Pervasive Computing (JCPC). 2009. Tamsui, Taipei: p. 623-626.
[176]Zhang, H.,X. Liu, A general object oriented description of DNA computing tehnique, in 2009 International Conference on Information Technology and Computer Science. 2009, IEEE computer society: Kiev, Ukraine. p. 3-6
[177]Zhang, H.,X. Liu. Improved Genetic Algorithm for Designing DNA Sequences[C]. in 2009 Second International Symposium on Electronic Commerce and Security. 2009: p. 514-518.
[178]Zhang, H.,X. Liu, A CLIQUE algorithm using DNA computing techniques based on closed-circle DNA sequences[J]. BioSystems, 2011. 105: p. 73-82.
[179]Zhao, J., et al., A parallel immun algorithm for traveling salesman problem and its application on colde rolling scheduling[J]. Information Sciences, 2011. 181: p. 1212-1223.
[180]Zhou, K., X. tong,X. Jin, Closed circle DNA algorithm of Eight Queens problem[J]. Computer Engineering and Applications, 2007. 43(6): p. 4-6.
[181]Zhou, K., et al., Algorithm of Maximum Independent Set Problem Based on Closed Circle DNA Computing[J]. Computer Engineering 2008. 34(4): p. 40-44.
[182]邓长春, et al.,一种求解TSP问题的多种群并行遗传算法[J].计算机仿真, 2008. 5(9): p. 187-190.
[183]董亚非,王淑栋,许进, DNA计算的粘贴模型及在组合优化中的应用[J].华中科技大学学报(自然科学版), 2003. 31(9): p. 59-61.
[184]范月科,强小利,许进,图的最大团与最大独立集粘贴DNA计算模型[J].计算机学报, 2010. 33(2): p. 305-310.
[185]刘军,王介生,旅行商问题(TSP)的伪并行遗传算法[J].控制理论与应用, 2007. 24(2): p. 279-282.
[186]刘锁兰, et al.,一种新的基于图论聚类的分割算法[J].计算机科学, 2008. 35(9): p. 245-247.
[187]卢昌乐,陈勇,基于Java多线程实现所有顶点间最短路径的并行算法[J].天津工业大学学报, 2006. 25(4): p. 67-69.
[188]强小利,赵东明,张凯,图顶点着色问题的DNA计算模型[J].计算机学报, 2009. 32(12): p. 2332-2337.
[189]唐天兵, et al.,基于DNA计算的混合遗传算法研究[J].计算机应用研究, 2010. 27(1): p. 89-91.
[190]王丽,图论在算法设计中的应用[D],41西安电子科技大学.2010
[191]王淑栋,基于粘贴和删除系统的图着色问题分析[J].计算机学报, 2008. 31(12): p. 2123-2128.
[192]王伟,殷志祥,基于粘贴系统的有向哈密顿路问题分析[J].计算机工程与应用, 2007. 43(26): p. 76-78.
[193]王小乐, et al.,一种最小生成树聚类算法[J].小型微型计算机系统, 2009. 30(5): p. 877-882.
[194]闫成新,桑农,张天序,基于图划分的图像直方图聚类分割[J].计算机应用, 2005. 25(3): p. 570-572.
[195]殷志祥, et al., DNA计算在组合优化中的应用及其复杂性[J].系统工程与电子技术, 2003. 25(4): p. 427-431.
[196]殷志祥,张家秀,图论中的DNA计算模型[J].系统工程与电子技术, 2007. 29(7): p. 1159-1163.
[197]周康,同小军,许进,基于DNA计算的指派问题[J].华中科技大学学报(自然科学版), 2008. 36(2): p. 35-38.
[198]周益民,孙世新,田玲,一种实用的所有点对之间最短路径并行算法[J].计算机应用研究, 2005. 25(12): p. 2921-2922,,234.
[199]秦昆,徐敏,基于云模型和FCM聚类的遥感图像分割方法[J].地球信息科学,2008,10(3):302-307.
[200]Schepeis,A.et.al, Appropriateness of management zones for characterzing spatial variability of soil properties and irrigated corn yields across years[J]. Agronomy Journal, 2004(96): 195-203.
[201]张鸿雁,刘希玉,一种网格聚类的边缘检测方法[J].控制与决策。已录用。
[2] Kaufman, L.,P.J. Rousseeuw, Finding groups in data: an introduction to cluster analysis[M]. 2008, New York, USA: John Wiley &Sons.
[3] T.Ng, R.,J. Han. Efficient and effective clustering method for spatial data mining[C]. in Proceedings of the International Conference on Very Large Data Bases. 1994. Santiago,Chile.
[4] Zhang, T., R. Ramakrishnan,M. Livny. BIRCH: An efficient data clustering method for very large databases[C]. in Proceedings of the 1996 ACM SIGMOD international conference on Management of data. 1996. Montreal, Canada: ACM: p. 103-114.
[5] Guha, S., R. Rastogi,K. Shim. CURE: An efficient clustering algorithm for large databases[C]. in Proceedings of the 1998 ACM SIGMOD international conference on Management of data. 1998. Seattle, WA: ACM: p. 73-84.
[6] Guha, S., R. Rastogi,K. Shim. Rock:A robust clustering algorithm for categorical attributes[C]. in Proceedings of International Conference on Data Engineering. 1999. Sydney, Australia: p. 512-521.
[7] Karypis, G., E.-H. Han,V. Kumar, Chameleon: hierarchical clustering using dynamic modeling[J]. Computer 2002. 32(9): p. 68-75.
[8] Ester, M., et al. A density-based algorithm for discovering clusters in large spatial databases[C]. in Proceedings of the International Conference on Knowledge Discover and Data Mining. 1996. Portland, OR: AAAI: p. 226-231.
[9] Ankerst, M., et al. OPTICS: Ordering points to identify the clustering structure[C]. in Proceedings of the 1999 ACM SIGMOD international conference on Management of data. 1999. Philadelphia,PA: ACM: p. 49-60.
[10] Hinneburg, A.,D. A.Keim. An efficient approach to clustering in large multimedia databases with noise[C]. in Proceedings of the 1998 International Conference Knowledge Discovery and Data Mining. 1998. New York,USA: AAAI: p. 58-65.
[11] Wang, W., J. Yang,R. Muntz. STING:A statistical information grid approach to spatial data mining[C]. in Proceedings of the International Conference on Very Large Data Bases. 1997.Athens,Greece: p. 186-195.
[12] Sheikholeslami, G., S. Chatterjee,A. Zhang. WaveCluster: A multiresolution clustering approach for very large spatial databases[C]. in Proceedings of the 24th VLDB Conference. 1998. New York,USA: p. 428-439.
[13] Agrawal, R., et al. Automatic subspace clustering of high dimensional data for data mining applications[C]. in Proceedings of the 1998 ACM SIGMOD international conference on Management of data 1998: SIGMOD'98: p. 94-105.
[14] Adleman, L.M., Molecular Computation of Solutions to Combinatorial Problems[J]. Science, 1994. 266(5187): p. 1021-1024.
[15] Lipton, R.J., DNA solution of hard computational problems[J]. Science, 1995. 268(5210): p. 542-545.
[16] Ouyang, Q., et al., DNA solution of the maximal clique problem[J]. Science, 1997. 278(5337): p. 446-9.
[17] T.Head, et al., Computing with DNA by operating on plasmids[J]. Biosystems, 2000. 57(2): p. 87-93.
[18] D.Faulhammer, et al. Molecular computation: RNA solutions to chess problems[C]. in Proceedings of the Natl Acas. Sci. 2000. Princeton,USA: p. 1328-1330.
[19]郭晓娟,刘晓霞,李晓玲,层次聚类算法的改进及分析[J].计算机应用与软件, 2005. 25(6): p. 243-244.
[20]龙真真, et al.,一种改进的Chameleon算法[J].计算机工程, 2009. 35(20): p. 189-191.
[21] Goil, S., H. Nagesh,A. Choudhary, MAFIA: Efficient and Scalable Subspace Clustering for Very Large Data Sets. 1999, Center for Parallel and Distributed Computing
[22] Cheng, C., A.W. Fu,Y. Zhang. Entropy-based subspace clustering for mining numberical data[C]. in Proceedings of the 5th ACM SIGKDD international conference on Knowledge discovery and data mining 1999. New York, USA: p. 84-93.
[23] Rickard, J.T., R.R. Yager,W. Miller, Mountain clustering on non-uniform grids using P-tree[J]. Fuzzy optimization and decision making, 2005. 4: p. 87-102.
[24] Hinneburg, A.,D.A. Keim. Optimal Grid-Clustering: Towards Breaking the Curse of Dimensionality in High-Dimensional Clustering[C]. in Proceedings of the 25th International Conference on Very Large Databases. 1999. Edinburgh, Scotland: Morgan Kaufmann: p.506-517.
[25] Aggarwal , C.C., et al. Fast algorithms for projected clustering[C]. in Proceedings of the ACM SIGMOD Conference. 1999. Philadelphia,PA: p. 61-72.
[26] Aggarwal, C.C.,P.S. Yu. Finding generalized projected clusters in high dimensional spaces[C]. in Proceedings of the 2000 ACM SIGMOD international conference on Management of data 2000. Dallas, Texas,USA: ACM.
[27]冯兴杰,黄亚楼,带约束条件的聚类算法研究[J].计算机工程与应用, 2005. 7: p. 12-15.
[28]陈卓,孟庆春,一种基于网络和密度凝聚点的快速聚类算法[J].哈尔滨工业大学学报, 2005. 27(12): p. 1654-1657.
[29] Nagesh, H.S., A. Choudhary,S. Goil, A Scalable Parallel Subspace Clustering Algorithm for Massive Data Sets in 2000 International Conference on Parallel Processing. 2000, IEEE Computer Society: Toronto, Canada. p. 477
[30]冯永, et al.,一种有效的并行高维聚类算法[J].计算机科学, 2005. 32(3): p. 216-218.
[31] T.Zahn, C., Graph-Theoretical Methods for Detecting and Describing Gestalt Clusters[J]. IEEE Transactions on Computers, 1971. C-20(1): p. 68-86.
[32] Wu, Z.,Y.R. Leah, An optimal graph theoretic approach to data clustering theory and its application to image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1993. 15(11): p. 1101-1113.
[33] Gamiol, J.C., S.J. Belongie,S. Majumdar. Normalized cuts for spinal MRI segmentation[C]. in Proceedings of CARS. 2002. France, Paris.
[34] Zhuykov, A.,L. Sarycheva, Cluster analysis of territories by the totality of ecological and socioeconomic indices[J]. Geoscience and Remote Sensing Symposim, 2001. 4: p. 1971-1972.
[35] Reif, J.H., Paradigms for Biomolecular Computation, in First International Conference on Unconventional Models of Computation J.C.a.M.J.D. C.S.Calude, Editor. 1998, Unconverntional Models of Computation, DMTCS Series,Springer-Verlag: Auckland,New Zealand. p. 72-93.J.C.a.M.J.D. C.S.Calude
[36] Guarnieri, F.,C. Bancrof, Use of a horizontal chain reactionfor DNA-based addition, in Discrete Mathematics and Theoretical Computer Science. 1999, DIMACS. p. 105-116
[37] Guainieri, F., M. Fliss,C. Bancroft, Making DNA Add[J]. Science, 1996. 273(5272): p. 220-223.
[38] Orlian, M., F. Guarnieri,C. Bancroft, Parallel primer extension horizontal chain reactions as a paradigm of parallel DNA-based computation, in DIMACS:Series in Discrete Matematics and Theoretical Computer Science. 1998, DMIACS Workshop on DNA Based Computers. p. 142-158
[39] H.Leete, T., et al., Bit Operations Using a DNA Template, in Proceedings of the Third DIMACS Workshop on DNA-based Computers. 1997, University of Rochester. Computer Science Department: Philadephia, USA. p. 159-366
[40] Gupta, V., S. Parthasarathy,M.J. Zaki, Arithmetic and logic operations with DNA in 3rd DIMACS Workshop on DNA-based Computers. 1997, University of Rochester. Computer Science Department: Philadelphia,USA. p. 212-232
[41] Qiu, Z.F.,M. Lu. Arithmetic and logic operations with DNA computers[C]. in Proceedings of the Second IASTED International Conference on Parallel and Distributed Computing and Networks. 1998. Australia: p. 481-486.
[42] Wasiewicz, P.,J. J.Mulawka, Adding numbers with DNA, in 2000 IEEE International Conference on Systems, Man,and Cybernetics. 2000, IEEE Press: Nashville,TN. p. 265-270
[43] Barua, R., et al., Binary Arithmetic for DNA Computers,DNA Computing[A]. 2003, Springer Berlin / Heidelberg. p. 124-132.
[44] H.LaBean, T., E. Winfree,J. H.Reif, Experimental progress in computation by self-assembly of DNA tilings, in In 5th DIMACS Workshop on DNA Based Computers. 2000: Rhode Island. p. 123-140
[45] Hug, H., R. Schuler,A.T. Informatik. DNA-based parallel computation of simple arithmetic[C]. in Proceedings of the 7th International Meeting on DNA Based Computers. 2001. Berlin: Springer: p. 159-166.
[46] Bakar, R.B.A.,J. Watada, Biological Clustering Method for Logistic Place Decision Making[J]. Knowledge-Based Intelligent Information and Engineering Systems, 2008(5179): p. 136-143.
[47] Rooss, D.,K.W. Wagner, On the Power of DNA Computing[J]. Information and Computation, 1996. 131: p. 95-109.
[48] Csuhaj-Varjú, E., et al. DNA computing based on splicing: universality results[C]. in Proceedings of the First Annual Pacific symposium on Biocomputing 1996. Hawaii: WorldScience Publication: p. 179-190.
[49] Kari, L., et al., DNA computing, sticker systems, and universality[J]. Acta Informatica, 1998. 35(5): p. 401-420.
[50] P?un, G., On the splicing operation[J]. Discrete Applied Mathematics, 1996. 70(1): p. 57-59.
[51] P?un, G., DNA computing based on splicing: university results[J]. Theoretical Computer Science, 2000. 231(2): p. 275-296.
[52] Ferretti, C.,S. Kabayashi, DNA splicing systems and post systems[J]. Pacific Symposium on Biocomputing, 1996: p. 288-299.
[53] P?un, G., G. Rozenberg,A. Salomaa, Computing by splicing[J]. Theoretical Computer Science, 1996. 168(2): p. 321-336.
[54] Arita, M., M. Hagiya,A. Suyama. Joining and Rotating Data with Molecules[C]. in Processings of 1997 IEEE International Conference on Evolutionary Computation. 1997. Indinapolis,USA: p. 243-248.
[55] P?un, G.,G. Rozenberg, Sticker systems[J]. Theoretical Computer Science, 1998. 204(1-2): p. 183-203.
[56] Ceterchi, R., Cut and paste languages[J]. Grammars, 1999. 2(3): p. 179-188.
[57] Daley, M., et al. Circular contextual insertions/deletions with applications to biomolecular computataions[C]. in String Processing and Information Retrieval Symposium, 1999 and International Workshop on Groupware. 1999. Cancun, Maxico: p. 47-54.
[58] Kari, L. DNA computing based on insertions and deletions[C]. in Proceedings of the conference conceptual tools for understanding dynamics in biological systems. 1996. London: p. 89-95.
[59] Kari, L. From micro-soft to bio-soft: computing with DNA[C]. in Proceedings of bio-comuting and emergent computers. 1997. Sweden: World Scientific Publishing: p. 146-164.
[60] Beaver, D., Computing with DNA[J]. Journal of Computational Biology, 1995. 2(1): p. 1-7.
[61] D.Smith, W., DNA computers in vitro and vivo[A], in DNA based Computers, R. J.Lipton and E. B.Baum, Editors. 1996, American Mathamtical Society: Princeton. p. 121-147.
[62] Winfree, E., On the computation power of DNA annealing and ligation, in Discrete mathmatics and Theoretical Computer Science. 1995, American Methematical Society. p.199-221
[63] Winfree, E., et al., Design and self-assembly of two-dimensional DNA crystals [J]. Nature, 1998. 394: p. 539-544.
[64] Winfree, E., X. Yang,N. C.Seeman, Universal computation via self-assembly of DNA: Some theory and experiments, in Series in Discrete mathematics and Theoretical Computer Science. 1996, DIMACS Workshop. p. 191-223
[65]Baum, E.B., Building an associative memory vastly larger than the brain[J]. Science, 1995. 268: p. 583-585.
[66] Bach, E., et al. DNA models and algorithm for NP-complete problems[C]. in Proceedings of the 11th Annual IEEE Conferences on Computational Complexity(CCC'96). 1996. Philadelphia, PA: p. 290.
[67] Landweber, L.F.,L. Kari, The evolution of cellular computing: nature's solution to a computational problem[J]. Biosystems, 1999. 52(1): p. 3-13.
[68] Sakamoto, K., et al., Molecular Computation by DNA Hairpin Formation[J]. Science, 2000. 288: p. 1223-1227.
[69] Liu, Q., et al., DNA computing on surfaces[J]. Nature, 2000. 403: p. 175-179.
[70] Roweis, S., et al., A sticker-based model for DNA computation[J]. J Comput Biol, 1998. 5(4): p. 615-29.
[71] Jonoskaa, N., S.A. Karlb,M. Saito, Three dimensional DNA structures in computing[J]. Biosystems, 1999. 52(1-3): p. 143-53.
[72]许进,张雷, DNA计算机原理、进展及难点(I):生物计算系统及其在图论中的应用[J].计算机学报, 2003. 26(1): p. 1-11.
[73]许进,黄布毅, DNA计算机:原理、进展及难点(II)计算机“数据库”的形成——DNA分子的合成问题[J].计算机学报, 2005. 28(10): p. 1583-1591.
[74]许进, et al., DNA计算机原理、进展及难点(III):分子生物计算中的数据结构与特性[J].计算机学报, 2007. 30(6): p. 869-880.
[75]许进, et al., DNA计算机原理、进展及难点(IV):论DNA计算机模型[J].计算机学报, 2007. 30(6): p. 881-893.
[76] Ren, L., Y. Ding,S. Shao, DNA bio-soft computing and its application to intelligent control systems[J]. Shanghai Jiaotong University(English version), 1999. E-2(2): p. 97-103.
[77]丁永生,任立红,邵世煌, DNA计算与软计算[J].系统仿真学报(增刊), 2011. 13: p. 198-201,213.
[78]丁永生,邵世煌,任立红, DNA计算与软计算[M]. 2002,北京:科学出版社.
[79]陈仲民,基于DNA计算模型的数据加密与解密[J].计算机与数字工程, 2007. 35(12): p. 86-92.
[80]姚小枝,黄杨,以DNA为载体的信息隐藏方法研究[J].计算机应用于软件, 2008. 25(3): p. 235-248.
[81]张勋才, et al.,基于自组装DNA计算的RSA密码系统破译方案[J].系统工程与电子技术, 2010. 32(5): p. 1094-1099.
[82] Gao, L.,J. Xu, DNA solution of vertex cover problem based on sticker model[J]. Chinese Journal of Computers, 2002. 11(2): p. 280-284.
[83]刘文斌, et al.,最大匹配问题的DNA表面计算模型[J].电子学报, 2003. 31(10): p. 1496-1499.
[84]李源,方辰,欧阳颀,最大集团问题的DNA计算机进化算法[J].科学通报, 2004. 49(5): p. 439-443.
[85]王淑栋,许进,董亚非,图的最小顶点覆盖问题的面上DNA解法[J].小型微型计算机系统, 2004. 25(2): p. 242-244.
[86]周康,同小军,刘文斌,排课表问题的闭环DNA计算模型的算法[J].计算机应用于, 2007. 27(4): p. 991-993.
[87]周康,同小军,许进,基于闭环DNA模型的八皇后问题算法[J].计算机工程与应用, 2007. 43(6): p. 4-6,13.
[88]周康, et al.,最短路问题的闭环DNA算法[J].系统工程与电子技术, 2008. 30(3): p. 556-560.
[89]周康, et al.,集合覆盖问题闭环DNA算法[J].华中科技大学学报(自然科学版), 2010. 38(2): p. 21-25.
[90]周康,同小军,许进,基于闭环DNA的指派问题算法[J].计算机科学, 2007. 34(12): p. 211-213.
[91]周康, et al.,基于闭环DNA计算的最大独立集问题的算法[J].计算机工程, 2008. 34(4): p. 40-44.
[92]刘毅,宋玉阶,收缩背包问题的DNA算法[J].计算机工程与科学, 2007. 29(8): p. 55-57.
[93] Bakar, R.B.A.,J. Watada. A DNA Computing Approach to Cluster-Based Logistic Design[C]. in Proceedings of the 2nd International Conference on Innovative Computing, Information and Control (2007). 2007. Kumamoto: p. 383-383.
[94] Bakar, R.B.A.,J. Watada, A Biologically Inspired Computing Approach to Solve Cluster-Based Determination of Logistic Problem [J]. Biomedical Soft Computing and Human Sciences, 2008. 13(2): p. 59-66.
[95] Bakar, R.B.A., J. Watada,W. Pedrycz, DNA approach to solve clustering problem based on a mutual order[J]. BioSystems, 2008(91): p. 1-12.
[96] Bakar, R.B.A., J. Watada,W. Pedrycz. A DNA computing approach to data clustering based on mutual distance order[C]. in 9th Czech-Japan Seminar (2006). 2006: p. 139-145.
[97] Kim, I.,J. Watada, Decision making with an interpretive structural modeling method using a DNA-based algorithm[J]. IEEE Trans Nanobioscience, 2009. 8(2): p. 181-91.
[98] Kim, I.,J. Watada. A DNA-Based Clustering Method Based on Statistics Adapted to Heterogeneous Coordinate Data[C]. in International Conference on Complex, Intelligence and Software Intensive Systems(2009). 2009: p. 892-897.
[99] Kim, I., J. Watada,J.-Y. Wu, A DNA Encoding Method to Determine and Sequence All Cliques in a Weighted Graph, in 2009 Fourth International Conference on Innovative Computing, Infomation and Control. 2009. p. 1532-1537
[100]王延峰,DNA计算中的编码理论与方法研究[D],116华中科技大学.2007: p. 116.
[101]Ogihara, M.,A. Ray, The minimum DNA computation model and its computational power, in Technical Report. 1997, Department of Computer Science: New York,USA
[102]Ignatova, Z., I. Martinez-Perez,k.-H. Zimmermann, DNA computing Models[M]. 2008: Springer.
[103] Deaton, R., et al. Good Encodings for DNA-based Solutions to Combinatiorial Problems[C]. in 2nd Annual Meeting on DNA Based Computers(1996). 1996. Princeton University: p. 159-171.
[104] Deaton, R., et al. Genetic Search of Reliable Encodings for DNA-based Computation[C]. in Proceedings of the First Annual Conference on Genetic Programming (1996). 1996. Memphis.
[105]Baum, E.B., DNA sequences useful for computation[M]. Princeton University. 1999.
[106]Frutos, A.G., et al., Demonstration of a word design strategy for DNA computing on surfaces[J]. Nucleic Acids Research, 1997. 25: p. 4748-4757.
[107]Garzon, M.,R. Deaton, Codeword design and information encoding in DNA ensembles[J]. Natural Computing, 2004. 3: p. 253-292.
[108]Feldkamp, U., H. Rauhe,W. Banzhaf, Software Tools for DNA Sequence Design[J]. Computer Science, 2003. 4(153-171).
[109]Zhang, K., et al., Improved taboo search algorithm for designing DNA sequences, in Progress in Natural Science. 2008. p. 623-627
[110]崔光照,张勋才,王延峰, DNA计算中编码序列的优化设计方案[J].计算机应用研究, 2007. 24(7): p. 195-201.
[111]张凯, et al.,基于汉明距离的DNA编码约束研究[J].计算机工程与应用, 2008. 44(14): p. 42,52,62.
[112]朱翔鸥,刘文斌,孙川, DNA计算编码研究及其算法[J].电子学报, 2006. 34(7): p. 1169-1174.
[113]Adleman, L.M., Computing with DNA[J]. Science American, 1998.
[114]Aili, H.,Z. Daming, DNA Computing Model for the Minimum Spanning Tree Problem[J]. Eighth International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC'06), 2006: p. 372-377.
[115]Andritsos, P., Data Clustering Techniques. 2002, University of Toronto: Toronto
[116]Arita, M., et al. Improving Sequence Design for DNA Computing[C]. in Proceedings of Genetic and Evolutionary Computation Conference 2000. 2000: Morgan Kaufmann: p. 875-882.
[117]Barreto, S., et al., Using clustering analysis in a capacitated location-routing problem[J]. European Journal of Operational Research, 2006. 179(3): p. 968-977.
[118]Batista, R.B., A. Boukerche,A.C.M.A.d. Melo, A parallel strategy for biological sequence aligment in restricted memory space[J]. Journal of Parallel and Distributed Computing, 2008. 68: p. 548-561.
[119]Benenson, Y., et al., An autonomous molecular computer for logical control of gene expression[J]. Nature, 2004. 429(6990): p. 423-9.
[120]Benenson, Y., et al., Programmable and autonomous computing machine made of biomolecules[J]. Nature, 2001. 414(6862): p. 430-4.
[121]Blain, D., et al., Development, evaluation and benchmarking of simulation software for biomolecule-based computing[J]. Natural Computing, 2004. 3: p. 427-442.
[122]Braich, R.S., et al., Solution of a 20-Variable 3-SAT Problem on A DNA Computer[J]. Science, 2002. 296: p. 499-502.
[123]Brandes, U., M. Gaertler,D. Wagner, Experiment on graph clustering algorithm, in In 11th Europ. Symp. Algorithms. 2001, Springer-Verlag. p. 568-579
[124]Chang, W.-L., M. Ho,M. Guo, Constructing Bio-molecular Databases on a DNA-based Computer[J]. CoRR, 2007. abs/0712.1863.
[125]Chen, J., et al., DNA computing implementing genetic algorithms, in DIMACS Workshop on Evolution as Computation. 1999, Princeon University. p. 39-51
[126]Deaton, R., et al., A DNA based implementation of an evolutionary search for good encodings for DNA computation, in IEEE International Conference on Evolutionary Computation 1997. 1997: Indianapolis, IN, USA. p. 267-271
[127]Ezziane, Z., DNA computing: applications and challenges[J]. Nanotechnology, 2005. 17: p. 27-39.
[128]Flake, G.W., R.E. Tarjan,K. Tsioutsiouliklis, Graph Clustering and Minimum Cut Trees[J]. Internet Mathematics, 2004. 1(4): p. 385-408.
[129]Freund, R.,F. Freund, Test tube systems with controlled applications of rules, in 1997 IEEE International Conference on Evolutionary Computation, . 1997: Indianapolis, IN,USA. p. 237-242
[130]Grady, L., Space Variant Computer Vision: A Graph Theoretic Approach[M]. 2004: Boston University.
[131]Guangwu, L., et al., Algorithm of graph isomorphism with three dimensional DNA graph strucutres[J]. Progress in Natural Science, 2005. 15(2): p. 181-184.
[132]H.Garzon, M., N.Jonoska,S. A.Karl, The bounded complexity of DNA computing[J]. Biosystems, 1999. 52(1-3): p. 63-72.
[133]Head, T., Splicing schiemes and DNA [J]. Nanotechnology, 1992. 1: p. 335-342.
[134]Hsieh, S.-Y.,M.-Y. Chen, A DNA-based solution to the graph isomorphism problem using Adleman-Lipton model with stickers[J]. Applied Mathematics and Computation, 2008. 197: p. 672-686.
[135]Hsieh, S.-Y., C.-W. Huang,H.-H. Chou, A DNA-based graph encoding scheme with its applications to graph isomorphism problems[J]. Applied Mathematics and Computation, 2008. 203: p. 502-512.
[136]Ibrahim, Z., Towards Solving Weighted Graph Problems by Direct-Proportional Length-Based DNA 2004, IEEE Computational Intelligence Society (CIS)
[137]Ibrahim, Z., et al., A New Readout Approach in DNA Computing Based on Real-Time PCR with TaqMan Probes,DNA Computing[A]. 2006, Springer Berlin / Heidelberg. p. 350-359.
[138]Ibrahim, Z., Y. Tsuboi,O. Ono, Direct-Proportional Length-Based DNA Computing for Shortest Path Problem [J]. International Journal of Computer Science and Applications, 2004. 1(1): p. 46-60.
[139]Jain, A.K., M.N. Murty,P.J. Flynn, Data Clustering : Areview[J]. ACM Computing Surveys, 1999. 31(3): p. 265-323.
[140]Jiejun, W.,X. Chuanpei, Test generation for combinational circuits based on DNA computing in 9th International Conference on Electronic Measurement & Instruments, 2009. ICEMI '09. 2009, IEEE Beijing, China. p. 4-650 - 4-653
[141]Jin, X.,Z. Lei, DNA Computer Principle, Advances and Difficulties (I): Biological Computing System and Its Applications to Graph Theory[J]. Chinese Journal of Computers, 2003. 26(1): p. 1-11.
[142]Jain, A.K., M.N. Murty,P.J. Flynn, Data Clustering : Areview[J]. ACM Computing Surveys, 1999. 31(3): p. 265-323.
[143]Kari, L.,G. Thierrin, Contextual insertions/deletions and computability[J]. Information and Computation, 1996. 131(1): p. 47-61.
[144]Kim, S.Y., J.W. Lee,J.S. Bae, Effect of data normalization on fuzzy clustering of DNA microarray data[J]. BMC Bioinformatics, 2006. 7: p. 134.
[145]Lee, J.Y., et al. Efficient initial pool generation for weighted graph problems using parallel overlap assembly[C]. in Preliminary Proceedings of the Tenth International Meeting on DNA Based Computers. 2004: Springer-Verlag: p. 357-364.
[146]Lingqiang, P., et al., Solid phase based DNA solution of the coloring problem[J]. Progress in Natural Science, 2004. 14(5): p. 459-462.
[147]Liu, X.,H. Liu, Spatial Cluster Analysis Based on Evolutionary DNA ComputingTechnique, in 3rd International Conference on Bioinformatics and Biomedical Engineering , 2009. . 2009. p. 1-4
[148]Liu, X.,H. Zhang, Spiking DNA neural trees with applications to conceptual design, in 2011 15th International Conference on Computer Supported Cooperative Work in Design. 2011. p. 276-280
[149]Lu, X., et al. Gene cluster algorithm based on most similarity tree[C]. in Proceedings of the Eighth International Conference on High-Performance Computing in Asia-Pacific Region (HPCASIA'05). 2005: p. 656.
[150]Makrogiannis, S., G. Economou,S. Fotopoulos, Segmentation of color images using multiscale clustering and graph theoretic region synthesis[J]. IEEE Transactions on Systems,Man and Sybernetics, 2005. 35(2): p. 224-234.
[151]Malic, J., S. Belongise,T. Leung, Contour and texture analysis for image segmentation[J]. International Journal of Computer Vision, 2000. 5(1): p. 7-27.
[152]Marathe, A., A.E. Condon,R.M. Corn, On Combinational DNA word design[J]. Discrete Mathematics and Theoretical computer Science, 2000. 54: p. 75-89.
[153]Razzazi, M.,M. Roayaei, Using sticker model of DNA computing to solve domatic partition,kernel and induced path problems[J]. Information and Computation, 2011. 181: p. 3581-3600.
[154]Rooss, D., Recent Developments in DNA-Computing, in 27th International Symposium on Multiple-Valued Logic (ISMVL '97). 1997, IEEE Computer Society: Antigonish. p. 3-9
[155]Roweis, S.,E. Winfree, On the reduction of errors in DNA computation[J]. J Comput Biol, 1999. 6(1): p. 65-75.
[156]Royer, L., et al., Unraveling Protein Networks with Power Graph Analysis[J]. PLoS Computation Biology, 2008. 4(7): p. e1000108.
[157]Rozen, D.E., S. McGrew,A. D.Ellington, Molecular computing: Does DNA compute?[J]. Current Biology, 1996. 16: p. 254-257.
[158]Schaeffer, S.E., Graph Clustering[J]. Computer Science Review, 2007. 1: p. 27-64.
[159]Sekhar, G.P.R., DNA Computing-Graph Algorithms[J].
[160]Sezgin, M.,B. Sankur, Survey over image thresholding techniques and quantiative performance evaluation[J]. Journal of Electronic Iamge, 2004. 13(1): p. 146-165.
[161]Shi, J.,J. Malik. Nomalized Cuts and Image Segmentation[C]. in Proceedins of IEEE Conference on Computer Vision and Pettern Recognition. 1997: p. 731-737.
[162]Shi, L., S. Olafsson,N. Sun, New parallel randomized algorithms for the traveling salesman problem[J]. Computer and Operation Research 1999. 26: p. 371-394.
[163]Shi, N.-Y.,C.-P. Chu, A molecular solution to the hitting-set problem in DNA-based supercomputing[J]. Information Sciences, 2010. 180: p. 1010-1019.
[164]Shiu, H.J., et al., Data hiding methods based upon DNA sequences[J]. Information Sciences, 2010. 180: p. 2196-2208.
[165]Su, X.,L. M.Smith, Demonstration of an universal surface DNA computer[J]. Nucleic Acids Research, 2004. 32(10): p. 3115-3123.
[166]Vlachos, T.,A.G. Constantinides, Graph theoretical approach to color picture segmentation and contour classification[J]. Communications,Speech and Vision, 1993. 140(1): p. 36-45.
[167]Wang, B., et al., Design of DNA Sequence Based on Improved Genetic Algorithm Advanced Intelligent Computing Theories and Applications. With Aspects of Theoretical and Methodological Issues[A]. 2008, Springer Berlin / Heidelberg. p. 9-14.
[168]Wang, S.,J. Siskund, Image segmentation with ratio cut[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003. 25(6): p. 675-690.
[169]Wang, X., et al., Solving the SAT problem using a DNA computing algorithm based on ligase chain reaction[J]. BioSystems, 2008. 91: p. 117-125.
[170]Watada, J., et al. DNA Computing Approach to Optimal Decision Problems[C]. in Proceedings of 2004 IEEE International Conference on Fuzzy Systems. 2004: p. 1579-1584.
[171]Xue, J.,X. Liu, Applying DNA computation to clustering in graph, in 2nd International Conference on Artificial Intelligence, Management Science and Eelctronic Commerce. 2011. p. 986-989
[172]Yamamoto, M., et al., DNA Solution of the Shortest Path Problem by Concentration Control[J]. Genome Informatics, 2000. 11: p. 466-467.
[173]Yin, Z.,J. Zhang, DNA computing in the graph theory[J]. Systems Engineering and Electronics, 2007. 29(7): p. 1159-1163.
[174]Zauner, K.-P., et al., Parallel computing with DNA: Toward the anti-universalmachine,Parallel Problem Solving from Nature:PPSN IV[A]. 1996, Springer Berlin / Heidelberg. p. 696-705.
[175]Zhang, H.,X. Liu. A Data Streams Clustering Algorithm Using DNA Computing Techniques[C]. in 2009 Joint Conferences on Pervasive Computing (JCPC). 2009. Tamsui, Taipei: p. 623-626.
[176]Zhang, H.,X. Liu, A general object oriented description of DNA computing tehnique, in 2009 International Conference on Information Technology and Computer Science. 2009, IEEE computer society: Kiev, Ukraine. p. 3-6
[177]Zhang, H.,X. Liu. Improved Genetic Algorithm for Designing DNA Sequences[C]. in 2009 Second International Symposium on Electronic Commerce and Security. 2009: p. 514-518.
[178]Zhang, H.,X. Liu, A CLIQUE algorithm using DNA computing techniques based on closed-circle DNA sequences[J]. BioSystems, 2011. 105: p. 73-82.
[179]Zhao, J., et al., A parallel immun algorithm for traveling salesman problem and its application on colde rolling scheduling[J]. Information Sciences, 2011. 181: p. 1212-1223.
[180]Zhou, K., X. tong,X. Jin, Closed circle DNA algorithm of Eight Queens problem[J]. Computer Engineering and Applications, 2007. 43(6): p. 4-6.
[181]Zhou, K., et al., Algorithm of Maximum Independent Set Problem Based on Closed Circle DNA Computing[J]. Computer Engineering 2008. 34(4): p. 40-44.
[182]邓长春, et al.,一种求解TSP问题的多种群并行遗传算法[J].计算机仿真, 2008. 5(9): p. 187-190.
[183]董亚非,王淑栋,许进, DNA计算的粘贴模型及在组合优化中的应用[J].华中科技大学学报(自然科学版), 2003. 31(9): p. 59-61.
[184]范月科,强小利,许进,图的最大团与最大独立集粘贴DNA计算模型[J].计算机学报, 2010. 33(2): p. 305-310.
[185]刘军,王介生,旅行商问题(TSP)的伪并行遗传算法[J].控制理论与应用, 2007. 24(2): p. 279-282.
[186]刘锁兰, et al.,一种新的基于图论聚类的分割算法[J].计算机科学, 2008. 35(9): p. 245-247.
[187]卢昌乐,陈勇,基于Java多线程实现所有顶点间最短路径的并行算法[J].天津工业大学学报, 2006. 25(4): p. 67-69.
[188]强小利,赵东明,张凯,图顶点着色问题的DNA计算模型[J].计算机学报, 2009. 32(12): p. 2332-2337.
[189]唐天兵, et al.,基于DNA计算的混合遗传算法研究[J].计算机应用研究, 2010. 27(1): p. 89-91.
[190]王丽,图论在算法设计中的应用[D],41西安电子科技大学.2010
[191]王淑栋,基于粘贴和删除系统的图着色问题分析[J].计算机学报, 2008. 31(12): p. 2123-2128.
[192]王伟,殷志祥,基于粘贴系统的有向哈密顿路问题分析[J].计算机工程与应用, 2007. 43(26): p. 76-78.
[193]王小乐, et al.,一种最小生成树聚类算法[J].小型微型计算机系统, 2009. 30(5): p. 877-882.
[194]闫成新,桑农,张天序,基于图划分的图像直方图聚类分割[J].计算机应用, 2005. 25(3): p. 570-572.
[195]殷志祥, et al., DNA计算在组合优化中的应用及其复杂性[J].系统工程与电子技术, 2003. 25(4): p. 427-431.
[196]殷志祥,张家秀,图论中的DNA计算模型[J].系统工程与电子技术, 2007. 29(7): p. 1159-1163.
[197]周康,同小军,许进,基于DNA计算的指派问题[J].华中科技大学学报(自然科学版), 2008. 36(2): p. 35-38.
[198]周益民,孙世新,田玲,一种实用的所有点对之间最短路径并行算法[J].计算机应用研究, 2005. 25(12): p. 2921-2922,,234.
[199]秦昆,徐敏,基于云模型和FCM聚类的遥感图像分割方法[J].地球信息科学,2008,10(3):302-307.
[200]Schepeis,A.et.al, Appropriateness of management zones for characterzing spatial variability of soil properties and irrigated corn yields across years[J]. Agronomy Journal, 2004(96): 195-203.
[201]张鸿雁,刘希玉,一种网格聚类的边缘检测方法[J].控制与决策。已录用。