Keywords
harmony search
hybrid metaheuristic
simulated annealing
alineamiento múltiple de secuencias
búsqueda de la armonía
metaheurística híbrida
recocido simulado
How to Cite
Abstract
In this paper we developed a new algorithm for solving the problem of multiple sequence alignment (AMS), which is a hybrid metaheuristic based on harmony search and simulated annealing. The hybrid was validated with the methodology of Julie Thompson. This is a basic algorithm and and results obtained during this stage are encouraging.
References
Agüero, F. (2004) “Alineamiento de secuencias. Búsqueda de secuencias en bases de datos”, en:
http://brucella.unsam.edu.ar/bioinformatica2004/sss-msa.ppt, Instituto de Investigaciones Biotecnológicas, Universidad Nacional de General San Martín. Consultado 1/10/2008 8:30 p.m.
Altschul, S.F.; Erickson, B.W. (1986) “Optimal sequence alignment using affine gap cost”, Bulletin of Mathematical Biology bf 48(5-6): 603–616.
Barton, G.J.; Sternberg, M.J.E. (1987) “A strategy for the rapid multiple alignment of protein sequences”, Journal Molecular Biology 198(2): 327–337.
Chan, S.C.; Wong, K.C.; Chiu, D.K. (1992) “A survey of multiple sequence comparison methods”, Bulletin of Mathematical Biology 54(4): 563–598.
Dong, E.; Smith, J.; Heinze, S.; Nathan, A.; Meiler, J. (2008) “BCL: Align-Sequence alignment and fold recognition with a custom scoring function online”, Gene 422(1-2): 41–46.
Elias, I. (2003) “Settling the intractability of multiple alignment”, in: T. Ibaraki, N. Katoh & H. Ono (Eds.) Proc. 14th Annual Int. Symp. on algorithms and computation (ISSAC), Springer-Verlag Berlin Heidelberg: 352–363.
Geem, Z.W.; Kim, J.H.; Loganathan, G.V. (2001) “A new heuristic optimization algoritm: harmony search”. Simulation 76(2): 60–68.
Grimaldi, R.P. (1998) Matemticas Discretas y Combinatorias. Una Introduccin con Aplicaciones, Tercera Edición. Pearson Printice Hall, México.
Gusfield, D. (1993) “Efficient methods for multiple sequence alignment with guaranteed error bounds”, Bulletin of Mathematical Biology 55(1): 141–154.
Ingram G.; Zhang, T. (2009) “Overview of applications and developments in the harmony search algorithm”, in: Z.W. Geem (Ed.) Music-Inspired Harmony Search Algorithm. Theory and Applications, Studies in Computational Intelligence 191, Springer, Berlin: 15–37.
Lee, R.C.T.; Tseng, S.S.; Chang, R.C.; Tsai, Y.T. (2007) Introduccin al Diseo y Anlisis de Algoritmos. Un Enfoque Estratgico. Mc Graw-Hill, México.
Ma, B.; Wang, L.; Li, M. (2007) “Near optimal multiple alignment within a band in polynomial time”, Journal of Computer and System Sciences 73(6): 997–1011.
Manthey, B.(2003) “Non-approximability of weighted multiple sequence alignment”, Theoretical Computer Science 296(1): 179–192.
Mora-Gutiérrez, R.A. (2009) Desarrollo de un Procedimiento para Solucionar el Problema de Alineamiento Múltiple de Secuencias. Tesis de Maestría en Ingeniería, Universidad Nacional Autónoma de México.
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(3): 443–453.
Notredame, C. (2000) “T-coffee: a novel method for fast and accurate multiple sequence alignment”, Journal of Molecular Biology 302(1): 205–217.
Omar, M.F.; Salam, R.A.; Abdullah, R.; Rashid, N.A. (2005) “Multiple sequence alignment using optimization algorithms”, International Journal of Computational Intelligence 1(2): 81–89.
Rech, D.H.; Pilatti, R.(2004) Align-UMA ferramenta para alinhamento múltiplo de seqüencias de DNA e proteínas. Tesis en Ciencias de la Computación, Universidade Federal de Santa Catarina, Brazil.
Thompson, J.D.; Plewnlak, F.; Poch, O. (1999) “BALiBASE: A benchmark aligment database for the evaluatios of multiple alignmet programs”, Bioinformatics 15(1): 87–88.
Wang, Y.; Li, K.B. (2004) “An adaptive and iterative algorithm for refining multiple sequence alignment”, omputational Biology and Chemistry 28(2): 141–148.
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(1): 55–78.