Extending the Evolvability Model to the Prokaryotic World: Simulations and Results on Real Data

Abstract

In 2006, Valiant introduced a variation to his celebrated PAC (Probably Approximately Correct) model to biology, by which he wished to explain how, with two simple mechanisms—random variation and natural selection—complex life mechanisms evolved in such a short time. Subsequently, several works extended and specialized the evolvability framework to more specific processes. In this study, we extend the evolvability framework to accommodate horizontal gene transfer, the transfer of genetic material between unrelated organisms. While in a separate work, we focused on the theoretical aspects of this extension and its learnability power; here, the focus is on more practical and biological facets of this new model. Specifically, we focus on the evolutionary process of developing a trait and model it as the conjunction function. We demonstrate the speedup in learning time for a variant of conjunction to which learning algorithms are known. We also confront the new model with the recombination model on real data of Escherichia coli strains under the task of developing pathogenicity and obtain results adhering to current existing knowledge. Apart from the sheer extension to the understudied prokaryotic world, our work offers comparisons of three different models of evolution under the same conditions, which we believe is unique and of a separate interest.

1. Introduction

One of the most fundamental tasks in biology is deciphering the history of life on Earth. Darwin was the first to speculate that the history of life is best described using a tree structure. The leaves of this tree represent existing species and the branches represent evolutionary relationships. It is of no wonder that Darwin's only drawing in his On the Origin of Species (Darwin, 1859) is a sketch of a tree structure. A direct implication of this theory is that all life forms evolved through a series of mutations, occurring in an ancestor–descendant basis since the beginning of life.

This is the predominant theory of evolution, and hence, its appeal to exact sciences. In 2006, this theory was put by Valiant (2006, 2009) under a rigorous computational framework attempting to explore the learning power of this mechanism. A genome is viewed as a function, reacting to a set of signals from the outer world. Over time, this function improves toward a hidden ideal function, through generating mutations and through natural selection. Valiant named this framework evolvability. The goal of computational learning theory is to separate concept classes that can be efficiently learned under a certain framework, from those that cannot. Then, the formal question asked by Valiant is, what is the complexity of functions that can be efficiently learned. Examples of concept classes of interest include Conjunctions, Parities, and so on. Thus, the question of evolution can be asked in the language of computational learning theory: For what classes of functions, can one expect to find an evolutionary mechanism that gets arbitrarily close to the ideal, within feasible computational resources?

All previous works, except for the recombination model of Kanade, assumed a vertical mode of evolution where variation is introduced by applying random mutations to the parent's inherited genome. However, the emergence of high-throughput sequencing revealed strong signals that stand in conflict to the Darwinian theory. It appears that some life forms on Earth do not adhere to the principals of vertical evolution. Specifically, prokaryotic evolution is characterized by extensive gene mobility between species that is crucial for their survival (Koonin and Galperin, 2002; Gogarten and Townsend, 2005). The principal mechanism accounting for gene mobility is horizontal gene transfer (HGT) (Doolittle, 1999; Ochman et al., 2000; Koonin et al., 2001; Nakamura et al., 2004; Jin et al., 2007) in which a group of genes can be transferred from a donor organism to recipient. Recent studies have shown that HGT stands out as the dominant factor in several important phenomena in bacterial evolution: adaptation to niches, development of antibiotic resistance, and pathogenicity. Even though HGT is an important factor in prokaryotic evolution, our knowledge on HGT is very limited, partly due to the lack of use of analytic tools and models in the field (Doolittle and Bapteste, 2007).

In this work, we extend the Evolvability theory to account for this less studied, yet very important, mode of evolution. In particular, we use the notion of population-based models where a population is evolving simultaneously and information is shared between members of this population. The model is inspired by the basic evolvability model and is extending it. The new model accommodates mechanism such as HGT where genetic information in the form of DNA is passed between individuals. While in a recent separate work (Snir and Yohay, 2018), we focused on the theoretical aspects of the newly defined model and showed that it provides an asymptotic acceleration in learning, here the emphasis is on more biological practical points. We first give the formal necessary definitions as required by the new extension. Subsequently, we use the conjunction function to model the process of acquiring a character or a property by an organism. Focusing on this important function class, we show experimental results regarding the new and existing models. Finally, we analyze real data in the form of developing virulence in Escherichia coli. We demonstrate that this function can be depicted by a monotone conjunction and compare between the models on this data. Our results, in the form of actual concrete times, give convincing evidence to the superiority of the HGT process over more conservative mechanisms, explaining the vastness of the gradually discovered world of mobile elements—the mobilome (Siefert, 2009).

2. Preliminaries

The new extension, which was first defined in our recent work (Snir and Yohay, 2018), relies on the existing theory of evolvability. We now give necessary definitions required for the extension. For the sake of compatibility with previous works, we tried to use original definitions from existing works in places where this was possible. In such cases, we give explicit reference to the appropriate work inside the definition.

