GENERIC PROPERTIES OF COMBINATORY MAPS - NEUTRAL NETWORKS OF RNA SECONDARY STRUCTURES

Random graph theory is used to model and analyse the relationships bet ween sequences and secondary structures of RNA molecules, which are un derstood as mappings from sequence space into shape space. These maps are non-invertible since there are always many orders of magnitude mor e sequences than structures. Sequences folding into identical structur es form neutral networks. A neutral network is embedded in the set of sequences that are compatible with the given structure. Networks are m odeled as graphs and constructed by random choice of vertices from the space of compatible sequences. The theory characterizes neutral; netw orks 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 larg est ''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 structu res almost touch each other, and, as expressed by the conjecture of sh ape space covering sequences folding into almost all common structures , can be found in a small ball of an arbitrary location in sequence sp ace. The results from random graph theory are compared to data obtaine d by folding large samples of RNA sequences. Differences are explained in terms of specific features of RNA molecular structures. (C) 1997 S ociety for Mathematical Biology.