A novel Swarm intelligence algorithm for finding DNA motifs

Chengwei Lei, Jianhua Ruan

Research output: Contribution to journalArticle

10 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)323-339
Number of pages17
JournalInternational Journal of Computational Biology and Drug Design
Volume2
Issue number4
DOIs
StatePublished - Jan 2009
Externally publishedYes

Keywords

  • DNA motif
  • Optimisation
  • PSO
  • Particle Swarm Optimisation
  • Swarm intelligence

ASJC Scopus subject areas

  • Drug Discovery
  • Computer Science Applications

Fingerprint Dive into the research topics of 'A novel Swarm intelligence algorithm for finding DNA motifs'. Together they form a unique fingerprint.

Cite this