Efficient computation of the inverse of gametic relationship matrix for a marked QTL

Best linear unbiased prediction of genetic merits for a marked quantitative trait locus (QTL) using mixed model methodology includes the inverse of conditional gametic relationship matrix (G^-1) for a marked QTL. When accounting for inbreeding, the conditional gametic relationships between two parents of individuals for a marked QTL are necessary to build G^-1 directly. Up to now, the tabular method and its adaptations have been used to compute these relationships. In the present paper, an indirect method was implemented at the gametic level to compute these few relationships. Simulation results showed that the indirect method can perform faster with significantly less storage requirements than adaptation of the tabular method. The efficiency of the indirect method was mainly due to the use of the sparseness of G^-1. The indirect method can also be applied to construct an approximate G^-1 for populations with incomplete marker data, providing approximate probabilities of descent for QTL alleles for individuals with incomplete marker data.     

Identification of gametes and treatment of linear dependencies in the gametic QTL-relationship matrix and its inverse

The estimation of gametic effects via marker-assisted BLUP requires the inverse of the conditional gametic relationship matrix G. Both gametes of each animal can either be identified (distinguished) by markers or by parental origin. By example, it was shown that the conditional gametic relationship matrix is not unique but depends on the mode of gamete identification. The sum of both gametic effects of each animal – and therefore its estimated breeding value – remains however unaffected. A previously known algorithm for setting up the inverse of G was generalized in order to eliminate the dependencies between columns and rows of G. In the presence of dependencies the rank of G also depends on the mode of gamete identification. A unique transformation of estimates of QTL genotypic effects into QTL gametic effects was proven to be impossible. The properties of both modes of gamete identification in the fields of application are discussed.     

A recursive procedure to compute the gametic relationship matrix and its inverse for marked QTL clusters

Recently, a variety of mixed linear models have been proposed for marker-assisted prediction of the effects of quantitative trait loci (QTLs) in outbred populations of animals. One of them addresses the effects of a cluster of linked QTLs, or those of a particular chromosomal segment, marked by DNA marker(s) and requires that the inverse of the corresponding gametic relationship matrix whose elements are the conditional expected values of the identity-by-descent (IBD) proportions between gametes for individuals be evaluated. Here, for a model of this type, utilizing the property of the IBD set and using the information on the joint gametogenesis processes at the flanking marker loci, we present a recursive method to systematically calculate the elements of the gametic relationship matrix and its inverse. A numerical example is given to illustrate the proposed computing procedure.     

A model for marker-assisted selection among single crosses with multiple genetic markers

 Trait means of marker genotypes are often inconsistent across experiments, thereby hindering the use of regression techniques in marker-assisted selection. Best linear unbiased prediction based on trait and marker data (TM-BLUP) does not require prior information on the mean effects associated with specific marker genotypes and, consequently, may be useful in applied breeding programs. The objective of this paper is to present a flanking-marker, TM-BLUP model that is applicable to interpopulation single crosses that characterize maize (Zea mays L.) breeding programs. The performance of a single cross is modeled as the sum of testcross additive and dominance effects at unmarked quantitative trait loci (QTL) and at marked QTL (MQTL). The TM-BLUP model requires information on the recombination frequencies between flanking markers and the MQTL and on MQTL variances. A tabular method is presented for calculating the conditional probability that MQTL alleles in two inbreds are identical by descent given the observed marker genotypes (G ^k _obs) at the kth MQTL. Information on identity by descent of MQTL alleles can then be used to calculate the conditional covariance of MQTL effects between single crosses given G ^k _obs. The inverse of the covariance matrix for dominance effects at unmarked QTL and MQTL can be written directly from the inverse of the covariance matrices of the corresponding testcross additive effects. In practice, the computations required in TM-BLUP may be prohibitive. The computational requirements may be reduced with simplified TM-BLUP models wherein dominance effects at MQTL are excluded, only the single crosses that have been tested are included, or information is pooled across several MQTL. Received: 22 June 1997 / Accepted: 25 February 1998     

Inclusion of genetically identical animals to a numerator relationship matrix and modification of its inverse

In the field of animal breeding, estimation of genetic parameters and prediction of breeding values are routinely conducted by analyzing quantitative traits. Using an animal model and including the direct inverse of a numerator relationship matrix (NRM) into a mixed model has made these analyses possible. However, a method including a genetically identical animal (GIA) in NRM if genetic relationships between pairs of GIAs are not perfect, is still lacking. Here, we describe a method to incorporate GIAs into NRM using a K matrix in which diagonal elements are set to 1.0, off-diagonal elements between pairs of GIAs to (1-x) and the other elements to 0, where x is a constant less than 0.05. The inverse of the K matrix is then calculated directly by a simple formula. Thus, the inverse of the NRM is calculated by the products of the lower triangular matrix that identifies the parents of each individual, its transpose matrix, the inverse of the K matrix and the inverse of diagonal matrix D, in which the diagonal elements comprise a number of known parents and their inbreeding coefficients. The computing method is adaptable to the analysis of a data set including pairs of GIAs with imperfect relationships.     

