5.3 Connectivity

As already mentioned, the connectivity property of neutral networks of RNA structures has a profound impact on our picture of evolutionary optimization. It is closely related to the connectivity of the two subcubes induced by the unpaired and paired nucleotides. We present the combinatorial, constructive proof that localizes the threshold value for generalized n-cubes due to [18]. The particular construction has led to several computational studies on the connectivity of neutral networks [11, 12].

Lemma 5.1 Let Qnα be a generalized n-cube, images, and Γ n an induced Qnα-subgraph obtained by selecting each Qnα-vertex with independent probability λ. Then we have


Proof. Claim1. Suppose images. Then for arbitrary limages,Γn contains a.s. exclusively vertices of degree ≥ l.

To prove the claim we first observe that images is equivalent to (1–λ)α–1)α<1. We fix limages. Using the linearity of expectation, ...

Get Analysis of Complex Networks now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.