{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T03:25:48Z","timestamp":1780629948683,"version":"3.54.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2025,8,1]],"date-time":"2025-08-01T00:00:00Z","timestamp":1754006400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,8,1]],"date-time":"2025-08-01T00:00:00Z","timestamp":1754006400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004435","name":"Universidad de Navarra","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004435","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Min Knowl Disc"],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Process Mining is a computational discipline aimed at discovering, monitoring, and improving processes. In the business sector, it integrates artificial intelligence and data mining to uncover trends, patterns, and insights within classified data systems. The Trace Alignment algorithm is a key tool in this field, designed to detect anomalies and identify similarities in event sequences. However, most implementations rely on progressive alignment approaches, which are computationally expensive. This paper introduces a novel Trace Alignment implementation with significant theoretical enhancements. By incorporating advanced programming techniques and parallel computing, the algorithm achieves polynomial time complexity, a notable improvement over previous methods. Validation results confirm its efficiency and the alignment\u2019s high quality.<\/jats:p>","DOI":"10.1007\/s10618-025-01130-6","type":"journal-article","created":{"date-parts":[[2025,8,1]],"date-time":"2025-08-01T04:24:28Z","timestamp":1754022268000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Trace alignment algorithm optimization"],"prefix":"10.1007","volume":"39","author":[{"given":"Leandro","family":"Gonz\u00e1lez-Montesino","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Darian H.","family":"Grass-Boada","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,8,1]]},"reference":[{"key":"1130_CR1","doi-asserted-by":"crossref","unstructured":"Amdahl GM (1967) Validity of the single processor approach to achieving large scale computing capabilities. In: Proceedings of the 18\u201320 Apr 1967. Spring joint computer conference, pp 483\u2013485","DOI":"10.1145\/1465482.1465560"},{"key":"1130_CR2","doi-asserted-by":"crossref","unstructured":"Backurs A, Indyk P (2015) Edit distance cannot be computed in strongly subquadratic time (unless seth is false). In: Proceedings of the 47th annual ACM symposium on theory of computing, pp 51\u201358","DOI":"10.1145\/2746539.2746612"},{"key":"1130_CR3","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1093\/nar\/29.1.323","volume":"29","author":"A Bahr","year":"2001","unstructured":"Bahr A, Thompson JD, Thierry JC, Poch O (2001) Balibase (benchmark alignment database): enhancements for repeats, transmembrane sequences and circular permutations. Nucleic Acids Res 29:323\u2013326","journal-title":"Nucleic Acids Res"},{"key":"1130_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1748-7188-5-21","volume":"5","author":"G Blackshields","year":"2010","unstructured":"Blackshields G, Sievers F, Shi W, Wilm A, Higgins DG (2010) Sequence embedding for fast construction of guide trees for multiple sequence alignment. Algorithms Mol Biol 5:1\u201311","journal-title":"Algorithms Mol Biol"},{"key":"1130_CR5","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1023\/A:1020499411651","volume":"5","author":"A Bookstein","year":"2002","unstructured":"Bookstein A, Kulyukin VA, Raita T (2002) Generalized hamming distance. Inf Retrieval 5:353\u2013375","journal-title":"Inf Retrieval"},{"key":"1130_CR6","doi-asserted-by":"crossref","unstructured":"Bose RJC, van\u00a0der Aalst W (2010) Trace alignment in process mining: opportunities for process diagnostics. In: International conference on business process management. Springer, pp 227\u2013242","DOI":"10.1007\/978-3-642-15618-2_17"},{"key":"1130_CR7","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.is.2011.08.003","volume":"37","author":"R Bose","year":"2012","unstructured":"Bose R, van der Aalst WM (2012) Process diagnostics using trace alignment: opportunities, issues, and challenges. Inf Syst 37:117\u2013141","journal-title":"Inf Syst"},{"key":"1130_CR8","first-page":"27","volume":"7","author":"MF Camilo","year":"2016","unstructured":"Camilo MF, Su\u00e1rez EI, Pando HD (2016) Aceleraci\u00f3n del algoritmo \u201calineamiento de trazas\u2019\u2019 empleando cuda. Revista Cubana de Ingenier\u00eda 7:27\u201335","journal-title":"Revista Cubana de Ingenier\u00eda"},{"key":"1130_CR9","doi-asserted-by":"crossref","unstructured":"Camilo MF, Su\u00e1rez EI, Pando HD (2016b) Implementaci\u00f3n del algoritmo trace alignment empleando t\u00e9cnicas de programaci\u00f3n paralela. L\u00e1mpsakos, 11\u201321","DOI":"10.21501\/21454086.1722"},{"key":"1130_CR10","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1137\/0148063","volume":"48","author":"H Carrillo","year":"1988","unstructured":"Carrillo H, Lipman D (1988) The multiple sequence alignment problem in biology. SIAM J Appl Math 48:1073\u20131082","journal-title":"SIAM J Appl Math"},{"key":"1130_CR11","doi-asserted-by":"publisher","first-page":"1009","DOI":"10.1093\/bib\/bbv099","volume":"17","author":"M Chatzou","year":"2016","unstructured":"Chatzou M, Magis C, Chang JM, Kemena C, Bussotti G, Erb I, Notredame C (2016) Multiple sequence alignment modeling: methods and applications. Brief Bioinform 17:1009\u20131023","journal-title":"Brief Bioinform"},{"key":"1130_CR12","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1016\/j.ygeno.2017.06.007","volume":"109","author":"B Chowdhury","year":"2017","unstructured":"Chowdhury B, Garai G (2017) A review on multiple sequence alignment from the perspective of genetic algorithm. Genomics 109:419\u2013431","journal-title":"Genomics"},{"key":"1130_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s12859-016-0930-z","volume":"17","author":"J Daily","year":"2016","unstructured":"Daily J (2016) Parasail: SIMD c library for global, semi-global, and local pairwise sequence alignments. BMC Bioinformatics 17:1\u201311","journal-title":"BMC Bioinformatics"},{"key":"1130_CR14","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/S0092-8240(84)80027-0","volume":"46","author":"WH Day","year":"1984","unstructured":"Day WH (1984) Properties of levenshtein metrics on sequences. Bull Math Biol 46:327\u2013332","journal-title":"Bull Math Biol"},{"key":"1130_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1471-2105-9-11","volume":"9","author":"A D\u00f6ring","year":"2008","unstructured":"D\u00f6ring A, Weese D, Rausch T, Reinert K (2008) Seqan an efficient, generic c++ library for sequence analysis. BMC Bioinformatics 9:1\u20139","journal-title":"BMC Bioinformatics"},{"key":"1130_CR16","doi-asserted-by":"publisher","first-page":"1792","DOI":"10.1093\/nar\/gkh340","volume":"32","author":"RC Edgar","year":"2004","unstructured":"Edgar RC (2004) Muscle: multiple sequence alignment with high accuracy and high throughput. Nucleic Acids Res 32:1792\u20131797","journal-title":"Nucleic Acids Res"},{"key":"1130_CR17","doi-asserted-by":"crossref","unstructured":"Fakirah M, Shehab MA, Jararweh Y, Al-Ayyoub M (2015) Accelerating Needleman-Wunsch global alignment algorithm with GPUS. In: 2015 IEEE\/ACS 12th International Conference of Computer Systems and Applications (AICCSA). IEEE, pp 1\u20135","DOI":"10.1109\/AICCSA.2015.7507113"},{"key":"1130_CR18","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0065-227X(99)80007-0","volume":"36","author":"O Gotoh","year":"1999","unstructured":"Gotoh O (1999) Multiple sequence alignment: algorithms and applications. Adv Biophys 36:159\u2013206","journal-title":"Adv Biophys"},{"key":"1130_CR19","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/270563.571472","volume":"28","author":"D Gusfield","year":"1997","unstructured":"Gusfield D (1997) Algorithms on strings, trees, and sequences: computer science and computational biology. ACM SIGACT News 28:41\u201360","journal-title":"ACM SIGACT News"},{"key":"1130_CR20","doi-asserted-by":"crossref","unstructured":"Hayashida M, Koyano H (2016) Finding median and center strings for a probability distribution on a set of strings under Levenshtein distance based on integer linear programming. In: International joint conference on biomedical engineering systems and technologies. Springer, pp 108\u2013121","DOI":"10.1007\/978-3-319-54717-6_7"},{"key":"1130_CR21","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/S0020-0255(96)00174-0","volume":"97","author":"C Houstis","year":"1997","unstructured":"Houstis C, Kapidakis S, Markatos EP, Gelenbe E (1997) Execution of compute-intensive applications into parallel machines. Inf Sci 97:83\u2013124. https:\/\/doi.org\/10.1016\/S0020-0255(96)00174-0","journal-title":"Inf Sci"},{"key":"1130_CR22","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo R, Paturi R, Zane F (2001) Which problems have strongly exponential complexity? J Comput Syst Sci 63:512\u2013530","journal-title":"J Comput Syst Sci"},{"key":"1130_CR23","doi-asserted-by":"crossref","unstructured":"Jiang X, Fu X, Dong G, Li H (2017) Research on pairwise sequence alignment Needleman-Wunsch algorithm, In: 2017 5th International conference on mechatronics, materials, chemistry and computer engineering (ICMMCCE 2017). Atlantis Press, pp 1041\u20131046","DOI":"10.2991\/icmmcce-17.2017.187"},{"key":"1130_CR24","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0020-0255(81)90056-6","volume":"23","author":"R Kashyap","year":"1981","unstructured":"Kashyap R, Oommen B (1981) An effective algorithm for string correction using generalized edit distance\u2013ii. computational complexity of the algorithm and some applications. Inf Sci 23:201\u2013217. https:\/\/doi.org\/10.1016\/0020-0255(81)90056-6","journal-title":"Inf Sci"},{"key":"1130_CR25","doi-asserted-by":"publisher","first-page":"3059","DOI":"10.1093\/nar\/gkf436","volume":"30","author":"K Katoh","year":"2002","unstructured":"Katoh K, Misawa K, Kuma K, Miyata T (2002) Mafft: a novel method for rapid multiple sequence alignment based on fast Fourier transform. Nucleic Acids Res 30:3059\u20133066","journal-title":"Nucleic Acids Res"},{"key":"1130_CR26","doi-asserted-by":"publisher","first-page":"772","DOI":"10.1093\/molbev\/mst010","volume":"30","author":"K Katoh","year":"2013","unstructured":"Katoh K, Standley DM (2013) Mafft multiple sequence alignment software version 7: improvements in performance and usability. Mol Biol Evol 30:772\u2013780","journal-title":"Mol Biol Evol"},{"key":"1130_CR27","doi-asserted-by":"publisher","first-page":"858","DOI":"10.1093\/nar\/gkn1006","volume":"37","author":"T Lassmann","year":"2009","unstructured":"Lassmann T, Frings O, Sonnhammer EL (2009) Kalign2: high-performance multiple alignment of protein and nucleotide sequences allowing external features. Nucleic Acids Res 37:858\u2013865","journal-title":"Nucleic Acids Res"},{"key":"1130_CR28","doi-asserted-by":"publisher","unstructured":"Okonechnikov K, Golosova O, Fursov M, the UGENE Team (2012) Unipro ugene: a unified bioinformatics toolkit. Bioinformatics 28:1166\u20131167. https:\/\/doi.org\/10.1093\/bioinformatics\/bts091","DOI":"10.1093\/bioinformatics\/bts091"},{"key":"1130_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1471-2105-4-47","volume":"4","author":"G Raghava","year":"2003","unstructured":"Raghava G, Searle SM, Audley PC, Barber JD, Barton GJ (2003) Oxbench: a benchmark for evaluation of protein multiple sequence alignment accuracy. BMC Bioinformatics 4:1\u201323","journal-title":"BMC Bioinformatics"},{"key":"1130_CR30","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1002\/pro.3290","volume":"27","author":"F Sievers","year":"2018","unstructured":"Sievers F, Higgins DG (2018) Clustal omega for making accurate alignments of many protein sequences. Protein Sci 27:135\u2013145","journal-title":"Protein Sci"},{"key":"1130_CR31","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1038\/msb.2011.75","volume":"7","author":"F Sievers","year":"2011","unstructured":"Sievers F, Wilm A, Dineen D, Gibson TJ, Karplus K, Li W, Lopez R, McWilliam H, Remmert M, S\u00f6ding J et al (2011) Fast, scalable generation of high-quality protein multiple sequence alignments using clustal omega. Mol Syst Biol 7:539","journal-title":"Mol Syst Biol"},{"key":"1130_CR32","doi-asserted-by":"publisher","first-page":"1394","DOI":"10.1093\/bioinformatics\/btw753","volume":"33","author":"M \u0160o\u0161i\u0107","year":"2017","unstructured":"\u0160o\u0161i\u0107 M, \u0160iki\u0107 M (2017) Edlib: a c\/c++ library for fast, exact sequence alignment using edit distance. Bioinformatics 33:1394\u20131395","journal-title":"Bioinformatics"},{"key":"1130_CR33","doi-asserted-by":"publisher","first-page":"D203","DOI":"10.1093\/nar\/gkh027","volume":"32","author":"LA Stebbings","year":"2004","unstructured":"Stebbings LA, Mizuguchi K (2004) Homstrad: recent developments of the homologous protein structure alignment database. Nucleic Acids Res 32:D203\u2013D207","journal-title":"Nucleic Acids Res"},{"key":"1130_CR34","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.ins.2010.11.014","volume":"182","author":"J Sun","year":"2012","unstructured":"Sun J, Wu X, Fang W, Ding Y, Long H, Xu W (2012) Multiple sequence alignment using the hidden Markov model trained by an improved quantum-behaved particle swarm optimization. Inf Sci 182:93\u2013114. https:\/\/doi.org\/10.1016\/j.ins.2010.11.014","journal-title":"Inf Sci"},{"key":"1130_CR35","doi-asserted-by":"crossref","unstructured":"Van\u00a0Dongen BF, de\u00a0Medeiros AKA, Verbeek HM, Weijters A, van Der\u00a0Aalst WM (2005) The prom framework: a new era in process mining tool support. In: Applications and theory of petri nets 2005: 26th international conference, ICATPN 2005, Miami, USA, June 20\u201325, 2005. Proceedings 26, Springer, pp 444\u2013454","DOI":"10.1007\/11494744_25"},{"key":"1130_CR36","doi-asserted-by":"crossref","unstructured":"Zhou M, Yang S, Li X, Lv S, Chen S, Marsic I, Farneth RA, Burd RS (2017) Evaluation of trace alignment quality and its application in medical process mining. In: 2017 IEEE international conference on healthcare informatics (ICHI). IEEE, pp 258\u2013267","DOI":"10.1109\/ICHI.2017.57"},{"key":"1130_CR37","doi-asserted-by":"publisher","first-page":"2475","DOI":"10.1093\/bioinformatics\/btv177","volume":"31","author":"Q Zou","year":"2015","unstructured":"Zou Q, Hu Q, Guo M, Wang G (2015) Halign: fast multiple similar DNA\/RNA sequence alignment based on the centre star strategy. Bioinformatics 31:2475\u20132481","journal-title":"Bioinformatics"},{"key":"1130_CR38","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1016\/j.phpro.2012.05.069","volume":"33","author":"Q Zou","year":"2012","unstructured":"Zou Q, Shan X, Jiang Y (2012) A novel center star multiple sequence alignment algorithm based on affine gap penalty and k-band. Phys Procedia 33:322\u2013327","journal-title":"Phys Procedia"}],"container-title":["Data Mining and Knowledge Discovery"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-025-01130-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10618-025-01130-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-025-01130-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,12]],"date-time":"2025-09-12T10:30:23Z","timestamp":1757673023000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10618-025-01130-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,1]]},"references-count":38,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["1130"],"URL":"https:\/\/doi.org\/10.1007\/s10618-025-01130-6","relation":{},"ISSN":["1384-5810","1573-756X"],"issn-type":[{"value":"1384-5810","type":"print"},{"value":"1573-756X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,1]]},"assertion":[{"value":"9 June 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 July 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 August 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"59"}}