符号序列间的LZ复杂性距离及其应用

LZ Complexity Distance of Symbol Sequences and its Application

在符号序列LZ复杂性的计算原理上,提出了序列间条件LZ复杂性的概念.基于条件LZ复杂性,定义了一个非空序列间的LZ复杂性距离并证明了该距离满足距离测度的4个基本性质.将LZ复杂性距离应用于计算语言学和生物信息学的研究领域,选取20种自然语言文本和29种有胎盘哺乳动物的全线粒体基因组,将它们视为不同符号集上的符号序列,分别计算两类符号序列的LZ复杂性距离矩阵.基于LZ复杂性距离矩阵,重构了20种语言的语言关系树和29种哺乳动物的系统进化树.其结果符合它们真实的演化关系,说明了LZ复杂性距离定量刻画符号序列间差异的有效性.

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.