J. Anim Sci. 2006. 84:3212-3218. doi:10.2527/jas.2006-145
© 2006 American Society of Animal Science
An algorithm to compute optimal genetic contributions in selection programs with large numbers of candidates
D. Hinrichs*,1,
M. Wetten
and
T. H. E. Meuwissen*
* Department of Animal and Aquacultural Sciences, Norwegian University of Life Sciences;
and
Aqua Gen AS, 7462 Trondheim, Norway
 |
Abstract
|
|---|
A novel algorithm, OCSELECT, is presented for the calculation of optimal genetic contributions with a restricted rate of inbreeding when the number of selection candidates is very large. The calculation of optimal genetic contributions requires the relationship matrix between the candidates and its inverse. The relationship matrix was written as: A = ZApZ' + D, where Ap is the relationship matrix of the parents, D is a diagonal matrix of Mendelian sampling variances, and Z contains genetic contributions from parents to offspring. Therefore, A–1 = d–1 – d–1Z(Z'd–1Z + AP–1)–1 Z'd–1, requires only inversion of matrices of the size of the number of parents instead of the number of offspring. The new algorithm was compared with the software package GENCONT on a salmon data set containing 39,214 selection candidates and 45,846 pedigreed fish in total. Because GENCONT could not handle such a large data set, this data set was split into 19 smaller data sets. Both algorithms gave the same solution with respect to the genetic gain and very similar solutions with respect to the number of selected animals. The OCSELECT algorithm was able to calculate the optimal contributions for the complete data set of 39,214, and therefore no preselection of the 39,214 fish was necessary before entering the fish into the new optimal contribution selection procedure.
Key Words: genetic contribution • genetic gain • inbreeding • salmon breeding • optimal selection
|
INTRODUCTION
|
|---|
The main goal of breeding programs is to maximize genetic gain. However, the management of inbreeding is important, and therefore, selection methods have been designed that manage rates of inbreeding (Wray and Goddard, 1994
; Grundy et al., 1998). Avendaño et al. (2003) analyzed the genetic gain caused by the optimization of genetic contributions of selection candidates in a beef cattle and a sheep population. In addition, Kearney et al. (2004) studied inbreeding trends and the application of optimized selection in the UK Holstein population. Both studies (Avendaño et al., 2003; Kearney et al., 2004) concluded that optimized selection should be used for the management of inbreeding in practical breeding programs. However, current methods are slow, and therefore a faster method would be useful for a further implementation of optimized selection in practical breeding programs.
This paper presents a new algorithm for the calculation of optimal genetic contributions based on the methods of Meuwissen (1997) and Meuwissen and Sonesson (1998). This new algorithm, called OCSELECT, uses an alternative method to calculate the relationship between the selection candidates, reducing computational time, which is important especially when the number of candidates is large. The OCSELECT algorithm was tested on different data sets and the solutions where compared with those of the software package GENCONT (Meuwissen, 2002).
|
MATERIALS AND METHODS
|
|---|
Optimal Genetic Contributions to the Next Generation
In most breeding schemes the main goal is to maximize the genetic level of the next generation of animals, Gt+1. This could be written as
where ct is the vector of genetic contributions of the selection candidates and EBVt is the vector of the BLUP estimated breeding values of the candidates. Furthermore we know that the contributions within each sex sum to 
, which could be written as
 | [1] |
where Q is a known incidence matrix for sex. To control the future increase of inbreeding the optimum genetic contribution theory restricts the average coancestry between selected animals to
 | [2] |
where 
t+1 is set to [1 – (1 – 
F)t+1], with F being the desired rate of inbreeding.
Now the optimal ct that maximizes Gt+1 under constraints [1] and [2] is obtained by introducing 2 La Grangian multipliers, 
0 and , and maximizing the following objective function:
 | [3] |
 | [4] |
and
 | [5] |
