The similarity metric
The similarity metric
复制标题
DOI：
10.1109/tit.2004.838101
复制
发表时间：
2004-12-01
影响因子：
2.5
通讯作者：
Vitányi, PMB
中科院分区：
文献类型：
--
作者：
Li, M;Chen, X;Vitányi, PMB
研究了一种新的适合于度量序列间相似关系的距离，即每种距离对应一种类型的相似性。我们提出了一个新的“归一化信息距离”，基于不可计算的概念Kolmogorov复杂性，并表明，它是在这个类中，它minorizes类中的每一个可计算的距离（也就是说，它是普遍的，因为它发现了所有可计算的相似性）。我们证明它是一个度量，并称之为相似性度量。这一理论构成了一种新的实用工具的基础。为了证明通用性和鲁棒性，我们给出了两个不同的应用程序，在广泛不同的领域使用标准的压缩程序，如gzip和GenCompress。首先，我们比较整个线粒体基因组并推断它们的进化历史。这导致第一个完全自动计算的完整线粒体同源树。其次，我们完全自动计算52种不同语言的语言树。
A new class of distances appropriate for measuring similarity relations between sequences, say one type of similarity per distance, is studied. We propose a new "normalized information distance," based on the noncomputable notion of Kolmogorov complexity, and show that it is in this class and it minorizes every computable distance in the class (that is, it is universal in that it discovers all computable similarities). We demonstrate that it is a metric and call it the similarity metric. This theory forms the foundation for a new practical tool. To evidence generality and robustness, we give two distinctive applications in widely divergent areas using standard compression programs like gzip and GenCompress. First, we compare whole mitochondrial genomes and infer their evolutionary history. This results in a first completely automatic computed whole mitochondrial phylogeny tree. Secondly, we fully automatically compute the language tree of 52 different languages.