linTests: Evaluating tree distance metrics by cluster recovery

linTestsR Documentation

Evaluating tree distance metrics by cluster recovery

Description

An effective measure of tree distance will recover clusters of similar trees. These datasets contain the results of tests modelled on those in Lin et al. (2012).

Usage

linTestOneResults

linTestTwoResults

linTestSPRResults

Format

A three-dimensional array.

Rows correspond to the clustering methods:

  • spc: spectral clustering

  • pam: partitioning around medioids

  • h...: hierarchical clustering using: h.cmp, complete; h.sng, single; and h.avg, average linkage.

Columns correspond to distance metrics; see 'Methods tested' below.

Slices correspond to values of k:

  • linTestOneResults: k = 30, 40, 50, 60, 70

  • linTestTwoResults: k = 10, 20, 30, 40

  • linTestSPRResults: k = 30, 40, 50, 60, 70

An object of class array of dimension 5 x 24 x 4.

An object of class array of dimension 5 x 24 x 5.

Details

I used three approaches to generate clusters of similar trees, and tested each metric in its ability to recover these clusters (Lin et al., 2012).

For the first test, I generated 500 datasets of 100 binary trees with n = 40 leaves. Each set of trees was created by randomly selecting two k-leaf 'skeleton' trees, where k ranges from 0.3 n to 0.9 n. From each skeleton, 50 trees were generated by adding each of the remaining n - k leaves in turn at a uniformly selected point on the tree.

For the second and third test, each dataset was constructed by selecting at random two binary 40-leaf trees. From each starting tree, I generated 50 binary trees by conducting k leaf-label interchange (LLI) operations (test two) or k subtree prune and regraft (SPR) operations (test three) on the starting tree. An LLI operation swaps the positions of two randomly selected leaves, without affecting tree shape; an SPR operation moves a subtree to a new location within the tree.

For each dataset, I calculated the distance between each pair of trees. Trees where then partitioned into clusters using five methods, using the packages stats and cluster. I define the success rate of each distance measure as the proportion of datasets in which every tree generated from the same skeleton was placed in the same cluster.

For analysis of this data, see the accompanying vignette.

Methods tested

  • pid: Phylogenetic Information Distance (Smith 2020)

  • msid: Matching Split Information Distance (Smith 2020)

  • cid: Clustering Information Distance (Smith 2020)

  • qd: Quartet divergence (Smith 2019)

  • nye: Nye et al. tree distance (Nye et al. 2006)

  • jnc2, jnc4: Jaccard-Robinson-Foulds distances with k = 2, 4, conflicting pairings prohibited ('no-conflict')

  • joc2, jco4: Jaccard-Robinson-Foulds distances with k = 2, 4, conflicting pairings permitted ('conflict-ok')

  • ms: Matching Split Distance (Bogdanowicz & Giaro 2012)

  • mast: Size of Maximum Agreement Subtree (Valiente 2009)

  • masti: Information content of Maximum Agreement Subtree

  • nni_l, nni_u: Lower and upper bounds for nearest-neighbour interchange distance (Li et al. 1996)

  • spr: Approximate SPR distance

  • tbr_l, tbr_u: Lower and upper bound for tree bisection and reconnection (TBR) distance, calculated using TBRDist

  • rf: Robinson-Foulds distance (Robinson & Foulds 1981)

  • icrf: Information-corrected Robinson-Foulds distance (Smith 2020)

  • path: Path distance (Steel & Penny 1993)

Source

Scripts used to generate data objects are housed in the data-raw directory.

References

\insertRef

Bogdanowicz2012TreeDist

\insertRef

Li1996TreeDist

\insertRef

Kendall2016TreeDistData

\insertRef

Nye2006TreeDist

\insertRef

Robinson1981TreeDist

\insertRef

Smith2019TreeDist

\insertRef

SmithDistTreeDist

\insertRef

Steel1993TreeDist

\insertRef

Valiente2009TreeDist

\insertRef

Lin2012TreeDistData


ms609/TreeDistData documentation built on June 30, 2024, 7:21 p.m.