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 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 : Friday, April 12, 2019 - 10:18:03 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

579

Files downloads

217