Modelling Biochemical Operations on RNA
Secondary Structures⋆

arXiv:cs/0306016v1 [] 3 Jun 2003

Mercè Llabrés and Francesc Rosselló
Dept. of Mathematics and Computer Science,
Research Institute of Health Science (IUNICS),
University of the Balearic Islands,
07122 Palma de Mallorca (Spain)
{merce.llabres,cesc.rossello}@uib.es

Abstract. In this paper we model several simple biochemical operations
on RNA molecules that modify their secondary structure by means of a
suitable variation of Große-Rhode’s Algebra Transformation Systems.

1

Introduction

Biochemical processes are responsible for most of the information processing that
takes place inside the cell. In the recent years, several representations and simulations of specific biochemical processes have been proposed using well known
rewriting formalisms borrowed from Theoretical Computer Science. Let us mention, for instance, Fontana’s lambda calculus chemistry [3,4], recently revised by
Müller [9] (for a recent survey on artificial chemistry, see [14]), the stochastic
Petri net approach [5], the π-calculus representation of biochemical processes
carried out by networks of proteins [10], and the graph replacement approach to
DNA operations [8]. In the latter, an ad hoc graph replacement formalism is developed to formalize DNA biochemical operations like annealing or denaturing,
by considering DNA double strands to be special graphs.
There is another popular line of research in theoretical biochemistry that
aims to represent the three-dimensional structure of biopolymers, and specially
of DNA and RNA, by means of different kinds of formal grammars; see, for
instance, [7,13] for two surveys on this topic. The ultimate goal of such a representation is to understand how the three-dimensional structure of a biopolymer
is determined from its sequence of monomers (for instance, how the sequence
of ribonucleotides of an RNA molecule determines its secondary structure; see
below for the relevant details of RNA’s biochemistry), and how this structure
evolves when the biopolymer is modified through biochemical processes.
Sooner or later, this two lines of research should intersect, and the main
goal of this paper is to move these two lines of research a step closer. We formalize some simple biochemical processes on RNA molecules, like for instance
⋆

This work has been partially supported by the Spanish DGES, grant BFM2000-1113C02-01.

ribonucleotide removals or mutations, and their effect on their three-dimensional
structures by means of a variant of Große Rhode’s Algebra Transformation Systems (ATS) [6] on partial algebras [1] representing RNA biomolecules.
Before entering into more details, it is time to introduce a little biochemistry.
As probably everybody knows, RNA molecules, together with DNA molecules
and proteins, form the molecular basis of life. An RNA molecule can be viewed
as a chain of ribonucleotides, and each ribonucleotide is characterized by the
base attached to it, which can be either adenine (A), cytosine (C), guanine
(G) or uracil (U ). An RNA molecule is uniquely determined by the sequence of
bases along its chain, and it has a definite orientation. Such an oriented chain of
ribonucleotides is called the primary structure of the RNA molecule.
In the cell and in vitro, each RNA molecule folds into a specific threedimensional structure that determines its biochemical activity. To determine this
structure from the primary structure of the molecule is one of the main open
problems in computational biology, and partial solutions have been proposed
using Stochastic Context Free Grammars and Dynamic Programming, among
other tools; see, for instance, [2, Chaps. 9, 10].
This three-dimensional structure is held together by weak interactions called
hydrogen bonds between pairs of non-consecutive bases.1 Almost all these bonds
form between complementary bases, i.e., between A and U and between C and
G, but other pairings do also occur sporadically. For simplicity, in this paper we
shall only consider pairings between complementary bases.
In most representations of RNA molecules, the detailed description of their
three-dimensional structure is overlooked and the attention is focused on its secondary structure: the set of its base pairs, or contacts. Secondary structures are
actually a simplified representation of RNA molecules’ three-dimensional structure, but that is enough in some applications, as different levels of “graining”
are suitable for different problems. Two restrictions are usually added to the
definition of secondary structure:
– If two bases bi and bj are paired, then neither bi or bj can bond with any
other base; this restriction is called the unique bonds condition.
– If contacts exist between bases bi and bj and between bases bk and bl , and if
bk lies between bi and bj , then bl also lies between bi and bj ; this restriction
is called the no-pseudoknots condition.
The unique bonds condition simply captures the fact that the “bond” between
two consecutive bases is of different nature, as a part of the molecule’s backbone. The no-pseudoknots condition is usually added in order to enable the use
of dynamic programming methods to predict RNA secondary structures and,
although real three-dimensional RNA structures have (pseudo)knots, we impose
it here to show the scope of our approach: if pseudoknots are allowed, one simply
has to allow them in the algebraic representation of RNA secondary structures
1

