Consider a pedigree P, which is a directed acyclic graph (V(P), E(P)). The vertices V(P) represent individuals and the edges E(P) represent parent-child relationships. Hence the maximum in-degree of any node is 2. We shall talk about the descendents of an individual I as being the set of all individuals reachable from vertex I using a walk of non-zero length, and the ancestors of I as being those individuals for which I is a descendent. Individuals with no ancestors are called founders. There is a Boolean function, available, which is defined on the individuals V(P), to define whether they are available or unavailable. Two individuals, I and J, are ‘unrelated’ if ancestors(I) and ancestors(J) are non-overlapping sets. Problem: find a maximal set of unrelated available individuals in P. Lemma 0: Consider the deletion of a set of individuals S from P such that for every s in S, descendents(s) is a subset of S. Such an operation will not change the relationships (either related or unrelated) of any individuals that remain in the pedigree. We shall call this aclosed, pruning operation. Proof: The relationship between two individuals i and j is defined in terms of the intersection of their ancestor sets. With a closed, pruning operation all descendents are deleted so the ancestor sets of those elements that remain are unaffected. QED.
|