A DNA Algorithm for Calculating the Maximum Flow of a Network

Sackmann, Andrea; Brown, Kristelle; Formanowicz, Piotr; Morgan, Kevin; Kalsheker, Noor; Garibaldi, Jon M.; Błażewicz, Jacek

doi:10.2478/fcds-2023-0021

Abstract

DNA computing is a highly interdisciplinary field which combines molecular operations with theoretical algorithm design. A number of algorithms have been demonstrated in DNA computing, but to date network flow problems have not been studied. We aim to provide an approach to calculate the value of the maximum flow in networks by encoding the mathematical problem in DNA molecules and by using molecular biology techniques to manipulate the DNA. We present results which demonstrate that the algorithm works for an example network problem.

This paper presents the first application of DNA computing to network-flow problems. The presented algorithm has a linear time complexity where the calculation itself is done in a constant number of steps.

References

Adleman, L., Molecular computation of solutions to combinatorial problems, Science 266, 1021–1024 (1994).
Search in Google Scholar Back to article
Ahuja, R. K., Magnanti, T. L., and Orlin, J. B., Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, Upper Saddle River, NJ, 1993.
Search in Google Scholar Back to article
Benenson, Y., DNA computes a square root, Nature Nanotechnology 6, 465–467 (2011).
Search in Google Scholar Back to article
Błażewicz, J., Formanowicz, P., Urbaniak, R., DNA Based Algorithms for Some Scheduling Problems, In: Raidl, G. et al. Applications of Evolutionary Computing. EvoWorkshops 2003. LNCS 2611, Springer, Berlin, Heidelberg, 673–683 (2003).
Search in Google Scholar Back to article
Braich, R. S., Chelyapov, N., Johnson, C., Rothemund, P. W. K., and Adleman, L., Solution of a 20-variable 3-SAT problem on a DNA compute, Science 296, 499–502 (2002).
Search in Google Scholar Back to article
Condon, A., Designed DNA molecules: principles and applications of molecular nanotechnology, Nat. Rev. Genet. 7, 565–575 (2006).
Search in Google Scholar Back to article
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C., Introduction to Algorithms (2nd edition). MIT Press, Cambridge/MA, 2001.
Search in Google Scholar Back to article
Darehmiraki M., A New Solution for Maximal Clique Problem based Sticker Model, BioSystems 95, 145–149 (2009).
Search in Google Scholar Back to article
Dodge, M., S. A. MirHassani, S. A., Hooshmand, F., Solving two-dimensional cutting stock problem via a DNA computing algorithm, Natural Computing 20, 145–159 (2021).
Search in Google Scholar Back to article
Eghdami, H., Darehmiraki, M., Application of DNA computing in graph theory, Artificial Intelligence Review 38, 223–235 (2012).
Search in Google Scholar Back to article
Elias, P., Feinstein, A., and Shannon, C. E., A note on the maximum flow through a network, IEEE Trans. Info. Theory. 2, 117–119 (1956).
Search in Google Scholar Back to article
Faulhammer, D., Cukras, A. R., Lipton, R. J., and Landweber, L. F., Molecular computation: RNA solutions to chess problems, Proc. of Natl. Acad. Sci. USA 97, 1385–1389 (2000).
Search in Google Scholar Back to article
Ford, L. R., Jr. and Fulkerson, D. R., Maximal flow through a network, Canad. J. Mathem. 8, 399–404 (1956).
Search in Google Scholar Back to article
Han, A. and Zhu, D., DNA encoding method of weight for Chinese postman problem, In Proc. of IEEE Congress on Evolutionary Computation, IEEE Press, pp. 681–686 (2006).
Search in Google Scholar Back to article
Ibrahim, Z., Towards solving weighted graph problems by direct-proportional length-based DNA computing, Research Report, IEEE Computational Intelligence Society (CIS) Walter J. Karplus Summer Research Grant (2004).
Search in Google Scholar Back to article
Jeng, D. J.-F., Kim, I., and Watada, J., Bio-soft computing with fixed-length DNA to a group control optimization problem, Soft Computing 12, 223–228 (2008).
Search in Google Scholar Back to article
Jungnickel, D., Graphs, Networks and Algorithms, Vol. 5 (2nd edition), Springer, Berlin (2005).
Search in Google Scholar Back to article
Lee, J. Y., Shin, S. Y., Augh, S. J., Park, T. H., and T., Z. B., Temperature gradient-based DNA computing for graph problems with weighted edges, In DNA8: 8th Intern Workshop on DNA Based Computers, LNCS 2568, Springer, London, pp. 73–84 (2003).
Search in Google Scholar Back to article
Lipton, R. J., DNA solution of hard computational problems, Science 268, 524–548 (1995).
Search in Google Scholar Back to article
Liu, Q., Wang, L., Frutos, A. G., Condon, A. E., Corn, R. M., and Smith, L. M., DNA computing on surfaces, Nature 403, 175–179 (2000).
Search in Google Scholar Back to article
Liu, Y., Xu, J., Pan, L., and Wang, S., DNA solution of a graph coloring problem, J. Chem. Inf. Comput. Sci. 42, 524–528 (2002).
Search in Google Scholar Back to article
Martínez-Pérez, I. M., Gong, Z., Ignatova, Z., and Zimmermann, K. H., Solving the maximum clique problem via DNA hairpin formation, Technical Report 06.3, Computer Engerneering Department TUHH, Germany (2006).
Search in Google Scholar Back to article
Nagy, N. and Akl, S. G., Aspects of biomolecular computing, Parallel. Proc. Lett. 17, 185–211 (2007).
Search in Google Scholar Back to article
Narayanan, A. and Zorbalas, S., DNA algorithms for computing shortest paths In Proc. of Genetic Programming, 718–723 (1998).
Search in Google Scholar Back to article
Ouyang, Q., Kaplan, P. D., Liu, S., and Libchaber, A., DNA solution of the maximal clique problem, Science 278, 446–449 (1997).
Search in Google Scholar Back to article
Păun, G., Rozenberg, G., and Salomaa, A., DNA Computing: new computing paradigms. Springer, Berlin (1998).
Search in Google Scholar Back to article
Ran, T., Kaplan, S., Shapiro, E., Molecular implementation of simple logic programs, Nature Nanotechnology 4, 642–648 (2009).
Search in Google Scholar Back to article
Razzazi, M. and Roayaei, M., Using sticker model of DNA computing to solve domatic partition, kernel and induced path problems, Information Sciences 181, 3581–3600 (2011).
Search in Google Scholar Back to article
Ren, X., Wang, X., Wang, Z., Wu, T., Parallel DNA Algorithms of Generalized Traveling Salesman Problem-Based Bioinspired Computing Model, International Journal of Computational Intelligence Systems 14, 228–237 (2021).
Search in Google Scholar Back to article
Roweis, S., Winfree, E., Burgoyne, R., Chelyapov, N. V., Goodman, M. F., Rothemund, P. W. K., Adleman, L. M., A sticker-based model for DNA computation, Journal of Computational Biology 5, 615–629 (1998).
Search in Google Scholar Back to article
Sager, J. and Stefanovic, D., Designing nucleotide sequences for computation: A survey of constraints, In DNA11: 11th Intern Workshop on DNA Based Computers, LNCS 3892, Springer, London, pp. 275–289 (2006).
Search in Google Scholar Back to article
Sakamoto, K., Gouzu, H., Komiya, K., Kiga, D., Yokoyama, S., Yokomori, T., and Hagiya, M., Molecular computation by DNA hairpin formation, Science 288, 1223–1226 (2000).
Search in Google Scholar Back to article
Stojanovic, M. N. and Stefanovic, D., A deoxyribozyme-based molecular automaton, Nat. Biotechnol. 21, 1069–1074 (2003).
Search in Google Scholar Back to article
Tian, X., Liu, X., Zhang, H., Sun, M., Zhao, Y., A DNA algorithm for the job shop scheduling problem based on the Adleman-Lipton model, PLOS ONE 15, e0242083 (2020).
Search in Google Scholar Back to article
Woods, D., Doty, D., Myhrvold, C., Hui, J., Zhou, F., Yin, P., Winfree, E., Diverse and robust molecular algorithms using reprogrammable DNA self-assembly, Nature 567, 366-372 (2019).
Search in Google Scholar Back to article
Xu, J., Qiang, X., Zhang, K., Zhang, C., Yang, J., A DNA computing model for the graph vertex coloring problem based on a probe graph, Engineering 4, 61–77 (2018).
Search in Google Scholar Back to article
Yamamoto, M., Matsuura, N., Shiba, T., Kawazoe, Y., and Ohuchi, A., Solutions of shortest path problems by concentration control, In DNA7: 7th Intern Workshop on DNA Based Computers, LNCS 2340, Springer, London, 203–212 (2002).
Search in Google Scholar Back to article
Yang, J., Yin, Z., Tang, Z., Huang, K., Cui, J., Yang, X., Search computing model for the knapsack problem based on DNA origami, Materials Express 9, 553–562 (2019).
Search in Google Scholar Back to article
Zimmermann, K.-H., Efficient DNA sticker algorithms for NP-complete graph problems, newblock Computer Physics Communications 144, 297–309 (2002).
Search in Google Scholar Back to article

A DNA Algorithm for Calculating the Maximum Flow of a Network

Abstract

Paradigm

My account