Actually, for a hydrogen bond to be stable, the bases involved in it must be several
nucleotides apart, but for simplicity we shall only consider the restriction that they
must be non-consecutive.

and to remove the corresponding production rules from the rewriting system.
Thus,
This allows traditionally to represent an RNA molecule as a labelled graph,
with nodes representing the ribonucleotides, and their labels denoting the bases
attached to them, and arcs of two different kinds: ones representing the order
of the bases in the primary structure (the backbone) and the rest representing
the bonds that form the secondary structure (the contacts) [11,12]. Our representation is slightly different: the backbone is represented by a partial algebra
corresponding, essentially, to a labelled finite chain, and then the contacts are
specified as arcs of a graph on the nodes of the backbone.
There are some biochemical operations that can be carried out on an RNA
molecule. For instance, a ribonucleotide can be added or removed somewhere in
the primary structure, a contact can form between two complementary bases, or
it can be removed, and a base can mutate into another base. These operations
may have collateral effects: for instance, if a base mutates into another one and it
was involved in a contact, then this contact will disappear, as the corresponding
bases will no longer be complementary, and if a nucleotide is removed and as
a consequence two nucleotides forming a contact become consecutive, then this
contact will also break.
It is precisely when we tried to specify these side effects that we were not
able to use simple graph transformation systems in an easy way, and we decided
to use the ATS approach. ATS is a very powerful algebra rewriting formalism,
introduced by M. Große-Rhode in 1999 in order to specify the behavior of complex states software systems. It is operationally described, but not categorically
formalized, and it takes care of side effects of the application of rules, similar
to those found in our work. Unfortunately, even the ATS formalism as defined
in [6], which was designed with software engineering specification applications
in mind, was not suitable, as it stands, for our purposes. Thus we have slightly
modified a simplified version of it, and we have dubbed the resulting formalism Withdrawal-based Algebra Transformation Systems (WATS). The reason is
that, in our approach, the inconsistencies are eliminated by retreating, i.e., by
removing, in a controlled way, the elements and operations that produce them,
while in the original ATS approach the inconsistencies were eliminated by adding
operations and identifying points.
The rest of this paper is organized as follows. In Section 2 we represent RNA
molecules as suitable partial algebras, in Section 3 we briefly introduce the WATS
formalism, and then in Section 4 we show how to represent the aforementioned
biochemical operations on RNA molecules by means of WATS production rules.
A final section on Conclusions closes the paper.

2

RNA Molecules as Partial Algebras

Roughly speaking, we represent the primary structure of an RNA molecule as a
chain n of length n ∈ N with a label in {A, C, G, U } attached to each element of

the chain, representing the base attached to the corresponding ribonucleotide,
and its secondary structure by means of ordered pairs in n × n.
Let Σps be the following many-sorted signature:
Sorts : N at, Bases
Opns : suc : N at → N at
F irst, Last :→ N at
A, C, G, U :→ Bases
minor : N at, N at → N at
label : N at → Bases
κ : Bases → Bases
An RNA primary structure is a finite partial Σps -algebra
P = (PN at , PBases ;
F irstP , LastP , AP , C P , GP , U P , sucP , minorP , labelP , κP )
such that:
i) (PN at ; F irstP , LastP , sucP ) is a chain with successor operation sucP , first
element F irstP and last element LastP .
ii) The operation minorP models the strict minority relation on this chain:
minorP (x, y) = x if and only if there exists some n ≥ 1 such that y =
(sucP )n (x).
iii) The values of the nullary operations AP , C P , GP , U P are pairwise different,
PBases = {AP , C P , GP , U P }, and on this set the operation κP is given by
the involution
κP (AP ) = U P , κP (U P ) = AP , κP (C P ) = GP , κP (GP ) = C P .
iv) The operation labelP is total.
Notice that all these conditions except the last one cannot be specified through
quasi-equations, since they are not satisfied by a trivial (with only one element
of each sort) total Σps -algebra.
Let Σss be now the signature containing Σps and, in addition, the following
sorts and operation symbols:
Sorts : Contacts
Opns : p1 : Contacts → N at
p2 : Contacts → N at
An RNA secondary structure is a partial Σss -algebra
B = (BN at , BBases , BContacts ;
B
F irstB , LastB , AB , C B , GB , U B , sucB , minorB , labelB, κB , pB
1 , p2 )

