Global Alignment

Abstract

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

Figure 1.

Spreadsheet representation of a dynamic programming matrix for the comparison of TACAGTC and TACAGC.

close

References

Carrilo H and Lipman D (1988) The multiple sequence alignment problem in biology. SIAM Journal on Applied Mathematics 48: 1073–1082.

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

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.

Pevzner P (2001) Computational Molecular Biology: an Algorithmic Approach, chaps 6 and 7, pp. 93–132. Cambridge, MA: MIT Press.

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.

Waterman MS (1995) Introduction to Computational Biology: Maps, Sequences, and Genomes, chaps 9 and 10, pp. 183–252. Cambridge, UK: Chapman & Hall.

Web Links

European Bioinformatics Institute (EBI). Global (and local) pairwise alignment web server www.ebi.ac.uk/emboss/align/

Institut de Génétique Humaine (IGH). Global pairwise alignment web server xylian.igh.cnrs.fr/bin/align‐guess.cgi

Michigan State University (MTU). Pairwise alignment web server with several oprions genome.cs.mtu.edu/align/align.html

University of Southern California (USC). Pairwise alignment web server with several oprions www‐hto.usc.edu/software/seqaln/

Contact Editor close
Submit a note to the editor about this article by filling in the form below.

* Required Field

How to Cite close
Meidanis, Joao(Sep 2005) Global Alignment. In: eLS. John Wiley & Sons Ltd, Chichester. http://www.els.net [doi: 10.1038/npg.els.0005256]