{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:52:52Z","timestamp":1760143972552,"version":"build-2065373602"},"reference-count":54,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2024,3,11]],"date-time":"2024-03-11T00:00:00Z","timestamp":1710115200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100002347","name":"Federal Ministry of Education and Research of Germany","doi-asserted-by":"publisher","award":["ScaDS.AI","57616814"],"award-info":[{"award-number":["ScaDS.AI","57616814"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]},{"name":"German Federal Ministry of Education and Research BMBF","award":["ScaDS.AI","57616814"],"award-info":[{"award-number":["ScaDS.AI","57616814"]}]},{"name":"German Research Foundation within the program Open Access Publication Funding","award":["ScaDS.AI","57616814"],"award-info":[{"award-number":["ScaDS.AI","57616814"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The comparison of multiple (labeled) graphs with unrelated vertex sets is an important task in diverse areas of applications. Conceptually, it is often closely related to multiple sequence alignments since one aims to determine a correspondence, or more precisely, a multipartite matching between the vertex sets. There, the goal is to match vertices that are similar in terms of labels and local neighborhoods. Alignments of sequences and ordered forests, however, have a second aspect that does not seem to be considered for graph comparison, namely the idea that an alignment is a superobject from which the constituent input objects can be recovered faithfully as well-defined projections. Progressive alignment algorithms are based on the idea of computing multiple alignments as a pairwise alignment of the alignments of two disjoint subsets of the input objects. Our formal framework guarantees that alignments have compositional properties that make alignments of alignments well-defined. The various similarity-based graph matching constructions do not share this property and solve substantially different optimization problems. We demonstrate that optimal multiple graph alignments can be approximated well by means of progressive alignment schemes. The solution of the pairwise alignment problem is reduced formally to computing maximal common induced subgraphs. Similar to the ambiguities arising from consecutive indels, pairwise alignments of graph alignments require the consideration of ambiguous edges that may appear between alignment columns with complementary gap patterns. We report a simple reference implementation in Python\/NetworkX intended to serve as starting point for further developments. The computational feasibility of our approach is demonstrated on test sets of small graphs that mimimc in particular applications to molecular graphs.<\/jats:p>","DOI":"10.3390\/a17030116","type":"journal-article","created":{"date-parts":[[2024,3,11]],"date-time":"2024-03-11T08:56:41Z","timestamp":1710147401000},"page":"116","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Progressive Multiple Alignment of Graphs"],"prefix":"10.3390","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-2307-595X","authenticated-orcid":false,"given":"Marcos E.","family":"Gonz\u00e1lez Laffitte","sequence":"first","affiliation":[{"name":"Bioinformatics Group, Department of Computer Science, Interdisciplinary Center for Bioinformatics, Leipzig University, H\u00e4rtelstra\u00dfe 16-18, D-04107 Leipzig, Germany"},{"name":"Center for Scalable Data Analytics and Artificial Intelligence (ScaDS.AI), Leipzig University, D-04103 Leipzig, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5016-5191","authenticated-orcid":false,"given":"Peter F.","family":"Stadler","sequence":"additional","affiliation":[{"name":"Bioinformatics Group, Department of Computer Science, Interdisciplinary Center for Bioinformatics, Leipzig University, H\u00e4rtelstra\u00dfe 16-18, D-04107 Leipzig, Germany"},{"name":"Center for Scalable Data Analytics and Artificial Intelligence (ScaDS.AI), Leipzig University, D-04103 Leipzig, Germany"},{"name":"Max Planck Institute for Mathematics in the Sciences, Inselstra\u00dfe 22, D-04103 Leipzig, Germany"},{"name":"Department of Theoretical Chemistry, University of Vienna, W\u00e4hringerstra\u00dfe 17, A-1090 Vienna, Austria"},{"name":"Center for Non-Coding RNA in Technology and Health, University of Copenhagen, DK-1870 Fredriksberg, Denmark"},{"name":"Facultad de Ciencias, Universidad National de Colombia, Sede Bogot\u00e1, Bogot\u00e1 CO-111321, Colombia"},{"name":"Santa Fe Institute, 1399 Hyde Park Rd., Santa Fe, NM 87501, USA"}]}],"member":"1968","published-online":{"date-parts":[[2024,3,11]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Rosenberg, M.S. (2009). Sequence Alignment: Methods, Models, Concepts, and Strategies, University of California Press.","key":"ref_1","DOI":"10.1525\/9780520943742"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1009","DOI":"10.1093\/bib\/bbv099","article-title":"Multiple sequence alignment modeling: Methods and applications","volume":"17","author":"Chatzou","year":"2015","journal-title":"Brief. Bioinform."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/0304-3975(95)80029-9","article-title":"Alignment of trees\u2014An alternative to tree edit","volume":"143","author":"Jiang","year":"1995","journal-title":"Theor. Comput. Sci."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1109\/TCBB.2004.11","article-title":"Pure multiple RNA secondary structure alignments: A progressive profile approach","volume":"1","author":"Voss","year":"2004","journal-title":"Trans. Comput. Biol. Bioinform."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1007\/s11786-020-00496-8","article-title":"Compositional properties of alignments","volume":"15","author":"Berkemer","year":"2021","journal-title":"Math. Comput. Sci."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"14689","DOI":"10.1073\/pnas.0305199101","article-title":"Local graph alignment and motif search in biological networks","volume":"101","author":"Berg","year":"2004","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1341","DOI":"10.1098\/rsif.2010.0063","article-title":"Topological network alignment uncovers biological function and phylogeny","volume":"7","author":"Kuchaiev","year":"2010","journal-title":"J. R. Soc. Interface"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1330","DOI":"10.1109\/TCBB.2011.35","article-title":"SEGA: Semiglobal graph alignment for structure-based protein comparison","volume":"8","author":"Mernberger","year":"2011","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1109\/TCBB.2007.1024","article-title":"Multiple graph alignment for the structural analysis of protein active sites","volume":"4","author":"Weskamp","year":"2007","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"12763","DOI":"10.1073\/pnas.0806627105","article-title":"Global alignment of multiple protein interaction networks with application to functional orthology detection","volume":"105","author":"Singh","year":"2008","journal-title":"Proc. Natl. Acad. Sci. USA"},{"unstructured":"Krishnapuram, B., Shah, M., Smola, A., Aggarwal, C., and Shen, D. (2016, January 13\u201317). FINAL: Fast attributed network alignment. Proceedings of the KDD \u201916: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA.","key":"ref_11"},{"key":"ref_12","first-page":"726","article-title":"HashAlign: Hash-based alignment of multiple graphs","volume":"Volume 10939","author":"Phung","year":"2018","journal-title":"Proceedings of the Advances in Knowledge Discovery and Data Mining, PAKDD 2018, Melbourne, VIC, Australia, 3\u20136 June 2018"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/2435209.2435212","article-title":"Message-passing algorithms for sparse network alignment","volume":"7","author":"Bayati","year":"2013","journal-title":"ACM Trans. Knowl. Discov. Data"},{"doi-asserted-by":"crossref","unstructured":"Tang, J., Zhang, W., Li, J., Zhao, K., Tsung, F., and Li, J. (2023, January 3\u20137). Robust attributed graph alignment via joint structure learning and optimal transport. Proceedings of the IEEE 39th International Conference on Data Engineering (ICDE), Los Alamitos, CA, USA.","key":"ref_14","DOI":"10.1109\/ICDE55515.2023.00129"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1331","DOI":"10.1007\/s10618-017-0505-2","article-title":"Lagrangian relaxations for multiple network alignment","volume":"31","author":"Malmi","year":"2017","journal-title":"Data Min. Knowl. Discov."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/BF02603120","article-title":"Progressive sequence alignment as a prerequisite to correct phylogenetic trees","volume":"25","author":"Feng","year":"1987","journal-title":"J. Mol. Evol."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1089\/cmb.1994.1.337","article-title":"On the complexity of multiple sequence alignment","volume":"1","author":"Wang","year":"1994","journal-title":"J. Comput. Biol."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1089\/106652701753307511","article-title":"Computational complexity of multiple sequence alignment with SP-score","volume":"8","author":"Just","year":"2001","journal-title":"J. Comput. Biol."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1323","DOI":"10.1089\/cmb.2006.13.1323","article-title":"Settling the intractability of multiple alignment","volume":"13","author":"Elias","year":"2006","journal-title":"J. Comput. Biol."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"2110","DOI":"10.1093\/bioinformatics\/btp144","article-title":"Evolutionary construction of multiple graph alignments for the structural analysis of biomolecules","volume":"25","author":"Fober","year":"2009","journal-title":"Bioinformatics"},{"unstructured":"Heath, R.W., Quynh, N.X., and Lap, L.H. (2014, January 15\u201317). A novel ant based algorithm for multiple graph alignment. Proceedings of the International Conference on Advanced Technologies for Communications (ATC 2014), Hanoi, Vietnam.","key":"ref_21"},{"key":"ref_22","first-page":"1409","article-title":"A statistical method for evaluating systematic relationships","volume":"38","author":"Sokal","year":"1958","journal-title":"Univ. Kansas Sci. Bull."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1367","DOI":"10.1109\/TPAMI.2004.75","article-title":"A (sub)graph isomorphism algorithm for matching large graphs","volume":"26","author":"Cordella","year":"2004","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/j.dam.2018.02.018","article-title":"VF2++\u2014An improved subgraph isomorphism algorithm","volume":"242","author":"Madarasi","year":"2018","journal-title":"Discret. Appl. Math."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"696","DOI":"10.1016\/j.jda.2006.07.002","article-title":"Comparing similar ordered trees in linear-time","volume":"5","author":"Touzet","year":"2007","journal-title":"J. Discret. Algorithms"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"20200066","DOI":"10.1098\/rsfs.2020.0066","article-title":"Alignments of biomolecular contact maps","volume":"11","author":"Stadler","year":"2021","journal-title":"Interface Focus"},{"unstructured":"Morgenstern, B., Stoye, J., and Dress, A.W.M. (1999). Consistent Equivalence Relations: A Set-Theoretical Framework for Multiple Sequence Alignments, University of Bielefeld, FSPM.","key":"ref_27"},{"doi-asserted-by":"crossref","unstructured":"Altman, R.B., Dunker, A.K., Hunter, L., and Klein, T.E. (2008). Pacific Sympomsium on Biocomputing PSB\u201908, Stanford Univ.","key":"ref_28","DOI":"10.1142\/7628"},{"doi-asserted-by":"crossref","unstructured":"Zhan, Q., Ye, Y., Lam, T.W., Yiu, S.M., Wang, Y., and Ting, H.F. (2015). Improving multiple sequence alignment by using better guide trees. BMC Bioinform., 16.","key":"ref_29","DOI":"10.1186\/1471-2105-16-S5-S4"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"689","DOI":"10.1016\/S0167-8655(97)00060-3","article-title":"On a relation between graph edit distance and maximum common subgraph","volume":"18","author":"Bunke","year":"1997","journal-title":"Pattern Recognit. Lett."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"25","DOI":"10.14778\/1687627.1687631","article-title":"Comparing stars: On approximating graph edit distance","volume":"2","author":"Zeng","year":"2009","journal-title":"Proc. VLDB Endow."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"116095","DOI":"10.1016\/j.eswa.2021.116095","article-title":"Graph kernels based on linear patterns: Theoretical and experimental comparisons","volume":"189","author":"Jia","year":"2022","journal-title":"Expert Syst. Appl."},{"unstructured":"Leen, T., Dietterich, T., and Tresp, V. (2000, January 1). The kernel trick for distances. Proceedings of the NIPS\u201900: Proceedings of the 13th International Conference on Neural Information Processing Systems, Denver, CO, USA.","key":"ref_33"},{"unstructured":"Phillips, J.M., and Venkatasubramanian, S. (2011). A gentle introduction to the kernel distance. arXiv.","key":"ref_34"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1007\/s41109-019-0195-3","article-title":"A survey on graph kernels","volume":"5","author":"Kriege","year":"2020","journal-title":"Appl. Netw. Sci."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/j.patrec.2021.01.003","article-title":"Graphkit-learn: A python library for graph kernels based on linear patterns","volume":"143","author":"Jia","year":"2021","journal-title":"Pattern Recognit. Lett."},{"unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability. A Guide to the Theory of NP Completeness, Freeman.","key":"ref_37"},{"key":"ref_38","first-page":"375","article-title":"On the approximability of the maximum common subgraph problem","volume":"Volume 577","author":"Finkel","year":"1992","journal-title":"Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science; Cachan, France, 13\u201315 February 1992"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0020-0190(76)90049-1","article-title":"Subgraph isomorphism, matching relational structures and maximal cliques","volume":"4","author":"Barrow","year":"1976","journal-title":"Inf. Process. Lett."},{"unstructured":"Sierra, C. (2017, January 19\u201325). A partitioning algorithm for maximum common subgraph problems. Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, Melbourne, Australia.","key":"ref_40"},{"key":"ref_41","first-page":"3907","article-title":"Between subgraph isomorphism and maximum common subgraph","volume":"Volume 1","author":"Markovitch","year":"2017","journal-title":"Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence"},{"key":"ref_42","first-page":"4044","article-title":"Hybrid learning with new value function for the maximum common induced subgraph problem","volume":"Volume 4","author":"Williams","year":"2023","journal-title":"Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI-37)"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1101\/gr.1642804","article-title":"CONREAL: Conserved regulatory elements anchored alignment algorithm for identification of transcription factor binding sites by phylogenetic footprinting","volume":"14","author":"Berezikov","year":"2004","journal-title":"Genome Res."},{"doi-asserted-by":"crossref","unstructured":"Morgenstern, B., Prohaska, S.J., Pohler, D., and Stadler, P.F. (2006). Multiple sequence alignment with user-defined anchor points. Algorithms Mol. Biol., 1.","key":"ref_44","DOI":"10.1186\/1748-7188-1-6"},{"unstructured":"Brun, L., Ga\u00fcz\u00e8re, B., and Fourey, S. (2012). Relationships between Graph Edit Distance and Maximal Common Unlabeled Subgraph, HAL.","key":"ref_45"},{"unstructured":"Varoquaux, G., Vaught, T., and Millman, J. (2008, January 19\u201324). Exploring network structure, dynamics, and function using NetworkX. Proceedings of the 7th Python in Science Conference, Pasadena, CA, USA.","key":"ref_46"},{"unstructured":"Gonz\u00e1lez-Laffitte, M.E., and Stadler, P.F. (2024, February 23). Github Repository of the Progressive Graph Alignment Software ProGrAlign. Available online: https:\/\/github.com\/MarcosLaffitte\/Progralign.","key":"ref_47"},{"unstructured":"(2024, March 01). Documentation on the Pickle Python Package. Available online: https:\/\/docs.python.org\/3\/library\/pickle.html.","key":"ref_48"},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1109\/MCSE.2007.55","article-title":"Matplotlib: A 2D graphics environment","volume":"9","author":"Hunter","year":"2007","journal-title":"Comput. Sci. Eng."},{"key":"ref_50","first-page":"111","article-title":"Consensus sequence zen","volume":"1","author":"Schneider","year":"2002","journal-title":"Appl. Bioinform."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1093\/bioinformatics\/btab601","article-title":"indelPost: Harmonizing ambiguities in simple and complex indel alignments","volume":"38","author":"Hagiwara","year":"2022","journal-title":"Bioinformatics"},{"doi-asserted-by":"crossref","unstructured":"Giancarlo, R., and Sankoff, D. (2000). Proceedings of the Combinatorial Pattern Matching. CPM\u201900, Montreal, QC, Canada, 21\u201323 June 2000, Springer.","key":"ref_52","DOI":"10.1007\/3-540-45123-4"},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"1408","DOI":"10.1093\/bioinformatics\/bti159","article-title":"Evaluation of iterative alignment algorithms for multiple alignment","volume":"21","author":"Wallace","year":"2005","journal-title":"Bioinformatics"},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1089\/cmb.2006.13.309","article-title":"A polynomial time solvable formulation of multiple sequence alignment","volume":"13","author":"Sze","year":"2006","journal-title":"J. Comput. Biol."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/3\/116\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T14:11:59Z","timestamp":1760105519000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/3\/116"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,11]]},"references-count":54,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2024,3]]}},"alternative-id":["a17030116"],"URL":"https:\/\/doi.org\/10.3390\/a17030116","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2024,3,11]]}}}