RNA Secondary Structure Prediction

The problem of predicting the RNA Secondary Structure without pseudoknots is well-resolved [1-6], with time O(n3) and space O(n2). The predition the secondary structure with pseudoknots has been proved to be NP-complete [7-8], but lots of approximate algorithms have been published, which achieved the time complexity as low as O(n4) [9-13].

1. R Nussinov, G Pieczenik, JR Griggs, DJ Kleitman, Algorithms for loop matchings, SIAM J. Appl. Math, Vol.35, No.1, 1978.

2. M. S. Waterman and T. F. Smith. RNA secondary structure: A complete mathematical analysis. Math. Biosc., 42:257--266, 1978.

3. M Zuker and P Stiegler, Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information. Nucleic Acids Res. 1981 January 10; 9(1): 133–148.

4. M.S. Waterman. Secondary structure of single-stranded nucleic acids. In Studies in foundations and combinatorics: Advan. in Math. Suppl. Studies, volume 1, pages 167–212. Academic Press, New York, 1978.

5. Mathews DH, Sabina J, Zuker M, Turner DH. Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure. J Mol Biol. 1999 May 21;288(5):911-40.

6. Lyngso RB, Zuker M, Pedersen CN. Fast evaluation of internal loops in RNA secondary structure prediction. Bioinformatics. 1999 Jun;15(6):440-5.

7. Lyngso RB, Pedersen CN. RNA pseudoknot prediction in energy-based models. J Comput Biol. 2000;7(3-4):409-27.

8. Tatsuya Akutsu. Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots. Discrete Applied Mathematics, Volume 104 , Issue 1-3 (August 2000).

9. Uemura, Y., Hasegawa, A., Kobayashi, S. and Yokomori, T., Grammatically modeling and predicting RNA secondary structures, Proc. Genome Informatics Workshop VI, Universal Academy Press, Tokyo, 67--76, 1995.

10. Brown M, Wilson C. RNA pseudoknot modeling using intersections of stochastic context free grammars with applications to database search. Pac Symp Biocomput. 1996;:109-25.

11. Dirks RM, Pierce NA. A partition function algorithm for nucleic acid secondary structure including pseudoknots. J Comput Chem. 2003 Oct;24(13):1664-77.

12. Rivas E, Eddy SR. A dynamic programming algorithm for RNA structure prediction including pseudoknots. J Mol Biol. 1999 Feb 5;285(5):2053-68.

13. Samuel Ieong, Ming-Yang Kao, Tak Wah Lam, Wing-Kin Sung, Siu-Ming Yiu: Predicting RNA Secondary Structures with Arbitrary Pseudoknots by Maximizing the Number of Stacking Pairs. BIBE 2001: 183-190.

Backrub Motions

This draft of a paper by Ian Davis and others in the Richardsons' lab explores proteins with alternate conformations in high resolution structures and tries to decide which are explainable as "backrub" motions. Not very quantified, so it would be interesting to try to repeat. Since it is not yet published, I better put it in a private section: BackrubMotion

MolecularDrivingForces

This book by Dill and Bromberg introduces statistical thermodynamics with all the necessary mathematics, and with applications to what drives molecules. Lots of problems, so it makes a good guide for study alone or together.

Minimizing RMSD by SVD and Quaternions

Minimizing Coordinate RMSD (Root Mean Squared Deviation) is the most common way of aligning two corresponding point sets {p_i} and {q_i} in biology: it minimizes the sqrt(Sum_i d(p_i, T(q_i))^2), where d(p,q) is the Euclidean distance between corresponding points p and q, and T(q_i) is a transformation of the point q_i to bring it into closer correspondence with p_i. Natural sets of tranformations include translations, rotations, and possibly reflections. There are closed forms for these possible transformations.

Golub and Van Loan's book shows that translations, rotations, and reflections can be determined by singular value decomposition of the covariance matrix of P and Q. This is easy to implement in matlab, but is probably not what one wants because it doesn't preserve chirality (handedness).

Berthold Horn showed that there is a closed form with translations and rotations, that is best computed using quaternions.

A recent paper of Dill et al. recaps these things, and adds derivatives. I find that most of the content (and even some of the page layout ideas) come from Horn.

• Absolute_Orientation.pdf: Horn's paper on minimizing RMSD. Very nice.
• rmsd-dill2004.pdf: min rmsd for protein; best stuff from Horn

Separators for Sphere-Packings and Nearest Neighbor Graphs

This paper proves the existence of a sphere separator for a set of balls. This separator divides the balls into two groups: those contained in the sphere and those outside of it. If there are n balls, then the larger of the two groups is O( k ^ {1/d} n ^ {1 - 1/d}). This "k" is an additional parameter of the set of balls; these balls are a k-ply system, meaning that no point in space is inside more than k balls. This is effectively a density limitation. Jinbo Xu uses this theorem to create his tree decompositions which he then applies to the side chain placement problem.

