Survey of the use of genetic algorithm for multiple sequence alignment

  • Authors

    • Mohamed Tahar Ben Othman Computer Science Dept., College of ComputerQassim UniversityKINGDOM of SAUDI ARABIA
    2016-06-08
    https://doi.org/10.14419/jacst.v5i2.6079
  • Genetic Algorithms, Multiple Sequence Alignment, Representation Closeness, Representativeness, Sequence Invariance.

  • Abstract

    Multiple Sequence Alignment (MSA) is used in genomic analysis, such as the identification of conserved sequence motifs, the estimation of evolutionary divergence between sequences, and the genes’ historical relationships inference. Several researches were conducted to determine the level of similarity of a set of sequences. Due to the problem of the NP-complete class property, a number of researches use genetic algorithms (GA) to find a solution to the multiple sequence alignment. However, the nature of genetic algorithms makes the complexity extremely high due to the redundancy provided by the different operators. The aim of this paper is to study some proposed GA solutions provided for MSA and to compare them using some criteria which we believe any solution should comply with in matters of representativeness, closeness and original sequence invariance.

  • References

    1. [1] C. Notredame, D.G. Higgins, "SAGA: Sequence Alignment by Genetic Algorithm", Nucleic Acid Research, Vol. 24, 1515-1524, 1996 http://dx.doi.org/10.1093/nar/24.8.1515.

      [2] Kosmas Karadimitrion and Donald H. Kraft, “Genetic Algorithms and The Multiple Sequence Alignment Problem in Biologyâ€, Proceedings of the Second Annual Molecular Biology and Biotechnology Conference, Baton Rouge, LA., February 1996.

      [3] Isokawa M, Wayama M, Shimizu T, “Multiple sequence alignment using a genetic algorithmâ€, Genome Informatics, 1996, 7:176–177.

      [4] Layeb, A. ; Meshoul, S. ; Batouche, M., "Multiple sequence alignment by quantum genetic algorithm", 20th International Parallel and Distributed Processing Symposium (IPDPS), 2006, http://dx.doi.org/10.1109/IPDPS.2006.1639617.

      [5] Naznin F, Sarker R, Essam D. "Vertical decomposition with Genetic Algorithm for Multiple Sequence Alignment.", BMC Bioinformatics 2011; 12:353; PMID:21867510; http://dx.doi.org/10.1186/1471- 2105-12-353.

      [6] Naznin, F. ; Sarker , R. ; Essam, D., "Progressive Alignment Method Using Genetic Algorithm for Multiple Sequence Alignment", IEEE Transactions on Evolutionary Computation, Vol 16, Issue: 5, http://dx.doi.org/10.1109/TEVC.2011.2162849.

      [7] Pramanik, S. ; Setua, S.K., "A steady state Genetic Algorithm for Multiple Sequence Alignment", International Conference on Advances in Computing, Communications and Informatics (ICACCI), 2014, http://dx.doi.org/10.1109/ICACCI.2014.6968251.

      [8] Liu Chao ; Liu Shuai, "The research on DNA multiple sequence alignment based on adaptive immune genetic algorithm", International Conference on Electronics and Optoelectronics (ICEOE) , 2011, Vol 3, http://dx.doi.org/10.1109/ICEOE.2011.6013304.

      [9] Williams, A.C. ; Carroll, H.D. ; Wallin, J.F. ; Brusuelas, J. ; Fortson, L. ; Lamblin, A.­ F. ; Haoyu Yu, "Identification of Ancient Greek Papyrus Fragments Using Genetic Sequence Alignment Algorithms", IEEE 10th International Conference on e­ Science (e­ Science), 2014, Vol 2, http://dx.doi.org/10.1109/eScience.2014.14.

      [10] Al Junid, S.A.M. ; Reffin, M.S. ; Majid, Z.A. ; Tahir , N.M. ; Har on, M.A., "Implementation of genetic algor ithm for optimizing DNA sequence alignment", IEEE Business Engineering and Industrial Applications Colloquium ( BEIAC) , 2012. http://dx.doi.org/10.1109/BEIAC.2012.6226111.

      [11] Naznin, F. ; Sarker , R. ; Essam, D., "DGA: Decomposition with genetic algorithm for multiple sequence alignment", IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology ( CIBCB) , 2010, http://dx.doi.org/10.1109/CIBCB.2010.5510595.

      [12] Miranda, L.A. ; Caetano, M.A.F. ; Melo, A.C.M.A. ; Correa, J.M. ; Bordim, J.L., "Multiple Biological Sequence Alignment with a Parallel Island Injection Genetic Algorithm", 12th IEEE International Conference on High Performance Computing and Communications (HPCC) , 2010, http://dx.doi.org/10.1109/HPCC.2010.31.

      [13] Ben Othman, M.T. ; Abdel­ Azim, G., "Multiple sequence alignment based on genetic algorithms with new chromosomes representation", Electro-technical Conference (MELECON) , 2012 16th IEEE Mediterranean, http://dx.doi.org/10.1109/MELCON.2012.6196603.

      [14] Kumar S, Filipski A (2007) Multiple sequence alignment: In pursuit of homologous DNA positions. Genome Res 17: 127–135. http://dx.doi.org/10.1101/gr.5232407.

      [15] T. Manning, R.D. Sleator, P. Walsh, Naturally selecting solutions: The use of genetic algorithms in bioinformatics, Bioengineered 4 (2012) 266–278. http://dx.doi.org/10.4161/bioe.23041.

      [16] Amouda Nizam, Jeyakodi Ravi, and Kuppuswami Subburaya, "Cyclic Genetic Algorithm for Multiple Sequence Alignment", International Journal of Research and Reviews in Electrical and Computer Engineering (IJRRECE), Vol. 1, No. 2, June 2011.

      [17] Mohamed Tahar Ben Othman, Gamil Abdel-Azim, "Genetic Algorithms with Permutation Coding for Multiple Sequence Alignment.", Recent Patent DNA Gene Seq. 2013: 22974260, VOLUME: 7, ISSUE: 2, Page: [105 - 114], Pages: 10, http://dx.doi.org/10.2174/1872215611307020004.

  • Downloads

  • How to Cite

    Ben Othman, M. T. (2016). Survey of the use of genetic algorithm for multiple sequence alignment. Journal of Advanced Computer Science & Technology (JACST), 5(2), 28-33. https://doi.org/10.14419/jacst.v5i2.6079

    Received date: 2016-04-05

    Accepted date: 2016-05-30

    Published date: 2016-06-08