A particle swarm optimization algorithm for finding DNA sequence motifs

Chengwei Lei, Jianhua Ruan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Scopus citations

Abstract

Discovering short DNA motifs from a set of co-regulated genes is an important step towards deciphering the 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 both computer science and molecular biology. In this work, we propose a novel motif finding algorithm based on a population-based stochastic optimization technique called Particle Swarm Optimization (PSO), which has been shown to be effective in optimizing difficult multidimensional problems in many fields. However, PSO has mainly been applied to problems in continuous domains. The motif finding problem, which is essentially a multiple local alignment problem, is discrete, as a slight shift in one sequence completely changes the alignment. Therefore, we propose to use a word dissimilarity graph to remap the neighborhood structure of the solution space, which transforms the motif finding problem into a contiguous integer domain, and propose a modification of the naive PSO algorithm to accommodate integer variables. In order to improve efficiency, we also propose several strategies for escaping from local optima, and determining the termination criteria automatically. 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 successful existing algorithms.

Original languageEnglish (US)
Title of host publicationProceedings - 2008 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW
Pages166-173
Number of pages8
DOIs
StatePublished - Dec 1 2008
Externally publishedYes
Event2008 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW - Philadelphia, PA, United States
Duration: Nov 3 2008Nov 5 2008

Publication series

NameProceedings - 2008 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW

Conference

Conference2008 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW
CountryUnited States
CityPhiladelphia, PA
Period11/3/0811/5/08

ASJC Scopus subject areas

  • Molecular Biology
  • Information Systems
  • Biomedical Engineering

Fingerprint Dive into the research topics of 'A particle swarm optimization algorithm for finding DNA sequence motifs'. Together they form a unique fingerprint.

  • Cite this

    Lei, C., & Ruan, J. (2008). A particle swarm optimization algorithm for finding DNA sequence motifs. In Proceedings - 2008 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW (pp. 166-173). [4686231] (Proceedings - 2008 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW). https://doi.org/10.1109/BIBMW.2008.4686231