Title: Minimising branch crossings in phylogenetic trees

Authors: Sung-Hyuk Cha; Yoo Jung An

Addresses: Department of Computer Science, Pace University, New York, NY, USA ' Engineering Technologies and Computer Sciences, Essex County College, Newark, NJ, USA

Abstract: While phylogenetic trees are widely used in bioinformatics, one of the major problems is that different dendrograms may be constructed depending on several factors. Albeit numerous quantitative measures to compare two different phylogenetic trees have been proposed, visual comparison is often necessary. Displaying a pair of alternative phylogenetic trees together by finding a proper order of taxa in the leaf level was considered earlier to give better visual insights of how two dendrograms are similar. This approach raised a problem of branch crossing. Here, a couple of efficient methods to count the number of branch crossings in the trees for a given taxa order are presented. Using the number of branch crossings as a fitness function, genetic algorithms are used to find a taxa order such that two alternative phylogenetic trees can be shown with semi-minimal number of branch crossing. A couple of methods to encode/decode a taxa order to/from a chromosome where genetic operators can be applied are also given.

Keywords: dendrograms; hierarchical clustering; phylogenetic trees; visualisation; branch crossings; bioinformatics; genetic algorithms; taxa order.

DOI: 10.1504/IJAPR.2016.076982

International Journal of Applied Pattern Recognition, 2016 Vol.3 No.1, pp.22 - 37

Received: 04 Dec 2015
Accepted: 25 Jan 2016
Published online: 16 Jun 2016 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article