whose Σps -reduct is an RNA primary structure and it satisfies moreover the
following quasi-equations:
B
(1) pB
1 and p2 are total
B
(2) pB
1 (x) = p1 (y) ⇒ x = y
B
(3) pB
2 (x) = p2 (y) ⇒ x = y
B
(4) pB
1 (x) = p2 (y) ⇒ x = y
B
B B
(5) minor(succB (pB
1 (x)), p2 (x)) = succ (p1 (x))
B
B
B
B
B
(6) minor(pB
1 (x), p1 (y)) = p1 (x) ∧ minor(p1 (y), p2 (x)) = p1 (y)
B
B
B
=⇒ minor(p2 (y), p2 (x)) = p2 (y)
B B
(7) κB (labelB(pB
1 (x))) = label (p2 (x))

In such an RNA secondary structure, each element c of sort Contacts repreB
sents, of course, a contact between nucleotides pB
1 (c) and p2 (c). Equations (2),
(3) and (4) represent the unique bonds condition, equation (5) represents the fact
that there cannot exist a contact between a nucleotide and itself or its successor
in the primary structure, equation (6) represents the no-pseudoknots condition,
and equation (7) represents the fact that a contact can only pair complementary
bases. Notice that, if we simply omit equation (6) then, pseudoknots are allowed
in the representation of RNA molecules.
Let Γss = (Σss , CE) be the specification whose set of consistence equations
CE are the quasi-equations (1) to (7) above. Let AlgΓss the category whose objects are all partial Γss -algebras, i.e., those partial Σss -algebras satisfying equation (1) to (7), and the morphisms between them are the plain homomorphisms,
and let AlgRN A be the full subcategory of AlgΓss supported on the RNA secondary structures.

3

Withdrawal-based Σss-Algebra Transformation
Systems

Our Withdrawal-based Algebra Transformation Systems (WATS) are a modification of a simplified version of the Algebra Transformation Systems (ATS)
introduced in [6]. This modification only affects the last step in the definition of
the application of a rewriting rule through a matching, and therefore all definitions previous to that one are the same as in the original ATS formalism. Since
we are only interested in rewriting RNA secondary structures, we shall only give
the main definitions for the signature Σss introduced in the previous section.
So, to simplify the notations, let us denote by S, Ω and η the set of sorts, the
set of operation symbols and the arity function of the signature Σss . For every
ϕ ∈ Ω, set η(ϕ) = (ω(ϕ), σ(ϕ)) ∈ S ∗ × S.
A Σss -presentation is a pair P = (PS , PE ) where PS = (Ps )s∈S is an Sset, whose elements will be called generators, and PE is a set of equations with
variables in PS
t = t′ ,
t, t′ ∈ TΣss (PS )s , s ∈ S.

A special type of equations are the function entries, of the form
ϕ(a) = b,

ω(ϕ)

ϕ ∈ Ω, a ∈ PS

, b ∈ Pσ(ϕ) .

