Generic properties of combinatory maps: Neutral networks of RNA secondary structures

Random graph theory is used to model and analyse the relationships between sequences and secondary structures of RNA molecules, which are understood as mappings from sequence space into shape space. These maps are non-invertible since there are always many orders of magnitude more sequences than structures. Sequences folding into identical structures form neutral networks. A neutral network is embedded in the set of sequences that are compatible with the given structure. Networks are modeled as graphs and constructed by random choice of vertices from the space of compatible sequences. The theory characterizes neutral; networks by the mean fraction of neutral neighbors (lambda). The networks are connected and percolate sequence space if the fraction of neutral nearest neighbors exceeds a threshold value (lambda > lambda*). Below threshold (lambda < lambda*), the networks are partitioned into a largest ''giant'' component and several smaller components. Structures are classified as ''common'' or ''rare'' according to the sizes of their pre-images, i.e. according to the fractions of sequences folding into them. The neutral networks of any pair of two different common structures almost touch each other, and, as expressed by the conjecture of shape space covering sequences folding into almost all common structures, can be found in a small ball of an arbitrary location in sequence space. The results from random graph theory are compared to data obtained by folding large samples of RNA sequences. Differences are explained in terms of specific features of RNA molecular structures. (C) 1997 Society for Mathematical Biology.