Inbreeding in populations with overlapping generations

An inbreeding matrix is defined for populations with overlapping generations. In the short term it can be expressed in terms of a matrix specifying the passage of genes between the different age groups (and sexes) and a diagonal matrix whose elements depend on the number of individuals in each age group. Formulae for the inbreeding effective number are derived using matrix theory. A comparison is made between the inbreeding coefficients predicted by this theory and those obtained by assuming a uniform rate of inbreeding from the outset, and these in turn are compared with the exact inbreeding coefficients.     

Derivation of single-locus relationship coefficients conditional on marker information

The coefficient of relationship is defined as the correlation between the additive genetic values of two individuals. This coefficient can be defined specifically for a single quantitative trait locus (QTL) and may deviate considerably from the overall expectation if it is taken conditional on information from linked marker loci. Conditional halfsib correlations are derived under a simple genetic model with a biallelic QTL linked to a biallelic marker locus. The conditional relationship coefficients are shown to depend on the recombination rate between the marker and the QTL and the population frequency of the marker alleles, but not on parameters of the QTL, i.e. number and frequency of QTL alleles, degree of dominance etc., nor on the (usually unknown) QTL genotype of the sire. Extensions to less simplified cases (multiple alleles at the marker locus and the QTL, two marker loci flanking the QTL) are given. For arbitrary pedigrees, conditional relationship coefficients can also be derived from the conditional gametic covariance matrix suggested by Fernando and Grossman (1989). The connection of these two approaches is discussed. The conditional relationship coefficient can be used for marker-assisted genetic evaluation as well as for the detection of QTL and the estimation of their effects.     

An efficient method of computing the numerator relationship matrix and its inverse matrix with inbreeding for large sets of animals

Summary The numerator relationship matrix describes the genetic relationships between individuals of a population. Its inverse is used for the prediction of breeding values, as outlined by Henderson (1975a).For large populations, the recursive method commonly used is difficult to apply because of the size of the relationship matrix. Recently Henderson (1975b) derived a method which allows computing the inverse of the numerator relationship matrix itself for a large number of animals, provided the population is non-inbred. The method presented here is an extension of Henderson's method to allow for inbreeding with large number of animals. It takes inbreeding into account and computes the numerator relationship matrix as well as its inverse. The method is particularly efficient in computer storage in that it allows handling of sets of animals larger than 5000 animals, and is almost as fast as the recursive method.     

A novel recursive algorithm for the calculation of the detailed identity coefficients

Background

A recursive algorithm to calculate the fifteen detailed coefficients of identity is introduced. Previous recursive procedures based on the generalized coefficients of kinship provided the detailed coefficients of identity under the assumption that the two individuals were not an ancestor of each other.

Findings

By using gametic relationships to include three, four or two pairs of gametes, we can obtain these coefficients for any pair of individuals. We have developed a novel linear transformation that allows for the calculation of pairwise detailed identity coefficients for any pedigree given the gametic relationships. We illustrate the procedure using the well-known pedigree of Julio and Mencha, which contains 20 Jicaque Indians of Honduras, to calculate their detailed coefficients.

Conclusions

The proposed algorithm can be used to calculate the detailed identity coefficients of two or more individuals with any pedigree relationship.     

Variance of prediction error with mixed model equations when relationships are ignored

Summary Formulas are presented to illustrate the calculation of correct variances of prediction error (PEV) and the correlation between true and predicted values (r_TI) when the incorrect variance-covariance matrix for the random effects is used in mixed-model equations (MME). The example with progeny records of highly related and inbred sires showed that PEV were underestimated from the diagonals of the inverse of the coefficient matrix of the MME when sires were assumed unrelated and not inbred and were overestimated when relationships among sires were calculated with Henderson's simple rules for the inverse of the numerator relationship matrix, A^-1, which do not consider inbreeding. When Quaas' rules for A^-1, which do consider inbreeding, are used, the correct PEV are obtained. In the example, calculations of r_TI from the diagonals of the inverse of the coefficient matrix were too large when relationships and inbreeding were ignored and were obviously wrong when the approximation to the numerator relationship matrix, A, was based on the simple rules for calculating A^-1. If the correct A is used in the MME, the calculation of r_TI may be incorrect if inbreeding of the evaluated individual is not considered. If inbreeding is known, adjustment for inbreeding is easy for calculation of r_TI.Published as paper no. 9947, Journal Ser, Nebraska Agric Res Div, University of Nebraska, Lincoln, Neb.     

