The emergence of eukaryotes as an evolutionary algorithmic phase transition.

The origin of eukaryotes represents one of the most significant events in evolution since it allowed the posterior emergence of multicellular organisms. Yet, it remains unclear how existing regulatory mechanisms of gene activity were transformed to allow this increase in complexity. Here, we address this question by analyzing the length distribution of proteins and their corresponding genes for 6,519 species across the tree of life. We find a scale-invariant relationship between gene mean length and variance maintained across the entire evolutionary history. Using a simple model, we show that this scale-invariant relationship naturally originates through a simple multiplicative process of gene growth. During the first phase of this process, corresponding to prokaryotes, protein length follows gene growth. At the onset of the eukaryotic cell, however, mean protein length stabilizes around 500 amino acids. While genes continued growing at the same rate as before, this growth primarily involved noncoding sequences that complemented proteins in regulating gene activity. Our analysis indicates that this shift at the origin of the eukaryotic cell was due to an algorithmic phase transition equivalent to that of certain search algorithms triggered by the constraints in finding increasingly larger proteins.