Article: A novel swarm intelligence algorithm for finding DNA motifs Journal: International Journal of Computational Biology and Drug Design (IJCBDD) 2009 Vol.2 No.4 pp.323 - 339 Abstract: Discovering DNA motifs from co-expressed or co-regulated genes is an important step towards deciphering complex gene regulatory networks and understanding gene functions. Despite significant improvement in the last decade, it still remains one of the most challenging problems in computational molecular biology. In this work, we propose a novel motif finding algorithm that finds consensus patterns using a population-based stochastic optimisation technique called Particle Swarm Optimisation (PSO), which has been shown to be effective in optimising difficult multidimensional problems in continuous domains. We propose to use a word dissimilarity graph to remap the neighborhood structure of the solution space of DNA motifs, and propose a modification of the naive PSO algorithm to accommodate discrete variables. In order to improve efficiency, we also propose several strategies for escaping from local optima and for automatically determining the termination criteria. Experimental results on simulated challenge problems show that our method is both more efficient and more accurate than several existing algorithms. Applications to several sets of real promoter sequences also show that our approach is able to detect known transcription factor binding sites, and outperforms two of the most popular existing algorithms. Inderscience Publishers - linking academia, business and industry through research

Title: A novel swarm intelligence algorithm for finding DNA motifs

Authors: Chengwei Lei, Jianhua Ruan

Addresses: Department of Computer Science, The University of Texas at San Antonio, One UTSA Circle, San Antonio, TX 78249, USA. ' Department of Computer Science, The University of Texas at San Antonio, One UTSA Circle, San Antonio, TX 78249, USA

Abstract: Discovering DNA motifs from co-expressed or co-regulated genes is an important step towards deciphering complex gene regulatory networks and understanding gene functions. Despite significant improvement in the last decade, it still remains one of the most challenging problems in computational molecular biology. In this work, we propose a novel motif finding algorithm that finds consensus patterns using a population-based stochastic optimisation technique called Particle Swarm Optimisation (PSO), which has been shown to be effective in optimising difficult multidimensional problems in continuous domains. We propose to use a word dissimilarity graph to remap the neighborhood structure of the solution space of DNA motifs, and propose a modification of the naive PSO algorithm to accommodate discrete variables. In order to improve efficiency, we also propose several strategies for escaping from local optima and for automatically determining the termination criteria. Experimental results on simulated challenge problems show that our method is both more efficient and more accurate than several existing algorithms. Applications to several sets of real promoter sequences also show that our approach is able to detect known transcription factor binding sites, and outperforms two of the most popular existing algorithms.

Keywords: DNA motifs; optimisation; swarm intelligence; PSO; particle swarm optimisation; gene regulatory networks; gene function; computational molecular biology; consensus patterns; simulation; transcription factor binding sites.

DOI: 10.1504/IJCBDD.2009.030764

International Journal of Computational Biology and Drug Design, 2009 Vol.2 No.4, pp.323 - 339

Published online: 04 Jan 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article

Title: A novel swarm intelligence algorithm for finding DNA motifs

Keep up-to-date