Cilibrasi's "Statistical Inference through Data Compression" is pretty cool. One nice application was using compression to infer the mutual-information between DNA from different animals, and using that to construct evolutionary trees.

Edit: I see your arxiv link is to the same thing (although I have a hard-copy of the book based on their thesis, so didn't spot it immediately)