computing the partition function for kinetically trapped rna secondary structures计算活动困rna二级结构的配分函数.pdfVIP

Computing the Partition Function for Kinetically Trapped RNA Secondary Structures 1 2 William A. Lorenz , Peter Clote * 1 Department of Mathematics and Computer Science, Denison University, Granville, Ohio, United States of America, 2 Biology Department, Boston College, Chestnut Hill, Massachusetts, United States of America Abstract An RNA secondary structure is locally optimal if there is no lower energy structure that can be obtained by the addition or removal of a single base pair, where energy is defined according to the widely accepted Turner nearest neighbor model. Locally optimal structures form kinetic traps, since any evolution away from a locally optimal structure must involve energetically unfavorable folding steps. Here, we present a novel, efficient algorithm to compute the partition function over all locally optimal secondary structures of a given RNA sequence. Our software, RNA 3 2 LOCOPT runs in O(n ) time and O(n ) space. Additionally, RNALOCOPT samples a user-specified number of structures from the Boltzmann subensemble of all locally optimal structures. We apply RNALOCOPT to show that (1) the number of locally optimal structures is far fewer than the total number of structures – indeed, the number of locally optimal structures approximately equal to the square root of the number of all structures, (2) the structural diversity of this subensemble may be either similar to or quite different from the structural diversity of the entire Boltzmann ensemble, a situation that depends on the type of input RNA, (3) the (modified) maximum expected accuracy structure, computed by taking into account base pai