A DNA Algorithm for Calculating the Maximum Flow of a Network

• Autorzy: Sackmann Andrea , Brown Kristelle , Formanowicz Piotr , Morgan Kevin , Kalsheker Noor , Garibaldi Jon M. , Blażewicz Jacek

Identyfikatory

DOI

10.2478/fcds-2023-0021

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

DNA computing; network problems; max-flow; min-cut

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2023
• Tom: Vol. 48, No. 4
• Strony: 483--506
• Opis fizyczny: Bibliogr. 39 poz., rys., tab.

Twórcy

autor

Sackmann Andrea

• School of Computer Science, University of Nottingham, Jubilee Campus, Wollaton Road, Nottingham, NG8 1BB, UK
• Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznań, Poland

autor

Brown Kristelle

• School of Molecular Medical Sciences, Queen’s Medical Centre, University of Nottingham, Nottingham, NG7 2UH, UK

autor

Formanowicz Piotr

• Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznań, Poland

autor

Morgan Kevin

• School of Molecular Medical Sciences, Queen’s Medical Centre, University of Nottingham, Nottingham, NG7 2UH, UK

autor

Kalsheker Noor

• School of Molecular Medical Sciences, Queen’s Medical Centre, University of Nottingham, Nottingham, NG7 2UH, UK

autor

Garibaldi Jon M.

• School of Computer Science, University of Nottingham, Jubilee Campus, Wollaton Road, Nottingham, NG8 1BB, UK

autor

Blażewicz Jacek

• Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznań, Poland; Institute of Bioorganic Chemistry, Polish Academy of Sciences, Noskowskiego 12/14, 61-704 Poznań, Poland
• European Centre for Bioinformatics and Genomics, Piotrowo 2, 60-965 Poznań, Poland

Bibliografia

• [1] Adleman, L., Molecular computation of solutions to combinatorial problems, Science 266, 1021-1024 (1994).
• [2] Ahuja, R. K., Magnanti, T. L., and Orlin, J. B., Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, Upper Saddle River, NJ, 1993.
• [3] Benenson, Y., DNA computes a square root, Nature Nanotechnology 6, 465-467 (2011).
• [4] 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).
• [5] 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).
• [6] Condon, A., Designed DNA molecules: principles and applications of molecular nanotechnology, Nat. Rev. Genet. 7, 565-575 (2006).
• [7] Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C., Introduction to Algorithms (2nd edition). MIT Press, Cambridge/MA, 2001.
• [8] Darehmiraki M., A New Solution for Maximal Clique Problem based Sticker Model, BioSystems 95, 145-149 (2009).
• [9] 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).
• [10] Eghdami, H., Darehmiraki, M., Application of DNA computing in graph theory, Artificial Intelligence Review 38, 223-235 (2012).
• [11] 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).
• [12] 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).
• [13] Ford, L. R., Jr. and Fulkerson, D. R., Maximal flow through a network, Canad. J. Mathem. 8, 399-404 (1956).
• [14] 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).
• [15] 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).
• [16] 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).
• [17] Jungnickel, D., Graphs, Networks and Algorithms, Vol. 5 (2nd edition), Springer, Berlin (2005).
• [18] 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).
• [19] Lipton, R. J., DNA solution of hard computational problems, Science 268, 524-548 (1995).
• [20] 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).
• [21] 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).
• [22] Mart´ınez-P´erez, I. M., Gong, Z., Ignatova, Z., and Zimmermann, K. H., Solving the maximum clique problem via DNA hairpin formation, Technical Report 06.3, Computer Engineering Department TUHH, Germany (2006).
• [23] Nagy, N. and Akl, S. G., Aspects of biomolecular computing, Parallel. Proc. Lett. 17, 185–211 (2007).
• [24] Narayanan, A. and Zorbalas, S., DNA algorithms for computing shortest paths In Proc. of Genetic Programming, 718-723 (1998).
• [25] Ouyang, Q., Kaplan, P. D., Liu, S., and Libchaber, A., DNA solution of the maximal clique problem, Science 278, 446-449 (1997).
• [26] Păun, G., Rozenberg, G., and Salomaa, A., DNA Computing: new computing paradigms. Springer, Berlin (1998).
• [27] Ran, T., Kaplan, S., Shapiro, E., Molecular implementation of simple logic programs, Nature Nanotechnology 4, 642-648 (2009).
• [28] 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).
• [29] 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).
• [30] 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).
• [31] 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).
• [32] 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).
• [33] Stojanovic, M. N. and Stefanovic, D., A deoxyribozyme-based molecular automaton, Nat. Biotechnol. 21, 1069-1074 (2003).
• [34] 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).
• [35] 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).
• [36] 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).
• [37] 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).
• [38] 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).
• [39] Zimmermann, K.-H., Efficient DNA sticker algorithms for NP-complete graph problems, newblock Computer Physics Communications 144, 297-309 (2002).

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).