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

Consider entire
input sequence
R i,j := R 1 ,n

Consider remaining
sequence fragment
R i,j := R j +1 ,n

Start

no S i,j becomes

single-strand

Further
helix?

End

no

yes

Overall
structure
S 1 ,n
folded?

Helix
possible on
R i,j ?

Sample free pair h.l
(first h ,then l )

no

yes yes

Start folding of
R i +1 ,j− 1 := R h +1 ,l− 1
(by adding pair i.j )

Recursively fold
substructure S h,l

i.j could
close loop?

R l +1 ,j− 1 remains
single-stranded

no

no

yes

k th helix
possible on
R l +1 ,j− 1 ?

Sample loop type
closed by i.j

Set k := k +1

Set k := 1 and l := i

yes

Sample k th accessible
pair h.l (first h ,then l )

Hairpin Type Multiloop

yes

Recursively
fold the k th
multiloop
substructure S h,l

Further
helix?

Bulge or
interior

Stacking

Take consecutive pair
h.l := ( i +1) . ( j − 1)

no

Helix
possible on
R i +1 ,j− 1 ?

yes

Sample accessible pair
h.l (first h ,then l )

Recursively fold
substructure S h,l

no

S i +1 ,j− 1 becomes
single-strand

Finish folding of R i,j
( S i,j is now complete)

Fig. 3. Flowchart for recursive sampling of an RNA secondary structure S 1 ,n for a given input
sequence r of length n according to an inherently controlled strategy with predetermined order,
similar to that of [1,4])

We then sample from the probability distribution induced by acX ( i,j ) (conditioned
on fragment R i,j ), which implies

p

z = β X ( i,j )

p
β X ( i,j ) ,

1= (13)

z

( k,p ) ∈acX ( i,j ) ( k,p ) ∈acX ( i,j )

with

z := p, (14)

( k,p ) ∈acX ( i,j )

since β X ( i,j ) =0 due to the definition of acX ( i,j ) (multiplicative term).