Journal
JOURNAL OF COMPUTATIONAL BIOLOGY
Volume 30, Issue 10, Pages 1089-1097Publisher
MARY ANN LIEBERT, INC
DOI: 10.1089/cmb.2022.0501
Keywords
counting algorithms; RNA secondary structure
Ask authors/readers for more resources
This paper examines the problem of counting distinguishable RNA secondary structures, particularly for circular sequences, using dynamic programming and group theory methods to address the issue of symmetry.
RNA secondary structures are essential abstractions for understanding spacial folding behaviors of those macromolecules. Many secondary structure algorithms involve a common dynamic programming setup to exploit the property that secondary structures can be decomposed into substructures. Dirks et al. noted that this setup cannot directly address an issue of distinguishability among secondary structures, which arises for classes of sequences that admit nontrivial symmetry. Circular sequences are among these. We examine the problem of counting distinguishable secondary structures. Drawing from elementary results in group theory, we identify useful subsets of secondary structures. We then extend an algorithm due to Hofacker et al. for computing the sizes of these subsets. This yields a cubic-time algorithm to count distinguishable structures compatible with a given circular sequence. Furthermore, this general approach may be used to solve similar problems for which the RNA structures of interest involve symmetries.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available