Mastering Python for Bioinformatics

Chapter 6. Finding the Hamming Distance: Counting Point Mutations

The Hamming distance, named after the same Richard Hamming mentioned in the Preface, is the number of edits required to change one string into another. It’s one metric for gauging sequence similarity. I have written a couple of other metrics for this, starting in Chapter 1 with tetranucleotide frequency and continuing in Chapter 5 with GC content. While the latter can be practically informative as coding regions tend to be GC-rich, tetranucleotide frequency falls pretty short of being useful. For example, the sequences AAACCCGGGTTT and CGACGATATGTC are wildly different yet produce the same base frequencies:

$ ./dna.py AAACCCGGGTTT
3 3 3 3
$ ./dna.py CGACGATATGTC
3 3 3 3

Taken alone, tetranucleotide frequency makes these sequences seem identical, but it’s quite obvious that they would produce entirely different protein sequences and so would be functionally unlike. Figure 6-1 depicts an alignment of the 2 sequences indicating that only 3 of the 12 bases are shared, meaning they are only 25% similar.

Figure 6-1. An alignment of two sequences with vertical bars showing matching bases

Another way to express this is to say that 9 of the 12 bases need to be changed to turn one of the sequences into the other. This is the Hamming distance, and it’s somewhat equivalent in bioinformatics to single-nucleotide polymorphisms ...