Content area
Abstract
We study the problem of reducing the crossing number in the phylogenetic network produced by a software PADRE. PADRE constructs a phylogenetic network from a multi-labeled (MUL) tree. We introduce a new metric, MIS-Distance for a MUL tree. We found that an optimal arrangement of the MUL tree reduces the graph crossing number . We describe a new heuristic, MUL-Arrange that uses MIS-Distance to optimally rearrange a MUL tree. We prove that for a class of MUL trees there exists a planar phylogenetic network and MUL-Arrange always finds the MUL tree that results in a planar network. We also show that MUL-Arrange reduces the crossing number in the network for other classes of MUL trees where we cannot guarantee planarity. We also establish a relationship between MIS-Distance and Graph Crossing Number for a special class of MUL trees. Finally, we show that adding the MUL-Arrange heuristic improvement to PADRE does not significantly increase the algorithm complexity.
