Tackling the challenging motif problem through hybrid particle swarm optimized alignment clustering

Previous studies show that Gibbs sampling methods and the like desperately failed to solve the challenging motif problem. This paper proposes a new hybrid algorithm, integrated Gibbs with particle swarm optimization (PSO) based motif alignment clustering (PSO-MAC), to solve the challenging motif problem by iteratively refining a population of potential solutions. The PSO-MAC algorithm is closely incorporated into a variant Gibbs called pseudo-Gibbs (pGibbs) motif sampler. Notably, pGibbs as a forerunner is executed multiple times and hence it brings about a population of potential alignments. Then, a PSO procedure coupled with motif alignment clustering (MAC) is developed to fine-tune such a population of solutions. The hybrid PSO-MAC algorithm aims to glean high quality motif solutions by cyclically refining and clustering the solution pool. Simulation and experimental results show that the new hybrid algorithm performs markedly better than others tested, and surprisingly it is able to solve the challenging motif problem with high precision. The new hybrid algorithm is also successfully applied to large-scale ChIP-Seq data sets.