Neutral Networks of Sequence to Shape Maps

الأصل · EN

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 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 R. Our main result is to prove the existence of at least √2ⁿ⁻¹ shapes with extended neutral networks, i.e. shapes that have a preimage with diameter n and a connected component of size at least (1+√52)ⁿ+(1-√52)ⁿ. 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.