A particle swarm optimization-based algorithm for finding gapped motifs

Chengwei Lei, Jianhua Ruan

    Research output: Contribution to journalArticlepeer-review

    15 Scopus citations

    Abstract

    Background. Identifying approximately repeated patterns, or motifs, in DNA sequences from a set of co-regulated genes is an important step towards deciphering the complex gene regulatory networks and understanding gene functions. Results. In this work, we develop a novel motif finding algorithm (PSO+) using a population-based stochastic optimization technique called Particle Swarm Optimization (PSO), which has been shown to be effective in optimizing difficult multidimensional problems in continuous domains. We propose a modification of the standard PSO algorithm to handle discrete values, such as characters in DNA sequences. The algorithm provides several features. First, we use both consensus and position-specific weight matrix representations in our algorithm, taking advantage of the efficiency of the former and the accuracy of the latter. Furthermore, many real motifs contain gaps, but the existing methods usually ignore them or assume a user know their exact locations and lengths, which is usually impractical for real applications. In comparison, our method models gaps explicitly, and provides an easy solution to find gapped motifs without any detailed knowledge of gaps. Our method allows the presence of input sequences containing zero or multiple binding sites. Conclusion. Experimental results on synthetic challenge problems as well as real biological sequences show that our method is both more efficient and more accurate than several existing algorithms, especially when gaps are present in the motifs.

    Original languageEnglish (US)
    Article number9
    JournalBioData Mining
    Volume3
    Issue number1
    DOIs
    StatePublished - 2010

    ASJC Scopus subject areas

    • Biochemistry
    • Molecular Biology
    • Genetics
    • Computer Science Applications
    • Computational Theory and Mathematics
    • Computational Mathematics

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

    Cite this