Tree edit distance for leaf-labelled trees on free leafset and its comparison with frequent subsplit dissimilarity and popular distance measures.
Tree edit distance for leaf-labelled trees on free leafset and its comparison with frequent subsplit dissimilarity and popular distance measures.
复制标题
DOI：
10.1186/1471-2105-12-204
复制
发表时间：
2011-05-25
影响因子：
3
通讯作者：
Walczak K
中科院分区：
文献类型：
--
作者：
Koperwas J;Walczak K
本文主要研究自由叶集上标叶树的距离度量问题。叶标记树是一种数据结构，它是一种特殊类型的树，其中只标记叶(终端)节点。这种数据结构被用于生物信息学，用于模拟基因和物种的进化史，也用于语言学，用于模拟语言进化史。出现了许多特定于领域的问题，需要借助树的后处理技术(如距离度量)来解决。在这里，我们介绍了为自由叶集上的叶标记树设计的树编辑距离，它是一个度量。它与树编辑一致性树的概念一起提出。我们以R-F、MAST和基于频繁细分的相异度量为参考度量，对所提供的度量进行统计评估。树的编辑距离被证明是一种度量，具有使用不同的代价进行收缩和剪枝的优点，因此它们的性质可以根据用户的需要进行调整。其中两种方法具有最有趣的特性。E(3，1)具有很强的区分性(具有很大的取值范围)，并且具有非常规则的距离分布，其形状类似于正态分布，对于相似和不相似的树都是好的。另一方面，NFC(2，1)与所使用的突变操作的数量成比例或几乎成比例，与它们的类型无关。
This paper is devoted to distance measures for leaf-labelled trees on free leafset. A leaf-labelled tree is a data structure which is a special type of a tree where only leaves (terminal) nodes are labelled. This data structure is used in bioinformatics for modelling of evolution history of genes and species and also in linguistics for modelling of languages evolution history. Many domain specific problems occur and need to be solved with help of tree postprocessing techniques such as distance measures. Here we introduce the tree edit distance designed for leaf labelled trees on free leafset, which occurs to be a metric. It is presented together with tree edit consensus tree notion. We provide statistical evaluation of provided measure with respect to R-F, MAST and frequent subsplit based dissimilarity measures as the reference measures. The tree edit distance was proven to be a metric and has the advantage of using different costs for contraction and pruning, therefore their properties can be tuned depending on the needs of the user. Two of the presented methods carry the most interesting properties. E(3,1) is very discriminative (having a wide range of values) and has a very regular distance distribution which is similar to a normal distribution in its shape and is good both for similar and non-similar trees. NFC(2,1) on the other hand is proportional or nearly proportional to the number of mutation operations used, irrespective of their type.
影响因子：
2
作者：
FINDEN, CR;GORDON, AD
通讯作者：
GORDON, AD
影响因子：
4.3
作者：
ROBINSON, DF;FOULDS, LR
通讯作者：
FOULDS, LR
影响因子：
6.5
作者：
STEEL, MA;PENNY, D
通讯作者：
PENNY, D