Evolution on Random Structures

In this paper we investigate the relation between the structure and dynamics of molecules, using a level of coarse graining at which we consider a molecular structure as a “random structure.” A random structure consists of (i) a (random) contact graph and (ii) a family of relations imposed on its adjacent vertices. The vertex set of the contact graph is simply the set of all indices of a sequence, and its edges are obtained by picking secondary and tertiary bonds (from the set of all possible bonds) in two randomization procedures. The corresponding relations associated with the edges are viewed as secondary base-pairing rules and tertiary interaction rules respectively. Mapping of sequences into random structures are constructed. Here, the set of all sequences that map into a particular random structure is modeled as a random graph in the sequence space, the so-called neutral network. We analyze the graph structure of the contact graphs of random structures and their union, and show how their graph theoretic properties influence the dynamics of sequences mapping into them. In particular, we see a phase transition (in the limit of long sequences) in the union graph, which is manifested in the emergence of a giant component. The critical parameter for this phase transition is the fraction of tertiary interactions in the molecule. A replication-deletion experiment reveals that this dramatic change in molecular structure has significant effects on the dynamics of the optimization process. This results in a nonlinear relation between the fraction of tertiary interactions in the biomolecules, and the times taken for a population of sequences to find a high-fitness target structure. These results have important implications for evolutionary optimization in biopolymers, in particular the evolution of viruses.