Page 322 - Linear Models for the Prediction of Animal Breeding Values 3rd Edition

Appendix B: Fast Algorithms

for Calculating Inbreeding

Based on the L Matrix

In this appendix, two algorithms based on the L matrix for calculating inbreeding are
discussed.

B.1 Meuwissen and Luo Algorithm

The algorithm given by Quaas (1976) invoves the calculation of one column of L at
a time. The algorithm requires n(n + 1)/2 operations and computational time is pro-
2
portional to n , where n is the size of the data set. It suffers from the disadvantage of
not being readily adapted for updating when a new batch of animals is available
without restoring a previously stored L. Meuwissen and Luo (1992) presented a
faster algorithm, which involves computing the elements of L row by row.
The fact that each row of L is calculated independently of other rows makes it
suitable for updating. The row i of L for animal i gives the fraction of genes the ani-
mal derives from its ancestors. If s and d are the sire and dam of animal i, then
i i
l = l = 0.5. The ith row of L can be calculated by proceeding through a list of i’s
is i id i
ancestors from the youngest to the oldest and updating continually as l = l + 0.5l
is j is j ij
and l = l + 0.5l , where j is an ancestor of i. The fraction of genes derived from
id j id j ij
an ancestor is:
ij l = å 0.5 ik l
ke P j
where P is a set of identities of the progeny of j. However, l = 0 only when k is not
j ij
an ancestor of i or k is not equal to i. Thus if AN is the set of identities of the number
of ancestors of i, then:
ij l = å 0.5 ik l
Ç
keAN p
j
that is, the summation of 0.5l is over those k animals that are both ancestors of i
ik
and progeny of j. This forms the basis of the algorithm given below for the calcula-
tion of the row i of L, one row at a time. As each row of L is calculated, its contribu-
tion to the diagonal elements of the relationship matrix (a ) is accumulated. Initially,
ii
set row i of L and a to zero. The list of ancestors whose contributions to a are yet
ii ii
to be included are added to the vector AN (if not already there) as each row of L is
being processed.
The algorithm is:
F = −1
0
For i = 1, N (all rows of L):

306 © R.A. Mrode 2014. Linear Models for the Prediction of Animal Breeding Values,
3rd Edition (R.A. Mrode)