Abstract The concept of self-organization is applied to the operators and parameters of genetic algorithm to develop a novel Auto-poietic algorithm solving a biological problem, Multiple Sequence Alignment (MSA). The self-organizing crossover operator of the developed algorithm undergoes a swap and shuffle process to alter the genes of chromosomes in order to produce better combinations. Unlike Standard Genetic Algorithms (SGA), the mutation rate of auto-poietic algorithm is not fixed. The mutation rate varies cyclically based on the improvement of fitness value in turn, determines the termination point of algorithm. Automated assignment of various parameter values reduces the intervention and inappropriate settings of parameters from user without prior the knowledge of input. As an advantage, the proposed algorithm also circumvents the major issues in standard genetic algorithm, premature convergence and time requirements to optimize the parameters. Using Benchmark Alignment Database (BAliBASE) reference multiple sequence alignments, the efficiency of the auto-poietic algorithm is analyzed. It is evident that the performance of auto-poietic algorithm is better than SGA and produces better alignments compared to other MSA tools.

References

[1] Bao-Juan H., Jian Z., and De-Hong Y., A Novel and Accelerated Genetic Algorithm, WSEAS Transactions on Systems and Control, vol. 3, no. 4, pp. 269-278, 2008.

[2] Carroll H., Beckstead W., O'Connor T., Ebbert M., Clement M., Snell Q., and McClellan D., DNA Reference Alignment Benchmarks Based on Tertiary Structure of Encoded Proteins, Bioinformatics, vol. 23, no. 19, pp. 2648-2649, 2007.

[3] Corpet F., Multiple Sequence Alignment with Hierarchical Clustering, Nucleic Acids Research, vol. 16, no. 22, pp. 10881-10890, 1988.

[4] Djennas S., Bendimerad F., and Meriah S., Genetic Algorithm-Based Synthesis of Three- Dimensional Microstrip Arrays, The International Arab Journal of Information Technology, vol. 2, no. 3, pp. 182-190, 2005.

[5] Edgar R., MUSCLE: Multiple Sequence Alignment with High Accuracy and High Throughput, Nucleic Acids Research, vol. 32, no. 5, pp. 1792-1797, 2004.

[6] Fatumo S., Akinyemi I., and Adebiyi E., Aligning Multiple Sequence with Genetic Algorithm, International Journal of Computer Theory and Engineering, vol. 1, no. 2, pp. 179- 182, 2009.

[7] Gondro C. and Kinghorn B., A simple Genetic Algorithm for Multiple Sequence Alignment, Genetics and Molecular Research, vol. 6, no. 4, pp. 964-982, 2007.

[8] Katoh K., Misawa K., Kuma K., and Miyata T., MAFFT: A Novel Method for Rapid Multiple Sequence Alignment Based on Fast Fourier Transform, Nucleic Acids Research, vol. 30, no. 14, pp. 3059-3066, 2002.

[9] Khayat O., Ebadzadeh M., Shahdoosti H., Rajaei R., and Khajehnasiri I., A Novel Hybrid Algorithm for Creating Self-Organizing Fuzzy Neural Networks, Neurocomputing, vol. 73, no. 1, pp. 517-524, 2009. Auto-Poietic Algorithm for Multiple Sequence Alignment 849

[10] Kubota N., Fukuda T., and Shimojima K., Virus Evolutionary Genetic Algorithm for ASelf- Organizing Manufacturing System, Computers and Industrial Engineering, vol. 30, no. 4, pp. 1015-1026, 1996.

[11] Mansour N., Awad M., and El-Fakih K., Incremental Genetic Algorithm, The International Arab Journal of Information Technology, vol. 3, no. 1, pp. 42-47, 2006.

[12] Morgenstern B., Dress A., and Werner T., Multiple DNA and Protein Sequence Based on Segment-to-Segment Comparison, in Proceedings of the National Academy of Sciences, vol. 93, no. 22, pp. 12098-12103, 1996.

[13] Nizam A., Shanmugham B., and Subburaya K., Self-Organizing Genetic Algorithm for Multiple Sequence Alignment, Global Journal of Computer Science and Technology, vol. 11, no. 7, pp. 7-14, 2011.

[14] Nizam A. and Shanmugham B., Self-Organizing Multi-mutation Algorithm for Multiple Sequence Alignment, in Proceedings of 15th International Conference on Advanced Computing Technologies, Rajampet, 2013.

[15] Notredame C., Higgins D., and Heringa J., T- Coffee: A Novel Method for Fast and Accurate Multiple Sequence Alignment, Journal of Molecular Biology, vol. 302, no. 1, pp. 205-217, 2000.

[16] Notredame C., Recent Progresses in Multiple Sequence Alignment: A Survey, Pharmacogenomics, vol. 3, no. 1, pp. 131-144, 2002.

[17] Seeley T., When Is Self-Organization Used in Biological Systems?, The Biological Bulletin, vol. 202, no. 3, pp. 314-318, 2002.

[18] Thompson J., Higgins D., and Gibson T., 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, 1994.

[19] Tin os R. and Yang S., Self-Organizing Random Immigrants Genetic Algorithm for Dynamic Optimization Problems, Genetic Programming and Evolvable Machines, vol. 8, no. 3, pp. 255- 286, 2007.

[20] Wu S., Lee M., Lee Y., and Gatton T., Multiple Sequence Alignment Using GA and NN, International Journal of Signal Processing, Image Processing and Pattern Recognition, vol. 1, no. 1, pp. 21-30, 2008.

[21] Zhang J., Zhuang J., Du H., and Wang S., Self- Organizing Genetic Algorithm Based Tuning of PID Controllers, Information Sciences, vol. 179, no. 7, pp. 1007-1018, 2009. Amouda Venkatesan is currently working as an Assistant Professor in the Centre for Excellence in Bioinformatics, Pondicherry University, India. She received the master degree in Software System from BITS Pilani and Doctorate degree in Computer Science and Engineering from Pondicherry University. She has more than 12 years of teaching experience. Her principle area of interests is Genetic algorithm and published more than 25 research publications. Buvaneswari Shanmugham is pursuing Ph.D. Bioinformatics in the Centre for Excellence in Bioinformatics, Pondicherry University, India. She received her M.Sc. degree in Bioinformatics in the year 2010. She has published six research papers in International journals and conferences. Her area of research includes Genetic algorithm and Comparative genomics.