Computer science applications of approximate string matching included spell checking and file difference testing. Edit Distance and Similarity Scores Computer scientists typically measure distance between strings x and y as the minimum number of insertions, deletions, and substitutions required to transform x to y . 1. for all x , y . 2. Biologists typically instead measure a sequence similarity score which gets larger the more similar the sequences are. Similar algorithms can be used to optimize both measures, but we will generally stick to the biological scoring convention.
Transitions are more common than transversions.
The following genetic code matrix calculates the minimum number of DNA base changes to go from a codon for i to a codon for j . Met Tyr requires all 3 positions to change. Hydrophobic residues do not want to be on the surface of a protein. This variety of possible matrix criteria make judging the significance of an alignment tricky. These were constructed by aligning very similar proteins, and tabulating how often each substitution occurred.