# Spatial Cluster Analysis by the Adleman-Lipton DNA Computing Model and Flexible Grids

Authors: Xiyu Liu; Laisheng Xiang; Xin Wang
Journal: Discrete Dynamics in Nature and Society
 (2012)

---

## Abstract

Spatial cluster analysis is an important data-mining task. Typical techniques include CLARANS, density- and gravity-based clustering, and other algorithms based on traditional von Neumann’s computing architecture. The purpose of this paper is to propose a technique for spatial cluster analysis based on DNA computing and a grid technique. We will adopt the Adleman-Lipton model and then design a flexible grid algorithm. Examples are given to show the effect of the algorithm. The new clustering technique provides an alternative for traditional cluster analysis.


---

## Body

## 1. Introduction

Deoxyribonucleic acid computing, or DNA computing in short, has attracted strong interests and wide focus recently. It is inspired by the similarity between the way DNA stores and manipulates information with traditional Turing machine. Although DNA computing is in a sense similar to evolutionary computing, but the significant difference between them lies in the computing medium, biomolecules rather than transistor chips. It is this difference that makes DNA computing a promising field with ultimate goal of making DNA computers [1].The essential work to reveal the ability of DNA in computing is by Adleman’s experiment (Adleman [2]), which demonstrated that the tools of laboratory molecular biology could be used to solve computation problems. Adleman also proves the huge information storage capacity of DNA which is contained in the sequence of nucleotide bases that hydrogen bonds in a complementary fashion to form double-stranded molecules from single-stranded oligonucleotides. Adleman’s work was later generalized by Lipton [3] to the satisfiability problem. Based on Adleman and Lipton’s research, a number of applications of DNA computing in solving combinatorially complex problems such as factorization, graph theory, control, and nanostructures have emerged [1]. There appeared also theoretical studies including DNA computers which are programmable, autonomous computing machines with hardware in biological molecules mode, see [4–7] for references.Adleman and Lipton’s original works include a basic computing model, often referred to as the Adleman-Lipton model. Later generalizations include the sticker model, the splicing model, and the insertion deletion model [1]. However, most applications in this area are restricted to problems of combinatory types due to searching nature of DNA computing. It is a challenge how to design applications of optimization types.Spatial cluster analysis is a traditional problem in knowledge discovery from databases [8]. It has wide applications since increasingly large amounts of data obtained from satellite images, X-ray crystallography, or other automatic equipment are stored in spatial databases. The most classical spatial clustering technique is due to Ng and Han [9] who developed a variant PAM algorithm called CLARANS, while new techniques are proposed continuously in the literature aiming to reduce the time complexity, or to fit for more complicated cluster shapes.For example, Bouguila [10] proposed some model-based methods for unsupervised discrete feature selection. Wang et al. [11] developed techniques to detect clusters with irregular boundaries by a minimum spanning tree-based clustering algorithms. By using an efficient implementation of the cut and the cycle property of the minimum spanning trees, they obtain a performance better than O(N2). In another paper, Wang and Huang [12] developed a new density-based clustering framework by a level set approach. By a valley seeking method data points are grouped into corresponding clusters.Although DNA computing and cluster analysis receive much attention and rapid development, there have appeared rare combination of these two important research areas. Up to the authors knowledge, the combination of DNA computing and cluster analysis is found in a few researches such as Bakar et al. [7].Inspired by the research of Bakar et al. [7], this paper focuses on the joint study of DNA computing with cluster analysis. We propose a new grid-based clustering technique which can be solved by DNA computing. Different with other researches, this can reduce the searching space significantly. Finally we present two examples to show the details of our technique.


## 2. DNA Computing and Operations

### 2.1. DNA Structures

Macromolecules of nucleic acids are composed of nucleotide building blocks. In DNA, the nucleotides are the purines adenine (A), guanine (G), the pyrimidines thymine (T), and cytosine (C). Single-stranded DNA molecules, or oligonucleotides, are formed by connecting the nucleotides together with phosphodiester bonds. The single strands of DNA can form a double-stranded molecule when the nucleotides hydrogen bonds to their Watson-Crick complements,A̅=T and G̅=C (Figure 1).Figure 1
A double-stranded DNA structure diagram.DNA stores information in nucleic acid and manipulates information via enzymes and interactions. A strand of DNA is encoded with four bases represented by the letters A, T, C, and G. Each strand has a3′- and a 5′-end, and hence any single strand has a natural orientation. The cutting of certain strands of a DNA molecule is performed by the restriction enzymes. These enzymes catalyse the cutting operations at very specific DNA base sequences which are called recognition sites. Figure 2(a) shows a DNA molecule in which its four nucleotides in the left end and five in the right end are not paired with nucleotides from the opposite strand caused by cutting, or some other operations. In this case, the molecule is called to have sticky ends.DNA molecules with sticky ends.
(a)(b)(c)Here is an example which illustrates the process by the enzyme EcoRI as shown in Figure2(b) where N represents some other arbitrary deoxyribonucleotide. EcoRI acts only at the six-term sequences which are exactly like the form(2.1)GAATTCCTTAAG.The effect is to cut the molecule into two pieces as shown in Figure2(c).There are over 100 different restriction enzymes, each of which cuts at its specific recognition site. A restriction enzyme cuts DNA into pieces with sticky ends. On the other hand, sticky ends will match and attach to other sticky ends of any other DNA that has been cut with the same enzyme. DNA ligase joins the matching sticky ends of the DNA pieces from different sources that have been cut by the same restriction enzyme.


### 2.2. DNA-Computing Models

There are several types of DNA-computing models among which the Adleman-Lipton model is the most traditional one. This model focuses on the hybridization between different DNA molecules as a basic step of computations. According to Adleman and Lipton’s original works [2, 3], this traditional DNA-computing strategy is based on enumerating all candidate solutions, and then using some selection process to choose the correct DNA. This technique requires that the size of the initial data pool increases exponentially with the number of variables in the calculation.Apart from the Adleman-Lipton model, other DNA computing models appeared such as the sticker model, the splicing model. The Sticker model is based on a coding scheme called DNA complex. A DNA complex is a partially double DNA strand. Usually a double piece represents a bit with value one while a single-strand represents zero. Hence each complex is constructed by two single stranded DNA molecules referred to as memory strands and sticker strands. A memory strand containsn nonoverlapping substrands each of which is m bases long. Each sticker strand is m bases long and is complementary to exactly one of the n substrands in a memory strand.The second model is the splicing model proposed by Tom [6] based on formal language theory. A splicing system S=(A,L,B,C) consists of a finite alphabet A, a finite set I of initial strings in A* (language over A), and finite sets B and C of triples (c,x,d) with c,d,x∈A*. Each such triple in B or C is called a pattern. For each such triple the string cxd is called a site, and the string x is called a crossing. Patterns in B are called left patterns, and patterns in C are called right patterns. The language L=L(S) generated by S consists of the strings in I and all strings that can be obtained by adjoining to Lucxfq and pexdv whenever ucsdv and pexfq are in L and (c,x,d) and (e,x,f) are patterns of the same hand. A language L is a splicing language if there exists a splicing system S for which L=L(S).The next model is thek-armed model which is based on some more complicated molecule structures which have three-dimensional DNA architecture. In [13] the authors pointed out that it is natural to use the armed model to represent SAT problem in terms of contact network framework, and they gave theoretical solutions to this NP-complete problems. Like the splicing model, biological operations in the k-armed model include cleaving and connecting.


