Global alignment is a means of showing the similarities and differences of two or more sequences, compared along their entire length.
Keywords: Needleman–Wunsch algorithm; score; gap penalty; dynamic programming
Global Alignment
Joao Meidanis, University of Campinas, Campinas, Brazil
Published online: September 2005
DOI: 10.1038/npg.els.0005256
|
Figure 1. Spreadsheet representation of a dynamic programming matrix for the comparison of TACAGTC and TACAGC.
|
| References | |
| Carrilo H and Lipman D (1988) The multiple sequence alignment problem in biology. SIAM Journal on Applied Mathematics 48: 1073–1082. | |
| book Dayhoff M, Schwartz RM and Orcutt BC (1978) "A model of evolutionary change in proteins". In: Dayhoff M (ed.) Atlas of Protein Sequence and Structure, supplement 3, pp. 345–352. Silver Spring, MD: National Biomedical Research Foundation. | |
| Feng D and Doolittle R (1987) Progressive sequence alignment as a prerequisite to correct phylogenetic trees. Journal of Molecular Evolution 25: 351–360. | |
| Gupta SK, Kececioglu J and Schäffer AA (1995) Improving the practical space and time efficiency of the shortest-paths approach to sum-of-pairs multiple sequence alignment. Journal of Computational Biology 2: 459–472. | |
| Henikoff S and Henikoff JG (1992) Amino acid substitution matrices from protein blocks. Proceedings of the National Academy of Sciences of the United States of America 89: 10915–10919. | |
| Hirschberg D (1975) A linear space algorithm for computing maximal common subsequences. Communications of the Association for Computing Machinery 18: 341–343. | |
| Myers EW and Miller W (1988) Optimal alignments in linear space. Computer Applications in the Biosciences 41: 11–17. | |
| Needleman SD and Wunsch CD (1970) A general method applicable to the search for similarities in the amino acid sequences of two proteins. Journal of Molecular Biology 48: 443–453. | |
| Thompson JD, Higgins DG and Gibson TJ (1994) CLUSTAL W: 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. | |
| Further Reading | |
| book Gusfield D (1997) "Part III: inexact matching, sequence alignment, dynamic programming". Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, pp. 209–392. New York, NY: Cambridge University Press. | |
| book Pevzner P (2001) Computational Molecular Biology: an Algorithmic Approach, chaps 6 and 7, pp. 93–132. Cambridge, MA: MIT Press. | |
| book Setubal JC and Meidanis J (1997) "Sequence comparison and database search". Introduction to Computational Molecular Biology, chap. 3, pp. 47–104. Boston, MA: PWS Publishing. | |
| book Waterman MS (1995) Introduction to Computational Biology: Maps, Sequences, and Genomes, chaps 9 and 10, pp. 183–252. Cambridge, UK: Chapman & Hall. | |
| Web Links | |
| ePath European Bioinformatics Institute (EBI). Global (and local) pairwise alignment web server www.ebi.ac.uk/emboss/align/ | |
| ePath Institut de Génétique Humaine (IGH). Global pairwise alignment web server xylian.igh.cnrs.fr/bin/align-guess.cgi | |
| ePath Michigan State University (MTU). Pairwise alignment web server with several oprions genome.cs.mtu.edu/align/align.html | |
| ePath University of Southern California (USC). Pairwise alignment web server with several oprions www-hto.usc.edu/software/seqaln/ | |
