Few methods exist for automated RNA motif discovery, due to the difficulty in predicting correct RNA structures and doing alignments where substantial computing costs are involved. This project will implement a new tool for motif discovery using algorithmically efficient alignment methods. The first thrust of the proposal is based on an extension of the loop model commonly used in RNA structure prediction. An extended model achieves better efficiency that current algorithms and allows a biologist to annotate conserved regions and incorporate these into the process, thereby obtaining more meaningful results. The second thrust applies the alignment algorithms to feature selection and motif discovery. This is an essential step in RNA mining, choosing a set of significant substructure from a set of molecules. The subset can be used alone or in combination with kernel methods to build new tools for RNA classification and clustering. The work will be validated and can advance interdisciplinary data mining and develop human resources by training graduate and undergraduate students. A new undergraduate course will also be developed, and selected materials also used for high school students.
