Heurística para Solucionar el Problema Alineamiento Múltiple de Secuencias

• Mora Gutiérrez, Roman Anselmo ^[1] ; Ramírez Rodriguez, Javier ; Elizondo Cortéz, Mayra ^[1]
  1. [1] Universidad Nacional Autónoma de México

     Universidad Nacional Autónoma de México

     México

     
• Localización: Revista de Matemática: Teoría y Aplicaciones, ISSN 2215-3373, ISSN-e 2215-3373, Vol. 18, Nº. 1, 2011, págs. 121-136
• Idioma: español
• DOI: 10.15517/rmta.v18i1.2118
• Títulos paralelos:
  • Heuristic for Solving the Multiple Alignment Sequence Problem
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    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.

  • English

    In this paper we developed a new algorithm for solving the problem of multiple sequence alignment (AM S), 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.

• Referencias bibliográficas
  • 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...
  • 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):...
  • 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...
  • Elias, I. (2003) “Settling the intractability of multiple alignment”, in: T. Ibaraki, N. Katoh & H. Ono (Eds.) Proc. 14th Annual Int....
  • 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):...
  • Ingram G.; Zhang, T. (2009) “Overview of applications and developments in the harmony search algorithm”, in: Z.W. Geem (Ed.) Music-Inspired...
  • 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,...
  • Ma, B.; Wang, L.; Li, M. (2007) “Near optimal multiple alignment within a band in polynomial time”, Journal of Computer and System Sciences...
  • 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...
  • Needleman, S.B.; Wunsch, C.D. (1970) “A general method applicable to the search for similarities in the amino acid sequence of two proteins”,...
  • 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...
  • 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,...
  • Thompson, J.D.; Plewnlak, F.; Poch, O. (1999) “BALiBASE: A benchmark aligment database for the evaluatios of multiple alignmet programs”,...
  • Wang, Y.; Li, K.B. (2004) “An adaptive and iterative algorithm for refining multiple sequence alignment”, omputational Biology and Chemistry...
  • 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”....