Minimization of the Crossing Number in a Reconciled Tree

The problem of building a reconciled tree from a gene and a species tree is of great interest in bioinformatics, since it allows to highlight the relation between the evolution of the genes with the evolution of one or more species. In particular, a reconciled tree with a minimized number of crossings can help tracing down accurately the biological events of interest and avoiding wrong assumptions on the available data. The way the operation is performed affects heavily the usefulness of the resulting tree. The Minimized Crossing Number in a Reconciled Tree problem(MCNRT) problem is an NP-Complete problem. In this thesis we present an heuristic that aims to provide a solution for this problem. The proposed algorithm is based on the solution of the Generalized Tanglegram Layout problem, that has been adapted to work for the whole tree structure. Finally, the algorithm has been integrated in a running project, namely PrimeTV. The resulting code has been tested and proved able to optimize the number of crossings under different conditions