Computation and Approximation of the Inverse of Relationship Matrices Between Genotyped Animals: Algorithms and Applications
Calcul et approximation de l'inverse de matrices de parenté entre animaux génotypés: algorithmes et applications
Abstract
The recent developments in molecular biology have made available thousands of
genetic markers, allowing livestock genotyping at a reasonable cost and the subsequent
development of genomic prediction. The single-step procedure, a unified approach of
genomic prediction, requires inversion of two matrices gathering additive relationships
between genotyped animals: the genomic relationship matrix (G) and a part of the
additive relationship matrix (A22). The inverse of A22 may also be interesting for other
applications. Matrix inverse can be constructed successively by, first, computing, for each
animal, the vector containing contributions of other animals to its relationship and,
secondly, adding the product of each vector of contributions by itself to a zeroed matrix.
The objectives of this thesis were (1) to propose algorithms to compute or to approximate
the vector of contributions and (2) to test the numerical efficiency of these algorithms
(computing speed, memory use and, if needed, approximation accuracy). Computing
contributions covered two points: (1) finding or approximating which contributions are
different from zero, and (2) computing the value of contributions considered as non-zero.
In the first approach, we considered that animals closely related have non-zero
contributions and approximated their values by linear regression. This approach was
extended in a recursive way. In the second approach, we empirically determined the set of
non-zero contributions by a heuristic algorithm of pedigree exploration (only for the case
of A22). Values were then computed either by linear regression, or using the already
computed inverse. We also tested an approximation strategy: limiting the number of
extracted generations of non-genotyped ancestors to reduce pedigree complexity. In a
third approach, we followed the same heuristic algorithm as before but restricted the
pedigree exploration to find out which animals have a non-zero contribution. Their values
were approximated by linear regression. The presentation of the different approaches is
followed by a general discussion in which the approaches are compared. It was found that
the best compromise between speed, memory and approximation accuracy was achieved
by the last approach for the case of A22. Use of this last approach simplified computations
and therefore made predictions more feasible. However, for the case of G, no sufficient
approximations could be reach in a reasonable time. Perspectives of other uses of
algorithms developed and of future researches were drawn, as well as practical
perspectives for animal breeding.
De récents développements en biologie moléculaire ont rendu disponibles des
milliers de marqueurs génétiques, permettant de génotyper les animaux de rentes à un
coût modéré et, conséquemment, le développement de la prédiction génomique. La
procédure « single-step », une approche unifiée de prédiction génomique, requiert
l’inversion de deux matrices rassemblant les parentés additives entre animaux génotypés :
la matrice de parenté génomique (G) et une partie de la matrice de parenté additive (A22).
L’inverse de A22 peut également être intéressante pour d’autres applications. L’inverse
d’une matrice peut être construite successivement : premièrement, en calculant, pour
chaque animal, le vecteur qui contient les contributions des autres animaux aux parentés
de celui-ci et, deuxièmement, en ajoutant le produit de chaque vecteur de contributions
par lui-même à une matrice nulle. Les objectifs de cette thèse sont (1) de proposer des
algorithmes pour construire ou approximer le vecteur des contributions et (2) de tester
l’efficience numérique de ces algorithmes (temps de calcul, usage de mémoire et, si
nécessaire, précision de l’approximation). Calculer les contributions recouvre deux
aspects : (1) trouver ou approximer quelles sont les contributions non-nulles, et (2)
calculer les contributions considérées comme non-nulles. Dans la première approche,
nous considérons que les animaux fortement apparentés ont des contributions non nulles
et approximons leur valeur par régression linéaire. Cette approche est étendue dans une
implémentation récursive. Dans la seconde approche, nous déterminons empiriquement
l’ensemble de contributions non-nulles par un algorithme heuristique d’exploration du
pedigree (seulement pour le cas de A22). Les valeurs sont alors calculés soit par régression
linéaire on en utilisant l’inverse déjà calculé à ce point. Nous testons aussi une stratégie
d’approximation : limiter le nombre de générations extraites d’ancêtres non-génotypés
pour réduire la complexité du pedigree. Dans une troisième approche, nous suivons le
même algorithme heuristique qu’avant mais restreignons l’exploration du pedigree pour
trouver quels animaux ont une contribution non-nulle. Leur valeur est approximée par
régression linéaire. La présentation des différentes approches est suivie par une discussion
générale dans laquelle les approches sont comparées. Il a été montré que le meilleur
compromis entre consommation de temps et de mémoire et justesse de l’approximation
était réalisé par la dernière approche dans le cas de A22. Utiliser cette dernière approche
simplifie les calculs et donc rend les prédictions plus faisables. Cependant, pour le cas de
G, aucune approximation suffisante n’a pu être atteinte en un temps raisonnable. Des
perspectives d’autres utilisations des algorithmes et de futures recherches sont esquissées,
aussi bien que des perspectives pratiques pour l’amélioration animale.