A more detailed description of optimum genetic contribution selection and the derivation of equations for the 2 La Grangian multipliers is given by Meuwissen (1997). In addition, Meuwissen and Sonesson (1998) presented the extension of optimum contribution selection for breeding schemes with overlapping generations.
Algorithm To Calculate A–1
The calculation of the optimal genetic contribution of an animal to future generations requires the relationship between the selection candidates; i.e., the additive relationship matrix and its inverse (see Equations [3], [4], and [5]). If the number of selection candidates is large, especially the inversion of the relationship matrix requires substantial memory and computational time. Furthermore, the computational time does not increase linearly, but rather proportionally, to N3, where N is the number of selection candidates.
The relationship between 2 animals, i and j, is equal to
where Asisj is the relationship between the sire of i and the sire of j, Asidj is the relationship between the sire of i and the dam of j, Adisj is the relationship between the dam of i and the sire of j, and Adidj is the relationship between the dam of i and the dam of j. In addition the relationship of an animal with itself is
where 
is the average inbreeding of the parents si and di.
In matrix form these equations could be written as
 | [6] |
where Z is a matrix where element Zij is if j is parent of i and 0 otherwise, Ap is the relationship matrix of the parents, and D is a diagonal matrix with the Mendelian sampling variances on the diagonal; i.e., (1 – F). By use of the algebra of partitioned matrices, the inverse of A is equal to A–1 = d–1 – d–1Z (Z'd–1Z + AP–1)–1 Z' d–1. Because D is a diagonal matrix this matrix is easy to invert.
In Equation [6], the inverse of the relationship matrix between the parents is needed, which is a relatively small matrix in most breeding schemes where few parents are selected. Furthermore, AP–1 needs to be calculated only once, because even if the number of selection candidates is reduced due to the discarding of selection candidates with zero-contributions, the number of parents stays the same (although some may have no offspring). The inverse of (Z'd–1Z + AP–1) is of the same size as the number of parents, so it is fast to calculate, but it does change if the list of selection candidates becomes smaller because of the rejection of selection candidates with negative contributions (because Z changes). However, if the change is small; e.g., only 1 selection candidate gets rejected, the Sherman-Morrison formula can be used to calculate the new inverse of (Z'd–1Z + AP–1) from that of the previous iteration (Press et al., 1992).
Therefore, in the presented algorithm, we reject only 1 selection candidate per iteration (i.e., the selection candidate with the most negative contribution). This algorithm is expected to be more robust against rejecting animals with negative contribution that should have had a positive contribution in the ultimate solution, compared with algorithms that reject all negative contributions simultaneously (e.g., GENCONT). The actual setting up of A–1 is avoided as follows: in Equations [3], [4], and [5], we need terms including A–1, of the form A–1R, where R is a matrix to be multiplied with A–1. Now instead of setting up A–1, we compute d–1R – d–1Z (Z'd–1Z + AP–1)–1 Z'd–1R directly, where d–1 is easy to calculate because D is diagonal.
Data
The new algorithm was tested on salmon breeding data (discrete generations, large number of candidates) from practical selection schemes. In the fish-breeding program, all selection was to be based on optimum contribution selection, with no other objectives; e.g., marker genotypes.
The EBV were based on BW, measured at 8 months of age. The file of EBV contained 39,214 selection candidates from 226 sires and 227 dams.
For the comparison of GENCONT and OCSELECT, this data set was split into 19 smaller data sets. Each of the smaller data sets 1 to 18 contained 2,000 selection candidates, whereas smaller data set 19 contained 3,215 selection candidates. The smaller data sets were created by randomly allocating families to the subset until the total size of the subset exceeded 2,000 animals, in which case the remaining family members were allocated to subset 2, etc. In subset 19, the total size of the data set was not limited, resulting in 3,215 selection candidates for this subset. In all analyses with the smaller data sets, the acceptable rate of inbreeding was set at 0.005.
At first both programs should minimize the relationship between the selected animals. Further analyses were carried out with different restrictions on the minimal and maximal contributions that a selected animal could contribute to the next generation. Minimal contributions implied that the selected animals had to contribute at least this amount or they were not used at all. The minimal contributions were fixed at 0.0025 or 0.005%, and the maximal contributions were fixed at 1, 2, 3, 4, or 5%, respectively. So in total all 19 of the smaller data sets were analyzed with different combinations of restrictions at first with GENCONT and thereafter with OCSELECT.
The number of male and female selection candidates and the average breeding values and their standard deviations for the different smaller data sets and the whole data set are given in Table 1. The entire data set of 39,214 candidates was analyzed by OCSELECT only because GENCONT could not handle such a large data set. The maximum number of selection candidates GENCONT could handle was approximately 4,000; i.e., smaller data set 19 was close to the maximal number of selection candidates GENCONT could handle (Table 1). The pedigree file contained 45,846 animals, which descended from 589 sires and 703 dams. The number of offspring per sire ranged from 1 to 267 and from 1 to 315 for the dams, respectively.
View this table:
[in this window]
[in a new window]
|
Table 1. Number of male and female selection candidates and EBV for the smaller data sets and the complete data set
|
|
The results section of this paper is divided in 2 parts. Firstly, the results of the comparison of the 2 methods are presented. Secondly, the results of the analysis of the complete data set are presented. The GENCONT could not be run with the full data set because the number of selection candidates was too large. Hence no comparison between GENCONT and OCSELECT was performed using the full data set.
|
RESULTS
|
|---|
Comparison of OCSELECT and GENCONT
The average of the pairwise relationships between the selection candidates in smaller data set 1 was 0.04062 and the minimal reachable average pairwise relationship between the parents for the next generation was 0.03269. To reach this minimal relationship both programs suggest the selection of 733 males and 725 females. In smaller data set 19 the current relationship between the selection candidates was 0.05454. Both programs selected the same number of males and females (885 males and 901 females), and the minimal reachable relationship between the selected animals was 0.03367. This pattern was general in all data sets, and the minimum reachable relationship between the selected animals was lower than the current average relationship between the selection candidates. On average the difference was 0.01489.
After the minimization the 19 smaller data sets were analyzed with a restriction on the acceptable rate of inbreeding, which was equal to F = 0.005, but no constraints on minimum nonzero contribution (Cmin) or maximum contribution (Cmax). For smaller data set 1 both programs estimated a G of 16.19 and selected 61 males and 65 females. The G in smaller data set 19 was 17.67 and the selected number of animals was 44 males and 45 females. Also in the smaller data sets 2 to 18 OCSELECT and GENCONT gave exactly the same results with respect to G, the number of selected males, the number of selected females, and the estimated genetic contributions of the selection candidates.
Table 2 summarizes the comparison of the 2 algorithms, with application of constraints, using smaller data set 1, and Table 3 shows the results of the 2 programs using smaller data set 19. If there were any difference between the 2 methods, then the results between the brackets belong to GENCONT.
View this table:
[in this window]
[in a new window]
|
Table 2. Analysis of data set 1 with 2,000 selection candidates and differing restrictions on the minimal (Cmin) and maximal (Cmax) with respect to genetic gain (G), selected males (Sel.  ), and selected females (Sel.  )1,2,3
|
|
View this table:
[in this window]
[in a new window]
|
Table 3. Analysis of a data set 19 with 3,215 selection candidates and differing restrictions on the minimal (Cmin) and maximal (Cmax) with respect to genetic gain (G), selected males (Sel. ), and selected females (Sel. )1,2,3
|
|
Table 2
shows that a restriction on the maximal contribution has a higher impact on genetic gain than a restriction on the minimal contribution. Furthermore in 2 cases GENCONT could not satisfy the constraint (italic font in Table 2), whereas OCSELECT holds the constraint with all restrictions on the minimal or maximal contribution, or both, of a selection candidate.
The results summarized in Table 3 showed again that a restriction on the maximal contribution had a higher impact than a restriction on the minimal contribution. In addition Figure 1 shows the plotted EBV of the selected male candidates against the contributions without any restriction on minimal or maximal contributions. Figure 2 shows the impact of a restriction on minimal contribution of selected animals. There is little difference between Figures 1 and 2 except that some of the lowest contributions in Figure 1 have moved to zero in Figure 2. Figure 3 (Cmax = 0.01) and Figure 4 (Cmax = 0.05) are plots from analysis with a restriction on maximal contribution. In Figure 3 the Cmax constraint was so stringent that all animals had a contribution of 1% or no contribution at all. In Figure 4, the Cmax constraint was less stringent, and the highest contributions in Figure 1 are reduced here to 5%. All results presented in Figures 1 to 4 are based on OCSELECT analysis. Furthermore in smaller data set 19 in some cases (italic font in Table 3) both programs could not satisfy the constraint. However, in that case OCSELECT presents a solution with smaller differences between the constraint and the achieved relationship. This could also be observed in some cases in the smaller data sets 2 to 18 (not shown).
View larger version (5K):
[in this window]
[in a new window]
|
Figure 1. Association between EBV and optimized contribution without restrictions on minimal or maximal contributions (acceptable rate of inbreeding = 0.005; male selection candidates = 1,618; female selection candidates = 1,597).
|
|
View larger version (6K):
[in this window]
[in a new window]
|
Figure 2. Association between EBV and optimized contribution with restrictions on minimal contributions (Cmin = 0.005; acceptable rate of inbreeding = 0.005; male selection candidates = 1,618; female selection candidates = 1,597).
|
|
View larger version (5K):
[in this window]
[in a new window]
|
Figure 3. Association between EBV and optimized contribution with restrictions on maximal contributions (Cmax = 0.01; acceptable rate of inbreeding = 0.005; male selection candidates = 1,618; female selection candidates = 1,597).
|
|
View larger version (5K):
[in this window]
[in a new window]
|
Figure 4. Association between EBV and optimized contribution with restrictions on maximal contributions (Cmax = 0.05; acceptable rate of inbreeding = 0.005; male selection candidates = 1,618; female selection candidates = 1,597).
|
|
Generally, the results of the comparison between OCSELECT and GENCONT showed that if the programs hold the constraint, the solutions of both programs were nearly identical with respect to the genetic gain, the number of selected males, the number of selected females, and the contributions of the selected animals. However, in all cases when both programs could not hold the constraint OCSELECT gave a better solution than GENCONT and that in some cases OCSELECT could satisfy the constraint when GENCONT did not hold the constraint. Further in all analysis no case could be observed where GENCONT held the constraint and OCSELECT could not satisfy the constraint. In all analyzed smaller data sets the highest genetic gain was achieved without any restrictions on the minimal or maximal contributions of the selected animals.
Calculation of Optimal Genetic Contributions for All 39,214 Candidates
The current relationship between the selection candidates in the complete salmon data set was 0.04223 and the minimal reachable relationship between the selected animals was 0.03055. To reach this relationship OCSELECT selected 10,142 males and 10,179 females, and the computational time for the minimization of inbreeding was 7 minutes.
Using the minimal pairwise relationship as a base and assigning an acceptable rate of inbreeding F = 0.005, the pairwise relationship of the parents of the next generation was restricted to
Using this constraint on the average pairwise relationship of the parents of the next generation OCSELECT estimated a genetic gain of 19.63 and 159 males and 140 females were selected (23 min computational time on a PC). This result suggests that it is possible to achieve genetic gain and reduce the average population relationship at the same time.
Table 4 shows the results of the calculation for the complete salmon data set with different restrictions on the minimal contribution, maximal contribution, or both. Also with the complete salmon data set a restriction on the maximal contribution of the selected animals has a higher impact than a restriction on the minimal contribution of a selected animal, with respect to the genetic gain and the computational time. As expected, the highest genetic gain was achieved again without any restrictions on the contributions of the selected animals.
View this table:
[in this window]
[in a new window]
|
Table 4. Genetic gain (G), selected males (Sel. ), selected females (Sel. ), and computational time (Min) for the complete data set (39,214 selection candidates) with differing restrictions on minimal (Cmin) or maximal (Cmax) contributions (or both) for selected animals1,2
|
|
|
DISCUSSION
|
|---|
In this paper a novel algorithm was presented to calculate optimal genetic contributions with a restricted rate of inbreeding or contributions that minimize the rate of inbreeding. Compared with previous published methods, e.g., Meuwissen (2002), we found that our method was faster and that it is possible to handle a much larger number of selection candidates simultaneously. Furthermore we found that the new method is very flexible with different restrictions on minimal contributions, maximal contributions, or both of a selected animal. The main advantages of our method are 1) a fast algorithm that avoids calculating A–1, and 2) the 1 by 1 rejection of candidates with negative contributions, which is a more conservative procedure than deleting several animals with of negative contributions simultaneously.
The calculation of optimal genetic contributions OCSELECT could be divided in 2 steps. The first step is the preparation of the Ap, AP–1, and the Z matrices, and in the second step the optimal genetic contributions are calculated in an iterative process, where negative contributions are excluded 1 by 1.
Previously presented algorithms used the additive relationship matrix between the selection candidates and the inverse of this matrix, which is computationally infeasible if the number of selection candidates is large, e.g., in fish breeding it is common to have between 10,000 and 100,000 selection candidates per selection round. In particular the inversion of the additive relationship matrix required a lot of computational time, and this time increases to the power 3 with the number of selection candidates. Henderson (1976) and Quaas (1976) derived fast methods to calculate the inverse of very large A matrices, but these methods assume that the A–1 of all animals in the pedigree is needed, whereas in optimum contribution selection the A–1 of a list of selection candidates is needed. In addition this matrix had to be calculated and thereafter inverted several times due to the fact that the candidates with negative contributions need to be removed from the solution.
In this paper we used the relationship matrix between the parents, AP, and its inverse AP–1. Our results showed that it is possible to use the additive relationship between the parents of the selection candidates to calculate the optimal genetic contribution of the selection candidates to the next generation. The main advantages of using the relationship between the parents, instead of the relationship between the selection candidates are that this matrix has a smaller dimension and that it is not necessary to recalculate this matrix because in most cases the number of parents did not change with a decreasing number of selection candidates, and otherwise some of the parents simply did not have any offspring. It should be noted that Equation [6] assumes that all selection candidates come from the same generation. However, in practical breeding schemes it can occur that parents as well as offspring are selection candidates. This is accommodated in Equation [6] by having such parents of candidates directly included in AP, and setting their diagonal element in D to a small positive value (e.g., 10–6). Therefore it is possible to use OCSELECT also in case of overlapping generations.
Alternatively, genetic and evolutionary optimization algorithms have been proposed to calculate optimal contributions (Kinghorn et al., 2002). These algorithms are general optimization algorithms and thus are very flexible in the choice of the objective function and the constraints that can be applied. However, these algorithms do not take advantage of the structure of the optimization problem and thus will have difficulty when applied to problems of high dimension, such as was the case here. Thus, it is expected that methods that take advantage of the structure of the solution are faster than general optimization algorithms when the number of candidates becomes very large, e.g., 39,214 as in the salmon breeding program.
The disadvantage of deleting all candidates with a negative contribution simultaneously is that there is no guarantee that all these candidates will have a negative contribution in the ultimate optimal solution, i.e., some of the deleted candidates might have a positive optimal contribution, but this solution will not be found by GENCONT once the animal has been removed. Therefore OCSELECT is safer against rejecting animals with negative contributions that should have had a positive contribution in the ultimate solution. This resulted in some situations where GENCONT could not achieve the constraint because it had removed too many individuals from the solution vector in a previous iteration (Tables 2 and 3).
The only way to be sure of obtaining an optimal solution is simultaneous handling of all constraints, including Cmax and Cmin. In view of the size of the optimization problem considered, such an approach was not attempted. Instead a heuristic approach was taken, namely, include the constraints that are violated by the optimal solution in an iterative manner. This probably results in a close to optimal solution, which is confirmed by the current result that different strategies of including the constraints (OCSELECT and GENCONT) led to the same or very similar solutions in the majority of the situations investigated in Tables 2 and 3. The optimality of the solution may be improved (but not guaranteed) by some heuristic that will permit reentry of excluded candidates. It is however not clear what the criterion for reentry should be. Once an animal is excluded, it is not included in A–1, and thus Equation [3] cannot be evaluated for such an animal in order to check what its contribution should have been. In practical breeding schemes, many practical constraints need to be considered involving mating logistics and possible migration across farms. Hence, the solutions presented by OCSELECT are expected to serve only as targets to aim at while accommodating such constraints.
Figures 1 and 2 showed that there was only a small effect when the analysis includes a restriction on the minimal nonzero contributions of selection candidates. In practical situations it could be important that the algorithm can deal with minimal nonzero contributions because this ensures that a selected animal must be used at least for 1 mating. The reasons for the higher impact of maximal contributions (Figures 3 and 4) are that 1) the contribution of the highest EBV animals are reduced, and 2) with stringent restrictions on Cmax, more animals need to be selected than otherwise would have been the case.
Genetic gains increased with the number of selection candidates (Table 2 and Table 3) and the highest genetic gain was achieved when the contribution of all selection candidates were optimized simultaneously (Table 4), which is in agreement with the results of computer simulations of Sonesson (2005). These computer simulations also showed that selection with a restriction on the rate of inbreeding is essential for populations with large numbers of candidates and large family sizes, such as fish populations, because the selected parents may otherwise come from very few families. Therefore the method presented in this paper is a further step for the implementation of optimum contribution selection on practical breeding schemes because this method makes it possible to treat all animals in large selection schemes as selection candidates simultaneously, and we do not need to preselect the candidates (e.g., on EBV) before entering them into the optimal contribution selection procedure.
|
IMPLICATIONS
|
|---|
This paper presents a novel algorithm for the calculation of optimal genetic contributions. The novel algorithm uses the relationship matrix of the parents instead of that of the selection candidates because of its smaller size. The latter makes the calculation of optimum contributions for much larger data sets possible. The new method gives similar results with respect to genetic gain, selected males, and selected females than a previously published method. Most importantly, the new method could handle much larger data sets. In an example the optimal contributions of 39,214 candidates were calculated, and therefore no preselection of candidates was necessary before calculating optimal contributions.
1 Corresponding author: dirk.hinrichs{at}umb.no
Received for publication March 15, 2006.
Accepted for publication May 26, 2006.
|
LITERATURE CITED
|
|---|
Avendaño, S., B. Villanueva, and J. A. Woolliams. 2003. Expected increases in genetic merit from using optimized contributions in two livestock populations of beef cattle and sheep. J. Anim. Sci. 81:2964–2975.[Abstract/Free Full Text]
Grundy, B., B. Villanueva, and J. A. Woolliams. 1998. Dynamic selection procedures for constrained inbreeding and their consequences for pedigree development. Genet. Res. 72:159–168.[CrossRef]
Henderson, C. R. 1976. A simple method for computing the inverse of a numerator relationship matrix used in prediction of breeding values. Biometrics 32:69–83.[CrossRef]
Kearney, J. F., E. Wall, B. Villanueva, and M. P. Coffey. 2004. Inbreeding trends and application of optimized selection in the UK Holstein population. J. Dairy Sci. 87:3503–3509.[Abstract/Free Full Text]
Kinghorn, B. P., S. A. Meszaros, and R. D. Vagg. 2002. Dynamic tactical decision systems for animal breeding. Proc. 7th World Congr. Genet. Applied to Livest. Prod., Montpellier, France 33:179–186.
Meuwissen, T. H. E. 1997. Maximizing the response of selection with a predefined rate of inbreeding. J. Anim. Sci. 75:934–940.[Abstract/Free Full Text]
Meuwissen, T. H. E. 2002. GENCONT: An operational tool for controlling inbreeding in selection and conservation schemes. Proc. 7th World Congr. Genet. Applied to Livest. Prod., Montpellier, France. 33:769–770.
Meuwissen, T. H. E., and A. K. Sonesson. 1998. Maximizing the response of selection with predefined rate of inbreeding: Overlapping generations. J. Anim. Sci. 76:2575–2583.[Abstract/Free Full Text]
Press, W. H., S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery. 1992. Numerical Recipes. 2nd ed. Cambridge Univ. Press, Cambridge, UK.
Quaas, R. L. 1976. Computing the diagonal elements of a large numerator relationship matrix. Biometrics 32:949–953.[CrossRef]
Sonesson, A. 2005. A combination of walk-back and optimum contribution selection in fish: A simulation study. Genet. Sel. Evol. 37:587–599.[CrossRef][Medline]
Wray, N. R., and M. E. Goddard. 1994. Increasing long term response to selection. Genet. Sel. Evol. 26:431–459.
Top
Abstract
INTRODUCTION
