Casting the Problem of Mining RNA Sequence-Structure Motifs as One of Search and Learning Hyper-Heuristics for it

Created by W.Langdon from gp-bibliography.bib Revision:1.4524

  author =       "Achiya Elyasaf and Pavel Vaks and Nimrod Milo and 
                 Moshe Sipper and Michal Ziv-Ukelson",
  title =        "Casting the Problem of Mining {RNA} Sequence-Structure
                 Motifs as One of Search and Learning Hyper-Heuristics
                 for it",
  booktitle =    "Genetic Programming Theory and Practice XIII",
  year =         "2015",
  editor =       "Rick Riolo and William P. Worzel and M. Kotanchek and 
                 A. Kordon",
  series =       "Genetic and Evolutionary Computation",
  pages =        "21--38",
  address =      "Ann Arbor, USA",
  month =        "14-16 " # may,
  publisher =    "Springer",
  keywords =     "genetic algorithms, genetic programming, Hyper
  isbn13 =       "978-3-319-34223-8",
  URL =          "",
  DOI =          "doi:10.1007/978-3-319-34223-8_2",
  abstract =     "The computational identification of conserved motifs
                 in RNA molecules is a major—yet largely
                 unsolved—problem. Structural conservation serves as
                 strong evidence for important RNA functionality. Thus,
                 comparative structure analysis is the gold standard for
                 the discovery and interpretation of functional RNAs.In
                 this paper we focus on one of the functional RNA motif
                 types, sequence-structure motifs in RNA molecules,
                 which marks the molecule as targets to be recognized by
                 other molecules.We present a new approach for the
                 detection of RNA structure (including pseudoknots),
                 which is conserved among a set of unaligned RNA
                 sequences. Our method extends previous approaches for
                 this problem, which were based on first identifying
                 conserved stems and then assembling them into complex
                 structural motifs. The novelty of our approach is in
                 simultaneously preforming both the identification and
                 the assembly of these stems. We believe this novel
                 unified approach offers a more informative model for
                 deciphering the evolution of functional RNAs, where the
                 sets of stems comprising a conserved motif co-evolve as
                 a correlated functional unit.Since the task of mining
                 RNA sequence-structure motifs can be addressed by
                 solving the maximum weighted clique problem in an
                 n-partite graph, we translate the maximum weighted
                 clique problem into a state graph. Then, we gather and
                 define domain knowledge and low-level heuristics for
                 this domain. Finally, we learn hyper-heuristics for
                 this domain, which can be used with heuristic search
                 algorithms (e.g., A-star, IDA*) for the mining task.The
                 hyper-heuristics are evolved using HH-Evolver, a tool
                 for domain-specific, hyper-heuristic evolution. Our
                 approach is designed to overcome the computational
                 limitations of current algorithms, and to remove the
                 necessity of previous assumptions that were used for
                 sparsifying the graph.This is still work in progress
                 and as yet we have no results to report. However, given
                 the interest in the methodology and its previous
                 success in other domains we are hopeful that these
                 shall be forthcoming soon.",
  notes =        "

                 Part of \cite{Riolo:2015:GPTP} Published after the
                 workshop in 2016",

Genetic Programming entries for Achiya Elyasaf Pavel Vaks Nimrod Milo Moshe Sipper Michal Ziv-Ukelson