Google
More docs on the ARB website.
See also index of helppages.
Last update on 25. Nov 2018 .
Main topics:
Related topics:

K.L. optimization

OCCURRENCE

ARB_PARSIMONY/<K.L.-mode-button>

 

DESCRIPTION

Searches for a better (more parsimonious) tree by swapping subtrees which are separated by many edges.

Not all possible topologies are tested here, because there are far too many (see ´Kernigham Lin (K.L.) properties´ for details).

Instead the K.L. optimizer selects several "paths" through the tree (we call this selection 'path reduction') and follows only those paths, while performing NNIs (see ´NNI (Nearest Neighbour Interchange)´) along it's way.

These NNIs are even attempted, when single NNIs degrade the quality of the topology. If some intermediate or the final NNI (which is by default done 15 edges away from the edge starting from) leads to an improvement of the tree, the topology change is kept. Otherwise all changes are undone and the next path will be attempted.

The default maximum path length of 15 and several parameters concerning the path reduction may be configured in ´Kernigham Lin (K.L.) properties´.

 

NOTES

The K.L. optimization occurs as step 2 of ´Global Optimization´.

It can be called directly using ´K.L.-mode´.

 

EXAMPLES

None

 

WARNINGS

None

 

BUGS

No bugs known