DNA computing algorithm for NP problems

Abstract

The numerical algorithm for DNA computing has been developed on the basis of the characteristics of the DNA molecules. Its use for the resolution of the current problems is getting common. It is capable of parallel processing and storing huge amount of da ta but it is difficult and costly to be implemented within the laboratory environment. In this study, Numerical DNA computing algorithm is implemented on non - polynomial problems (NP). NPs are known to be difficult problems with only a close solution rathe r than a definite one. The simulations conducted as part of this study have shown that NP problems can be solved more easily and quickly by the given numerical algorithm for DNA computing. The algorithm is developed upon the selection of travelling salesma n and knapsack problems and its performance has been verified by the results of matlab simulations.

DNA moleküllerinin özelliklerinden yararlanılarak geliştirilen sayısal DNA hesaplama algoritmasının son yıllarda günümüz problemlerinin çözümündeki kullanımı artmaktadır. Paralel işlem yapma ve büyük miktarda veri saklama özelliği bulunan DNA hesaplamanın laboratuar ortamında uygulanması zor ve pahalıdır. Bu çalışmada sayısal DNA hesaplama algoritması polinomal olmayan (NP) problemlere uygulanmıştır. NP problemler kesin çözümü olmayıp yaklaşık çözümü bulunabilen zor problem sınıfında yer alırlar. Bu çalışma daki yapılan simülasyonlarda NP problemlerin verilen sayısal DNA hesaplama algoritması ile daha kolay ve hızlı çözülebileceği gösterilmiştir. Bunun için gezgin satıcı ve sırt çantası problemi seçilerek geliştirilen DNA hesaplama algoritmasının performansı matlab’da alınan simülasyon sonuçları ile doğrulanmıştır.