A Boltzmann Sampler for 1-Pairs with Double Filtration

Journal of computational biology: A journal of computational molecular cell biology

Fenix W.Huang^1¹  ChristopherBarrett^1,2²  QijunHe^1³  Christian M.Reidys^3,1,4⁴ 

[1] Address correspondence to: Dr. Christian M. Reidys, Biocomplexity Initiative and Institute, University of Virginia, Charlottesville, Virginia 22904^3;Biocomplexity Initiative and Institute, University of Virginia, Charlottesville, Virginia^1;Department of Computer Science, University of Virginia, Charlottesville, Virginia^2;Department of Mathematics, University of Virginia, Charlottesville, Virginia^4

关键词: base pair distance filtration;    Boltzmann sampling;    Hamming distance filtration;    pseudoknot;    sequence/structure pair;   

DOI  :  10.1089/cmb.2018.0095

学科分类：生物科学（综合）

来源: Mary Ann Liebert, Inc. Publishers

【 摘 要 】

Recently, a framework considering RNA sequences and their RNA secondary structures as pairs led to some information-theoretic perspectives on how the semantics encoded in RNA sequences can be inferred. This pairing arises naturally from the energy model of RNA secondary structures. Fixing the sequence in the pairing produces the RNA energy landscape, whose partition function was discovered by McCaskill. Dually, fixing the structure induces the energy landscape of sequences. The latter has been considered originally for designing more efficient inverse folding algorithms and subsequently enhanced by facilitating the sampling of sequences. We present here a partition function of sequence/structure pairs, with endowed Hamming distance and base pair distance filtration. This partition function is an augmentation of the previous mentioned (dual) partition function. We develop an efficient dynamic programming routine to recursively compute the partition function with this double filtration. Our framework is capable of dealing with RNA secondary structures as well as 1-structures, where a 1-structure is an RNA pseudoknot structure consisting of “building blocks” of genus 0 or 1. In particular, 0-structures, consisting of only “building blocks” of genus 0, are exactly RNA secondary structures. The time complexity for calculating the partition function of 1-pairs, that is, sequence/structure pairs where the structures are 1-structures, is O(h3b3n6), whereh, b, ndenote the Hamming distance, base pair distance, and sequence length, respectively. The time complexity for the partition function of 0-pairs is O(h2b2n3).

【 授权许可】

Unknown