jfnavarro/PrimeTV2 — Issue #6: Reduce crossing lines
Author: arvestad
Created: 2011-10-11 06:57:59+00:00
State: open

It is hard (maybe even NP?) to find a drawing without unnecessary crossing gene tree edges. But there are some heuristics that can be used to simplify and one that we used in version 1 was to order gene tree clades consistently.

Simple trick 1: Order gene nodes assigned to a speciation such that those with children in left sub tree only comes first, then nodes with children in both subtrees, and last nodes with children in only the right subtree.

Simple trick 2: Consider an edge (x, y) in S (x is a parent of y) and four gene nodes u1, u2, v1, and v2 where u1 and u2 are mapped to x and v1 and v2 are mapped to y. If v1 is left of v2, then u1 should be left of u2.