2.1. The evolvability model

A description of the evolvability framework is necessary for our extension and is given hereby. For the full definition of the evolvability model, the reader is referred to the work of Valiant (2009).

We start with a notational comment. Throughout the article, we abuse notation \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$P - r$$ \end{document} to mean \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$P \backslash \left\{ r \right\} $$ \end{document} .

We assume a finite set of conditions organisms have to respond to. A condition may represent a certain disease, availability of food, or water. All the possible combinations of conditions are given by the set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$X = \left\{ {{x_1} , \ldots , {x_n}} \right\} $$ \end{document} . In this framework, each condition is represented as Boolean attribute with a low value of −1 and a high value of +1. The probability distribution D over X describes the relative frequency with which the various combinations of values for x_i are generated.

The functions discussed in this work are Boolean functions with domain X and possible outputs of −1 and +1. A concept class C over X is a set of Boolean functions. Suppose that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$f \in C$$ \end{document} is the hidden ideal function. The ideal function can be thought of as the organism that has the most desirable response to any set of conditions. The goal is to learn the ideal function and produce a hypothesis within computationally bounded resources that depend on a polynomial in n and on an accuracy parameter \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\varepsilon$$ \end{document} .

The hypothesis shall be viewed as a representation of a function since it should be represented concretely in the organism. In accordance with the function class, a representation class R is a set of representations, such that every \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r \in R$$ \end{document} is a Boolean function, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r:X \to \left\{ { - 1 , + 1} \right\} $$ \end{document} .

The goal of the evolvability learning algorithm is to evolve some representation into a hypothesis that gets arbitrary close to the ideal function, using evolutionary processes. The learning occurs throughout discrete generations.

2.2. Evolvability with HGT

We now define a model that captures the central mechanisms in the process of HGT.

The neighborhood function is the algorithm by which representations mutate across generations. We define a neighborhood function such that a representation can receive information (genes) from many different representations:

Definition 1 (HGT Neighborhood Function; Snir and Yohay, 2018). For polynomial \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$p \left( { \cdot , \cdot } \right)$$ \end{document} , a p-bounded HGT neighborhood function is a randomized Turing machine that takes as input a representation \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r \in R$$ \end{document} , a set of representations, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$P \prime \subset R$$ \end{document} , and a constant \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\varepsilon$$ \end{document} and outputs a multiset of representations \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$Neigh \left( {r , P \prime , \varepsilon } \right) \subseteq R$$ \end{document} . The running time of the Turing machine is bounded by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$p \left( {n , { \varepsilon ^{ - 1}}} \right)$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left\vert {Neigh \left( {r , P \prime , \varepsilon } \right) \,} \right\vert \le p \left( {n , { \varepsilon ^{ - 1}}} \right)$$ \end{document} . If \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$Neigh \left( {r , P \prime , \varepsilon } \right)$$ \end{document} is empty, it is interpreted as the representation r cannot continue to the next generation.

Remark 1. We have defined \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$Neigh{ \left( {r , P \prime , \varepsilon } \right) _{}}$$ \end{document} as a multiset since it can be populated by an algorithm that chooses to insert the same representation multiple times to the set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$Neigh \left( {r , P \prime , \varepsilon } \right)$$ \end{document} .

Thus, r is mutated according to the set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$P \prime$$ \end{document} . This models the process in which a genome (typically of a prokaryote) is receiving genes from other nearby genomes.

We now define the performance. The performance is used to give a quantitative measurement of the how well a representation approximates the ideal function.

Definition 2 (Performance; Valiant, 2009). The performance of a representation r with respect to target function f and distribution D is defined as:

\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} Per{f_{f , D}} \left( r \right) = { \mathbb{E}_D} \left[ {f \left( x \right) \cdot r \left( x \right) } \right] \in \left[ { - 1 , 1} \right] . \tag{1} \end{align*} \end{document}

The evolutionary algorithm will have access to an oracle that given a representation returns its estimated performance. We define the estimated performance according to Valiant's basic evolvability definition, with a slight modification: Instead of observing the sample size s, we observe the estimation error (noise) \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\tau$$ \end{document} . A conversion from s to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\tau$$ \end{document} can be carried out using Hoeffding–Chernoff bound.

Definition 3 (Estimated Performance). The estimated performance function takes as input a representation r and outputs \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\tau - Per{f_{f , D}} \left( r \right)$$ \end{document} , which satisfies \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left\vert { \tau - Per{f_{f , D}} \left( r \right) - Per{f_{f , D}} \left( r \right) } \right\vert \le \tau$$ \end{document} . We require that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \tau ^{ - 1}}$$ \end{document} is bounded by a polynomial in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$n , { \varepsilon ^{ - 1}}$$ \end{document} .

