×

An infinite class of unsaturated rooted trees corresponding to designable RNA secondary structures. (English) Zbl 1453.92232

Summary: An RNA secondary structure is designable if there is an RNA sequence which can attain its maximum number of base pairs only by adopting that structure. The combinatorial RNA design problem, introduced by J. Haleš et al. [Algorithmica 79, No. 3, 835–856 (2017; Zbl 1383.92058)] is to determine whether or not a given RNA secondary structure is designable. Haleš et al. [loc. cit.] identified certain classes of designable and non-designable secondary structures by reference to their corresponding rooted trees. We introduce an infinite class of rooted trees containing unpaired nucleotides at the greatest depth, and prove constructively that their corresponding secondary structures are designable. This complements previous results for the combinatorial RNA design problem.

MSC:

92D20 Protein sequences, DNA sequences

Citations:

Zbl 1383.92058

Software:

MODENA
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aguirre-Hernández, R.; Hoos, H. H.; Condon, A., Computational RNA secondary structure design: empirical complexity and improved methods, BMC Bioinform., 8, 1, 34 (2007)
[2] Bonnet, É.; Rzążewski, P.; Sikora, F., Designing RNA secondary structures is hard (2017)
[3] Busch, A.; Backofen, R., Info-RNA-a fast approach to inverse RNA folding, Bioinformatics, 22, 15, 1823-1831 (2006)
[4] Esmaili-Taheri, A.; Ganjtabesh, M.; Mohammad-Noori, M., Evolutionary solution for the RNA design problem, Bioinformatics, 30, 9, 1250-1258 (2014)
[5] Garcia-Martin, J. A.; Clote, P.; Dotu, I., RNAiFold: a constraint programming algorithm for RNA inverse folding and molecular design, J. Bioinform. Comput. Biol., 11, Article 1350001 pp. (2013)
[6] Haleš, J.; Héliou, A.; Maňuch, J.; Ponty, Y.; Stacho, L., Combinatorial RNA design: designability and structure-approximating algorithm in Watson-Crick and Nussinov-Jacobson energy models, Algorithmica, 79, 3, 835-856 (2017) · Zbl 1383.92058
[7] Lyngsø, R. B.; Anderson, J. W.J.; Sizikova, E.; Badugu, A.; Hyland, T.; Hein, J., Frnakenstein: multiple target inverse RNA folding, BMC Bioinform., 13, 1, 260 (2012)
[8] Mathews, D. H.; Sabina, J.; Zuker, M.; Turner, D. H., Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure, J. Mol. Biol., 288, 5, 911-940 (1999)
[9] Nebel, M. E.; Scheid, A.; Weinberg, F., Random generation of RNA secondary structures according to native distributions, Algorithms Mol. Biol., 6, 24 (2011), Available online:
[10] Nussinov, R.; Jacobson, A. B., Fast algorithm for predicting the secondary structure of single-stranded RNA, Proc. Natl. Acad. Sci., 77, 11, 6309-6313 (1980)
[11] Petrie, T. J., The combinatorial RNA design problem for binary trees (2017), Simon Fraser University, Available online:
[12] Y. Ponty, Personal communication, August 2016.
[13] Schnall-Levin, M.; Chindelevitch, L.; Berger, B., Inverting the Viterbi algorithm: an abstract framework for structure design, (Proceedings of the 25th International Conference on Machine Learning (2008), ACM), 904-911
[14] Taneda, A., MODENA: a multi-objective RNA inverse folding, Adv. Appl. Bioinform. Chem., 4, 1-12 (2011)
[15] Zadeh, J. N.; Wolfe, B. R.; Pierce, N. A., Nucleic acid sequence design via efficient ensemble defect optimization, J. Comput. Chem., 32, 3, 439-452 (2011)
[16] Zuker, M.; Stiegler, P., Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information, Nucleic Acids Res., 9, 1, 133-148 (1981)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.