Centroid Wheel Tree

Centroid Wheel Tree is an Intuitive, Informative, and Most Balanced representation of phylogenetic trees.

Menu

Top/Introduction
Execute on Web
Key Concept
Examples
Web API
Download
NHX Format
Theory
Reference
Extra

Languages

/

Contact

Wataru IWASAKI
Dept. Biological Sciences,
Grad. Sch. Science,
University of Tokyo, Japan
E-mail:
iwasaki AT bs.s.u-tokyo.ac.jp

Licenses

CWT Software:
GNU General Public License
The other content:
Creative Commons License

CWT Algorithm and Travelling Salesman Problem

The algorithm for building wheel trees is given in the figure below.

The procedure accepts phylogenetic trees containing the same set of taxonomic units and first builds a consensus tree with a given threshold. It can also accept weight values that reflect observed frequencies or probabilities of the trees.

Then, for each multifurcating node (v) on the consensus tree, the best circular ordering of the branches adjacent to v (v-branches) is calculated through the following steps.

(1) For each branch pair of v-branches, sum the distances (the minimum number of edges) between the corresponding branch pairs over all input trees.
(2) Let these values be the traveling cost between each branch pair.
(3) Solve the Travelling Salesman Problem that minimizes the total traveling cost to obtain the best circular ordering of v-branches. Intuitively, this traveling cost was designed to become large if distant splits in the input trees are successive around the wheel nodes. In other words, the TSP solution minimizing the total cost makes close splits in the input trees successive as much as possible, embodying the key idea described in Key Concept.

After repeating the above for all multifurcating nodes, finally visualize the consensus tree by using the TSP circular orderings for branches around each multifurcation (wheel node).

Wheel Tree as Most Balanced Representation

Wheel trees produced by the procedure outlined above not only embodies the Key Concept. Mathematically, it is the centroid representation, which is the most balanced representation of the tree distributions. An intuitive explanation is as follows:

Imagine a heap of stones, each of which has a drawing of a phylogenetic tree and whose mass is proportional to the probability of the tree.
If we place the stones so that similar trees are close to each other, a map of a tree distribution is created.
If this distribution is unimodal and unbiased, the heaviest stone or the best tree is anticipated to be at the "center" of the distribution and represent it well, although this assumption cannot hold true for estimation problems in ultra-high dimensional spaces.
Instead, the wheel tree representation finds the centroid (or the center of gravity) of the trees, by placing them on a light plate on which each position corresponds to a wheel tree.

For more details, please refer to our Publication. Or, please make wheel trees by Executing Online.