Recognition of the folding consensus in RNA secondary structures by the topological-filtering method

A graph-topological approach to recognition of pattern and similarity in RNA secondary structures

Secondary and tertiary RNA structures play an important role in many biological processes. Therefore the necessity arises to find similar higher-order structures for different but functionally homologous RNA sequences. We propose here a graph-topological approach to the problem, which shows two main features: simplified graph representation which allows the recognition of similarity of RNA secondary structures with the same branching look despite minor differences. This allows comparison among foldings from different sequences, and "pruning" of the secondary structures not shared by all the sequences since the early stages of the search. (b) The graph representation is encoded by the Randić topological index, and the search for the folding similarity is reduced to checking the identity of single numbers. These characteristics make this approach significantly different, less depending on empirical criteria, and less computationally heavy then previous methods, where the folding consensus has been measured by an alignment procedure or correlation of strings representing the secondary structures. Some U2 snRNA and viroid sequences are studied by this approach, which is imbedded in our previous search method based on genetic algorithms.

A genetic algorithm to search for optimal and suboptimal RNA secondary structures

Genetic algorithms are a search method used in solving problems by selection, recombination and mutation of tentative solutions, until the better ones are achieved. They are very efficient when the 'building block' hypothesis is effective for the solutions, which means that a better solution can be obtained by assembling short 'motifs' or 'schemata' that can be retrieved in some other worse solutions. The additive nature of the secondary structure free energy rules suggests the validity of this hypothesis, and therefore the likely power of a genetic algorithm approach to search for RNA secondary structures. We describe in detail an original genetic algorithm specific for this problem. The sharing function used to obtain differentiated solutions is also described. It results in a greater effectiveness of the algorithm in retrieving a large number of suboptimal RNA foldings besides the optimal one. RNA sequences of different length are used to test the method. The PSTV viroid sequence has been studied.