The gap between the amount of genome information released by genome sequencing projects and our knowledge about the proteins' functions is rapidly increasing. To fill this gap, various 'genomic-context' methods have been proposed that exploit sequenced genomes to predict the functions of the encoded proteins. One class of methods, phylogenetic profiling, predicts protein function by correlating the phylogenetic distribution of genes with that of other genes or phenotypic characteristics. The functions of a number of proteins, including ones of medical relevance, have thus been predicted and subsequently confirmed experimentally. Additionally, various approaches to measure the similarity of phylogenetic profiles and to account for the phylogenetic bias in the data have been proposed. We review the successful applications of phylogenetic profiling and analyse the performance of various profile similarity measures with a set of one microsporidial and 25 fungal genomes. In the fungi, phylogenetic profiling yields high-confidence predictions for the highest and only the highest scoring gene pairs illustrating both the power and the limitations of the approach. Both practical examples and theoretical considerations suggest that in order to get a reliable and specific picture of a protein's function, results from phylogenetic profiling have to be combined with other sources of evidence.

Plasmodium falciparum sporozoites that develop and mature inside an Anopheles mosquito initiate a malaria infection in humans. Here we report the first proteomic comparison of different parasite stages from the mosquito -- early and late oocysts containing midgut sporozoites, and the mature, infectious salivary gland sporozoites. Despite the morphological similarity between midgut and salivary gland sporozoites, their proteomes are markedly different, in agreement with their increase in hepatocyte infectivity. The different sporozoite proteomes contain a large number of stage specific proteins whose annotation suggest an involvement in sporozoite maturation, motility, infection of the human host and associated metabolic adjustments. Analyses of proteins identified in the P. falciparum sporozoite proteomes by orthologous gene disruption in the rodent malaria parasite, P. berghei, revealed three previously uncharacterized Plasmodium proteins that appear to be essential for sporozoite development at distinct points of maturation in the mosquito. This study sheds light on the development and maturation of the malaria parasite in an Anopheles mosquito and also identifies proteins that may be essential for sporozoite infectivity to humans.

BACKGROUND: In the post-genomic era various functional genomics, proteomics and computational techniques have been developed to elucidate the protein interaction network. While some of these techniques are specific for a certain type of interaction, most predict a mixture of interactions. Qualitative labels are essential for the molecular biologist to experimentally verify predicted interactions. RESULTS: Of the individual protein-protein interaction prediction methods, some can predict physical interactions without producing other types of interactions. None of the methods can specifically predict metabolic interactions. We have constructed an 'omics evidence landscape' that combines all sources of evidence for protein interactions from various types of omics data for Saccharomyces cerevisiae. We explore this evidence landscape to identify areas with either only metabolic or only physical interactions, allowing us to specifically predict the nature of new interactions in these areas. We combine the datasets in ways that examine the whole evidence landscape and not only the highest scoring protein pairs in both datasets and find specific predictions. CONCLUSION: The combination of evidence types in the form of the evidence landscape allows for qualitative labels to be inferred and placed on the predicted protein interaction network of S. cerevisiae. These qualitative labels will help in the biological interpretation of gene networks and will direct experimental verification of the predicted interactions.

A full description of a protein's function requires knowledge of all partner proteins with which it specifically associates. From a functional perspective, 'association' can mean direct physical binding, but can also mean indirect interaction such as participation in the same metabolic pathway or cellular process. Currently, information about protein association is scattered over a wide variety of resources and model organisms. STRING aims to simplify access to this information by providing a comprehensive, yet quality-controlled collection of protein-protein associations for a large number of organisms. The associations are derived from high-throughput experimental data, from the mining of databases and literature, and from predictions based on genomic context analysis. STRING integrates and ranks these associations by benchmarking them against a common reference set, and presents evidence in a consistent and intuitive web interface. Importantly, the associations are extended beyond the organism in which they were originally described, by automatic transfer to orthologous protein pairs in other organisms, where applicable. STRING currently holds 730,000 proteins in 180 fully sequenced organisms, and is available at http://string.embl.de/.