We now define the tolerance function. The tolerance function separates the mutations that performed good from the other mutations in relation to the current representation's performance.

Definition 4 (Tolerance Function; Valiant, 2009). A tolerance function t takes as input a representation \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r \in R$$ \end{document} and an accuracy parameter \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\varepsilon$$ \end{document} and outputs \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$t{ \left( {r , \varepsilon } \right) _{}} \in \left[ {0 , 1} \right]$$ \end{document} that is bounded above and below by two polynomially related polynomials. That is, there exist polynomials \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$tl \left( { \cdot , \cdot } \right) , \, \,tu \left( { \cdot , \cdot } \right)$$ \end{document} such that for every \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r \in R$$ \end{document} , n, and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\varepsilon$$ \end{document} , \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$1 / tu \left( {n , { \varepsilon ^{ - 1}}} \right) \le t \left( {r , \varepsilon } \right) \le 1 / tl \left( {n , { \varepsilon ^{ - 1}}} \right)$$ \end{document} and that there exists a constant a such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$tu \left( {n , { \varepsilon ^{ - 1}}} \right) \le { \left( {tl \left( {n , \, \,{ \varepsilon ^{ - 1}}} \right) } \right) ^a}$$ \end{document} . Furthermore, t can be computed in polynomial time in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$n , { \varepsilon ^{ - 1}}$$ \end{document} .

We define a probability function \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\rho \left( {r , \, \,r \prime , \, \, \varepsilon } \right)$$ \end{document} that returns the probability that r mutates into \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r \prime$$ \end{document} . It is required that the sum of the probabilities \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\rho \left( {r , \, \,r{ \rm{ \prime }} , \, \, \varepsilon } \right)$$ \end{document} over all \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r \prime$$ \end{document} is 1.

A selection rule Sel selects a (possibly random) mutations of the neighborhood function based on its estimated performance. In this work, we use the selection rule used by Valiant, which we denote by SelNB.

Definition 5 (Valiant, 2009). For an error parameter \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\varepsilon$$ \end{document} , a tolerance t, noise \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\tau$$ \end{document} , and probability function \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\rho$$ \end{document} , the selection rule SelNB is an algorithm that for any representation r, any population \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$P \prime$$ \end{document} , outputs a random variable \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r \prime$$ \end{document} determined as follows: 1.

Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$Ben{e_{t , \tau }} \left( {r , \, \,P \prime , \, \, \varepsilon } \right) = \left\{ {r \prime \in \, \,Neigh \left( {r , \, \,P \prime , \, \, \varepsilon } \right) \vert \tau - Per{f_{f , D}} \left( {r \prime } \right) \ge \tau - Per{f_{f , D}} \left( r \right) + t \left( {r , \, \, \varepsilon } \right) } \right\} $$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$Neu{t_{t , \tau }} \left( {r , \, \,P \prime , \, \, \varepsilon } \right) = \left\{ {r \prime \in Neigh \left( {r , P \prime , \, \, \varepsilon } \right) \vert \left\vert { \tau - Per{f_{f , D}} \left( {r \prime } \right) - \tau - Per{f_{f , D}} \left( r \right) } \right\vert < t \left( {r , \varepsilon } \right) } \right\} $$ \end{document} .

If \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$Ben{e_{t , \tau }} \left( {r , \, \,P \prime , \, \, \varepsilon } \right) \ne \O$$ \end{document} , output one from it according to the relative probability \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\rho \left( {r , r \prime , \varepsilon } \right) / \sum \nolimits_{r \prime\prime \in Ben{e_{t , \tau }} \left( {r , \,P \prime , \, \varepsilon } \right) } {{ \rm{ }} \rho \left( {r , \, \,r \prime\prime , \, \, \varepsilon } \right) }$$ \end{document} .

Otherwise, if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$Neu{t_{t , \tau }} \left( {r , \,P \prime , \, \varepsilon } \right) \ne \O$$ \end{document} , output one from it according to the relative probability \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\rho \left( {r , r \prime , \varepsilon } \right) / \sum \nolimits_{r \prime\prime \in Neu{t_{t , \tau }} \left( {r , \,P \prime , \, \varepsilon } \right) } {{ \rm{ }} \rho \left( {r , r \prime\prime , \varepsilon } \right) }$$ \end{document} .

Otherwise, output \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\bot$$ \end{document} .

Thus, SelNB chooses a beneficial mutation if one exists or otherwise chooses a neutral representation.

The notion of a population was suggested by Kanade (2011) to allow the process of recombination between individuals. Indeed, in an environment where information is shared between organisms, it is more natural to look at a set of representations across generations. Thus, we assume the existence of a finite population with polynomial size.

An HGT mutator (or evolutionary step) takes a population P_i to population \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${P_{i + 1}}$$ \end{document} at the next generation. This involves taking variants of representations in P_i using the neighborhood function and inserting them to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${P_{i + 1}}$$ \end{document} using the selection rule. The transition is completed when the size of the next population equals the size of the current population. Formally,

Definition 6 (Snir and Yohay, 2018). An HGT mutator takes as input a starting population \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${P_i} \subseteq R$$ \end{document} and using an HGT neighborhood function that defines \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$Neigh \left( {r , \, \,P \prime , \, \, \varepsilon } \right)$$ \end{document} for every \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r \in R , \,P \prime \subset R$$ \end{document} and a selection rule Sel outputs a population \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${P_{i + 1}}$$ \end{document} as follows: 1.

While \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left\vert {{P_{i + 1}}} \right\vert < \left\vert {{P_i}} \right\vert$$ \end{document}

2.1.

Select randomly \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r \in {P_i}$$ \end{document} .

2.2.

Consider the mutations \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$Neigh \left( {r , \, \,{P_i} - r , \, \varepsilon } \right)$$ \end{document} .

2.3.

Activate the selection rule function \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$Sel \left( {r , \, \,{P_i} - r , \, \, \varepsilon } \right)$$ \end{document} , which returns a representation \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r \prime$$ \end{document} .

2.4.

If \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r \prime \ne \bot$$ \end{document} , put \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r \prime$$ \end{document} in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${P_{i + 1}}$$ \end{document} .

Remark 2. Note that the same function \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r \in {P_i}$$ \end{document} can be chosen multiple times during the evolutionary step. This may seem unnatural because the same genome cannot mutate several times and still remain in the original population. We say that this is due to the process of prokaryotic replication. Prokaryotes divide very rapidly; their population may double itself in a single day. We assume that evolutionary processes take much longer than replication, and thus, we assume that replication may have occurred during an evolutionary step.

Definition 7 (Snir and Yohay, 2018). For a polynomial \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$p \left( { \cdot , \cdot } \right)$$ \end{document} , a p-bounded evolutionary algorithm consists of a representation class R, an HGT neighborhood function operator Neigh, a tolerance function t, a probability function \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\rho$$ \end{document} , and has access to a performance oracle \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\tau Per{f_{f , D}}_{}$$ \end{document} . An evolutionary algorithm starting with population P₀ is a sequence of evolutionary steps (activations of the mutator), which successively produce populations \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${P_0} , \, \,{P_1} , \, \,{P_2} \ldots .$$ \end{document} It is required that Neigh is p-bounded, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left\vert {{P_0}} \right\vert \le p \left( {n , { \varepsilon ^{ - 1}}} \right) \;{ \rm{and}} { \tau ^{ - 1}} \le p \left( {n , \, \,{ \varepsilon ^{ - 1}}} \right).$$ \end{document}

Remark 3. Note that basic evolvability is a special case where the population consists only of a single representation, that is, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$P = \left\{ r \right\} $$ \end{document} . In this case, neighborhood will be of the form \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$Neigh \left({ r , \O , \varepsilon }\right) $$ \end{document} , which is essentially equivalent to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$Neigh \left( {r ,\varepsilon } \right)$$ \end{document} in Valiant's model.

Finally, we define the notion of evolvability with HGT in g generations.

Definition 8 (Snir and Yohay, 2018). We say that a concept class C is evolvable with HGT with respect to distribution D over X in g generations, if for some polynomial \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$p \left( {n , \, \,{ \varepsilon ^{ - 1}}} \right)$$ \end{document} there exists a p-bounded evolutionary algorithm, that for every \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\varepsilon > { \kern 1pt} 0$$ \end{document} , from any starting population P₀ and for every target function \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$f \in C$$ \end{document} , with probability at least \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$1 - \varepsilon$$ \end{document} for some \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$k < g$$ \end{document} reaches a population P_k containing a member \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$r \in {P_k}$$ \end{document} such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$Per{f_{f , D}} \left( r \right) \ge 1 - \varepsilon$$ \end{document} .

In our recent work (Snir and Yohay, 2018), we have showed the equivalence between evolvability and evolvability with HGT, by proving the following straightforward theorem:

Theorem 1. A concept class C is evolvable with HGT extension if and only if it is evolvable.

The equivalence shows that the models can learn the same range of concept classes efficiently (i.e., within polynomially bounded resources). Nevertheless, different models can learn the same problem in different speed, that is, different number of generations. The main result of our previous work (Snir and Yohay, 2018) manifests that the HGT extension allows an acceleration in terms of the number of generations. This is performed using a general reduction from the parallel CSQ model (Correlational Statistical Query, a learning model that performs queries like PAC) that we define below.

2.3. Parallel CSQ models

