{"id":891,"date":"2011-06-22T11:08:46","date_gmt":"2011-06-22T10:08:46","guid":{"rendered":"http:\/\/www.monkeyshines.co.uk\/blog\/?p=891"},"modified":"2012-02-23T14:20:55","modified_gmt":"2012-02-23T14:20:55","slug":"tree-comparison","status":"publish","type":"post","link":"https:\/\/monkeyshines.co.uk\/blog\/tree-comparison\/","title":{"rendered":"Tree Comparison"},"content":{"rendered":"

\nThroughout the course of my degree I have found it useful to write summaries of the various aspects of phylogenetics and biology that I have learned. That these will be useful to others is perhaps a vain hope, in both senses of the word, but I thought I might as well publish some of them on my blog. (It also afforded me the chance to try my hand at LyX\/LaTeX<\/a>.) For your reading convenience, this post is available as a pdf pdf<\/a>.\n<\/p>\n

\nTree Comparison<\/b>
\nPhylogenetic trees have two properties that can usefully be compared, their topologies and their branch lengths. Usually, the desired outcome of a tree comparison is a single number, indicating how different the trees are from one another. Reducing multiple complex structures to a single interpretable digit is
\ndifficult, even when just comparing two trees; a range of methods have been
\ndeveloped, most of which use (sometimes implicitly) graph theoretical measures of distance. Note that this is different from the situation of tree evaluation,
\nwhere the aim is to determine whether some trees are a better representation
\nof evolutionary history than others. Tree comparison is often done after evaluation, to gauge how much credence and importance to give to the results of the evaluation (there is, as yet, no method to state formally that the difference between trees is significant).\n<\/p>\n

\nFelsenstein (2004, pp.528-535) provides a historical overview of phylogenetic
\ntree comparison, starting with the symmetric difference metric, also known
\nas the Robinson-Foulds (RF) distance, which measures differences in topology between a pair of (possibly multifurcating) trees (Robinson and Foulds, 1981). The symmetric difference can be conceptualised as the minimum number of transformations that are required to convert one tree to the other, where a transformation corresponds to either removing a branch and merging the nodes
\nit connected, or by splitting a node into two and inserting a branch between the
\nnew nodes. The symmetric difference is widely used, but can be highly sensitive;
\nthat is, it can have a high value for trees which are intuitively similar (Felsenstein, 2004).\n<\/p>\n

\nIncluding information on branch lengths in tree comparisons is potentially useful, particularly when the tree has a relatively wide range of branch lengths.
\nThe weighted Robinson-Foulds distance (Robinson and Foulds, 1979) and the
\nbranch score (Kuhner and Felsenstein, 1994) are two metrics that use branch
\nlength information, and both are based on the symmetric difference. The
\nweighted RF distance is the sum of the differences between corresponding
\nbranch lengths; a branch length is considered to be zero if it does not exist in
\none of the trees. The branch score is similar, but squares the differences before adding them, and the square root of this sum is named the branch-length
\ndistance (BLD) (Felsenstein, 2004).\n<\/p>\n

\nThe pair of trees being compared can be mapped to two points in tree space,
\nwhich suggests another distance metric, the geodesic distance, defined as the
\nshortest path between two points in tree space. In tree space, the weighted
\nRF distance and the BLD correspond to Manhattan and Euclidean distances, respectively (Kupczok et al., 2008). Calculating the geodesic distance may be
\ncomputationally prohibitive for large trees, but good approximations are available (Kupczok et al., 2008).\n<\/p>\n

\nAll of the distances that use branch lengths will produce relatively high values if
\nthe branches in one tree tend to be larger, even if the topologies are very similar; that is, if the evolutionary rate differs between the trees. This behaviour may or may not be desirable, so to prevent differences in rate from having a disproportionate effect, Kuhner and Felsenstein (1994) suggested using relative
\nbranch lengths, dividing each branch length by the sum of all branch lengths.
\nAs far as I am aware, this has not been implemented in any publicly available
\nsoftware. The K score is a modification of the BLD that scales one tree to have
\nsimilar global divergence to the other before calculating the BLD, but the scaling means that the K score is no longer mathematically defined as a distance,
\nand its use is not always appropriate (Soria-Carrasco et al., 2007).\n<\/p>\n

\nCiting this Document<\/b>
\n[If referring to this document, please cite its location on the Monkeyshines
\nwebsite: http:\/\/www.monkeyshines.co.uk\/blog\/archives\/891<\/a>]\n<\/p>\n

\nReferences<\/b><\/p>\n