In the genomics era, the interactions between proteins are at the center of attention. Genomic-context methods used to predict these interactions have been put on a quantitative basis, revealing that they are at least on an equal footing with genomics experimental data. A survey of experimentally confirmed predictions proves the applicability of these methods, and new concepts to predict protein interactions in eukaryotes have been described. Finally, the interaction networks that can be obtained by combining the predicted pair-wise interactions have enough internal structure to detect higher levels of organization, such as 'functional modules'.

Functional links between proteins can often be inferred from genomic associations between the genes that encode them: groups of genes that are required for the same function tend to show similar species coverage, are often located in close proximity on the genome (in prokaryotes), and tend to be involved in gene-fusion events. The database STRING is a precomputed global resource for the exploration and analysis of these associations. Since the three types of evidence differ conceptually, and the number of predicted interactions is very large, it is essential to be able to assess and compare the significance of individual predictions. Thus, STRING contains a unique scoring-framework based on benchmarks of the different types of associations against a common reference set, integrated in a single confidence score per prediction. The graphical representation of the network of inferred, weighted protein interactions provides a high-level view of functional linkage, facilitating the analysis of modularity in biological processes. STRING is updated continuously, and currently contains 261 033 orthologs in 89 fully sequenced genomes. The database predicts functional interactions at an expected level of accuracy of at least 80% for more than half of the genes; it is online at http://www.bork.embl-heidelberg.de/STRING/.

With the increasing availability of genome sequences, new methods are being proposed that exploit information from complete genomes to classify species in a phylogeny. Here we present SHOT, a web server for the classification of genomes on the basis of shared gene content or the conservation of gene order that reflects the dominant, phylogenetic signal in these genomic properties. In general, the genome trees are consistent with classical gene-based phylogenies, although some interesting exceptions indicate massive horizontal gene transfer. SHOT is a useful tool for analysing the tree of life from a genomic point of view. It is available at http://www.Bork.EMBL-Heidelberg.de/SHOT.

By combining the pairwise interactions between proteins, as predicted by the conserved co-occurrence of their genes in operons, we obtain protein interaction networks. Here we study the properties of such networks to identify functional modules: sets of proteins that together are involved in a biological process. The complete network contains 3,033 orthologous groups of proteins in 38 genomes. It consists of one giant component, containing 1,611 orthologous groups, and of 516 small disjointed clusters that, on average, contain only 2.7 orthologous groups. These small clusters have a homogeneous functional composition and thus represent functional modules in themselves. Analysis of the giant component reveals that it is a scale-free, small-world network with a high degree of local clustering (C = 0.6). It consists of locally highly connected subclusters that are connected to each other by linker proteins. The linker proteins tend to have multiple functions, or are involved in multiple processes and have an above average probability of being essential. By splitting up the giant component at these linker proteins, we identify 265 subclusters that tend to have a homogeneous functional composition. The rare functional inhomogeneities in our subclusters reflect the mixing of different types of (molecular) functions in a single cellular process, exemplified by subclusters containing both metabolic enzymes as well as the transcription factors that regulate them. Comparative genome analysis, thus, allows identification of a level of functional interaction between that of pairwise interactions, and of the complete genome.

In the course of evolution, genomes are shaped by processes like gene loss, gene duplication, horizontal gene transfer, and gene genesis (the de novo origin of genes). Here we reconstruct the gene content of ancestral Archaea and Proteobacteria and quantify the processes connecting them to their present day representatives based on the distribution of genes in completely sequenced genomes. We estimate that the ancestor of the Proteobacteria contained around 2500 genes, and the ancestor of the Archaea around 2050 genes. Although it is necessary to invoke horizontal gene transfer to explain the content of present day genomes, gene loss, gene genesis, and simple vertical inheritance are quantitatively the most dominant processes in shaping the genome. Together they result in a turnover of gene content such that even the lineage leading from the ancestor of the Proteobacteria to the relatively large genome of Escherichia coli has lost at least 950 genes. Gene loss, unlike the other processes, correlates fairly well with time. This clock-like behavior suggests that gene loss is under negative selection, while the processes that add genes are under positive selection.

We raise some issues in detecting the conservation (or absence thereof) of co-regulation using gene order; how we think the variations in the cellular network in various species can be studied; and how to determine and interpret the higher order structure in networks of functional relations.

Comparisons of the gene order in closely related genomes reveal a major role for inversions in the genome shuffling process. In contrast to prokaryotes, where the inversions are predominantly large, half of the inversions between Saccharomyces cerevisiae and Candida albicans appear to be small, often encompassing only a single gene. Overall the genome rearrangement rate appears higher in eukaryotes than in prokaryotes, and the current genome data do not indicate that functional constraints on the co-expression of neighboring genes have a large role in conserving eukaryotic gene order. Nevertheless, qualitatively interesting examples of conservation of gene order in eukaryotes can be observed.

Much has been learned about the cellular pathology of Friedreich's ataxia, a recessive neurodegenerative disease resulting from insufficient expression of the mitochondrial protein frataxin. However, the biochemical function of frataxin has remained obscure, hampering attempts at therapeutic intervention. To predict functional interactions of frataxin with other proteins we investigated whether its gene specifically co-occurs with any other genes in sequenced genomes. In 56 available genomes we identified two genes with identical phylogenetic distributions to the frataxin/cyaY gene: hscA and hscB/JAC1. These genes have not only emerged in the same evolutionary lineage as the frataxin gene, they have also been lost at least twice with it, and they have been horizontally transferred with it in the evolution of the mitochondria. The proteins encoded by hscA and hscB, the chaperone HSP66 and the co-chaperone HSP20, have been shown to be required for the synthesis of 2Fe-2S clusters on ferredoxin in proteobacteria. JAC1, an ortholog of hscB, and SSQ1, a paralog of hscA, have been shown to be required for iron-sulfur cluster assembly in mitochondria of Saccharomyces cerevisiae. Combining data on the co-occurrence of genes in genomes with experimental and predicted cellular localization data of their proteins supports the hypothesis that frataxin is directly involved in iron-sulfur cluster protein assembly. They indicate that frataxin is specifically involved in the same sub-process as HSP20/Jac1p.

Four years after the original sequence submission, we have re-annotated the genome of Mycoplasma pneumoniae to incorporate novel data. The total number of ORFss has been increased from 677 to 688 (10 new proteins were predicted in intergenic regions, two further were newly identified by mass spectrometry and one protein ORF was dismissed) and the number of RNAs from 39 to 42 genes. For 19 of the now 35 tRNAs and for six other functional RNAs the exact genome positions were re-annotated and two new tRNA(Leu) and a small 200 nt RNA were identified. Sixteen protein reading frames were extended and eight shortened. For each ORF a consistent annotation vocabulary has been introduced. Annotation reasoning, annotation categories and comparisons to other published data on M.pneumoniae functional assignments are given. Experimental evidence includes 2-dimensional gel electrophoresis in combination with mass spectrometry as well as gene expression data from this study. Compared to the original annotation, we increased the number of proteins with predicted functional features from 349 to 458. The increase includes 36 new predictions and 73 protein assignments confirmed by the published literature. Furthermore, there are 23 reductions and 30 additions with respect to the previous annotation. mRNA expression data support transcription of 184 of the functionally unassigned reading frames.

