In this paper we present a novel framework for sequence to shape maps. These combinatorial maps realize exponentially many shapes, and have preimages which contain extended connected subgraphs of diameter n (neutral networks). We prove that all basic properties of RNA folding maps also hold for combinatorial maps. Our construction is as follows: suppose we are given a graph $H$ over the $\{ 1 >...,n\}$ and an alphabet of nucleotides together with a symmetric relation $\mathcal{ R}$, implied by base pairing rules. Then the shape of a sequence of length n is the maximal H subgraph in which all pairs of nucleotides incident to H-edges satisfy $\mathcal{ R}$. Our main result is to prove the existence of at least $\sqrt{ 2}^{ n-1}$ shapes with extended neutral networks, i.e. shapes that have a preimage with diameter $n$ and a connected component of size at least $(\frac{ 1+\sqrt{ 5}}{ 2})^n+(\frac{ 1-\sqrt{ 5}}{ 2})^n$. Furthermore, we show that there exists a certain subset of shapes which carries a natural graph structure. In this graph any two shapes are connected by a path of shapes with respective neutral networks of distance one. We finally discuss our results and provide a comparison with RNA folding maps.
Categories: q-bio.QM math-ph math.CO math.MP q-bio.BM