To explore the statistics of protein sequences, we employ the idea of mapping the sequence onto the trajectory of a random walk. Using three different mappings, corresponding to three basic physical interactions between amino-acids, we found pronounced deviations from pure randomness, and these deviations seem directed towards the minimization of the energy of the 3D structure. We consider this result as evidence for a physically driven stage of evolution. We also discuss further findings of non-random patterns found in proteins in connection with their folding properties, such as reliable nucleation.