Random fitness landscapes are highly navigable

Abstract With the increasing availability of large-scale empirical fitness landscape data, there is a need for simple yet informative null models that can be used to interpret metrics of landscape ruggedness and navigability. A natural choice of a null model for highly rugged landscapes assigns independent and identically distributed fitness values to the genotypes, a setting often referred to as the House of Cards (HoC) or mutational landscape model. In this work, we examine the navigability of these landscapes, as quantified by the mean size of the adaptive basins of local fitness peaks. The adaptive basin is the set of genotypes from which a peak can be reached via selectively accessible, i.e. strictly fitness-increasing mutational paths. Building on recent rigorous results on the statistics of accessible paths, we show that the adaptive basins in the HoC landscape encompass a positive fraction of all genotypes that is an analytically computable, increasing function of the number of alleles per site. For the four letter nucleotide alphabet, an average peak basin contains 52.8% of all genotypes. When conditioned on peak fitness, the expected basin size increases linearly with fitness rank. The exact results on adaptive basins are complemented by an approximate analysis of gradient basins formed by greedy adaptive paths which maximize the fitness increase in each step. We argue that recent reports of large adaptive basins in empirical fitness landscapes should be reinterpreted in the light of our findings.