Please use this identifier to cite or link to this item:
https://research.matf.bg.ac.rs/handle/123456789/686
Title: | Application of A <sup>∗</sup> to the Generalized Constrained Longest Common Subsequence Problem with Many Pattern Strings | Authors: | Djukanovic, Marko Matic, Dragan Blum, Christian Kartelj, Aleksandar |
Affiliations: | Informatics and Computer Science | Issue Date: | 1-Jan-2022 | Journal: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Abstract: | This paper considers the constrained longest common subsequence problem with an arbitrary set of input strings and an arbitrary set of pattern strings as input. The problem has applications, for example, in computational biology, serving as a measure of similarity among different molecules that are characterized by common putative structures. We develop an exact A ∗ search to solve it. Our A ∗ search is compared to the only existing competitor from the literature, an Automaton approach. The results show that A ∗ is very efficient for real-world benchmarks, finding provenly optimal solutions in run times that are an order of magnitude lower than the ones of the competitor. Even some of the large-scale real-world instances were solved to optimality by A ∗ search. |
URI: | https://research.matf.bg.ac.rs/handle/123456789/686 | ISBN: | 9783031092817 | ISSN: | 03029743 | DOI: | 10.1007/978-3-031-09282-4_5 |
Appears in Collections: | Research outputs |
Show full item record
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.