The full EM algorithm for the MLEs of QTL effects and positions and their estimated variances in multiple-interval mapping

The advent of complete genetic linkage maps of DNA markers has made systematic studies of mapping quantitative trait loci (QTL) in experimental organisms feasible. The method of multiple-interval mapping provides an appropriate way for mapping QTL using genetic markers. However, efficient algorithms for the computation involved remain to be developed. In this article, a full EM algorithm for the simultaneous computation of the MLEs of QTL effects and positions is developed. EM-based formulas are derived for computing the observed Fisher information matrix. The full EM algorithm is compared with an ECM algorithm developed by Kao and Zeng (1997, Biometrics 53, 653-665). The validity of the inverted observed Fisher information matrix as an estimate of the variance matrix of the MLEs is demonstrated by a simulation study.     

Inbreeding depression in intra-provenance crosses driven by founder relatedness in white spruce

Genetic means for height growth differed between intra- and inter-provenance crosses, which we hypothesized was due partly to unidentified relatedness among intra-provenance base parents resulting in mild inbreeding and inbreeding depression among their offspring. A dense array of 5,844 single nucleotide polymorphisms was used to directly construct a genomic relationship matrix (G) that had four elements ranging from 0.17 to 0.24, between five intra-provenance base parents. Adjusting the numerator relationship matrix for this relatedness among base parents produced inbreeding coefficients of F _i ≈ 0.1 in their offspring, which displayed depressed height growth. Accounting for inbreeding level as a covariate in a mixed model decreased grossly overestimated (up to 2 ×) dominance variance in models without the covariate adjustment. Height growth decreased 39 cm (～ 6 %) for every 0.1 increase in F _i .     

Efficient path-based computations on pedigree graphs with compact encodings

A pedigree is a diagram of family relationships, and it is often used to determine the mode of inheritance (dominant, recessive, etc.) of genetic diseases. Along with rapidly growing knowledge of genetics and accumulation of genealogy information, pedigree data is becoming increasingly important. In large pedigree graphs, path-based methods for efficiently computing genealogical measurements, such as inbreeding and kinship coefficients of individuals, depend on efficient identification and processing of paths. In this paper, we propose a new compact path encoding scheme on large pedigrees, accompanied by an efficient algorithm for identifying paths. We demonstrate the utilization of our proposed method by applying it to the inbreeding coefficient computation. We present time and space complexity analysis, and also manifest the efficiency of our method for evaluating inbreeding coefficients as compared to previous methods by experimental results using pedigree graphs with real and synthetic data. Both theoretical and experimental results demonstrate that our method is more scalable and efficient than previous methods in terms of time and space requirements.     

A numerical solution to the equilibria of the two-locus two-allele selection model.

Examination of the equilibria of the standard two-locus two-allele selection model leads to the construction of a polynomial with coefficients derived from selective values in the genotypic fitness matrix. This polynomial can be partially factored algebraically and numerical techniques are available to extract the roots of the remainder. Each root provides a possible value of the disequilibrium coefficient and the gametic frequencies at equilibrium, and these can be readily checked for stability.     

Minimal Increase Network Coding for Dynamic Networks

Because of the mobility, computing power and changeable topology of dynamic networks, it is difficult for random linear network coding (RLNC) in static networks to satisfy the requirements of dynamic networks. To alleviate this problem, a minimal increase network coding (MINC) algorithm is proposed. By identifying the nonzero elements of an encoding vector, it selects blocks to be encoded on the basis of relationship between the nonzero elements that the controls changes in the degrees of the blocks; then, the encoding time is shortened in a dynamic network. The results of simulations show that, compared with existing encoding algorithms, the MINC algorithm provides reduced computational complexity of encoding and an increased probability of delivery.     

Inexpensive Computation of the Inverse of the Genomic Relationship Matrix in Populations with Small Effective Population Size

