RNA secondary structure comparison: exact analysis of the Zhang-Shasha tree edit algorithm

We are interested in RNA secondary structure comparison, using an approach which consists to represent these structures by labeled ordered trees. Following the problem considered, this tree representation can be rough (considering only the structural patterns), or refined until an exact coding of the structure is obtained. After some preliminary definitions and the description of the Zhang-Shasha (SIAM J. Comput. 18 (6) (1989) 1245) tree edit algorithm, which is on the one hand the reference when dealing with ordered labeled trees comparison, and on the other hand the starting point of our work, this article will present an exact analysis of its complexity. The purpose of this work is also to lead us to a better comprehension of the parameters of this algorithm, in order to be able to modify it more easily without changing its time complexity to take into account biological constraints that occur when comparing RNA secondary structures. (C) 2003 Published by Elsevier B.V.