How to compare arc-annotated sequences: The alignment hierarchy

Guillaume Blin 1, * Helene Touzet 2, 3
* Auteur correspondant
1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 LIFL - Laboratoire d'Informatique Fondamentale de Lille
3 SEQUOIA - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : We describe a new unifying framework to express comparison of arc-annotated sequences, which we call alignment of arc-annotated sequences. We first prove that this framework encompasses main existing models, which allows us to deduce complexity results for several cases from the literature. We also show that this framework gives rise to new relevant problems that have not been studied yet. We provide a thorough analysis of these novel cases by proposing two polynomial time algorithms and an NP-completeness proof. This leads to an almost exhaustive study of alignment of arc-annotated sequences.
Type de document :
Communication dans un congrès
Crestani Fabio and Ferragina Paolo and Sanderson Mark. 13th String Processing and Information Retrieval, Oct 2006, Glasgow, United Kingdom. Springer Verlag, 4209, pp.291-303, 2006, Lecture Notes in Computer Sciences
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00178671
Contributeur : Helene Touzet <>
Soumis le : lundi 21 novembre 2011 - 15:27:50
Dernière modification le : mercredi 11 avril 2018 - 12:12:03
Document(s) archivé(s) le : mercredi 22 février 2012 - 02:20:06

Fichier

hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00178671, version 1

Collections

INRIA | LIFL | ENPC | PARISTECH | ENPC-LIGM | LIGM_ALGO | LIGM | UNIV-MLV | UPEC-UPEM | UNIV-LILLE3

Citation

Guillaume Blin, Helene Touzet. How to compare arc-annotated sequences: The alignment hierarchy. Crestani Fabio and Ferragina Paolo and Sanderson Mark. 13th String Processing and Information Retrieval, Oct 2006, Glasgow, United Kingdom. Springer Verlag, 4209, pp.291-303, 2006, Lecture Notes in Computer Sciences. 〈inria-00178671〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

407

Téléchargements de fichiers

237

Contact


archive-ouverte@inria.fr