, one such
family is designated as the first. There is an edge between that first
family and all the other multiple marriages in which is a parent.
The description in Ott's book suggests that the pedigree traversal algorithm in LINKAGE is a minor modification of the Elston-Stewart bottom-up approach. I can see how this claim is plausible from a genetics or statistics point of view. However, as an algorithmicist, I find the suggestion that the Elston-Stewart and LINKAGE algorithms are similar to be misleading.
It is true that for pedigrees that satisfy the 4 conditions above, the two probability update algorithms can visit the nuclear families in the same order. However, this is far from obvious if one stares at the LINKAGE traversal code. I use the word ``can'' rather than ``do'' in the first sentence because both the Elston-Stewart algorithm and the LINKAGE algorithm allow for some arbitrary orderings in the nuclear family visits. It is possible to correctly implement the Elston-Stewart algorithm to visit the nuclear families in orders which are absolutely impossible with LINKAGE, no matter how LINKAGE makes its free choices. For example, in a pedigree that satisfies the 4 conditions above and has multiple nuclear families at each generation but the topmost, the generation-by-generation traversal sequences proposed above as possible for the Elston-Stewart algorithm are not possible in LINKAGE. This will be illustrated with an example below.
Since I am trained in graph algorithms, I prefer to think of the pedigree with the following auxiliary graph, which I call the nuclear family graph. First let's assume that there are no multiple marriages. In this graph each nuclear family becomes a vertex and two vertices are adjacent (i.e., connected by an undirected edge) if their nuclear families share an individual which is a parent in one family and a child in the other.
The case of multiple marriages is subtle. We call a nuclear family
a ``multiple marriage'' if one of its parents parented offspring with
multiple distinct mates both of whom are in the pedigree.
We distinguish two types of multiple marriages. A f-multiple
marriage (nuclear family)
is one in which the multiply married spouse is a founder.
A n-multiple marriage (nuclear family)
is one in which the multiply married person is
not a founder in the pedigree.
Each multiple marriage corresponds to a distinct vertex
in the nuclear family graph. There is an edge between an n-multiple
marriage and the parent nuclear family in which the multiply married person is
a child.
Among all f-multiple marriages involving some individual , one such
family is designated as the first. There is an edge between that first
family and all the other multiple marriages in which is a parent.