Molecular solution to the optimal linear arrangement problem based on DNA computation期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

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

Authors:	Xingchang Liu Xiaofan Yang Yuan Yan Tang

Institution:	(1) College of Computer Science, Chongqing University, Chongqing, 400044, China;(2) Department of Logistical, Information Engineering, Logistical Engineering University, Chongqing, 400016, China

Abstract:	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 ³log₂ n) DNA operations on tubes of (nK + n + m + L + 1)-bits DNA strands, where $K = \left\lceil {\log_2 n} \right\rceil$ and $L = \left\lceil {\log _2 \left({nm} \right)} \right\rceil + 1$ . With the advance in molecular biology techniques, this algorithm may be of practical utility.

Keywords:	DNA computation DNA algorithm Adleman-Lipton-sticker model Optimal linear arrangement problem NP-hardness
本文献已被 SpringerLink 等数据库收录！