The general form of 0-1 programming problem based on DNA computing

Presentation on theme: "The general form of 0-1 programming problem based on DNA computing"— Presentation transcript:

1 The general form of 0-1 programming problem based on DNA computing
ZhiXiang Y, Fengyue Z, Jin X., Biosystems Jun;70(1):73-8. Summarized by Wha-Jin Lee

2 Introduction(1/2) Adleman showed that DNA can be used to solve the directed Hamiltonian path problem. Lipton proposed DNA experiment to solve the SAT problem. Ouyang et al. presented a solution to the maximal clique problem. Parallelism allows DNA computers to solve larger, harder problems such as NP-complete problems. Adleman은 Hamiltonian path problem을 DNA를 이용해 풀었고 그 후 SAT problem과 maximal clique problem가 DNA를 이용해 풀 수 있다는 것을 보여주었다.

3 Introduction(2/2) We present the general form of the 0-1 programming problem was solved by fluorescence labeling techniques based on surface chemistry. 0-1 programming problem is an important in operation research and has very widespread application But the model of 0-1 programming problem based on DNA computing has never been studied. Problems A great amount of DNA in decoding DNA computing is inaccurate 이 논문에서는 0-1 programming problem을 DNA를 이용하여 풀었는데 Surface chemistry에 기반한 Fluorescence labeling을 이용하였다. 0-1 programming problem은 operation 연구분야에서 매우 중요하고 방대한 어플리케이션을 가지고 있어서 이문제를 푸는 것은 중요하다. 아직까지 DNA를 기반하여 연구한 내용은 보고되지 않아 이 논문에 의의가 있다. 하지만 아직까지 한계점이 있는데 많은 양의 DNA를 디코딩 해야하는 것과 DNA computing 전반적으로 나타나는 실험의 부정확성이다. 예를 들어 Hybridization이 잘못될 수 있고 DNA 2차구조에 영향을 받을 수 있고 실험이 정확하게 되지 않을 수 있다.

4 0-1 programming problem The general form of 0-1 programming problem :
a,b,c가 임의의 실수로 정해졌을 때 아래 식들의 조건을 만족시키며 윗 식의 결과가 최대 혹은 최소가 되는 x값을 찾는다. 이때 x는 0 또는 1의 값을 갖아야 한다.

5 Example of 0–1 programming problem
simple 0–1 programming problem example 다음은 간단한 0–1 programming problem의 예이다. 오른쪽의 식들을 모두 만족시키고 오른쪽 식의 결과가 최소가 되는 x,y,z를 찾는 것이 목표이다. x,y,z 는 0 또는 1의 값을 갖는다.

6 Method - decoding The first group represented variable x, y, z.
The second group represented variable (x = 1 if and only of = 0, such as y, z) The third group represented the complementary strand of the first group The fouth group represented the complementary strand of the second group.

7 Example 2) x+z<=1 1) x+y-z>=1 3) y+z<=1
Fig3. 주어진 문제에 따라서 가능한 답들을 모두 generation한다. Fig4. 첫번째 조건에서 +인 변수는 녹색으로 레이블링 하고 –변수는 파란색으로 레이블링 한 후 hybridization시킨다. Fig5. 1) x+y-z>=1 3) y+z<=1 Optimal solution : (1,0,0)

8 Method Step 1. Generate all possible combinations of variable 0 or 1 in the given problem. Step 2. Reject infeasible solutions according to constraint inequalities (reserved feasible solution). Step 3. Generate remaining solutions. Step 4. Repeat Steps 2 and 3. We can remove all infeasible solutions and obtain feasible solutions of the problem; then proceed Step 5. Step 5. By comparing to value of object function corresponding to every feasible solution, we can obtain an optimum solution. Step1. 주어진 문제에 모든 변수들의 가능한 조합을 만든다. 앞 예의 경우 x, y, z 세 개의 변수가 주어졌으니 각각 변수는 0과 1 의 값을 갖을 수 있고 2의 3승은 8의 조합이 가능하게 된다. Step2-4. 각각의 조건에 맞지 않은 솔루션은 제한다. Step5. 실행 가능한 조합 중에 최적화된 솔루션을 선택한다.

9 Result In order to solve a practical issue, there are still some problems that need further study in biologic technology. We adopt fluorescence marking technique and laser focus technique, and determine the solution by analyzing fluorescence, the method of which has some significant advantages such as low cost, low error, short operating time, reusable surface and imple experimental steps.