Computing a longest common subsequence of two given sequences is a fundamental problem in several fields of computer science. While there exist dynamic programming algorithms that can solve the problem in polynomial-time, their running time is considered too high for some practical applications. In this contribution we propose a method for comparing two sequences that is based on (1) a combinatorial algorithm that computes a window constrained longest common subsequence and (2) a genetic algorithm. We present experiments on synthetic datasets that show that the method is able to return solutions close to the length of a longest compute common subsequence. Moreover, the method is faster than the dynamic programming algorithm for the longest common subsequence problem.

(2022). Sequence Classification via LCS . Retrieved from https://hdl.handle.net/10446/234191

Sequence Classification via LCS

Dondi, Riccardo
2022-01-01

Abstract

Computing a longest common subsequence of two given sequences is a fundamental problem in several fields of computer science. While there exist dynamic programming algorithms that can solve the problem in polynomial-time, their running time is considered too high for some practical applications. In this contribution we propose a method for comparing two sequences that is based on (1) a combinatorial algorithm that computes a window constrained longest common subsequence and (2) a genetic algorithm. We present experiments on synthetic datasets that show that the method is able to return solutions close to the length of a longest compute common subsequence. Moreover, the method is faster than the dynamic programming algorithm for the longest common subsequence problem.
File allegato/i alla scheda:
File Dimensione del file Formato  
IDT2022.pdf

Solo gestori di archivio

Versione: publisher's version - versione editoriale
Licenza: Licenza default Aisberg
Dimensione del file 162.08 kB
Formato Adobe PDF
162.08 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10446/234191
Citazioni
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact