Home » Computational Evolutionary Biology

Introduction

An evolutionary tree for a set of entities, each with defined character states, can be constructed using 'tree clustering', i.e. using a cluster analysis method which builds trees. A simple approach is:

1. Form a matrix of distances between all pairs of entities.
2. Find the closest pair (entities or clusters).
3. Combine this pair to form a new cluster. The distances between the new cluster and existing entities or clusters can be determined in several ways, e.g. as the minimum of the distances for each of the pair or the unweighted or weighted average.
4. Repeat from (2) until only one cluster remains.

Input

• Each character state is described by a SINGLE letter or digit.

  • The letters 'A'-'Z' represent discrete character states.
  • All other letters and digits represent ordered character states, in which distances are defined by the ASCII code of the character (e.g. 'a' is 3 away from 'd').

  Characters must be consistently coded, i.e. either all the states of a character must be discrete or all the states must be ordered.

• Each entity is represented by a string of character states. Strings MUST be enclosed in ' ' (even if the character states are represented by digits). Every entity must have the same number of characters (i.e. all the strings must be the same length). Thus 'ACaX3' and 'CTeB4' are two consistent character state strings.

• The entities to be analysed are described by a list of character state strings, separated by commas and enclosed in '[' and ']'.

• The combination method used to calculate the new distances when a pair of entities/clusters are combined can be selected.

The initial distance for every pair of entities is found by summing over all characters, adding 1 for every different state if the character is discrete and the ASCII code difference if the character is ordered. This typically results in a substantial fraction of the distances being the same. To help in reducing ambiguity, for every pair of entities, the average difference between the two distances from each of the pair to every other entity is found. This is divided by 100 and added to the initial distance.

The Fitch/Wagner algorithms are applied to the tree resulting from the clustering process. ('Fitch' and 'Wagner' are used in the sense of Ronquist & Beerli, http://people.sc.fsu.edu/~beerli/ISC5317/Lectures/02pars.pdf. However, the algorithm for the Wagner up-pass is not as given by their 2007 lecture notes: see instead Programming the Wagner Uppass Algorithm.)

Note: there is no validation of the input, so it needs to be in the right format!