{"references": ["N. M. Luscombe, D. Greebaum, M. Gerstein, (2001). What is\nbioinformatics? A proposed definition and overview of the field.\nDepartment of Molecular Biophysics and Biochemistry, Yale University,\nUSA.", "R. Musick, T. Slezak, T. Crithlow, (2001). An Overview of\nBioinformatics Research at Lawrence Livermore National Laboratory.\nJoint Genome Institute / Computing Application Organization .Lawrence\nLivermore National Laboratory.", "Online Lectures on Bioinformatics (September 2003) (Online),\nAvailable: http://lectures.molgen.mpg.de/Biol/index.html.", "P. C. Turner, A. G. McLennan, A. D Bates, M. R. H. White, (1997).\nNucleic Acid Structure. Instant Notes in Molecular Biology C1:31-35.\nBios Scientific Publishers Limited, Liverpool.", "M. Tompa .(2000). Lecture Notes on Biological Sequence Analysis.\nTechnical Report #2000-06-01.Department of Computer Science and\nEngineering, University of Washington.", "W. Zhong(2003). Using Travel Salesman Problem Algorithms To\ndetermine Multiple Sequence Alignment Orders. Master Thesis,\nUniversity of Georgia: Athens, Georgia.", "C. Karostensky, G. Gonnet. Near Optimal Multiple Sequence Alignment\nusing a Traveling Salesman Problem approach. Swiss Federal Institute\nof Technology, Institute of Scientific Computing. ETH Zurich,\nSwitzerland (2000).", "R. Choudry, (1999). Application of Evolutionary Algorithms for Multiple\nSequence Alignment. Stanford University.", "D. J. Lipman, S. F. Altschul, J. D. Kececioglun, (1989). A tool for\nMultiple Sequence Alignment. Vol. 86.pp 4412-4415, Biochemistry.\nProc. Natl. Acad. Sci. USA.\n[10] M. Gribskov, J. Devereux, (1991). Similarity and Homology. Sequence\nAnalysis Primer.3: 89-157. Stockton Press. NY.\n[11] C. Notredame, (2002). Recent Progress in Multiple Sequence Alignment:\nA Survey., Pharmacogenomics, 3(1):131-144.\n[12] D. Higgins, (1999). Multiple Sequence Alignment. Genetics\nDatabases.9:165-183 Academic Press, London, UK .\n[13] J. D. Thompson, F. Plewniak, and O. Poch. (1999). A comprehensive\ncomparison of multiple sequence alignment programs. Nucleic Acids\nResearch, 27(13):2682-2690.\n[14] Introduction to hidden markov models (June 2003) (Online), Available: www.scs.leeds.ac.uk/scsonly/teachingmaterials/HiddenMarko\nvModels/html dev/main.html.\n[15] Introduction to HMM (April 2003) (Online) Available:\nhttp://www.cs.brown.edu/research/ai/dynamics/tutorial/Documents/Hidd\nenMarkovModels.html.\n[16] S. R. Eddy, (1998). Profile Hidden Markov Models. Bioinformatics\nReview. Vol. 14. 9: 755-763. Oxford University Press.\n[17] P. Baldi, S. Brunak, Y. Chauven, A. Krogh (1997). Hidden Markov\nModel For Human Genes: Periodic Pattern in Exon Sequence.\nTheoretical and Computational Methods in Genome Research, 2: 15-32.\nPlenum Press, New York.\n[18] S. R. Eddy, (1996). Multiple Alignment Using Hidden Markov Models.\nDept. of Genetics, Washington University School of Medicine St. Louis,\nUS.\n[19] M. Gen, R. Cheng. (2000). Genetic Algorithms and Engineering\nOptimization. John Wiley & Sons: Canada.\n[20] D. Beasley, D. R. Bull, R. R. Martin, (1993). An Overview of Genetic\nAlgorithms: Part 1, Fundamentals. Inter-University Committee on\nComputing. 15(2) 58-69. [21] CCS 501 Neural Network and Genetic\nAlgorithm http:// office1.cs.usm.my.\n[21] C. Notredame, and D. G. Higgins, (1996). SAGA: sequence alignment\nby genetic algorithm, Nuc. Acids Res., 24(8), 1515-1524.\n[22] M. Isokawa, M. Wayama, T. Shimizu, (1996). Multiple Sequence\nAlignment using Genetic Algorithm. Department of Information Science,\nFaculty of Science, Hirosaki University, Japan.\n[23] J. T. Horng, C. N. Lin, B. H. Yang, and C. Y. Kao, (2001). A genetic\nalgorithm for multiple sequence alignment. In Poster in German\nConference on Bioinformatics.\n[24] S. Kirkpatrick, C. D. J. Gellat, and M. P. Vecchi, (1983). Optimization\nby Simulated Annealing, Science, 220 pp. 671-680."]}

Proteins or genes that have similar sequences are likely to perform the same function. One of the most widely used techniques for sequence comparison is sequence alignment. Sequence alignment allows mismatches and insertion/deletion, which represents biological mutations. Sequence alignment is usually performed only on two sequences. Multiple sequence alignment, is a natural extension of two-sequence alignment. In multiple sequence alignment, the emphasis is to find optimal alignment for a group of sequences. Several applicable techniques were observed in this research, from traditional method such as dynamic programming to the extend of widely used stochastic optimization method such as Genetic Algorithms (GAs) and Simulated Annealing. A framework with combination of Genetic Algorithm and Simulated Annealing is presented to solve Multiple Sequence Alignment problem. The Genetic Algorithm phase will try to find new region of solution while Simulated Annealing can be considered as an alignment improver for any near optimal solution produced by GAs.