Hardware accelerated genetic programming for pattern mining in strings

Abstract

This thesis considers the problem of mining patterns in strings. Informally, this is the problem of extracting information (patterns) that characterizes parts of, or even the complete, string. The thesis describes a high performance hardware for string searching, which together with genetic programming, forms the basis for the thesis’ pattern mining algorithms.

This work considers two different pattern mining problems and develops several different algorithms to solve different variants of these problems. Common to all algorithms is that they use genetic programming to evolve patterns that can be evaluated by the special purpose search hardware.

The first pattern mining problem considered is unsupervised mining of prediction rules in discretized time series. Such prediction rules describe relations between consecutive patterns in the discretized time series; that is, the prediction rules state that if the first pattern occurs, the second pattern will, with high probability, follow within a fixed number of symbols. The goal is to automatically extract prediction rules that are accurate, comprehensible, and interesting.

The second pattern mining problem considered is supervised learning of classifiers that predict whether or not a given string belongs to a specific class of strings. This binary classification problem is very general, but this thesis focuses on two recent problems from molecular biology: i) predicting the efficacy of short interfering RNAs and antisense oligonucleotides; and ii) predicting whether or not a given DNA sequence is a non-coding RNA gene. The thesis describes a genetic programming based mining algorithm that produce state-of-the-art classifiers on both problems.