The problem of finding the longest common subsequence (lcs) of a given set of sequences over an alphabet occurs in many interesting contexts, such as data compression and molecular biology, in order to measure the “similarity degree” among biological sequences. Since the problem is NP-complete in its decision version (i.e. does there exist a lcs of length at least k, for a given k?) even over fixed alphabet, polynomial algorithms which give approximate solutions have been proposed. Among them, Long Run (LR) is the only one with guaranteed constant performance ratio. In this paper, we give a new approximation algorithm for the longest common subsequence problem: the Expansion Algorithm (EA). First of all, we prove that the solution found by the Expansion Algorithm is always at least as good as the one found by LR. Then we report the results of an experimentation with two different groups of instances, which show that EA clearly outperforms Long Run in practice.

Bonizzoni, P., DELLA VEDOVA, G., Mauri, G. (2001). Experimenting an approximation algorithm for the LCS. DISCRETE APPLIED MATHEMATICS, 110(1), 13-24 [10.1016/S0166-218X(00)00300-0].

Experimenting an approximation algorithm for the LCS

BONIZZONI, PAOLA;DELLA VEDOVA, GIANLUCA;MAURI, GIANCARLO
2001

Abstract

The problem of finding the longest common subsequence (lcs) of a given set of sequences over an alphabet occurs in many interesting contexts, such as data compression and molecular biology, in order to measure the “similarity degree” among biological sequences. Since the problem is NP-complete in its decision version (i.e. does there exist a lcs of length at least k, for a given k?) even over fixed alphabet, polynomial algorithms which give approximate solutions have been proposed. Among them, Long Run (LR) is the only one with guaranteed constant performance ratio. In this paper, we give a new approximation algorithm for the longest common subsequence problem: the Expansion Algorithm (EA). First of all, we prove that the solution found by the Expansion Algorithm is always at least as good as the one found by LR. Then we report the results of an experimentation with two different groups of instances, which show that EA clearly outperforms Long Run in practice.
Articolo in rivista - Articolo scientifico
approximation algorithms; longest common subsequence
English
2001
110
1
13
24
none
Bonizzoni, P., DELLA VEDOVA, G., Mauri, G. (2001). Experimenting an approximation algorithm for the LCS. DISCRETE APPLIED MATHEMATICS, 110(1), 13-24 [10.1016/S0166-218X(00)00300-0].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/2542
Citazioni
  • Scopus 24
  • ???jsp.display-item.citation.isi??? 19
Social impact