Neutral networks of sequence to shape maps. (English) Zbl 1397.92531
Summary: In this paper we present a combinatorial model of sequence to shape maps. Our particular construction arises in the context of representing nucleotide interactions beyond Watson-Crick base pairs and its key feature is to replace biophysical steric by combinatorial constraints. We show that these combinatory maps produce exponentially many shapes and induce sets of sequences which contain extended connected subgraphs of diameter \(n\), where \(n\) denotes the length of the sequence. Our main result is to prove the existence of exponentially many shapes that have neutral networks.
References:
| [1] | Barnett, L., Ruggedness and neutrality—the nkp family of fitness landscapes, (), 18-27 |
| [2] | Bastolla, U.; Porto, M.; Roman, H.; Vendruscolo, M., Conectivity of neutral networks, overdispersion, and structural conservation in protein evolution, J. mol. evol., 56, 243-254, (2003) |
| [3] | Batey, R.; Rambo, R.; Doudna, J., Tertiary motifs in RNA structure and folding, Angew. chem. int. ed., 38, 2326-2343, (1999) |
| [4] | Chamorro, M.; Parkin, N.; Varmus, H., An RNA pseudoknot and an optimal heptameric shift site are required for highly efficient ribosomal frameshifting on a retroviral messenger RNA, J. proc. natl acad. sci. USA, 89, 713-717, (1991) |
| [5] | Chen, W., Qin, J., Reidys, C., 2007. Crossings and nestings in tangled-diagrams. Electron. J. Combin., submitted, arXiv:0710.4053.; Chen, W., Qin, J., Reidys, C., 2007. Crossings and nestings in tangled-diagrams. Electron. J. Combin., submitted, arXiv:0710.4053. · Zbl 1163.05309 |
| [6] | Clote, P.; Gasieniec, L.; Kolpakov, R.; Kranakis, E.; Krizanc, D., On realizing shapes in the theory of RNA neutral networks, J. theoret. biol., 236, 216-227, (2005) · Zbl 1442.92115 |
| [7] | Flamm, C.; Hofacker, I.; Maurer-Stroh, S.; Stadler, P.; Zehl, M., Design of multistable RNA molecules, RNA, 7, 254-265, (2001) |
| [8] | Fontana, W.; Schuster, P., Continuity in evolution, Science, 289, 1451-1455, (1998) |
| [9] | Göbel, U., 2000. Neutral networks of minimum free energy rna secondary structures. Ph.D. thesis, University of Vienna.; Göbel, U., 2000. Neutral networks of minimum free energy rna secondary structures. Ph.D. thesis, University of Vienna. |
| [10] | Goebel, U.; Forst, C., RNA pathfinder – global properties of neutral networks, Z. phys. chem., 216, 175, (2002) |
| [11] | Grüner, W.; Giegerich, R.; Strothmann, D.; Reidys, C.; Weber, J.; Hofacker, I.; Stadler, P.; Schuster, P., Analysis of RNA sequence structure maps by exhaustive enumeration I. neutral networks, Chemical monthly, 127, 355-374, (1996) |
| [12] | Grüner, W.; Giegerich, R.; Strothmann, D.; Reidys, C.; Weber, J.; Hofacker, I.; Stadler, P.; Schuster, P., Analysis of RNA sequence structure maps by exhaustive enumeration II. structures of neutral networks and shape space covering, Chemical monthly, 127, 375-389, (1996) |
| [13] | Haslinger, C.; Stadler, P., RNA structures with pseudo-knots, Bull. math. biol., 61, 437-467, (1999) · Zbl 1323.92149 |
| [14] | Hofacker, I.; Schuster, P.; Stadler, P., Combinatorics of RNA secondary structures, Discrete appl. math., 88, 207-237, (1998) · Zbl 0918.05004 |
| [15] | Jin, E.Y., Qin, J., Reidys, C.M., 2007. Combinatorics of RNA structures with Pseudoknots. Bull. Math. Biol., Sep. 26, PMID:17896159.; Jin, E.Y., Qin, J., Reidys, C.M., 2007. Combinatorics of RNA structures with Pseudoknots. Bull. Math. Biol., Sep. 26, PMID:17896159. · Zbl 1281.92055 |
| [16] | Jin, E.Y., Reidys, C.M., 2007. Asymptotic enumeration of RNA structures with pseudoknots. Bull. Math. Biol., accepted for publication.; Jin, E.Y., Reidys, C.M., 2007. Asymptotic enumeration of RNA structures with pseudoknots. Bull. Math. Biol., accepted for publication. · Zbl 1152.92007 |
| [17] | Kauffman, S.A., The origin of order, (1993), Oxford University Press New York, Oxford |
| [18] | Konings, D.A.M.; Gutell, R., A comparison of thermodynamic foldings with comparatively derived structures of 16s and 16s-like rrnas, RNA, 1, 559-574, (1995) |
| [19] | Mapping RNA form and function. Science 2, 2005.; Mapping RNA form and function. Science 2, 2005. |
| [20] | Puglisi, J.D.; Williamson, J.R., The RNA world, (1999), Cold Spring Harbor Laboratory Press, pp. 403-425 |
| [21] | Reidys, C.M., Random induced subgraphs of generalized \(n\)-cubes, Adv. appl. math., 19, 360-377, (1997) · Zbl 0898.05075 |
| [22] | Reidys, C.M., Random structures, Ann. combin., 4, 375-382, (2000) · Zbl 0970.05039 |
| [23] | Reidys, C.M., Distances in random induced subgraphs of generalized \(n\)-cubes, Combin. probab. comput., 11, 599-605, (2003) · Zbl 1012.05060 |
| [24] | Reidys, C.M., 2007. Random Combinatory Maps, Private communication.; Reidys, C.M., 2007. Random Combinatory Maps, Private communication. |
| [25] | Reidys, C.M.; Stadler, P.F.; Schuster, P.K., Generic properties of combinatory maps and neutral networks of RNA secondary structures, Bull. math. biol., 59, 2, 339-397, (1997) · Zbl 0925.92006 |
| [26] | Schmitt, W.; Waterman, M., Linear trees and RNA secondary structure, Discrete appl. math., 51, 317-323, (1994) · Zbl 0799.92006 |
| [27] | Schuster, P., 2002. A testable genotype-phenotype map: modeling evolution of RNA molecules. Michael Laessig and Angelo Valeriani, editors, Springer.; Schuster, P., 2002. A testable genotype-phenotype map: modeling evolution of RNA molecules. Michael Laessig and Angelo Valeriani, editors, Springer. |
| [28] | Schuster, P.; Fontana, W.; Stadler, P.F.; Hofacker, I.L., From sequences to shapes and back: a case study in RNA secondary structures, Proc. roy. soc. lond. B, 255, 279-284, (1994) |
| [29] | Schuster, P.; Weber, J.; Gruener, W.; Reidys, C.M., Molecular evolutionary biology: from concepts to technology, () |
| [30] | Stadler, P.F.; Schuster, P., Discrete models of biopolymers, () |
| [31] | Waterman, M.S., Secondary structure of single—stranded nucleic acids, Adv. math. I (suppl.), 1, 167-212, (1978) · Zbl 0434.05007 |
| [32] | Waterman, M.S., Combinatorics of RNA hairpins and cloverleafs, Stud. appl. math., 60, 91-96, (1979) · Zbl 0399.05003 |
| [33] | Wedekind, J.E.; McKay, D.B., Annu. rev. biophys. biomol. struct., 27, 475-502, (1998) |
| [34] | Westhof, E.; Jaeger, L., RNA pseudoknots, Curr. opin. struct. biol., 2, 327-333, (1992) |
| [35] | Woese, C.R.; Pace, N.R., The RNA world, (1993), Cold Spring Harbor Laboratory Press, pp. 91-117 |
| [36] | Zuker, M.; Sankoff, D., RNA secondary structures and their prediction, Bull. math. biol., 46, 4, 591-621, (1984) · Zbl 0548.92007 |
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.
