# Solving the Maximum Weighted Clique Problem Based on Parallel Biological Computing Model

Authors: Zhaocai Wang; Jiangfeng Qin; Zuwen Ji; Dongmei Huang; Lei Li
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

The maximum weighted clique (MWC) problem, as a typical NP-complete problem, is difficult to be solved by the electronic computer algorithm. The aim of the problem is to seek a vertex clique with maximal weight sum in a given undirected graph. It is an extremely important problem in the field of optimal engineering scheme and control with numerous practical applications. From the point of view of practice, we give a parallel biological algorithm to solve the MWC problem. For the maximum weighted clique problem withm edges and n vertices, we use fixed length DNA strands to represent different vertices and edges, fully conduct biochemical reaction, and find the solution to the MVC problem in certain length range with O(n2) time complexity, comparing to the exponential time level by previous computer algorithms. We expand the applied scope of parallel biological computation and reduce computational complexity of practical engineering problems. Meanwhile, we provide a meaningful reference for solving other complex problems.


---

## Body

## 1. Introduction

DNA computing, as a comprehensive discipline, can use DNA biological technologies to solve complex practical engineering problems. In 1994, Adleman [1] made use of DNA molecule operations to solve the Hamiltonian path problem with n vertices in O(n) time complexity; simultaneously, he also demonstrated the strong parallel ability of DNA computing. In 1995, Lipton [2] figured out the NP-complete satisfiability problem utilizing Adleman’s biochemical experiment. Since then, DNA biological computing attracted more and more interest from different disciplinary scholars. DNA biological computing has three advantages: high parallelism, low energy consumption, and large memory capacity. Many research scholars, designing DNA procedures and algorithms, succeed in solving multifarious kinds of complicated NP-complete problems [3–21], which promoted development of DNA computing. In order to better apply DNA computing theory to more practical engineering science broad, it is worth trying to solve more intractable problems using the DNA molecular computing. Furthermore, most previous works, relating to DNA computing, focused on how to solve the path search problems that the solutions are continuous head-to-tail ligation edge or vertex sets, so that the possible solutions can be relatively easily represented by DNA strands, while some practical engineering problems, such as maximum weighted clique problem, are discrete set problems without sequentially connected path. So how to represent discrete data on DNA strands is an important key to expand the applied scope of DNA computing.The maximum weighted clique problem has a wide range of applications in optimal engineering scheme and computational mathematics. In this paper, DNA algorithm, based on the research foundation of Adleman [1] and Lipton [2], is used to get solution of the maximum weighted clique problem. The rest dissertation is organized as follows. In Section 2, the parallel biological computing model is introduced with detailed description. Section 3 uses DNA molecular algorithm to solve the maximum weighted clique problem. Section 4 proves DNA algorithm correctness and feasibility and gets the computation complexity. We come to the conclusions in Section 5.


## 2. The Parallel Biological Computing Model

DNA is the material basis of biological genetics, which is strung together from deoxyribonucleotides. DNA is formed by four kinds of base composition. These bases are, respectively, called adenine (A), guanine (G), cytosine (C), and thymine (T). The permutation and combination of bases store genetic information. An important feature of DNA is that two single strands can form a double strand through complementary base pairing. Moreover, the pairing has high specificity: A can only match T; C can only be paired with G. The length of a DNA single strand is counted by the number of bases. For example, a single strand (ATTCG) includes 5 bases; then it is called a 5mer.Based on Adleman [1] and Lipton’s [2] research, DNA biological algorithm operations are described as follows. Corresponding biological operations can be used to get solution of the maximum weighted clique problem. In the parallel biological computing model, we can perform the following operations with given tubes which contain a list of DNA strands.(1)
Copy(P1,P2): given a test tube P1, it can get another test tube P2 with the same strands as P1.(2)
Merge(P1,P2): given two test tubes P1 and P2, it can get the compound strands P1 and P2 in P1 and leave P2 empty.(3)
Annealing(P): given a test tube P, it can generate all feasible double strands in P by annealing. The products and residues are still stored in P after annealing.(4)
Separation(P1,Z,P2): given a test tube P1 and a list strands set Z, it can remove all single strands in Z from P1 and get an another tube P2 with the removed strands.(5)
Ligation(T): given a tube P, it is used to ligate together the strands in P.(6)
Sort(P1,P2,P3): it picks out the shortest length strands into tube P2 from tube P1, the longest strands into P3, and the surplus strands are still kept in P1.(7)
Denaturation(P): given a test tube P, it can dissociate every double strand in P to couple of single strands.(8)
Read(P): given a tube P, it can be used to describe each single strand in P.(9)
Append-tail(P,z): given a test tube P and a single strand z, it can append z at back of each strand in the tube P.(10)
Discard(P): given a test tube P, it discards the strands in tube P and leave P empty.Since above operations are realized through the limited biological experimental procedures with DNA strands [18], we can reasonably conclude that each operation is in O(1) time complexity.


