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
* Corresponding author
1 IGM - Institut de génétique et microbiologie [Orsay]
2 AMIB - Algorithms and Models for Integrative Biology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France
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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download
https://hal.inria.fr/inria-00541269
Contributor : Mireille Regnier <>
Submitted on : Tuesday, November 30, 2010 - 11:37:57 AM
Last modification on : Monday, December 9, 2019 - 5:24:07 PM
Long-term archiving on: Tuesday, March 1, 2011 - 2:48:46 AM

File

HeDeDuTCS.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00541269, version 1

Collections

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

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

618

Files downloads

301

 

 

Contact

archive-ouverte@inria.fr