Normalized Information Distance and Whole Mitochondrial Genome Phylogeny Analysis

A new class of similarity measures aimed at measuring the evolutionary relation of sequences is studied. A prime example is the ``normalized information distance'', based on the noncomputable notion of Kolmogorov complexity. We demonstrate that it is a metric, takes values in $[0,1]$, and is universal. To apply it (and some related metrics) we use a simple approximation scheme to computationally compare whole mitochondrial genomes and infer their evolutionary history. This results in a first completely automatic computed whole mitochondrial phylogeny tree.