DNA 계산을 이용한 그래프 해밀턴 경로

Question

그래프에서 해밀턴 경로를 찾으려고 시도하는 "DNA 컴퓨팅"알고리즘 (유전자 프로그래밍 또는 유전자 알고리즘 아님)이 최근에 발견되었지만 의사 코드로 인해 약간 혼란 스럽습니다. . 내가 그것을 from a PDF paper on DNA computing를 복사하기 때문에 표기가 엉망 조금 떨어져 있음을 알아 :

Input: for each node v and edge (u; v), 
    Tv contains Sv (and Sv) 
    T0uv contains Suv (and Suv) 
Mix(fTi; T0 uvg,T) 
Remove(T,T0,fSfg) 
Remove(T0,T0,fStg) 
Move length 20n+10 strings from T0 to T00 
if Detect(T0') 
then return ``Yes'' 
else return ``No'' 

더 나은 표기 및 배경 정보 please see the paper와 의사 코드의 경우. 누군가가 그것을 의사 코드로 더 잘 번역 할 수 있습니까? 이 알고리즘을 사용하고 싶지만 믹스 -> 제거 -> 제거 후 이동 (20n + 10) ... 힌트를 사용하여 수행중인 작업을 얻지 못합니다.

P. 이 알고리즘은 O (n^2)이므로 기존 알고리즘과 비슷한 버전 일 수 있습니다.

Answer 1

일부 의견에서 추측 되었 듯이 알고리즘은 실리콘이 아닌 테스트 튜브에서 수행됩니다.

Input: for each node v and edge (u; v), 
    Tv contains Sv (and Sv) 
    T0uv contains Suv (and Suv) 

그래서 우리는 그 노드를 표현하는 DNA 단편, 및 그래프의 각각의 에지에 대한 테스트 튜브를 포함하는, 그래프의 각 노드에 대한 시험관으로 초기화한다. 노드를 나타내는 DNA 서열은 무작위로 생성됩니다. 우리는 서로 어닐링 (스틱) 할 수 없기를 바랍니다. 가장자리를 나타내는 DNA 서열은 그들이 연결하는 노드의 DNA 서열과 겹치도록 설계된다. 즉 노드가 가장자리에 연결되어 있으면 노드 DNA가 가장자리 DNA에 붙을 것입니다. (이것은이 모든 기술을 작동시키는 핵심 포인트입니다.) DNA 서열은 증폭 될 필요가있다 (충분한 DNA를 가지며 DNA 농도는 동일한 두 노드 사이의 가장자리 수에 비례한다).

Mix(fTi; T0 uvg,T) 
Remove(T,T0,fSfg) 
Remove(T0,T0,fStg) 

여기에 우리는 우리가 우리의 해밀턴 경로의 시작과 끝의 노드를 표현 프라이머를 사용, 튜브의 DNA 서열을 모두 넣어, 그리고 PCR에서 Polymerase Chain Reaction. 를 실행합니다. 결과는 시작 노드 시퀀스로 시작하여 끝 노드에 도달 할 때까지 edge-node-edge로 이동하는 DNA 문자열입니다.

Move length 20n+10 strings from T0 to T00 
if Detect(T0') 
then return ``Yes'' 
else return ``No'' 

다음으로 run the DNA on a gel, 그리고 올바른 길이의 DNA 서열을 고른다. 이것은 해밀턴 경로 여야합니다. 나에게 완전히 명확하지 않은 한 가지는 꼭지점을 중복 방문하는 것을 방지하는 방법이지만 위에서 설명한 것처럼 올바른 농도를 갖는 것은 자연스럽게 발생한다고 생각합니다.

흥미로운 이유는 화학이 기본적으로 이러한 계산을 병렬로 실행하기 때문입니다. 가능한 모든 경로가 확인됩니다 - DNA 조각의 모든 호환 가능한 조합이 만들어 졌기 때문에 - 그러나 PCR과 젤은 해밀턴 경로를 나타내는 경로 만 선택합니다. 그리고 이것은 지수 적 시간없이 컴퓨터에서 할 수있는 것이 아닙니다.