Tree edit distance for leaf-labelled trees on free leafset and its comparison with frequent subsplit dissimilarity and popular distance measures

Jakub Janusz Koperwas , Krzysztof Walczak


Background: 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. Results: 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. Conclusions: 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.
Author Jakub Janusz Koperwas (FEIT / IN)
Jakub Janusz Koperwas,,
- The Institute of Computer Science
, Krzysztof Walczak (FEIT / IN)
Krzysztof Walczak,,
- The Institute of Computer Science
Journal seriesBMC Bioinformatics, (A 35 pkt)
Issue year2011
Keywords in Polish-
Keywords in English-
ASJC Classification2604 Applied Mathematics; 1706 Computer Science Applications; 1312 Molecular Biology; 1303 Biochemistry; 1315 Structural Biology
Abstract in Polish-
ProjectDevelopment of new methods and algorithms in the following areas: computer graphics, artificial intelligence, and information systems; and distributed systems. Project leader: Rybiński Henryk, , Phone: +48 22 234 7731, start date 24-06-2010, planned end date 31-12-2010, end date 30-11-2011, II/2010/DS/1, Completed
WEiTI Działalność statutowa
Languageen angielski
koperwas-walczak.pdf 483.27 KB
Score (nominal)35
Score sourcejournalList
Publication indicators Scopus Citations = 2; WoS Citations = 2; Scopus SNIP (Source Normalised Impact per Paper): 2011 = 1.196; WoS Impact Factor: 2011 = 2.751 (2) - 2011=3.493 (5)
Citation count*5 (2020-02-23)
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Are you sure?