A GRAPH-TOPOLOGICAL APPROACH TO RECOGNITION OF PATTERN AND SIMILARITYIN RNA SECONDARY STRUCTURES

Secondary and tertiary RNA structures play an important role in many b iological processes, Therefore the necessity arises to find similar hi gher-order structures for different but functionally homologous RNA se quences. We propose here a graph-topological approach to the problem, which shows two main features: (a) A simplified graph representation w hich allows the recognition of similarity of RNA secondary structures with the same branching look despite minor differences. This allows co mparison among foldings from different sequences, and ''pruning'' of t he secondary structures not shared by all the sequences since the earl y stages of the search. (b) The graph representation is encoded by the Randic topological index, and the search for the folding similarity i s reduced to checking the identity of single numbers. These characteri stics make this approach significantly different, less depending on em pirical criteria, and less computationally heavy then previous methods , where the folding consensus has been measured by an alignment proced ure or correlation of strings representing the secondary structures. S ome U2 snRNA and viroid sequences are studied by this approach, which is imbedded in our previous search method based on genetic algorithms.