Evolution on Random Structures

Christian M. Reidys and Simon M. Fraser

Working Papers from Santa Fe Institute

Abstract: 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) contract graph and (ii) a family of relations imposed on its adjacent vertices. The vertex set of the contact graph is imply 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. Mappings 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 non-linear 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.

Keywords: random structure; sequence-structure mapping; random graph; connectivity; giant component; hitting time; optimization (search for similar items in EconPapers)
Date: 1995-11
References: View references in EconPapers View complete reference list from CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wop:safiwp:95-11-082

Access Statistics for this paper

More papers in Working Papers from Santa Fe Institute Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Krichel ().