title: RiboFSM: frequent subgraph mining for the discovery of RNA structures and interactions.
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.
authors.forename: Alex R
authors.initials: AR
authors.lastname: Gawronski
authors.forename: Marcel
authors.initials: M
authors.lastname: Turcotte
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D003196:Computer Graphics; D049469:Meiotic Prophase I / Q000235:genetics; D008958:Models, Molecular; D008969:Molecular Sequence Data; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry* / Q000145:classification / Q000378:metabolism; D017393:RNA Editing; D014346:Trypanosoma brucei brucei / Q000235:genetics*
chemical_list: D012313:RNA