## 3. Biological Algorithm for the Maximum Weighted Clique Problem

An undirected simple graphG=(V,E,W) is a pair of vertex set V={v1,v2,…,vn} with corresponding vertex positive weight value {w1,w2,…,wn} and edge set E={ei,j∣1≤i<j≤n}. For a vertex subset T1⫅V, if ∀vi,vj∈T1, vi and vj can be linked by edge ei,j in the graph, then T1 is called a clique of the graph G, and simultaneously the clique weight is the sum of vertex weight in the T1. The solution of maximum weighted clique problem aims to seek a vertex clique T of graph G with maximal weight sum. For example, the undirected simple graph in Figure 1 is defined as the MVC problem.Figure 1
An undirected simple graphG with 5 vertices and 8 edges.In succession, the symbolsAk, Bk(k=1,2,…,n), 1, 0, #¯, # are composed by different single strands having same length, as tmer. Certainly, t would be best to choose a small integer which can be determined by the scale of the problem. Then in the following algorithms, we use DNA single strands symbols Ak0Bk, Ak1Bk to indicate the vertex vk, with strands symbol Ak1Bk for vertex vk in the vertex subset while Ak0Bk for not. Simultaneously, the symbols #, #¯ are the signal of division between different vertex subsets. We denote DNA singled strands yk to encode the vertex vk weight value with length of wkmer. For distinguishing some edges belonging to the graph G or not, we meantime design DNA strings BiAj in the tube R if ei,j∈E. Let(1)T1={#¯,Ak0Bk¯,Ak1Bk¯∣k=1,2,…,n},T2={#A1,Bn#,0,1,Bk-1Ak∣k=2,3,…,n},R={BiAj∣ei,j∈E},Y=yk∣k=1,2,…,n.For an-vertex graph, every vertex subset can be expressed by a n-bit binary value. The kth bit set to 1 means the vertex vk in the subset; on the contrary, the kth bit set to 0 shows the vertex vk out of the subset. Taking Figure 1, for example, the vertex subset {v2,v3,v5} can be expressed by the binary value 01101. Using the same method, we can represent the vertex subsets of a n-vertex simple graph as a series of n-bit binary numbers.(1)
We generate all possible vertex subsets in graphG;
(1)
Merge(T1,T2);(2)
Annealing(T1);(3)
Ligation(T1);(4)
Denaturation(T1,{#A1},T3);(5)
Discard(T1);(6)
Denaturation(T3,{Bn#},T1).After the above six manipulations, the single strands in tubeT1 mean all kinds of vertex subsets. For example, in Figure 1, we have single strands: (2)#A11B1A21B2A30B3A41B4A51B5#∈T1which denote the vertex subset{v1,v2,v4,v5} corresponding to binary value 11011. These operations can be executed with O(1) time complexity since every operation can be finished in O(1).(2)
Every strand in tubeT1 denotes one kind of vertex subset. For the maximum weighted clique problem, solution is one kind of vertex subset that arbitrary two vertices in the subset can be connected by one edge included in the graph G. Therefore, we check whether all vertex subsets in T1 are in line with the condition or not. If ei,j∉E, we discard the strands indicating that both vertices vi and vj are in the same subset. For example, in Figure 1, the singled strands #A10B1A21B2A30B3A41B4A51B5# representing the vertex subset ({v2,v4,v5}) should be discarded for not including the edge e2,4 in graph G to connect vertices v2 and v4. We choose all possible vertex cliques in graph.
Fori=1 to i=n,
(1)
Separation(P,{Ai1Bi},T2);Forj=1 and j≠i to j=n(2)
Separation(R,{BiAj},T3);(3)
If(Detect(T3));Then(4)
Discard(T3);(5)
Separation(T2,{Aj1Bj},T4);(6)
Merge(P,T2);End forEnd forThrough the above operations, all the single strands in tubeT1 represent different vertex clique subsets. Meanwhile, the algorithm includes two “For” clauses, this step is executed in O(n2) time complexity since each operation can be finished in O(1).(3)
The maximum weighted clique problem should be a maximal vertex clique subset in which arbitrary two vertices should be linked by certain edge of the graphG. So we select the maximal vertex subset from all kinds of vertex clique subsets. If the vertex vk is included in the vertex subset, we append additional strand yk at the end of previous subset strand in order to find the optimum solution strand. For the singled strand (representing the vertex subset {v2,v3,v5}) (3)#A10B1A21B2A31B3A40B4A51B5#∈T1,we append strands{y2,y3,y5} at end of the previous strand to (4)#A10B1A21B2A31B3A40B4A51B5#y2y3y5.
This step can be carried out as follows.Fork=1 to k=n,
(1)
Separation(T1,Ak1Bk,T7);(2)
Append-tali(T7,yk);(3)
Merge(T1,T7);(4)
Dscard(T7).End forThis step includes one “For” clause; thus it can be finished inO(n) time complexity.(4)
We select single strands with the longest length fromT1, which represent the solutions of maximum weighted clique problem. For example, in Figure 1, single strands in T1 with the largest length are (5)#A10B1A20B2A31B3A41B4A51B5#y3y4y5.Consequently, solution of maximum weighted clique problem for Figure1 is vertex subset {v3,v4,v5} with weight sum 15.
(1)
Sort(T1,T8,T9);(2)
Read(T9).


## 4. The Feasibility and Computational Complexity of the Parallel Biological Computing Algorithm

Theorem 1.
The maximum weighted clique problem for an-vertex graph can be solved by the biological computing algorithm.Proof.
At first, we get all kinds of the vertex combinational subset in the test tube after Step(1). For the maximum weighted clique problem, if ei,j∉E, vertices vi and vj should be not in the same subset. Therefore, basic biological manipulations remove illegal combinations and seek legal ones from solution space strands through the Step (2). At Step (3), we append a series of “tails” yk at the end of the strands which imply the vertex vk included in the vertex subset. Owing to the length of strands yk=wk, the longest length strands in the pool mean the solutions of maximum weighted clique problem. Besides, we can search and get the solution at the last step.Theorem 2.
The solutions of maximum weighted clique problem for an-vertex graph can be solved in O(n2) time complexity using DNA molecules computing.Proof.
The parallel biological computing algorithm can be entirely executed in finite time complexity such as Steps(1) and (4) in O(1), Step (3) in O(n), and simultaneously Step (2) in O(n2) time complexity. The total algorithm complexity T is as below: (6)T(Step(1))=O(1);T(Step(2))=O(n);T(Step(3))=O(n2);T(Step(4))=O(1);T=TStep1+TStep2+T(Step(3))+T(Step(4));=O(1)+O(n2)+O(n)+O(1);=O(n2).In conclusion, we can get the solutions of maximum weighted clique problems with n-vertices in O(n2) time complexity.Theorem 3.
Solution strands to the maximum weighted clique problem withn-vertices can be found in the finite length range.Proof.
After Step(1), the singled strands in tube T1 denote all possible vertex subsets. These strands can be described as follows:(7)#A1x1B1A2x2B2⋯AkxkBk⋯AnxnBn#xk=0or1.At Step (2), the single strands in T1 mean all possible vertex clique subsets. We design the fixed length strands of #, Ak, Bk, and xk, for (8)Ak=Bk=#=xk=tmer.S is defined as strands assemblage after Step (3). Then S can be described: (9)#A1x1B1A2x2B2⋯AkxkBk⋯AnxnBn#yi1⋯yin.Appending the strands yij or not is decided whether there exists vertex vij information strands Aij1Bij on the previous strands. Due to the fact that the number of vertex vk in sunset is between 1 and n, so after “append” operation, the strands is also in a finite length range: (10)S=#+A1+x1+B1+⋯+Ak+xk+Ak+⋯+An+xn+An+#+yi1+⋯+yin=2#+∑k=1n‍Ak+∑k=1n‍xk+∑k=1n‍Bk+∑xk=1‍yk=(3n+2)t+∑xk=1‍yk∵0≤∑xk=1‍yk≤∑k=1n‍ykLet∑k=1n‍yk=m∴(3n+2)t≤S≤(3n+2)t+m.For the maximum vertex clique problem, the length of solution strands is between (3n+2)t and (3n+2)t+m. Therefore, we can get the solution in appropriate length range at Step (4).


## 5. The Detailed Approach and Walkthrough of the Biological Computing Algorithm

Taking Figure1 as example, we describe operation result of each step. Due to the fact that biological computing algorithm depends on basic biochemical DNA molecules reactions which may cause errors in the process, it is an important matter to make biological computing more reliable by means of the DNA molecular sequence design. To have a better performance in hybridization reactions, we follow [22] to accomplish the sequence design. For the problem of Figure 1, the program generates 3-base random sequences to represent symbols #, Ak, Bk, and yk. If the generated DNA sequence fails to pass any of the constraints, the program will regenerate a new DNA sequence. If the constraints are satisfied, the new DNA sequences are accepted. If all the DNA strands satisfy the constraints, the program has then succeeded and these sequences would be the outputs. The corresponding vertex symbol sequences are shown in Table 1. In accordance with the above design, we can get all kinds of symbol representations of vertex subsets in Table 2 after Step (1). Step (2) discards the inappropriate vertex combinatorial sequences and retains the vertex clique sequences in Table 3. At Step (4), we append the corresponding weighted sequences which are showed in Table 4. Through the “Sort” operation at Step (4), we find the optimal solution to the maximum weighted clique problem of Figure 1 in Table 5.Table 1
Sequences chosen to represent#, Ak,Bk,yk(k=1,2,…,n) in the example of Figure 1.
Symbol
3′-5′ DNA sequence
Symbol
3′-5′ DNA sequence
A
1
C
C
T
B
1
A
C
T
A
2
C
A
C
B
2
T
A
T
A
3
C
T
A
B
3
T
A
A
A
4
T
T
C
B
4
A
T
C
A
5
A
A
C
B
5
C
T
T
0
C
A
A
1
A
A
T
#
T
A
C
y
1
G
G
y
2
G
G
G
y
3
G
G
G
G
G
y
4
G
G
G
G
G
G
y
5
G
G
G
GTable 2
Sequences chosen to represent all kinds of vertex subsets for the example of Figure1.
Vertex  subset
Symbols sequence
3′-5′ DNA sequence
{
v
1
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
A
A
T
A
C
T
C
A
C
C
A
A
T
A
T
C
T
A
C
A
A
T
A
A
T
T
C
C
A
A
A
T
C
A
A
C
C
A
A
C
T
T
T
A
C
{
v
2
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
C
A
A
A
C
T
C
A
C
A
A
T
T
A
T
C
T
A
C
A
A
T
A
A
T
T
C
C
A
A
A
T
C
A
A
C
C
A
A
C
T
T
T
A
C
{
v
3
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
C
A
A
A
C
T
C
A
C
C
A
A
T
A
T
C
T
A
A
A
T
T
A
A
T
T
C
C
A
A
A
T
C
A
A
C
C
A
A
C
T
T
T
A
C
{
v
4
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
C
A
A
A
C
T
C
A
C
C
A
A
T
A
T
C
T
A
C
A
A
T
A
A
T
T
C
A
A
T
A
T
C
A
A
C
C
A
A
C
T
T
T
A
C
{
v
5
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
C
A
A
A
C
T
C
A
C
C
A
A
T
A
T
C
T
A
C
A
A
T
A
A
T
T
C
C
A
A
A
T
C
A
A
C
A
A
T
C
T
T
T
A
C
{
v
1
,
v
2
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
A
A
T
A
C
T
C
A
C
A
A
T
T
A
T
C
T
A
C
A
A
T
A
A
T
T
C
C
A
A
A
T
C
A
A
C
C
A
A
C
T
T
T
A
C
{
v
1
,
v
3
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
A
A
T
A
C
T
C
A
C
C
A
A
T
A
T
C
T
A
A
A
T
T
A
A
T
T
C
C
A
A
A
T
C
A
A
C
C
A
A
C
T
T
T
A
C
{
v
1
,
v
4
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
A
A
T
A
C
T
C
A
C
C
A
A
T
A
T
C
T
A
C
A
A
T
A
A
T
T
C
A
A
T
A
T
C
A
A
C
C
A
A
C
T
T
T
A
C
{
v
1
,
v
5
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
A
A
T
A
C
T
C
A
C
C
A
A
T
A
T
C
T
A
C
A
A
T
A
A
T
T
C
C
A
A
A
T
C
A
A
C
A
A
T
C
T
T
T
A
C
{
v
2
,
v
3
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
C
A
A
A
C
T
C
A
C
A
A
T
T
A
T
C
T
A
A
A
T
T
A
A
T
T
C
C
A
A
A
T
C
A
A
C
C
A
A
C
T
T
T
A
C
{
v
2
,
v
4
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
C
A
A
A
C
T
C
A
C
A
A
T
T
A
T
C
T
A
C
A
A
T
A
A
T
T
C
A
A
T
A
T
C
A
A
C
C
A
A
C
T
T
T
A
C
{
v
2
,
v
5
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
C
A
A
A
C
T
C
A
C
A
A
T
T
A
T
C
T
A
C
A
A
T
A
A
T
T
C
C
A
A
A
T
C
A
A
C
A
A
T
C
T
T
T
A
C
{
v
3
,
v
4
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
C
A
A
A
C
T
C
A
C
C
A
A
T
A
T
C
T
A
A
A
T
T
A
A
T
T
C
A
A
T
A
T
C
A
A
C
C
A
A
C
T
T
T
A
C
{
v
3
,
v
5
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
C
A
A
A
C
T
C
A
C
C
A
A
T
A
T
C
T
A
A
A
T
T
A
A
T
T
C
C
A
A
A
T
C
A
A
C
A
A
T
C
T
T
T
A
C
{
v
4
,
v
5
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
C
A
A
A
C
T
C
A
C
C
A
A
T
A
T
C
T
A
C
A
A
T
A
A
T
T
C
A
A
T
A
T
C
A
A
C
A
A
T
C
T
T
T
A
C
{
v
1
,
v
2
,
v
3
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
A
A
T
A
C
T
C
A
C
A
A
T
T
A
T
C
T
A
A
A
T
T
A
A
T
T
C
C
A
A
A
T
C
A
A
C
C
A
A
C
T
T
T
A
C
{
v
1
,
v
2
,
v
4
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
A
A
T
A
C
T
C
A
C
A
A
T
T
A
T
C
T
A
C
A
A
T
A
A
T
T
C
A
A
T
A
T
C
A
A
C
C
A
A
C
T
T
T
A
C
{
v
1
,
v
2
,
v
5
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
A
A
T
A
C
T
C
A
C
A
A
T
T
A
T
C
T
A
C
A
A
T
A
A
T
T
C
C
A
A
A
T
C
A
A
C
A
A
T
C
T
T
T
A
C
{
v
1
,
v
3
,
v
4
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
A
A
T
A
C
T
C
A
C
C
A
A
T
A
T
C
T
A
A
A
T
T
A
A
T
T
C
A
A
T
A
T
C
A
A
C
C
A
A
C
T
T
T
A
C
{
v
1
,
v
3
,
v
5
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
A
A
T
A
C
T
C
A
C
C
A
A
T
A
T
C
T
A
A
A
T
T
A
A
T
T
C
C
A
A
A
T
C
A
A
C
A
A
T
C
T
T
T
A
C
{
v
1
,
v
4
,
v
5
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
A
A
T
A
C
T
C
A
C
C
A
A
T
A
T
C
T
A
C
A
A
T
A
A
T
T
C
A
A
T
A
T
C
A
A
C
A
A
T
C
T
T
T
A
C
{
v
2
,
v
3
,
v
4
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
C
A
A
A
C
T
C
A
C
A
A
T
T
A
T
C
T
A
A
A
T
T
A
A
T
T
C
A
A
T
A
T
C
A
A
C
C
A
A
C
T
T
T
A
C
{
v
2
,
v
3
,
v
5
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
C
A
A
A
C
T
C
A
C
A
A
T
T
A
T
C
T
A
A
A
T
T
A
A
T
T
C
C
A
A
A
T
C
A
A
C
A
A
T
C
T
T
T
A
C
{
v
2
,
v
4
,
v
5
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
C
A
A
A
C
T
C
A
C
A
A
T
T
A
T
C
T
A
C
A
A
T
A
A
T
T
C
A
A
T
A
T
C
A
A
C
A
A
T
C
T
T
T
A
C
{
v
3
,
v
4
,
v
5
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
C
A
A
A
C
T
C
A
C
C
A
A
T
A
T
C
T
A
A
A
T
T
A
A
T
T
C
A
A
T
A
T
C
A
A
C
A
A
T
C
T
T
T
A
C
{
v
1
,
v
2
,
v
3
,
v
4
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
A
A
T
A
C
T
C
A
C
A
A
T
T
A
T
C
T
A
A
A
T
T
A
A
T
T
C
A
A
T
A
T
C
A
A
C
C
A
A
C
T
T
T
A
C
{
v
1
,
v
2
,
v
3
,
v
5
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
A
A
T
A
C
T
C
A
C
A
A
T
T
A
T
C
T
A
A
A
T
T
A
A
T
T
C
C
A
A
A
T
C
A
A
C
A
A
T
C
T
T
T
A
C
{
v
1
,
v
2
,
v
4
,
v
5
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
A
A
T
A
C
T
C
A
C
A
A
T
T
A
T
C
T
A
C
A
A
T
A
A
T
T
C
A
A
T
A
T
C
A
A
C
A
A
T
C
T
T
T
A
C
{
v
1
,
v
3
,
v
4
,
v
5
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
A
A
T
A
C
T
C
A
C
C
A
A
T
A
T
C
T
A
A
A
T
T
A
A
T
T
C
A
A
T
A
T
C
A
A
C
A
A
T
C
T
T
T
A
C
{
v
2
,
v
3
,
v
4
,
v
5
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
C
A
A
A
C
T
C
A
C
A
A
T
T
A
T
C
T
A
A
A
T
T
A
A
T
T
C
A
A
T
A
T
C
A
A
C
A
A
T
C
T
T
T
A
C
{
v
1
,
v
2
,
v
3
,
v
4
,
v
5
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
T
A
C
C
C
T
A
A
T
A
C
T
C
A
C
A
A
T
T
A
T
C
T
A
A
A
T
T
A
A
T
T
C
A
A
T
A
T
C
A
A
C
A
A
T
C
T
T
T
A
CTable 3
Symbols sequences chosen to represent the different vertex cliques for the example of Figure1.
Vertex  cliques
Symbols sequence
{
v
1
,
v
2
}
#
A
1
1
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
{
v
1
,
v
3
}
#
A
1
1
B
1
A
2
0
B
2
A
3
1
B
3
A
4
0
B
4
A
5
0
B
5
#
{
v
1
,
v
4
}
#
A
1
1
B
1
A
2
0
B
2
A
3
0
B
3
A
4
1
B
4
A
5
0
B
5
#
{
v
1
,
v
5
}
#
A
1
1
B
1
A
2
0
B
2
A
3
0
B
3
A
4
0
B
4
A
5
1
B
5
#
{
v
2
,
v
3
}
#
A
1
0
B
1
A
2
1
B
2
A
3
1
B
3
A
4
0
B
4
A
5
0
B
5
#
{
v
2
,
v
4
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
1
B
4
A
5
0
B
5
#
{
v
2
,
v
5
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
1
B
5
#
{
v
3
,
v
4
}
#
A
1
0
B
1
A
2
0
B
2
A
3
1
B
3
A
4
1
B
4
A
5
0
B
5
#
{
v
3
,
v
5
}
#
A
1
0
B
1
A
2
0
B
2
A
3
1
B
3
A
4
0
B
4
A
5
1
B
5
#
{
v
4
,
v
5
}
#
A
1
0
B
1
A
2
0
B
2
A
3
0
B
3
A
4
1
B
4
A
5
1
B
5
#
{
v
1
,
v
2
,
v
3
}
#
A
1
1
B
1
A
2
1
B
2
A
3
1
B
3
A
4
0
B
4
A
5
0
B
5
#
{
v
1
,
v
2
,
v
5
}
#
A
1
1
B
1
A
2
1
B
2
A
3
0
B
3
A
4
1
B
4
A
5
0
B
5
#
{
v
1
,
v
3
,
v
5
}
#
A
1
1
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
1
B
5
#
{
v
2
,
v
3
,
v
5
}
#
A
1
1
B
1
A
2
0
B
2
A
3
1
B
3
A
4
1
B
4
A
5
0
B
5
#
{
v
3
,
v
4
,
v
5
}
#
A
1
1
B
1
A
2
0
B
2
A
3
1
B
3
A
4
0
B
4
A
5
1
B
5
#
{
v
1
,
v
2
,
v
3
,
v
5
}
#
A
1
1
B
1
A
2
0
B
2
A
3
0
B
3
A
4
1
B
4
A
5
1
B
5
#Table 4
Symbols sequences chosen to represent the vertex weighted cliques for the example of Figure1.
Vertex  set
Symbols sequence
{
v
1
,
v
2
}
#
A
1
1
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
0
B
5
#
y
1
y
2
{
v
1
,
v
3
}
#
A
1
1
B
1
A
2
0
B
2
A
3
1
B
3
A
4
0
B
4
A
5
0
B
5
#
y
1
y
2
{
v
1
,
v
4
}
#
A
1
1
B
1
A
2
0
B
2
A
3
0
B
3
A
4
1
B
4
A
5
0
B
5
#
y
1
y
4
{
v
1
,
v
5
}
#
A
1
1
B
1
A
2
0
B
2
A
3
0
B
3
A
4
0
B
4
A
5
1
B
5
#
y
1
y
5
{
v
2
,
v
3
}
#
A
1
0
B
1
A
2
1
B
2
A
3
1
B
3
A
4
0
B
4
A
5
0
B
5
#
y
2
y
3
{
v
2
,
v
4
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
1
B
4
A
5
0
B
5
#
y
2
y
4
{
v
2
,
v
5
}
#
A
1
0
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
1
B
5
#
y
2
y
5
{
v
3
,
v
4
}
#
A
1
0
B
1
A
2
0
B
2
A
3
1
B
3
A
4
1
B
4
A
5
0
B
5
#
y
3
y
4
{
v
3
,
v
5
}
#
A
1
0
B
1
A
2
0
B
2
A
3
1
B
3
A
4
0
B
4
A
5
1
B
5
#
y
3
y
5
{
v
4
,
v
5
}
#
A
1
0
B
1
A
2
0
B
2
A
3
0
B
3
A
4
1
B
4
A
5
1
B
5
#
y
4
y
5
{
v
1
,
v
2
,
v
3
}
#
A
1
1
B
1
A
2
1
B
2
A
3
1
B
3
A
4
0
B
4
A
5
0
B
5
#
y
1
y
2
y
3
{
v
1
,
v
2
,
v
5
}
#
A
1
1
B
1
A
2
1
B
2
A
3
0
B
3
A
4
1
B
4
A
5
0
B
5
#
y
1
y
2
y
5
{
v
1
,
v
3
,
v
5
}
#
A
1
1
B
1
A
2
1
B
2
A
3
0
B
3
A
4
0
B
4
A
5
1
B
5
#
y
1
y
3
y
5
{
v
2
,
v
3
,
v
5
}
#
A
1
1
B
1
A
2
0
B
2
A
3
1
B
3
A
4
1
B
4
A
5
0
B
5
#
y
2
y
3
y
5
{
v
3
,
v
4
,
v
5
}
#
A
1
1
B
1
A
2
0
B
2
A
3
1
B
3
A
4
0
B
4
A
5
1
B
5
#
y
3
y
4
y
5
{
v
1
,
v
2
,
v
3
,
v
5
}
#
A
1
1
B
1
A
2
0
B
2
A
3
0
B
3
A
4
1
B
4
A
5
1
B
5
#
y
1
y
2
y
3
y
5Table 5
DNA sequences chosen to represent the solution of the maximum weighted clique problem.
{
v
3
,
v
4
,
v
5
}
3′-TACCCTCAAACTCACCAATAT
C
T
A
A
A
T
T
A
A
T
T
C
A
A
T
A
T
C
A
A
C
A
A
T
C
T
T
T
A
C
G
G
G
G
G
G
G
G
G
G
G
G
G
G
G-5′


## 6. Conclusions

In this paper, we present a parallel computing algorithm to solve the maximum weighted clique problem based on biological operations. Due to the fact that DNA biological computing has some advantages including high parallelism, low energy consumption, and large memory capacity, comparing to electronic computers low speed and limited memory, the method of DNA computing has attracted more and more attention. Besides, compared with the previous algorithms, our proposed algorithm has the following features:(1) we utilize fixed length DNA strands to generate the solution strands of the problem, the algorithm actually has lower error rate in hybrid operations; (2) the time cost of algorithm and solution strands length increase in linear proportion with the expansion of instance scale. For an undirected simple n-vertex graph, the parallel biological computing algorithm executes in O(n2) time complexity for the maximum weighted clique problem, having lower computational complexity than previous algorithms in exponential level. Although operations in our paper are on the basis of a theoretical model, the capacity to executive complicated operations in algorithm could help us understand more about the nature of computing and promote the better and faster development of biocomputing, more conducive for us to solve complex practical engineering problems.



---

*Source: 275019-2015-06-23.xml*