Exploring Consensus RNA Substructural Patterns Using Subgraph Mining

Frequently recurring RNA structural motifs play important roles in RNA folding process and interaction with other molecules. Traditional index-based and shape-based schemas are useful in modeling RNA secondary structures but ignore the structural discrepancy of individual RNA family member. Further, the in-depth analysis of underlying substructure pattern is insufficient due to varied and unnormalized substructure data. This prevents us from understanding RNAs functions and their inherent synergistic regulation networks. This article thus proposes a novel labeled graph-based algorithm RnaGraph to uncover frequently RNA substructure patterns. Attribute data and graph data are combined to characterize diverse substructures and their correlations, respectively. Further, a top-k graph pattern mining algorithm is developed to extract interesting substructure motifs by integrating frequency and similarity. The experimental results show that our methods assist in not only modelling complex RNA secondary structures but also identifying hidden but interesting RNA substructure patterns.

1 Introduction

RNAs have been proved to implicate in diverse biological roles in coding, regulation, and expression of genes. Most studied sequences in human genome are protein-coding genes. However, these protein-coding sequences account for only a small fraction ($<$2 percent) of the genome and a large fraction (98 percent) of the transcriptome comprises non-coding RNA (ncRNAs). In recent years, there has been increasing evidence to indicate that the non-coding portion of the genome is of crucial functional importance: for normal development and physiology and for disease. For example, microRNAs (miRNAs) have been uncovered as key regulators of gene expression at the post-transcriptional level, and epigenetic and genetic defects in miRNAs and their processing machinery are a common hallmark of disease [31]. ncRNAs are emerging as key regulators of embryogenesis by controlling embryonic gene expression, ranging from miRNA induced degradation of mRNAs to long ncRNA-mediated modification of chromatin [30] .