In Bioinformatics, Motif Finding is one of the most popular problems, which has many applications. Generally, it is to locate recurring patterns in the sequence of nucleotides or amino acids. As we can’t expect the pattern to be exact matching copies owing to biological mutations, the motif finding turns to be an NP-complete problem. By approximating the same in different aspects, scientists have provided many solutions in the literature. The most of the algorithms suffer with local optima. Particle swarm optimization (PSO) is a new global optimization technique which has wide applications. It finds the global best solution by simply adjusting the trajectory of each individual towards its own best location and towards the best particle of the swarm at each generation. We have adopted the features of the PSO to solve the Planted Motif Finding Problem and have designed a sequential algorithm. We have performed experiments with simulated data it outperforms MbGA and PbGA. The PMbPSO also applied for real biological data sets and observe that the algorithm is also able to detect known TFBS accurately when there are no mutations.

1. Xiong, J. 2006. Essentials of Bioinformatics, Cambridge press.
2. Lawrence, C., Altschul, S., Boguski, M., Liu, J., Neuwald, A., and Wootton, J. 1993. Detecting subtle sequence signals: a Gibbs sampling strategy for multiple alignments, Science, 262, 208-214.
3. Bailey, T., and Elkan, C. 1995. Unsupervised learning of multiple motifs in biopolymers using expectation maximization, Mach. Learning, 21, 51–80).
4. Bubhler, J., and Tompa, M. 2001, Finding motifs using random projections, Proceedings of the Fifth Annual International Conference on Research in Computational Molecular Biology, (69-76).
5. Price, A., Ramabhadran, S., and Pevzner, P. 2003. Finding subtle motifs by branching from sample strings, Bioinformatics, (149-155).
6. Modan, K., Das and Dai, H. 2007. A survey of DNA motif finding algorithms, BMC Bioinformatics, (1-13).
7. Mart´ınez-Arellano, G., and. Brizuela, C.A. 2007. Comparison of Simple Encoding Schemes in GA’s for the Motif Finding Problem: Preliminary Results, Springer-Verlag Berlin Heidelberg, (22–33).
8. Hassanien, A., Mariofanna, G., Milanova, Tomasz G., Smolinski, and Abraham, A. 2008. Computational Intelligence in Solving Bioinformatics Problems: Reviews, Perspectives, and Challenges, (1-48).
9. Hardin, C. T., and Rouchka, E. C. 2005. DNA Motif Detection Using Particle Swarm Optimization and Expectation-Maximization, proc. IEEE, (181- 184).
10. Zhou, W., Zhou, C., Liu, G., and Huang, Y. 2005. Identification of Transcription Factor Binding Sites Using Hybrid Particle Swarm Optimization, Springer-Verlag Berlin Heidelberg, (438–445).
11. Zhou, W., Zhu, H., Liu, G., Huang, Y., Wang, Y., Han, D., and Zhou, C. 2005. A Novel Computational Based Method for Discovery of Sequence Motifs from Coexpressed Genes, International Journal of Information Technology, 11, 8, (75-83).
12. Chang, X., Zhou, C., Li, Y., and Hu, P. 2006. Identification of Transcription Factor Binding Sites Using GA and PSO, Proc.6th Int. Conf on Intelligent Systems Design and Applications, (1-5).
13. Chang, B. 2004. Particle Swarm Optimization for Protein Motif Discovery, in Genetic Programming and Evolvable Machines, 5, (203-214).
14. Gusfield, D. 1997. Algorithms on Strings, Trees and Sequences, Computer Science and Computational Biology. Cambridge University Press, Cambridge.
15. Pevzner, P., and Sze, S.-H. 2000. Combinatorial approaches to finding subtle signals in DNA Sequences. Proc. 8th Int. Conf. Intelligent Systems for Molecular Biology, (269–278).
16. Hu,Y. 2003. Finding subtle motifs with variable gaps in unaligned DNA sequences, Computer Methods and Programs in Biomedicine, 70, (11–20).
17. Kennedy, J., and Eberhart, R. C. 1995. Particle Swarm Optimization, Proc. of the IEEE International Conference on Neural Networks (1942-1948).
18. Zhu, J., and Zhang M.Q. 1999. A promoter database of the yeast Saccharomyces cerevisiae. Bioinformatics, 15, (607-611).

Motif Finding Particle Swarm Optimization (PSO) Swarm Intelligence (SI) Transcriptional Factor Binding Sites (TFBS) Planted Motifs