## 3 Phenotype Computation  
The main ideas behind efficient phenotype computation are (i) storing the progeny as genome segments and (ii) pre-computing the founder phenotype values for all possible segments, by adding up the contributions of each genotype marker within a segment. This is applicable when the phenotype is additive (or multiplicative), which is one of the fundamental and widely used models underlying phenotype computations [6]. Furthermore, popular whole genome prediction models, such as rrBLUP [13; 14], Bayes A [14], Bayes B [14], Bayes Cpi [15] and Lasso [16], utilize an additive phenotype model. The phenotype computation is specific to a given marker model, and the pre-computed  
Figure 4: Time requirements of selfing the result of a cross for 10 generations, while at each generation, applying selection after computing the phenotype values. Cumulative time taken for progeny generation and phenotype computation after each generation is shown. Figure 3: Average number of segments per one Morgan in a haploid during 500 generations in simulations of random mating populations. F is the number of individuals in the founder population, and N is the number of individuals in every subsequent population. The parents of each progeny are chosen at random (with replacement) from the previous generation. values apply only for the model for which they were computed. The phenotype contribution of each possible genome segment can be evaluated using the pre-computed cumulative sum (or product) of phenotype contributions, as explained below. An additive phenotype value for individual \(i\), \(\mathcal{P}_{i}=\sum_{j}^{M}g_{i,j}\beta_{j}+\alpha\), can be efficiently computed by adding up the independent pre-computed values for each segment in \(i\). Here, \(\beta_{j}\) and \(\alpha\) are given parameters of the phenotype model, and \(g_{i,j}\) is the genotype at marker \(j\) in individual \(i\). The additive nature of the phenotype, \(\mathcal{P}\), allows the phenotype computation to be defined as a sum over subsets of markers. In order to utilize this subdivision, one can pre-compute a table, \(V\), containing the phenotype value of each possible segment of the genome. In practice, the values can be stored as a cumulative sum from the first genotype marker to the last. For simplicity, assume here we have just two founder haploids, \(A\) and \(B\), for example, in the case where the founders fully homozygous, as is often encountered in plant breeding. The discussion below applies to any number of founders; only the dimensionality of the pre-computed tables may change. In the two-founder case, there are three possible founder combinations for each diploid segment: \(AA\), \(AB\), \(BB\). Therefore three pre-computed tables are needed: \(V_{AA}\), \(V_{AB}\) and \(V_{BB}\). Since, in the segment representation, we are dealing with genome segments instead of individual markers, we need to map the genome segment boundaries to the genotype markers, in order to efficiently index the pre-computed tables, \(V\). Let \(\varphi\) be a function that maps a genomic location, \(x\), onto the nearest genotype marker, \(s\), whose location is larger than \(x\). Given \(x\) and \(y\), \(x<y\), as two genetic positions in the haploid, we have \(s=\varphi(x)\) and \(t=\varphi(y)\). For example, the phenotype contribution, \(\mathcal{P}(s,t-1)\), for markers \(0<s<t\), corresponding to the genome segment from \(x\) to \(y\), where both haploids originate from founder \(A\), can be quickly computed as \(\mathcal{P}(s,t)=V_{AA}[t-1]-V_{AA}[s-1]\). The markers' genome locations can be represented as a sorted list of positions in a searchable data structure, enabling logarithmic time search for the marker closest to a given segment boundary. When computing the phenotype value of a genome from the segment representation, the indices of the first and last markers in each segment need to be determined, as well as the parental origins of the segment, in order to correctly index the pre-computed phenotype contribution tables, \(V\).