RiboFSM: Frequent Subgraph Mining for the Discovery of RNA Structures and Interactions

Overview

Journal BMC Bioinformatics

Publisher Biomed Central

Specialty Biology

Date 2014 Dec 2

PMID 25434643

Citations 3

Authors

Alex R Gawronski

Marcel Turcotte

Affiliations

Soon will be listed here.

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.

Citing Articles

Fuzzy RNA recognition by the Trypanosoma brucei editosome.

Leeder W, Geyer F, Goringer H Nucleic Acids Res. 2022; 50(10):5818-5833.

PMID: 35580050 PMC: 9178004. DOI: 10.1093/nar/gkac357.

Graph- and rule-based learning algorithms: a comprehensive review of their applications for cancer type classification and prognosis using genomic data.

Mallik S, Zhao Z Brief Bioinform. 2019; 21(2):368-394.

PMID: 30649169 PMC: 7373185. DOI: 10.1093/bib/bby120.

RiboFSM: frequent subgraph mining for the discovery of RNA structures and interactions.

Gawronski A, Turcotte M BMC Bioinformatics. 2014; 15 Suppl 13:S2.

PMID: 25434643 PMC: 4248650. DOI: 10.1186/1471-2105-15-S13-S2.

References

Zikova A, Kopecna J, Schumacher M, Stuart K, Trantirek L, Lukes J . Structure and function of the native and recombinant mitochondrial MRP1/MRP2 complex from Trypanosoma brucei. Int J Parasitol. 2008; 38(8-9):901-12. PMC: 2492832. DOI: 10.1016/j.ijpara.2007.12.009. View

Kiethega G, Turcotte M, Burger G . Evolutionarily conserved cox1 trans-splicing without cis-motifs. Mol Biol Evol. 2011; 28(9):2425-8. DOI: 10.1093/molbev/msr075. View

Kiethega G, Yan Y, Turcotte M, Burger G . RNA-level unscrambling of fragmented genes in Diplonema mitochondria. RNA Biol. 2013; 10(2):301-13. PMC: 3594288. DOI: 10.4161/rna.23340. View

Hajduk S, Ochsenreiter T . RNA editing in kinetoplastids. RNA Biol. 2010; 7(2):229-36. DOI: 10.4161/rna.7.2.11393. View

Blum B, Bakalara N, Simpson L . A model for RNA editing in kinetoplastid mitochondria: "guide" RNA molecules transcribed from maxicircle DNA provide the edited information. Cell. 1990; 60(2):189-98. DOI: 10.1016/0092-8674(90)90735-w. View

Ochsenreiter T, Cipriano M, Hajduk S . KISS: the kinetoplastid RNA editing sequence search tool. RNA. 2006; 13(1):1-4. PMC: 1705751. DOI: 10.1261/rna.232907. View

Veksler-Lublinsky I, Ziv-Ukelson M, Barash D, Kedem K . A structure-based flexible search method for motifs in RNA. J Comput Biol. 2007; 14(7):908-26. DOI: 10.1089/cmb.2007.0061. View

Gan H, Pasquali S, Schlick T . Exploring the repertoire of RNA secondary motifs using graph theory; implications for RNA design. Nucleic Acids Res. 2003; 31(11):2926-43. PMC: 156709. DOI: 10.1093/nar/gkg365. View

Kim N, Petingi L, Schlick T . Network Theory Tools for RNA Modeling. WSEAS Trans Math. 2014; 9(12):941-955. PMC: 4235620. View

10.

Von Haeseler A, Blum B, Simpson L, Sturm N, Waterman M . Computer methods for locating kinetoplastid cryptogenes. Nucleic Acids Res. 1992; 20(11):2717-24. PMC: 336913. DOI: 10.1093/nar/20.11.2717. View

11.

Lorenz R, Bernhart S, Honer Zu Siederdissen C, Tafer H, Flamm C, Stadler P . ViennaRNA Package 2.0. Algorithms Mol Biol. 2011; 6:26. PMC: 3319429. DOI: 10.1186/1748-7188-6-26. View

12.

Hamada M, Tsuda K, Kudo T, Kin T, Asai K . Mining frequent stem patterns from unaligned RNA sequences. Bioinformatics. 2006; 22(20):2480-7. DOI: 10.1093/bioinformatics/btl431. View

13.

Gawronski A, Turcotte M . RiboFSM: frequent subgraph mining for the discovery of RNA structures and interactions. BMC Bioinformatics. 2014; 15 Suppl 13:S2. PMC: 4248650. DOI: 10.1186/1471-2105-15-S13-S2. View

14.

Madej M, Niemann M, Huttenhofer A, Goringer H . Identification of novel guide RNAs from the mitochondria of Trypanosoma brucei. RNA Biol. 2008; 5(2):84-91. DOI: 10.4161/rna.5.2.6043. View

15.

Yao Z, Weinberg Z, Ruzzo W . CMfinder--a covariance model based RNA motif finding algorithm. Bioinformatics. 2005; 22(4):445-52. DOI: 10.1093/bioinformatics/btk008. View

16.

Izzo J, Kim N, Elmetwaly S, Schlick T . RAG: an update to the RNA-As-Graphs resource. BMC Bioinformatics. 2011; 12:219. PMC: 3123240. DOI: 10.1186/1471-2105-12-219. View

17.

Anwar M, Nguyen T, Turcotte M . Identification of consensus RNA secondary structures using suffix arrays. BMC Bioinformatics. 2006; 7:244. PMC: 1475642. DOI: 10.1186/1471-2105-7-244. View