Many computations with SNP data including genomic evaluation, parameter estimation, and genome-wide association studies use an inverse of the genomic relationship matrix. The cost of a regular inversion is cubic and is prohibitively expensive for large matrices. Recent studies in cattle demonstrated that the inverse can be computed in almost linear time by recursion on any subset of ∼10,000 individuals. The purpose of this study is to present a theory of why such a recursion works and its implication for other populations. Assume that, because of a small effective population size, the additive information in a genotyped population has a small dimensionality, even with a very large number of SNP markers. That dimensionality is visible as a limited number of effective SNP effects, independent chromosome segments, or the rank of the genomic relationship matrix. Decompose a population arbitrarily into core and noncore individuals, with the number of core individuals equal to that dimensionality. Then, breeding values of noncore individuals can be derived by recursions on breeding values of core individuals, with coefficients of the recursion computed from the genomic relationship matrix. A resulting algorithm for the inversion called “algorithm for proven and young” (APY) has a linear computing and memory cost for noncore animals. Noninfinitesimal genetic architecture can be accommodated through a trait-specific genomic relationship matrix, possibly derived from Bayesian regressions. For populations with small effective population size, the inverse of the genomic relationship matrix can be computed inexpensively for a very large number of genotyped individuals.     

An efficient variance component approach implementing an average information REML suitable for combined LD and linkage mapping with a general complex pedigree

Variance component (VC) approaches based on restricted maximum likelihood (REML) have been used as an attractive method for positioning of quantitative trait loci (QTL). Linkage disequilibrium (LD) information can be easily implemented in the covariance structure among QTL effects (e.g. genotype relationship matrix) and mapping resolution appears to be high. Because of the use of LD information, the covariance structure becomes much richer and denser compared to the use of linkage information alone. This makes an average information (AI) REML algorithm based on mixed model equations and sparse matrix techniques less useful. In addition, (near-) singularity problems often occur with high marker densities, which is common in fine-mapping, causing numerical problems in AIREML based on mixed model equations. The present study investigates the direct use of the variance covariance matrix of all observations in AIREML for LD mapping with a general complex pedigree. The method presented is more efficient than the usual approach based on mixed model equations and robust to numerical problems caused by near-singularity due to closely linked markers. It is also feasible to fit multiple QTL simultaneously in the proposed method whereas this would drastically increase computing time when using mixed model equation-based methods.     

A spectral theory for Wright’s inbreeding coefficients and related quantities

Wright’s inbreeding coefficient, F_ST, is a fundamental measure in population genetics. Assuming a predefined population subdivision, this statistic is classically used to evaluate population structure at a given genomic locus. With large numbers of loci, unsupervised approaches such as principal component analysis (PCA) have, however, become prominent in recent analyses of population structure. In this study, we describe the relationships between Wright’s inbreeding coefficients and PCA for a model of K discrete populations. Our theory provides an equivalent definition of F_ST based on the decomposition of the genotype matrix into between and within-population matrices. The average value of Wright’s F_ST over all loci included in the genotype matrix can be obtained from the PCA of the between-population matrix. Assuming that a separation condition is fulfilled and for reasonably large data sets, this value of F_ST approximates the proportion of genetic variation explained by the first (K − 1) principal components accurately. The new definition of F_ST is useful for computing inbreeding coefficients from surrogate genotypes, for example, obtained after correction of experimental artifacts or after removing adaptive genetic variation associated with environmental variables. The relationships between inbreeding coefficients and the spectrum of the genotype matrix not only allow interpretations of PCA results in terms of population genetic concepts but extend those concepts to population genetic analyses accounting for temporal, geographical and environmental contexts.     

Descent measures for two loci with some applications

For any four genes, two at each of two loci, in a population, a 15 component descent measure has been introduced. These components are the probabilities of the 15 possible arrangements on a set of initial gametes of those genes of which the four of interest are copies. Since identity by descent of genes is equivalent to their being copies of a single gene on an initial gamete, descent measures have inbreeding coefficients as special cases. The individual descent measure, defined for four genes on two uniting gametes can be evaluated for any pedigree by means of an algorithm developed here. If initial gametic frequencies are specified, descent measures allow genotypic frequencies and disequilibria functions at one and two loci to be found. The procedures are illustrated for selfing and for sib mating. Several applications of the descent measures are discussed.     

An algorithm for efficient constrained mate selection

Background

Mate selection can be used as a framework to balance key technical, cost and logistical issues while implementing a breeding program at a tactical level. The resulting mating lists accommodate optimal contributions of parents to future generations, in conjunction with other factors such as progeny inbreeding, connection between herds, use of reproductive technologies, management of the genetic distribution of nominated traits, and management of allele/genotype frequencies for nominated QTL/markers.

Methods

This paper describes a mate selection algorithm that is widely used and presents an extension that makes it possible to apply constraints on certain matings, as dictated through a group mating permission matrix.

Results

This full algorithm leads to simpler applications, and to computing speed for the scenario tested, which is several hundred times faster than the previous strategy of penalising solutions that break constraints.

Conclusions

The much higher speed of the method presented here extends the use of mate selection and enables implementation in relatively large programs across breeding units.