We define a model for parallel correlational statistical-query learning with a \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\tau - CSQ$$ \end{document} oracle. The model was first introduced in Kanade's article. A parallel CSQ algorithm has a polynomial number of processors p. We assume that there is a common clock, which defines the parallel time steps. During every time step, each processor may ask a query from the oracle, perform polynomially bounded computation, and send a message that any other processor can read. The oracle answers all the queries in parallel.

Definition 9 (Parallel CSQ Learning; Kanade, 2011). A concept class C over an instance space X is \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( { \tau , \, \,T} \right)$$ \end{document} -parallel CSQ learnable using p processors under distribution D, if there exists a parallel CSQ algorithm that uses p processors and for every \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\varepsilon > 0$$ \end{document} and target function \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$f \in C$$ \end{document} , after at most T parallel steps and with access to a \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\tau - CSQ$$ \end{document} oracle, outputs a hypothesis h such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$Per{f_{f , D}} \left( h \right) \ge 1 - \varepsilon$$ \end{document} . Each query \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\varphi$$ \end{document} must be polynomially (in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$n , \, \,{ \varepsilon ^{ - 1}}$$ \end{document} ) evaluatable and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \tau ^{ - 1}}$$ \end{document} must be bounded by a polynomial in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$n , \, \,{ \varepsilon ^{ - 1}}$$ \end{document} . Each parallel step must be completed by each processor in polynomial time.

In our recent work, we have proved a theorem that shows the power of the HGT model using a general reduction from parallel CSQ model.

Theorem 2 (Snir and Yohay, 2018). Suppose concept class C is \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( { \tau , \, \,T} \right)$$ \end{document} -parallel CSQ learnable using p processors. Then, C is evolvable with HGT starting with an initialized population P₀ within polynomially bounded resources in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O \left( T \right)$$ \end{document} generations using the selection rule SelNB.

This theorem shows that from a theoretical perspective, the HGT model allows to learn in less generations than possible using the basic model. Next, we describe experiments we devised that compare between the different learning models. The experiments show the same trend.

3. Results

In this section, we show several implications of the theoretical results described in previous sections. We model a biological trait that depends on multiple parameters as a conjunction function and acquisition of that trait as learning of the function. Due to the importance of this class, we derived analytical results in a recent article (Snir and Yohay, 2018) and now strengthen these results with experiments. We run simulations in which the conjunctions concept class is learned and show that these results affirm our analytical results. We end this section by applying these models to real biological data regarding the development of pathogenicity in microbes.

3.1. The conjunction function and concept class

Let the sample space consist of n Boolean variables (literals), \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$X = { \{ - 1 , 1 \} ^n}$$ \end{document} . A conjunction function (Mendelson, 1997) (class) f is defined by a subset \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$S \subseteq X$$ \end{document} . Given a sample \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$x \in X$$ \end{document} , f outputs 1 if each literal in f is consistent with the literals of x. Otherwise, f outputs −1. The concept class of conjunctions is the set of all conjunctions, denoted by C.

The concept class of monotone conjunctions is the set of conjunction classes such that the classes do not contain a negated literal.

Conjunction is biologically relevant as many biological processes or characters can be seen as a result of the simultaneous existence of a set of genes and absence of another set (see, e.g., microbial pathogenicity in our real data part Section 3.3). The same also holds for an expression of a certain protein that is conditioned on the existence and absence of some other proteins (Alon, 2006).

The values \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$1 / - 1$$ \end{document} at index i of a sample indicate that the ith gene is expressed/not expressed. A conjunction function is a combination of genes (genome), where the presence/absence of the ith literal indicates the presence/absence of the ith gene. Thus, learning the ideal function (genome) can be viewed as acquiring/losing certain genes in the representations. The learning stops when a sufficiently close genome was found (i.e., the performance of a representation has an error rate of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\varepsilon$$ \end{document} ).

3.2. Simulation study

We conducted simulation study to illustrate the difference between the various models under realistic size problems. The processes (models) examined are as follows: the mutation process (i.e., evolvability), recombination, and HGT. As each such process uses another technique to adapt to the environment, we ask, how fast, in terms of generations, a given function is learned, under each such evolutionary process.

Roughly speaking, we can divide the models into two very distinct groups: individuum-based model, where only a single representation is examined, and population-based models, where a population of representations are generated, each generation and relations between them are enabled. Even though recombination and HGT are population-based, recombination allows merging only between two individuals, whereas HGT allows information sharing between the whole population. We will see that this variance makes a large difference in the results.

In reality, HGT is mandated by HGT rate that determines probability of HGT events. Therefore, the first experiment measures the effect of HGT rate on the speed of evolution. We model the HGT as a Poisson process (Grimmett and Stirzaker, 2001) operating on a genome through time (Galtier, 2007; Roch and Snir, 2012). This allows easy conversion from rate to event probability. We executed the HGT algorithm with HGT rate varies from \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${P_{HGT}} = 0$$ \end{document} to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${P_{HGT}} = 1$$ \end{document} . We then compared the results with the results from the other models.

