How to compare arc-annotated sequences: The alignment hierarchy

Guillaume Blin 1, * Helene Touzet 2, 3
* Corresponding author
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.
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/inria-00178671
Contributor : Helene Touzet <>
Submitted on : Monday, November 21, 2011 - 3:27:50 PM
Last modification on : Monday, September 30, 2019 - 3:36:03 PM
Long-term archiving on: Wednesday, February 22, 2012 - 2:20:06 AM

File

hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00178671, version 1

Citation

Guillaume Blin, Helene Touzet. How to compare arc-annotated sequences: The alignment hierarchy. 13th String Processing and Information Retrieval, Oct 2006, Glasgow, United Kingdom. pp.291-303. ⟨inria-00178671⟩

Share

Metrics

Record views

549

Files downloads

388