Summary
Research in bioinformatics necessitates the use of advanced computing tools for processing huge amounts of ambiguous and uncertain biological data. Swarm Intelligence (SI) has recently emerged as a family of nature inspired algorithms, especially known for their ability to produce low cost, fast and reasonably accurate solutions to complex search problems. In this chapter, we explore the role of SI algorithms in certain bioinformatics tasks like microarray data clustering, multiple sequence alignment, protein structure prediction and molecular docking. The chapter begins with an overview of the basic concepts of bioinformatics along with their biological basis. It also gives an introduction to swarm intelligence with special emphasis on two specific SI algorithms well-known as Particle Swarm Optimization (PSO) and Ant Colony Systems (ACS). It then provides a detailed survey of the state of the art research centered around the applications of SI algorithms in bioinformatics. The chapter concludes with a discussion on how SI algorithms can be used for solving a few open ended problems in bioinformatics.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Genetic Algorithm
- Particle Swarm Optimization
- Particle Swarm Optimization Algorithm
- Travel Salesman Problem
- Swarm Intelligence
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Baldi P and Brunak S (1998) Bioinformatics: The Machine Learning Approach, MIT Press, Cambridge, MA.
Altman RB, Valencia A, Miyano S and Ranganathan, S (2001) Challenges for intelligent systems in biology, IEEE Intelligent Systems, vol. 16, no. 6, pp. 14–20.
Haykin S. (1999) Neural Networks: A Comprehensive Foundation, Prentice Hall.
Holland JH (1975) Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor.
Goldberg DE (1975) Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Reading, MA.
Mitra S and Hayashi Y (2006) Bioinformatics with soft computing, IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, Vol. 36, pp. 616–635.
Bonabeau E, Dorigo M, Theraulaz G (2001) Swarm intelligence: From natural to artificial systems. Journal of Artificial Societies and Social Simulation, 4(1).
Engelbrecht AP (2005) Fundamentals of Computational Swarm Intelligence. Wiley.
Beni G and Wang U (1989) Swarm intelligence in cellular robotic systems. In NATO Advanced Workshop on Robots and Biological Systems, Il Ciocco, Tuscany, Italy.
Kennedy J, Eberhart R (1995) Particle swarm optimization, In Proceedings of IEEE International conference on Neural Networks. 1942–1948.
Dorigo M (1992) Optimization, learning, and natural algorithms, Ph.D. dissertation (in Italian), Dipartimento di Elettronica, Politecnico di Milano, Milano, Italy.
Dorigo M, Di Caro G and Gambardella L (1999) Ant colony optimization: A new metaheuristic. In PJ Angeline, Z Michalewicz, M Schoenauer, X Yao, and A Zalzala, (eds), Proceedings of the Congress on Evolutionary Computation, IEEE Press, Vol. 2, pp. 1470–1477.
Lewin B (1995) Genes VII. Oxford University Press, New York, NY.
Wu AS and Lindsay RK (1996) A Survey of Intron Research in Genetics, In Proc. 4th Conf. of on Parallel Problem Solving from Nature, pp. 101–110.
Setubal J and Meidanis J (1999) Introduction to Computational Molecular Biology, International Thomson Publishing, 20 park plaza, Boston, MA 02116.
Couzin ID, Krause J, James R, Ruxton GD, Franks NR (2002) Collective Memory and Spatial Sorting in Animal Groups, Journal of Theoretical Biology, 218, pp. 1–11.
Krause J and Ruxton GD (2002) Living in Groups. Oxford: Oxford University Press.
Partridge BL, Pitcher TJ (1980) The sensory basis of fish schools: relative role of lateral line and vision. Journal of Comparative Physiology, 135, pp. 315–325.
Partridge BL (1982) The structure and function of fish schools. Science American, 245, pp. 90–99.
Major PF, Dill LM (1978) The three-dimensional structure of airborne bird flocks. Behavioral Ecology and Sociobiology, 4, pp. 111–122.
Branden CI and Tooze J (1999) Introduction to Protein Structure: 2nd edition. Garland Publishing, New York, 2nd edition.
Grosan C, Abraham A and Monica C (2006) Swarm Intelligence in Data Mining, in Swarm Intelligence in Data Mining, Abraham A, Grosan C and Ramos V (Eds), Springer, pp. 1–16.
Milonas MM (1994) Swarms, phase transitions, and collective intelligence, In Langton CG Ed., Artificial Life III, Addison Wesley, Reading, MA.
Serra R and Zanarini G (1990) Complex Systems and Cognitive Processes. New York, NY: Springer-Verlag.
Flake G (1999) The Computational Beauty of Nature. Cambridge, MA: MIT Press.
Kennedy J, Eberhart R and Shi Y (2001) Swarm Intelligence, Morgan Kaufmann Academic Press.
Dorigo M and Gambardella LM (1996) A Study of Some Properties of Ant Q, In Proc. PPSN IV - 4th Int. Conf. Parallel Problem Solving From Nature, Berlin, Germany: Springer-Verlag, pp. 656–665.
Dorigo M and Gambardella LM (1997) Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Trans. Evol. Comput., vol. 1, pp. 53–66.
Deneubourg JL (1997) Application de I’ordre par fluctuations? la descriptio de certaines? tapes de la construction dun id chez les termites, Insect Sociaux, vol. 24, pp. 117–130.
Dorigo M, Maniezzo V and Colorni A (1996) The ant system: Optimization by a colony of cooperating agents, IEEE Trans. Syst. Man Cybern. B, vol. 26.
Kennedy J (1999) Small Worlds and Mega-Minds: Effects of Neighborhood Topology on Particle Swarm Performance, Proceedings of the 1999 Congress of Evolutionary Computation, vol. 3, IEEE Press, pp. 1931–1938.
Kennedy J and Mendes R (2002) Population structure and particle swarm performance. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC), IEEE Press, pp. 1671–1676.
Watts DJ and Strogatz SH (1998) Collective dynamics of small-world networks. Nature, 393, 440–442.
Dall’Asta L, Baronchelli A, Barrat A and Loreto V (2006) Agreement dynamics on small-world networks. Europhysics Letters.
Barrat A and Weight M (2000) On the properties of small-world network models. The European Physical Journal, 13, pp. 547–560.
Moore C and Newman MEJ (2000) Epidemics and percolation in small-world networks. Physics. Review. E 61, 5678–5682.
Jasch F and Blumen A (2001) Trapping of random walks on small-world networks. Physical Review E 64, 066104.
Chen J, Antipov E, Lemieux B, Cedeno W, and Wood DH (1999) DNA computing implementing genetic algorithms, Evolution as Computation, Springer Verlag, New York, pp. 39–49.
Vesterstrom J and Thomsen R (2004) A comparative study of differential evolution, particle swarm optimization, and evolutionary algorithms on numerical benchmark problems, In Proceedings of the IEEE Congress on Evolutionary Computation (CEC 04), IEEE Press, pp. 1980–1987.
Das S, Konar A, Chakraborti UK (2005) A New Evolutionary Algorithm Applied to the Design of Two-dimensional IIR Filters in ACM-SIGEVO Proceedings of Genetic and Evolutionary Computation Conference (GECCO-2005), Washington DC.
Hassan R, Cohanim B and de Weck O (2005) Comparison of Particle Swarm Optimization and the Genetic Algorithm, AIAA-2005-1897, 46th AIAA/ASME/ASCE/AHS/ASC Structures, Structural Dynamics & Materials Conference.
Luscombe NM, Greenbaum D and Gerstein M (2001) What is Bioinformatics? A Proposed Definition and Overview of the Field, Yearbook of Medical Informatics, pp. 83–100.
Quackenbush J (2001) Computational analysis of microarray data, National Review of Genetics, vol. 2, pp. 418–427.
Special Issue on Bioinformatics, IEEE Computer, vol. 35, July 2002.
Jain AK, Murty MN and Flynn, PJ (1999) Data clustering: a review, ACM Computing Surveys, vol. 31, no. 3, pp. 264–323.
Baker TK, Carfagna MA, Gao H, Dow ER, Li O, Searfoss GH, and Ryan TP (2001) Temporal Gene Expression Analysis of Monolayer Cultured Rat Hepatocytes, Chem. Res. Toxicol., Vol. 14, No. 9.
Alon U, Barkai N, Notterman DA, Gish K, Ybarra S, Mack D and Levine AJ (1999) Broad Patterns of Gene Expression Revealed by Clustering Analysis of Tumor and Normal Colon Tissues Probed by Oligonucleotide Arrays, Proc. Natl. Acad. Sci. USA, Cell Biology, Vol. 96, pp. 6745–6750.
Maurice G and Kendall M (1961) The Advanced Theory of Statistics, Vol. 2, Charles Griffin and Company Limited.
Wen X, Fuhrman S, Michaels GS, Carr DB, Smith S, Barker JL, and Somogyi R (1998) Large-scale temporal gene expression mapping of central nervous system development, Proc. Natl. Acad. Sci. USA, Neurobiology, Vol. 95, pp. 334–339.
Spellman EM, Brown PL, Brown D (1998) Cluster Analysis and Display of Genome-wide expression patterns, Proc. Natl. Acad. Sci. USA 95: 14863–14868.
Yeung KY, Ruzzo WL (2001) Principal Component Analysis for Clustering Gene Expression Data, Bioinformatics, 17, pp. 763–774.
Raychaudhuri S, Stuart JM and Altman RB (2000) Principal Components Analysis to Summarize Microarray Experiments: Application to Sporulation Time Series, Pacific Symposium on Biocomputing 2000, Honolulu, Hawaii, pp. 452–463.
Li L, Weinberg CR, Darden TA and Pedersen LG (2001) Gene Selection for Sample Classification Based on Gene Expression Data: Study of Sensitivity to Choice of Parameters of the GA/KNN Method, Bioinformatics, 17, pp. 1131–1142.
Herrero J, Valencia A and Dopazo J (2001) A hierarchical unsupervised growing neural network for clustering gene expression patterns, Bioinformatics, 17, pp. 126–136.
Tamayo P, Slonim D, Mesirov J, Zhu Q, Kitareewan S, Dmitrovsky E, Lander ES and Golub TR (1999) Interpreting patterns of gene expression with self organizing maps: Methods and applications to hematopoietic differentiation. PNAS, 96, pp. 2907–2912.
Toronen P, Kolehmainen M, Wong G, Castren E (1999) Analysis of Gene Expression Data Using Self-organizing Maps, FEBS letters 451, pp. 142–146.
Xiao X, Dow ER, Eberhart RC, Miled ZB and Oppelt RJ (2003) Gene Clustering Using Self-Organizing Maps and Particle Swarm Optimization, Proc of the 17th International Symposium on Parallel and Distributed Processing (PDPS ’03), IEEE Computer Society, Washington DC.
Kohonen T (1995) Self-organizing Maps, 2nd ed., Springer-Verlag, Berlin.
Liu BF, Chen HM, Huang HL, Hwang SF and Ho SY (2005) Flexible protein-ligand docking using particle swarm optimization, in Proc. of Congress on Evolutionary Computation (CEC 2005), IEEE Press, Washinton DC.
Jones G, Willett P, Glen RC, Leach AR and Taylor R (1997) Development and validation of a genetic algorithm for flexible docking. Journal of Molecular Biology, 267(3): pp. 727–748.
Morris GM, Goodsell DS, Halliday RS, Huey R, Hart WE, Belew RK and Olson AJ (1998) Automated docking using a lamarckian genetic algorithm and an empirical binding free energy function. Journal of Computational Chemistry, 19(14): pp. 1639–1662.
Ewing TJA, Makino S, Skillman AG and Kuntz ID (2001) Dock 4.0: Search strategies for automated molecular docking of flexible molecule databases. Journal of Computer-Aided Molecular Design, 15(5): pp. 411–428.
Lipman DJ, Altschul SF and Kececioglu JD (1989). A tool for multiple sequence alignment. Proc. Natl. Acad. Sci. USA, 86: pp. 4412–4415.
Feng DF, Doolittle RF (1987) Progressive sequence alignment as a prerequisite to correct phylogenetic trees. J. Mol. Evol. 25, pp. 351–360.
Thompson JD, Higgins DG and Gibson TJ (1994) CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position specific gap penalties and weight matrix choice. Nucleic Acids Research, vol. 22, No. 22, pp. 4673–4680.
Chen Y, Pan Y, Chen L, Chen J (2006) Partitioned optimization algorithms for multiple sequence alignment, Proc. of the 20th International Conference on Advanced Information Networking and Applications - (AINA’06), IEEE Computer Society Press, Washington DC., Volume 02, pp. 618–622.
Notredame C and Higgins DG, SAGA: sequence alignment by genetic algorithm, Nucleic Acids Research, vol. 24, no. 8, pp. 1515–1524.
Rasmussen TK and Krink T (2003) Improved hidden Markov model training for multiple sequence alignment by a particle swarm optimization-evolutionary algorithm hybrid, BioSystems 72 (2003).
Stolcke A and Omohundro S (1993) Hidden Markov Model induction by Bayesian model merging. In NIPS 5, pp. 11–18.
Hamam Y and Al-Ani T (1996). Simulated annealing approach for Hidden Markov Models. 4th WG-7.6 Working Conference on Optimization-Based Computer-Aided Modeling and Design, ESIEE, France.
Felsenstein J (1973). Maximum likelihood estimation of evolutionary trees from continuous characters.Am. J. Hum. Gen. 25: 471–492.
Lewis PO (1998), A genetic algorithm for maximum likelihood phylogeny inference using nucleotide sequence data, Molecular Biology and Evolution, vol. 15, no. 3, pp. 277–283.
Lemmon AR and Milinkovitch MC (2002) The metapopulation genetic algorithm: An efficient solution for the problem of large phylogeny estimation, Proc. Natl Acad Sci U S A., vol. 99, no. 16, pp. 10516–10521.
Perretto M and Lopes HS (2005) Reconstruction of phylogenetic trees using the ant colony optimization paradigm, Genetic and Molecular Research 4 (3), pp. 581–589.
Ando S and Iba H (2002) Ant algorithm for construction of evolutionary tree, in Proc. of Congress on Evolutionary Computation (CEC 2002), IEEE Press, USA.
Neethling M and Engelbrecht AP (2006) Determining RNA Secondary Structure using Set-based Particle Swarm Optimization, in Proc. of Congress on Evolutionary Computation (CEC 2006), IEEE Press, USA.
Hofacker IL (2003) Vienna rna secondary structure server, Nucleic Acids Research, vol. 31:13, pp. 3429–3431.
Lau KF and Dill KA (1989) A lattice statistical mechanics model of the conformation and sequence space of proteins. Macromolecules 22, pp. 3986–3997.
Richards FM (1977) Areas, volumes, packing, and protein structures. Annu. Rev. Biophys. Bioeng. 6, pp. 151–176.
Krasnogor N, Hart WE, Smith J and Pelta DA (1999) Protein structure prediction with evolutionary algorithms. Proceedings of the Genetic & Evolutionary Computing Conf (GECCO 1999).
Shmygelska A, Hoos HH (2003) An Improved Ant Colony Optimization Algorithm for the 2D HP Protein Folding Problem. Canadian Conference on AI 2003: 400–417.
Shmygelska A, Hoos HH (2005) An ant colony optimization algorithm for the 2D and 3D hydrophobic polar protein folding problem. BMC Bioinformatics 6:30.
Chu D, Till M and Zomaya A (2005) Parallel Ant Colony Optimization for 3D Protein Structure Prediction using the HP Lattice Model, Proc. of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS’05), IEEE Computer Society Press.
Meksangsouy P and Chaiyaratana N (2003) DNA fragment assembly using an ant colony system algorithm, in Proc. of Congress on Evolutionary Computation (CEC 2006), IEEE Press, USA.
Ando S and Iba H (2001) Inference of gene regulatory model by genetic algorithms, Proc. Congress on Evolutionary Computation (CEC 2001), vol. 1, pp. 712–719.
Behera N and Nanjundiah V (1997) Trans-gene regulation in adaptive evolution: a genetic algor-ithm model, Journal of Theoretical Biology, vol. 188, pp. 153–162.
Ando S and Iba H (2000) Quantitative Modeling of Gene Regulatory Network - Identifying the Network by Means of Genetic Algorithms, The Eleventh Genome Informatics Workshop, 2000.
Ando S and Iba H (2001) The Matrix Modeling of Gene Regulatory Networks - Reverse Engineering by Genetic Algorithms, Proc. Atlantic Symposium on Computational Biology and Genome Information Systems and Technology.
Tominaga D, Okamoto M, Maki Y, Watanabe S and Eguchi Y (1999) Nonlinear Numerical optimization technique based on a genetic algorithm for inverse Problems: Towards the inference of genetic networks, Computer Science and Biology (Proc. German Conf. on Bioinformatics), pp. 127–140.
Branden CI and Tooze J (1999) Introduction to Protein Structure: 2nd edition. Garland Publishing, New York, 2nd edition.
Liu Y and Beveridge DL (2002) Exploratory studies of ab initio protein structure prediction: multiple copy simulated annealing, amber energy functions, and a generalized born/solvent accessibility solvation model. Proteins, 46.
Unger R and Moult J (1993) A genetic algorithm for 3d protein folding simulations. In 5th Proc. Intl. Conf. on Genetic Algorithms, pp. 581–588.
Pokarowski P, Kolinski A and Skolnick J (2003) A minimal physically realistic protein-like lattice model: Designing an energy landscape that ensures all-or-none folding to a unique native state. Biophysics Journal, 84: pp. 1518–26.
Kitagawa U and Iba H (2002) Identifying Metabolic Pathways and Gene Regulation Networks with Evolutionary Algorithms, in Evolutionary Computation in Bioinformatics, Fogel GB and Corne DW (Eds.) Morgan Kaufmann.
Shayne CG (2005), Drug Discovery Handbook, Wiley-Interscience.
Madsen U. (2002), Textbook of Drug Design and Discovery, CRC Press, USA.
Venkatasubramanian V, Chan K and Caruthers JM (1995). Evolutionary Design of Molecules with Desired Properties Using the Genetic Algorithm, J. Chem. Inf. Comp. Sci., 35, pp. 188–195.
Glen RC and Payne AWR (1995) A Genetic Algorithm for the Automated Generation of Molecule within Constraints. J. Computer-Aided Molecular Design, 9, pp. 181–202.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Das, S., Abraham, A., Konar, A. (2008). Swarm Intelligence Algorithms in Bioinformatics. In: Kelemen, A., Abraham, A., Chen, Y. (eds) Computational Intelligence in Bioinformatics. Studies in Computational Intelligence, vol 94. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-76803-6_4
Download citation
DOI: https://doi.org/10.1007/978-3-540-76803-6_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-76802-9
Online ISBN: 978-3-540-76803-6
eBook Packages: EngineeringEngineering (R0)