График гамильтонова пути с вычислением ДНК

Question

Недавно я нашел алгоритм «ДНК-вычисления» (не генетическое программирование или генетические алгоритмы), который пытается найти гамильтонов путь в графе, но я немного смущен псевдокодом ... обратите внимание, что обозначениенемного запутался, потому что я скопировал его из PDF-документа о ДНК-вычислениях :

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''

Псевдокод с улучшенными обозначениями и справочной информацией см. в статье ,Может ли кто-нибудь перевести его в лучше псевдокод?Я хочу попробовать этот алгоритм, но я не понимаю, что они делают с Mix -> Remove -> Remove затем Move (20n + 10) ... какие-нибудь подсказки?

PS Этот алгоритм O(n ^ 2), поэтому я подозреваю, что это может быть версия, похожая на уже существующий алгоритм.

Answer 1

Как предполагалось в некоторых комментариях, алгоритм предназначен для выполнения на пробирках, а не на кремнии.

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)

Здесь мы помещаем все последовательности ДНК в пробирку и запускаем полимеразную цепную реакцию. В PCR мы используем праймеры, которые представляют начальный и конечный узлы для нашего гамильтонова пути. Результатом будут цепочки ДНК, которые начинаются с последовательности начального узла, а затем идут до ребра-узла-края, пока не будет достигнут конечный узел.

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

Затем мы запускаем ДНК на геле и выбираем последовательность ДНК правильной длины. Это должен быть гамильтонов путь. Одна вещь, которая мне не совсем понятна, это то, как они предотвращают повторные посещения вершины, но думают, что это естественно из-за правильных концентраций, как описано выше.

Причина, по которой это интересно, состоит в том, что химия, по сути, выполняет эти вычисления параллельно. Все возможные пути проверены - поскольку все совместимые комбинации фрагментов ДНК созданы - но ПЦР и гель выбирают только тот, который представляет гамильтонов путь И это не то, что вы можете сделать на компьютере без экспоненциального времени.