Neutral Networks of Sequence to Shape Maps

Details Neutral Networks of Sequence to Shape Maps Neutral Networks of Sequence to Shape Maps

2007-06-06

arxiv.org/abs/0706.0760v2

Biology

Quantitative Biology

Quantitative Methods

24 pages,4 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Neutral Networks of Sequence to Shape Maps does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Neutral Networks of Sequence to Shape Maps, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Neutral Networks of Sequence to Shape Maps will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-356616