Biomedical Engineering Reference
In-Depth Information
4
Considered Sampling Strategies
For the subsequent examinations, we will employ two different sampling strategies,
which are introduced now.
4.1
Well-Established Strategy
Let us first consider a slightly modified variant of the rather simple and widely known
sampling strategy from [1,4]. Briefly, this well-established strategy samples a complete
secondary structure
S
1
,n
for a given input sequence
r
of length
n
in the following
recursive way: Start with the entire RNA sequence
R
1
,n
and consecutively compute the
adjacent substructures (single-stranded regions and paired substructures) of the exterior
loop (from left to right). Any (paired) substructure on fragment
R
i,j
,
1
n
,is
folded by recursively constructing substructures (hairpins, stacked pairs, bulges, interior
and multibranched loops) on smaller fragments
R
l,h
,
i
≤
i<j
≤
≤
l<h
≤
j
. That is, fragments
are sampled in an
outside-to-inside
fashion.
Notably, without disturbances of the underlying probabilistic model, it is guaranteed
that any sampled loop type for a considered sequence fragment can be successfully gen-
erated (otherwise its probability would have been
0
). As this must not hold in disturbed
cases (like e.g. those of Sect. 2.3), the most straightforward modification to solve this
problem is that in any such case where the chosen substructure type can not be success-
fully generated, the strategy returns the partially formed substructure. Figure 3 gives a
schematic overview on this inherently controlled sampling strategy; a simple example
is presented in Fig. 4.
As regards this particular sampling strategy, the outside values can easily be omit-
ted from the corresponding formulæ for defining the needed sampling probabilities,
since in any case they contribute the same multiplicative factor to the distinct sampling
probabilities for mutually exclusive and exhaustive cases, such that they finally do not
influence the sampling decision at all.
The correctness of this simplification can easily be verified by considering a partic-
ular set
ac
X
(
i,j
)
of all choices for (valid) derivations of intermediate symbol
X
∈I
G
s
on sequence fragment
R
i,j
,
1
n
, which actually correspond to possible sub-
structures on
R
i,j
. Under the assumption that the alternatives for intermediate symbol
X
are
X
≤
i<j
≤
→
Y
and
X
→
VW
, the (valid) mutually exclusive and exhaustive cases are
defined by:
acX
(
i,j
):=
acX
Y
(
i,j
)
∪
acX
VW
(
i,j
)
,
(10)
where
acX
Y
(
i,j
):=
=0
for
p
=
β
X
(
i,j
)
{
(0
,p
)
|
p
Pr
tr
(
X
·
α
Y
(
i,j
)
·
→
Y
)
}
(11)
and
acX
VW
(
i,j
):=
{
(
k,p
)
|
i
≤
k
≤
j
and
p
=0
for
Pr
tr
(
X
p
=
β
X
(
i,j
)
·
α
V
(
i,k
)
α
W
(
k
+1
,j
)
·
→
VW
)
}
.
(12)
Search WWH ::
Custom Search