DNA Solution of the Hitting Set Problem 전기컴퓨터공학부 문승현, 김진
What is a Hitting Set Problem? A kind of NP-Complete problem INSTANCE: Collection C of subsets of a finite set S, positive integer K≤|S|. QUESTION: Is there a subset S’ ⊆ S with |S’|≤K such that S’ contains at least one element from each subset in C? EX) –Instance: {A, B, C}, {B, C}, {B, D}, {D, E}, K=2 –Answer: {B, D}, {B, E}
DNA Representation 집합을 binary 로 표현 – 전체집합 S 의 원소 각각을 S1, S2, …, Sn 이라 하 면 있는 것을 1, 없는 것을 0 으로 나타냄 – 예 ) S={A, B, C, D, E} 인 경우 {B, D} = Use modified Lipton encoding exhaustive search 로 해를 찾아내기 위해서 전체집합의 모든 부분집합을 생성 –Use a kind of mix-and-split combinatorial synthesis technique
Algorithm 1. 전체집합 S 의 모든 부분집합을 만든다 2.1. 에서 만든 부분집합 중 입력의 각 원소를 하나 이상 포함하고 있는 것을 남기고, 나머지를 제거 한다. 입력이 {B, E} 라면 B, E 두 원소 중 적어도 하나는 갖는 집합만을 남기고, 나머지는 버림 3. 입력의 모든 집합에 대해서 2. 를 반복한다. 4. 마지막 단계에 이르면 hitting set 만 남는다. 이 중 에서 가장 짧은 것을 찾는다 에서 찾은 것의 길이가 K 보다 작은지 확인한다.
The computer
Computation process 1. 앞에서 보인 장치의 hot chamber 에 라이브러리 모듈을, cold chamber 에는 첫 번째 집합 모듈을 삽입하고 전기영 동을 시작한다. – 첫 번째 집합의 원소 중 하나라도 가지고 있는 library strand 는 capture layer 에서 잡힐 것이고 그렇지 않은 것들은 buffer reservoir 로 흘러나갈 것이다 2. 각 모듈을 제거하고 box 를 씻은 다음 새로운 버퍼로 채운 다. –hot chamber 에는 이전 단계의 cold chamber 에 있던 모듈을, cold chamber 에는 두 번째 집합 모듈을 삽입 3. 모든 집합에 대해서 Step 2 를 반복한다. – 마지막 단계의 종료시점까지 남아 있는 library strands 가 hitting set 이다. 다음 단계에서 이 중 짧은 것을 골라내야 한다.
Determination of the answer 가장 원소 수가 적은 library strand 를 해로 선택해야 한다. 1. 전기영동 (electrophoresis) 을 통해 마지막 단계까지 남은 것들을 길이 순으로 정렬 2. 가장 짧은 것을 골라내 PCR-amplify 를 한 다. 3. 이것의 sequence 를 분석하여 그 길이를 K 와 비교한다.
Simulation Result 옳은 해가 살아남을 확률과, 잘못된 해가 살 아남을 확률을 각각 살펴본다. 전체집합의 원소 개수가 20 개인 hitting set 에 대하여 –2250 개 중복된 입력에서 평균 70 개 정도가 살아 남는다. 이것은 PCR amplification 을 통해 쉽게 늘릴 수 있다. – 한 단계에서 잘못된 해가 남을 확률은 0.003% 정도인데 같은 과정을 20 회 반복하므로 최종단 계까지 남을 확률은 매우 적다.
Conclusion Adleman(2002) 의 방법을 Hitting Set Problem 에도 어렵지 않게 응용할 수 있다. 중간과정에서 에러가 나올 수 있으나 전체 과정으로 보면 충분히 해결 가능함 전체 집합 크기가 30 개인 경우까지 해결 가 능