A presentation is functional when all its equations are function entries, and a
functional presentation is consistently functional when for every ϕ ∈ Ω and
ω(ϕ)
a ∈ PS , there is at most one function entry of the form ϕ(a) = b in PE .
Let p : PS → PS′ be a mapping of S-sets. If e is an equation t = t′ with
′
t, t ∈ TΣss (PS )s , then we shall denote by e[p] the equation t(p) = t′ (p) where
t(p), t′ (p) ∈ TΣss (PS′ )s are the terms obtained from t and t′ , respectively, by
replacing all variables in them by their corresponding images under p. In particular, if e is the function entry ϕ(a) = b, then e[p] stands for the function entry
ϕ(p(a)) = pσ(ϕ) (b). Given a mapping of S-sets p : Ps → Ps′ and any set E of
equations with variables in PS , let
E[p] = {e[p] | e ∈ E}.
A morphism of Σss -presentations p : (PS , PE ) → (PS′ , PE′ ) is then a mapping of
S-sets p : PS → PS′ such that PE [p] ⊆ PE′ .
A Σss -rewriting rule is a pair of Σss -presentations, written r = (Pl ←→ Pr ),
where Pl = (Xl , El ) and Pr = (Xr , Er ) are functional presentations. Informally,
the left-hand side presentation in such a rule specifies the elements and operations that must be removed from the algebra which the rule is applied to,
while its right-hand side presentation specifies the elements and operations to
be added. The generators that occur in a rule play the role of variables (and
therefore we shall usually call them variables): those appearing in the left-hand
side presentation must be matched into the algebra to rewrite, and those appearing in the right-hand side presentation must be matched into the resulting
algebra, in such a way that if a variable occurs in both parts of a rule, its image
must be preserved. In the sequel, we shall assume that all variables that occur
in rewriting rules are taken from a universal S-set X that is globally fixed and
disjoint from all sets of operation symbols in the signatures we use. We shall also
assume that X is large enough to contain equipotent copies of the carrier sets
of all algebras we are interested in.
For every Σss -rewriting rule r = (Pl ←→ Pr ), with Pl = (Xl , El ) and Pr =
(Xr , Er ), let:
Xr0 = Xr − Xl ,
Xl0 = Xl − Xr ,
0
El = El − Er ,
Er0 = Er − El .
For every Γss -algebra A = (A, (ϕA )ϕ∈Ωss )), let AS = A and
Ae = {ϕ(a) = b | ϕ ∈ Ωss , a ∈ dom ϕA , ϕA (a) = b}.
A match m for a Σss -rewriting rule r = (Pl ←→ Pr ) in A is simply a presentation morphism m : Pl → (AS , AE ). The extension
m∗ : Xl ∪ Xr → AS ⊔ Xr0

of m is defined by2
∗

m (x) =



m(x) ∈ AS if x ∈ Xl
x ∈ Xr0
if x ∈ Xr0 = Xr − Xl

The application of r to A through m rewrites then A into the partial Γss algebra B defined, step by step, as follows:
1) Set BS = (AS − m(Xl0 )) ⊔ Xr0 . This step removes from A the elements that
are images of elements in Xl that do no longer belong to Xr , and adds to it
the elements in Xr that did not belong to Xl .
2) Set BE = (AE − El0 [m]) ∪ Er0 [m∗ ]. This step removes from A the operations
that are images of function entries in El that do no longer belong to Er , and
adds to it the equations in Er that did not belong to El , with variables in
BS .
3) Since the presentation (BS , BE ) is functional, it defines a partial Σss -algebra
with carrier set B = BS by simply translating the function entries in BE into
operations; if this presentation is not consistently functional, then we must
identify elements in B in order to remove inconsistencies. This step can be
formally described by means of a functor left adjoint to a functor that sends
every Σss -algebra to its presentation (AS , AE ).
4) If the Σss -algebra defined in this way satisfies equations (1) to (7), we are
done. Otherwise, there are two possibilities:
– Every contact x ∈ BContacts that violates equations (1), (5) or (7) is
removed.
– After performing all removals in the previous step, if there are still pairs
of contacts x, y ∈ BContacts that violate equations (2), (3), (4) or (6),
then, if one of them comes from Xr0 and the other comes from AS , the
one from Xr0 is removed and the other one preserved, and otherwise both
are removed.
It is in step (4) where the main difference between Große-Rhode’s original
ATS formalism and our WATS formalism lies. In ATS, the Σss -algebra obtained
in (3) would be forced to satisfy equations (1) to (7) by taking its universal
solution in AlgΓss , and thus adding operations and identifying elements. In our
formalism, violations of equations (1) to (7) are obviated by simply removing in
a controlled way the contacts that yield them.

4

Biochemical operations modelled by means of WATS

The biochemical operations considered in this paper are the addition, deletion
and mutation of a ribonucleotide and the addition and deletion of a contact.
Each of these biochemical operations can be modelled as a rewriting step of a
2

