The Computer Journal, Volume 42, Issue 1, pp.1-10, 1999.

Compression and approximate matching

L. Allison, D. Powell and T. I. Dix

School of Computer Science and Software Engineering, Monash University, Australia 3168,


A population of sequences is called non-random if there is a statistical model and an associated compression algorithm that allows members of the population to be compressed, on average. Any available statistical model of a population should be incorporated into algorithms for alignment of the sequences and doing so changes the rank order of possible alignments in general. The model should also be used in deciding if a resulting approximate match between two sequences is significant or not. It is shown how to do this for two plausible interpretations involving pairs of sequences that might or might not be related. Efficient alignment algorithms are described for quite general statistical models of sequences. The new alignment algorithms are more sensitive to what might be termed 'features' of the sequences. A natural significance test is shown to be rarely fooled by apparent similarities between two sequences that are merely typical of all or most members of the population, even unrelated members.

This page should redirect in a moment, if not click the following link: Computer Journal [doi:10.1093/comjnl/42.1.1]['05] and [pdf]['05].

Also see: D. R. Powell, L. Allison, T. I. Dix, Modelling-Alignment for Non-Random Sequences, 17th ACS Australian Joint Conf. on Artificial Intelligence (AI2004), Springer-Verlag, LNCS/LNAI 3339, isbn:3-540-24059-4, pp.203-214, 2004, (including software).

The method makes the character-matching scoring function context dependent and allows "features" of sequences to be weighted appropriately.