Linear time algorithm for parsing RNA secondary structure!
RNA secondary structure prediction is an important problem in computational
molecular biology. Experiments show that existing polynomial time prediction
algorithms have limited success in predicting correctly the base pairs, i.e.
secondary structure, in known biological RNA structures. One limitation of
many current algorithms is that they can predict only restricted classes of
structures, excluding many so-called pseudoknotted secondary structures. The
type of the pseudoknotted structures that occur in biological structures, as
well as the type of structures handled by current algorithms, have been
poorly understood, making it difficult to assess the generality of current
In this thesis we present a comprehensive and precise classification of
structural elements and loops in a secondary structure, along with a linear
time algorithm for parsing secondary structures into their structural
The parsing algorithm, along with the classification scheme for the loops in
a pseudoknotted secondary structure, can be used in analysing existing
prediction algorithms to determine which known biological RNA structures can
not be predicted by the algorithms. This analysis can help us to design new
and more powerful prediction algorithms.
Furthermore, we present two applications of our work: (i) linear time free
energy calculation algorithm, and (ii) linear time test for Akutsu's
We present a linear time algorithm for calculating the free energy of a
given secondary structure. This algorithm can be useful especially in
heuristic prediction algorithms, as they commonly use a procedure to
calculate the free energy for a given sequence and structures.
We also present a linear time algorithm to test whether the prediction
algorithm introduced by Akutsu can handle a given structure. The result of
our analysis on algorithm of Akutsu on some sets of biological structures
shows that although it is proved theoretically that the class of structures
handled by Akutsu's algorithm is more general than that handled by the
algorithm of Dirks and Pierce, they can both handle the same class of given