### 2.3. Operations of the Adleman-Lipton Model

The basic principle of DNA computing is to use the encoded information in the sequence of nucleotides and evolve them by breaking and making new bonds between them to reach the answer. The basic operations performed by enzymes are denaturing, replicating, merging, detecting, and so forth.According to the DNA computing models proposed by Adleman [2] and Lipton [3], there are several basic DNA operations. One important operation is hybridization which is a main process in DNA computing to form all possibilities of solution strands in which the right answer lies. Hybridization is done by mixing strands in tubes with the help of some enzymes.Apart form hybridization, the basic DNA operations available on DNA are mainly the following.(i)
Merge.m(N1,N2)≜N1∪N2=N.(ii)
Amplify.Duplicate(N1)=N.(iii)
Detect(N).(iv)
Separate or extract.N←+(N,w),N←-(N,w). Given a word w consisting of strings from Σ={A,G,C,T} and a tube N, generate two tubes +(N,w) and -(N,w) which contain and does not contains the string w.(v)
Length separate.N←(N,≤n). Given a tube N and an integer n, generate a tube containing stands with length less or equal to n.(vi)
Position separate.N←B(N1,w), N←E(N1,w). Given a tube and word generate a tube with stands beginning (ending) with the word.


## 2.1. DNA Structures

Macromolecules of nucleic acids are composed of nucleotide building blocks. In DNA, the nucleotides are the purines adenine (A), guanine (G), the pyrimidines thymine (T), and cytosine (C). Single-stranded DNA molecules, or oligonucleotides, are formed by connecting the nucleotides together with phosphodiester bonds. The single strands of DNA can form a double-stranded molecule when the nucleotides hydrogen bonds to their Watson-Crick complements,A̅=T and G̅=C (Figure 1).Figure 1
A double-stranded DNA structure diagram.DNA stores information in nucleic acid and manipulates information via enzymes and interactions. A strand of DNA is encoded with four bases represented by the letters A, T, C, and G. Each strand has a3′- and a 5′-end, and hence any single strand has a natural orientation. The cutting of certain strands of a DNA molecule is performed by the restriction enzymes. These enzymes catalyse the cutting operations at very specific DNA base sequences which are called recognition sites. Figure 2(a) shows a DNA molecule in which its four nucleotides in the left end and five in the right end are not paired with nucleotides from the opposite strand caused by cutting, or some other operations. In this case, the molecule is called to have sticky ends.DNA molecules with sticky ends.
(a)(b)(c)Here is an example which illustrates the process by the enzyme EcoRI as shown in Figure2(b) where N represents some other arbitrary deoxyribonucleotide. EcoRI acts only at the six-term sequences which are exactly like the form(2.1)GAATTCCTTAAG.The effect is to cut the molecule into two pieces as shown in Figure2(c).There are over 100 different restriction enzymes, each of which cuts at its specific recognition site. A restriction enzyme cuts DNA into pieces with sticky ends. On the other hand, sticky ends will match and attach to other sticky ends of any other DNA that has been cut with the same enzyme. DNA ligase joins the matching sticky ends of the DNA pieces from different sources that have been cut by the same restriction enzyme.


## 2.2. DNA-Computing Models

There are several types of DNA-computing models among which the Adleman-Lipton model is the most traditional one. This model focuses on the hybridization between different DNA molecules as a basic step of computations. According to Adleman and Lipton’s original works [2, 3], this traditional DNA-computing strategy is based on enumerating all candidate solutions, and then using some selection process to choose the correct DNA. This technique requires that the size of the initial data pool increases exponentially with the number of variables in the calculation.Apart from the Adleman-Lipton model, other DNA computing models appeared such as the sticker model, the splicing model. The Sticker model is based on a coding scheme called DNA complex. A DNA complex is a partially double DNA strand. Usually a double piece represents a bit with value one while a single-strand represents zero. Hence each complex is constructed by two single stranded DNA molecules referred to as memory strands and sticker strands. A memory strand containsn nonoverlapping substrands each of which is m bases long. Each sticker strand is m bases long and is complementary to exactly one of the n substrands in a memory strand.The second model is the splicing model proposed by Tom [6] based on formal language theory. A splicing system S=(A,L,B,C) consists of a finite alphabet A, a finite set I of initial strings in A* (language over A), and finite sets B and C of triples (c,x,d) with c,d,x∈A*. Each such triple in B or C is called a pattern. For each such triple the string cxd is called a site, and the string x is called a crossing. Patterns in B are called left patterns, and patterns in C are called right patterns. The language L=L(S) generated by S consists of the strings in I and all strings that can be obtained by adjoining to Lucxfq and pexdv whenever ucsdv and pexfq are in L and (c,x,d) and (e,x,f) are patterns of the same hand. A language L is a splicing language if there exists a splicing system S for which L=L(S).The next model is thek-armed model which is based on some more complicated molecule structures which have three-dimensional DNA architecture. In [13] the authors pointed out that it is natural to use the armed model to represent SAT problem in terms of contact network framework, and they gave theoretical solutions to this NP-complete problems. Like the splicing model, biological operations in the k-armed model include cleaving and connecting.


## 2.3. Operations of the Adleman-Lipton Model

The basic principle of DNA computing is to use the encoded information in the sequence of nucleotides and evolve them by breaking and making new bonds between them to reach the answer. The basic operations performed by enzymes are denaturing, replicating, merging, detecting, and so forth.According to the DNA computing models proposed by Adleman [2] and Lipton [3], there are several basic DNA operations. One important operation is hybridization which is a main process in DNA computing to form all possibilities of solution strands in which the right answer lies. Hybridization is done by mixing strands in tubes with the help of some enzymes.Apart form hybridization, the basic DNA operations available on DNA are mainly the following.(i)
Merge.m(N1,N2)≜N1∪N2=N.(ii)
Amplify.Duplicate(N1)=N.(iii)
Detect(N).(iv)
Separate or extract.N←+(N,w),N←-(N,w). Given a word w consisting of strings from Σ={A,G,C,T} and a tube N, generate two tubes +(N,w) and -(N,w) which contain and does not contains the string w.(v)
Length separate.N←(N,≤n). Given a tube N and an integer n, generate a tube containing stands with length less or equal to n.(vi)
Position separate.N←B(N1,w), N←E(N1,w). Given a tube and word generate a tube with stands beginning (ending) with the word.


