Overlap of image for big structures

[Tomasz Żok]

Hi,

I would like to draw big structure (300 nucleotides and more) using
either Radiate of NAView algorithm. The first creates totally
intermixed image, while the other handles it pretty well. Still, some
parts of the drawn structure are overlapping. I did not have a look
into the code yet, but can you tell me - is it rather a bug in
software or is it NAView some intrinsic feature which will be rather
difficult to solve?

Best regards,
Tomek

[Yann Ponty]

Hi Tomasz,

Theoretically speaking, there is simply no way to avoid overlapping
layouts in general. In other words, for any drawing algorithms that
preserves some maximal distance D between consecutive backbone
elements, and some minimal base radius r, there exists a structure
such that some loops will overlap.
Indeed, consider the tree-like nature of secondary structures: Remark
that, even if you only allow for three-ways junctions (ie binary
trees), you are still left with 2^k bases at depth k in the worst-
case. Now consider a secondary structure, whose helices all has equal
length M (which will depend on D). Remark that any terminal loop at
depth k is distant from the exterior loop by at most M*k. It follows
that all of the 2^k bases at depth k, occupying a total area r*2^k,
will have to fit in a disc of area pi*M^2*k^2 (centered on the
exterior loop). So, for some value of k, the exponential (aka room
needed to draw all of the loops at depth k) is going to win over the
square (aka room available to draw them).

Ok, that was my CS/Math geek moment ;)

From a practical standpoint, NAView usually does a good job at
avoiding overlaps.
The only thing he is not very good at is long regions of unpaired
bases, in my experience.
We had to tweak NAView a bit to make it fit within VARNA, since the
original implementations did not distinguish the distances between two
bases consecutive in the backbone, and base-pairs. Essentially, NAView
considers the structure as a tree, and has a test to decide if he
switches to a "stick" drawing for long unpaired regions (the limit
behavior being a terminal loop being drawn as an helix without base-
pairs). I suspect something is buggy with this test in VARNA's
implementation. If you wish to look at the code, you may find a more
time-tested implementation in the Vienna package source code, on which
we based our Java reimplementation.

Best regards,

Yann