In the second experiment, we examined the interplay between the two processes occurring in the population simultaneously. Underneath the population processes—recombination and HGT—an underlying mutation process operates individually on every element. We therefore set to test that interplay under the two population models. Specifically, we varied the underlying mutation factor while maintaining all other parameters constant, including the population parameters.

The third experiment deals with the role of the size of the population in learning. We start with some population and increase it up to a size of five times that starting population.

3.2.1. Learning and models description

We have conducted the experiments with three models: the basic evolvability model described by Valiant, evolvability with recombination as described by Kanade, and the model we described in Section 2.1, evolvability with HGT. We start by describing the common setup and goal of the models. Our overall goal is to draw a distinction between the three learning models. As the learning processes are computationally very heavy, we selected fairly small parameter values; however, the general trend is still reflected.

The parameters in the experiments are thus: The number of Boolean variables was set to 40 ( \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$n = 40$$ \end{document} ). Under this value, an exhaustive search for the ideal function will not be possible. We chose the approximation parameter \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\varepsilon$$ \end{document} to be \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${2^{ - 31}}$$ \end{document} guaranteeing that the performance of a random starting representation is low with high probability.^* Thus, if no starting representation has high performance, learning is performed. D was chosen to be the uniform distribution. Valiant (2009) proved that monotone conjunctions is evolvable and described an algorithm for evolving this concept class. The tolerance function and the noise of the performance oracle are derived from that algorithm.

A run of the experiment starts by choosing a random ideal function f and a representation r (or a population of such) and trying to learn f throughout generations. The next generation is obtained by applying the mutator (or recombinator) to the current generation.

The learning stops when at least one representation r in the current population satisfies \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$Per{f_{f , D}} \left( r \right) \ge 1 - \varepsilon$$ \end{document} . For completeness, a more detailed description of the models is given in the Appendix.

3.2.2. Experimental results

We now describe the experiments performed. In any experiment, the number of runs was set to 10 for any value of the independent parameter (x) and the average result (generations) is plotted.

Our first experiment focused on the effect of HGT on the speed of learning. Obviously, this parameter is effective only to the HGT model. In the population-based models, mutation factor was set to 0.1, so it does not interfere with the overlying processes recombination and HGT (in the basic evolvability model, mutation is the only process so we set it to 1). The results of the experiment are shown in Figure 1. With an HGT rate of 0.2 or higher, the HGT model outraces the other models. Actually, under HGT rate of 1, the model learns in almost third of the generations that took the recombination model. Alternatively, under HGT rate of 0, learning is confined only to natural mutation with a factor of 0.1, which explains why it is very slow, even slower than the basic evolvability model. We can therefore infer that HGT rate plays a major role in the learning process of the HGT model.

FIG. 1.

(a) Experimental results of the HGT effect on the HGT model. Note that in the case of recombination and the basic evolvability model, the HGT rate does not affect these models at all, and therefore, the value is constant. (b) The results of the experiment of the effect of an increasing mutation factor on recombination and HGT model. When the mutation factor is 0, the algorithm cannot always learn the ideal function so the number of generations is \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\infty$$ \end{document} . This is due to the fact that recombination and HGT do not introduce new variation to the population. HGT, horizontal gene transfer.

In the next experiment, we examined the role of the underlying mutation factor under the three models. For HGT, we considered two rates: 0.2 and 1. In the experiment, mutation factor varied from 0 to 1. The number of Boolean variables of the functions is set to 10 and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\varepsilon$$ \end{document} was set to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${2^{ - 8}}$$ \end{document} . The results appear in Figure 1. We comment that under no mutations (i.e., factor zero), there were runs where the models could not learn the ideal function, due to the fact that the models without natural mutation do not introduce new variation to the population. Under recombination, from 0.1 to 0.6, we can see a gradual decrease in the generations. However, around a mutation factor of 0.6, it has almost no effect on it. In the case of HGT with a rate of 1, we see that the mutation factor has almost no effect on the model as the overlying model introduces enough variation. However, under HGT rate of 0.2, the mutation factor has a large impact. A mutation factor of 1 makes the model seven times faster than under 0.1. Finally, as the two HGT curves meet, we hypothesize that under certain mutation rate, the HGT model is faster than recombination for any HGT rate.

Our final experiment examined the effect of population size on speed of learning under the two population models—recombination and HGT. We therefore varied population size from 100 up to 1000. The results (Fig. 2) show interestingly a constant decrease in learning time (generations) under both population models; however, HGT decreases faster than recombination.

FIG. 2.

Experimental results of the effect of the size of the population on the number of generations.

3.3. Real data analysis

