Average complexity of the Jiang-Wang-Zhang pairwise tree alignment algorithm and of a RNA secondary structure alignment algorithm

Claire Herrbach 1 Alain Denise 2, 3, * Serge Dulucq 4
* Auteur correspondant
1 IGM - Institut de génétique et microbiologie [Orsay]
2 AMIB - Algorithms and Models for Integrative Biology
CNRS - Centre National de la Recherche Scientifique : UMR8623, X - École polytechnique, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
3 LRI - Laboratoire de Recherche en Informatique
4 LaBRI - Laboratoire Bordelais de Recherche en Informatique
Abstract : We prove that the average complexity of the pairwise ordered tree alignment algo- rithm of Jiang, Wang and Zhang is in O(nm), where n and m stand for the sizes of the two trees, respectively. We show that the same result holds for the aver- age complexity of pairwise comparison of RNA secondary structures, using a set of biologically relevant operations.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2010, 411, pp.2423-2432
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00541269
Contributeur : Mireille Regnier <>
Soumis le : mardi 30 novembre 2010 - 11:37:57
Dernière modification le : jeudi 17 mai 2018 - 12:52:03
Document(s) archivé(s) le : mardi 1 mars 2011 - 02:48:46

Fichier

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

Identifiants

  • HAL Id : inria-00541269, version 1

Collections

INRIA | LIX | LABRI | UNIV-BORDEAUX | X | PARISTECH | X-LIX | UMR8623 | I2BC | X-DEP-INFO

Citation

Claire Herrbach, Alain Denise, Serge Dulucq. Average complexity of the Jiang-Wang-Zhang pairwise tree alignment algorithm and of a RNA secondary structure alignment algorithm. Theoretical Computer Science, Elsevier, 2010, 411, pp.2423-2432. 〈inria-00541269〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

526

Téléchargements de fichiers

176

Contact


archive-ouverte@inria.fr