LZ Complexity Distance of Symbol Sequences and its Application
According to the principle of LZ complexity measure of symbol sequence, the concept of conditional LZ complexity between two sequences was proposed. An LZ complexity distance metric between two non-null sequences was defined by utilizing conditional LZ complexity, the proposed distance was proofed to satisfy the four basic rules of a distance metric as well. Applications of LZ complexity distance in research fields of computational linguistics and bioinformatics were introduced then. Regarded as symbol sequences over different alphabets, texts of 20 natural languages and complete mitochondrial genomes of 29 Eutherian animals were applied to calculate two LZ complexity distance matrices respectively. The evolutional tree of these 20 languages and the phylogenetic tree of these 29 animals were reconstructed based on the two LZ complexity distance matrices. Results showed high correspondence to their real evolution as well as the validity of LZ complexity distance in quantitatively detecting dissimilarities between symbol sequences.