Abstract
The algorithm of weightening serves as building blocks for the construction of more complex sticker algorithms. However, due to the previous weightening algorithms with single function, so the scope of solving problems is small. To this end, we propose three multifunctional weightening algorithms which running on the sticker machines. First, the basic operators of the algorithms consist of the pre-defined operations of the sticker model. Second, one can obtain the new algorithms by organizing these basic operations in a certain logical way. At last, running these new algorithms, we can obtain the corresponding functional results by reading the biochemical reaction products.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Adleman, L.M.: Molecular computation of solutions to combinatorial problems. Nature 369, 40 (1994)
Fan, Y.-K., Qiang, X.-L., Xu, J.: Sticker model for maximum clique problem and maximum independent set. Chin. J. Comput. 33(2), 305–310 (2010)
Lipton, R.J.: DNA solution of hard computational problems. Science 268(5210), 542–545 (1995)
Braich, R.S., Johnson, C., Rothemund, P.W.K., Hwang, D., Chelyapov, N., Adleman, L.M.: Solution of a satisfiability problem on a gel-based DNA computer. In: Condon, A., Rozenberg, G. (eds.) DNA 2000. LNCS, vol. 2054, pp. 27–42. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44992-2_3
Song, B.-S., Yin, Z.-X., Zhen, C., et al.: DNA self-assembly model for general satisfiability problem. J. Chin. Comput. Syst. 32(9), 1872–1875 (2011)
Pan, L., Jin, X., Liu, Y.: A surface-based DNA algorithm for the minimal vertex cover problem. Prog. Nat. Sci. Mater. Int. 13(1), 78–80 (2003)
Dond, Y.-F., Zhang, J.-X., Yin, Z.-X., et al.: An improved sticker model of the minimal covering problem. J. Electron. Inf. Technol. (4), 556–560 (2005)
Wu, F., Li, K., Sallam, A., et al.: A molecular solution for minimum vertex cover problem in tile assembly model. J. Supercomput. 66(1), 148–169 (2013)
Al Junid, S.A.M., Tahir, N.M., Majid, Z.A., et al.: Potential of graph theory algorithm approach for DNA sequence alignment and comparison. In: 2012 Third International Conference on Intelligent Systems, Modelling and Simulation (ISMS), pp. 187–190. IEEE (2012)
Wu, F., Li, K.-L.: An algorithm in tile assembly model for N queen problem. Acta Electron. Sin. 41(11), 2174–2180 (2013)
Xixu, W., Jing, L., Zhichao, S., et al.: A molecular computing model for maximum independent set based on origami and greedy algorithm. J. Comput. Theoret. Nanosci. 11(8), 1773–1778 (2014)
Zhou, K., Duan, Y., Dong, W., et al.: A matrix algorithm for maximum independent set problem based on sticker model. J. Comput. Theoret. Nanosci. 13(6), 3734–3743 (2016)
Zhou, X., Li, K.-L., Yue, G.-X., et al.: A volume molecular solution for the maximum matching problem on DNA-based computing. J. Comput. Res. Dev. 48(11), 2147–2154 (2011)
Wu, X., Song, C.-Y., Zhang, N., et al.: DNA algorithm for maximum matching problem based on sticker computation model. Comput. Sci. 40(12), 127–132 (2013)
Lee, J.Y., Shin, S.Y., Park, T.H., et al.: Solving traveling salesman problems with DNA molecules encoding numerical values. BioSystems 78(1–3), 39–47 (2004)
Dong, Y.F., Tan, G.J., Zhang, S.M.: Algorithm of TSP based on sticker systems of DNA computing. Acta Simulata Syst. Sin. 17(6), 1299–1387 (2005)
Kang, Z., Liu, W.B., Jin, X.U.: Algorithm of DNA computing of TSP. Syst. Eng. Electron. 29(2), 316–319 (2007)
Martínez-Pérez, I.M., Zimmermann, K.H.: Parallel bioinspired algorithms for NP complete graph problems. J. Parallel Distrib. Comput. 69(3), 221–229 (2009)
Roweis, S., Winfree, E., Burgoyne, R., et al.: A sticker-based model for DNA computation. J. Comput. Biol. 5(4), 615–629 (1998)
Ignatova, Z., Martínez-Pérez, I., Zimmermann, K.H.: DNA computing models. Springer, Boston (2008)
Hasudungan, R., Rohani, A.B., Rozlina, M.: DNA computing and its application on NP completeness problem. Asian Pac. J. Trop. Dis. (2013)
Acknowledgement
This work has been supported by NSFC under grant No. U1204608 and No. 61572444.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Zhang, C., Zhu, W., Zhou, Q. (2018). The Algorithms of Weightening Based on DNA Sticker Model. In: Zhou, Q., Miao, Q., Wang, H., Xie, W., Wang, Y., Lu, Z. (eds) Data Science. ICPCSEE 2018. Communications in Computer and Information Science, vol 902. Springer, Singapore. https://doi.org/10.1007/978-981-13-2206-8_22
Download citation
DOI: https://doi.org/10.1007/978-981-13-2206-8_22
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-13-2205-1
Online ISBN: 978-981-13-2206-8
eBook Packages: Computer ScienceComputer Science (R0)