[1] GARY L. MILLER, SHANG-HUA TENG, WILLIAM THURSTON, and STEPHEN A. VAVASIS. Separators for Sphere-Packings and Nearest Neighbor Graphs. Journal of the ACM. 1997. v44(1) pp1-29.

-- AndrewLeaverFay^? April 28, 2005

Chain-tree algorithm for self-collision checking and energy maintenance in protein structure

[1] I. Lotan, F. Schwarzer, D. Halperin and J.-C Latombe. Efficient Maintenace and Self-Collision Testing for Kinematic Chains. Proc. Symposium on Computational Geometry (SoCG^? `02), 2002 pp. 43-52

[2] I. Lotan, F. Schwarzer, D. Halperin and J.-C Latombe. Algorithm and Data Structures for Efficient Energy Maintenance during Monte Carlo Simulation of Proteins. J. of Computational Biology, 11(2004), 902-932.

Protein is a long chain (backbone) with many short side chains. During Monte-Carlo simulation, normally only the dihedrals in the backbone are changed but the bond lengths and angles are kept for the same. These two papers gave a new algorithm for checking collisions. They reconstructed the protein backbone into a binary tree structure. The leaves are atoms on the backbone, and each leaf (except the last one) contains a transformation matrix for transforming to the next atom position. Each internal node contains a transformation matrix for transforming the left-most leaf in its left subtree to the left-most leaf in its right subtree. So that it only needs O(klog(n/k)) for updating the transformation matrixes in the chain-tree for k rotations.

Then each node keeps an Oriented Bounding Box (OBB) to enclose all the leaves it contains. After rotations, some OBBs are changed. For checking collisions, the algorithm starts from root, walks down one level at a time, checks the overlaps between OBB pairs (in the pair, one is changed OBB and the other is unchanged OBB). If there are overlaps, the algorithm walks down one level and checks overlaps (if one pair has overlap, then in the next level, four pairs need to be checked), if not, discard the pair. In this way, they proved that the algorithm can finish collision checking in O(n4/3) in worst time. Although the grid algorithm has better performance in worst time, which is O(n), the chain-tree structure can find collision quickly and doesn't need to resample all the atoms in each step as needed in grid algorithm. The experiment shows that the chain-tree algorithm can be up to 10 times faster than grid algorithm.

A further improvement called chain-tree+ can further reduce the cost for calculating energy of the protein structure. Chain-tree+ has two steps, first step uses a very small cut-off distance for checking collision and discards the rotation if there are bad collisions, the second steps uses the normal cut-off distance for calculating the energy. The experiment shows chain-tree+ can be up to 6 times faster then chain-tree algorithm.

-- XueyiWang - 14 Feb 2005

Protein Universe paper for Friday Protein Discussion meeting

Another paper submitted by Gary Pielak is attached for discussion on Friday 2/11 at noon in room 802 FLOB [JS: MEJH] with pizza provided.

Lindorff-Larsen, Rogen, Paci, Vendruscolo, and C. M. Dobson. Protein folding and the organization of the protein topology universe. Trends in Biochem. Sci. 30 13-19 (2005).

Dobson2-GP.pdf:

Alex says:

This seems to be an interesting paper that talks about issues related to protein folding) where we could make an impact the description of protein topology. I suggest that we discus this (and related papers mentioned in this review, mostly by Michele), that talk about a few key residues that define folds. It resonated strongly with me because of the work done by Bala (and published in Bioinformatics) where we have shown that we could find the key residues based on Delaunay profiles. I thin Deepak is playing with the profiles now. It would be of interest to (a) see if we could deduce the key residues from the profiles that would agree with whatever Michele is claiming in his papers); and (b) if the ensembles that are generated from simulations by David O'Brien/Zong could be characterized using topological measures to see if we could accurately predict at least SCOP class (and therefore deduce function) even if our current prediction is far from ideal.

If any of the students CC'd in this mail is interested in doing some work along the above lines, I would like to meet and discuss the course of actions. I believe I could get folding trajectories from Michele (I sent him our scoring function in the past).

-- JackSnoeyink - 08 Feb 2005

PXR

@article{WDSLR03
,author="Ryan E. Watkins, Paula R. Davis-Searles, Mill H. Lambert and Matthew R. Redinbo"
,title="Coactivator Binding Promotes the Specific Interaction Between Ligand and the Pregnane X Receptor"
,journal="J. Mol. Biol."
,year=2003
,volume=331
,pages="815--828"
}

link to paper

This paper describes how the ligand binding domain (LBD) of pregnane X receptor (PXR) binds with the cholesterol-lowering compound SR12813 and a 25 residue fragment of the human steroid coactivator-1 (SRC-1). The associated PDB entry is 1NRL. Previous studies show that the LBD of PXR binds SR12813 in at least three different orientations (PDB 1ILH). However, with SRC-1 bound, SR12813 binds in a single orientation (different than those observed in 1ILH). This is likely the active orientation, and the binding of SRC-1 restricts the "breathing" of PXR, "freezing" the active orientation. The order of binding SRC-1 and SR12813 is not know.

-- AndreaMantler - 07 Feb 2005
to top