BACKGROUND
rna and its structure
ribo-nucleic acid  is a polymer of nitrogenous bases, composed mainly of adenine, cytosine, guanine, and uracil .
rna is very similar to deoxyribo-nucleic acid  in its basic composition, but while dna is regularly found as two complimentary strands, rna can be found as a single strand of nucleotides.
this primary structure  then folds over itself into a secondary structure when the bases in the rna strands pair up via hydrogen bonding.
the rna molecule can then twist, fold, or otherwise change its conformation in 3d space, giving it a functional three dimensional form, known as the tertiary structure.
single stranded, functional rna is an important agent in many biological processes.
from humans to bacteria and viruses, there are many examples of rna molecules that are important to understand, classify, and research.
some notable examples include rna motifs that allow viruses to manipulate host replication machinery , bacterial rna motifs that give rise to antibiotic resistance  <cit> , and man-made rna molecules designed for therapeutics  <cit> .
rna secondary structure visualization
there are many rna visualization tools that have been developed, and two excellent reviews of them can be found in  <cit> , with notable examples that are still available including varna  <cit> , jviz.rna , forna  <cit> , pseudoviewer , 4sale  <cit> , assemble <dig>  <cit> , rna2dmap  <cit> , r2r  <cit> , and r-chie  <cit> .
all visualization software developed for rna have as their goal to display an informative structure of the rna molecule, usually focusing on its secondary structure, that can be annotated and used to convey information in presentations, publications, and any other two-dimensional media.
however, the majority of rna visualization software designed produce a static layout of the rna molecule that may not be ideal for the user.
while for small rna molecules such as transfer rna , this problem almost never arises, for large rna molecules, this layout can be such that sections of the rna overlap each other, making annotation of certain regions problematic and uninformative.
there are only three notable examples that create dynamic layouts which are responsive to user interactions: jviz.rna, pseudoviewer, and varna.
the designers of varna do not explicitly state how they construct the rna molecule and how the algorithm responsible for user response behaves, but one can estimate how the algorithm operates from interacting with the software as a web applet  <cit> .
the rna structure is translated into a graph where loops make up the vertexes and stems make up the edges.
thus, by dragging the stems, the user can arrange the layout of the rna molecule.
while this allows users to fully customize the rna layout to their needs.
the high degree of user involvement might make the task seem very daunting for large rna molecules.
pseudoviewer is another application that allows its users to manipulate the rna structure.
originally an application designed focusing on rna pseudoknots, pseudoviewer puts a great deal of effort into creating the initial layout of the rna molecule.
additionally, the user can manipulate the rna structural motifs.
however, certain manipulations of the rna conformation destabilize the system and cause the rna model to break apart.
furthermore, since pseudoviewer’s focus is primarily on pseudoknotted rna structures, it tends to arrange the rna structure layout focusing very heavily on clear display of pseudoknot types, at the expense of the aesthetics related to the rest of the structure.
jviz.rna, a third software designed for dynamic rna visualization, employs a different approach to creating the rna model.
jviz.rna translates the rna molecule into a graph as well, but maps each nucleotide to a vertex and each bond between nucleotides  to an edge.
jviz.rna then uses repulsion and attraction forces between all nucleotides to calculate the position and movement.
this process continues until the forces reach an equilibrium for all nucleotides.
users can still move the individual nucleotides, and by doing so interact with the rna structure.
mapping each nucleotide into a vertex creates a graph with a high number of vertexes and edges.
as such, we denote this method as constructing a detailed graph.
a software similar to jviz.rna, forna, also uses a detailed graph representation in order to construct a dynamic rna model.
all nucleotides and chemical bonds are translated into vertexes and edges, and an automatic layout is constructed utilizing attraction and repulsion forces, as well as invisible "helper vertexes" which aid in the improvement of loop appearance.
like the previous three software tools, forna allows for users to interact with the constructed dynamic model.
of the four software tools mentioned, the approach employed by jviz.rna and forna relies mostly on the program to produce the layout, rather than require user intervention.
this approach makes the production of rna images less involved for the user, due to very little, if any, overlap even for large molecules.
however, both forna and jviz.rna require more computation time for structure layout than pseudoviewer or varna.
for very large structures of over 900nt, waiting for the automatic layout can be very inconvenient, and interaction with the structure becomes problematic as the structure’s movement becomes delayed.
in addition, current jviz.rna output contains some inconsistencies with regards to current accepted rna visualization guidelines.
the following section discusses these shortcomings in more detail.
motivation
while the current implementation for jviz.rna produces dynamic rna models that display secondary structure elements very well, the simple graph representation described presents some visual shortcomings.
most rna images found in the literature follow several visualization norms, and two such norms that are very important are that stems are drawn such that the distance between base-pairs is consistent across the stem, and that loops are drawn as circular elements wherever they occur in the structure.
figure  <dig> demonstrates such limitations of jviz.rna.
while fig.
1
a contains stems with consistent base-pair distances and loops which are clearly distinguishable by their circular nature, fig.
1
b contains stems where the base pair distance varies across the stem, and some loops that are not immediately visible .
fig.
<dig> the visualization differences observed in jviz.rna compared to an rna image which highlights rna visualization norms in literature.
a the yellow fever virus 3’ untranslated region .
image taken from  <cit>  and used with permission,  an example produced by jviz.rna of the s. cervisiae 5s ribosomal rna
the main motivation for the work presented in this manuscript was to address the visual shortcomings presented by the current algorithm employed in jviz.rna, as well as improvements in the run-time performance.
the objectives of this work were:
to create an rna representation which was more consistent with existing rna visual conventions, such as round loops and equidistant base pairs.
to design an automatic layout algorithm which works with the new representation, while introducing noticeable speed-ups to that automatic layout algorithm, and reduce overlap of structural elements.
both objectives address important areas for improvement in jviz.rna.
while currently the resulting rna molecule is laid out very clearly, personal feedback from rna researchers, as well as visual comparison with other software, demonstrates that it ignores several visualization conventions such as the shape of loops and stems.
this visualization pattern makes it more difficult to share informative images and diagrams about rna, as the resulting visualization is not in the format most rna scientists expect.
another challenge the current setup faces is its time complexity.
calculating the attraction force for each nucleotide n
i is in o since there are at most three nucleotides bonded to it, so the total calculation time for all the nucleotides’ attraction forces is in o at each iteration .
however, calculating the repulsion forces for each nucleotide is in o since it must account for the repulsion of all other nucleotides, so the total calculation time for all the nucleotides’ repulsing forces is in o. this run-time can make the automatic layout algorithm perform slowly for large rna structures such as 16s ribosomal rna.
as such, the work presented in this manuscript was set to implement the improvements while reducing the run-time required for the rna structures to stabilize.
in order to achieve this two-pronged effect, the method by which jviz.rna builds the graph to represent the rna structure had to be modified; the simple graphs built were replaced by a more compressed representation of the rna molecule, named compressed graphs.
the work in this manuscript is divided into three main sections.
first, we discuss how the rna molecule can be mapped into a graph with a smaller number of vertexes, a compressed graph, similar to the one used by varna.
secondly, we profile the performance of the original version of jviz.rna against the performance obtained by employing the reduced graph.
third and finally, a superior method for calculating movement is presented and profiled against the original movement calculation method.
methods
language, implementation, and system
the code presented in this manuscript was implemented using java  <dig> .
the swing library was used for the graphical component of the code.
measurements were all taken on a pc with an intel core i7- <dig>  <dig>  ghz processor, running ubuntu  <dig> .
<dig> lts.
constructing and manipulating the new graph
one intuitive method of decreasing the run-time for the algorithm mentioned is to decrease the number of vertexes simulated.
since the run-time for the algorithm at every iteration is in order of o, decreasing the number of vertexes would theoretically have a tremendous effect on reducing the run-time.
however, the mapping of the structure into vertexes and edges must be done in a way that still produces visually pleasing layouts and rna diagrams.
inspired by varna, we have employed a representation which maps each rna loop, as well as every stem base pair, to a vertex, and connects those via edges.
.
fig.
<dig> the compressed graph mapped to an rna structure.
a the main rna elements are compressed into vertexes where each vertex represents an rna loop element, or a stem base pair.
b the nucleotides belonging to each rna element are drawn on top of the underlying rna compressed graph.
c the resulting rna representation contains less vertexes than there are nucleotides , and a more familiar visual layout
furthermore, we have implemented the system in such a way that repulsion only occurs between loops, and not base pairs.
since the repulsion step is the main time consuming step of each iteration ), decreasing the number of participating vertexes in the repulsion interaction should greatly reduce the run time of the algorithm.
constructing the system in such a way that only loops experience repulsion ensures that loops will be pushed away from each other, thus not intersecting each other.
in theory, this should aid the structure in adopting a final layout that has minimal or no intersection of any structural elements.
at the initial step of the simulation, the rna graphs are placed in a naive initial layout which is inspired from a circular representation of the rna molecule .
then, an iterative process begins in which the structure is slowly brought to a stable position by newtonian inspired spring and repulsion forces.
fig.
<dig> the initial vertex layout process demonstrated using a sample theoretical rna molecule.
l
<dig>  l
<dig>  l
<dig>  l
<dig>  l
<dig>  and l
<dig> represent loops while b
<dig>  b
<dig>  b
<dig>  b
<dig>  b
<dig>  b
<dig>  and b
<dig> represent base pairs.
the loops and base pair vertexes are connected via black edges.
a the rna nucleotides are first laid out in a circle.
b each set of nucleotides has its average position calculated, and the vertex corresponding to that set is placed in that average position.
following this step, the iterative process of stabilization begins
jviz.rna and the newtonian model
originally jviz.rna mapped the rna structure into a detailed graph, g={v,e}.
in the detailed graph representation, each nucleotide is a vertex v∈v, and each chemical bond corresponds to an edge e∈e.
the entire structure is initially laid out in a circle, and an iterative process designed to move the structure into a stable layout begins.
in this paper, we employ the compressed graph representation, where each structural element  is a vertex v∈v, and the edges are graph elements which connect the different structure elements .
for the purposes of the following sections, the notation p→ will be used to denote the positions of the different vertexes which represent the rna structures, and p→n,ki will be used to denote the position of vertex i , at time-step n , during the k-th newton iteration .
the most basic computation done at each iteration is the unit vector function, u→.
this function calculates the unit vector pointing from point p→j  to point p→i  as follows:
<dig> u→p→i,p→j=p→i−p→jp→i−p→j
in each iteration, each vertex moves based on two forces: repulsion and attraction.
the repulsion forces each vertex v
i experiences from vertex v
j can be described as:
<dig> r→p→i,p→j=gp→i−p→j2×u→p→i,p→j
where u→ is the unit vector function showing the direction from vertex v
j to vertex v
i, and g is a coefficient to control the size of the force experienced.
the attraction forces each vertex v
i experiences from vertex v
j can be described as:
<dig> a→p→i,p→j=k×p→j−p→i+rideal×u→p→i,p→j
where u→ is again the unit vector function, k is an attraction coefficient to control for the size of the force, and r
ideal is the ideal desired distance between the vertexes v
i and v
j.
the iterative process stops when the forces for all vertexes have reached equilibrium, or when for all vertexes {v
i|1≤i≤n} the following holds:
<dig> ∀vi,∑vj∈l,j≠ir→p→i,p→j+∑vj∈cia→p→i,p→j≤ε
where c
i is the set of all vertexes connected to vertex v
i , and l is the set of all loops .
that is to say, the iterative process stops when the sum of the forces acting on the vertexes is smaller than ε. setting ε= <dig> will force the simulation to continue to calculate until the forces are perfectly at odds, but setting a small value for ε allows the layout algorithm to stop sooner when achieving a stable structure.
ε as such, controls the degree of stability required before simulation of the structure’s movement stops.
in this work, we chose to explore two methods of implementing the physics based rna model: the forward euler method, and the backward euler method.
the two methods make it possible to evaluate the movement of the vertexes.
however, the latter is more numerically stable than the former, and allows for greater time steps and faster visualizations, as well as a more stable user interaction experience.
the forward euler method
the euler method is a first-order integration method which belongs to a larger class called the runge-kutta methods .
the simplest version is called the forward euler method  <cit> .
this method of calculating each time step can be expressed in the following manner:
<dig> tn+1=tn+Δtp→n+1i=p→ni+Δtf
which means the time t
n is advanced by the time-step Δ
t and then the position of the vertex v
i is updated based on the size of the time-step, and the current behaviour of the particle, f .
when applied to the movement of the rna vertexes, the forward euler method can be written as:
<dig> tn+1=tn+Δtf=∑vj∈l,j≠ir→p→ni,p→nj+∑vj∈cia→p→ni,p→njp→n+1i=p→ni+Δtftn,p→ni
where in this case, the behaviour of the particle with regard to its position is the sum of repulsion  forces  and attraction  forces acting on the particle.
since base pair vertexes do no participate in the repulsion step, the expression for a base pair vertex’s forward euler implementation will be:
<dig> tn+1=tn+Δtftn,p→ni=∑vj∈cia→p→ni,p→njp→n+1i=p→ni+Δtftn,p→ni
however, since the implementation of this expression is trivially similar to the expression in , the remainder of this text will focus on that expression, with the implications for the expression in  being omitted for brevity.
the main drawback presented by the forward euler method is its numerical instability.
simply put, when the time-step Δ
t is too long, or the coefficients which control the simulation become too large, the simulation does not stabilize into an equilibrium.
in fact, it can become increasingly unstable.
the solution to this drawback lies in the implementation of the backward euler method, which takes this instability into account.
the backward euler method
much like the forward euler method is described as explicit, there is an implicit euler method; the backward euler method.
generally, it is defined as:
<dig> tn+1=tn+Δtp→n+1i=p→ni+Δtftn,p→n+1i
where f is again a function that describes the movement of the object.
notice it is very similar to the explicit method, but the term p→n+1i appears on both sides of the equation.
as a result, finding p→n+1i is no longer a simple issue of updating the timestep, but it is that of solving for it algebraically.
in the case of the current simulation, the backward euler method would yield the following expression:
<dig> tn+1=tn+Δtftn,p→n+1i=∑vj∈l,j≠ir→p→n+1i,p→nj+∑vj∈cia→p→n+1i,p→njp→n+1i=p→ni+Δtftn,p→n+1i
which becomes a fairly difficult equation to solve for p→n+1i directly.
instead, an approximation is used to solve for p→n+1i.
applying newton’s method to solve the backward euler expression
the expression in  can be rearranged to produce the following equation:
<dig> p→n+1i=p→ni+Δt∑vj∈l,j≠ir→p→n+1i,p→nj+∑vj∈cia→p→n+1i,p→nj
which can be rewritten as:
<dig> f→p→n+1i=0→=−p→n+1i+p→ni+Δt∑vj∈l,j≠ir→p→n+1i,p→nj+∑vj∈cia→p→n+1i,p→nj
meaning the solution for p→n+1i is the root of the function f→.
while it may be difficult to solve for the root directly, newton’s method offers an approach for approximating the root of the vector function f→p→n+1i  <cit> .
defining the vector function’s components
as outlined in  <cit> , it is necessary to define each of the components in f→ individually so that their derivatives can then be found with respect to each of the variables.
in the case of the rna simulation, the function f→ contains only two components; f
x and f
y which are each defined as:
<dig> fxp→n+1i=−xn+1i+xni+Δt∑vj∈l,j≠irxp→n+1i,p→nj+∑vj∈ciaxp→n+1i,p→njfyp→n+1i=−yn+1i+yni+Δt∑vj∈l,j≠iryp→n+1i,p→nj+∑vj∈ciayp→n+1i,p→nj
this definition requires both r→ and a→  to be defined in terms of their x and y components as:
<dig> rxp→n+1i,p→nj=gxn+1i−xnj2+yn+1i−ynj2×uxp→n+1i,p→njryp→n+1i,p→nj=gxn+1i−xnj2+yn+1i−ynj2×uyp→n+1i,p→njaxp→n+1i,p→nj=k×xnj−xn+1i+rideal×uxp→n+1i,p→njayp→n+1i,p→nj=k×ynj−yn+1i+rideal×uyp→n+1i,p→njuxp→n+1i,p→nj=xn+1i−xnjxn+1i−xnj2+yn+1i−ynj2uyp→n+1i,p→nj=yn+1i−ynjxn+1i−xnj2+yn+1i−ynj <dig>
finding the components’ derivatives
in order to apply newton’s method to the rna model, the jacobian matrix d of the vector function f→ needs to be defined.
in order to do so, expressions for all partial derivatives of the components in eqs.
-  need to be defined, where each component has two partial derivatives; with respect to xn+1i and with respect to yn+1i.
the derivation of each component’s partial derivatives is quite long and is not the main focus of this article.
therefore, for brevity purposes, the individual derivatives are outlined in the set of eqs.
-:
<dig> δfxδxn+1ip→n+1i=−1+Δt∑vj∈l,j≠iδrxδxn+1ip→n+1i,p→nj+∑vj∈ciδaxδxn+1ip→n+1i,p→njδfxδyn+1ip→n+1i=Δt∑vj∈l,j≠iδrxδyn+1ip→n+1i,p→nj+∑vj∈ciδaxδyn+1ip→n+1i,p→njδfyδxn+1ip→n+1i=Δt∑vj∈l,j≠iδryδxn+1ip→n+1i,p→nj+∑vj∈ciδayδxn+1ip→n+1i,p→njδfyδyn+1ip→n+1i=−1+Δt∑vj∈l,j≠iδryδyn+1ip→n+1i,p→nj+∑vj∈ciδayδyn+1ip→n+1i,p→nj
<dig> r=xn+1i−xnj2+yn+1i−ynj2δrxδxn+1ip→n+1i,p→nj=δuxδxn+1ip→n+1i,p→nj×gr−2gxn+1i−xnjr2×uxp→n+1i,p→njδrxδyn+1ip→n+1i,p→nj=δuxδyn+1ip→n+1i,p→nj×gr−2gyn+1i−ynjr2×uxp→n+1i,p→njδryδxn+1ip→n+1i,p→nj=δuyδxn+1ip→n+1i,p→nj×gr−2gxn+1i−xnjr2×uyp→n+1i,p→njδryδyn+1ip→n+1i,p→nj=δuyδyn+1ip→n+1i,p→nj×gr−2gyn+1i−ynjr2×uyp→n+1i,p→nj
<dig> δaxδxn+1ip→n+1i,p→nj=k×−1+rideal×δuxδxn+1ip→n+1i,p→njδaxδyn+1ip→n+1i,p→nj=k×rideal×δuxδyn+1ip→n+1i,p→njδayδxn+1ip→n+1i,p→nj=k×rideal×δuyδxn+1ip→n+1i,p→njδayδyn+1ip→n+1i,p→nj=k×−1+rideal×δuyδyn+1ip→n+1i,p→nj
<dig> r=xn+1i−xnj2+yn+1i−ynj2δuxδxn+1ip→n+1i,p→nj=yn+1i−ynj2r3δuxδyn+1ip→n+1i,p→nj=−yn+1i−ynjxn+1i−xnjr3δuyδxn+1ip→n+1i,p→nj=−yn+1i−ynjxn+1i−xnjr3δuyδyn+1ip→n+1i,p→nj=xn+1i−xnj2r <dig>
and the matrix d is defined as:
dp→n+1i=δfxδxn+1ip→n+1iδfxδyn+1ip→n+1iδfyδxn+1ip→n+1iδfyδyn+1ip→n+1i.
constructing the newton step
given the function f→ and the matrix d, progressively better estimates for the value of p→n+1i can be found by applying the following newton step:
<dig> p→n+ <dig> k+1i=p→n+ <dig> ki−f→p→n+ <dig> ki×d−1p→n+ <dig> ki
where d−1p→n+ <dig> ki is the inverse matrix of dp→n+ <dig> ki.
that is, at every newton step k+ <dig>  the value of both the function f→ and its components’ derivatives, encapsulated in the matrix d
− <dig>  are evaluated at the point p→n+ <dig> ki, that is, the point p→n+1i from the previous newton step.
the initial estimate, p→n+ <dig> i can be obtained by applying the forward euler.
as more newton steps are repeated, a better and better estimate for p→n+1i emerges.
however, each newton step increases the run-time of each iteration of the algorithm.
in general, each additional newton step increases the run time of the physics based simulation by o where l is the number of loops in the simulation.
experimental parameters and test-bed structures
for the purposes of these experiments,  <dig> rna molecules were chosen from the rna strand v <dig>  database  <cit> , and were run under two different configurations.
the configurations and their parameters can be found in table  <dig>  while the structure details can be found in table 2
<dig>  the structure lengths are given in “nt,” which stands for “nucleotides.”
different time-steps were chosen for the different configurations .
configuration  <dig> was assigned the highest time-steps it can support without losing stability.
configuration  <dig> can handle larger time steps, but the choice of time-step influences the choice for the number of newton iterations .
therefore, a value of  <dig>  was chosen to support satisfactory convergence within  <dig> newton iterations.
each structure was run  <dig> times and the cpu time of the run was measured until the structure stabilized .
the average run-time was calculated and plotted.
if a structure’s stabilization process took more than  <dig> mins  it was terminated and its stabilization time was taken as  <dig> s.
improving the attraction force calculations
the system of forces described in the previous section allowed the rna structure simulation to stabilize and present the rna structural elements much better than the former jviz.rna implementation .
however, the resulting stable layouts were not satisfactory due to the overlap artefacts created .
stems would often overlap loops and would not stabilize into their correct position based on their connectivity to the loops.
while a user could, in theory, address such a problem manually, we felt there is room for further improvements.
in order to correct the overlap artefacts, a slight modification to the attraction force calculation was implemented.
fig.
<dig> the visualization result obtained for the  <dig> nt rna .
a the visualization obtained with jviz’s detailed graph representation .
b the visualization obtained with jviz’s compressed graph representation and the forward euler method.
c the visualization obtained with jviz’s compressed graph representation and the backward euler method
originally, the attraction forces would apply attraction between the centres of two vertexes .
however, with a slight modification, each vertex can store the ideal positions for each stem protruding from it .
using these ideal positions in the equation for a→ to move each vertex to its ideal position and orientation .
the resulting layouts prove to be much more visually appealing and containing much less overlap, especially for smaller rna structures .
fig.
<dig> implementing the ideal position attraction forces causes the stems to align with their ideal layout.
a originally, attraction forces were acting between base pairs, and the loops, attracting the centres of the vertexes directly.
b the resulting layout contained artefacts of distorted stems, since base-pairs were unaware of their positions relative to loops.
c the idealized attraction forces employ the ideal positions  of the stems to attract the base-pair vertexes.
d the resulting layout when employing the ideal positions is aware of the position stems should take relative to their parent loops
RESULTS
comparison of jviz.rna’s performance employing the forward and backward euler methods <dig> of the run times was taken and plotted in fig.
<dig>  as can be seen, the run times of the forward euler method are often ≈ <dig> times longer than the backward euler run times.
considering the fact that no structure was allowed longer than  <dig> seconds to stabilize, it is fair to assume that under the current parameters of k and g, the difference in run time could have been even greater for some structures.
fig.
<dig> the run-times  of jviz.rna’s compressed graph representations employing both the forward and backward euler methods
fig.
<dig> the run-times ) of jviz.rna’s compressed graph representations employing both the forward and backward euler methods
one would expect that the run-times would increase in a quadratic order to the number of nucleotides.
however, while there is a general increase in run time with structure size, some small structures take longer than larger ones to stabilize.
this observation points to the fact that the connectivity of the structure plays a very important role in its stabilization time.
overall, a structure x composed of  <dig> times as many nucleotides as structure y would take longer to stabilize, but it may not be straightforward to deduce exactly how much longer.
even the number of vertexes in a given structure does not provide a good heuristic to calculating the difference in stabilization time for both the forward and backward euler.
despite the relative uncertainty in the relationship between a given structure’s run time and its size, there is a great deal of certainty that the backward euler proved superior when compared to the forward euler.
first, it can produce stable layouts employing a time step  <dig> times larger than the forward euler method without losing stability.
second, it exhibits much faster run-time performance.
as demonstrated in this work, some large structures may pose a challenge to a system which takes smaller time step since the topology of the structure itself dictates how long it will take to stabilize
visual comparison of the different algorithms
in order to get a full appreciation of the advantages of the different methods explored in this work, as well as potential future improvements, it is necessary to look at both the run-times reported in figs.
<dig> and  <dig>  as well as at the resulting visualizations each method produced.
figures  <dig>   <dig>   <dig>   <dig>   <dig> and  <dig> demonstrate the visualizations produced when employing the four different methods explored in this paper .
comparing the images produced by the compressed and detailed graphs reveals additional differences between the methods.
it is immediately evident that the figures produced by employing the compressed graph adhere more strictly to rna visualization conventions; namely, the circular loops, and the constant distance between base pairs.
however, at the same time, the detailed graph representation demonstrates some advantages over the compressed graph images.
first, there are no cases of stems that intersect, which contributes to less user intervention being required to “untangle” the structure.
the compressed graph representations, on the other hand, occasionally have stems that intersect and would require the user to explore the structure to resolve such conflicts.
though this drawback is addressed to a large extent by substituting the ideal positions as the attraction points for the vertexes, the need to manually untangle the structure may persist in certain cases.
fig.
<dig> the visualization result obtained for the  <dig> nt rna  utilizing: a the detailed graph representation .
b the compressed graph representation and the forward euler method.
c the compressed graph representation and the backward euler method.
d the compressed graph representation and the backward euler method while employing ideal positions attraction forces
fig.
<dig> the visualization result obtained for the  <dig> nt rna  utilizing: a the detailed graph representation .
b the compressed graph representation and the forward euler method.
c the compressed graph representation and the backward euler method.
d the compressed graph representation and the backward euler method while employing ideal positions attraction forces
fig.
<dig> the visualization result obtained for the  <dig> nt rna  utilizing: a the detailed graph representation  utilizing: a the detailed graph representation .
b the compressed graph representation and the forward euler method.
c the compressed graph representation and the backward euler method.
d the compressed graph representation and the backward euler method while employing ideal positions attraction forces
fig.
<dig> the visualization result obtained for the  <dig> nt rna  utilizing: a the detailed graph representation .
b the compressed graph representation and the forward euler method.
c the compressed graph representation and the backward euler method.
d the compressed graph representation and the backward euler method while employing ideal positions attraction forces
fig.
<dig> the visualization result obtained for the  <dig> nt rna  utilizing: a the detailed graph representation .
b the compressed graph representation and the forward euler method.
c the compressed graph representation and the backward euler method.
d the compressed graph representation and the backward euler method while employing ideal positions attraction forces
fig.
<dig> a visualization comparison of trna molecules employing the backward euler method and the ideal positions attraction forces.
a the visualization for a yeast trna utilizing jviz.rna .
b the visualization for a yeast trna utilizing jviz.rna .
c the visualization for an e.coli trna utilizing jviz.rna
discussion
two major objectives have been set out for this work: the first was to improve jviz.rna’s visualization through a new representation, the second was to design an enhanced automatic layout algorithm in light of this new representation and to improve its run-time performance.
both objectives have been achieved through our employment of the compressed graph representation and the backward euler method.
improving jviz.rna’s visualization
comparing the detailed graphs and compressed graph visualization demonstrated that employing the compressed graphs produces visualizations more consistent with current rna visualization methods, and does so at a fraction of the time.
however, for large molecules that gain in time may be offset by the time required by the user to examine and untangle the rna structure in the case of intersecting stems.
this can be addressed by the modification of the attraction force to act as both an attraction and rotation force.
however, the existence of some overlap may still be present for certain structures .
future work to address this limitation would focus on configuring the system to find an equilibrium between the correct positioning of stems and repulsion between the various rna components to prevent them from overlaying each other.
extending the automatic layout algorithm
comparing the two methods of calculating movement for the rna components of the compressed graph revealed that employing the backward euler method produces more stable simulations of the vertexes’ movement, and does so in less time than the forward euler method .
though it is evident the connectivity of the structure determines the degree of run-time improvement, it is evident that all structures we have tested stabilize faster using the backward euler method.
given that the backward euler implementation is much more stable than its forward counter-part, it is the backward euler method that becomes the more desirable choice.
CONCLUSIONS
in this article we described advances made in the representation and layout algorithms for dynamic rna secondary structure visualization.
we reviewed existing tools and algorithms and showed that only few allow for dynamic visualization.
one such tool is jviz.rna.
we discussed its shortcomings in terms of layout, stability and run-time performance and proposed several improvements based on a compressed graph representation and advanced numerical integration methods.
we presented two graph based representations for rna visualization, as well as two methods to create dynamic rna structures that lay themselves out automatically and respond to user interaction.
the utilization of compressed graphs as a model of the rna structure, the experiments shown here profiling their performance, and examining the underlying physics, demonstrate a substantial improvement to the original representation and layout algorithms employed in jviz.rna.
the work on layout conventions was greatly influenced by feedback from life science collaborators.
the new algorithms have increased stability for automatic layout, reduced overlap of structural elements that decreases the need for user intervention, and increased run time performance to allow for the handling of larger rna structures.
having examined the basic properties of compressed graph behaviour, we can verify it is a better tool to produce dynamic and responsive rna models than its detailed counter-part.
we have also discovered a few important areas of improvement such as stem orientation relative to loops, and prevention of structural element intersection, and provided improvements to the layout algorithm to handle these issues.
by comparing the forward and backward euler methods we demonstrated the superiority of the backward euler method in its ability to support larger time steps without losing stability, and consequently, allowing for faster simulations of the rna compressed graph.
our future work will focus on incorporating pseudoknot representation into the compressed graph model, to allow for the visualization of pseudoknotted structures.
additionally, constructing and modifying rna structures will also be explored.
overall, this manuscript has explored the use of compressed graphs to improve the layout of rna secondary structures, as well as the best physics based simulation method for such an implementation.
the results presented demonstrate that both the compressed graph representation, as well as the backward euler integrator, greatly enhance the run-time performance and usability.
we anticipate these findings to benefit other researchers in rna structure visualization, or more generally, biological structure visualization, as the underlying ideas are transferrable.
we also provide a tool that is platform independent, easy to use, and can quickly render publication quality structure images.
we would anticipate that many researchers in rna structure will find this tool useful and that it will find wide acceptance.
we believe the technical details discussed in this manuscript will impact how other visualization researchers think about dynamic structure visualization and we see the impact of this work in both providing a useful software tool as well as presenting a methodology for other visualization tools to adopt.
endnote
<dig> the original ids of the structures were obtained from the comparative rna website   <cit> , the protein data bank   <cit> , the signal recognition particle database   <cit> , and the rna families database   <cit> .
additional file
additional file  <dig> the file jviz <dig> _complete is a zip file containing a java executable file , a user manual in pdf format , and a subfolder containing rna secondary structure files in.ct format for the rna structures visualized in this manuscript .
abbreviations
crwcomparative rna website
dnadeoxyribo-nucleic acid
ntnucleotide
pdbprotein data bank
rfamrna families database
rnaribo-nucleic acid
rrnaribosomal rna
srpdbsignal recognition particle database
trnatransfer rna
utruntranslated region
electronic supplementary material
the online version of this article  contains supplementary material, which is available to authorized users.

 rna and its structure ribo-nucleic acid is a polymer of nitrogenous bases, composed mainly of adenine, cytosine, guanine, and uracil. rna is very similar to deoxyribo-nucleic acid in its basic composition, but while dna is regularly found as two complimentary strands, rna can be found as a single strand of nucleotides. this primary structure then folds over itself into a secondary structure when the bases in the rna strands pair up via hydrogen bonding. the rna molecule can then twist, fold, or otherwise change its conformation in 3d space, giving it a functional three dimensional form, known as the tertiary structure. single stranded, functional rna is an important agent in many biological processes. from humans to bacteria and viruses, there are many examples of rna molecules that are important to understand, classify, and research. some notable examples include rna motifs that allow viruses to manipulate host replication machinery, bacterial rna motifs that give rise to antibiotic resistance, and man-made rna molecules designed for therapeutics. rna secondary structure visualization there are many rna visualization tools that have been developed, and two excellent reviews of them can be found in, with notable examples that are still available including varna, jviz.rna, forna, pseudoviewer, 4sale, assemble, rna2dmap, r2r, and r-chie. all visualization software developed for rna have as their goal to display an informative structure of the rna molecule, usually focusing on its secondary structure, that can be annotated and used to convey information in presentations, publications, and any other two-dimensional media. however, the majority of rna visualization software designed produce a static layout of the rna molecule that may not be ideal for the user. while for small rna molecules such as transfer rna, this problem almost never arises, for large rna molecules, this layout can be such that sections of the rna overlap each other, making annotation of certain regions problematic and uninformative. there are only three notable examples that create dynamic layouts which are responsive to user interactions: jviz.rna, pseudoviewer, and varna. the designers of varna do not explicitly state how they construct the rna molecule and how the algorithm responsible for user response behaves, but one can estimate how the algorithm operates from interacting with the software as a web applet. the rna structure is translated into a graph where loops make up the vertexes and stems make up the edges. thus, by dragging the stems, the user can arrange the layout of the rna molecule. while this allows users to fully customize the rna layout to their needs. the high degree of user involvement might make the task seem very daunting for large rna molecules. pseudoviewer is another application that allows its users to manipulate the rna structure. originally an application designed focusing on rna pseudoknots, pseudoviewer puts a great deal of effort into creating the initial layout of the rna molecule. additionally, the user can manipulate the rna structural motifs. however, certain manipulations of the rna conformation destabilize the system and cause the rna model to break apart. furthermore, since pseudoviewer’s focus is primarily on pseudoknotted rna structures, it tends to arrange the rna structure layout focusing very heavily on clear display of pseudoknot types, at the expense of the aesthetics related to the rest of the structure. jviz.rna, a third software designed for dynamic rna visualization, employs a different approach to creating the rna model. jviz.rna translates the rna molecule into a graph as well, but maps each nucleotide to a vertex and each bond between nucleotides to an edge. jviz.rna then uses repulsion and attraction forces between all nucleotides to calculate the position and movement. this process continues until the forces reach an equilibrium for all nucleotides. users can still move the individual nucleotides, and by doing so interact with the rna structure. mapping each nucleotide into a vertex creates a graph with a high number of vertexes and edges. as such, we denote this method as constructing a detailed graph. a software similar to jviz.rna, forna, also uses a detailed graph representation in order to construct a dynamic rna model. all nucleotides and chemical bonds are translated into vertexes and edges, and an automatic layout is constructed utilizing attraction and repulsion forces, as well as invisible "helper vertexes" which aid in the improvement of loop appearance. like the previous three software tools, forna allows for users to interact with the constructed dynamic model. of the four software tools mentioned, the approach employed by jviz.rna and forna relies mostly on the program to produce the layout, rather than require user intervention. this approach makes the production of rna images less involved for the user, due to very little, if any, overlap even for large molecules. however, both forna and jviz.rna require more computation time for structure layout than pseudoviewer or varna. for very large structures of over 900nt, waiting for the automatic layout can be very inconvenient, and interaction with the structure becomes problematic as the structure’s movement becomes delayed. in addition, current jviz.rna output contains some inconsistencies with regards to current accepted rna visualization guidelines. the following section discusses these shortcomings in more detail. motivation while the current implementation for jviz.rna produces dynamic rna models that display secondary structure elements very well, the simple graph representation described presents some visual shortcomings. most rna images found in the literature follow several visualization norms, and two such norms that are very important are that stems are drawn such that the distance between base-pairs is consistent across the stem, and that loops are drawn as circular elements wherever they occur in the structure. figure demonstrates such limitations of jviz.rna. while fig. 1 a contains stems with consistent base-pair distances and loops which are clearly distinguishable by their circular nature, fig. 1 b contains stems where the base pair distance varies across the stem, and some loops that are not immediately visible. fig. the visualization differences observed in jviz.rna compared to an rna image which highlights rna visualization norms in literature. a the yellow fever virus 3’ untranslated region. image taken from and used with permission, an example produced by jviz.rna of the s. cervisiae 5s ribosomal rna the main motivation for the work presented in this manuscript was to address the visual shortcomings presented by the current algorithm employed in jviz.rna, as well as improvements in the run-time performance. the objectives of this work were: to create an rna representation which was more consistent with existing rna visual conventions, such as round loops and equidistant base pairs. to design an automatic layout algorithm which works with the new representation, while introducing noticeable speed-ups to that automatic layout algorithm, and reduce overlap of structural elements. both objectives address important areas for improvement in jviz.rna. while currently the resulting rna molecule is laid out very clearly, personal feedback from rna researchers, as well as visual comparison with other software, demonstrates that it ignores several visualization conventions such as the shape of loops and stems. this visualization pattern makes it more difficult to share informative images and diagrams about rna, as the resulting visualization is not in the format most rna scientists expect. another challenge the current setup faces is its time complexity. calculating the attraction force for each nucleotide n i is in o since there are at most three nucleotides bonded to it, so the total calculation time for all the nucleotides’ attraction forces is in o at each iteration. however, calculating the repulsion forces for each nucleotide is in o since it must account for the repulsion of all other nucleotides, so the total calculation time for all the nucleotides’ repulsing forces is in o. this run-time can make the automatic layout algorithm perform slowly for large rna structures such as 16s ribosomal rna. as such, the work presented in this manuscript was set to implement the improvements while reducing the run-time required for the rna structures to stabilize. in order to achieve this two-pronged effect, the method by which jviz.rna builds the graph to represent the rna structure had to be modified; the simple graphs built were replaced by a more compressed representation of the rna molecule, named compressed graphs. the work in this manuscript is divided into three main sections. first, we discuss how the rna molecule can be mapped into a graph with a smaller number of vertexes, a compressed graph, similar to the one used by varna. secondly, we profile the performance of the original version of jviz.rna against the performance obtained by employing the reduced graph. third and finally, a superior method for calculating movement is presented and profiled against the original movement calculation method. methods language, implementation, and system the code presented in this manuscript was implemented using java. the swing library was used for the graphical component of the code. measurements were all taken on a pc with an intel core i7- ghz processor, running ubuntu. lts. constructing and manipulating the new graph one intuitive method of decreasing the run-time for the algorithm mentioned is to decrease the number of vertexes simulated. since the run-time for the algorithm at every iteration is in order of o, decreasing the number of vertexes would theoretically have a tremendous effect on reducing the run-time. however, the mapping of the structure into vertexes and edges must be done in a way that still produces visually pleasing layouts and rna diagrams. inspired by varna, we have employed a representation which maps each rna loop, as well as every stem base pair, to a vertex, and connects those via edges.. fig. the compressed graph mapped to an rna structure. a the main rna elements are compressed into vertexes where each vertex represents an rna loop element, or a stem base pair. b the nucleotides belonging to each rna element are drawn on top of the underlying rna compressed graph. c the resulting rna representation contains less vertexes than there are nucleotides, and a more familiar visual layout furthermore, we have implemented the system in such a way that repulsion only occurs between loops, and not base pairs. since the repulsion step is the main time consuming step of each iteration ), decreasing the number of participating vertexes in the repulsion interaction should greatly reduce the run time of the algorithm. constructing the system in such a way that only loops experience repulsion ensures that loops will be pushed away from each other, thus not intersecting each other. in theory, this should aid the structure in adopting a final layout that has minimal or no intersection of any structural elements. at the initial step of the simulation, the rna graphs are placed in a naive initial layout which is inspired from a circular representation of the rna molecule. then, an iterative process begins in which the structure is slowly brought to a stable position by newtonian inspired spring and repulsion forces. fig. the initial vertex layout process demonstrated using a sample theoretical rna molecule. l l l l l and l represent loops while b b b b b b and b represent base pairs. the loops and base pair vertexes are connected via black edges. a the rna nucleotides are first laid out in a circle. b each set of nucleotides has its average position calculated, and the vertex corresponding to that set is placed in that average position. following this step, the iterative process of stabilization begins jviz.rna and the newtonian model originally jviz.rna mapped the rna structure into a detailed graph, g={v,e}. in the detailed graph representation, each nucleotide is a vertex v∈v, and each chemical bond corresponds to an edge e∈e. the entire structure is initially laid out in a circle, and an iterative process designed to move the structure into a stable layout begins. in this paper, we employ the compressed graph representation, where each structural element is a vertex v∈v, and the edges are graph elements which connect the different structure elements. for the purposes of the following sections, the notation p→ will be used to denote the positions of the different vertexes which represent the rna structures, and p→n,ki will be used to denote the position of vertex i, at time-step n, during the k-th newton iteration. the most basic computation done at each iteration is the unit vector function, u→. this function calculates the unit vector pointing from point p→j to point p→i as follows: u→p→i,p→j=p→i−p→jp→i−p→j in each iteration, each vertex moves based on two forces: repulsion and attraction. the repulsion forces each vertex v i experiences from vertex v j can be described as: r→p→i,p→j=gp→i−p→j2×u→p→i,p→j where u→ is the unit vector function showing the direction from vertex v j to vertex v i, and g is a coefficient to control the size of the force experienced. the attraction forces each vertex v i experiences from vertex v j can be described as: a→p→i,p→j=k×p→j−p→i+rideal×u→p→i,p→j where u→ is again the unit vector function, k is an attraction coefficient to control for the size of the force, and r ideal is the ideal desired distance between the vertexes v i and v j. the iterative process stops when the forces for all vertexes have reached equilibrium, or when for all vertexes {v i|1≤i≤n} the following holds: ∀vi,∑vj∈l,j≠ir→p→i,p→j+∑vj∈cia→p→i,p→j≤ε where c i is the set of all vertexes connected to vertex v i, and l is the set of all loops. that is to say, the iterative process stops when the sum of the forces acting on the vertexes is smaller than ε. setting ε= will force the simulation to continue to calculate until the forces are perfectly at odds, but setting a small value for ε allows the layout algorithm to stop sooner when achieving a stable structure. ε as such, controls the degree of stability required before simulation of the structure’s movement stops. in this work, we chose to explore two methods of implementing the physics based rna model: the forward euler method, and the backward euler method. the two methods make it possible to evaluate the movement of the vertexes. however, the latter is more numerically stable than the former, and allows for greater time steps and faster visualizations, as well as a more stable user interaction experience. the forward euler method the euler method is a first-order integration method which belongs to a larger class called the runge-kutta methods. the simplest version is called the forward euler method. this method of calculating each time step can be expressed in the following manner: tn+1=tn+Δtp→n+1i=p→ni+Δtf which means the time t n is advanced by the time-step Δ t and then the position of the vertex v i is updated based on the size of the time-step, and the current behaviour of the particle, f. when applied to the movement of the rna vertexes, the forward euler method can be written as: tn+1=tn+Δtf=∑vj∈l,j≠ir→p→ni,p→nj+∑vj∈cia→p→ni,p→njp→n+1i=p→ni+Δtftn,p→ni where in this case, the behaviour of the particle with regard to its position is the sum of repulsion forces and attraction forces acting on the particle. since base pair vertexes do no participate in the repulsion step, the expression for a base pair vertex’s forward euler implementation will be: tn+1=tn+Δtftn,p→ni=∑vj∈cia→p→ni,p→njp→n+1i=p→ni+Δtftn,p→ni however, since the implementation of this expression is trivially similar to the expression in, the remainder of this text will focus on that expression, with the implications for the expression in being omitted for brevity. the main drawback presented by the forward euler method is its numerical instability. simply put, when the time-step Δ t is too long, or the coefficients which control the simulation become too large, the simulation does not stabilize into an equilibrium. in fact, it can become increasingly unstable. the solution to this drawback lies in the implementation of the backward euler method, which takes this instability into account. the backward euler method much like the forward euler method is described as explicit, there is an implicit euler method; the backward euler method. generally, it is defined as: tn+1=tn+Δtp→n+1i=p→ni+Δtftn,p→n+1i where f is again a function that describes the movement of the object. notice it is very similar to the explicit method, but the term p→n+1i appears on both sides of the equation. as a result, finding p→n+1i is no longer a simple issue of updating the timestep, but it is that of solving for it algebraically. in the case of the current simulation, the backward euler method would yield the following expression: tn+1=tn+Δtftn,p→n+1i=∑vj∈l,j≠ir→p→n+1i,p→nj+∑vj∈cia→p→n+1i,p→njp→n+1i=p→ni+Δtftn,p→n+1i which becomes a fairly difficult equation to solve for p→n+1i directly. instead, an approximation is used to solve for p→n+1i. applying newton’s method to solve the backward euler expression the expression in can be rearranged to produce the following equation: p→n+1i=p→ni+Δt∑vj∈l,j≠ir→p→n+1i,p→nj+∑vj∈cia→p→n+1i,p→nj which can be rewritten as: f→p→n+1i=0→=−p→n+1i+p→ni+Δt∑vj∈l,j≠ir→p→n+1i,p→nj+∑vj∈cia→p→n+1i,p→nj meaning the solution for p→n+1i is the root of the function f→. while it may be difficult to solve for the root directly, newton’s method offers an approach for approximating the root of the vector function f→p→n+1i. defining the vector function’s components as outlined in, it is necessary to define each of the components in f→ individually so that their derivatives can then be found with respect to each of the variables. in the case of the rna simulation, the function f→ contains only two components; f x and f y which are each defined as: fxp→n+1i=−xn+1i+xni+Δt∑vj∈l,j≠irxp→n+1i,p→nj+∑vj∈ciaxp→n+1i,p→njfyp→n+1i=−yn+1i+yni+Δt∑vj∈l,j≠iryp→n+1i,p→nj+∑vj∈ciayp→n+1i,p→nj this definition requires both r→ and a→ to be defined in terms of their x and y components as: rxp→n+1i,p→nj=gxn+1i−xnj2+yn+1i−ynj2×uxp→n+1i,p→njryp→n+1i,p→nj=gxn+1i−xnj2+yn+1i−ynj2×uyp→n+1i,p→njaxp→n+1i,p→nj=k×xnj−xn+1i+rideal×uxp→n+1i,p→njayp→n+1i,p→nj=k×ynj−yn+1i+rideal×uyp→n+1i,p→njuxp→n+1i,p→nj=xn+1i−xnjxn+1i−xnj2+yn+1i−ynj2uyp→n+1i,p→nj=yn+1i−ynjxn+1i−xnj2+yn+1i−ynj finding the components’ derivatives in order to apply newton’s method to the rna model, the jacobian matrix d of the vector function f→ needs to be defined. in order to do so, expressions for all partial derivatives of the components in eqs. - need to be defined, where each component has two partial derivatives; with respect to xn+1i and with respect to yn+1i. the derivation of each component’s partial derivatives is quite long and is not the main focus of this article. therefore, for brevity purposes, the individual derivatives are outlined in the set of eqs. -: δfxδxn+1ip→n+1i=−1+Δt∑vj∈l,j≠iδrxδxn+1ip→n+1i,p→nj+∑vj∈ciδaxδxn+1ip→n+1i,p→njδfxδyn+1ip→n+1i=Δt∑vj∈l,j≠iδrxδyn+1ip→n+1i,p→nj+∑vj∈ciδaxδyn+1ip→n+1i,p→njδfyδxn+1ip→n+1i=Δt∑vj∈l,j≠iδryδxn+1ip→n+1i,p→nj+∑vj∈ciδayδxn+1ip→n+1i,p→njδfyδyn+1ip→n+1i=−1+Δt∑vj∈l,j≠iδryδyn+1ip→n+1i,p→nj+∑vj∈ciδayδyn+1ip→n+1i,p→nj r=xn+1i−xnj2+yn+1i−ynj2δrxδxn+1ip→n+1i,p→nj=δuxδxn+1ip→n+1i,p→nj×gr−2gxn+1i−xnjr2×uxp→n+1i,p→njδrxδyn+1ip→n+1i,p→nj=δuxδyn+1ip→n+1i,p→nj×gr−2gyn+1i−ynjr2×uxp→n+1i,p→njδryδxn+1ip→n+1i,p→nj=δuyδxn+1ip→n+1i,p→nj×gr−2gxn+1i−xnjr2×uyp→n+1i,p→njδryδyn+1ip→n+1i,p→nj=δuyδyn+1ip→n+1i,p→nj×gr−2gyn+1i−ynjr2×uyp→n+1i,p→nj δaxδxn+1ip→n+1i,p→nj=k×−1+rideal×δuxδxn+1ip→n+1i,p→njδaxδyn+1ip→n+1i,p→nj=k×rideal×δuxδyn+1ip→n+1i,p→njδayδxn+1ip→n+1i,p→nj=k×rideal×δuyδxn+1ip→n+1i,p→njδayδyn+1ip→n+1i,p→nj=k×−1+rideal×δuyδyn+1ip→n+1i,p→nj r=xn+1i−xnj2+yn+1i−ynj2δuxδxn+1ip→n+1i,p→nj=yn+1i−ynj2r3δuxδyn+1ip→n+1i,p→nj=−yn+1i−ynjxn+1i−xnjr3δuyδxn+1ip→n+1i,p→nj=−yn+1i−ynjxn+1i−xnjr3δuyδyn+1ip→n+1i,p→nj=xn+1i−xnj2r and the matrix d is defined as: dp→n+1i=δfxδxn+1ip→n+1iδfxδyn+1ip→n+1iδfyδxn+1ip→n+1iδfyδyn+1ip→n+1i. constructing the newton step given the function f→ and the matrix d, progressively better estimates for the value of p→n+1i can be found by applying the following newton step: p→n+ k+1i=p→n+ ki−f→p→n+ ki×d−1p→n+ ki where d−1p→n+ ki is the inverse matrix of dp→n+ ki. that is, at every newton step k+ the value of both the function f→ and its components’ derivatives, encapsulated in the matrix d − are evaluated at the point p→n+ ki, that is, the point p→n+1i from the previous newton step. the initial estimate, p→n+ i can be obtained by applying the forward euler. as more newton steps are repeated, a better and better estimate for p→n+1i emerges. however, each newton step increases the run-time of each iteration of the algorithm. in general, each additional newton step increases the run time of the physics based simulation by o where l is the number of loops in the simulation. experimental parameters and test-bed structures for the purposes of these experiments, rna molecules were chosen from the rna strand v database, and were run under two different configurations. the configurations and their parameters can be found in table while the structure details can be found in table 2 the structure lengths are given in “nt,” which stands for “nucleotides.” different time-steps were chosen for the different configurations. configuration was assigned the highest time-steps it can support without losing stability. configuration can handle larger time steps, but the choice of time-step influences the choice for the number of newton iterations. therefore, a value of was chosen to support satisfactory convergence within newton iterations. each structure was run times and the cpu time of the run was measured until the structure stabilized. the average run-time was calculated and plotted. if a structure’s stabilization process took more than mins it was terminated and its stabilization time was taken as s. improving the attraction force calculations the system of forces described in the previous section allowed the rna structure simulation to stabilize and present the rna structural elements much better than the former jviz.rna implementation. however, the resulting stable layouts were not satisfactory due to the overlap artefacts created. stems would often overlap loops and would not stabilize into their correct position based on their connectivity to the loops. while a user could, in theory, address such a problem manually, we felt there is room for further improvements. in order to correct the overlap artefacts, a slight modification to the attraction force calculation was implemented. fig. the visualization result obtained for the nt rna. a the visualization obtained with jviz’s detailed graph representation. b the visualization obtained with jviz’s compressed graph representation and the forward euler method. c the visualization obtained with jviz’s compressed graph representation and the backward euler method originally, the attraction forces would apply attraction between the centres of two vertexes. however, with a slight modification, each vertex can store the ideal positions for each stem protruding from it. using these ideal positions in the equation for a→ to move each vertex to its ideal position and orientation. the resulting layouts prove to be much more visually appealing and containing much less overlap, especially for smaller rna structures. fig. implementing the ideal position attraction forces causes the stems to align with their ideal layout. a originally, attraction forces were acting between base pairs, and the loops, attracting the centres of the vertexes directly. b the resulting layout contained artefacts of distorted stems, since base-pairs were unaware of their positions relative to loops. c the idealized attraction forces employ the ideal positions of the stems to attract the base-pair vertexes. d the resulting layout when employing the ideal positions is aware of the position stems should take relative to their parent loops  comparison of jviz.rna’s performance employing the forward and backward euler methods of the run times was taken and plotted in fig. as can be seen, the run times of the forward euler method are often ≈ times longer than the backward euler run times. considering the fact that no structure was allowed longer than seconds to stabilize, it is fair to assume that under the current parameters of k and g, the difference in run time could have been even greater for some structures. fig. the run-times of jviz.rna’s compressed graph representations employing both the forward and backward euler methods fig. the run-times ) of jviz.rna’s compressed graph representations employing both the forward and backward euler methods one would expect that the run-times would increase in a quadratic order to the number of nucleotides. however, while there is a general increase in run time with structure size, some small structures take longer than larger ones to stabilize. this observation points to the fact that the connectivity of the structure plays a very important role in its stabilization time. overall, a structure x composed of times as many nucleotides as structure y would take longer to stabilize, but it may not be straightforward to deduce exactly how much longer. even the number of vertexes in a given structure does not provide a good heuristic to calculating the difference in stabilization time for both the forward and backward euler. despite the relative uncertainty in the relationship between a given structure’s run time and its size, there is a great deal of certainty that the backward euler proved superior when compared to the forward euler. first, it can produce stable layouts employing a time step times larger than the forward euler method without losing stability. second, it exhibits much faster run-time performance. as demonstrated in this work, some large structures may pose a challenge to a system which takes smaller time step since the topology of the structure itself dictates how long it will take to stabilize visual comparison of the different algorithms in order to get a full appreciation of the advantages of the different methods explored in this work, as well as potential future improvements, it is necessary to look at both the run-times reported in figs. and as well as at the resulting visualizations each method produced. figures and demonstrate the visualizations produced when employing the four different methods explored in this paper. comparing the images produced by the compressed and detailed graphs reveals additional differences between the methods. it is immediately evident that the figures produced by employing the compressed graph adhere more strictly to rna visualization conventions; namely, the circular loops, and the constant distance between base pairs. however, at the same time, the detailed graph representation demonstrates some advantages over the compressed graph images. first, there are no cases of stems that intersect, which contributes to less user intervention being required to “untangle” the structure. the compressed graph representations, on the other hand, occasionally have stems that intersect and would require the user to explore the structure to resolve such conflicts. though this drawback is addressed to a large extent by substituting the ideal positions as the attraction points for the vertexes, the need to manually untangle the structure may persist in certain cases. fig. the visualization result obtained for the nt rna utilizing: a the detailed graph representation. b the compressed graph representation and the forward euler method. c the compressed graph representation and the backward euler method. d the compressed graph representation and the backward euler method while employing ideal positions attraction forces fig. the visualization result obtained for the nt rna utilizing: a the detailed graph representation. b the compressed graph representation and the forward euler method. c the compressed graph representation and the backward euler method. d the compressed graph representation and the backward euler method while employing ideal positions attraction forces fig. the visualization result obtained for the nt rna utilizing: a the detailed graph representation utilizing: a the detailed graph representation. b the compressed graph representation and the forward euler method. c the compressed graph representation and the backward euler method. d the compressed graph representation and the backward euler method while employing ideal positions attraction forces fig. the visualization result obtained for the nt rna utilizing: a the detailed graph representation. b the compressed graph representation and the forward euler method. c the compressed graph representation and the backward euler method. d the compressed graph representation and the backward euler method while employing ideal positions attraction forces fig. the visualization result obtained for the nt rna utilizing: a the detailed graph representation. b the compressed graph representation and the forward euler method. c the compressed graph representation and the backward euler method. d the compressed graph representation and the backward euler method while employing ideal positions attraction forces fig. a visualization comparison of trna molecules employing the backward euler method and the ideal positions attraction forces. a the visualization for a yeast trna utilizing jviz.rna. b the visualization for a yeast trna utilizing jviz.rna. c the visualization for an e.coli trna utilizing jviz.rna discussion two major objectives have been set out for this work: the first was to improve jviz.rna’s visualization through a new representation, the second was to design an enhanced automatic layout algorithm in light of this new representation and to improve its run-time performance. both objectives have been achieved through our employment of the compressed graph representation and the backward euler method. improving jviz.rna’s visualization comparing the detailed graphs and compressed graph visualization demonstrated that employing the compressed graphs produces visualizations more consistent with current rna visualization methods, and does so at a fraction of the time. however, for large molecules that gain in time may be offset by the time required by the user to examine and untangle the rna structure in the case of intersecting stems. this can be addressed by the modification of the attraction force to act as both an attraction and rotation force. however, the existence of some overlap may still be present for certain structures. future work to address this limitation would focus on configuring the system to find an equilibrium between the correct positioning of stems and repulsion between the various rna components to prevent them from overlaying each other. extending the automatic layout algorithm comparing the two methods of calculating movement for the rna components of the compressed graph revealed that employing the backward euler method produces more stable simulations of the vertexes’ movement, and does so in less time than the forward euler method. though it is evident the connectivity of the structure determines the degree of run-time improvement, it is evident that all structures we have tested stabilize faster using the backward euler method. given that the backward euler implementation is much more stable than its forward counter-part, it is the backward euler method that becomes the more desirable choice.  in this article we described advances made in the representation and layout algorithms for dynamic rna secondary structure visualization. we reviewed existing tools and algorithms and showed that only few allow for dynamic visualization. one such tool is jviz.rna. we discussed its shortcomings in terms of layout, stability and run-time performance and proposed several improvements based on a compressed graph representation and advanced numerical integration methods. we presented two graph based representations for rna visualization, as well as two methods to create dynamic rna structures that lay themselves out automatically and respond to user interaction. the utilization of compressed graphs as a model of the rna structure, the experiments shown here profiling their performance, and examining the underlying physics, demonstrate a substantial improvement to the original representation and layout algorithms employed in jviz.rna. the work on layout conventions was greatly influenced by feedback from life science collaborators. the new algorithms have increased stability for automatic layout, reduced overlap of structural elements that decreases the need for user intervention, and increased run time performance to allow for the handling of larger rna structures. having examined the basic properties of compressed graph behaviour, we can verify it is a better tool to produce dynamic and responsive rna models than its detailed counter-part. we have also discovered a few important areas of improvement such as stem orientation relative to loops, and prevention of structural element intersection, and provided improvements to the layout algorithm to handle these issues. by comparing the forward and backward euler methods we demonstrated the superiority of the backward euler method in its ability to support larger time steps without losing stability, and consequently, allowing for faster simulations of the rna compressed graph. our future work will focus on incorporating pseudoknot representation into the compressed graph model, to allow for the visualization of pseudoknotted structures. additionally, constructing and modifying rna structures will also be explored. overall, this manuscript has explored the use of compressed graphs to improve the layout of rna secondary structures, as well as the best physics based simulation method for such an implementation. the results presented demonstrate that both the compressed graph representation, as well as the backward euler integrator, greatly enhance the run-time performance and usability. we anticipate these findings to benefit other researchers in rna structure visualization, or more generally, biological structure visualization, as the underlying ideas are transferrable. we also provide a tool that is platform independent, easy to use, and can quickly render publication quality structure images. we would anticipate that many researchers in rna structure will find this tool useful and that it will find wide acceptance. we believe the technical details discussed in this manuscript will impact how other visualization researchers think about dynamic structure visualization and we see the impact of this work in both providing a useful software tool as well as presenting a methodology for other visualization tools to adopt. endnote the original ids of the structures were obtained from the comparative rna website, the protein data bank, the signal recognition particle database, and the rna families database. additional file additional file the file jviz _complete is a zip file containing a java executable file, a user manual in pdf format, and a subfolder containing rna secondary structure files in.ct format for the rna structures visualized in this manuscript. abbreviations crwcomparative rna website dnadeoxyribo-nucleic acid ntnucleotide pdbprotein data bank rfamrna families database rnaribo-nucleic acid rrnaribosomal rna srpdbsignal recognition particle database trnatransfer rna utruntranslated region electronic supplementary material the online version of this article contains supplementary material, which is available to authorized users. 
this is done first by presenting an alternative method for mapping the rna molecule into a graph, which we call the compressed graph, and then employing advanced numerical integration methods for the compressed graph representation. the results presented demonstrate that both the compressed graph representation, as well as the backward euler integrator, greatly enhance the run-time performance and usability. currently, jviz.rna employs a unique method for the creation of the rna molecule layout by mapping the rna nucleotides into vertexes in a graph, which we call the detailed graph, and then utilizes a newtonian mechanics inspired system of forces to calculate a layout for the rna molecule. comparing the two numerical integration methods demonstrates the higher stability of the backward euler method, and its resulting ability to handle much larger time steps, a high priority feature for any software which entails user interaction. the work in this manuscript presents the preferred use of compressed graphs to detailed ones, as well as the advantages of employing the backward euler method over the forward euler method. rna visualization software tools have traditionally presented a static visualization of rna molecules with limited ability for users to interact with the resulting image once it is complete. comparing the compressed graph and detailed graph implementations, we find that the compressed graph produces results more consistent with rna drawing conventions. the online version of this article contains supplementary material, which is available to authorized users. the work presented here focuses on improvements to jviz.rna that allow the drawing of rna secondary structures according to common drawing conventions, as well as dramatic run-time performance improvements. these improvements produce more stable as well as visually aesthetic representations of the rna secondary structures.
 rna visualization software tools have traditionally presented a static visualization of rna molecules with limited ability for users to interact with the resulting image once it is complete. only a few tools allowed for dynamic structures. one such tool is jviz.rna. currently, jviz.rna employs a unique method for the creation of the rna molecule layout by mapping the rna nucleotides into vertexes in a graph, which we call the detailed graph, and then utilizes a newtonian mechanics inspired system of forces to calculate a layout for the rna molecule. the work presented here focuses on improvements to jviz.rna that allow the drawing of rna secondary structures according to common drawing conventions, as well as dramatic run-time performance improvements. this is done first by presenting an alternative method for mapping the rna molecule into a graph, which we call the compressed graph, and then employing advanced numerical integration methods for the compressed graph representation.  comparing the compressed graph and detailed graph implementations, we find that the compressed graph produces results more consistent with rna drawing conventions. however, we also find that employing the compressed graph method requires a more sophisticated initial layout to produce visualizations that would require minimal user interference. comparing the two numerical integration methods demonstrates the higher stability of the backward euler method, and its resulting ability to handle much larger time steps, a high priority feature for any software which entails user interaction.  the work in this manuscript presents the preferred use of compressed graphs to detailed ones, as well as the advantages of employing the backward euler method over the forward euler method. these improvements produce more stable as well as visually aesthetic representations of the rna secondary structures. the results presented demonstrate that both the compressed graph representation, as well as the backward euler integrator, greatly enhance the run-time performance and usability. the newest iteration of jviz.rna is available at https://jviz.cs.sfu.ca/download/download.html. electronic supplementary material the online version of this article contains supplementary material, which is available to authorized users. keywords rnavisualizationgraph layoutnumerical integrationnatural sciences and engineering research council of canada611362shabash boris natural sciences and engineering research council of canadacgs-dwiese kay c. issue-copyright-statement© the author 2017 