{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T02:40:54Z","timestamp":1767840054915,"version":"3.49.0"},"reference-count":63,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,12,28]],"date-time":"2020-12-28T00:00:00Z","timestamp":1609113600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,12,28]],"date-time":"2020-12-28T00:00:00Z","timestamp":1609113600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100008678","name":"Universit\u00e4t Leipzig","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008678","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math.Comput.Sci."],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Alignments, i.e., position-wise comparisons of two or more strings or ordered lists are of utmost practical importance in computational biology and a host of other fields, including historical linguistics and emerging areas of research in the Digital Humanities. The problem is well-known to be computationally hard as soon as the number of input strings is not bounded. Due to its practical importance, a huge number of heuristics have been devised, which have proved very successful in a wide range of applications. Alignments nevertheless have received hardly any attention as formal, mathematical structures. Here, we focus on the compositional aspects of alignments, which underlie most algorithmic approaches to computing alignments. We also show that the concepts naturally generalize to finite partially ordered sets and partial maps between them that in some sense preserve the partial orders. As a consequence of this discussion we observe that alignments of even more general structure, in particular graphs, are essentially characterized by the fact that the restriction of alignments to a row must coincide with the corresponding input graphs. Pairwise alignments of graphs are therefore determined completely by common induced subgraphs. In this setting alignments of alignments are well-defined, and alignments can be decomposed recursively into subalignments. This provides a general framework within which different classes of alignment algorithms can be explored for objects very different from sequences and other totally ordered data structures.\n<\/jats:p>","DOI":"10.1007\/s11786-020-00496-8","type":"journal-article","created":{"date-parts":[[2020,12,28]],"date-time":"2020-12-28T13:02:47Z","timestamp":1609160567000},"page":"609-630","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Compositional Properties of Alignments"],"prefix":"10.1007","volume":"15","author":[{"given":"Sarah J.","family":"Berkemer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"H\u00f6ner zu Siederdissen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter F.","family":"Stadler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,12,28]]},"reference":[{"key":"496_CR1","first-page":"1488","volume":"76","author":"T Akutsu","year":"1993","unstructured":"Akutsu, T.: A polynomial time algorithm for finding a largest common subgraph of almost trees of bounded degree. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 76, 1488\u20131493 (1993)","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"496_CR2","doi-asserted-by":"crossref","first-page":"3389","DOI":"10.1093\/nar\/25.17.3389","volume":"25","author":"SF Altschul","year":"1997","unstructured":"Altschul, S.F., Madden, T.L., Sch\u00e4ffer, A.A., Zhang, J., Zhang, Z., Miller, W., Lipman, D.J.: Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nucleic Acids Res. 25, 3389\u20133402 (1997)","journal-title":"Nucleic Acids Res."},{"issue":"157","key":"496_CR3","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1016\/j.biosystems.2017.03.003","volume":"156","author":"S Baichoo","year":"2017","unstructured":"Baichoo, S., Ouzounis, C.A.: Computational complexity of algorithms for sequence comparison, short-read assembly and genome alignment. Biosystems 156(157), 72\u201385 (2017)","journal-title":"Biosystems"},{"key":"496_CR4","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0020-0190(76)90049-1","volume":"4","author":"HG Barrow","year":"1976","unstructured":"Barrow, H.G., Burstall, R.M.: Subgraph isomorphism, matching relational structures and maximal cliques. Inf. Process. Lett. 4, 83\u201384 (1976)","journal-title":"Inf. Process. Lett."},{"key":"496_CR5","doi-asserted-by":"crossref","first-page":"135","DOI":"10.3390\/a10040135","volume":"10","author":"SJ Berkemer","year":"2017","unstructured":"Berkemer, S.J., Siederdissen, C.H., Stadler, P.F.: Algebraic dynamic programming on trees. Algorithms 10, 135 (2017)","journal-title":"Algorithms"},{"key":"496_CR6","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1093\/jole\/lzy004","volume":"3","author":"T Bhattacharya","year":"2018","unstructured":"Bhattacharya, T., Blasi, D., Croft, W., Cysouw, M., Hruschka, D., Maddieson, I., M\u00fcller, L., Retzlaff, N., Smith, E., Stadler, P.F., Starostin, G., Youn, H.: Studying language evolution in the age of big data. J. Lang. Evol. 3, 94\u2013129 (2018)","journal-title":"J. Lang. Evol."},{"key":"496_CR7","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/S0304-3975(99)00324-2","volume":"259","author":"P Bonizzoni","year":"2001","unstructured":"Bonizzoni, P., Vedova, G.D.: The complexity of multiple sequence alignment with SP-score that is a metric. Theor. Comput. Sci. 259, 63\u201379 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"496_CR8","doi-asserted-by":"crossref","first-page":"689","DOI":"10.1016\/S0167-8655(97)00060-3","volume":"18","author":"H Bunke","year":"1997","unstructured":"Bunke, H.: On a relation between graph edit distance and maximum common subgraph. Pattern Recognit. Lett. 18, 689\u2013694 (1997)","journal-title":"Pattern Recognit. Lett."},{"key":"496_CR9","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1137\/0148063","volume":"48","author":"H Carrillo","year":"1988","unstructured":"Carrillo, H., Lipman, D.: The multiple sequence alignment problem in biology. SIAM J. Appl. Math. 48, 1073\u20131082 (1988)","journal-title":"SIAM J. Appl. Math."},{"key":"496_CR10","doi-asserted-by":"crossref","unstructured":"Cysouw, M., Jung, H.: Cognate identification and alignment using practical orthographies. In: Proceedings of Ninth Meeting of the ACL Special Interest Group in Computational Morphology and Phonology, pp. 109\u2013116. Association for Computational Linguistics (2007)","DOI":"10.3115\/1626516.1626530"},{"key":"496_CR11","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1101\/gr.2821705","volume":"15","author":"CB Do","year":"2005","unstructured":"Do, C.B., Mahabhashyam, M.S.P., Brudno, M., Batzoglou, S.: ProbCons: probabilistic consistency-based multiple sequence alignment. Genome Res. 15, 330\u2013340 (2005)","journal-title":"Genome Res."},{"key":"496_CR12","doi-asserted-by":"crossref","first-page":"588","DOI":"10.1002\/cmdc.201700482","volume":"13","author":"E Duesbury","year":"2018","unstructured":"Duesbury, E., Holliday, J., Willett, P.: Comparison of maximum common subgraph isomorphism algorithms for the alignment of 2D chemical structures. ChemMedChem 13, 588\u2013598 (2018)","journal-title":"ChemMedChem"},{"key":"496_CR13","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids","author":"R Durbin","year":"1998","unstructured":"Durbin, R., Eddy, S.R., Krogh, A., Mitchison, G.: Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, Cambridge (1998)"},{"key":"496_CR14","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1016\/j.sbi.2006.04.004","volume":"16","author":"RC Edgar","year":"2006","unstructured":"Edgar, R.C., Batzoglou, S.: Multiple sequence alignment. Curr. Opin. Struct. Biol. 16, 368\u2013373 (2006)","journal-title":"Curr. Opin. Struct. Biol."},{"key":"496_CR15","doi-asserted-by":"crossref","first-page":"1792","DOI":"10.1093\/nar\/gkh340","volume":"32","author":"RC Edgar","year":"2004","unstructured":"Edgar, R.C.: MUSCLE: multiple sequence alignment with high accuracy and high throughput. Nucleic Acids Res. 32, 1792\u20131797 (2004)","journal-title":"Nucleic Acids Res."},{"key":"496_CR16","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1002\/wcms.5","volume":"1","author":"H-C Ehrlich","year":"2011","unstructured":"Ehrlich, H.-C., Rarey, M.: Maximum common subgraph isomorphism algorithms and their applications in molecular science: a review. Wiley Interdiscip. Rev. Comput. Mol. Sci. 1, 68\u201379 (2011)","journal-title":"Wiley Interdiscip. Rev. Comput. Mol. Sci."},{"key":"496_CR17","doi-asserted-by":"crossref","first-page":"1323","DOI":"10.1089\/cmb.2006.13.1323","volume":"13","author":"I Elias","year":"2006","unstructured":"Elias, I.: Settling the intractability of multiple alignment. J. Comput. Biol. 13, 1323\u20131339 (2006)","journal-title":"J. Comput. Biol."},{"issue":"347","key":"496_CR18","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1016\/j.ins.2016.01.074","volume":"346","author":"F Emmert-Streib","year":"2016","unstructured":"Emmert-Streib, F., Dehmer, M., Shi, Y.: Fifty years of graph matching, network alignment and network comparison. Inf. Sci. 346(347), 180\u2013197 (2016)","journal-title":"Inf. Sci."},{"key":"496_CR19","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1137\/S0895480102412856","volume":"17","author":"R Fagin","year":"2003","unstructured":"Fagin, R., Kumar, R., Sivakumar, D.: Comparing top-$$k$$ lists. SIAM J. Discrete Math. 17, 134\u2013160 (2003)","journal-title":"SIAM J. Discrete Math."},{"key":"496_CR20","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/BF02603120","volume":"25","author":"D-F Feng","year":"1987","unstructured":"Feng, D.-F., Doolittle, R.F.: Progressive sequence alignment as a prerequisite to correct phylogenetic trees. J. Mol. Evol. 25, 351\u2013360 (1987)","journal-title":"J. Mol. Evol."},{"key":"496_CR21","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Todinca, I., Villanger, Y.: Exact algorithm for the maximum induced planar subgraph problem. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) Proceedings of the 19th European conference on Algorithms, Volume 6942 of Lecture Notes Comp. Sci., pp. 287\u2013298. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-23719-5_25"},{"key":"496_CR22","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1016\/0022-2836(82)90398-9","volume":"162","author":"O Gotoh","year":"1982","unstructured":"Gotoh, O.: An improved algorithm for matching biological sequences. J. Mol. Biol. 162, 705\u2013708 (1982)","journal-title":"J. Mol. Biol."},{"key":"496_CR23","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/S0022-5193(86)80112-6","volume":"121","author":"O Gotoh","year":"1986","unstructured":"Gotoh, O.: Alignment of three biological sequences with an efficient traceback procedure. J. Theor. Biol. 121, 327\u2013337 (1986)","journal-title":"J. Theor. Biol."},{"key":"496_CR24","doi-asserted-by":"crossref","first-page":"1145","DOI":"10.1093\/bioinformatics\/btq102","volume":"26","author":"MG Grabherr","year":"2010","unstructured":"Grabherr, M.G., Russell, P., Meyer, M., Mauceli, E., Alf\u00f6ldi, J., Di Palma, F., Lindblad-Toh, K.: Genome-wide synteny through highly sensitive sequence alignment: Satsuma. Bioinformatics 26, 1145\u20131151 (2010)","journal-title":"Bioinformatics"},{"key":"496_CR25","doi-asserted-by":"crossref","first-page":"1546","DOI":"10.1093\/bioinformatics\/bth126","volume":"20","author":"C Grasso","year":"2004","unstructured":"Grasso, C., Lee, C.: Combining partial order alignment and progressive multiple sequence alignment increases alignment speed and scalability to very large alignment problems. Bioinformatics 20, 1546\u20131556 (2004)","journal-title":"Bioinformatics"},{"key":"496_CR26","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1109\/TCBB.2004.11","volume":"1","author":"M H\u00f6chsmann","year":"2004","unstructured":"H\u00f6chsmann, M., Voss, B., Giegerich, R.: Pure multiple RNA secondary structure alignments: a progressive profile approach. IEEE\/ACM Trans. Comput. Biol. Bioinf. 1, 53\u201362 (2004)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"key":"496_CR27","doi-asserted-by":"crossref","unstructured":"H\u00f6ner\u00a0zu Siederdissen, C.: Sneaking around concatMap: efficient combinators for dynamic programming. In: Thiemann, P., Findler, R. (eds.) Proceedings of the 17th ACM SIGPLAN International Conference on Functional Programming, pp. 215\u2013226. ACM, New York (2012)","DOI":"10.1145\/2398856.2364559"},{"key":"496_CR28","doi-asserted-by":"crossref","unstructured":"H\u00f6ner zu Siederdissen, C., Hofacker, I.L., Stadler, P.F. Product grammars for alignment and folding. IEEE\/ACM Trans. Comput. Biol. Bioinform. 12, 507\u2013519 (2015)","DOI":"10.1109\/TCBB.2014.2326155"},{"key":"496_CR29","doi-asserted-by":"crossref","unstructured":"H\u00f6ner zu Siederdissen, C., Prohaska, S.J., Stadler, P.F.: Algebraic dynamic programming over general data structures. BMC Bioinform. 16, S2 (2015)","DOI":"10.1186\/1471-2105-16-S19-S2"},{"key":"496_CR30","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/0304-3975(95)80029-9","volume":"143","author":"T Jiang","year":"1995","unstructured":"Jiang, T., Wang, L., Zhang, K.: Alignment of trees\u2014an alternative to tree edit. Theor. Comput. Sci. 143, 137\u2013148 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"496_CR31","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1089\/106652701753307511","volume":"8","author":"W Just","year":"2001","unstructured":"Just, W.: Computational complexity of multiple sequence alignment with SP-score. J. Comput. Biol. 8, 615\u2013623 (2001)","journal-title":"J. Comput. Biol."},{"key":"496_CR32","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1093\/nar\/gki198","volume":"33","author":"K Katoh","year":"2005","unstructured":"Katoh, K., Kuma, K., Toh, H., Miyata, T.: MAFFT version 5: improvement in accuracy of multiple sequence alignment. Nucleic Acids Res. 33, 511\u2013518 (2005)","journal-title":"Nucleic Acids Res."},{"key":"496_CR33","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1089\/cmb.2017.0264","volume":"26","author":"VNS Kavya","year":"2019","unstructured":"Kavya, V.N.S., Tayal, K., Srinivasan, R., Sivadasan, N.: Sequence alignment on directed graphs. J. Comput. Biol. 26, 53\u201367 (2019)","journal-title":"J. Comput. Biol."},{"key":"496_CR34","doi-asserted-by":"crossref","unstructured":"Kececioglu, J.D.: The maximum weight trace problem in multiple sequence alignment. In: Proceedings of the 4th Symposium on Combinatorial Pattern Matching, Volume 684 of Lecture Notes Comp. Sci., pp. 106\u2013119. Springer, Berlin (1993)","DOI":"10.1007\/BFb0029800"},{"key":"496_CR35","doi-asserted-by":"crossref","unstructured":"Kececioglu, J., Starrett, D.: Aligning alignments exactly. In: Bourne, P.E., Gusfield, D. (eds.) Proceedings of the 8th ACM Conference on Research in Computational Molecular Biology (RECOMB), pp. 85\u201396. ACM, New York, NY (2004)","DOI":"10.1145\/974614.974626"},{"key":"496_CR36","doi-asserted-by":"crossref","first-page":"719","DOI":"10.1142\/S0219720004000831","volume":"2","author":"AS Konagurthu","year":"2004","unstructured":"Konagurthu, A.S., Whisstock, J., Stuckey, P.J.: Progressive multiple alignment using sequence triplet optimization and three-residue exchange costs. J. Bioinform. Comput. Biol. 2, 719\u2013745 (2004)","journal-title":"J. Bioinform. Comput. Biol."},{"key":"496_CR37","unstructured":"Kondrak, G.: A new algorithm for the alignment of phonetic sequences. In: Proceedings of NAACL 2000 1st Meeting of the North American Chapter of the Association for Computational Linguistics, pp. 288\u2013295. Morgan Kaufmann Publishers Inc, San Francisco (2000)"},{"key":"496_CR38","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1186\/1471-2105-8-254","volume":"8","author":"M Kruspe","year":"2007","unstructured":"Kruspe, M., Stadler, P.F.: Progressive multiple sequence alignments from triplets. BMC Bioinform. 8, 254 (2007)","journal-title":"BMC Bioinform."},{"key":"496_CR39","doi-asserted-by":"crossref","first-page":"2947","DOI":"10.1093\/bioinformatics\/btm404","volume":"23","author":"MA Larkin","year":"2007","unstructured":"Larkin, M.A., Blackshields, G., Brown, N.P., Chenna, R., McGettigan, P.A., McWilliam, H., Valentin, F., Wallace, I.M., Wilm, A., Lopez, R., Thompson, J.D., Gibson, T.J., Higgins, D.G.: Clustal W and Clustal X version 2.0. Bioinformatics 23, 2947\u20132948 (2007)","journal-title":"Bioinformatics"},{"key":"496_CR40","doi-asserted-by":"crossref","first-page":"999","DOI":"10.1093\/bioinformatics\/btg109","volume":"19","author":"C Lee","year":"2003","unstructured":"Lee, C.: Generating consensus sequences from partial order multiple sequence alignment graphs. Bioinformatics 19, 999\u20131008 (2003)","journal-title":"Bioinformatics"},{"key":"496_CR41","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1093\/bioinformatics\/18.3.452","volume":"18","author":"C Lee","year":"2002","unstructured":"Lee, C., Grasso, C., Sharlow, M.F.: Multiple sequence alignment using partial order graphs. Bioinformatics 18, 452\u2013464 (2002)","journal-title":"Bioinformatics"},{"key":"496_CR42","doi-asserted-by":"crossref","first-page":"4412","DOI":"10.1073\/pnas.86.12.4412","volume":"86","author":"DJ Lipman","year":"1989","unstructured":"Lipman, D.J., Altschul, S.F., Kececioglu, J.D.: A tool for multiple sequence alignment. Proc. Natl. Acad. Sci. USA 86, 4412\u20134415 (1989)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"496_CR43","doi-asserted-by":"crossref","first-page":"e54422","DOI":"10.1371\/journal.pone.0054422","volume":"8","author":"K Malde","year":"2013","unstructured":"Malde, K., Furmanek, T.: Increasing sequence search sensitivity with transitive alignments. PloS One 8, e54422 (2013)","journal-title":"PloS One"},{"key":"496_CR44","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/S0304-3975(02)00439-5","volume":"296","author":"B Manthey","year":"2003","unstructured":"Manthey, B.: Non-approximability of weighted multiple sequence alignment. Theor. Comput. Sci. 296, 179\u2013192 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"496_CR45","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1089\/cmb.2009.0168","volume":"17","author":"M M\u00f6hl","year":"2010","unstructured":"M\u00f6hl, M., Will, S., Backofen, R.: Lifting prediction to alignment of RNA pseudoknots. J. Comput. Biol. 17, 429\u2013442 (2010)","journal-title":"J. Comput. Biol."},{"key":"496_CR46","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1093\/bioinformatics\/15.3.211","volume":"15","author":"B Morgenstern","year":"1999","unstructured":"Morgenstern, B.: DIALIGN 2: improvement of the segment-to-segment approach to multiple sequence alignment. Bioinformatics 15, 211\u2013218 (1999)","journal-title":"Bioinformatics"},{"key":"496_CR47","doi-asserted-by":"crossref","first-page":"12098","DOI":"10.1073\/pnas.93.22.12098","volume":"93","author":"B Morgenstern","year":"1996","unstructured":"Morgenstern, B., Dress, A., Werner, T.: Multiple DNA and protein sequence alignment based on segment-to-segment comparison. Proc. Natl. Acad. Sci. USA 93, 12098\u201312103 (1996)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"496_CR48","unstructured":"Morgenstern, B., Stoye, J., Dress, A.W.M.: Consistent equivalence relations: a set-theoretical framework for multiple sequence alignments. Technical report, University of Bielefeld, FSPM (1999)"},{"key":"496_CR49","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"SB Needleman","year":"1970","unstructured":"Needleman, S.B., Wunsch, C.D.: A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol. 48, 443\u2013453 (1970)","journal-title":"J. Mol. Biol."},{"key":"496_CR50","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1006\/jmbi.2000.4042","volume":"302","author":"C Notredame","year":"2000","unstructured":"Notredame, C., Higgins, D.G., Heringa, J.: T-coffee: a novel method for fast and accurate multiple sequence alignment. J. Mol. Biol. 302, 205\u2013217 (2000)","journal-title":"J. Mol. Biol."},{"key":"496_CR51","doi-asserted-by":"crossref","unstructured":"Otto, W., Stadler, P.F., Prohaska, S.J.: Phylogenetic footprinting and consistent sets of local aligments. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011, Volume 6661 of Lecture Notes in Computer Science, pp. 118\u2013131. Springer, Heidelberg (2011)","DOI":"10.1007\/978-3-642-21458-5_12"},{"key":"496_CR52","doi-asserted-by":"crossref","unstructured":"Rautiainen, M., Marschall, T.: Aligning sequences to general graphs in $$o(v + me)$$ time. Technical report, bioRxiv (2017)","DOI":"10.1101\/216127"},{"key":"496_CR53","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1023\/A:1021271615909","volume":"16","author":"J Raymond","year":"2002","unstructured":"Raymond, J., Willett, P.: Maximum common subgraph isomorphism algorithms for the matching of chemical structures. J. Comput. Aided Mol. Des. 16, 521\u2013533 (2002)","journal-title":"J. Comput. Aided Mol. Des."},{"key":"496_CR54","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/s11786-018-0338-4","volume":"12","author":"N Retzlaff","year":"2018","unstructured":"Retzlaff, N., Stadler, P.F.: Partially local multi-way alignments. Math. Comput. Sci. 12, 207\u2013234 (2018)","journal-title":"Math. Comput. Sci."},{"key":"496_CR55","volume-title":"Time Warps, String Edits and Macromolecules: The Theory and Practice of Sequence Comparison","year":"1983","unstructured":"Sankoff, D., Kruskal, J. (eds.): Time Warps, String Edits and Macromolecules: The Theory and Practice of Sequence Comparison. Addison-Wesley, London (1983)"},{"key":"496_CR56","doi-asserted-by":"crossref","first-page":"482","DOI":"10.1016\/0196-8858(81)90046-4","volume":"2","author":"TF Smith","year":"1981","unstructured":"Smith, T.F., Waterman, M.S.: Comparison of biosequences. Adv. Appl. Math. 2, 482\u2013489 (1981)","journal-title":"Adv. Appl. Math."},{"key":"496_CR57","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1163\/221058211X570358","volume":"1","author":"L Steiner","year":"2011","unstructured":"Steiner, L., Stadler, P.F., Cysouw, M.: A pipeline for computational historical linguistics. Lang. Dyn. Change 1, 89\u2013127 (2011)","journal-title":"Lang. Dyn. Change"},{"key":"496_CR58","first-page":"625","volume":"13","author":"J Stoye","year":"1997","unstructured":"Stoye, J., Moulton, V., Dress, A.W.M.: DCA: an efficient implementation of the divide-and-conquer approach to simultaneous multiple sequence alignment. Comput. Appl. Biosci. 13, 625\u2013626 (1997)","journal-title":"Comput. Appl. Biosci."},{"key":"496_CR59","doi-asserted-by":"crossref","first-page":"132","DOI":"10.13189\/lls.2017.050209","volume":"5","author":"J Tiepmar","year":"2017","unstructured":"Tiepmar, J., Heyer, G.: An overview of canonical text services. Linguist. Lit. Stud. 5, 132\u2013148 (2017)","journal-title":"Linguist. Lit. Stud."},{"key":"496_CR60","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1186\/s12864-016-2927-4","volume":"17","author":"CA Velandia-Huerto","year":"2016","unstructured":"Velandia-Huerto, C.A., Berkemer, S.J., Hoffmann, A., Retzlaff, N., Marroqu\u00edn, L.C.R., Rosales, M.H., Stadler, P.F., Berm\u00fadez-Santana, C.I.: Orthologs, turn-over, and remolding of tRNAs in primates and fruit flies. BMC Genomics 17, 617 (2016)","journal-title":"BMC Genomics"},{"key":"496_CR61","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1089\/cmb.1994.1.337","volume":"1","author":"L Wang","year":"1994","unstructured":"Wang, L., Jiang, T.: On the complexity of multiple sequence alignment. J. Comput. Biol. 1, 337\u2013348 (1994)","journal-title":"J. Comput. Biol."},{"key":"496_CR62","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1089\/cmb.1995.2.509","volume":"2","author":"HT Wareham","year":"1995","unstructured":"Wareham, H.T.: A simplified proof of the NP- and MAX SNP-hardness of multiple sequence tree alignment. J. Comput. Biol. 2, 509\u2013514 (1995)","journal-title":"J. Comput. Biol."},{"issue":"8","key":"496_CR63","first-page":"781","volume":"6","author":"JG Wolff","year":"2000","unstructured":"Wolff, J.G.: Syntax, parsing and production of natural language in a framework of information compression by multiple alignment, unification and search. J. Univ. Comput. Sci. 6(8), 781\u2013829 (2000)","journal-title":"J. Univ. Comput. Sci."}],"container-title":["Mathematics in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-020-00496-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11786-020-00496-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-020-00496-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,9]],"date-time":"2021-10-09T04:17:28Z","timestamp":1633753048000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11786-020-00496-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,28]]},"references-count":63,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["496"],"URL":"https:\/\/doi.org\/10.1007\/s11786-020-00496-8","relation":{},"ISSN":["1661-8270","1661-8289"],"issn-type":[{"value":"1661-8270","type":"print"},{"value":"1661-8289","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,28]]},"assertion":[{"value":"15 May 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 June 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 September 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 December 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}