A new algorithm for computing similarity between RNA structures

The primary structure of a ribonucleic acid (RNA) molecule is a sequence of nucleotides (bases) over the four-letter alphabet {A, C, G, U}. The second ary or tertiary structure of an RNA is a set of base-pairs (nucleotide pair s) which form bonds between A-U and C-G. For secondary structures, these bo nds have been traditionally assumed to be one-to-one and non-crossing. We c onsider the edit distance between two RNA structures. This is a notion of s imilarity, introduced in [Proceedings of the Tenth Symposium on Combinatori al Pattern Matching, Lecture Notes in Computer Science, vol. 1645, Springer , Berlin, 1999, p. 281], between two RNA molecule structures taking into ac count the primary, the secondary and the tertiary structures. In general th is problem is NP-hard for tertiary structures. In this paper, we consider t his notion under some constraints. We present an algorithm and then show ho w to use this algorithm for practical applications. (C) 2001 Elsevier Scien ce Inc. All rights reserved.