## 3. Grid-Based Clustering

The grid-based clustering uses a multiresolution grid structure, called cells, which contains the data objects and acts as operands of clustering performance. Traditional approaches include STRING WaveCluster, and CLIQUE [8]. The most common grids are regular hypercubic grid. This requires that the grid construction covers all the data space with the same precision. The second method uses flexible grids, that is, multiresolution grids with hypercubic or hyperrectangular cells having randomly oriented borders [14].


### 3.1. A Flexible Grid Definition

Suppose that the data set isΩ={x1,…,xN}⊂Rn. It is bounded by a rectangle D0 in Rn. A grid is a undirected graph 𝒢=(V,E) where each node of V is called a cell and is represented by a quad v=(D,c,p,σ), where D is a polyhedra, c is a center point of D, p=|ω∩D| is the number of points of Ω covered by the cell, and σ is the diameter of D. We will always assume that a cell is nontrivial; that is, D has interior points in Rn. For a cell v=(D,c,p,σ), its boundary is denoted by ∂D which is the set of hyperplane pieces bounding the polyhedra. If S∈∂D and S is part of a hyperplane H, then H is called a tangent plane of the cell. Two nodes vi=(Di,ci,pi,σi), i=1,2, are called adjacent if the two cells share a common tangent plane and D1∩D2≠∅. For two adjacent cells, define an edge between them. Hence, E={uv:uandvareadjacent}. Figure 3 presents an illustration of tangent plane and adjacent cells.Figure 3
Illustration of tangent plane and adjacent cells.To construct the graph𝒢, we need two parameters p0 and σ0 indicating the minimum number of points to be considered, and the minimum diameter. Then the graph is constructed iteratively. We start with the first node v1=(D0,c1,N,σ1), where D0 is the original rectangle, c0 is the center of D0. Then at each step, the cell containing dense points (controlled by a threshold value p0), or with larger diameter (controlled by threshold value σ0), is split into two subcells by a hyperplane. A cell is sparse if it contains less points than p0. It is called a small cell if its diameter is less than σ0. If we reach a sparse or small cell, then add this cell to the node set of the graph. This step continues until no more cell left to be split. The resulting graph is called a flexible grid. Algorithm 1 gives the algorithm for the graph construction process.Algorithm 1:A flexible grid construction algorithm.
Inputs:   Ω={x1,x2,…,xN} dataset of N points in Rn, D: hyper-rectangle containing Ω, p0:population threshold value,σ0: cell diameter threshold valueOutputs:V={v1,v2,…}: set of verticesBeginV(1)={v1=(D0,c1,N,σ1)}. Let t=1 and D1=D0.whileV(t)≠∅   dofor eachv=(D,c,p,σ)∈V(t)doChoose a cutting hyperplaneL passing c. Cut the current cell v into two subcells v′,v′′.For eachv∈{v′,v′′} of the new cells, if pv<p0 or diam(Dv)<σ0, add this new cell vto the node setV. Else add v to V(t+1).endfort=t+1;endEndWe present an example to show the data set and the flexible grid generated by the above algorithm (Figure4).Figure 4
An example of flexible grid with induced graph.Next we define the weights on edges. A weight on an edge is the dissimilarity of the adjacent nodes. Suppose that the Euclidean distance inRn is denoted by d(·,·). Here and after, we will always assume that a data point x∈D means x∈D∩Ω. Then for two nodes vi=(Di,ci,pi,σi), i=1,2, the weight is defined by(3.1)ω(v1,v2)={0,ifmin⁡{p1,p2}=01p1p2min⁡x∈D1,y∈D2d(x,y)ifmin⁡{p1,p2}>0.


### 3.2. Clustering Problems

When the graph is constructed, the clustering problem is converted into grouping nodes of the graph into clusters. Traditional techniques include the hierarchical clustering [8] For the purpose of this paper, we will give a different approach for this problem. First it should be noted that nodes corresponding to sparse areas are outliers. Therefore, in order to reduce computing complexity, we first remove all sparse graph nodes with corresponding edges. We still use 𝒢=(V,E) to denote the resulting graph, where V is the set of vertices, and E the set of weighted edges. An example is shown in Figure 4 with part of its edges.Now we consider the problem of weight computation. By the graph construction procedure, we know that any node will correspond to a cell with diameter no larger thanσ0. Therefore, the distance between cells can be approximated by d(c1,c2), and (3.1) will be(3.2)ω(v1,v2)=1p1p2d(c1,c2).In this way we can significantly reduce the computing time without loss of much precision. Again we define a parameter0<ω0≤∞. We will eliminate those edges with weight ω>ω0. If this parameter ω0=∞, this means that no edges are eliminated. Now we use 𝒞={Vq:q=1,2,…,k} to denote a clustering of the vertices set V of graph 𝒢 for threshold values p0 and σ0. Next we will use |Vq| to denote the number of its vertices. Define the energy of clustering as follows:(3.3)min⁡E(C):E(C)=∑q=1k∑vi≠vjvi,vj∈Vqω(vi,vj),min⁡Eint⁡(C):Eint⁡(C)=(min⁡1≤i,j≤ki≠j⁡min⁡u∈Viv∈Vj⁡ω(u,v))-1.Then the clustering problem is a minimization of the energy functions. However, the optimization problem is hard to solve. We will present a variation in the following.


### 3.3. Path Clustering

Now we consider the graph𝒢=(V,E) with weight matrix W. Assume that the number k of clusters is a positive integer. A Hamiltonian path ℒ of 𝒢 is a path that visited each vertex exactly once. Now we remove k-1 nonadjacent edges from ℒ and denote the result by ℒk. Define the energy E(ℒk) of Lk as the sum of its edge weights. The path with least energy E(ℒk) is called a path clustering(3.4)min⁡{E(Lk):foranyL.E(Lk):foranyL,2≤k≤N.The first minimization of (3.4) is clustering for a fixed k, and the latter is clustering without fixing k. Path clustering is slightly different with distance-based clustering. The next example illustrates path clustering (Figure 5).Figure 5
An example of path clustering with three clusters.


## 3.1. A Flexible Grid Definition

Suppose that the data set isΩ={x1,…,xN}⊂Rn. It is bounded by a rectangle D0 in Rn. A grid is a undirected graph 𝒢=(V,E) where each node of V is called a cell and is represented by a quad v=(D,c,p,σ), where D is a polyhedra, c is a center point of D, p=|ω∩D| is the number of points of Ω covered by the cell, and σ is the diameter of D. We will always assume that a cell is nontrivial; that is, D has interior points in Rn. For a cell v=(D,c,p,σ), its boundary is denoted by ∂D which is the set of hyperplane pieces bounding the polyhedra. If S∈∂D and S is part of a hyperplane H, then H is called a tangent plane of the cell. Two nodes vi=(Di,ci,pi,σi), i=1,2, are called adjacent if the two cells share a common tangent plane and D1∩D2≠∅. For two adjacent cells, define an edge between them. Hence, E={uv:uandvareadjacent}. Figure 3 presents an illustration of tangent plane and adjacent cells.Figure 3
Illustration of tangent plane and adjacent cells.To construct the graph𝒢, we need two parameters p0 and σ0 indicating the minimum number of points to be considered, and the minimum diameter. Then the graph is constructed iteratively. We start with the first node v1=(D0,c1,N,σ1), where D0 is the original rectangle, c0 is the center of D0. Then at each step, the cell containing dense points (controlled by a threshold value p0), or with larger diameter (controlled by threshold value σ0), is split into two subcells by a hyperplane. A cell is sparse if it contains less points than p0. It is called a small cell if its diameter is less than σ0. If we reach a sparse or small cell, then add this cell to the node set of the graph. This step continues until no more cell left to be split. The resulting graph is called a flexible grid. Algorithm 1 gives the algorithm for the graph construction process.Algorithm 1:A flexible grid construction algorithm.
Inputs:   Ω={x1,x2,…,xN} dataset of N points in Rn, D: hyper-rectangle containing Ω, p0:population threshold value,σ0: cell diameter threshold valueOutputs:V={v1,v2,…}: set of verticesBeginV(1)={v1=(D0,c1,N,σ1)}. Let t=1 and D1=D0.whileV(t)≠∅   dofor eachv=(D,c,p,σ)∈V(t)doChoose a cutting hyperplaneL passing c. Cut the current cell v into two subcells v′,v′′.For eachv∈{v′,v′′} of the new cells, if pv<p0 or diam(Dv)<σ0, add this new cell vto the node setV. Else add v to V(t+1).endfort=t+1;endEndWe present an example to show the data set and the flexible grid generated by the above algorithm (Figure4).Figure 4
An example of flexible grid with induced graph.Next we define the weights on edges. A weight on an edge is the dissimilarity of the adjacent nodes. Suppose that the Euclidean distance inRn is denoted by d(·,·). Here and after, we will always assume that a data point x∈D means x∈D∩Ω. Then for two nodes vi=(Di,ci,pi,σi), i=1,2, the weight is defined by(3.1)ω(v1,v2)={0,ifmin⁡{p1,p2}=01p1p2min⁡x∈D1,y∈D2d(x,y)ifmin⁡{p1,p2}>0.


## 3.2. Clustering Problems

When the graph is constructed, the clustering problem is converted into grouping nodes of the graph into clusters. Traditional techniques include the hierarchical clustering [8] For the purpose of this paper, we will give a different approach for this problem. First it should be noted that nodes corresponding to sparse areas are outliers. Therefore, in order to reduce computing complexity, we first remove all sparse graph nodes with corresponding edges. We still use 𝒢=(V,E) to denote the resulting graph, where V is the set of vertices, and E the set of weighted edges. An example is shown in Figure 4 with part of its edges.Now we consider the problem of weight computation. By the graph construction procedure, we know that any node will correspond to a cell with diameter no larger thanσ0. Therefore, the distance between cells can be approximated by d(c1,c2), and (3.1) will be(3.2)ω(v1,v2)=1p1p2d(c1,c2).In this way we can significantly reduce the computing time without loss of much precision. Again we define a parameter0<ω0≤∞. We will eliminate those edges with weight ω>ω0. If this parameter ω0=∞, this means that no edges are eliminated. Now we use 𝒞={Vq:q=1,2,…,k} to denote a clustering of the vertices set V of graph 𝒢 for threshold values p0 and σ0. Next we will use |Vq| to denote the number of its vertices. Define the energy of clustering as follows:(3.3)min⁡E(C):E(C)=∑q=1k∑vi≠vjvi,vj∈Vqω(vi,vj),min⁡Eint⁡(C):Eint⁡(C)=(min⁡1≤i,j≤ki≠j⁡min⁡u∈Viv∈Vj⁡ω(u,v))-1.Then the clustering problem is a minimization of the energy functions. However, the optimization problem is hard to solve. We will present a variation in the following.


## 3.3. Path Clustering

Now we consider the graph𝒢=(V,E) with weight matrix W. Assume that the number k of clusters is a positive integer. A Hamiltonian path ℒ of 𝒢 is a path that visited each vertex exactly once. Now we remove k-1 nonadjacent edges from ℒ and denote the result by ℒk. Define the energy E(ℒk) of Lk as the sum of its edge weights. The path with least energy E(ℒk) is called a path clustering(3.4)min⁡{E(Lk):foranyL.E(Lk):foranyL,2≤k≤N.The first minimization of (3.4) is clustering for a fixed k, and the latter is clustering without fixing k. Path clustering is slightly different with distance-based clustering. The next example illustrates path clustering (Figure 5).Figure 5
An example of path clustering with three clusters.


## 4. Clustering by DNA Computing

In this section we consider clustering of the graph𝒢=(V,E). We still use N to denote the number of nodes in V, and this will not cause any confusion. Suppose that the number of clusters is k which is a priori determined, or defined in the process of clustering. The problem is to partition the vertex set V into k clusters. Suppose that the original data set Ω is bounded by a constant M/2>0, that is, ∥x∥≤M/2 for x∈Ω. Here we use the Euclidean distance for points in Rn and ∥x∥=a12+⋯+an2, where x=[a1,…,an]. Points in Ω are denoted by xi and Ω={x1,…,xN}. A point in the data set Ω will be denoted by the lower case letter x.For each pointx∈Ω and a cluster C, define the distance between them as d(x,C)=minz∈Cd(c,z) where d(·,·) is the Euclidean distance. If C1, C2 are two clusters, then define d(C1,C2)=minx∈C1y∈C2d(x,y). Clearly these distances are bounded by the constant M. For u,v∈V define the dissimilarity measure as ρ(u,v)=ω(x,y)/M. Clearly these dissimilarity measures are in the interval [0,1].Now we convert the dissimilarity measures into integers. First we need to define an acceptable error rateε>0. This means that we do not distinguish those measures where their difference is less than ε. Now we divide the interval [0,1] into I subintervals with equal width I-1<ε. For z∈[0,1] let its corresponding integer be s(z)=[Iz] where operator [·] is the largest integer without exceeding it. Hence the dissimilarity measure lies in the set {1,…,I}.Now we define the weight matrix on the graph𝒢 by(4.1)W=[wij]N×N,wij=s(ρ(xi,xj)),i,j=1,…,N.A clustering of the graph𝒢, denoted by 𝒞, is a partition V=∪i=1kCi. Thus any clustering can be taken as a rearrangement of the vertices v1,…,vN. For example, the vertex set {{v3,v2,v1},{v5,v4},{v6,v7,v8,v9}} with three clusters can be written as (4.2)C=v3v2v1αv5v4αv6v7v8v9.Here we use the greed letterα as a separator between clusters. Therefore, we have k-1 separators if we obtain k clusters. If we take dissimilarity measure into account, then a clustering will be as follows:(4.3)C=v3w32v2w21v1αv5w54v4αv6w67v7w78v8w89v9.Now we have converted the clustering problem to a permutation problem. That is, any permutation of the set{1,2,…,N,α,…,α} (the number of α’s is k-1) is a candidate solution. The string with minimum length is the optimal solution.


### 4.1. DNA Coding for Data

First we give the encoding of the dissimilarity measure, or the weights. In order to do this, we assume that 1 is coded by the stringAG. And any integer i∈{1,…,I} is coded by seq(i):(4.4)seq(i)=AGAG⋯⋯AG︷inumberofAGs.Next we present the encoding of a vertexv∈V. This is done by using a fixed mer sequence as the following example (20-mer):(4.5)seq(v)=5′-TCTCTCTCTCTCTCTCTCTCTCTCT-3′.The separatorα is also coded with a single-strand seq(α) of the same length with that of points. This is done exactly as the data point coding except that we need to distinguish separators with data points.


### 4.2. Encoding Scheme

Now we need to put everything together for a candidate solution (4.3). First we design a code for an edge uv∈E with weight w. This is done by linking the last half part of seq(u), seq(w), and the first half of seq(v) as shown in Figure 6(a). We need two special edges called the left half-edge and the right half-edge. The left half edge is a linking of seq(u), seq(w), and the first half of seq(v). The right half edge is a linking of the first half of seq(u), seq(w), and seq(v).DNA-encoding architecture.
(a)
Designated DNA coding for an edgeuv(b)
Designated DNA coding for an left half-edge(c)
Designated DNA coding for a centroidNext we define coding for a centroid which is a complementary form of a separatorα. First for two vertices u,v∈V, we define its similarity as ρ̂(u,v)=I-s(ρ(u,v)). One should notice the difference with dissimilarity measure defined in the matrix W. Now we define the code of a centroid as a linking of the last half part of seq(u), seq(α), seq(ρ̂(u,v)), and the first half of seq(v) as shown in Figure 6(c). Here u,v are two vertices in V.Finally, the code for a cluster𝒞 is a permutation of the following string without changing the position of the left half-edge and the right half-edge:
(4.6)seq(C)=A⋯C︷lefthalf-edgeA⋯C︷edgesG⋯T︷centroid⋯⋯G⋯T︷centroidA⋯C︷edges⎴N-k-1edges,k-1centroidsT⋯G︷righthalf-edge.⎵Npointsandk-1separatorsaltogether


### 4.3. DNA Program

Now we describe the biological operations for the clustering. First we put single strands in a tubeT0 including complementary strands of all vertices, complementary strands of the separator α, and complementary strands of integers 1,2,…,I. These strands serve as splints. We also pour strands into T0 of all the left half-edges, right half-edges, strands of integers 1,2,…,I, all edges, and all centroids. Then hybridization and ligation can be executed. As a result, all combinations representing clustering schemes are obtained in the tube T0.In order to select acceptable solutions among these combinations, we need to eliminate those strands which do not contain a separatorα and those which do not contain all the vertices v1,…,vN. Finally, by counting the number of separators α as k of the strand with shortest length, we get the solution of the clustering problem. This final procedure can be implemented by direct observation to calculate the separator sequences by using special microscope such as atomic force microscope (AFM) to identify and calculate marking sequences [7].The DNA program of biological operations is shown in Algorithm2.Algorithm 2:The DNA program.
Step and Procedure(1)Input(T0).All DNA sequences and complementary DNA sequences are placed in empty test tubeT0.(2)Amplify(T0).Make all sequences inT0 mixed together and execute ligation process. After hybridizationprocess, all possible combinations of DNA sequences happen inT0.(3)T1←+(T0,seq(α)).Select only those DNA strands which include at least one separatorα from T0 and keep theminto empty test tubeT1.(4)fori=1  toN  do{beginT1←+(T1,seq(vi))end;}endfor; T2←T1.Select all DNA strands that contain all theN vertices v1,…,vN in test tube T1. Put them inempty test tubeT2.(5)Gel Electrophoresis.Find the shortest DNA sequence in test tubeT2. Put them in an empty tube T3. This is thesolution of clustering the problem.(6)Count the number of separatorsα.Amplify and count the number of clusters in tubeT3.END


## 4.1. DNA Coding for Data

First we give the encoding of the dissimilarity measure, or the weights. In order to do this, we assume that 1 is coded by the stringAG. And any integer i∈{1,…,I} is coded by seq(i):(4.4)seq(i)=AGAG⋯⋯AG︷inumberofAGs.Next we present the encoding of a vertexv∈V. This is done by using a fixed mer sequence as the following example (20-mer):(4.5)seq(v)=5′-TCTCTCTCTCTCTCTCTCTCTCTCT-3′.The separatorα is also coded with a single-strand seq(α) of the same length with that of points. This is done exactly as the data point coding except that we need to distinguish separators with data points.


## 4.2. Encoding Scheme

Now we need to put everything together for a candidate solution (4.3). First we design a code for an edge uv∈E with weight w. This is done by linking the last half part of seq(u), seq(w), and the first half of seq(v) as shown in Figure 6(a). We need two special edges called the left half-edge and the right half-edge. The left half edge is a linking of seq(u), seq(w), and the first half of seq(v). The right half edge is a linking of the first half of seq(u), seq(w), and seq(v).DNA-encoding architecture.
(a)
Designated DNA coding for an edgeuv(b)
Designated DNA coding for an left half-edge(c)
Designated DNA coding for a centroidNext we define coding for a centroid which is a complementary form of a separatorα. First for two vertices u,v∈V, we define its similarity as ρ̂(u,v)=I-s(ρ(u,v)). One should notice the difference with dissimilarity measure defined in the matrix W. Now we define the code of a centroid as a linking of the last half part of seq(u), seq(α), seq(ρ̂(u,v)), and the first half of seq(v) as shown in Figure 6(c). Here u,v are two vertices in V.Finally, the code for a cluster𝒞 is a permutation of the following string without changing the position of the left half-edge and the right half-edge:
(4.6)seq(C)=A⋯C︷lefthalf-edgeA⋯C︷edgesG⋯T︷centroid⋯⋯G⋯T︷centroidA⋯C︷edges⎴N-k-1edges,k-1centroidsT⋯G︷righthalf-edge.⎵Npointsandk-1separatorsaltogether


## 4.3. DNA Program

Now we describe the biological operations for the clustering. First we put single strands in a tubeT0 including complementary strands of all vertices, complementary strands of the separator α, and complementary strands of integers 1,2,…,I. These strands serve as splints. We also pour strands into T0 of all the left half-edges, right half-edges, strands of integers 1,2,…,I, all edges, and all centroids. Then hybridization and ligation can be executed. As a result, all combinations representing clustering schemes are obtained in the tube T0.In order to select acceptable solutions among these combinations, we need to eliminate those strands which do not contain a separatorα and those which do not contain all the vertices v1,…,vN. Finally, by counting the number of separators α as k of the strand with shortest length, we get the solution of the clustering problem. This final procedure can be implemented by direct observation to calculate the separator sequences by using special microscope such as atomic force microscope (AFM) to identify and calculate marking sequences [7].The DNA program of biological operations is shown in Algorithm2.Algorithm 2:The DNA program.
Step and Procedure(1)Input(T0).All DNA sequences and complementary DNA sequences are placed in empty test tubeT0.(2)Amplify(T0).Make all sequences inT0 mixed together and execute ligation process. After hybridizationprocess, all possible combinations of DNA sequences happen inT0.(3)T1←+(T0,seq(α)).Select only those DNA strands which include at least one separatorα from T0 and keep theminto empty test tubeT1.(4)fori=1  toN  do{beginT1←+(T1,seq(vi))end;}endfor; T2←T1.Select all DNA strands that contain all theN vertices v1,…,vN in test tube T1. Put them inempty test tubeT2.(5)Gel Electrophoresis.Find the shortest DNA sequence in test tubeT2. Put them in an empty tube T3. This is thesolution of clustering the problem.(6)Count the number of separatorsα.Amplify and count the number of clusters in tubeT3.END


## 5. Examples and Discussions

In this section, we present some examples to illustrate the performance of our algorithm. Then we will show that our technique will give clusters more naturally.


### 5.1. Example One

First we present an example with 20 points to be clustered that is discussed in [7]. First we construct a grid with interval 1 as shown in Figure 7. Then we take p0=1 as minimum points located in each grid. As a result, the induced graph is disconnected with 10 subgraphs. The final result shows four clusters with additional 6 outliers. This is different with result of [7] where they obtain four clusters with no outliers.Figure 7
Data example one with graph generated with grid interval 1. Parametersp0=1.Now we change the grid into interval 2. Then we have only half the grids compared to grid with interval 1. We takep0=1 but we use another parameter ω0=1. This time we surprisingly obtain three clusters (Figure 8) with two outliers. This fact shows that the clustering method proposed here is sensitive to the construction of grids and parameters. Considering various definitions and measurements of clustering, this is not too surprising.Figure 8
Data example one with graph generated with grid interval 2. Parametersp0=1 and ω0=1.Now we construct a grid similar with Figure8 but starting the first horizontal vertical lines not from coordinates (0,2) and (2,0). Identically, we can implement this case by moving the whole data set in the grid of Figure 8. With the same parameters as above, we obtain the third clustering result as shown in Figure 9. Now four clusters are generated without outliers. It is interesting to note that the three different grids induce one common cluster (left-bottom cluster). In fact, this common cluster is better organized than the other clusters. Hence we know that clustering is sensitive to the construction of grids especially for those bad clusters.Figure 9
Data with different grid (interval 2). Parametersp0=1 and ω0=1.


### 5.2. Example Two

Now we consider another example as shown in Figure10 with the data to be clustered and the graph constructed. For this example, we take p0=2. For adjacent cells, if they share a common edge, then we define their dissimilarity measure as 1. Otherwise if they share a common vertex, then define dissimilarity measure as 1.4. There are 40 nontrivial cells.Figure 10
A data example with graph generated. The numbers in circles are the values ofp in cells.Since for any two cellsp1p2≤100, we take I=100 and by (4.1) the weight matrix is(5.1)W=[W1W2W3W4].HereW1, W2, W3, and W4 are 20×20 matrices, and W is symmetric. The matrix W1, W3, W4 is shown in Table 1. The weighted graph is shown in Figure 11.Table 1
Sample data weight matrix[W1,W3,W4].
0500001813350000000000001000035000000000000100007700000000000600006600000000000000352500000000001300000000000000600000000000001300000000000000000000000025002535000000003525000000130013000000090000025000025000003500000010006000000000000000003525000025000000000000002000000000000000000900000000000000001200000000000000431800000000000000060000000000000350000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000009250000000000000000000100000000000006000000000000000003000000000000000000000000000000006043000000000000018000000000000017000000000600001813000000000018000005000023000000018131800250000182502500003502500000000006000600130Figure 11
The constructed graph with weights on edges.By the technique of this paper, the solution of clustering is a string. One of the clustering string as a clustering is as follows:(5.2)v17v18v19v25v24v23αv6v7v8v2v1v9v3v4v5v11v10v14v15v21v20,v26v27v30v29v36v35v34v33v40v39v38v37v31v32v28v22v16v13v12.


## 5.1. Example One

First we present an example with 20 points to be clustered that is discussed in [7]. First we construct a grid with interval 1 as shown in Figure 7. Then we take p0=1 as minimum points located in each grid. As a result, the induced graph is disconnected with 10 subgraphs. The final result shows four clusters with additional 6 outliers. This is different with result of [7] where they obtain four clusters with no outliers.Figure 7
Data example one with graph generated with grid interval 1. Parametersp0=1.Now we change the grid into interval 2. Then we have only half the grids compared to grid with interval 1. We takep0=1 but we use another parameter ω0=1. This time we surprisingly obtain three clusters (Figure 8) with two outliers. This fact shows that the clustering method proposed here is sensitive to the construction of grids and parameters. Considering various definitions and measurements of clustering, this is not too surprising.Figure 8
Data example one with graph generated with grid interval 2. Parametersp0=1 and ω0=1.Now we construct a grid similar with Figure8 but starting the first horizontal vertical lines not from coordinates (0,2) and (2,0). Identically, we can implement this case by moving the whole data set in the grid of Figure 8. With the same parameters as above, we obtain the third clustering result as shown in Figure 9. Now four clusters are generated without outliers. It is interesting to note that the three different grids induce one common cluster (left-bottom cluster). In fact, this common cluster is better organized than the other clusters. Hence we know that clustering is sensitive to the construction of grids especially for those bad clusters.Figure 9
Data with different grid (interval 2). Parametersp0=1 and ω0=1.


## 5.2. Example Two

Now we consider another example as shown in Figure10 with the data to be clustered and the graph constructed. For this example, we take p0=2. For adjacent cells, if they share a common edge, then we define their dissimilarity measure as 1. Otherwise if they share a common vertex, then define dissimilarity measure as 1.4. There are 40 nontrivial cells.Figure 10
A data example with graph generated. The numbers in circles are the values ofp in cells.Since for any two cellsp1p2≤100, we take I=100 and by (4.1) the weight matrix is(5.1)W=[W1W2W3W4].HereW1, W2, W3, and W4 are 20×20 matrices, and W is symmetric. The matrix W1, W3, W4 is shown in Table 1. The weighted graph is shown in Figure 11.Table 1
Sample data weight matrix[W1,W3,W4].
0500001813350000000000001000035000000000000100007700000000000600006600000000000000352500000000001300000000000000600000000000001300000000000000000000000025002535000000003525000000130013000000090000025000025000003500000010006000000000000000003525000025000000000000002000000000000000000900000000000000001200000000000000431800000000000000060000000000000350000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000009250000000000000000000100000000000006000000000000000003000000000000000000000000000000006043000000000000018000000000000017000000000600001813000000000018000005000023000000018131800250000182502500003502500000000006000600130Figure 11
The constructed graph with weights on edges.By the technique of this paper, the solution of clustering is a string. One of the clustering string as a clustering is as follows:(5.2)v17v18v19v25v24v23αv6v7v8v2v1v9v3v4v5v11v10v14v15v21v20,v26v27v30v29v36v35v34v33v40v39v38v37v31v32v28v22v16v13v12.


## 6. Clustering of the Iris Data

In this section, we present another detailed examples to illustrate the encoding of the DNA-based clustering technique proposed in previous sections. The new example is the well-known Iris flower data set problem. The Iris flower data set is introduced by Sir Ronald Aylmer Fisher as an example of discriminant analysis [15]. The data set consists of 50 samples from each of three species of Iris flowers, that is, Iris setosa, Iris virginica, and Iris versicolor. Four features were measured from each sample, and they are the length and the width of sepal and petal [15, 16].


### 6.1. Grids and Graph of the Problem

Now we use a matrixX|150×4 to denote the data set. Then X is located in a rectangle [4.3,7.7]×[2.0,4.4]×[1.1,6.9]×[0.1,2.5] which is in the four-dimensional space R4. A grid cell (rectangle) D in R4 has 24+4×23+4×22+4×2 adjacent cells. If we choose D0=[4.01,8.01]×[1.81,5.01]×[1.01,7.01]×[0.01,3.01] for instance, then the grids are defined as follows:(6.1)g1=[4.01,4.21,4,41,4,61,4,81,5,01,…,7.81,8.01],g2=[1.81,2.01,2.21,2.41,2.61,…,4.81,5.01],g3=[1.01,1.21,1.41,1.61,1.81,2.01,…,6.81,7.01],g4=[0.01,0.21,0.41,0.61,0.81,…,2.61,2.81,3.01].Then the cells can be denoted by𝒟={Dpqrs∣20×16×30×15} with 144000 cells which is a huge number. Due to this reason, we choose x2x4 among the four dimensions as shown in the first image in Figure 12 as cluster feature variables. The second figure in the same image shows the other two dimensions x1x2 which is studied in Qu et al. [16].Figure 12
The Iris data figures for dimensionsx2-x4 and x1-x2.Next we design a flexible grid structure as shown in Figure13. Choose parameter p0=0. Then the induced graph is shown in Figure 14. By (3.2) and direct computation, we obtain dissimilarities as matrices of the graph. Now we define the error rate ε=0.001 and I=1000. We cut the weight value by a maximum value 999. Then the weight matrices of 𝒢 are shown as in Tables 2 and 3. Here we write the matrix as(6.2)W=[W11W12W22W22],W11,W12,W21,W22are13×13sub-matrices.Table 2
Dissimilarity weight matricesW11,W12,W22 of subgraphs I.
0672366711801005650283017750050070701001980501067910601339999250001250125039509999990999000053001580025035402503543540250035435400999099900500035403548801181130152033350035401571432000372368394016392204001250500Table 3
Dissimilarity weight matrix of subgraphs II.
016779679401411003545000331670400100183050070750009999990999099900Figure 13
The Iris data figure for dimensionx2-x4 and with grids and candidate graph nodes.The induced graph with weight.
(a)
The number in node is its ID, and the number on edges is the weight value(b)
The number in the circled nodes is the population of each cellFor the two subgraphs as in Figure14, we can find Hamiltonian paths easily. For subgraph two, the path is(6.3)v1v2v7v8v11v6v5v4v3v10v9.There exists many paths for subgraph one. One shortest path with indicatorα along the edge v16v22 as shown in Figure 15(a) is(6.4)v11v3v2v1v4v5v6v12v13v15v18v10v9v17v8v14v7v16v22v23v20v26v25v21v24v19.A short Hamiltonian path for the induced graph.
(a)
The shortest Hamiltonian path obtained(b)
The three clusters DNA methodThe detailed encoding scheme is shown in the Appendix. The final clustering result is shown in Figure15(b). The number of points which is not correctly clustered is 7. Clearly this is much better than other methods such as CEPSO of [16] where the error number is more than 20.


### 6.2. Discussions

Now we present some discussions about the time and computational costs of the proposed technique in this section. According to Algorithms1 and 2, the computational costs consist of two main procedures, that is, the grid construction and biological operations, and we will show that the complexity is roughly linear.First we check Algorithm1 for the construction of flexible grids. The time complexity is the total searching counts ∑t=1t=T|V(t)| where |V(t)| is the cardinality of V(t) and T is the final t that V(t) reaches null. Clearly |V(t)|≤2t. Now we estimate the upper bound of T. In the worst case when V(t) consists of 2t cells, and each cell has a data population larger than p0, we have(6.5)p02t≤N.There we obtain the estimateT≤log(N/p0). And the total time upper bound is a linear time as follows:(6.6)∑t=1T|V(t)|≤∑t=0T2T≤2T+1≤2Np0.Next we analyze the complexity of DNA program as proposed in Algorithm2. It is clear that the DNA program consists of three searching procedures. Step 3 selects those strands which contain at least one marker α which is a O(1) operation. Step 4 checks if we get a sequence containing all the vertices with a complexity of O(Nv), where Nv is the number of vertices and Nv≤N. The final Step 6 counts the number of α′s and splits the sequence into clusters. For the shortest sequence which contains all the vertices, the maximum number of markers α is Nv. Hence the total DNA complexity of the program is O(N) which is linear.Finally we make some comments about experiments. By Adleman [2] and Păun et al. [1], when we design a DNA program for solving the problem, a test tube (as taken in the laboratory) is considered a multiset of words (finite strings) over the alphabet {A,C,G,T} with basic operations proposed as in [1, 2]. These basic operations are standard and biologically implementable.However, when we want to simulate the algorithm with personal computers, there will appear some tricky complexity that lay behind the biological operations. Again we analyze the steps in Algorithm2. First we consider Step 2, and we only consider generating sequences containing each vertex exactly once. The time complexity here will be O(2Nv)=O(2N). By examining other steps, we find the total time is O(2N).


## 6.1. Grids and Graph of the Problem

Now we use a matrixX|150×4 to denote the data set. Then X is located in a rectangle [4.3,7.7]×[2.0,4.4]×[1.1,6.9]×[0.1,2.5] which is in the four-dimensional space R4. A grid cell (rectangle) D in R4 has 24+4×23+4×22+4×2 adjacent cells. If we choose D0=[4.01,8.01]×[1.81,5.01]×[1.01,7.01]×[0.01,3.01] for instance, then the grids are defined as follows:(6.1)g1=[4.01,4.21,4,41,4,61,4,81,5,01,…,7.81,8.01],g2=[1.81,2.01,2.21,2.41,2.61,…,4.81,5.01],g3=[1.01,1.21,1.41,1.61,1.81,2.01,…,6.81,7.01],g4=[0.01,0.21,0.41,0.61,0.81,…,2.61,2.81,3.01].Then the cells can be denoted by𝒟={Dpqrs∣20×16×30×15} with 144000 cells which is a huge number. Due to this reason, we choose x2x4 among the four dimensions as shown in the first image in Figure 12 as cluster feature variables. The second figure in the same image shows the other two dimensions x1x2 which is studied in Qu et al. [16].Figure 12
The Iris data figures for dimensionsx2-x4 and x1-x2.Next we design a flexible grid structure as shown in Figure13. Choose parameter p0=0. Then the induced graph is shown in Figure 14. By (3.2) and direct computation, we obtain dissimilarities as matrices of the graph. Now we define the error rate ε=0.001 and I=1000. We cut the weight value by a maximum value 999. Then the weight matrices of 𝒢 are shown as in Tables 2 and 3. Here we write the matrix as(6.2)W=[W11W12W22W22],W11,W12,W21,W22are13×13sub-matrices.Table 2
Dissimilarity weight matricesW11,W12,W22 of subgraphs I.
0672366711801005650283017750050070701001980501067910601339999250001250125039509999990999000053001580025035402503543540250035435400999099900500035403548801181130152033350035401571432000372368394016392204001250500Table 3
Dissimilarity weight matrix of subgraphs II.
016779679401411003545000331670400100183050070750009999990999099900Figure 13
The Iris data figure for dimensionx2-x4 and with grids and candidate graph nodes.The induced graph with weight.
(a)
The number in node is its ID, and the number on edges is the weight value(b)
The number in the circled nodes is the population of each cellFor the two subgraphs as in Figure14, we can find Hamiltonian paths easily. For subgraph two, the path is(6.3)v1v2v7v8v11v6v5v4v3v10v9.There exists many paths for subgraph one. One shortest path with indicatorα along the edge v16v22 as shown in Figure 15(a) is(6.4)v11v3v2v1v4v5v6v12v13v15v18v10v9v17v8v14v7v16v22v23v20v26v25v21v24v19.A short Hamiltonian path for the induced graph.
(a)
The shortest Hamiltonian path obtained(b)
The three clusters DNA methodThe detailed encoding scheme is shown in the Appendix. The final clustering result is shown in Figure15(b). The number of points which is not correctly clustered is 7. Clearly this is much better than other methods such as CEPSO of [16] where the error number is more than 20.


## 6.2. Discussions

Now we present some discussions about the time and computational costs of the proposed technique in this section. According to Algorithms1 and 2, the computational costs consist of two main procedures, that is, the grid construction and biological operations, and we will show that the complexity is roughly linear.First we check Algorithm1 for the construction of flexible grids. The time complexity is the total searching counts ∑t=1t=T|V(t)| where |V(t)| is the cardinality of V(t) and T is the final t that V(t) reaches null. Clearly |V(t)|≤2t. Now we estimate the upper bound of T. In the worst case when V(t) consists of 2t cells, and each cell has a data population larger than p0, we have(6.5)p02t≤N.There we obtain the estimateT≤log(N/p0). And the total time upper bound is a linear time as follows:(6.6)∑t=1T|V(t)|≤∑t=0T2T≤2T+1≤2Np0.Next we analyze the complexity of DNA program as proposed in Algorithm2. It is clear that the DNA program consists of three searching procedures. Step 3 selects those strands which contain at least one marker α which is a O(1) operation. Step 4 checks if we get a sequence containing all the vertices with a complexity of O(Nv), where Nv is the number of vertices and Nv≤N. The final Step 6 counts the number of α′s and splits the sequence into clusters. For the shortest sequence which contains all the vertices, the maximum number of markers α is Nv. Hence the total DNA complexity of the program is O(N) which is linear.Finally we make some comments about experiments. By Adleman [2] and Păun et al. [1], when we design a DNA program for solving the problem, a test tube (as taken in the laboratory) is considered a multiset of words (finite strings) over the alphabet {A,C,G,T} with basic operations proposed as in [1, 2]. These basic operations are standard and biologically implementable.However, when we want to simulate the algorithm with personal computers, there will appear some tricky complexity that lay behind the biological operations. Again we analyze the steps in Algorithm2. First we consider Step 2, and we only consider generating sequences containing each vertex exactly once. The time complexity here will be O(2Nv)=O(2N). By examining other steps, we find the total time is O(2N).


## 7. Conclusion

In this paper we presented a new DNA-based technique for spatial cluster analysis. Two examples are given to show the effect of our algorithm. We do not need the number of clusters in advance. By a flexible grid method we can reduce the size of searching space significantly. This is different with other DNA-based applications in that they enumerate all solutions which will produce a large search space. This is especially useful for large database even through DNA computing that has large parallel ability. Also by changing the grid and corresponding parameters, we can get various clusters.Finally we will point out that nonconvex clusters can be easily obtained by the technique of this paper. Comparing to research in [7] where only convex clusters can be generated, this is useful for complex database to be clustered. Up to the authors knowledge, this is, the first research in cluster analysis by DNA computing for nonconvex clusters. It provides an alternative solution for this traditional knowledge-engineering problem, which is not a combinatorial in nature. Comparing the many applications of DNA computing mainly in combinatorial problems, this is still interesting.



---

*Source: 894207-2012-04-23.xml*