In this section, we apply the same models from the previous section on real data. We chose to focus on the pathogenicity of the E. coli bacteria. The virulence of an organism is the degree of pathology caused by that organism. To use the evolvability framework, we need a quantitative trait of pathogenicity, which is why we focus on virulence in this section. A virulence gene is a gene whose existence in the genome of an organism affects its virulence. A genome is considered pathogenic if it has an appropriate virulence gene combination (Chapman et al., 2006).

We do not, however, claim that these models represent the processes exactly as they occur in nature. The use of real data in the rigorous framework of evolvability and the comparison between the models grants a realistic aspect to this framework and, in particular, to evolvability with HGT, and hence its importance.

We now show an example of how to deduce the Boolean variables from the genes: The pathogenic strain Enterotoxigenic E. coli was identified by Do et al. (2005) by carrying either the gene combination fedA, estII or faeG, estI, estII, eltA. First, we enumerate the genes \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${x_1} = fedA$$ \end{document} , \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${x_2} = estII$$ \end{document} , \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${x_3} = faeG$$ \end{document} , \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${x_4} = estI$$ \end{document} , \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${x_5} = eltA$$ \end{document} . Then, assuming there are no more virulence genes, we can model the virulence of the genome by the following conjunction: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${x_1}{\wedge}{x_2}{\wedge}{x_3}{\wedge}{x_4}{\wedge}{x_5}$$ \end{document} . Thus, the more virulence genes an organism has, the more virulent it becomes. Note that because we consider only the existence of genes, we can limit the concept class to be the class of monotone conjunctions.

3.3.1. Simulation of real data results

We compare between the power of two biological processes: the process of HGT and recombination.

Fifty-eight virulence genes were observed in the work of Chapman et al. (2006). The number of Boolean variables was set to 100, where 58 of them were randomly chosen to represent the virulence genes and their values were set to 1. The other variables were chosen randomly. A value of 1 in one of the other variables represents a virulence gene that has yet been discovered.

The size of the population is chosen to be 75, corresponding to the 75 E. coli isolates that were taken in the work of Chapman et al. (2006). The approximation parameter \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\varepsilon$$ \end{document} was chosen to be \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${2^{ - 70}}$$ \end{document} . We believe that this approximation of the ideal function is reasonable for a representation to be considered highly virulent.

An estimation of the HGT rate for E. coli showed that 17.6% of the genes have been transferred since its divergence from Salmonella lineage 100 million years ago (Lawrence and Ochman, 1998). We consider a single generation in our models as a million year and set the HGT and recombination rate to be 0.176% (A recombination rate of x signifies that if recombination does not occur, one of the two representations is chosen randomly).

Over a total of 20 runs, the recombination model learned in 256 generations average, and the HGT model learned in 35 generations average.

In conclusion, if evolution would have occurred according to our parameters, a highly virulent organism would have emerged in 35 million years using HGT process. If instead the recombination process would have taken place, the pathogenic organism would have emerged in 256 million years.

3.3.2. Comparison with Escherichia lineage

In this section, we try to measure how the result from the previous section compares with real data. The evolvability with HGT model yielded a 35 million years for a highly virulent pathogen to emerge. We have put this result alongside the divergence times in the evolutionary lineage of Escherichia (Walk et al., 2009). The evolutionary lineage is displayed in Figure 3. Interestingly, the result is in the same order of magnitude as the splits in the evolutionary lineage.

FIG. 3.

Evolutionary lineage of the Escherichia genus. The nodes indicate how long ago the divergence occurred in million years. The dot indicates the result that evolvability with HGT yielded: The emergence of a highly pathogenic organism, starting from the divergence from Salmonella.

4. Conclusions

In his seminal work from 2006 (Valiant, 2009), Leslie Valiant extended his celebrated PAC (Probably Approximately Correct) model (Valiant, 1984) to the biological world and denoted it evolvability. Evolvability quantifies the process of evolution in terms of computational learning power. Subsequently, Kanade (2011) extended evolvability to higher level organisms' reproduction by combining the mechanism of recombination. Nevertheless, to the best of our knowledge, no such extension to evolvability was suggested for prokaryotes. Prokaryotic evolution largely proceeds by exchanging DNA between unrelated organisms, a mechanism denoted HGT. It is mainly due to HGT that microbes adapt to new ecological conditions, develop resistance to antibiotics, and so forth. In this work, we define a conceptual model encompassing this phenomenon. The model is conceptual/mathematical and therefore is not limited to a specific biological phenomenon. Valiant's evolvability is a special case in this new model. The evolutionary advantage of the new model is by allowing (genetic) information sharing between individuals in an evolving population, similar to the recombination model.

While in a recent work, we have focused on the theoretical aspects of the newly suggested model, here the emphasis is on its biological application. Specifically, we focus at apparently a biologically relevant function—conjunction, modeling existence of an entity contingent on the presence of several other entities. We show that for conjunction, the new model achieves asymptotic acceleration in learning time over evolvability and recombination. We corroborate these findings in simulation where we use a randomized learning algorithm for conjunction under evolvability. We conclude with learning a real data function of virulence in the E. coli bacterium.

