Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
Hamiltonian path problem solution using DNA computing. / Sergeenko, Anna; Yakunina, Maria; Granichin, Oleg.
в: Cybernetics and Physics, Том 9, № 1, 30.06.2020, стр. 69-74.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - Hamiltonian path problem solution using DNA computing
AU - Sergeenko, Anna
AU - Yakunina, Maria
AU - Granichin, Oleg
PY - 2020/6/30
Y1 - 2020/6/30
N2 - In this article we study DNA computing, a method which is based on working with DNA molecules in a lab-oratory. That approach is implemented in solving one of the most popular combinatorial problem — the Hamiltonian path problem. Related to recent improvements in the biophysics methods, which are needed for DNA computing, we propose to change some steps in the clas-sical algorithm to increase accuracy of this method. The branch-and-bound method, the most popular method which is realized on a computer, is also shown in this pa-per to compare its performance with the time consump-tion of DNA computing. The results of that compari-son prove that it becomes inefficient to use the branch-and-bound method from the counted number of vertices because of its exponentially growing complexity, while DNA computing works parallel and has linearly growing time consumption.
AB - In this article we study DNA computing, a method which is based on working with DNA molecules in a lab-oratory. That approach is implemented in solving one of the most popular combinatorial problem — the Hamiltonian path problem. Related to recent improvements in the biophysics methods, which are needed for DNA computing, we propose to change some steps in the clas-sical algorithm to increase accuracy of this method. The branch-and-bound method, the most popular method which is realized on a computer, is also shown in this pa-per to compare its performance with the time consump-tion of DNA computing. The results of that compari-son prove that it becomes inefficient to use the branch-and-bound method from the counted number of vertices because of its exponentially growing complexity, while DNA computing works parallel and has linearly growing time consumption.
KW - DNA
KW - Evolutionary computation
KW - Hamiltonian path
KW - Optimization
UR - http://www.scopus.com/inward/record.url?scp=85087357719&partnerID=8YFLogxK
UR - https://www.elibrary.ru/item.asp?id=43304164
M3 - Article
AN - SCOPUS:85087357719
VL - 9
SP - 69
EP - 74
JO - Cybernetics and Physics
JF - Cybernetics and Physics
SN - 2223-7038
IS - 1
ER -
ID: 60761380