Abstract
The satisfiability problem (SAT) is one of the NP-complete problems in the fields of theoretical computer and artificial intelligence, is the core of NP-complete problems. Compared with traditional DNA self-assembly, DNA origami is a new method of DNA self-assembly. We first give a description and the status quo of study of the satisfiability problem, briefly introduce the principle of DNA origami, propose the computing model based on DNA origami to solve the satisfiability problem, and solve an instance with 3 variables, 3 clauses to illustrate the feasibility of the algorithm. The proposed model only uses gel electrophoresis to search the solution to the problem, which is the most reliable biological operation known to date, therefore the proposed model is feasible. At present, the reported results concerning using origami to solve the NP-complete problem is relatively few. Our method is a new attempt to solve the NP- complete problem using biological DNA molecules.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Neidell, N.S.: Amplitude variation with offset. Lead. Edge 5(3), 47–51 (1986)
Li, S.P.: AVO seismic parameter inversion method and its application. China University of Petroleum (2009). (in Chinese)
Chen, J.J.: Inversion method of the three AVO parameters. China University of Petroleum (2007). (in Chinese)
Wang, L.P.: Prestack AVO non-linear inversion of intelligent optimization algorithm. China University of Geosciences (2015). (in Chinese)
Berg, E.: Simple convergent genetic algorithm for inversion of multiparameter data. In: SEG Technical Program Expanded Abstracts 1993, pp. 1126–1128. Society of Exploration Geophysicists (1990)
Porsani, M.J.: A combined genetic and linear inversion algorithm for seismic waveform inversion. In: SEG Technical Program Expanded Abstracts 1993, pp. 692–695. Society of Exploration Geophysicists (1993)
Mallick, S.: Model-based inversion of amplitude-variations-with-offset data using a genetic algorithm. Geophysics 60(4), 939–954 (1995)
Priezzhev, I.I., Shmaryan, L.E., Bejarano, G.: Nonlinear multitrace seismic inversion using neural network and genetic algorithm. In: 3rd EAGE St. Petersburg International Conference and Exhibition on Geosciences-geosciences: From New Ideas to New Discoveries (2008)
Soupios, P., Akca, I., Mpogiatzis, P.: Applications of hybrid genetic algorithms in seismic tomography. J. Appl. Geophys. 75(3), 479–489 (2011)
Bai, J., Xu, Z., Xiao, Y., Xie, T.: Nonlinear hybrid optimization algorithm for seismic impedance inversion. In: Beijing International Geophysical Conference & Exposition 21–24, Beijing, China (2014)
Agarwal, A., Sain, K., Shalivahan, S.: Traveltime and constrained AVO inversion using FDR PSO. In: SEG Technical Program Expanded Abstracts 2016, pp. 577–581. Society of Exploration Geophysicists (2016)
Sun, S.Z.: PSO non-linear pre-stack inversion method and the application in reservoir prediction. In: SEG Technical Program Expanded Abstracts 2012, pp. 1–5. Society of Exploration Geophysicists (2012)
Sun, S.Z., Liu, L.: A numerical study on non-linear AVO inversion using chaotic quantum particle swarm optimization. J. Seismic Explor. 23(4), 379–392 (2014)
Zhou, Y., Nie, Z., Jia, Z.: An improved differential evolution algorithm for nonlinear inversion of earthquake dislocation. Geodesy Geodyn. 5(4), 49–56 (2014)
Gao, Z., Pan, Z., Gao, J.: Multimutation differential evolution algorithm and its application to seismic inversion. IEEE Trans. Geosci. Remote Sens. 54(6), 3626–3636 (2016)
Yin, X.Y., Kong, S.S., Zhang, F.C.: Prestack AVO inversion based on differential evolution algorithm. Oil Geophys. Prospect. 48(4), 591–596 (2013)
Wu, Q.H., Wang, L.P., Zhu, Z.X.: Research of pre-stack AVO elastic parameter inversion problem based on hybrid genetic algorithm. Cluster Comput. 20(4), 3173–3783 (2017)
Wu, Q., Zhu, Z.X., Yan, X.S.: Research on the parameter inversion problem of prestack seismic data based on improved differential evolution algorithm. Cluster Comput. 20(4), 2881–2890 (2017)
De Castro, L.N., Von Zuben, F.J.: Learning and optimization using the clonal selection principle. IEEE Trans. Evol. Comput. 6(3), 239–251 (2002)
Gong, M., Jiao, L., Zhang, L.: Baldwinian learning in clonal selection algorithm for optimization. Inf. Sci. 180(8), 1218–1236 (2010)
Feng, J., Jiao, L.C., Zhang, X.: Bag-of-visual-words based on clonal selection algorithm for SAR image classification. IEEE Geosci. Remote Sens. Lett. 8(4), 691–695 (2011)
Karoum, B., Elbenani, Y.B.: A clonal selection algorithm for the generalized cell formation problem considering machine reliability and alternative routings. Prod. Eng. 2017(15), 1–12 (2017)
Rao, B.S., Vaisakh, K.: Multi-objective adaptive clonal selection algorithm for solving optimal power flow problem with load uncertainty. Int. J. Bio-Inspired Comput. 8(2), 67 (2016)
Swain, R.K., Barisal, A.K., Hota, P.K.: Short-term hydrothermal scheduling using clonal selection algorithm. Int. J. Electr. Power Energy Syst. 33(3), 647–656 (2011)
Chitsaz, H., Amjady, N., Zareipour, H.: Wind power forecast using wavelet neural network trained by improved clonal selection algorithm. Energy Convers. Manage. 89, 588–598 (2015)
Sindhuja, L.S., Padmavathi, G.: Replica node detection using enhanced single Hop detection with clonal selection algorithm in mobile wireless sensor networks. Hindawi Publishing Corp (2016)
Acknowledgement
The author sincerely thanks for the encouragement and advice given by the DNA computing research group, and thanks Professor Yin for his guidance. This research is funded by the National Natural Science Foundation of China; 61672001, 61702008.
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
Yang, Z., Yin, Z., Cui, J., Yang, J. (2018). DNA Origami Based Computing Model for the Satisfiability Problem. In: Qiao, J., et al. Bio-inspired Computing: Theories and Applications. BIC-TA 2018. Communications in Computer and Information Science, vol 951. Springer, Singapore. https://doi.org/10.1007/978-981-13-2826-8_14
Download citation
DOI: https://doi.org/10.1007/978-981-13-2826-8_14
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-13-2825-1
Online ISBN: 978-981-13-2826-8
eBook Packages: Computer ScienceComputer Science (R0)