HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

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
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
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.
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/inria-00541269
Contributor : Mireille Regnier Connect in order to contact the contributor
Submitted on : Tuesday, November 30, 2010 - 11:37:57 AM
Last modification on : Saturday, January 8, 2022 - 3:46:02 AM
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

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⟩

Share

Metrics

Record views

290

Files downloads

132