A Novel Bio-Geography Based Approach for Multiple Sequence Alignment
Article Sidebar
Section
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Main Article Content
Abstract
In this paper, an improved Biogeography Based Optimization (BBO) is applied for aligning multiple sequences. Biogeography Based Optimization is a nature inspired technique which is based on species migration one to other habitat due to climate. Here we used improve migration operator in place of conventional migration operator. However, there are some deficiencies in solving complicated problems, due to low population diversity and slow convergence speed in the later stage. To overcome these drawbacks, we propose an improved BBO algorithm integrating a new improved migration operator. The improved migration operator simultaneously adopts more information from other habitats, maintains population diversity and preserves exploitation ability. The performance of the proposed method has been tested on publicly available benchmark datasets (i.e. Bali base) with some of the existing methods such as VDGA, MOMSA and GAPAM. It has been observed that, the proposed method perform better and/or competitive in most of the cases.
Article Details
References
[1] Bahr, A., Thompson, J.D., Thierry, J.C., (2001):Poch, O; Bali base (benchmark alignment database): enhancements for repeats, transmembrane sequences and circular permutations. Nucleic Acids Research. 29,323- 326.
[2] Bonizzoni, P., Della Vedova, G., (2001): The complexity of multiple sequence alignment with sp-score that is a metric. Theoretical Computer Science.259,63-79.
[3] Cai, L., Juedes, D., Liakhovitch, E.: Evolutionary computation techniques for multiple sequence alignment. In, (2000): Evolutionary Computation Proceedings of the Congress.829-835.
[4] Carrillo, H., Lipman, D., (1988) : The multiple sequence alignment problem in biology. SIAM Journal on Applied Mathematics.48, 1073 1082.
[5] Chellapilla, K., Fogel, G.B., (1999): Multiple sequence alignment using evolutionary programming. In: Evolutionary Computation CEC Proceedings of the Congress.
[6] Day hoff, M.O., Schwartz, R.M., (1978) : A model of evolutionary change in proteins. In: In Atlas of protein sequence and structure.
[7] Eddy, S.R.:, (1995) Multiple alignment using hidden markov models.3,114-120.
[8] Feng, D., Johnson, M., Doolittle, R, (1985) .:0 Aligning amino acid sequences: comparison of commonly used methods .Journal of Molecular Evolution 21: 112-125.
[9] Feng, D.F., Doolittle, R.F., (1987): Progressive sequence alignment as a prerequisitetto correct phylogenetic trees. Journal of molecular
evolution.25,351-360.
[10] Gondro, C., Kinghorn, B., (2007): A simple genetic algorithm for multiple sequence alignment. Genetics and Molecular Research.6,964-982.
[11] Gus field, D., (1997): Algorithms on strings, trees and sequences computer science.
[12] Horng, J.T., Lin, C.M., Liu. B.J., Kao, C.Y., (2000) ;Using genetic algorithms to solve multiple sequence alignments. In: GECCO.
[13] Ishikawa, M., Toya, T., Totoki, Y., Konagaya, A. (1993): Parallel iterative aligner with genetic algorithm. Genome Informatics.4,84-93.
[14] Kim, J., Pramanik, S., Chung, M.J., (1994): Multiple sequence alignment using simulated annealing. Computer applications in the biosciences: CABIOS.10,419-426.
[15] Lee, Z.J., Su, S.F., Chuang, C.C., Liu, K.H., (2008): Genetic algorithm with ant colony optimization (ga-aco) for multiple sequence
alignment. Applied Soft Computing.8,55-78.
[16] Lukashin, A.V., Engelbrecht, J., Brunak, S., (1992):Multiple alignment using simulated annealing: branch point definition in human mrna splicing. Nucleic acids research.20,2511-
2516.
[17] Needleman, S.B., Wunsch, C.D. (1970): A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of molecular biology.48,443-
453.
[18] Notredame, C., Higgins, D.G., (1996): Saga: sequence alignment by genetic algorithm. Nucleic acids research.24, 1515-1524.
[19] Simon, D.: Biogeography-based optimization. IEEE Trans Evol Comput.12,702–713(2008)
[20] Shyu, C., Sheneman, L., (2004) : Foster, J.A; Multiple sequence alignment with evolutionary computation. Genetic Programming and
Evolvable Machines.5,121-144.
[21] Taheri, J., Zomaya, A.Y. ,(2009): Rbt-ga: a novel metaheuristic for solving the multiple sequence alignment problem. Bmc Genomics.10.
[22] Taheri, J., Zomaya, A.Y., (2010): Rbt-l: A location based approach for solving the multiple sequence alignment problem. International journal of bioinformatics research and applications.6,37-57.
[23] Taheri, J., Zomaya, A.Y., Zhou, B.B. .(2008)
[24] : RBT-L: A Location Based Approach for Solving the Multiple Sequence Alignment Problem. School of Information Technologies, University of Sydney.
[25] Taylor, W.R., (1988) : A flexible method to align large numbers of biological sequences. Journal of Molecular Evolution.28,161-169.
[26] Thompson, J.D., Higgins, D.G., Gibson, T.J.: Clustal w, (1994): improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucleic acids research.22,4673-4680.
[27] Thompson, J.D., (1999): Plewniak, F., Poch, O.: Balibase: a benchmark alignment database for the evaluation of multiple alignment programs. Bioinformatics.15,87-88.
[28] Naznin, F., Sarker, R., Essam, D., (2012) : Progressive Alignment Method Using Genetic Algorithm for Multiple Sequence Alignment. IEEE Transaction on Evolutionary Computation.16,615-631.
[29] Naznin, F., Sarker, R., and Essam, D., (2011): Vertical decomposition with Genetic Algorithm for Multiple Sequence Alignment. BMC
Bioinformatics.12,353.
[30] Zhu, H., He, Z., and Jia, Y., (2015): A Novel Approach to Multiple Sequence Alignment Using Multi-objective Evolutionary Algorithm Based on Decomposition. IEEE Journal of Biomedical and Health Informatics. 1-11.