The Evolutionary Search for an RNA Common-Structural Grammar
Jin-Wu Nam1, Je-Gun Joung2, Byoung-Tak Zhang
1jwnam@bi.snu.ac.kr, Graduate Program In Bioinformatics, Seoul National University; 2jgjoung@bi.snu.ac.kr, Graduate Program In Bioinformatics, Seoul National University
Genetic programming has been applied to learning programs automatically, reconstructing networks, and predicting protein secondary structures. We developed a system for learning an RNA common-structural grammar from RNA sequences using genetic programming.
Knowing the structure of RNA is necessary for understanding their in-vivo functions. The same kind of RNA has a low similarity in sequence but, a high similarity in structure. Consequently, the inference of common secondary structure is a crucial step in studying RNA structures and in identifying functional RNAs. However it is not easy to find a common-structural grammar of a certain RNA from the sequence set including various sequence variations. Our system may help predict the RNA structural grammar, representing common RNA structure and may also help identify novel RNA using the grammar from RNA database. We describe how the grammar can be evolved by genetic programming. Furthermore, we present a method for converting RNA structural grammars into function trees.
In this research, we suggest each common-structural grammar that is learned from tRNA and RNA pseudoknots sequences. We show the possibility of identifying novel RNAs which correspond to the common-structural grammar. Furthermore, we present an evaluation of the optimal solution which is the common-structural grammar.