Palabras clave
harmony search
hybrid metaheuristic
simulated annealing
alineamiento múltiple de secuencias
búsqueda de la armonía
metaheurística híbrida
recocido simulado
Cómo citar
Resumen
En el presente trabajo se desarrolló un nuevo algoritmo para resolver el problema de alineamiento múltiple de secuencias (AMS) que es un híbrido basado en las metaheurísticas de búsqueda de armonía (HS) y recocido simulado (RS). Este fue validado con la metodología de Julie Thompson. Es un algoritmo básico y los resultados obtenidos durante esta etapa son alentadores.
Citas
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.