The prediction of secondary RNA folds from primary sequences continues to be an important area of research given the significance of RNA molecules in biological processes such as gene regulation. To facilitate this effort, graph models of secondary structure have been developed to quantify and thereby characterize the topological properties of the secondary folds. In this work we utilize a multigraph representation of a secondary RNA structure to examine the ability of the existing graph-theoretic descriptors to classify all possible topologies as either RNA-like or not RNA-like. We use more than one hundred descriptors and several different machine learning approaches, including nearest neighbor algorithms, one-class classifiers, and several clustering techniques. We predict that many more topologies will be identified as those representing RNA secondary structures than currently predicted in the RAG (RNA-As-Graphs) database. The results also suggest which descriptors and which algorithms are more informative in classifying and exploring secondary RNA structures. 1. Introduction The need for a more complete understanding of the structural characteristics of RNA is evidenced by the increasing awareness of the significance of RNA molecules in biological processes such as their role in gene regulatory networks which guide the overall expressions of genes. Consequently, the number of studies investigating the structure and function of RNA molecules continues to rise and the characterization of the structural properties of RNA remains a tremendous challenge in computational biology. RNA molecules are seemingly more sensitive to their environment and have greater degrees of backbone torsional freedom than proteins, resulting in even greater structural diversity [1]. Although the tertiary structure is of significant importance, it is much more difficult to predict than the tertiary structure of proteins. Advances in molecular modeling have resulted in accurate predictions of small RNAs. However, the structure prediction for large RNAs with complex topologies is beyond the reach of the current ab initio methods [2]. A coarse-grained model to refine tertiary RNA structure prediction was developed by Ding et al. [2] to produce useful candidate structures by integrating biochemical footprinting data with molecular dynamics. Although the focus is on tertiary folds, their method uses information about RNA base pairings from known secondary structures as a starting point. This, coupled with the understanding that the RNA folding mechanisms producing tertiary
References
[1]
S. C. Flores and R. B. Altman, “Turning limited experimental information into 3D models of RNA,” RNA, vol. 16, no. 9, pp. 1769–1778, 2010.
[2]
F. Ding, C. A. Lavender, and K. M. Weeks, “Three-dimensional RNA structure renement by hydroxyl radical probing,” Nature Methods, vol. 9, pp. 603–608, 2012.
[3]
M. Zuker, “Mfold web server for nucleic acid folding and hybridization prediction,” Nucleic Acids Research, vol. 31, no. 13, pp. 3406–3415, 2003.
[4]
I. L. Hofacker, “Vienna RNA secondary structure server,” Nucleic Acids Research, vol. 31, no. 13, pp. 3429–3431, 2003.
[5]
J. P. Abrahams, M. van den Berg, E. van Batenburg, and C. Pleij, “Prediction of RNA secondary structure, including pseudoknotting, by computer simulation,” Nucleic Acids Research, vol. 18, no. 10, pp. 3035–3044, 1990.
[6]
H. H. Gan, D. Fera, J. Zorn et al., “RAG: RNA-As-Graphs database—concepts, analysis, and features,” Bioinformatics, vol. 20, no. 8, pp. 1285–1291, 2004.
[7]
F. Harary and G. Prins, “The number of homeomorphically irreducible trees, and other species,” Acta Mathematica, vol. 101, no. 1-2, pp. 141–162, 1959.
[8]
D. R. Koessler, D. J. Knisley, J. Knisley, and T. Haynes, “A predictive model for secondary RNA structure using graph theory and a neural network,” BMC Bioinformatics, vol. 11, no. 6, article 21, 2010.
[9]
J. A. Izzo, N. Kim, S. Elmetwaly, and T. Schlick, “RAG: an update to the RNA-As-Graphs resource,” BMC Bioinformatics, vol. 12, article 219, 2011.
[10]
M. Guttman, I. Amit, M. Garber et al., “Chromatin signature reveals over a thousand highly conserved large non-coding RNAs in mammals,” Nature, vol. 458, no. 7235, pp. 223–227, 2009.
[11]
A. Rockney, predictive model which uses descriptors of RNA secondary structures derived from graph theory [M.S. thesis], East Tennessee State University, 2011, http://libraries.etsu.edu/record=b2339936~S1a.
[12]
A. Hagberg, A. Schult, and P. Swart, “Exploring network structure, dynamics, and function using NetworkX,” in Proceedings of the 7th Python in Science Conference (SciPy'08), G. Varoquaux, T. Vaught, and J. Millman, Eds., p. 1115, Pasadena, Calif, USA, August 2008.
[13]
M. E. Smoot, K. Ono, J. Ruscheinski, P. L. Wang, and T. Ideker, “Cytoscape 2.8: new features for data integration and network visualization,” Bioinformatics, vol. 27, no. 3, Article ID btq675, pp. 431–432, 2011.
[14]
O. Boehm, D. Hardoon, and L. Manevitz, “Classifying cognitive states of brain activity via one-class neural networks with feature selection by genetic algorithms,” International Journal of Machine Learning and Cybernetics, vol. 2, no. 3, pp. 125–134, 2011.
[15]
D. Tax and R. Duin, “Data domain description using support vectors,” in Proceedings of the European Symposium on Articial Neural Networks (ESANN'99), pp. 251–256, D-Facto Public, Brugge, Belgium, April 1999.
[16]
C. Elkan and K. Noto, “Learning classiers from only positive and unlabeled data,” in Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'08), pp. 213–220, ACM, New York, NY, USA, 2008.
[17]
Y. Karklin, R. F. Meraz, and S. R. Holbrook, “Classification of non-coding RNA using graph representations of secondary structure,” Pacific Symposium on Biocomputing, pp. 4–15, 2005.
[18]
D. Knisley and J. Knisley, “Predicting protein-protein interactions using graph invariants and a neural network,” Computational Biology and Chemistry, vol. 35, no. 2, pp. 108–113, 2011.
