Automated extraction of extended structured motifs using multi-objective genetic algorithm

Abstract

A structured motif is defined as a collection of highly conserved simple motifs with pre-specified sizes and gaps between them. In structured motif extraction, while all simple motifs are unknown, all gap ranges are known earlier. In this paper, we propose a novel method using multi-objective evolutionary algorithm to extract automatically extended structured motifs in which all simple motifs and gap ranges are unknown. The method employs three conflicting objectives; similarity and support maximization and total gap range minimization. To the best of our knowledge, this is the first effort in this direction. The proposed method can be applied to any data set with a sequential character. Furthermore, it allows any choice of similarity measures for finding motifs. We compare our method with the two well-known structured motif extraction methods, EXMOTIF and RISOTTO. Experiments conducted on synthetics and real data set demonstrate that the proposed method exhibits good performance over the other methods in terms of runtime and accuracy. (C) 2009 Elsevier Ltd. All rights reserved.