During the last three decades a considerable effort has been made to
develop algorithms that compare sequences of macromolecules (proteins,
DNA). The purpose of such algorithms is to detect evolutionary,
structural and functional relations among the sequences. Successful
sequence comparison would allow to infer the biological properties of
new sequences from data accumulated on related genes.
For example, a similarity between a translated nucleotide sequence and
a known protein sequence suggests a homologous coding
region in the corresponding nucleotide sequence.  Significant sequence
similarity among proteins may imply that the proteins share the same
secondary and tertiary structure, and have close biological functions.
The prediction of unknown protein structures is often based on the
study of known structures of homologous proteins.

This chapter is a survey of sequence comparison, scoring schemes, and
the statistics of sequence alignments which are essential for the
purpose of distinguishing true relations among proteins from chance
similarities. The chapter is based on books by M. Waterman [1995] and
by Setubal and Meidanis [1996], as well as on various papers in this
field.