Ribofsm: Frequent Subgraph Mining For the Discovery of RNA Structures and Interactions

Peer reviewed: 
Yes, item is peer reviewed.
Scholarly level: 
Faculty/Staff
Final version published as: 

Gawronski and Turcotte
BMC Bioinformatics
2014,
15
(Suppl 13):S2
http://www.biomedcentral.com/1471-2105/15/S13/S2

Date created: 
2014
Keywords: 
RNA
Graph mining
Dual graphs
Abstract: 

Frequent subgraph mining is a useful method for extracting meaningful patterns from a set of graphs or a single large graph. Here, the graph represents all possible RNA structures and interactions. Patterns that are significantly more frequent in this graph over a random graph are extracted. We hypothesize that these patterns are most likely to represent biological mechanisms. The graph representation used is a directed dual graph, extended to handle intermolecular interactions. The graph is sampled for subgraphs, which are labeled using a canonical labeling method and counted. The resulting patterns are compared to those created from a randomized dataset and scored. The algorithm was applied to the mitochondrial genome of the kinetoplastid species Trypanosoma brucei, which has a unique RNA editing mechanism. The most significant patterns contain two stem-loops, indicative of gRNA, and represent interactions of these structures with target mRNA.

Language: 
English
Document type: 
Article
File(s): 
Statistics: