<title>1. Introduction</title> <p>Two assumptions are generally made when considering the molecular evolution of functional proteins during the history of life on Earth. Firstly, the size of protein sequence space, i.e. the number of possible amino acid sequences, is astronomically large and, secondly, that only an infinitesimally small portion has been explored during the course of life on Earth (e.g. ##REF##5343878##Salisbury 1969##; ##REF##5411867##Maynard Smith 1970##; ##UREF##14##Mandecki 1998##; ##REF##12816604##Luisi 2003##; ##UREF##4##Carrier 2004##; ##UREF##8##de Duve 2005##). Luisi and Chiarabelli have termed the unexplored part of sequence space as containing the ‘never born proteins’ (##REF##17131092##Luisi et al. 2006##; ##REF##17610146##Chiarabelli &amp; de Lucrezia 2007##). We wish to discuss these two assumptions by estimating how much of this space could have been explored since the origin of life some 4 Gyr ago. As will be described below, others have concluded that the first assumption is incorrect and we agree with this conclusion. However, we also conclude that the second assumption is incorrect and calculate that most of the sequence space may have been explored.</p> <p>Before turning to a discussion of the second assumption, we wish to summarize information showing the first assumption, namely that the sequence space is vast, to be false. A typical estimate of the size of sequence space is 20<sup>100</sup> (approx. 10<sup>130</sup>) for a protein of 100 amino acids in which any of the normally occurring 20 amino acids can be found. This number is indeed gigantic but it is likely to be a significant overestimate of the size of protein sequence space. For example, Dill and colleagues used simple theoretical models to suggest (##REF##2300551##Lau &amp; Dill 1990##; ##UREF##5##Chan &amp; Dill 1991##; ##REF##10386867##Dill 1999##), and experimental or computational variation of protein sequence provides ample evidence (##REF##8696970##Cordes et al. 1996##; ##REF##9334745##Riddle et al. 1997##; ##REF##9519299##Plaxco et al. 1998##; ##REF##12441379##Larson et al. 2002##; ##REF##15197260##Guo et al. 2004##; ##REF##15928003##Doi et al. 2005##), that the actual identity of most of the amino acids in a protein is irrelevant. An example in nature could be the prokaryotic DNA methyltransferases which each contain a target recognition domain (TRD) of approximately 150 amino acids that recognizes specific DNA sequences usually of 3–6 bp in length, and a conserved catalytic domain. The thousands of known TRD sequences show negligible amino acid sequence conservation despite the rather limited number of nucleotide sequences they are required to recognize (e.g. ##REF##9254696##Sturrock &amp; Dryden 1997##; ##REF##9843515##O'Neill et al. 1998##; ##REF##11996004##Bujnicki 2001##; ##REF##17202163##Roberts et al. 2007##). As an extreme method to reduce the size of sequence space, ##REF##10386867##Dill (1999)## suggested that only two types of amino acid were needed to form a protein structure, hydrophilic and hydrophobic, and that furthermore it was critical to define only the surface of the protein. These two suggestions reduce the size of sequence space to 2<sup>100</sup> and 2<sup>33</sup>, respectively (i.e. approx. 10<sup>30</sup> and approx. 10<sup>10</sup>). It is noteworthy that recent coarse-grained ‘tube’ models go even further and remove all atomic information leaving only a potential energy function for interaction with other parts of the tube. Despite the extreme coarse graining of this model, recognizable ‘protein’ structures can still be found (##UREF##1##Banavar et al. 2006##). Although this may appear to go against Anfinsen's dogma that a protein structure is determined by its amino acid sequence (##UREF##0##Anfinsen 1973##), it is really only a case of an extreme reduction in the size of the amino acid ‘alphabet’. The tube structures obtained are rather similar to the short folded segments adopted by sequences apparently conserved since the last universal ancestor (##REF##17075700##Sobolevsky &amp; Trifonov 2006##). The assumption that a protein chain needs to be at least 100 amino acids in length also rather inflates the size of sequence space when it is known that many proteins are modular and contain domains of as few as approximately 50 amino acids thereby reducing the space to 20<sup>50</sup> or approximately 10<sup>65</sup> (e.g. ##REF##17075700##Sobolevsky &amp; Trifonov 2006##). The conclusion from all of these coarse-graining approaches is that a reduced alphabet of amino acids is quite capable of producing all protein folds (approx. a few thousand discrete folds; ##UREF##10##Denton 2008##) and providing a scaffold capable of supporting all protein functions (we will ignore the space of natively unfolded proteins for this current discussion but since such proteins usually fold upon performing their function, the distinction is not important for our purposes; ##REF##15738986##Dyson &amp; Wright 2005##). The phase space of function may be some orders of magnitude greater than the size of the folding space as metagenomics projects are revealing increasing numbers of unknown protein families as adjudged by the number of novel protein sequences (##REF##17574832##Raes et al. 2007##). However, it is not clear that new folds are present as a conserved fold, such as the TIM barrel, is capable of displaying many functions (##REF##12206759##Nagano et al. 2002##).</p> <p>To further support this idea of a reduced alphabet of amino acids, there are also very plausible suggestions that the original amino acid repertoire consisted of only four or five amino acids like those found in the Miller–Urey experiments and the Murchison meteorite (##REF##1018332##Miller et al. 1976##), and that the genetic code was initially limited to these few amino acids that still predominate in proteins to the current day (e.g. ##REF##11164045##Trifonov 2000##; ##REF##12270892##Brooks et al. 2002##; ##REF##11937687##Ikehara 2002##). Proteins with reduced amino acid repertoires can fold and function successfully (e.g. ##REF##8696970##Cordes et al. 1996##; ##REF##9334745##Riddle et al. 1997##; ##REF##9519299##Plaxco et al. 1998##; ##REF##15197260##Guo et al. 2004##; ##REF##15928003##Doi et al. 2005##; ##UREF##13##López de la Osa et al. 2007##).</p> <p>##FIG##0##Figure 1## shows the number of possible sequences as a function of the number of different amino acids (or classes of amino acids, 1–20) and the length of the functionally important amino acid chain (33, 50 or 100). It highlights the drastic reduction in the size of sequence space if one limits the number of available amino acid types to less than the 20 usually found today, a limitation that appears to be justified experimentally.</p>
<title>2. Results</title> <p>We now wish to consider the second assumption commonly made about protein sequence space: that only an infinitesimal fraction has been explored by life on Earth. To examine how much of sequence space could have been explored, it is simplest to make upper and lower limit estimates for the number of unique amino acid sequences produced since the origin of life using some liberal assumptions. Considering the upper limit, it is clear that bacteria dominate the planet in terms of the product of the number of cells (10<sup>30</sup>; ##REF##9618454##Whitman et al. 1998##) multiplied by the number of genes in each genome (10<sup>4</sup>, a small overestimate). Let us assume that every single gene in this total of 10<sup>34</sup> is unique and that evolution has been working on these genes for 4 Gyr completely changing each gene to some other unique, new gene every single year. This gives an extreme upper limit of 4×10<sup>43</sup> different amino acid sequences explored since the origin of life. The contribution to this number of sequences by viral and eukaryotic genomes is difficult to estimate but it is very unlikely to be orders of magnitude greater than the 4×10<sup>43</sup> sequences from bacteria. If their contribution is similar or smaller, then it can be ignored in our rough calculation. For comparison with our calculation, ##UREF##14##Mandecki (1998)## gave a limit of 10<sup>50</sup> protein sequences since the origin of life. A lower limit to the number of sequences explored is more difficult to estimate but it has been estimated that there are 10<sup>9</sup> different bacterial species on Earth (##REF##9618454##Whitman et al. 1998##; ##REF##16185861##Medini et al. 2005##; ##REF##15851667##Simonson et al. 2005##). If we assume that each species has a unique complement of 10<sup>3</sup> sequences (an underestimate) and that only one sequence has changed per species per generation (a reasonable estimate based upon analysis of mutation rates in bacteria; ##REF##17690297##Perfeito et al. 2007##), and that the generation time is 1 year (a considerable underestimate for many modern bacteria (##UREF##15##Ochman et al. 1999##), but perhaps reasonable for an ancient organism or one growing slowly in a poor environment), then we arrive at a figure of 4×10<sup>21</sup> different protein sequences tested since the origin of life.</p> <p>These two limits are shown in ##FIG##0##figure 1##. Although the oft-quoted 20<sup>100</sup> (approx. 10<sup>130</sup>) size of sequence space is far above these limits, the other more plausible estimates for the size of sequence space, particularly with limited amino acid diversity or reduced length, are near to or within these two limits. Considering the upper limit, all sequences containing 20, 8 and 3 types of amino acids have been explored if the chains are 33, 50 and 100 amino acids in length, respectively. Considering the lower limit, then virtually all chains of length 33 and 50 amino acids containing five or three types of amino acid, respectively, could have been explored. (The exploration of longer chains of 100 amino acids with only two types of residue is obviously much less complete but it is not a negligible fraction of the total.) Therefore it is entirely feasible that for all practical (i.e. functional and structural) purposes, protein sequence space has been fully explored during the course of evolution of life on Earth (perhaps even before the appearance of eukaryotes).</p>
<title>3. Discussion</title> <p>Protein sequence space is often viewed as a limitless desert of maladjusted sequences with only a few oases of working sequences linked by narrow pathways (Axe ##REF##10966772##2000##, ##REF##15321723##2004##). The navigation over this space by natural selection is difficult and could take many different routes thus resulting in organisms with largely different protein compositions. This idea of contingency, if taken at the level of species, led Gould to suggest that if one was to rerun the ‘tape of life’ then evolution would take a totally different path and we, as a species, would only appear as a highly improbable accident (##UREF##11##Gould 1991##; ##REF##12816604##Luisi 2003##; ##REF##17443872##de Duve 2007a##,##REF##17906945##b##). However, if there is any merit to our simple calculation then protein sequence analysis provides no support for the idea of contingency at a molecular level and it provides strong support for the ideas of convergence (Conway Morris ##REF##10647927##2000##, ##UREF##6##2004##; ##UREF##7##Dawkins 2005##; ##REF##16443685##Vermeij 2006##; ##REF##17443872##de Duve 2007a##,##REF##17906945##b##). If one was to rerun the tape, then the protein composition of organisms would be similar. Our calculation removes the almost impossibly unrealistic pressure on natural selection to navigate through protein sequence space avoiding the vast number of functionless sequences by simply indicating that most sequences have been tried are useful in some way, and that there are many possible routes to obtain proteins with desirable functions (##REF##12206759##Nagano et al. 2002##; ##REF##12547421##Anantharaman et al. 2003##; ##REF##17727879##Holliday et al. 2007##).</p> <p>Finally, we conclude that the number 20<sup>100</sup> and similar large numbers (e.g. ##REF##5343878##Salisbury 1969##; ##REF##5411867##Maynard Smith 1970##; ##UREF##14##Mandecki 1998##; ##REF##12816604##Luisi 2003##; ##UREF##4##Carrier 2004##; ##UREF##8##de Duve 2005##) are simply ‘straw men’ advanced to initiate discussion in the same spirit as the ‘Levinthal paradox’ of protein folding rates (##UREF##12##Levinthal 1969##; ##REF##1729690##Zwanzig et al. 1992##). 20<sup>100</sup> is now no more useful than the approximate 2×10<sup>1 834 097</sup> books present in ##UREF##2##Borges' (1999)## fantastical ‘Library of Babel’ and has no connection with the real world of amino acids and proteins. Hence, we hope that our calculation will also rule out any possible use of this big numbers ‘game’ to provide justification for postulating divine intervention (##UREF##3##Bradley 2004##; ##UREF##9##Dembski 2004##).</p>
<p>We suggest that the vastness of protein sequence space is actually completely explorable during the populating of the Earth by life by considering upper and lower limits for the number of organisms, genome size, mutation rate and the number of functionally distinct classes of amino acids. We conclude that rather than life having explored only an infinitesimally small part of sequence space in the last 4 Gyr, it is instead quite plausible for all of functional protein sequence space to have been explored and that furthermore, at the molecular level, there is no role for contingency.</p>
<p>We thank the Engineering and Physical Sciences Research Council for the award of a grant to D. Dryden, M. Greaney, M. Bradley, D. A. Leigh and R. L. Baxter which partially funded this work. We gratefully acknowledge discussions with Simon Conway Morris (Cambridge), Tom McLeish (Leeds) and Wilson Poon (Edinburgh). We also thank the referees, including Geerat J. Vermeij, for their detailed comments and opinions. This work was initiated at the Isaac Newton Institute for Mathematical Sciences workshop on ‘Statistical Mechanics of Molecular and Cellular Biological Systems’, January–July 2004.</p>
<fig id="fig1" position="float"><label>Figure 1</label><caption><p>The size of protein sequence space log(<italic>x</italic><sup><italic>L</italic></sup>) as a function of the size of the amino acid alphabet (i.e. the number of different types of amino acids, <italic>x</italic>) for proteins containing 33 (asterisks), 50 (open circles) or 100 (filled circles) amino acids (length <italic>L</italic>). The horizontal lines represent estimates of the maximum (solid line) and minimum (dashed line) number of sequences explored during the 4 Gyr since the origin of life on Earth.</p></caption></fig>
<graphic xlink:href="rsif20080085f01"/>
[{"mixed-citation": ["Anfinsen, C. B. 1973 "], "italic": ["Studies on the principles that govern the folding of protein chains"]}, {"surname": ["Banavar"], "given-names": ["J.R"], "article-title": ["Geometry of proteins: hydrogen bonding, sterics, and marginally compact tubes"], "source": ["Phys. Rev. E"], "volume": ["73"], "year": ["2006"], "fpage": ["031921"], "pub-id": ["10.1103/PhysRevE.73.031921"]}, {"mixed-citation": ["Borges, J. L. 1999 The Library of Babel. In "], "italic": ["Collected fictions"]}, {"surname": ["Bradley", "Dembski", "Ruse"], "given-names": ["W.L", "W.A", "M"], "article-title": ["Information, entropy and the origin of life"], "source": ["Debating design: from Darwin to DNA"], "year": ["2004"], "publisher-name": ["Cambridge University Press"], "publisher-loc": ["New York, NY"], "fpage": ["331"], "lpage": ["351"]}, {"surname": ["Carrier"], "given-names": ["R.C"], "article-title": ["The argument from biogenesis: probabilities against a natural origin of life"], "source": ["Biol. Philos"], "volume": ["19"], "year": ["2004"], "fpage": ["739"], "lpage": ["764"], "pub-id": ["10.1007/s10539-005-6860-1"]}, {"surname": ["Chan", "Dill"], "given-names": ["H.S", "K.A"], "article-title": ["\u201cSequence space soup\u201d of proteins and copolymers"], "source": ["J. Chem. Phys"], "volume": ["95"], "year": ["1991"], "fpage": ["3775"], "lpage": ["3787"], "pub-id": ["10.1063/1.460828"]}, {"surname": ["Conway Morris"], "given-names": ["S"], "article-title": ["Life's solution: inevitable humans in a lonely universe"], "year": ["2004"], "publisher-name": ["Cambridge University Press"], "publisher-loc": ["Cambridge, UK"]}, {"surname": ["Dawkins"], "given-names": ["R"], "article-title": ["The ancestor's tale: a pilgrimage to the dawn of life"], "year": ["2005"], "publisher-name": ["Phoenix, Orion Books Ltd"], "publisher-loc": ["London, UK"]}, {"surname": ["de Duve"], "given-names": ["C"], "article-title": ["Singularities: landmarks on the pathways of life"], "year": ["2005"], "publisher-name": ["Cambridge University Press"], "publisher-loc": ["Cambridge, UK"]}, {"surname": ["Dembski", "Dembski", "Ruse"], "given-names": ["W.A", "W.A", "M"], "article-title": ["The logical underpinnings of intelligent design"], "source": ["Debating design: from Darwin to DNA"], "year": ["2004"], "publisher-name": ["Cambridge University Press"], "publisher-loc": ["New York, NY"], "fpage": ["311"], "lpage": ["330"]}, {"surname": ["Denton", "Barrow", "Conway Morris", "Freeland", "Harper"], "given-names": ["M.J", "J.D", "S", "S.J", "C.L"], "article-title": ["Protein-based life as an emergent property of matter: the nature and biological fitness of the protein folds"], "suffix": ["Jr"], "source": ["Fitness of the cosmos for life; biochemistry and fine-tuning"], "year": ["2008"], "publisher-name": ["Cambridge University Press"], "publisher-loc": ["Cambridge, UK"], "fpage": ["256"], "lpage": ["279"]}, {"surname": ["Gould"], "given-names": ["S.J"], "article-title": ["Wonderful life: the Burgess shale and the nature of history"], "year": ["1991"], "publisher-name": ["Penguin Books Ltd"], "publisher-loc": ["London, UK"]}, {"surname": ["Levinthal", "Debrunner", "Tsibris", "Munck"], "given-names": ["C", "P", "J.C.M", "E"], "article-title": ["How to fold graciously. Mossbauer spectroscopy in biological systems"], "source": ["Proc. Meeting held at Allerton House, Monticello, IL"], "year": ["1969"], "publisher-name": ["University of Illinois Press"], "publisher-loc": ["Urbana, IL"], "fpage": ["22"], "lpage": ["24"]}, {"surname": ["L\u00f3pez de la Osa", "Bateman", "Ho", "Gonzalez", "Chakrabartty", "Laurents"], "given-names": ["J", "D.A", "S", "C", "A", "D.V"], "article-title": ["Getting specificity from simplicity in putative proteins from the prebiotic Earth"], "source": ["Proc. Natl Acad. Sci. USA"], "volume": ["104"], "year": ["2007"], "fpage": ["14\u200a941"], "lpage": ["14\u200a946"], "pub-id": ["10.1073/pnas.0706876104"]}, {"surname": ["Mandecki"], "given-names": ["W"], "article-title": ["The game of chess and searches in protein sequence space"], "source": ["Trends Biotechnol"], "volume": ["16"], "year": ["1998"], "fpage": ["200"], "lpage": ["202"], "pub-id": ["10.1016/S0167-7799(98)01188-3"]}, {"surname": ["Ochman", "Elwyn", "Moran"], "given-names": ["H", "S", "N.A"], "article-title": ["Calibrating bacterial evolution"], "source": ["Proc. Natl Acad. Sci. USA"], "volume": ["96"], "year": ["1999"], "fpage": ["12\u200a638"], "lpage": ["12\u200a643"], "pub-id": ["10.1073/pnas.96.22.12638"]}]
J R Soc Interface. 2008 Aug 6; 5(25):953-956