As always, we identify any set with its image into its disjoint union with any other
set.

WATS by the applications of a Σss -rewriting rule to a RNA secondary structure.
The rewriting rules that model these biochemical operations are the following
ones.
Adding a nucleotide: We have to consider three different cases, corresponding
to adding the new nucleotide at the beginning of the chain, at the end, or
in the middle of it. In this case, each rule must be understood as having a
parameter x which corresponds to the base attached to the new nucleotide.
So, there are four different values of this parameter, the nullary operation
symbols A, U , C and G.
– Rule Padd−base−f irst (x) has:
• as Pl the set of variables Xl = {k1 } of sort N at and the set of
equations El = {F irst = k1 };
• as Pr the set of variables Xr = {t, k1 , k0 }, of sorts t ∈ Bases and
k1 , k0 ∈ N at, and the set of equations Er = {F irst = k0 , suc(k0 ) =
k1 , label(k0 ) = t, x = t}.
– Rule Padd−base−last (x) has
• as Pl the set of variables Xl = {kn } of sort N at and the set of
equations El = {Last = kn };
• as Pr the set of variables Xr = {t, kn+1 , kn }, of sorts t ∈ Bases and
kn+1 , kn ∈ N at, and the set of equations Er = {Last = kn+1 , suc(kn )
= kn+1 , label(kn+1) = t, x = t}.
– Rule Padd−base−middle (x) has:
• as Pl the set of variables Xl = {ki , kj } of sort N at and the set of
equations El = {suc(ki ) = kj };
• as Pr the set of variables Xr = {t, ki , kj , k}, of sorts t ∈ Bases and
ki , kj , k ∈ N at, and the set of equations Er = {suc(ki ) = k, suc(k) =
kj , label(k) = t, x = t}.
Remove a nucleotide: We have to consider again three different cases, corresponding to removing the nucleotide at the beginning of the chain, at the
end, or in the middle of it.
– Rule Pdel−base−f irst has:
• as Pl the set of variables Xl = {k1 , k0 }, both of sort N at, and the
set of equations El = {F irst = k0 , suc(k0 ) = k1 };
• as Pr the set of variables Xr = {k1 } of sort N at and the set of
equations Er = {F irst = k1 }.
– Rule Pdel−base−last has:
• as Pl the set of variables Xl = {kn−1 , kn }, both of sort N at, and the
set of equations El = {Last = kn , suc(kn−1 ) = kn };
• as Pr the set of variables Xr = {kn−1 } of sort N at and the set of
equations Er = {Last = kn−1 }.
– Rule Pdel−base−middle has:
• as Pl the set of variables Xl = {ki , kj , kl }, all of them of sort N at,
and the set of equations El = {suc(ki ) = kl , suc(kl ) = kj };
• as Pr the set of variables Xr = {ki , kj } of sort N at and the set of
equations Er = {suc(ki ) = kj }.

Mutating a base: The mutation of a base is specified by just redefining the
operation label. Thus we consider the following rule:
– Rule Pmutation has:
• as Pl the set of variables Xl = {x, y, k}, of sorts x, y ∈ Bases and
k ∈ N at, and the set of equations El = {label(k) = x};
• as Pr the set of variables Xr = {x, y, k}, of sorts x, y ∈ Bases and
k ∈ N at and the set of equations Er = {label(k) = y}.
Adding a contact: To add a contact we simply add a new element of sort
Contact and the projections from it to the nucleotides it bonds.
– Rule Padd−contact has:
• as Pl the set of variables Xl = {x, y, ki , ki+1 , kj }, of sorts x, y ∈
Bases and ki , ki+1 , kj ∈ N at, and the set of equations El = {suc(ki )
= ki+1 , minor(ki+1 , kj ) = ki+1 , κ(x) = y, κ(y) = x, label(ki ) = x,
label(kj ) = y};
• as Pr the set of variables Xr = {x, y, ki , ki+1 , kj , c}, of sorts x, y ∈
Bases, ki , ki+1 , kj ∈ N at and c ∈ Contacts, and the set of equations
Er = {suc(ki ) = ki+1 , minor(ki+1 , kj ) = ki+1 , κ(x) = y, κ(y) =
x, p1 (c) = ki , p2 (c) = kj , label(ki ) = x, label(kj ) = y}.
Remove a contact: To remove a contact we simply delete it.
– Rule Pdel−contact has:
• as Pl the set of variables Xl = {ki , kj , c}, of sorts ki , kj ∈ N at and
c ∈ Contacts, and the set of equations El = {p1 (c) = ki , p2 (c) = kj };
• as Pr the set of variables Xr = {ki , kj }, both of sort N at, and the
set of equations Er = ∅.
It is not difficult to check that an RNA secondary structure is always rewritten by the application of any one of these rules through any matching into an
RNA secondary structure, and that in each case their effect is the desired one.
This must be done rule by rule and case by case.

