Molecular solution to the optimal linear arrangement problem based on DNA computation

摘要

Due to massive parallelism, enormous memory storage and very low energy consumption, biomolecular operations have been suggested to solve various NP-hard problems that are beyond the capability of the fastest known digital computer. The optimal linear arrangement (OLA) problem is a well-known NP-hard combinatorial optimization problem. Based on a DNA computational model, this paper describes a novel algorithm for the OLA problem, which is executed in O(n 3log₂ n) DNA operations on tubes of (nK + n + m + L + 1)-bits DNA strands, where K = é log₂ n ùK = leftlceil {log_2 n} rightrceil and L = é log₂ (nm ) ù + 1L = leftlceil {log _2 left({nm} right)} rightrceil + 1 . With the advance in molecular biology techniques, this algorithm may be of practical utility.