Google
More docs on the ARB website.
See also index of helppages.
Last update on 04. Mar 2022 .
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