We believe that the importance of this model stems from the lag of application of rigorous computational learning tools to model evolution in this life domain. The comparison between several modes of real-life evolutionary mechanisms under a common ground, from a rigorous computational learning perspective, provides another explanation to the versatility of this increasingly discovered world.

There are several future directions to take from this work that we consider of interest. Conjunction may be relevant for the case discussed here, but other biological mechanisms may require other concept classes. This may give insight into these mechanisms. We think that evolvability is a powerful yet flexible tool and can be used extensively to analyze more real biological data, using the scheme described in this work. Finally, modeling more evolutionary phenomena with this framework is interesting both from the aspect of computer science and from the aspect of biology.

Footnotes

Acknowledgment

The authors wish to acknowledge the Israel Science Foundation (ISF) for its kind support in performing this research.

Author Disclosure Statement

The authors declare that no competing financial interests exist.

References

Alon

2006. An Introduction to Systems Biology: Design Principles of Biological Circuits. CRC Press.

Chapman

T.A.

, Wu

X.-Y.

, Barchia

, et al. 2006. Comparison of virulence gene profiles of Escherichia coli strains isolated from healthy and diarrheic swine. Appl. Environ. Microbiol. 72, 4782–4795.

Darwin

1859. On the Origin of Species. John Murray.

, Stephens

, Townsend

, et al. 2005. Rapid identification of virulence genes in enterotoxigenic Escherichia coli isolates associated with diarrhoea in queensland piggeries. Aust. Vet. J. 83, 293–299.

Doolittle

W.F.

1999. Phylogenetic classification and the universal tree. Science, 284, 2124–2128.

Doolittle

W.F.

, and Bapteste

2007. Pattern pluralism and the tree of life hypothesis. Proc. Natl. Acad. Sci. 104, 2043–2049.

Galtier

2007. A model of horizontal gene transfer and the bacterial phylogeny problem. Syst. Biol. 56, 633–642.

Gogarten

J.P.

, and Townsend

J.P.

2005. Horizontal gene transfer, genome innovation and evolution. Nat. Rev. Microbiol. 3, 679–687.

Grimmett

, and Stirzaker

2001. Probability and Random Processes. Oxford University Press.

10.

Jin

, Nakhleh

, Snir

, et al. 2007. Inferring phylogenetic networks by the maximum parsimony criterion: A case study. Mol. Biol. Evol. 24, 324–337.

11.

Kanade

2011. Evolution with recombination. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011. Palm Springs, CA, October 22–25, 2011, 837–846.

12.

Koonin

E.V.

, and Galperin

M.Y.

2002. Sequence–Evolution–Function: Computational Approaches in Comparative Genomics. Kluwer Academic Publishers, Norwell, MA.

13.

Koonin

E. V.

, Makarova

, and Aravind

2001. Horizontal gene transfer in prokaryotes—quantification and classification. Annu. Rev. Microbiol. 55, 709–742.

14.

Lawrence

J.G.

, and Ochman

1998. Molecular archaeology of the Escherichia coli genome. Proc. Natl. Acad. Sci. 95, 9413–9417.

15.

Mendelson

1997. Introduction to Mathematical Logic, 4th ed. Chapman and Hall.

16.

Nakamura

, Itoh

, Matsuda

, et al. 2004. Corrigendum: Biased biological functions of horizontally transferred genes in prokaryotic genomes. Nat. Genet. 36, 1126.

17.

Ochman

, Lawrence

J.G.

, and Groisman

E.A.

2000. Lateral gene transfer and the nature of bacterial innovation. Nature, 405, 299–304.

18.

Roch

, and Snir

2012. Recovering the tree-like trend of evolution despite extensive lateral genetic transfer: A probabilistic analysis. CoRR. abs/1206.3520.

19.

Siefert

J.L.

2009. Defining the mobilome. In Gogarten

, Gogarten

, and Olendzenski

, eds., Horizontal Gene Transfer: Genomes in Flux. Methods in Molecular Biology. Humana Press.

20.

Snir

, and Yohay

2018. Prokaryotic evolutionary mechanisms accelerate learning. Discrete Applied Math. (Accepted).

21.

Valiant

L.G.

1984. A theory of the learnable. In Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30–May 2, 1984, Washington, DC, 436–445.

22.

Valiant

L.G.

2006. Evolvability. Electr. Colloq. Comput. Compl. 13, 6100.

23.

Valiant

L.G.

2009. Evolvability. J. ACM, 56, 3:1–3:21.

24.

Walk

S.T.

, Alm

E.W.

, Gordon

D.M.

, et al. 2009. Cryptic lineages of the genus escherichia. Appl. Environ. Microbiol. 75, 6534–6544.