5

Conclusion

We have modelled several simple biochemical operations on RNA molecules that
modify their secondary structure by means of rewriting rules in a modified version of the Algebra Transformation Systems of Große-Rhode, which we have
dubbed Withdrawal-based Algebra Transformation Systems. This modification
has been made ad hoc for algebras representing RNA secondary structures, but
we feel that the philosophy of removing inconsistencies by retreating should have
applications in other contexts, and could probably be formalized for algebras over
arbitrary specifications.
In this paper we have made some simplifications on the RNA secondary
structure that could perfectly be avoided. For instance, if we want to allow
contacts between pairs of basis other than the usual complementary pairs, like
for instance between G and U (they are called wobble pairs, not so uncommon),
then we only have to replace the involution κ by a symmetric relation on the

carrier of sort Bases. And if we want to impose that two bases paired by a
contact must be at least at a fixed distance, we only have to modify in a suitable
way equation (5).
There are also other collateral effects that could, and probably should, be
specified. For instance, isolated contacts tend to break, and pseudoknots should
be allowed under certain circumstances.

References
1. Burmeister, P., A Model Theoretic Oriented Approach to Partial Algebras. Mathematical Research 32, Akademie-Verlag (1986).
2. Durbin, R., Eddy, S., Krogh, A., Mitchison, G., Biological Sequence Analysis. Cambrideg Univ. Press (1998).
3. Fontana, W., “Algorithmic chemistry.” In Artificial Life II (Addison-Wesley, 1992),
159–210. Also Technical Report LA-UR 90-1959, Los Alamos National Lab. (1990).
4. Fontana, W., Buss, L. W. “The barrier of objects: from dynamical systems to
bounded organization.” In Boundaries and Barriers (Addison-Wesley, 1996), 56–
116.
5. Goss, P., Peccoud, J. “Quantitative modeling of stochastic systems in molecular
biology by using stochastic Petri nets.” Proc. Nat. Acad. Sicences USA 95 (1998),
6750–6755.
6. Große-Rhode, M. “Specification of State Based Systems by Algebra Rewrite Systems and Refinements.” Technical Report 99-04, TU Berlin (March 1999).
7. Mayoh, B. “DNA Pattern multigrammars.” Technical Report (1994).
8. McCaskill, J., Niemann, U. “Graph replacement chemistry for DNA processing.” In
Proc. DNA6: 6th International Meeting on DNA based computers, DIMACS Series
in Discrete Mathematics and Theoretical Computer Science (AMS, to appear),
89–99.
9. Müller, S. Functional Organization in Molecular Systems and the λ-calculus. PhD
Thesis, Univ. Wien (1999).
10. Regev, A., Silverman, W., Shapiro, E. “Representation and simulation of biochemical processes using the π-calculus process algebra.” In Proc. Pacific Symposyum
on Biocomputing 2001 (2001), 459–470.
11. C. Reidys, P. F. Stadler, Bio-molecular shapes and algebraic structures. Computers
& Chemistry 20 (1996), 85–94.
12. P. Schuster, P. F. Stadler, Discrete models of biopolymers. Univ. Wien TBI
Preprint No. pks-99-012 (1999).
13. Searls, D. B. “Formal Language and Biological Macromolecules”. In Mathematical Support for Molecular Biology, DIMACS Series in Discrete Mathematics and
Theoretical Computer Science 47 (AMS, 1999), 117–140.
14. Speroni di Fenizio, P. “Artificial Chemistries.” Bulletin EATCS 76 (February
2002), 128–141.

