Home » Computational Evolutionary Biology

Introduction

Consider an evolutionary tree for a set of entities, each entity having a fixed number of characters with given states. An 'optimal' tree can be defined as one whose shape and internal nodes are such that it has the minimum number of changes in the character states summed over every pair of connected nodes in the tree -- the 'parsimony' criterion. This demonstration enables you to experiment with small numbers of entities (a maximum of about 10 or 11 is feasible depending on your hardware and sofware).

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 in-group can have from 2 to about 10 members, and is described by a list of character state strings, separated by commas and enclosed in '[' and ']'.

• The SINGLE out-group entity is described by a character state string.

• Optimization is based on hill-climbing. The initial tree is based on two of the entities. Then one more entity is added, generating all possible extended trees. Only trees within a given tolerance of the current most parsimonious number of changes are retained into the next step. The process terminates when all entities have been added. There is, of course, no guarantee that all optimal solutions will be found unless the tolerance is large enough to allow exhaustive searching. In practice, it is usually effective to start with tolerance = 0 and increase it in steps of 1 until no extra solutions are found.

Potential solutions are evaluated using Fitch Parsimony for the discrete characters and Wagner Parsimony for the ordered characters. ('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!