An Efficient Dual Sampling Algorithm with Hamming Distance 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,5⁴ 

[1] Address correspondence to: Prof. Christian M. Reidys, Biocomplexity Institute of Virginia Tech, 1015 Life Science Circle, Blacksburg, VA 24061^3;Biocomplexity Institute of Virginia Tech, Blacksburg, Virginia^1;Department of Computer Science, Virginia Tech, Blacksburg, Virginia^2;Department of Mathematics, Virginia Tech, Blacksburg, Virginia^4;Thermo Fisher Scientific Fellow in Advanced Systems for Information Biology, Thermo Fisher Scientific, Waltham, Massachusetts^5

关键词: Boltzmann sampler;    inverse folding;    neutral path;    partition function;    sequence–structure pairs;   

DOI  :  10.1089/cmb.2018.0075

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

来源: Mary Ann Liebert, Inc. Publishers

【 摘 要 】

Recently, a framework considering ribonucleic acid (RNA) sequences and their RNA secondary structures as pairs has led to new information theoretic perspectives on how the semantics encoded in RNA sequences can be inferred. In this context, the 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 for designing more efficient inverse folding algorithms. In this work, we present the dual partition function filtered by Hamming distance, together with a Boltzmann sampler using novel dynamic programming routines for the loop-based energy model. The time complexity of the algorithm is, whereare Hamming distance and sequence length, respectively, reducing the time complexity of samplers, reported in the literature by. We then present two applications, the first in the context of the evolution of natural sequence–structure pairs of microRNAs and the second in constructing neutral paths. The former studies the inverse folding rate (IFR) of sequence–structure pairs, filtered by Hamming distance, observing that such pairs evolve toward higher levels of robustness, that is, increasing IFR. The latter is an algorithm that constructs neutral paths: given two sequences in a neutral network, we employ the sampler to construct short paths connecting them, consisting of sequences all contained in the neutral network.

【 授权许可】

Unknown