There is undeniable evidence showing that bacteria have strongly influenced the evolution and biological functions of multicellular organisms. It has been hypothesized that many host-microbial interactions have emerged so as to increase the adaptive fitness of the (the host plus its microbiota). Although this association has been corroborated for many specific cases, general mechanisms explaining the role of the microbiota in the evolution of the host are yet to be understood. Here we present an evolutionary model in which a network representing the host adapts in order to perform a predefined function. During its adaptation, the host network (HN) can interact with other networks representing its microbiota. We show that this interaction greatly accelerates and improves the adaptability of the HN without decreasing the adaptation of the microbial networks. Furthermore, the adaptation of the HN to perform several functions is possible only when it interacts with many different bacterial networks in a specialized way (each bacterial network participating in the adaptation of one function). Disrupting these interactions often leads to non-adaptive states, reminiscent of dysbiosis, where none of the networks the holobiont consists of can perform their respective functions. By considering the holobiont as a unit of selection and focusing on the adaptation of the host to predefined but arbitrary functions, our model predicts the need for specialized diversity in the microbiota. This structural and dynamical complexity in the holobiont facilitates its adaptation, whereas a homogeneous (non-specialized) microbiota is inconsequential or even detrimental to the holobiont's evolution. To our knowledge, this is the first model in which symbiotic interactions, diversity, specialization and dysbiosis in an ecosystem emerge as a result of coevolution. It also helps us understand the emergence of complex organisms, as they adapt more easily to perform multiple tasks than non-complex ones.
