Analysis of Complex Networks

5.6 Conclusion

We began by showing how RNA sequence-structure relations give rise to particular subcubes within a sequence space. These subcubes reduce many questions arising in the context of a neutral evolution of RNA sequences to structural properties of random induced subgraphs of n-cubes. The first and probably best known property is the connectivity of n-cubes in Section 5.3. Here we give a constructive proof that shows how the actual paths can be obtained. In Section 5.4 we discuss the largest component in n-cubes. We prove an extension of Ajtai et al.'s [1] result for random graphs in which edges are selected with independent probability. We adopt an “algorithmic” approach and try to give constructive proofs of our results; see, for instance, Lemma 5.3. Only the argument given in Theorem 5.5, where we show that the small subcomponents constructed in Lemma 5.3 have to “melt,” does not indicate how to obtain the largest component constructively. The existence of the largest component is of vital importance for neutral evolution. It represents the structural prerequisite for changing the nucleotides of a sequence by successive local “computations” while remaining on the neutral network of a given structure. Upon closer inspection, however, additional properties for neutral evolution are needed [21]. The neutral network has to have many “short” paths whose lengths scale with the Hamming distance of the sequences. This led in Section 5.5 to the analysis of the local connectivity ...