Fast RNA Secondary Structure Prediction Using Fuzzy Stochastic Models - Biomedical Engineering Systems and Technologies - page 159

Hplot Mplot

1.0 1.0

0.8 0.8

0.6 0.6

0.4 0.4

0.2 0.2

0.0 0.0

0 10 20 30 40 50 60 70 0 10 20 30 40 50 60 70

Nucleotide Position Nucleotide Position

Ala corresponding to those presented in Fig. 1, where
max ErrVal =10 − 9 (thick gray lines) and fix ErrVal =10 − 9 (thick dotted darker gray lines) have
been chosen for generating the disturbances

Fig. 2. Sampling results for E.coli tRNA

3 Reducing the Preprocessing Time

According to the previous discussion, the proclaimed aim of this section is to lower
the ( n 2 ) ,such

that the preprocessing has the same worst-case time requirements as the subsequent
sampling process (for constructing a constant number of random secondary structure of
size n ).

( n 3 ) time complexity for preliminary inside-outside calculations to O O

3.1 Basic Idea

The main idea for reaching this time complexity reduction by a factor n in the worst-
case is actually quite simple: Instead of deriving the inside values α X ( i,j ) (and the
corresponding outside probabilities β X ( i,j ) ), X ∈I G s , for any combination of start

position i and end position j , 1 n , we abstract from the actual position of sub-

word R i,j = r i ...r j in the input sequence and consider only its length d =

≤ i,j ≤

| r i ...r j | .

( n 2 ) values α X ( i,j ) (and

Thus, for any X ∈I G s , we do not need to calculate O

β X ( i,j ) )for 1 n .

However, the problem with this approach is that distance d alone may be associated
with any of the strings in

≤ i,j ≤ n , but only O ( n ) values α X ( d ) (and β X ( d ) )for 0 ≤ d ≤

, i.e. without using positions i and
j we are inevitably forced to additionally abstract from the actual input sequence r .
Note that it is also possible to combine both alternatives, that is we can first use
the traditional algorithms to calculate exact values α X ( i,j ) (and β X ( i,j ) ) within a
window of fixed size W exact ,i.e.for j

{ r i ...r j | j − i +1= d }

− i +1 ≤ W exact (and j − i +1 ≥ n −

W exact ), and afterwards derive the remaining values for W exact <d ≤ n (and 0 ≤

d<n W exact ) in an approximate fashion by employing the time-reduced variant

for obtaining α X ( d ) (and β X ( d ) ) for each X

−

∈I G s .Since W exact is constant, this
effectively yields an improvement in the time complexity of the corresponding complete
inside computation, which is then given by ( n 2 ·

W exact ) .However,evenforfix
W exact the time requirements for such a mixed outside computation are

O

( n 3 ) .

O

3.2 Approximation of Emission Probabilities

Due to the unavoidable abstraction from sequence, we have to determine some approx-
imated terms for the emissions of unpaired bases and base pairs, respectively, that