nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

A\(^*\)-Based Compilation of Relaxed Decision Diagrams for the Longest Common Subsequence Problem

verfasst von : Matthias Horn, Günther R. Raidl

Erschienen in: Integration of Constraint Programming, Artificial Intelligence, and Operations Research

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We consider the longest common subsequence (LCS) problem and propose a new method for obtaining tight upper bounds on the solution length. Our method relies on the compilation of a relaxed multi-valued decision diagram (MDD) in a special way that is based on the principles of A\(^*\) search. An extensive experimental evaluation on several standard LCS benchmark instance sets shows that the novel construction algorithm clearly outperforms a traditional top-down construction (TDC) of MDDs. We are able to obtain stronger and at the same time more compact relaxed MDDs than TDC and this in shorter time. For several groups of benchmark instances new best known upper bounds are obtained. In comparison to existing simple upper bound procedures, the obtained bounds are on average 14.8% better.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Learning Variable Activity Initialisation for Lazy Clause Generation Solvers

Nächstes Kapitel Partitioning Students into Cohorts During COVID-19

Andersen, H.R., Hadzic, T., Hooker, J.N., Tiedemann, P.: A constraint store based on multivalued decision diagrams. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 118–132. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74970-7_11CrossRef

Beal, R., Afrin, T., Farheen, A., Adjeroh, D.: A new algorithm for “the LCS problem” with application in compressing genome resequencing data. BMC Genom. 17(4), 544 (2016). https://doi.org/10.1186/s12864-016-2793-0CrossRef

Bergman, D., Cire, A.A., van Hoeve, W.J., Hooker, J.N.: Discrete optimization with decision diagrams. INFORMS J. Comput. 28(1), 47–66 (2016)MathSciNetCrossRef

Bergman, D., Cire, A.A., von Hoeve, W.J., Hooker, J.N.: Optimization bounds from binary decision diagrams. INFORMS J. Comput. 26(2), 253–268 (2014)MathSciNetCrossRef

Bergman, D., Cire, A.A., van Hoeve, W.J., Hooker, J.N.: Decision Diagrams for Optimization. Artificial Intelligence: Foundations, Theory, and Algorithms. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-319-42849-9CrossRefMATH

Bergman, D., Cire, A.A., van Hoeve, W.-J., Yunes, T.: BDD-based heuristics for binary optimization. J. Heuristics 20(2), 211–234 (2014). https://doi.org/10.1007/s10732-014-9238-1CrossRef

Blum, C., Blesa, M.J.: Probabilistic beam search for the longest common subsequence problem. In: Stützle, T., Birattari, M., Hoos, H.H. (eds.) SLS 2007. LNCS, vol. 4638, pp. 150–161. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74446-7_11CrossRef

Blum, C., Blesa, M.J., López-Ibáñez, M.: Beam search for the longest common subsequence problem. Comput. Oper. Res. 36(12), 3178–3186 (2009)MathSciNetCrossRef

Blum, C., et al.: Solving longest common subsequence problems via a transformation to the maximum clique problem. Comput. Oper. Res. 125, 105089 (2021). https://doi.org/10.1016/j.cor.2020.105089MathSciNetCrossRefMATH

10.

Blum, C., Festa, P.: Longest common subsequence problems. In: Metaheuristics for String Problems in Bioinformatics, chap. 3, pp. 45–60. Wiley (2016)

11.

Bonizzoni, P., Della Vedova, G., Mauri, G.: Experimenting an approximation algorithm for the LCS. Discret. Appl. Math. 110(1), 13–24 (2001)MathSciNetCrossRef

12.

Brisk, P., Kaplan, A., Sarrafzadeh, M.: Area-efficient instruction set synthesis for reconfigurable system-on-chip designs. In: Proceedings of DAC 2004 - the 41st Annual Design Automation Conference, pp. 395–400. IEEE Press (2004)

13.

Chan, H.T., Yang, C.B., Peng, Y.H.: The generalized definitions of the two-dimensional largest common substructure problems. In: Proceedings of the 33rd Workshop on Combinatorial Mathematics and Computation Theory, pp. 1–12. National Taiwan University (2016)

14.

