SOGA: space oriented genetic algorithm for multiple sequence alignment

  • Authors

    • Ruchi Gupta
    • Pankaj Agarwal
    2018-09-22
    https://doi.org/10.14419/ijet.v7i4.5.21138
  • Genetic Algorithm, Crossover, Mutation, Selection, Multiple Sequence Alignment.

  • Multiple sequence alignment is one of the recurrent assignments in Bioinformatics. This method allows organizing a set of molecular sequences in order to expose their similarities and their differences. Although several applicable techniques were observed in this re- search, from traditional method such as dynamic programming to the extent of widely used stochastic optimization method such as Simu- lated Annealing and motif finding for solving this problem, their use is limited by the computing demands which are necessary for ex- ploring such a large and complex search space. This paper presents a new genetic algorithm, namely SOGA (Space Oriented Genetic Algorithm for Multiple Sequence Alignment), which has two new mechanisms: the first generates the population with randomly inserting the space between the selected sequences and the second applying new crossover and mutation operator, within an iterative process, to generate new and better solutions. This method is simple and fast. Its performance will further be tested on standard benchmark databas- es and will be compared with well-known algorithms. However, as its solutions clears that there is scope for further improvement.

     

  • References

    1. [1] Mount, D. W.: Bioinformatics: Sequence and Genome Analysis.ColdSpring Harbor Laboratory Press, vol.23. , 2001, pp.134-156.

      [2] Needleman, S. B. and Wunsch, C. D.: A general method applicable to the search for similarity in the amino acid sequences of two pro- teins. Journal of Molecular Biology, vol. 48, 1970, pp. 443-453.

      [3] Isokawa, M., Wayama, M. and Shimizu, T.: Multiple sequence alignment using a genetic algorithm. Genome Informatics, vol. 7, 1997, pp. 176–177.

      [4] Wayama, W., Takahashi, K. and Shimizu, T.: An approach to amino acid sequence alignment using a genetic algorithm. Genome Infor- matics, vol. 6, 1995, pp. 122–123.

      [5] Notredame, C. and Higgins, D. G.: SAGA: Sequence alignment by genetic algorithm. Nucleic Acids Res., vol. 24, 1996, pp. 1515–1524.

      [6] Agarwal, P. and Gupta, R.: A Genetic Algorithm for Alignment of Multiple DNA Sequences. CNC, 2012, pp. 437–443.

      [7] Gondro, C. and Kinghorn, B. P.: A simple genetic algorithm for multiple sequence alignment. Genetic and Molecular Res. vol. 6, 2007, pp. 964- 982.

      [8] Thompson, J. D., Higgins, D.G. and Gibson, T. J.: CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucleic Acids Res. vol. 22, 1994, pp. 4673- 4680.

      [9] Lamiche, C and Moussaoui A.: An Adaptive Tabu Search Algorithm for Obtaining Alignment of Multiple Sequences. Baltic J. Modern Computing, Vol. 2, No-2, 2014, pp.75-83.

      [10] Lamiche, C and Moussaoui A.: A Hybrid Method Applied to Mul- tiple Sequence Alignment Problem. WSEAS Transactions on com- puters, Vo.14, 2014, pp.2224-2872.

      [11] Horng, J.T., Lin, E.M., Yang, B.H., Kao, E.Y.: A Genetic Algorithm for Multiple Sequence Alignment. In Proceeding of GCB.,2001.

      [12] Liu, D., Xiong, X., Hou, Z., Gupta B.D.: Identification of Motifs with Insertions and Deletions in Protein Sequences using Self- organizing Neural Networks. Neural Networks, vol. 18, 2005, pp. 835-842.

      [13] Wayama M., Takahashi K., and Shimizu T.: An Approach to Amino Acid Sequence Alignment Using A Genetic Algorithm. Genome In- formatics, vol. 6, 1995, pp 122–123.

      [14] Wu S, Lee M, Gatton, TM. : Multiple Sequence Alignment using GA and NN. International Journal of Signal Processing. Image Processing and Pattern Recognition, 2002, pp. 21-30.

      [15] Hong, T., Wang, H., Lin, W., Lee, W.: Evolution of Appropriate Crossover and Mutation Operators in a Genetic Process. Applied In- telligence, 16, vol. 16, 2002, pp.1-7.

      [16] Sivanandam, S.N., Deepa, S.N.: Introduction to Genetic Algorithms.Springer, 2008.

      [17] Sankar, K. and Paul, P.: Genetic algorithms for pattern recognition. CRC Press, Boca Raton, 1996.

  • Downloads

  • How to Cite

    Gupta, R., & Agarwal, P. (2018). SOGA: space oriented genetic algorithm for multiple sequence alignment. International Journal of Engineering & Technology, 7(4.5), 481-484. https://doi.org/10.14419/ijet.v7i4.5.21138