Practical lower and upper bounds for the Shortest Linear Superstring

Bastien Cazaux 1, 2 Samuel Juhel 1, 2 Eric Rivals 1, 2
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Given a set P of words, the Shortest Linear Superstring (SLS) problem is an optimization problem that asks for a superstring of $P$ of minimal length. SLS has applications in data compression, where a superstring is a compact representation of $P$, and in bioinformatics where it models the first step of genome assembly. Unfortunately SLS is hard to solve (NP-hard) and to closely approximate (MAX-SNP-hard). If numerous polynomial time approximation algorithms have been devised, few articles report on their practical performance. We lack knowledge about how closely an approximate superstring can be from an optimal one in practice. Here, we exhibit a linear time algorithm that reports an upper and a lower bound on the length of an optimal superstring. The upper bound is the length of a superstring. This algorithm can be used to evaluate beforehand whether one can get an approximate superstring whose length is close to the optimum for a given instance. Experimental results suggest that its approximation performance is orders of magnitude better than previously reported practical values. Moreover, the proposed algorithm remain efficient even on large instances and can serve to explore in practice the approximability of SLS.
Type de document :
Communication dans un congrès
Gianlorenzo D'Angelo. SEA: Symposium on Experimental Algorithms, Jun 2018, L'Aquilla, Italy. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 17th International Symposium on Experimental Algorithms, LIPIcs (103), pp.18:1--18:14, 2018, Leibniz International Proceedings in Informatics. 〈http://cs.gssi.it/sea2018〉. 〈10.4230/LIPIcs.SEA.2018.18〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01929399
Contributeur : Eric Rivals <>
Soumis le : mercredi 21 novembre 2018 - 10:48:40
Dernière modification le : vendredi 23 novembre 2018 - 01:20:02

Fichier

sls-bounds-sea-2018.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Collections

Citation

Bastien Cazaux, Samuel Juhel, Eric Rivals. Practical lower and upper bounds for the Shortest Linear Superstring. Gianlorenzo D'Angelo. SEA: Symposium on Experimental Algorithms, Jun 2018, L'Aquilla, Italy. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 17th International Symposium on Experimental Algorithms, LIPIcs (103), pp.18:1--18:14, 2018, Leibniz International Proceedings in Informatics. 〈http://cs.gssi.it/sea2018〉. 〈10.4230/LIPIcs.SEA.2018.18〉. 〈lirmm-01929399〉

Partager

Métriques

Consultations de la notice

63

Téléchargements de fichiers

4