Various new methods have been proposed to predict functional interactions between proteins based on the genomic context of their genes. The types of genomic context that they use are Type I: the fusion of genes; Type II: the conservation of gene-order or co-occurrence of genes in potential operons; and Type III: the co-occurrence of genes across genomes (phylogenetic profiles). Here we compare these types for their coverage, their correlations with various types of functional interaction, and their overlap with homology-based function assignment. We apply the methods to Mycoplasma genitalium, the standard benchmarking genome in computational and experimental genomics. Quantitatively, conservation of gene order is the technique with the highest coverage, applying to 37% of the genes. By combining gene order conservation with gene fusion (6%), the co-occurrence of genes in operons in absence of gene order conservation (8%), and the co-occurrence of genes across genomes (11%), significant context information can be obtained for 50% of the genes (the categories overlap). Qualitatively, we observe that the functional interactions between genes are stronger as the requirements for physical neighborhood on the genome are more stringent, while the fraction of potential false positives decreases. Moreover, only in cases in which gene order is conserved in a substantial fraction of the genomes, in this case six out of twenty-five, does a single type of functional interaction (physical interaction) clearly dominate (>80%). In other cases, complementary function information from homology searches, which is available for most of the genes with significant genomic context, is essential to predict the type of interaction. Using a combination of genomic context and homology searches, new functional features can be predicted for 10% of M. genitalium genes.

Recently, a number of techniques have been proposed that use completely sequenced genomes for the function prediction of individual proteins encoded therein. They use the fusion of genes, their conserved location in operons or merely their co-occurrence in genomes to predict the existence of functional interactions between the proteins they encode. This type of information complements functional features that are predicted by classical homology-based search techniques.

The repeated occurrence of genes in each other's neighbourhood on genomes has been shown to indicate a functional association between the proteins they encode. Here we introduce STRING (search tool for recurring instances of neighbouring genes), a tool to retrieve and display the genes a query gene repeatedly occurs with in clusters on the genome. The tool performs iterative searches and visualises the results in their genomic context. By finding the genomically associated genes for a query, it delineates a set of potentially functionally associated genes. The usefulness of STRING is illustrated with an example that suggests a functional context for an RNA methylase with unknown specificity.

Comparative analysis of metabolic pathways in different genomes yields important information on their evolution, on pharmacological targets and on biotechnological applications. In this study on glycolysis, three alternative ways of comparing biochemical pathways are combined: (1) analysis and comparison of biochemical data, (2) pathway analysis based on the concept of elementary modes, and (3) a comparative genome analysis of 17 completely sequenced genomes. The analysis reveals a surprising plasticity of the glycolytic pathway. Isoenzymes in different species are identified and compared; deviations from the textbook standard are detailed. Several potential pharmacological targets and by-passes (such as the Entner-Doudoroff pathway) to glycolysis are examined and compared in the different species. Archaean, bacterial and parasite specific adaptations are identified and described.

The presence of genes encoding enzymes involved in the citric-acid cycle has been studied in 19 completely sequenced genomes. In the majority of species, the cycle appears to be incomplete or absent. Several distinct, incomplete cycles reflect adaptations to different environments. Their distribution over the phylogenetic tree hints at precursors in the evolution of the citric-acid cycle.