Cire, A.A., van Hoeve, W.J.: Multivalued decision diagrams for sequencing problems. Oper. Res. 61(6), 1411–1428 (2013)MathSciNetCrossRef

15.

Djukanovic, M., Raidl, G.R., Blum, C.: A beam search for the longest common subsequence problem guided by a novel approximate expected length calculation. In: Nicosia, G., Pardalos, P., Umeton, R., Giuffrida, G., Sciacca, V. (eds.) LOD 2019. LNCS, vol. 11943, pp. 154–167. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-37599-7_14CrossRef

16.

Djukanovic, M., Raidl, G.R., Blum, C.: Finding longest common subsequences: new anytime A* search results. Appl. Soft Comput. 95, 106499 (2020). https://doi.org/10.1016/j.asoc.2020.106499CrossRef

17.

Easton, T., Singireddy, A.: A large neighborhood search heuristic for the longest common subsequence problem. J. Heuristics 14(3), 271–283 (2008). https://doi.org/10.1007/s10732-007-9038-yCrossRefMATH

18.

Fraser, C.B.: Subsequences and supersequences of strings. Ph.D. thesis, University of Glasgow, UK (1995)

19.

Gusfield, D.: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)CrossRef

20.

Hart, P., Nilsson, N., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100–107 (1968)CrossRef

21.

Horn, M., Maschler, J., Raidl, G.R., Rönnberg, E.: A*-based construction of decision diagrams for a prize-collecting scheduling problem. Comput. Oper. Res. 126, 105125 (2021). https://doi.org/10.1016/j.cor.2020.105125MathSciNetCrossRefMATH

22.

Huang, K., Yang, C., Tseng, K.: Fast algorithms for finding the common subsequences of multiple sequences. In: Proceedings of the IEEE International Computer Symposium, pp. 1006–1011. IEEE Press (2004)

23.

Jiang, T., Lin, G., Ma, B., Zhang, K.: A general edit distance between RNA structures. J. Comput. Biol. 9(2), 371–388 (2002)CrossRef

24.

Kinable, J., Cire, A.A., van Hoeve, W.J.: Hybrid optimization methods for time-dependent sequencing problems. Eur. J. Oper. Res. 259(3), 887–897 (2017)MathSciNetCrossRef

25.

Kruskal, J.B.: An overview of sequence comparison: time warps, string edits, and macromolecules. SIAM Rev. 25(2), 201–237 (1983)MathSciNetCrossRef

26.

Li, Y., Wang, Y., Zhang, Z., Wang, Y., Ma, D., Huang, J.: A novel fast and memory efficient parallel mlcs algorithm for long and large-scale sequences alignments. In: 2016 IEEE 32nd International Conference on Data Engineering (ICDE), pp. 1170–1181. IEEE Press (2016)

27.

Maier, D.: The complexity of some problems on subsequences and supersequences. J. ACM 25(2), 322–336 (1978)MathSciNetCrossRef

28.

Peng, Z., Wang, Y.: A novel efficient graph model for the multiple longest common subsequences (MLCS) problem. Front. Genet. 8, 104 (2017)CrossRef

29.

Shyu, S.J., Tsai, C.Y.: Finding the longest common subsequence for multiple biological sequences by ant colony optimization. Comput. Oper. Res. 36(1), 73–91 (2009)MathSciNetCrossRef

30.

Smith, T., Waterman, M.: Identification of common molecular subsequences. J. Mol. Biol. 147(1), 195–197 (1981)CrossRef

31.

Wang, Q., Korkin, D., Shang, Y.: A fast multiple longest common subsequence (MLCS) algorithm. IEEE Trans. Knowl. Data Eng. 23(3), 321–334 (2011)CrossRef

Titel: A-Based Compilation of Relaxed Decision Diagrams for the Longest Common Subsequence Problem
verfasst von: Matthias Horn
Günther R. Raidl
Verlag: Springer International Publishing
Buch: Integration of Constraint Programming, Artificial Intelligence, and Operations Research
Print ISBN: 978-3-030-78229-0

Electronic ISBN: 978-3-030-78230-6

Copyright-Jahr: 2021
DOI: https://doi.org/10.1007/978-3-030-78230-6_5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner