TY - JOUR
ID - 108035
TI - Parallelizing Assignment Problem with DNA Strands
JO - Iranian Journal of Biotechnology
JA - IJB
LA - en
SN - 1728-3043
AU - Khorsand, Babak
AU - Savadi, Abdorreza
AU - Naghibzadeh, Mahmoud
AD - Computer Engineering Department, Faculty of Engineering, Ferdowsi University of Mashhad, Mashhad, Iran.
AD - Computer Engineering Department, Faculty of Engineering, Ferdowsi University of Mashhad, Mashhad, Iran
Y1 - 2020
PY - 2020
VL - 18
IS - 1
SP - 73
EP - 78
KW - Adelman Lipton model
KW - assignment
KW - DNA algorithm
KW - DNA computing
KW - Molecular computation
DO - 10.30498/ijb.2020.195413.2547
N2 - Background: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. Objectives: 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. Material and Methods: Applying bio molecular operations of Adelman Lipton model, a novel parallel DNA algorithm have been proposed for solving the assignment problem. Results: The proposed algorithm can solve the problem in time complexity, and just O(n) initial DNA strand in comparison with initial sequence, which is used by the other methods. Conclusions: In this article, using DNA computing, we proposed a parallel DNA algorithm to solve the assignment problem in linear time.
UR - http://www.ijbiotech.com/article_108035.html
L1 - http://www.ijbiotech.com/article_108035_237f4606fc34bd8ff1877431d4a32cd7.pdf
ER -