Predicting RNA Structures With Pseudoknots Under Nearest-Neighbour Models
Dr. Rune Lyngsoe ( Department of Statistics, University of Oxford )
- 16:30 10th March 2009 ( week 8, Hilary Term 2009 )Lecture Theatre B
Most computer scientists plunge straight for tertiary protein structure
prediction in a suitably abstract, most often square lattice, model when
venturing into the field of biostructure prediction. These models have
interesting properties and a clean combinatorial formulation, but due to
their abstract nature work is seldom transferable to actual structural
prediction. I will briefly discuss the benefits of instead focusing on the
secondary structure prediction problem for RNA, the problem of predicting
base pairings in an RNA molecule. When ignoring interactions this is just a
maximum (weighted) matching problem. However, it is well known that
nearest-neighbour interactions need to be considered. I will demonstrate
that the structure prediction problem balances on the edge between P and NP,
depending on exactly how nearest-neighbour interaction is incorporated and
assumptions made about alphabet size.
prediction in a suitably abstract, most often square lattice, model when
venturing into the field of biostructure prediction. These models have
interesting properties and a clean combinatorial formulation, but due to
their abstract nature work is seldom transferable to actual structural
prediction. I will briefly discuss the benefits of instead focusing on the
secondary structure prediction problem for RNA, the problem of predicting
base pairings in an RNA molecule. When ignoring interactions this is just a
maximum (weighted) matching problem. However, it is well known that
nearest-neighbour interactions need to be considered. I will demonstrate
that the structure prediction problem balances on the edge between P and NP,
depending on exactly how nearest-neighbour interaction is incorporated and
assumptions made about alphabet size.
Share this:
