Dada uma colecção de genomas, será possivel derivar a sua evolução histórica? E considerando-se antes uma colecção de linguagens? Ou uma colecção de partituras de musica? Mais genéricamente, dada uma colecção de sequências, será possivel agrupa-las concenientemente? Existirá alguma medida independente da aplicação que sirva para todos estes exemplos?

Resultados recentes em bioinformática e teoria da conputação parecem indicar que sim. Estes são motivados em observações na teoria da complexidade de Kolmogorov mas, de uma forma prática, podem ser sistemas simples podem ser concretizados em poucas linhas de código usando um compressor de dados off-the-shelf.

De uma forma sucinta, estes trabalhos assentam em duas grandes ideias:

Ming Li: A distância entre duas strings x e y pode ser definida como K(x|y) + K(y|x) ] / K(x,y) onde K(x|y) é a complexidade de Kolmogorov de x, dado y como informação auxiliar.

Keogh et al: A distância entre duas strings é C(xy)/[ C(x) + C(y) ] onde C(x) é o comprimento da string x comprimida.

Ficam os links para dois artigos bem interessantes:

Towards Parameter-Free Data Mining
The Similarity Metric