Doolittle argued that to construct phylogenies, an organism should be regarded as either less or more than the sum of its genes (1). The argument is based on the observation that gene phylogenies are rarely consistent with one another because, among others, of lateral gene transfer (LGT). Creating phylogenies from sequence data in which an organism is described exactly as the sum of its genes is not, however, the only approach (2). Rather than creating phylogenies based on sequence identity for separate genes, this alternative creates a distance-based phylogeny at the genome level by comparing the fraction of genes shared between genomes (2). The resulting phylogeny (Fig. 1) of completely sequenced genomes (for an overview, see http://www.tigr.org/tdb/tdb.html) is remarkably similar to the phylogenies that are based on 16S ribosomal RNA (3). Not only is the trichotomy between Eukarya, Bacteria, and Archaea present, but within each of these taxa the clusters generally recognized as being monophyletic and for which multiple genomes are available, all have high bootstrap values (the Proteobacteria and their branching order, the Spirochaetales, the low (G+C) Gram-positive bacteria, and the Euryarchaeota). This method does not resolve the major branchings of the Bacteria, but neither do the phylogenies based on sequences that do not show LGT resolve this part of Bacterial phylogeny with a high degree of confidence.

Species phylogenies derived from comparisons of single genes are rarely consistent with each other, due to horizontal gene transfer, unrecognized paralogy and highly variable rates of evolution. The advent of completely sequenced genomes allows the construction of a phylogeny that is less sensitive to such inconsistencies and more representative of whole-genomes than are single-gene trees. Here, we present a distance-based phylogeny constructed on the basis of gene content, rather than on sequence identity, of 13 completely sequenced genomes of unicellular species. The similarity between two species is defined as the number of genes that they have in common divided by their total number of genes. In this type of phylogenetic analysis, evolutionary distance can be interpreted in terms of evolutionary events such as the acquisition and loss of genes, whereas the underlying properties (the gene content) can be interpreted in terms of function. As such, it takes a position intermediate to phylogenies based on single genes and phylogenies based on phenotypic characteristics. Although our comprehensive genome phylogeny is independent of phylogenies based on the level of sequence identity of individual genes, it correlates with the standard reference of prokarytic phylogeny based on sequence similarity of 16s rRNA. Thus, shared gene content between genomes is quantitatively determined by phylogeny, rather than by phenotype, and horizontal gene transfer has only a limited role in determining the gene content of genomes.

We introduce and analyze a general model of a population evolving over a network of selectively neutral genotypes. We show that the population's limit distribution on the neutral network is solely determined by the network topology and given by the principal eigenvector of the network's adjacency matrix. Moreover, the average number of neutral mutant neighbors per individual is given by the matrix spectral radius. These results quantify the extent to which populations evolve mutational robustness-the insensitivity of the phenotype to mutations-and thus reduce genetic load. Because the average neutrality is independent of evolutionary parameters-such as mutation rate, population size, and selective advantage-one can infer global statistics of neutral network topology by using simple population data available from in vitro or in vivo evolution. Populations evolving on neutral networks of RNA secondary structures show excellent agreement with our theoretical predictions.

Predicting function from sequence using computational tools is a highly complicated procedure that is generally done for each gene individually. This review focuses on the added value that is provided by completely sequenced genomes in function prediction. Various levels of sequence annotation and function prediction are discussed, ranging from genomic sequence to that of complex cellular processes. Protein function is currently best described in the context of molecular interactions. In the near future it will be possible to predict protein function in the context of higher order processes such as the regulation of gene expression, metabolic pathways and signalling cascades. The analysis of such higher levels of function description uses, besides the information from completely sequenced genomes, also the additional information from proteomics and expression data. The final goal will be to elucidate the mapping between genotype and phenotype.

A systematic comparison of nine bacterial and archaeal genomes reveals a low level of gene-order (and operon architecture) conservation. Nevertheless, a number of gene pairs are conserved. The proteins encoded by conserved gene pairs appear to interact physically. This observation can therefore be used to predict functions of, and interactions between, prokaryotic gene products.

We propose a new method for detecting conserved RNA secondary structures in a family of related RNA sequences. Our method is based on a combination of thermodynamic structure prediction and phylogenetic comparison. In contrast to purely phylogenetic methods, our algorithm can be used for small data sets of approximately 10 sequences, efficiently exploiting the information contained in the sequence variability. The procedure constructs a prediction only for those parts of sequences that are consistent with a single conserved structure. Our implementation produces reasonable consensus structures without user interference. As an example we have analysed the complete HIV-1 and hepatitis C virus (HCV) genomes as well as the small segment of hantavirus. Our method confirms the known structures in HIV-1 and predicts previously unknown conserved RNA secondary structures in HCV.

The determination of complete genome sequences provides us with an opportunity to describe and analyze evolution at the comprehensive level of genomes. Here we compare nine genomes with respect to their protein coding genes at two levels: (i) we compare genomes as "bags of genes" and measure the fraction of orthologs shared between genomes and (ii) we quantify correlations between genes with respect to their relative positions in genomes. Distances between the genomes are related to their divergence times, measured as the number of amino acid substitutions per site in a set of 34 orthologous genes that are shared among all the genomes compared. We establish a hierarchy of rates at which genomes have changed during evolution. Protein sequence identity is the most conserved, followed by the complement of genes within the genome. Next is the degree of conservation of the order of genes, whereas gene regulation appears to evolve at the highest rate. Finally, we show that some genomes are more highly organized than others: they show a higher degree of the clustering of genes that have orthologs in other genomes.

We introduce a simple and rapid strategy to identify genes that are responsible for species-specific phenotypes. The genome of a species that has a specific phenotype is compared with at least one, closely related, species that lacks this phenotype. Homologous genes that are shared among the species compared are identified and discarded from the list of candidates for species-specific genes. The process is automated and rapidly yields a small subset of the genome that likely contains genes responsible for the species-specific features. Functions are assigned to the genes, and dubious annotations are filtered out. Information is extracted not only from the presence of genes, but also from their absence with respect to known phenotypes. We have applied the technique to identify a set of species-specific genes in Helicobacter pylori by comparing it with its closest relatives for which complete genome sequences are available, Haemophilus influenzae and Escherichia coli. Of the genes of this set for which functional features can be obtained, a large fraction (63%, 123 proteins) is (potentially) involved in H. pylori's interaction with its host. We hypothesize that a family of outer membrane proteins is critical for the ability of H. pylori to colonize host cells in highly acidic environments.

Homology search techniques based on the iterative PSI-BLAST method in combination with various filters for low sequence complexity are applied to assign folds to all Mycoplasma genitalium proteins. The resulting procedure (implemented as a web server) is able to predict at least one domain in 37% of these proteins automatically, with an estimated accuracy higher than 98%. Taking structural features such as coiled coil or transmembrane regions aside, folds can be assigned to more than half of the globular proteins in a bacterium just by iterative sequence comparison.

We compare the frequency distribution of gene family sizes in the complete genomes of six bacteria (Escherichia coli, Haemophilus influenzae, Helicobacter pylori, Mycoplasma genitalium, Mycoplasma pneumoniae, and Synechocystis sp. PCC6803), two Archaea (Methanococcus jannaschii and Methanobacterium thermoautotrophicum), one eukaryote (Saccharomyces cerevisiae), the vaccinia virus, and the bacteriophage T4. The sizes of the gene families versus their frequencies show power-law distributions that tend to become flatter (have a larger exponent) as the number of genes in the genome increases. Power-law distributions generally occur as the limit distribution of a multiplicative stochastic process with a boundary constraint. We discuss various models that can account for a multiplicative process determining the sizes of gene families in the genome. In particular, we argue that, in order to explain the observed distributions, gene families have to behave in a coherent fashion within the genome; i.e., the probabilities of duplications of genes within a gene family are not independent of each other. Likewise, the probabilities of deletions of genes within a gene family are not independent of each other.

The bovine papillomavirus type 1 (BPV-1) exonic splicing suppressor (ESS) is juxtaposed immediately downstream of BPV-1 splicing enhancer 1 and negatively modulates selection of a suboptimal 3' splice site at nucleotide 3225. The present study demonstrates that this pyrimidine-rich ESS inhibits utilization of upstream 3' splice sites by blocking early steps in spliceosome assembly. Analysis of the proteins that bind to the ESS showed that the U-rich 5' region binds U2AF65 and polypyrimidine tract binding protein, the C-rich central part binds 35- and 54-55-kDa serine/arginine-rich (SR) proteins, and the AG-rich 3' end binds alternative splicing factor/splicing factor 2. Mutational and functional studies indicated that the most critical region of the ESS maps to the central C-rich core (GGCUCCCCC). This core sequence, along with additional nonspecific downstream nucleotides, is sufficient for partial suppression of spliceosome assembly and splicing of BPV-1 pre-mRNAs. The inhibition of splicing by the ESS can be partially relieved by excess purified HeLa SR proteins, suggesting that the ESS suppresses pre-mRNA splicing by interfering with normal bridging and recruitment activities of SR proteins.

We have analyzed the base-pairing probability distributions of 16 S and 16 S-like, and 23 S and 23 S-like ribosomal RNAs of Archaea, Bacteria, chloroplasts, mitochondria and Eukarya, as predicted by the partition function approach for RNA folding introduced by McCaskill. A quantitative analysis of the reliability of RNA folding is done by comparing the base-pairing probability distributions with the structures predicted by comparative sequence analysis (comparative structures). We distinguish two factors that show a relationship to the reliability of RNA minimum free energy structure. The first factor is the dominance of one particular base-pair or the absence of base-pairing for a given base within the base-pairing probability distribution (BPPD). We characterize the BPPD per base, including the probability of not base-pairing, by its Shannon entropy (S). The S value indicates the uncertainty about the base-pairing of a base: low S values result from BPPDs that are strongly dominated by a single base-pair or by the absence of base-pairing. We show that bases with low S values have a relatively high probability that their minimum free energy (MFE) structure corresponds to the comparative structure. The BPPDs of prokaryotes that live at high temperatures (thermophilic Archaea and Bacteria) have, calculated at 37 degrees C, lower S values than the BPPDs of prokaryotes that live at lower temperatures (mesophilic and psychrophilic Archaea and Bacteria). This reflects an adaptation of the ribosomal RNAs to the environmental temperature. A second factor that is important to consider with regard to the reliability of MFE structure folding is a variable degree of applicability of the thermodynamic model of RNA folding for different groups of RNAs. Here we show that among the bases that show low S values, the Archaea and Bacteria have similar, high probabilities (0.96 and 0.94 in 16 S and 0.93 and 0.91 in 23 S, respectively) that the MFE structure corresponds to the comparative structure. These probabilities are lower in the chloroplasts (16 S 0.91, 23 S 0.79), mitochondria (16 S-like 0.89, 23 S-like 0.69) and Eukarya (18 S 0.81, 28 S 0.86).

RNA secondary-structure folding algorithms predict the existence of connected networks of RNA sequences with identical secondary structures. Fitness landscapes that are based on the mapping between RNA sequence and RNA secondary structure hence have many neutral paths. A neutral walk on these fitness landscapes gives access to a virtually unlimited number of secondary structures that are a single point mutation from the neutral path. This shows that neutral evolution explores phenotype space and can play a role in adaptation.

We have calculated the base pair probability distribution for the secondary structure of a full length HIV-1 genome using the partition function approach introduced by McCaskill (1990). By analyzing the full distribution of base pair probabilities instead of a restricted number of secondary structures, we gain more complete and reliable information about the secondary structure of HIV-1. We introduce methods that condense the information in the probability distribution to one value per nucleotide in the sequence. Using these methods we represent the secondary structure as a weighted average of the base pair probabilities, and we can identify interesting secondary structures that have relatively well-defined base pairing. The results show high probabilities for the known secondary structures at the 5'-end of the molecule that have been predicted on the basis of biochemical data. The Rev response element (RRE) appears as a distinct element in the secondary structure. It has a meta-stable domain at the high affinity site for the binding of Rev. The overall structure decomposes into fairly small independent structures in the first 4,000 bases of the molecule. The remaining 5,000 bases (excluding the terminal repeat) form a single, large structure, on top of which the RRE is located.

RNA secondary structure folding algorithms predict the existence of connected networks of RNA sequences with identical structure. On such networks, evolving populations split into subpopulations, which diffuse independently in sequence space. This demands a distinction between two mutation thresholds: one at which genotypic information is lost and one at which phenotypic information is lost. In between, diffusion enables the search of vast areas in genotype space while still preserving the dominant phenotype. By this dynamic the success of phenotypic adaptation becomes much less sensitive to the initial conditions in genotype space.