Khorsand Babak, Savadi Abdorreza, Naghibzadeh Mahmoud
Computer Engineering Department, Faculty of Engineering, Ferdowsi University of Mashhad, Mashhad, Iran.
Iran J Biotechnol. 2020 Jan 1;18(1):e2547. doi: 10.30498/IJB.2020.195413.2547. eCollection 2020 Jan.
Many problems of combinatorial optimization, which are solvable only in exponential time, are known to be Non-Deterministic Polynomial hard (NP-hard). With the advent of parallel machines, new opportunities have been emerged to develop the effective solutions for NP-hard problems. However, solving these problems in polynomial time needs massive parallel machines and is not applicable up to now.
DNA (Deoxyribonucleic acid) computing provides a fantastic method to solve NP-hard problems in polynomial time. Accordingly, one of the famous NP-hard problems is assignment problem, which is designed to find the best assignment of n jobs to n persons in a way that it could maximize the profit or minimize the cost.
Applying bio molecular operations of Adelman Lipton model, a novel parallel DNA algorithm have been proposed for solving the assignment problem.
The proposed algorithm can solve the problem in time complexity, and just O(n) initial DNA strand in comparison with nn initial sequence, which is used by the other methods.
In this article, using DNA computing, we proposed a parallel DNA algorithm to solve the assignment problem in linear time.
许多组合优化问题仅能在指数时间内求解，已知这些问题是NP难问题。随着并行机的出现，为NP难问题开发有效解决方案出现了新的机遇。然而，在多项式时间内解决这些问题需要大量并行机，目前尚不可行。
DNA（脱氧核糖核酸）计算为在多项式时间内解决NP难问题提供了一种奇妙的方法。因此，著名的NP难问题之一是指派问题，其旨在以能够使利润最大化或成本最小化的方式找到n项工作给n个人的最佳分配。
应用阿德尔曼-利普顿模型的生物分子操作，提出了一种用于解决指派问题的新型并行DNA算法。
所提出的算法能够在时间复杂度内解决该问题，与其他方法使用的nⁿ初始序列相比，仅需O(n)条初始DNA链。
在本文中，我们利用DNA计算提出了一种并行DNA算法，以在线性时间内解决指派问题。
