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

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.

• Publication year

  2014

• Venue

  BMC Bioinformatics

• Publication date

  2014-11-13

• Fields of study

  Biology, Medicine, Computer Science

• Identifiers
  DOI 10.1186/1471-2105-15-S13-S2PMID 25434643PMCID 4248650
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• Computers And Intractability A Guide To The Theory Of Np Completeness

  2016cited by this paper
• Mining Graph Patterns

  2014cited by this paper
• RiboFSM: Frequent subgraph mining for the discovery of RNA structures and interactions

  2014cited by this paper
• Advances in the Techniques for the Prediction of microRNA Targets

  2013cited by this paper
• RNA-level unscrambling of fragmented genes in Diplonema mitochondria

  2013cited by this paper
• Network Theory Tools for RNA Modeling.

  2013cited by this paper
• Mining functional subgraphs from cancer protein-protein interaction networks

  2012cited by this paper
• A survey of frequent subgraph mining algorithms

  2012cited by this paper
• Classifying Multigraph Models of Secondary RNA Structure Using Graph-Theoretic Descriptors

  2012cited by this paper
• Computational Prediction of Intronic microRNA Targets using Host Gene Expression Reveals Novel Regulatory Mechanisms

  2011cited by this paper
• LGM: Mining Frequent Subgraphs from Linear Graphs

  2011cited by this paper
• RAG: An update to the RNA-As-Graphs resource

  2011cited by this paper
• ViennaRNA Package 2.0

  2011cited by this paper
• Evolutionarily conserved cox1 trans-splicing without cis-motifs.

  2011cited by this paper
• RNA editing in kinetoplastids

  2010cited by this paper
• Frequent subgraph mining on a single large graph using sampling techniques

  2010cited by this paper
• Large Scale Similarity Search for Locally stable Secondary Structures among RNA Sequences (IPSJ Transactions on Bioinformatics Vol.2)

  2009cited by this paper
• Identification of novel guide RNAs from the mitochondria of Trypanosoma brucei

  2008cited by this paper
• Structure and function of the native and recombinant mitochondrial MRP1/MRP2 complex from Trypanosoma brucei.

  2008cited by this paper
• Cold-stress-induced de novo expression of infC and role of IF3 in cold-shock translational bias.

  2007cited by this paper
• Fast Pairwise Structural RNA Alignments by Pruning of the Dynamical Programming Matrix

  2007cited by this paper
• What Is Frequent in a Single Graph?

  2007cited by this paper
• Support Computation for Mining Frequent Subgraphs in a Single Graph

  2007cited by this paper
• Mining RNA Tertiary Motifs with Structure Graphs

  2007cited by this paper
• A Structure-Based Flexible Search Method for Motifs in RNA

  2007cited by this paper
• Identification of consensus RNA secondary structures using suffix arrays

  2006cited by this paper
• RNAhybrid: microRNA target prediction easy, fast and flexible

  2006cited by this paper
• miTarget: microRNA target gene prediction using a support vector machine

  2006cited by this paper
• Frequent subgraph mining in outerplanar graphs

  2006cited by this paper
• Mining frequent stem patterns from unaligned RNA sequences

  2006cited by this paper
• KISS: the kinetoplastid RNA editing sequence search tool.

  2006influential reference
• CMfinder - a covariance model based RNA motif finding algorithm

  2006influential reference
• Interactions of mRNAs and gRNAs involved in trypanosome mitochondrial RNA editing: structure probing of a gRNA bound to its cognate mRNA.

  2006cited by this paper
• The relationship between Precision-Recall and ROC curves

  2006cited by this paper
• Conserved seed pairing, often flanked by adenosines, indicates that thousands of human genes are microRNA targets.

  2005cited by this paper
• Subdue: compression-based frequent pattern discovery in graph data

  2005cited by this paper
• Algorithms for pattern matching and discovery in RNA secondary structure

  2005cited by this paper
• BIOINFORMATICS ORIGINAL PAPER Sequence analysis Pair stochastic tree adjoining grammars for aligning and predicting pseudoknot RNA structures

  2005cited by this paper
• Mining coherent dense subgraphs across massive biological networks for functional discovery

  2005cited by this paper
• Finding Frequent Patterns in a Large Sparse Graph*

  2004influential reference
• An efficient algorithm for detecting frequent subgraphs in biological networks

  2004cited by this paper
• GREW - a scalable frequent subgraph discovery algorithm

  2004cited by this paper
• Exploring the repertoire of RNA secondary motifs using graph theory; implications for RNA design.

  2003influential reference
• WU-Blast2 server at the European Bioinformatics Institute

  2003cited by this paper
• RNA（ribonucleic acid）

  2002cited by this paper
• Prediction of consensus structural motifs in a family of coregulated RNA sequences.

  2002cited by this paper
• gSpan: graph-based substructure pattern mining

  2002cited by this paper
• Prediction of common secondary structures of RNAs: a genetic algorithm approach.

  2000cited by this paper
• The Graph Isomorphism Problem

  1996cited by this paper
• A graph-topological approach to recognition of pattern and similarity in RNA secondary structures.

  1996cited by this paper
• The ins and outs of editing RNA in kinetoplastids.

  1995cited by this paper
• RNA sequence analysis using covariance models.

  1994cited by this paper
• Computer methods for locating kinetoplastid cryptogenes.

  1992cited by this paper
• A model for RNA editing in kinetoplastid mitochondria: "guide" RNA molecules transcribed from maxicircle DNA provide the edited information.

  1990cited by this paper
• Tree graphs of RNA secondary structures and their comparisons.

  1989cited by this paper
• Goodness-of-Fit-Techniques

  1987cited by this paper
• Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems

  1985cited by this paper
• RNA secondary structures and their prediction

  1984cited by this paper
• Johnson: computers and intractability: a guide to the theory of np- completeness (freeman

  1979cited by this paper
• マグロ類のDNA(Deoxyribonucleic acid)に関する研究

  1964cited by this paper

• Community evolution and frequent subgraph patterns affect the thermostability of B. subtilis lipase A

  2021cites this paper
• Fuzzy RNA recognition by the Trypanosoma brucei editosome

  2021cites this paper
• SICOR: Subgraph Isomorphism Comparison of RNA Secondary Structures

  2020cites this paper
• Motif Discovery Algorithms in Static and Temporal Networks: A Survey

  2020cites this paper
• Graph- and rule-based learning algorithms: a comprehensive review of their applications for cancer type classification and prognosis using genomic data

  2019cites this paper
• Exploring Consensus RNA Substructural Patterns Using Subgraph Mining

  2017cites this paper
• A novel geometric graph miner and its applications

  2016cites this paper
• RiboFSM: Frequent subgraph mining for the discovery of RNA structures and interactions

  2014cites this paper