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

摘要：

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

关键词：序列复杂性、条件LZ复杂性、LZ复杂性距离、计算语言学、生物信息学

所属期刊栏目：28

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金60371046

在线出版日期：2007-06-04（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：849-854