# Path-Counting Formulas for Generalized Kinship Coefficients and Condensed Identity Coefficients

Authors: En Cheng; Z. Meral Ozsoyoglu
Journal: Computational and Mathematical Methods in Medicine
 (2014)

---

## Abstract

An important computation on pedigree data is the calculation of condensed identity coefficients, which provide a complete description of the degree of relatedness of two individuals. The applications of condensed identity coefficients range from genetic counseling to disease tracking. Condensed identity coefficients can be computed using linear combinations of generalized kinship coefficients for two, three, four individuals, and two pairs of individuals and there are recursive formulas for computing those generalized kinship coefficients (Karigl, 1981). Path-counting formulas have been proposed for the (generalized) kinship coefficients for two (three) individuals but there have been no path-counting formulas for the other generalized kinship coefficients. It has also been shown that the computation of the (generalized) kinship coefficients for two (three) individuals using path-counting formulas is efficient for large pedigrees, together with path encoding schemes tailored for pedigree graphs. In this paper, we propose a framework for deriving path-counting formulas for generalized kinship coefficients. Then, we present the path-counting formulas for all generalized kinship coefficients for which there are recursive formulas and which are sufficient for computing condensed identity coefficients. We also perform experiments to compare the efficiency of our method with the recursive method for computing condensed identity coefficients on large pedigrees.


---

## Body

## 1. Introduction

With the rapidly expanding field of medical genetics and genetic counseling, genealogy information is becoming increasingly abundant. In January 2009, the US Department of Health and Human Services released an updated and improved version of the Surgeon General’s Web-based family health history tool [1]. This Web-based tool makes it easy for users to record their family health history. Large extended human pedigrees are very informative for linkage analysis. Pedigrees including thousands of members in 10–20 generations are available from genetically isolated populations [2, 3]. In human genetics, a pedigree is defined as “a simplified diagram of a family’s genealogy that shows family members’ relationships to each other and how a specific trait, abnormality, or disease has been inherited” [4]. Pedigrees are utilized to trace the inheritance of a specific disease, calculate genetic risk ratios, identify individuals at risk, and facilitate genetic counseling. To calculate genetic risk ratios or identify individuals at risk, we need to assess the degree of relatedness of two individuals. As a matter of fact, all measures of relatedness are based on the concept ofidentical by descent (IBD). Two alleles are identical by descent if one is an ancestral copy of the other or if they are both copies of the same ancestral allele. The IBD concept is primarily due to Cotterman [5] and Malecot [6] and has been successfully applied to many problems in population genetics.The simplest measure of relationship between two individuals is their kinship coefficient. Thekinship coefficient between two individuals i and j is the probability that an allele selected randomly from i and an allele selected randomly from the same autosomal locus of j are identical by descent. To better discriminate between different types of pairs of relatives, identity coefficients were introduced by Gillois [7] and Harris [8] and promulgated by Jacquard [9]. Considering the four alleles of two individuals at a fixed autosomal locus, there are 15 possible identity states. Disregarding the distinction between maternally and paternally derived alleles, we obtain 9 condensed identity states. The probabilities associated with each condensed identity state are calledcondensed identity coefficients, which are useful in a diverse range of fields. This includes the calculation of risk ratios for qualitative disease, the analysis of quantitative traits, and genetic counseling in medicine.A recursive algorithm for calculating condensed identity coefficients proposed by Karigl [10] has been known for some time. This method requires that one calculates a set of generalized kinship coefficients, from which one obtains condensed identity coefficients via a linear transformation. One limitation is that this recursive approach is not scalable when applied to very large pedigrees. It has been previously shown that the kinship coefficients for two individuals [11–13] and the generalized kinship coefficients for three individuals [14, 15] can be efficiently calculated using path-counting formulas together with path encoding schemes tailored for pedigree graphs.Motivated by the efficiency of path-counting formulas for computing the kinship coefficient for two individuals and the generalized kinship coefficient for three individuals, we first introduce a framework for developing path-counting formulas to compute generalized kinship coefficients concerning three individuals, four individuals, and two pairs of individuals. Then, we present path-counting formulas for all generalized kinship coefficients which have recursive formulas proposed by Karigl [10] and are sufficient to compute condensed identity coefficients. In summary, our ultimate goal is to use path-counting formulas for generalized kinship coefficients computation so that efficiency and scalability for condensed identity coefficients calculation can be improved.The main contributions of our work are as follows:(i)
a framework to develop path-counting formulas for generalized kinship coefficients;(ii)
a set of path-counting formulas for all generalized kinship coefficients having recursive formulas [10];(iii)
experimental results demonstrating significant performance gains for calculating condensed identity coefficients based on our proposed path-counting formulas as compared to using recursive formulas [10].


## 2. Materials and Methods

This section describes kinship coefficients and generalized kinship coefficients, identity coefficients, and condensed identity coefficients in more detail. Conceptual terms for the path-counting formulas for three and four individuals are introduced in Section2.3. In addition, an overview of path-counting formula derivation is presented.


### 2.1. Kinship Coefficients and Generalized Kinship Coefficients

The kinship coefficient between two individualsa and b is the probability that a randomly chosen allele at the same locus from each is identical by descent (IBD). There are two approaches to computing the kinship coefficient Φab: the recursive approach [10] and the path-counting approach [16]. The recursive formulas [10] for Φab and Φaa are
(1)Φab=12(Φfb+Φmb)ifaisnotanancestorofb,Φaa=12(1+Φfm)=12(1+Fa),
where f and m denote the father and the mother of a, respectively, and Fa is the inbreeding coefficient of a.Wright’s path-counting formula [16] for Φab is
(2)Φab=∑A∑〈PAa,PAb〉∈PP(12)r+s+1(1+FA),
where A is a common ancestor of a and b,PP is a set of nonoverlapping path-pairs 〈PAa,PAb〉 from A to a and b, r is the length of the path PAa, s is the length of the path PAb, and FA is the inbreeding coefficient of A. The path-pair 〈PAa,PAb〉 isnonoverlapping if and only if the two paths share no common individuals, except A.Recursive formulas proposed by Karigl [10] for generalized kinship coefficients concerning three individuals, four individuals, and two pairs of individuals are listed as follows in (3), (4), and (5):
(3)Φabc=12(Φfbc+Φmbc)ifaisnotanancestorofborc,Φaab=12(Φab+Φfmb)ifaisnotanancestorofb,Φaaa=14(1+3Φfm)=14(1+3Fa),(4)Φabcd=12(Φfbcd+Φmbcd)ifaisnotanancestorofborcord,Φaabc=12(Φabc+Φfmbc)ifaisnotanancestorofborc,Φaaab=14(Φab+3Φfmb)ifaisnotanancestorofb,Φaaaa=18(1+7Φfm)=18(1+7Fa),(5)Φab,cd=12(Φfb,cd+Φmb,cd)ifaisnotanancestorofborcord,Φaa,bc=12(Φbc+Φfm,bc)ifaisnotanancestorofborc,Φab,ac=14(2Φabc+Φfb,mc+Φmb,fc)ifaisnotanancestorofborc,Φaa,ab=12(Φab+Φfmb)ifaisnotanancestorofb,Φaa,aa=14(1+3Φfm)=14(1+3Fa).Φ
a
b
c is the probability that randomly chosen alleles at the same locus from each of the three individuals (i.e., a,b, and c) are identical by descent (IBD). Similarly, Φabcd is the probability that randomly chosen alleles at the same locus from each of the four individuals (i.e., a,b,c, and d) are IBD. Φab,cd is the probability that a random allele from a is IBD with a random allele from b and that a random allele from c is IBD with a random allele from d at the same locus. Note that Φabc=0 if there is no common ancestor of a,b, and c. Φabcd=0 if there is no common ancestor of a, b, c, and d, and Φab,cd=0 in the absence of a common ancestor either for a and b or for c and d.


### 2.2. Identity Coefficients and Condensed Identity Coefficients

Given two individualsa and b with maternally and paternally derived alleles at a fixed autosomal locus, there are 15 possible identity states, and the probabilities associated with each identity state are calledidentity coefficients. Ignoring the distinction between maternally and paternally derived alleles, we categorize the 15 possible states to 9 condensed identity states, as shown in Figure 1. The states range from state 1, in which all four alleles are IBD, to state 9, in which none of the four alleles are IBD. The probabilities associated with each condensed identity state are calledcondensed identity coefficients, denoted by {Δi∣1≤i≤9}. The condensed identity coefficients can be computed based on generalized kinship coefficients using the linear transformation shown as follows in (6):
(6)[11111111122221111122112211140202021080402021080204021016040402104422221111604040410][Δ1Δ2Δ3Δ4Δ5Δ6Δ7Δ8Δ9]=[12Φaa2Φbb4Φab8Φaab8Φabb16Φaabb4Φaa,bb16Φab,ab].Figure 1
The 15 possible identity states for individualsa and b, grouped by their 9 condensed states. Lines indicate alleles that are IBD.In our work, we focus on deriving the path-counting formulas for the generalized kinship coefficients, includingΦabc, Φabcd, and Φab,cd.


### 2.3. Terms Defined for Path-Counting Formulas for Three and Four Individuals

(1) Triple-Common Ancestor. Given three individuals a, b, and c, if A is a common ancestor of the three individuals, then we call A atriple-common ancestor of a, b, and c.(2) Quad-Common Ancestor. Given four individuals a, b, c, and d, if A is a common ancestor of the four individuals, then we call A aquad-common ancestor of a, b, c, and d.(3)
P
(
A
,
a
). It denotes the set of all possible paths from A to a, where the paths can only traverse edges in the direction of parent to child such that P(A,a)≠NULL if and only if A is an ancestor of a. PAa denotes a particular path from A to a, where PAa∈P(A,a).(4) Path-Pair. It consists of two paths, denoted as 〈PAa,PAb〉, where PAa∈P(A,a) and PAb∈P(A,b).(5) Nonoverlapping Path-Pair. Given a path-pair 〈PAa,PAb〉, it isnonoverlapping if and only if the two paths share no common individuals, except A.(6) Path-Triple. It consists of three paths, denoted as 〈PAa,PAb,PAc〉, where PAa∈P(A,a), PAb∈P(A,b), and PAc∈P(A,c).(
7) Path-Quad. It consists of four paths, denoted as 〈PAa,PAb,PAc,PAd〉, where PAa∈P(A,a), PAb∈P(A,b), PAc∈P(A,c), and PAd∈P(A,d).(
8)
B
i
_
C
(
P
A
a
,
P
A
b
). It denotes all common individuals shared between PAa and PAb, except A.(
9)
T
r
i
_
C
(
P
A
a
,
P
A
b
,
P
A
c
). It denotes all common individuals shared among PAa, PAb, and PAc, except A.(
10)
Q
u
a
d
_
C
(
P
A
a
,
P
A
b
,
P
A
c
,
P
A
d
). It denotes all common individuals shared among PAa, PAb, PAc, and PAd, except A.(
11) Crossover and 2-Overlap Individual. If s∈Bi_C(PAa,PAb), we call s acrossover individual with respect to PAa and PAb if the two paths pass throughdifferent parents of s. On the other hand, if PAa and PAb pass through thesame parent of s, then we call s a 2-overlap individual with respect to PAa and PAb.(
12) 3-Overlap Individual. If s∈Tri_C(PAa,PAb,PAc) and the three paths PAa, PAb, and PAc pass through thesame parent of s, then we call s a3-overlap individual with respect to PAa, PAb, and PAc.(13) 2-Overlap Path. If s is a 2-overlap individual with respect to PAa and PAb, then both PAa and PAb pass through the same parent of s, denoted by p, and the edge from p to s is called anoverlap edge. All consecutive overlap edges constitute a path and this path is called a 2-overlap path. If the 2-overlap path extends all the way to the ancestor A, we call it aroot2-overlap path.(14) 3-Overlap Path.
It consists of all 3-overlap individuals in a consecutive order. If the 3-overlap path extends all the way to the root A, we call it aroot 3-overlap path.Example 1.
Consider thepath-pairs from A to a and b in Figure 2, where A is a common ancestor of a and b. Forpath-pair1, Bi_C(PAa,PAb)={s,e,t}, and A→s→e→t is aroot 2-overlap path with respect to PAa and PAb. Forpath-pair4, Bi_C(PAa,PAb)={e,t}, where e is acrossover individual; t is a 2-overlap individual with respect to PAa and PAb, and e→t is aroot 2-overlap path with respect to PAa and PAb.Figure 2
Examples of path-pairs and path-triples.Example 2.
There are four path-quads listed in Figure3, from A to four individuals a, b, c, and d, where A is a quad-common ancestor of the four individuals. Forpath-quad2, considering the paths PAa and PAb, the path A→t→f→s is aroot2-overlap path; {t,f,s} are 2-overlap individuals with respect to PAa and PAb. Forpath-quad3, {t,f,s} are 3-overlap individuals with respect to PAa, PAb, and PAc, and the path A→t→f→s is aroot 3-overlap path.Figure 3
Examples of path-quads.Then, we summarize all the conceptual terms used in the path-counting formulas for two individuals, three individuals, and four individuals in Table1 which reveals a glimpse of our framework for generalizing Wright’s formula to three and four individuals from terminology aspect.Table 1
The conceptual terms used for two, three, and four individuals.
Two individuals
Three individuals
Four individuals
Common ancestor
Triple-common ancestor
Quad-common ancestor
Path-pair
Path-triple
Path-quad
B
i
_
C
(
P
A
a
,
P
A
b
)
T
r
i
_
C
(
P
A
a
,
P
A
b
,
P
A
c
)
Q
u
a
d
_
C
(
P
A
a
,
P
A
b
,
P
A
c
,
P
A
d
)
N/A
2-Overlap individual
3-Overlap individual
N/A
2-Overlap path
3-Overlap path
N/A
Root 2-overlap path
Root 3-overlap path
N/A
Crossover individual
Crossover individual


### 2.4. An Overview of Path-Counting Formula Derivation

According to Wright’s path-counting formula [16] (see (2)) for two individuals a and b, the path-counting approach requires identifying common ancestors of a and b and calculating the contribution of each common ancestor to Φab. More specifically, for each common ancestor, denoted as A, we obtain all path-pairs from A to a and b and identify acceptable path-pairs. For Φab, an acceptable path-pair 〈PAa,PAb〉 is a nonoverlapping path-pair where the two paths share no common individuals, except A. In Figure 2,path-pair2 is an acceptable path-pair, whilepath-pair1,path-pair3, andpath-pair4 are not acceptable path-pairs. The contribution of each common ancestor A to Φab is computed based on the inbreeding coefficient of A, modified by the length of each acceptable path-pair.To computeΦabc, the path-counting approach requires identifying all triple-common ancestors of a, b, and c and summing up all triple-common ancestors’ contributions to Φabc. For each triple-common ancestor, denoted as A, we first identify all path-triples each of which consists of three paths from A to a, b, and c, respectively. Some examples of path-triples are presented in Figure 2.ForΦab, only nonoverlapping path-pairs are acceptable. A path-triple 〈PAa,PAb,PAc〉 consists of three path-pairs 〈PAa,PAb〉, 〈PAa,PAc〉, and 〈PAb,PAc〉. For Φabc, a path-triple might be acceptable even though either 2-overlap individuals or crossover individuals exist between a path-pair. The main challenge we need to address is finding necessary and sufficient conditions for acceptable path-triples.Aiming at solving the problem of identifying acceptable path-triples, we first use a systematic method to generate all possible cases for a path-pair by considering different types of common individuals shared between the two paths. Then, we introduce building blocks which are connected graphs with conditions on every edge in the graph that encapsulates a set of acceptable cases of path-pairs. In each building block, we represent paths as nodes and interactions (i.e., shared common individuals between two paths) as edges. There are at least two paths in a building block. For each building block, we obtain all acceptable cases for concerned path-pairs. Given a path-triple, it can be decomposed to one or multiple building blocks. Considering a shared path-pair between two building blocks, we use thenatural join operator from relational algebra to match the acceptable cases for the shared path-pair between two building blocks. In other words, considering the acceptable cases for building blocks as inputs, we use the natural join operator to construct all acceptable cases for a path-triple. Acceptable cases for a path-triple are identified and then used in deriving the path-counting formula for Φabc.Then, we summarize all the main procedures used for deriving the path-counting formula forΦabc in a flowchart shown in Figure 4. The main procedures are also applicable for deriving the path-counting formulas for Φabcd and Φab,cd.Figure 4
A flowchart for path-counting formula derivation.


## 2.1. Kinship Coefficients and Generalized Kinship Coefficients

The kinship coefficient between two individualsa and b is the probability that a randomly chosen allele at the same locus from each is identical by descent (IBD). There are two approaches to computing the kinship coefficient Φab: the recursive approach [10] and the path-counting approach [16]. The recursive formulas [10] for Φab and Φaa are
(1)Φab=12(Φfb+Φmb)ifaisnotanancestorofb,Φaa=12(1+Φfm)=12(1+Fa),
where f and m denote the father and the mother of a, respectively, and Fa is the inbreeding coefficient of a.Wright’s path-counting formula [16] for Φab is
(2)Φab=∑A∑〈PAa,PAb〉∈PP(12)r+s+1(1+FA),
where A is a common ancestor of a and b,PP is a set of nonoverlapping path-pairs 〈PAa,PAb〉 from A to a and b, r is the length of the path PAa, s is the length of the path PAb, and FA is the inbreeding coefficient of A. The path-pair 〈PAa,PAb〉 isnonoverlapping if and only if the two paths share no common individuals, except A.Recursive formulas proposed by Karigl [10] for generalized kinship coefficients concerning three individuals, four individuals, and two pairs of individuals are listed as follows in (3), (4), and (5):
(3)Φabc=12(Φfbc+Φmbc)ifaisnotanancestorofborc,Φaab=12(Φab+Φfmb)ifaisnotanancestorofb,Φaaa=14(1+3Φfm)=14(1+3Fa),(4)Φabcd=12(Φfbcd+Φmbcd)ifaisnotanancestorofborcord,Φaabc=12(Φabc+Φfmbc)ifaisnotanancestorofborc,Φaaab=14(Φab+3Φfmb)ifaisnotanancestorofb,Φaaaa=18(1+7Φfm)=18(1+7Fa),(5)Φab,cd=12(Φfb,cd+Φmb,cd)ifaisnotanancestorofborcord,Φaa,bc=12(Φbc+Φfm,bc)ifaisnotanancestorofborc,Φab,ac=14(2Φabc+Φfb,mc+Φmb,fc)ifaisnotanancestorofborc,Φaa,ab=12(Φab+Φfmb)ifaisnotanancestorofb,Φaa,aa=14(1+3Φfm)=14(1+3Fa).Φ
a
b
c is the probability that randomly chosen alleles at the same locus from each of the three individuals (i.e., a,b, and c) are identical by descent (IBD). Similarly, Φabcd is the probability that randomly chosen alleles at the same locus from each of the four individuals (i.e., a,b,c, and d) are IBD. Φab,cd is the probability that a random allele from a is IBD with a random allele from b and that a random allele from c is IBD with a random allele from d at the same locus. Note that Φabc=0 if there is no common ancestor of a,b, and c. Φabcd=0 if there is no common ancestor of a, b, c, and d, and Φab,cd=0 in the absence of a common ancestor either for a and b or for c and d.


## 2.2. Identity Coefficients and Condensed Identity Coefficients

Given two individualsa and b with maternally and paternally derived alleles at a fixed autosomal locus, there are 15 possible identity states, and the probabilities associated with each identity state are calledidentity coefficients. Ignoring the distinction between maternally and paternally derived alleles, we categorize the 15 possible states to 9 condensed identity states, as shown in Figure 1. The states range from state 1, in which all four alleles are IBD, to state 9, in which none of the four alleles are IBD. The probabilities associated with each condensed identity state are calledcondensed identity coefficients, denoted by {Δi∣1≤i≤9}. The condensed identity coefficients can be computed based on generalized kinship coefficients using the linear transformation shown as follows in (6):
(6)[11111111122221111122112211140202021080402021080204021016040402104422221111604040410][Δ1Δ2Δ3Δ4Δ5Δ6Δ7Δ8Δ9]=[12Φaa2Φbb4Φab8Φaab8Φabb16Φaabb4Φaa,bb16Φab,ab].Figure 1
The 15 possible identity states for individualsa and b, grouped by their 9 condensed states. Lines indicate alleles that are IBD.In our work, we focus on deriving the path-counting formulas for the generalized kinship coefficients, includingΦabc, Φabcd, and Φab,cd.


## 2.3. Terms Defined for Path-Counting Formulas for Three and Four Individuals

(1) Triple-Common Ancestor. Given three individuals a, b, and c, if A is a common ancestor of the three individuals, then we call A atriple-common ancestor of a, b, and c.(2) Quad-Common Ancestor. Given four individuals a, b, c, and d, if A is a common ancestor of the four individuals, then we call A aquad-common ancestor of a, b, c, and d.(3)
P
(
A
,
a
). It denotes the set of all possible paths from A to a, where the paths can only traverse edges in the direction of parent to child such that P(A,a)≠NULL if and only if A is an ancestor of a. PAa denotes a particular path from A to a, where PAa∈P(A,a).(4) Path-Pair. It consists of two paths, denoted as 〈PAa,PAb〉, where PAa∈P(A,a) and PAb∈P(A,b).(5) Nonoverlapping Path-Pair. Given a path-pair 〈PAa,PAb〉, it isnonoverlapping if and only if the two paths share no common individuals, except A.(6) Path-Triple. It consists of three paths, denoted as 〈PAa,PAb,PAc〉, where PAa∈P(A,a), PAb∈P(A,b), and PAc∈P(A,c).(
7) Path-Quad. It consists of four paths, denoted as 〈PAa,PAb,PAc,PAd〉, where PAa∈P(A,a), PAb∈P(A,b), PAc∈P(A,c), and PAd∈P(A,d).(
8)
B
i
_
C
(
P
A
a
,
P
A
b
). It denotes all common individuals shared between PAa and PAb, except A.(
9)
T
r
i
_
C
(
P
A
a
,
P
A
b
,
P
A
c
). It denotes all common individuals shared among PAa, PAb, and PAc, except A.(
10)
Q
u
a
d
_
C
(
P
A
a
,
P
A
b
,
P
A
c
,
P
A
d
). It denotes all common individuals shared among PAa, PAb, PAc, and PAd, except A.(
11) Crossover and 2-Overlap Individual. If s∈Bi_C(PAa,PAb), we call s acrossover individual with respect to PAa and PAb if the two paths pass throughdifferent parents of s. On the other hand, if PAa and PAb pass through thesame parent of s, then we call s a 2-overlap individual with respect to PAa and PAb.(
12) 3-Overlap Individual. If s∈Tri_C(PAa,PAb,PAc) and the three paths PAa, PAb, and PAc pass through thesame parent of s, then we call s a3-overlap individual with respect to PAa, PAb, and PAc.(13) 2-Overlap Path. If s is a 2-overlap individual with respect to PAa and PAb, then both PAa and PAb pass through the same parent of s, denoted by p, and the edge from p to s is called anoverlap edge. All consecutive overlap edges constitute a path and this path is called a 2-overlap path. If the 2-overlap path extends all the way to the ancestor A, we call it aroot2-overlap path.(14) 3-Overlap Path.
It consists of all 3-overlap individuals in a consecutive order. If the 3-overlap path extends all the way to the root A, we call it aroot 3-overlap path.Example 1.
Consider thepath-pairs from A to a and b in Figure 2, where A is a common ancestor of a and b. Forpath-pair1, Bi_C(PAa,PAb)={s,e,t}, and A→s→e→t is aroot 2-overlap path with respect to PAa and PAb. Forpath-pair4, Bi_C(PAa,PAb)={e,t}, where e is acrossover individual; t is a 2-overlap individual with respect to PAa and PAb, and e→t is aroot 2-overlap path with respect to PAa and PAb.Figure 2
Examples of path-pairs and path-triples.Example 2.
There are four path-quads listed in Figure3, from A to four individuals a, b, c, and d, where A is a quad-common ancestor of the four individuals. Forpath-quad2, considering the paths PAa and PAb, the path A→t→f→s is aroot2-overlap path; {t,f,s} are 2-overlap individuals with respect to PAa and PAb. Forpath-quad3, {t,f,s} are 3-overlap individuals with respect to PAa, PAb, and PAc, and the path A→t→f→s is aroot 3-overlap path.Figure 3
Examples of path-quads.Then, we summarize all the conceptual terms used in the path-counting formulas for two individuals, three individuals, and four individuals in Table1 which reveals a glimpse of our framework for generalizing Wright’s formula to three and four individuals from terminology aspect.Table 1
The conceptual terms used for two, three, and four individuals.
Two individuals
Three individuals
Four individuals
Common ancestor
Triple-common ancestor
Quad-common ancestor
Path-pair
Path-triple
Path-quad
B
i
_
C
(
P
A
a
,
P
A
b
)
T
r
i
_
C
(
P
A
a
,
P
A
b
,
P
A
c
)
Q
u
a
d
_
C
(
P
A
a
,
P
A
b
,
P
A
c
,
P
A
d
)
N/A
2-Overlap individual
3-Overlap individual
N/A
2-Overlap path
3-Overlap path
N/A
Root 2-overlap path
Root 3-overlap path
N/A
Crossover individual
Crossover individual


## 2.4. An Overview of Path-Counting Formula Derivation

According to Wright’s path-counting formula [16] (see (2)) for two individuals a and b, the path-counting approach requires identifying common ancestors of a and b and calculating the contribution of each common ancestor to Φab. More specifically, for each common ancestor, denoted as A, we obtain all path-pairs from A to a and b and identify acceptable path-pairs. For Φab, an acceptable path-pair 〈PAa,PAb〉 is a nonoverlapping path-pair where the two paths share no common individuals, except A. In Figure 2,path-pair2 is an acceptable path-pair, whilepath-pair1,path-pair3, andpath-pair4 are not acceptable path-pairs. The contribution of each common ancestor A to Φab is computed based on the inbreeding coefficient of A, modified by the length of each acceptable path-pair.To computeΦabc, the path-counting approach requires identifying all triple-common ancestors of a, b, and c and summing up all triple-common ancestors’ contributions to Φabc. For each triple-common ancestor, denoted as A, we first identify all path-triples each of which consists of three paths from A to a, b, and c, respectively. Some examples of path-triples are presented in Figure 2.ForΦab, only nonoverlapping path-pairs are acceptable. A path-triple 〈PAa,PAb,PAc〉 consists of three path-pairs 〈PAa,PAb〉, 〈PAa,PAc〉, and 〈PAb,PAc〉. For Φabc, a path-triple might be acceptable even though either 2-overlap individuals or crossover individuals exist between a path-pair. The main challenge we need to address is finding necessary and sufficient conditions for acceptable path-triples.Aiming at solving the problem of identifying acceptable path-triples, we first use a systematic method to generate all possible cases for a path-pair by considering different types of common individuals shared between the two paths. Then, we introduce building blocks which are connected graphs with conditions on every edge in the graph that encapsulates a set of acceptable cases of path-pairs. In each building block, we represent paths as nodes and interactions (i.e., shared common individuals between two paths) as edges. There are at least two paths in a building block. For each building block, we obtain all acceptable cases for concerned path-pairs. Given a path-triple, it can be decomposed to one or multiple building blocks. Considering a shared path-pair between two building blocks, we use thenatural join operator from relational algebra to match the acceptable cases for the shared path-pair between two building blocks. In other words, considering the acceptable cases for building blocks as inputs, we use the natural join operator to construct all acceptable cases for a path-triple. Acceptable cases for a path-triple are identified and then used in deriving the path-counting formula for Φabc.Then, we summarize all the main procedures used for deriving the path-counting formula forΦabc in a flowchart shown in Figure 4. The main procedures are also applicable for deriving the path-counting formulas for Φabcd and Φab,cd.Figure 4
A flowchart for path-counting formula derivation.


## 3. Results and Discussion

### 3.1. Path-Counting Formulas for Three Individuals

We first introduce a systematic method to generate all possible cases for a path-pair. Then we discuss building blocks for path-triples and identify all acceptable cases which are used in deriving the path-counting formula forΦabc.


#### 3.1.1. Cases for a Path-Pair

Given a path-pair〈PAa,PAb〉 with Bi_C(PAa,PAb)≠NULL, where A is a common ancestor of a and b and Bi_C(PAa,PAb) consists of all common individuals shared between PAa and PAb, except A, we introduce three patterns (i.e.,crossover, 2-overlap, androot 2-overlap) to generate all possible cases for 〈PAa,PAb〉.(1)
X(PAa,PAb): PAa and PAb share one or multiple crossover individuals.(2)
T(PAa,PAb): PAa and PAb are root 2-overlapping from A, and the root 2-overlap path can have one or multiple 2-overlap individuals.(3)
Y(PAa,PAb): PAa and PAb are overlapping but not from A, and the 2-overlap path can have one or multiple 2-overlap individuals.Based on the three patterns,X(PAa,PAb), T(PAa,PAb), and Y(PAa,PAb), we use regular expressions to generate all possible cases for the path-pair 〈PAa,PAb〉. For convenience, we drop 〈PAa,PAb〉 and use X,T, and Y instead of patterns X(PAa,PAb), T(PAa,PAb), and Y(PAa,PAb), whenever there is no confusion. When Bi_C(PAa,PAb)≠NULL, the eight cases shown in (7) cover all possible cases for 〈PAa,PAb〉. The completeness of eight cases shown in (7) for 〈PAa,PAb〉 can be proved by induction on the total number of T, X, and Y appearing in 〈PAa,PAb〉. Using the pedigree in Figure 2, Cases 1–3 and Case 6 are illustrated in (8), (9), (10), and (11):
(7){Case1:TCase2:X+Case3:TX+Case4:T(X+Y)+,{Case5:T(X+Y)+X+Case6:X+YCase7:X+(YX+)+Case8:X+(YX+)+Y,(8)A⟶s⟶e⟶t⟶aA⟶s⟶e⟶t⟶b}∈T,
where {s,e,t} are 2-overlap individuals and the overlap path is a root 2-overlap path:
(9)A⟶s⟶e⟶t⟶aA⟶s⟶f⟶t⟶b}∈TX,
where s is a 2-overlap individual and the overlap path is a root 2-overlap path; t is a crossover individual:
(10)A⟶s⟶e⟶t⟶aA⟶d⟶f⟶t⟶b}∈X,
where t is a crossover individual:
(11)A⟶c⟶e⟶t⟶aA⟶s⟶e⟶t⟶b}∈XY,
where e is a crossover individual; t is a 2-overlap individual and the overlap path is a 2-overlap path.


#### 3.1.2. Path-Pair Level Graphical Representation of a Path-Triple

Given a path-triple〈PAa,PAb,PAc〉, we represent each path as a node. The path-triple can be decomposed to three path-pairs (i.e., 〈PAa,PAb〉, 〈PAa,PAc〉, and 〈PAb,PAc〉). For each path-pair, if the two paths share at least one common individual (i.e., either 2-overlap individual or crossover individual), except A, then there is an edge between the two nodes representing the two paths. Therefore, we obtain four different scenarios S0–S3, shown in Figure 5.Figure 5
A path-pair level graphical representation of〈PAa,PAb,PAc〉.In Figure5, the scenario S0 has no edges, so it means that 〈PAa,PAb,PAc〉 consists of three independent paths. In Figure 2,path-triple1 is an example of S0. Next, we introduce a lemma which can assist with identifying the options for the edges in the scenarios S1–S3.Lemma 3.
Given a path-triple〈PAa,PAb,PAc〉, consider the three path-pairs 〈PAa,PAb〉, 〈PAa,PAc〉, and 〈PAb,PAc〉, if there is a 2-overlap edge which is represented by Y in regular expression representation of any of the three path-pairs, and then the path-triple 〈PAa,PAb,PAc〉 has no contribution to Φabc.Proof.
In [17], Nadot and Vaysseix proposed, from a genetic and biological point of view, that Φabc can be evaluated by enumerating all eligible inheritance paths at allele-level starting from a triple common ancestor A to the three individuals a, b, and c.
For the pedigree in Figure6, let us consider the path-triple 〈PAa,PAb,PAc〉 listed as follows. PAa:A→a; PAb:A→p3→p6→p7→b; PAc:A→p4→p6→p7→c.
For〈PAb,PAc〉,   p6 is a crossover individual,   p7 is an overlap individual, and p6→p7 is a 2-overlap edge represented by Y in regular expression representation (see the definition for Y in Section 3.1.1).
For the individualp6, let us denote the two alleles at one fixed autosomal locus as g1 and g2. At allele-level, only one allele can be passed down from p6 to p7. Since p3 and p4 are parents of p6,g1 is passed down from one parent, and g2 is passed down from the other parent. It is infeasible to pass down both g1 and g2 from p6 to p7. In other words, there are no corresponding inheritance paths for the path-triple 〈PAa,PAb,PAc〉 with a 2-overlap edge between 〈PAb,PAc〉 (i.e., Case 6: XY). Therefore, such kind of path-triples has no contribution to Φabc.Examples of pedigree and inheritance paths.
(a)
Pedigree
(b)
Inheritance pathsFigure6(b) shows one example of eligible inheritance paths corresponding to a pedigree graph. Each individual is represented by two allele nodes. The eligible inheritance paths in Figure 6(b) consist of red edges only.Only Case 1, Case 2, and Case 3 do not haveY in the regular expression representation of a path-pair (see (7)); considering the scenarios S1–S3 shown in Figure 5, an edge can have three options {Case1:T;Case2:X;Case3:TX}.


#### 3.1.3. Constructing Cases for a Path-Triple

For the scenariosS1–S3 in Figure 5, we define two building blocks {B1,B2} along with some rules in Figure 7 to generate acceptable cases. For B1, the edge can have three options {Case1:T;Case2:X;Case3:TX}. For B2, we cannot allow both edges to be root overlap, because if two edges are root overlap, then PAa and PAc must share at least one common individual, except A, which contradicts the fact that PAa and PAc have no edge.Figure 7
Building blocks{B1,B2} and basic rules.Next, we focus on generating all acceptable cases for the scenariosS1–S3 in Figure 5, where only S3 contains more than one building block. In order to leverage the dependency among building blocks, we decompose S3 to S3={u1=B2,u2=B2,u3=B2}, shown in Figure 8. For each ui, we have a set of acceptable path-triples, denoted as Ri.Figure 8
A graphical illustration for obtainingT3.Considering the dependency among{R1,R2,R3}, we use the natural join operator, denoted as ⋈, operating on {R1,R2,R3} to generate all acceptable cases for S3. As a result, we obtain T3=R1⋈R2⋈R3, where T3 denotes the acceptable cases of the path-triple 〈PAa,PAb,PAc〉 in the scenario S3.For each scenario in Figure5, we generate all acceptable cases for 〈PAa,PAb,PAc〉. The scenario S0 has no edges, and it shows that 〈PAa,PAb,PAc〉 consists of three independent paths, while, for the other scenarios Sk (k=1,2,3), the k edges can have two options:(1)
allk edges belong tocrossover; or(2)
one edge belongs toroot 2-overlap; the remaining (k-1) edges belong tocrossover.In summary, acceptable path-triples can have at most one root 2-overlap path, any number of crossover individuals, but zero 2-overlap path.


#### 3.1.4. Splitting Operator

Considering the existence of root 2-overlap path and crossover in acceptable path-triples, we propose a splitting operator to transform a path-triple with crossover individuals to a noncrossover path-triple without changing the contribution from this path-triple toΦabc. The main purpose of using the splitting operator is to simplify the path-counting formula derivation process. We first use an example in Figure 9 to illustrate how the splitting operator works. In Figure 9, there is a crossover individual s between PAa and PAb in the path triple 〈PAa,PAb,PAc〉 in Gk+1. The splitting operator proceeds as follows:(1)
split the nodes to two nodes, s1 and s2;(2)
transform the edgess→a’ and s→b’ to s1→a’ and s2→b’, respectively;(3)
add two new edges,s2→a’ and s1→b’.Figure 9
Transforming pedigree graphGk+1 having k+1 crossover to Gk having k crossover.Lemma 4.
Given a pedigree graphGk+1 having (k+1) crossover individuals regarding 〈PAa,PAb,PAc〉 shown in Figure 9, let s denote the lowest crossover individual, where no descendant of s can be a crossover individual among the three paths PAa, PAb, and PAc. After using the splitting operator for the lowest crossover individual s in Gk+1, the number of crossover individuals in Gk+1 is decreased by 1.Proof.
The splitting operator only affects the edges froms to a’ and b’. If there is a new crossover node appearing, the only possible node is either a’ or b’. Assume b’ becomes a crossover individual; it means that b’ is able to reach a and b from two separate paths. It contradicts the fact that s is the lowest crossover individual between PAa and PAb.Next, we introduce a canonical graph which results from applying the splitting operator for all crossover individuals. The canonical graph has zero crossover individual.Definition 5 (Canonical Graph).
Given a pedigree graphG having one or more crossover individuals regarding Φabc, If there exists a graph G’ which has no crossover individuals with regards to Φabc such that(i)
any acceptable path-triple inG has an acceptable path-triple in G’ which has the same contribution to Φabc as the one in G for Φabc;(ii)
any acceptable path-triple inG’ has an acceptable path-triple in G which and has the same contribution to Φabc as the one in G’ for Φabc.
We callG’ acanonical graph of G regarding Φabc.Lemma 6.
For a pedigree graphG having one or more crossover individuals regarding 〈PAa,PAb,PAc〉, there exists a canonical graph G’ for G.Proof (Sketch).
The proof is by induction on the number of crossover individuals.
Induction hypothesis: assume that ifG has k or less crossovers, there is a canonical graph G’ for G.
In the induction step, letGk+1 be a graph with k+1 crossovers; let s be the lowest crossover between paths PAa and PAb in Gk+1. We apply the splitting operator on s in Gk+1 and obtain Gk having k crossovers by Lemma 4.


#### 3.1.5. Path-Counting Formula forΦabc

Now, we present the path-counting formula forΦabc:
(12)Φabc=∑A(∑Type1(12)LtripleΦAAAvvvv+∑Type2(12)Ltriple+1ΦAA),
where  ΦAA=(1/2)(1+FA), ΦAAA=(1/4)(1+3FA),FA: the inbreeding coefficient of A, A: a triple-common ancestor of a, b, and c,  Type 1: 〈PAa,PAb,PAc〉 has zero root 2-overlap,  Type 2: 〈PAa,PAb,PAc〉 has one root 2-overlap path PAs ending at the individual s(13)Ltriple={LPAa+LPAb+LPAcforType1LPAa+LPAb+LPAc-LPAsforType2,
and LPAa: the length of the path PAa (also applicable for PAa, PAc, and PAs).For completeness, the path-counting formula forΦaab is given in Appendix A; and the correctness proof of the path-counting formula is given in Appendix B.


### 3.2. Path-Counting Formulas for Four Individuals

#### 3.2.1. Path-Pair Level Graphical Representation of〈PAa,PAb,PAc,PAd〉

Given a path-quad〈PAa,PAb,PAc,PAd〉 and Quad_C(PAa,PAb,PAc,PAd)=∅, the path-quad can have 11 scenarios S0–S10 shown in Figure 10 where all four paths are considered symmetrically.Figure 10
A path-pair level graphical representation of〈PAa,PAb,PAc,PAd〉.In Figure11, we introduce three building blocks {B1,B2,B3}. For B1 and B2, the rules presented in Figure 7 are also applicable for Figure 11. For B3, we only consider root overlap, because the crossover individuals can be eliminated by using the splitting operator introduced in Section 3.1.4. Note that for B3, if Tri_C(PAa,PAb,PAc)=∅, then it is equivalent to the scenario S3 in Figure 8 Therefore, we only need to consider B3 when Tri_C(PAa,PAb,PAc)≠∅.Figure 11
Building blocks for all scenarios of〈PAa,PAb,PAc,PAd〉.


#### 3.2.2. Building Block-Based Cases Construction for〈PAa,PAb,PAc,PAd〉

For a scenarioSi(0≤i≤10) in Figure 11, we first decompose Si to one or multiple building blocks. For a scenario Si∈{S1,S3}, it has only one building block, and all acceptable cases can be obtained directly. For S2={u1=B1,u2=B1}, there is no need to consider the conflict between the edges in u1 and u2 because u1 and u2 are disconnected. Let Ri denote all acceptable cases of the path-pairs in ui, and let Ti denote all acceptable cases for Si. Therefore, we obtain T2=R1×R2 where × denotes the Cartesian product operator from relational algebra.ForS6={u1=B3}, we obtain T6=R1. For Si∈{Si∣4≤i≤10andi≠6}, we define the largest subgraph of Si based on which we construct Ti.Definition 7 (Largest Subgraph).
Given a scenarioSi(4≤i≤10 and i≠6),the largest subgraph of Si, denoted as Sj, is defined as follows:(1)
Sj is a proper subgraph of Si;(2)
ifSi contains B3, then Sj must also contain B3;(3)
no suchSk exists that Sj is a proper subgraph of Sk while Sk is also a proper subgraph of Si.For each scenarioSi(4≤i≤10 and i≠6), we list the largest subgraph of Si, denoted as Sj, in Table 2.Table 2
Largest subgraph of a scenarioSi (4≤i≤10 and i≠6).
S
i
S
4
S
5
S
7
S
8
S
9
S
10
S
j
S
3
S
3
S
6
S
5
S
7
S
9For a scenarioSi(4≤i≤10 and i≠6), let Diff(Si∖Sj) denote the set of building blocks in Si but not in Sj, where Sj is the largest subgraph of Si. Let |Ei| and |Ej| denote the number of edges in Si and Sj, respectively. According to Table 2, we can conclude that |Ei|-|Ej|=1. In order to leverage the dependency among building blocks, we consider only B2 in Diff(Si∖Sj). For example, Diff(S5∖S3)={B2}. Let T3 denote all acceptable cases for S3. And let R1 denote the set of acceptable cases for Diff(S5∖S3). Then, we can use S3 and Diff(S5∖S3) to construct all acceptable cases for S5. Then, we apply this idea for constructing all acceptable cases for each Si in Table 2.Given a path-quad〈PAa,PAb,PAc,PAd〉, an acceptable case has the following properties:(1)
if there is one root 3-overlap path, there can be at most one root 2-overlap path;(2)
otherwise, there can be at most two root 2-overlap paths.


#### 3.2.3. Path-Counting Formula forΦabcd

Now, we present the path-counting formula forΦabcd as follows:
(14)Φabcd=∑A(∑Type1(12)LquadΦAAAAvvvv+∑Type2(12)Lquad+1ΦAAAvvvv+∑Type3(12)Lquad+2ΦAA),
where   ΦAA=(1/2)(1+FA), ΦAAA=(1/4)(1+3FA), ΦAAAA=(1/8)(1+7FA),FA: the inbreeding coefficient of A, A: a quad-common ancestor of a, b, c, and d, Type 1: zero root 2-overlap and zero root 3-overlap path, Type 2: one root 2-overlap path PAs ending at s(15)Type3:{Case  1: tworoot 2-overlap pathsPAs1,PAs2endingats1ands2,respectivelyCase  2: oneroot 3-overlap pathPAtendingattCase  3: oneroot 2-overlap pathPAs,one root 3-overlappathPAtendingatsandt,respectively,Lquad={LPAa+LPAb+LPAc+LPAdforType1LPAa+LPAb+LPAc+LPAd-LPAsforType2LPAa+LPAb+LPAc+LPAd-LPAs1-LPAs2forCase1∈Type3LPAa+LPAb+LPAc+LPAd-2*LPAtforCase2∈Type3LPAa+LPAb+LPAc+LPAd-LPAt-LPAsforCase3∈Type3,
and LPAa: the length of the path PAa (also applicable for PAb,PAc,PAd, etc.).For completeness, the path-counting formulas forΦaabc and Φaaab are presented in Appendix A. The correctness of the path-counting formula for four individuals is proven in Appendix C.


### 3.3. Path-Counting Formulas for Two Pairs of Individuals

#### 3.3.1. Terminology and Definitions

(1) 2-Pair-Path-Pair. It consists of two pairs of path-pairs denoted as 〈(PSa,PSb),(PTc,PTd)〉, where PSa∈P(S,a),PSb∈P(S,b),PTc∈P(T,c),PTd∈P(T,d), S is a common ancestor of a and b, and T is a common ancestor of c and d. If A=S=T, then A is aquad-common ancestor of a, b, c, and d.(2) Homo-Overlap and Heter-Overlap Individual. Given two pairs of individuals 〈a,b〉and〈c,d〉, if s∈Bi_C(PAa,PAb) (or s∈Bi_C(PAc,PAd), we call s ahomo-overlap individual when PAa and PAb (or PAc and PAd) pass through thesame parent of s. If r∈Bi_C(PAi,PAj), where i∈{a,b} and j∈{c,d}, we call r aheter-overlap individual when PAi and PAj pass through thesame parent of r.(3) Root Homo-Overlap and Heter-Overlap Path. Given a 2-pair-path-pair 〈(PAa,PAb),(PAc,PAd)〉, if s is a homo-overlap individual and the homo-overlap path extends all the way to the quad-common ancestor A, then we call it aroot homo-overlap path. If r is a heter-overlap individual and the heter-overlap path extends all the way to the quad-common ancestor A, then we call it aroot heter-overlap path.Example 8.
A isquad-common ancestor for a, b, c, and d in Figure 12. For (a), s is ahomo-overlap individual between PAa and PAb.
t is ahomo-overlap individual between PAc and PAd. And, A→s and A→t areroot homo-overlap paths. For (b), x is aheter-overlap individual between PAa and PAd. y is aheter-overlap individual between PAb and PAc. And A→x and A→y areroot heter-overlap paths.Examples of 2-pair-path-quads forΦab,cd.
(a)
(b)


#### 3.3.2. Path-Counting Formula forΦab,cd

Now, we present a path-pair level graphical representation for〈(PAa,PAb),(PAc,PAd)〉 shown in Figure 13. The options for an edge can be {T,X,TX}. (Refer to Section 3.1.1 for definitions of T,X, and TX). Based on the different types of 〈PAa,PAb,PAc,PAd〉 presented in (14), all cases for 〈(PAa,PAb),(PAc,PAd)〉 are summarized in Table 3, where h is the last individual of a root homo-overlap path PAh (i.e., the path PAh ending at h) and r1 and r2 are the last individuals of root heter-overlap paths PAr1 and PAr2, respectively.Table 3
A summary of all cases for〈(PAa,PAb),(PAc,PAd)〉.
〈
P
A
a
,
P
A
b
,
P
A
c
,
P
A
d
〉
〈
(
P
A
a
,
P
A
b
)
,
(
P
A
c
,
P
A
d
)
〉
Zero root 2-overlap andzero root 3-overlap
Zero root homo-overlap and zero root heter-overlap
One root 2-overlap path
One root homo-overlap and zero root heter-overlap
Zero root homo-overlap and one root heter-overlap
Two root 2-overlap paths
Two root homo-overlaps and zero root heter-overlap
Zero root homo-overlap and two root heter-overlaps
One root 3-overlap path
One root homo-overlap and two root heter-overlaps, andh=r1=r2
One root 2-overlap and one root 3-overlap
One root homo-overlap and two root heter-overlaps, andr1=r2≠h
One root homo-overlap and two root heter-overlaps, andh=r1≠r2Figure 13
Scenarios of〈(PAa,PAb),(PAc,PAd)〉 at path-pair level.Given a pedigree graph having one or multiple progenitors{pi∣i>0}, we define that the generation of a progenitor pi is 0, denoted as gen(pi)=0. If an individual a has only one parent p, then we define gen(a)=gen(p)+1. If an individual a has two parents f and m, we define gen(a)=MAX{gen(f),gen(m)}+1.The path-counting formula forΦab,cd is as follows:
(16)Φab,cd=∑A(∑Type1(12)L2-pairΦAAA+∑Type2(12)L2-pair+1ΦAAAvvvv+∑Type3(12)L2-pair+2ΦAAvvvv+∑Type4(12)L2-pair+1ΦAA)+∑(S,T)∈Type5(12)L〈PSa,PSb〉+L〈PTc,PTd〉+1ΦBB,
where A: a quad-common ancestor of a, b, c, and d, S: a common ancestor of a and b, and T: a common ancestor of c and d. For 〈(PAa,PAb),(PAc,PAd)〉(S=T=A), there are four types (i.e., Type 1 to Type 4).Type 1: zero root homo-overlap and zero root heter-overlap.Type 2: zero root homo-overlap and one root heter-overlapPAr ending at r,
(17)Type3:{zeroroothomo-overlapandtworootheter-overlapPAr1andPAr2endingatr1andr2,respectively,oneroothomo-overlapPAhendingathandtworootheter-overlapPAr1andPAr2endingatr1andr2,andr1≠r2.Type 4: one root homo-overlapPAh ending at h and two root heter-overlap ending at r1 andr2, andh=r1=r2. For 〈(PSa,PSb),(PTc,PTd)〉(S≠T), there is one type (i.e., Type 5).Type 5:〈PSa,PSb〉 has zero overlap individual, 〈PTc,PTd〉 has zero overlap individual.At most one path-pair(either〈PSa,PSb〉or〈PTc,PTd〉)can have crossover individuals.Between a path from〈PSa,PSb〉 and a path from 〈PTc,PTd〉, there are no overlap individuals, but there can be crossover individuals, x, where x≠S and x≠T:(18)B={Swhengen(S)<gen(T)Swhengen(S)=gen(T)andThastwoparentsTotherwise,L2-pair={LPAa+LPAb+LPAc+LPAdforType1LPAa+LPAb+LPAc+LPAd-LPArforType2LPAa+LPAb+LPAc+LPAd-LPAr1-LPAr2forType3LPAa+LPAb+LPAc+LPAd-2*LPAhforType4,L〈PSa,PSb〉=LPSa+LPSbforType5,L〈PTc,PTd〉=LPTc+LPTdforType5.Note that if〈a,b〉 and 〈c,d〉 have zero quad-common ancestors, we have the following formula for Φab,cd:
(19)Φab,cd=∑(S,T)∈Type6(12)L〈PSa,PSb〉+L〈PTc,PTd〉ΦSS*ΦTT.
Type  6:〈PSa,PSb〉 is a nonoverlapping path-pair and 〈PTc,PTd〉is a nonoverlapping path-pair. Between a path from 〈PSa,PSb〉 and a path from 〈PTc,PTd〉, there are no overlap individuals, but there can be crossover individuals.L
〈
P
S
a
,
P
S
b
〉 and L〈PTc,PTd〉 are defined as in Type 5.The correctness of the path-counting formula forΦab.cd is proven in Appendix C. For completeness, please refer to [18] for the path-counting formulas for Φaa,bc, Φab,ac, Φab,ab, and Φaa,ab.


### 3.4. Experimental Results

In this section, we show the efficiency of our path-counting method using NodeCodes for condensed identity coefficients by making comparisons with the performance of a recursive method used in [10]. We implemented two methods: (1) using recursive formulas to compute each required kinship coefficient and generalized kinship coefficient; (2) using path-counting method coupled with NodeCodes to compute each required kinship coefficient and generalized kinship coefficient independently. We refer to the first method asRecursive, the second method asNodeCodes. For completeness, please refer to [18] for the details of the NodeCodes-based method.Nodecodes of a node is a set of labels each representing a path to the node from its ancestors. Given a pedigree graph, letr be the progenitor (i.e., the node with 0 in-degree). (For simplicity, we assume there is one progenitor, r, as the ancestor of all individuals in the pedigree. Otherwise, a virtual node r can be added to the pedigree graph and all progenitors can be made children of r.)   For each node u in the graph, the set of NodeCodes of u, denoted as NC(u), are assigned using a breadth-first-search traversal starting from r as follows.(1)
Ifu is r then NC(r) contains only one element: the empty string.(2)
Otherwise, letu be a node with NC(u), and v0,v1,…,vk be u’s children in sibling order; then for each x in NC(u), a code xi* is added to NC(vi), where 0≤i≤k, and * indicates the gender of the individual represented by node vi.Computations of kinship coefficients for two individuals and generalized kinship coefficients for three individuals presented in [11, 12, 14, 15] are using NodeCodes. The NodeCodes-based computation schemes can also be applied for the generalized kinship coefficients for four individuals and two pairs of individuals. For completeness, please refer to [18] for the details using NodeCodes to compute the generalized kinship coefficients for four individuals and two pairs of individuals based on our proposed path-counting formulas in Sections 3.2 and 3.3.In order to test the scalability of our approach for calculating condensed identity coefficients on large pedigrees, we used a population simulator implemented in [11] to generate arbitrarily large pedigrees. The population simulator is based on the algorithm for generating populations with overlapping generations in Chapter 4 of [19] along with the parameters given in Appendix B of [20] to model the relatively isolated Finnish Kainuu subpopulation and its growth during the years 1500–2000. An overview of the generation algorithm was presented in [11, 12, 14]. The parameters include starting/ending year, initial population size, initial age distribution, marriage probability, maximum age at pregnancy, expected number of children by time period, immigration rate, and probability of death by time period and age group.We examine the performance of condensed identity coefficients using twelve synthetic pedigrees which range from 75 individuals to 195,197 individuals. The smallest pedigree spans 3 generations, and the largest pedigree spans 19 generations. We analyzed the effects of pedigree size and the depth of individuals in the pedigree (the longest path between the individual and a progenitor) on the computation efficiency improvement.In the first experiment, 300 random pairs were selected from each of our 12 synthetic pedigrees. Figure14 shows computation efficiency improvement for each pedigree. As can be seen, the improvement ofNodeCodes overRecursive grew increasingly larger as the pedigree size increased, from a comparable amount of 26.83% on the smallest pedigree to 94.75% on the largest pedigree. It also shows that path-counting method coupled with NodeCodes can scale very well on large pedigrees in terms of computing condensed identity coefficients.Figure 14
The effect of pedigree size on computation efficiency improvement.In our next experiment, we examined the effect of the depth of the individual in the pedigree on the query time. For each depth, we generated 300 random pairs from the largest synthetic pedigree.Figure15 shows the effect of depth on the computation efficiency improvement. We can see the improvement ofNodeCodes overRecursive, ranging from 86.48% to 91.30%.Figure 15
The effect of depth on computation efficiency improvement.


## 3.1. Path-Counting Formulas for Three Individuals

We first introduce a systematic method to generate all possible cases for a path-pair. Then we discuss building blocks for path-triples and identify all acceptable cases which are used in deriving the path-counting formula forΦabc.


### 3.1.1. Cases for a Path-Pair

Given a path-pair〈PAa,PAb〉 with Bi_C(PAa,PAb)≠NULL, where A is a common ancestor of a and b and Bi_C(PAa,PAb) consists of all common individuals shared between PAa and PAb, except A, we introduce three patterns (i.e.,crossover, 2-overlap, androot 2-overlap) to generate all possible cases for 〈PAa,PAb〉.(1)
X(PAa,PAb): PAa and PAb share one or multiple crossover individuals.(2)
T(PAa,PAb): PAa and PAb are root 2-overlapping from A, and the root 2-overlap path can have one or multiple 2-overlap individuals.(3)
Y(PAa,PAb): PAa and PAb are overlapping but not from A, and the 2-overlap path can have one or multiple 2-overlap individuals.Based on the three patterns,X(PAa,PAb), T(PAa,PAb), and Y(PAa,PAb), we use regular expressions to generate all possible cases for the path-pair 〈PAa,PAb〉. For convenience, we drop 〈PAa,PAb〉 and use X,T, and Y instead of patterns X(PAa,PAb), T(PAa,PAb), and Y(PAa,PAb), whenever there is no confusion. When Bi_C(PAa,PAb)≠NULL, the eight cases shown in (7) cover all possible cases for 〈PAa,PAb〉. The completeness of eight cases shown in (7) for 〈PAa,PAb〉 can be proved by induction on the total number of T, X, and Y appearing in 〈PAa,PAb〉. Using the pedigree in Figure 2, Cases 1–3 and Case 6 are illustrated in (8), (9), (10), and (11):
(7){Case1:TCase2:X+Case3:TX+Case4:T(X+Y)+,{Case5:T(X+Y)+X+Case6:X+YCase7:X+(YX+)+Case8:X+(YX+)+Y,(8)A⟶s⟶e⟶t⟶aA⟶s⟶e⟶t⟶b}∈T,
where {s,e,t} are 2-overlap individuals and the overlap path is a root 2-overlap path:
(9)A⟶s⟶e⟶t⟶aA⟶s⟶f⟶t⟶b}∈TX,
where s is a 2-overlap individual and the overlap path is a root 2-overlap path; t is a crossover individual:
(10)A⟶s⟶e⟶t⟶aA⟶d⟶f⟶t⟶b}∈X,
where t is a crossover individual:
(11)A⟶c⟶e⟶t⟶aA⟶s⟶e⟶t⟶b}∈XY,
where e is a crossover individual; t is a 2-overlap individual and the overlap path is a 2-overlap path.


### 3.1.2. Path-Pair Level Graphical Representation of a Path-Triple

Given a path-triple〈PAa,PAb,PAc〉, we represent each path as a node. The path-triple can be decomposed to three path-pairs (i.e., 〈PAa,PAb〉, 〈PAa,PAc〉, and 〈PAb,PAc〉). For each path-pair, if the two paths share at least one common individual (i.e., either 2-overlap individual or crossover individual), except A, then there is an edge between the two nodes representing the two paths. Therefore, we obtain four different scenarios S0–S3, shown in Figure 5.Figure 5
A path-pair level graphical representation of〈PAa,PAb,PAc〉.In Figure5, the scenario S0 has no edges, so it means that 〈PAa,PAb,PAc〉 consists of three independent paths. In Figure 2,path-triple1 is an example of S0. Next, we introduce a lemma which can assist with identifying the options for the edges in the scenarios S1–S3.Lemma 3.
Given a path-triple〈PAa,PAb,PAc〉, consider the three path-pairs 〈PAa,PAb〉, 〈PAa,PAc〉, and 〈PAb,PAc〉, if there is a 2-overlap edge which is represented by Y in regular expression representation of any of the three path-pairs, and then the path-triple 〈PAa,PAb,PAc〉 has no contribution to Φabc.Proof.
In [17], Nadot and Vaysseix proposed, from a genetic and biological point of view, that Φabc can be evaluated by enumerating all eligible inheritance paths at allele-level starting from a triple common ancestor A to the three individuals a, b, and c.
For the pedigree in Figure6, let us consider the path-triple 〈PAa,PAb,PAc〉 listed as follows. PAa:A→a; PAb:A→p3→p6→p7→b; PAc:A→p4→p6→p7→c.
For〈PAb,PAc〉,   p6 is a crossover individual,   p7 is an overlap individual, and p6→p7 is a 2-overlap edge represented by Y in regular expression representation (see the definition for Y in Section 3.1.1).
For the individualp6, let us denote the two alleles at one fixed autosomal locus as g1 and g2. At allele-level, only one allele can be passed down from p6 to p7. Since p3 and p4 are parents of p6,g1 is passed down from one parent, and g2 is passed down from the other parent. It is infeasible to pass down both g1 and g2 from p6 to p7. In other words, there are no corresponding inheritance paths for the path-triple 〈PAa,PAb,PAc〉 with a 2-overlap edge between 〈PAb,PAc〉 (i.e., Case 6: XY). Therefore, such kind of path-triples has no contribution to Φabc.Examples of pedigree and inheritance paths.
(a)
Pedigree
(b)
Inheritance pathsFigure6(b) shows one example of eligible inheritance paths corresponding to a pedigree graph. Each individual is represented by two allele nodes. The eligible inheritance paths in Figure 6(b) consist of red edges only.Only Case 1, Case 2, and Case 3 do not haveY in the regular expression representation of a path-pair (see (7)); considering the scenarios S1–S3 shown in Figure 5, an edge can have three options {Case1:T;Case2:X;Case3:TX}.


### 3.1.3. Constructing Cases for a Path-Triple

For the scenariosS1–S3 in Figure 5, we define two building blocks {B1,B2} along with some rules in Figure 7 to generate acceptable cases. For B1, the edge can have three options {Case1:T;Case2:X;Case3:TX}. For B2, we cannot allow both edges to be root overlap, because if two edges are root overlap, then PAa and PAc must share at least one common individual, except A, which contradicts the fact that PAa and PAc have no edge.Figure 7
Building blocks{B1,B2} and basic rules.Next, we focus on generating all acceptable cases for the scenariosS1–S3 in Figure 5, where only S3 contains more than one building block. In order to leverage the dependency among building blocks, we decompose S3 to S3={u1=B2,u2=B2,u3=B2}, shown in Figure 8. For each ui, we have a set of acceptable path-triples, denoted as Ri.Figure 8
A graphical illustration for obtainingT3.Considering the dependency among{R1,R2,R3}, we use the natural join operator, denoted as ⋈, operating on {R1,R2,R3} to generate all acceptable cases for S3. As a result, we obtain T3=R1⋈R2⋈R3, where T3 denotes the acceptable cases of the path-triple 〈PAa,PAb,PAc〉 in the scenario S3.For each scenario in Figure5, we generate all acceptable cases for 〈PAa,PAb,PAc〉. The scenario S0 has no edges, and it shows that 〈PAa,PAb,PAc〉 consists of three independent paths, while, for the other scenarios Sk (k=1,2,3), the k edges can have two options:(1)
allk edges belong tocrossover; or(2)
one edge belongs toroot 2-overlap; the remaining (k-1) edges belong tocrossover.In summary, acceptable path-triples can have at most one root 2-overlap path, any number of crossover individuals, but zero 2-overlap path.


### 3.1.4. Splitting Operator

Considering the existence of root 2-overlap path and crossover in acceptable path-triples, we propose a splitting operator to transform a path-triple with crossover individuals to a noncrossover path-triple without changing the contribution from this path-triple toΦabc. The main purpose of using the splitting operator is to simplify the path-counting formula derivation process. We first use an example in Figure 9 to illustrate how the splitting operator works. In Figure 9, there is a crossover individual s between PAa and PAb in the path triple 〈PAa,PAb,PAc〉 in Gk+1. The splitting operator proceeds as follows:(1)
split the nodes to two nodes, s1 and s2;(2)
transform the edgess→a’ and s→b’ to s1→a’ and s2→b’, respectively;(3)
add two new edges,s2→a’ and s1→b’.Figure 9
Transforming pedigree graphGk+1 having k+1 crossover to Gk having k crossover.Lemma 4.
Given a pedigree graphGk+1 having (k+1) crossover individuals regarding 〈PAa,PAb,PAc〉 shown in Figure 9, let s denote the lowest crossover individual, where no descendant of s can be a crossover individual among the three paths PAa, PAb, and PAc. After using the splitting operator for the lowest crossover individual s in Gk+1, the number of crossover individuals in Gk+1 is decreased by 1.Proof.
The splitting operator only affects the edges froms to a’ and b’. If there is a new crossover node appearing, the only possible node is either a’ or b’. Assume b’ becomes a crossover individual; it means that b’ is able to reach a and b from two separate paths. It contradicts the fact that s is the lowest crossover individual between PAa and PAb.Next, we introduce a canonical graph which results from applying the splitting operator for all crossover individuals. The canonical graph has zero crossover individual.Definition 5 (Canonical Graph).
Given a pedigree graphG having one or more crossover individuals regarding Φabc, If there exists a graph G’ which has no crossover individuals with regards to Φabc such that(i)
any acceptable path-triple inG has an acceptable path-triple in G’ which has the same contribution to Φabc as the one in G for Φabc;(ii)
any acceptable path-triple inG’ has an acceptable path-triple in G which and has the same contribution to Φabc as the one in G’ for Φabc.
We callG’ acanonical graph of G regarding Φabc.Lemma 6.
For a pedigree graphG having one or more crossover individuals regarding 〈PAa,PAb,PAc〉, there exists a canonical graph G’ for G.Proof (Sketch).
The proof is by induction on the number of crossover individuals.
Induction hypothesis: assume that ifG has k or less crossovers, there is a canonical graph G’ for G.
In the induction step, letGk+1 be a graph with k+1 crossovers; let s be the lowest crossover between paths PAa and PAb in Gk+1. We apply the splitting operator on s in Gk+1 and obtain Gk having k crossovers by Lemma 4.


### 3.1.5. Path-Counting Formula forΦabc

Now, we present the path-counting formula forΦabc:
(12)Φabc=∑A(∑Type1(12)LtripleΦAAAvvvv+∑Type2(12)Ltriple+1ΦAA),
where  ΦAA=(1/2)(1+FA), ΦAAA=(1/4)(1+3FA),FA: the inbreeding coefficient of A, A: a triple-common ancestor of a, b, and c,  Type 1: 〈PAa,PAb,PAc〉 has zero root 2-overlap,  Type 2: 〈PAa,PAb,PAc〉 has one root 2-overlap path PAs ending at the individual s(13)Ltriple={LPAa+LPAb+LPAcforType1LPAa+LPAb+LPAc-LPAsforType2,
and LPAa: the length of the path PAa (also applicable for PAa, PAc, and PAs).For completeness, the path-counting formula forΦaab is given in Appendix A; and the correctness proof of the path-counting formula is given in Appendix B.


## 3.1.1. Cases for a Path-Pair

Given a path-pair〈PAa,PAb〉 with Bi_C(PAa,PAb)≠NULL, where A is a common ancestor of a and b and Bi_C(PAa,PAb) consists of all common individuals shared between PAa and PAb, except A, we introduce three patterns (i.e.,crossover, 2-overlap, androot 2-overlap) to generate all possible cases for 〈PAa,PAb〉.(1)
X(PAa,PAb): PAa and PAb share one or multiple crossover individuals.(2)
T(PAa,PAb): PAa and PAb are root 2-overlapping from A, and the root 2-overlap path can have one or multiple 2-overlap individuals.(3)
Y(PAa,PAb): PAa and PAb are overlapping but not from A, and the 2-overlap path can have one or multiple 2-overlap individuals.Based on the three patterns,X(PAa,PAb), T(PAa,PAb), and Y(PAa,PAb), we use regular expressions to generate all possible cases for the path-pair 〈PAa,PAb〉. For convenience, we drop 〈PAa,PAb〉 and use X,T, and Y instead of patterns X(PAa,PAb), T(PAa,PAb), and Y(PAa,PAb), whenever there is no confusion. When Bi_C(PAa,PAb)≠NULL, the eight cases shown in (7) cover all possible cases for 〈PAa,PAb〉. The completeness of eight cases shown in (7) for 〈PAa,PAb〉 can be proved by induction on the total number of T, X, and Y appearing in 〈PAa,PAb〉. Using the pedigree in Figure 2, Cases 1–3 and Case 6 are illustrated in (8), (9), (10), and (11):
(7){Case1:TCase2:X+Case3:TX+Case4:T(X+Y)+,{Case5:T(X+Y)+X+Case6:X+YCase7:X+(YX+)+Case8:X+(YX+)+Y,(8)A⟶s⟶e⟶t⟶aA⟶s⟶e⟶t⟶b}∈T,
where {s,e,t} are 2-overlap individuals and the overlap path is a root 2-overlap path:
(9)A⟶s⟶e⟶t⟶aA⟶s⟶f⟶t⟶b}∈TX,
where s is a 2-overlap individual and the overlap path is a root 2-overlap path; t is a crossover individual:
(10)A⟶s⟶e⟶t⟶aA⟶d⟶f⟶t⟶b}∈X,
where t is a crossover individual:
(11)A⟶c⟶e⟶t⟶aA⟶s⟶e⟶t⟶b}∈XY,
where e is a crossover individual; t is a 2-overlap individual and the overlap path is a 2-overlap path.


## 3.1.2. Path-Pair Level Graphical Representation of a Path-Triple

Given a path-triple〈PAa,PAb,PAc〉, we represent each path as a node. The path-triple can be decomposed to three path-pairs (i.e., 〈PAa,PAb〉, 〈PAa,PAc〉, and 〈PAb,PAc〉). For each path-pair, if the two paths share at least one common individual (i.e., either 2-overlap individual or crossover individual), except A, then there is an edge between the two nodes representing the two paths. Therefore, we obtain four different scenarios S0–S3, shown in Figure 5.Figure 5
A path-pair level graphical representation of〈PAa,PAb,PAc〉.In Figure5, the scenario S0 has no edges, so it means that 〈PAa,PAb,PAc〉 consists of three independent paths. In Figure 2,path-triple1 is an example of S0. Next, we introduce a lemma which can assist with identifying the options for the edges in the scenarios S1–S3.Lemma 3.
Given a path-triple〈PAa,PAb,PAc〉, consider the three path-pairs 〈PAa,PAb〉, 〈PAa,PAc〉, and 〈PAb,PAc〉, if there is a 2-overlap edge which is represented by Y in regular expression representation of any of the three path-pairs, and then the path-triple 〈PAa,PAb,PAc〉 has no contribution to Φabc.Proof.
In [17], Nadot and Vaysseix proposed, from a genetic and biological point of view, that Φabc can be evaluated by enumerating all eligible inheritance paths at allele-level starting from a triple common ancestor A to the three individuals a, b, and c.
For the pedigree in Figure6, let us consider the path-triple 〈PAa,PAb,PAc〉 listed as follows. PAa:A→a; PAb:A→p3→p6→p7→b; PAc:A→p4→p6→p7→c.
For〈PAb,PAc〉,   p6 is a crossover individual,   p7 is an overlap individual, and p6→p7 is a 2-overlap edge represented by Y in regular expression representation (see the definition for Y in Section 3.1.1).
For the individualp6, let us denote the two alleles at one fixed autosomal locus as g1 and g2. At allele-level, only one allele can be passed down from p6 to p7. Since p3 and p4 are parents of p6,g1 is passed down from one parent, and g2 is passed down from the other parent. It is infeasible to pass down both g1 and g2 from p6 to p7. In other words, there are no corresponding inheritance paths for the path-triple 〈PAa,PAb,PAc〉 with a 2-overlap edge between 〈PAb,PAc〉 (i.e., Case 6: XY). Therefore, such kind of path-triples has no contribution to Φabc.Examples of pedigree and inheritance paths.
(a)
Pedigree
(b)
Inheritance pathsFigure6(b) shows one example of eligible inheritance paths corresponding to a pedigree graph. Each individual is represented by two allele nodes. The eligible inheritance paths in Figure 6(b) consist of red edges only.Only Case 1, Case 2, and Case 3 do not haveY in the regular expression representation of a path-pair (see (7)); considering the scenarios S1–S3 shown in Figure 5, an edge can have three options {Case1:T;Case2:X;Case3:TX}.


## 3.1.3. Constructing Cases for a Path-Triple

For the scenariosS1–S3 in Figure 5, we define two building blocks {B1,B2} along with some rules in Figure 7 to generate acceptable cases. For B1, the edge can have three options {Case1:T;Case2:X;Case3:TX}. For B2, we cannot allow both edges to be root overlap, because if two edges are root overlap, then PAa and PAc must share at least one common individual, except A, which contradicts the fact that PAa and PAc have no edge.Figure 7
Building blocks{B1,B2} and basic rules.Next, we focus on generating all acceptable cases for the scenariosS1–S3 in Figure 5, where only S3 contains more than one building block. In order to leverage the dependency among building blocks, we decompose S3 to S3={u1=B2,u2=B2,u3=B2}, shown in Figure 8. For each ui, we have a set of acceptable path-triples, denoted as Ri.Figure 8
A graphical illustration for obtainingT3.Considering the dependency among{R1,R2,R3}, we use the natural join operator, denoted as ⋈, operating on {R1,R2,R3} to generate all acceptable cases for S3. As a result, we obtain T3=R1⋈R2⋈R3, where T3 denotes the acceptable cases of the path-triple 〈PAa,PAb,PAc〉 in the scenario S3.For each scenario in Figure5, we generate all acceptable cases for 〈PAa,PAb,PAc〉. The scenario S0 has no edges, and it shows that 〈PAa,PAb,PAc〉 consists of three independent paths, while, for the other scenarios Sk (k=1,2,3), the k edges can have two options:(1)
allk edges belong tocrossover; or(2)
one edge belongs toroot 2-overlap; the remaining (k-1) edges belong tocrossover.In summary, acceptable path-triples can have at most one root 2-overlap path, any number of crossover individuals, but zero 2-overlap path.


## 3.1.4. Splitting Operator

Considering the existence of root 2-overlap path and crossover in acceptable path-triples, we propose a splitting operator to transform a path-triple with crossover individuals to a noncrossover path-triple without changing the contribution from this path-triple toΦabc. The main purpose of using the splitting operator is to simplify the path-counting formula derivation process. We first use an example in Figure 9 to illustrate how the splitting operator works. In Figure 9, there is a crossover individual s between PAa and PAb in the path triple 〈PAa,PAb,PAc〉 in Gk+1. The splitting operator proceeds as follows:(1)
split the nodes to two nodes, s1 and s2;(2)
transform the edgess→a’ and s→b’ to s1→a’ and s2→b’, respectively;(3)
add two new edges,s2→a’ and s1→b’.Figure 9
Transforming pedigree graphGk+1 having k+1 crossover to Gk having k crossover.Lemma 4.
Given a pedigree graphGk+1 having (k+1) crossover individuals regarding 〈PAa,PAb,PAc〉 shown in Figure 9, let s denote the lowest crossover individual, where no descendant of s can be a crossover individual among the three paths PAa, PAb, and PAc. After using the splitting operator for the lowest crossover individual s in Gk+1, the number of crossover individuals in Gk+1 is decreased by 1.Proof.
The splitting operator only affects the edges froms to a’ and b’. If there is a new crossover node appearing, the only possible node is either a’ or b’. Assume b’ becomes a crossover individual; it means that b’ is able to reach a and b from two separate paths. It contradicts the fact that s is the lowest crossover individual between PAa and PAb.Next, we introduce a canonical graph which results from applying the splitting operator for all crossover individuals. The canonical graph has zero crossover individual.Definition 5 (Canonical Graph).
Given a pedigree graphG having one or more crossover individuals regarding Φabc, If there exists a graph G’ which has no crossover individuals with regards to Φabc such that(i)
any acceptable path-triple inG has an acceptable path-triple in G’ which has the same contribution to Φabc as the one in G for Φabc;(ii)
any acceptable path-triple inG’ has an acceptable path-triple in G which and has the same contribution to Φabc as the one in G’ for Φabc.
We callG’ acanonical graph of G regarding Φabc.Lemma 6.
For a pedigree graphG having one or more crossover individuals regarding 〈PAa,PAb,PAc〉, there exists a canonical graph G’ for G.Proof (Sketch).
The proof is by induction on the number of crossover individuals.
Induction hypothesis: assume that ifG has k or less crossovers, there is a canonical graph G’ for G.
In the induction step, letGk+1 be a graph with k+1 crossovers; let s be the lowest crossover between paths PAa and PAb in Gk+1. We apply the splitting operator on s in Gk+1 and obtain Gk having k crossovers by Lemma 4.


## 3.1.5. Path-Counting Formula forΦabc

Now, we present the path-counting formula forΦabc:
(12)Φabc=∑A(∑Type1(12)LtripleΦAAAvvvv+∑Type2(12)Ltriple+1ΦAA),
where  ΦAA=(1/2)(1+FA), ΦAAA=(1/4)(1+3FA),FA: the inbreeding coefficient of A, A: a triple-common ancestor of a, b, and c,  Type 1: 〈PAa,PAb,PAc〉 has zero root 2-overlap,  Type 2: 〈PAa,PAb,PAc〉 has one root 2-overlap path PAs ending at the individual s(13)Ltriple={LPAa+LPAb+LPAcforType1LPAa+LPAb+LPAc-LPAsforType2,
and LPAa: the length of the path PAa (also applicable for PAa, PAc, and PAs).For completeness, the path-counting formula forΦaab is given in Appendix A; and the correctness proof of the path-counting formula is given in Appendix B.


## 3.2. Path-Counting Formulas for Four Individuals

### 3.2.1. Path-Pair Level Graphical Representation of〈PAa,PAb,PAc,PAd〉

Given a path-quad〈PAa,PAb,PAc,PAd〉 and Quad_C(PAa,PAb,PAc,PAd)=∅, the path-quad can have 11 scenarios S0–S10 shown in Figure 10 where all four paths are considered symmetrically.Figure 10
A path-pair level graphical representation of〈PAa,PAb,PAc,PAd〉.In Figure11, we introduce three building blocks {B1,B2,B3}. For B1 and B2, the rules presented in Figure 7 are also applicable for Figure 11. For B3, we only consider root overlap, because the crossover individuals can be eliminated by using the splitting operator introduced in Section 3.1.4. Note that for B3, if Tri_C(PAa,PAb,PAc)=∅, then it is equivalent to the scenario S3 in Figure 8 Therefore, we only need to consider B3 when Tri_C(PAa,PAb,PAc)≠∅.Figure 11
Building blocks for all scenarios of〈PAa,PAb,PAc,PAd〉.


### 3.2.2. Building Block-Based Cases Construction for〈PAa,PAb,PAc,PAd〉

For a scenarioSi(0≤i≤10) in Figure 11, we first decompose Si to one or multiple building blocks. For a scenario Si∈{S1,S3}, it has only one building block, and all acceptable cases can be obtained directly. For S2={u1=B1,u2=B1}, there is no need to consider the conflict between the edges in u1 and u2 because u1 and u2 are disconnected. Let Ri denote all acceptable cases of the path-pairs in ui, and let Ti denote all acceptable cases for Si. Therefore, we obtain T2=R1×R2 where × denotes the Cartesian product operator from relational algebra.ForS6={u1=B3}, we obtain T6=R1. For Si∈{Si∣4≤i≤10andi≠6}, we define the largest subgraph of Si based on which we construct Ti.Definition 7 (Largest Subgraph).
Given a scenarioSi(4≤i≤10 and i≠6),the largest subgraph of Si, denoted as Sj, is defined as follows:(1)
Sj is a proper subgraph of Si;(2)
ifSi contains B3, then Sj must also contain B3;(3)
no suchSk exists that Sj is a proper subgraph of Sk while Sk is also a proper subgraph of Si.For each scenarioSi(4≤i≤10 and i≠6), we list the largest subgraph of Si, denoted as Sj, in Table 2.Table 2
Largest subgraph of a scenarioSi (4≤i≤10 and i≠6).
S
i
S
4
S
5
S
7
S
8
S
9
S
10
S
j
S
3
S
3
S
6
S
5
S
7
S
9For a scenarioSi(4≤i≤10 and i≠6), let Diff(Si∖Sj) denote the set of building blocks in Si but not in Sj, where Sj is the largest subgraph of Si. Let |Ei| and |Ej| denote the number of edges in Si and Sj, respectively. According to Table 2, we can conclude that |Ei|-|Ej|=1. In order to leverage the dependency among building blocks, we consider only B2 in Diff(Si∖Sj). For example, Diff(S5∖S3)={B2}. Let T3 denote all acceptable cases for S3. And let R1 denote the set of acceptable cases for Diff(S5∖S3). Then, we can use S3 and Diff(S5∖S3) to construct all acceptable cases for S5. Then, we apply this idea for constructing all acceptable cases for each Si in Table 2.Given a path-quad〈PAa,PAb,PAc,PAd〉, an acceptable case has the following properties:(1)
if there is one root 3-overlap path, there can be at most one root 2-overlap path;(2)
otherwise, there can be at most two root 2-overlap paths.


### 3.2.3. Path-Counting Formula forΦabcd

Now, we present the path-counting formula forΦabcd as follows:
(14)Φabcd=∑A(∑Type1(12)LquadΦAAAAvvvv+∑Type2(12)Lquad+1ΦAAAvvvv+∑Type3(12)Lquad+2ΦAA),
where   ΦAA=(1/2)(1+FA), ΦAAA=(1/4)(1+3FA), ΦAAAA=(1/8)(1+7FA),FA: the inbreeding coefficient of A, A: a quad-common ancestor of a, b, c, and d, Type 1: zero root 2-overlap and zero root 3-overlap path, Type 2: one root 2-overlap path PAs ending at s(15)Type3:{Case  1: tworoot 2-overlap pathsPAs1,PAs2endingats1ands2,respectivelyCase  2: oneroot 3-overlap pathPAtendingattCase  3: oneroot 2-overlap pathPAs,one root 3-overlappathPAtendingatsandt,respectively,Lquad={LPAa+LPAb+LPAc+LPAdforType1LPAa+LPAb+LPAc+LPAd-LPAsforType2LPAa+LPAb+LPAc+LPAd-LPAs1-LPAs2forCase1∈Type3LPAa+LPAb+LPAc+LPAd-2*LPAtforCase2∈Type3LPAa+LPAb+LPAc+LPAd-LPAt-LPAsforCase3∈Type3,
and LPAa: the length of the path PAa (also applicable for PAb,PAc,PAd, etc.).For completeness, the path-counting formulas forΦaabc and Φaaab are presented in Appendix A. The correctness of the path-counting formula for four individuals is proven in Appendix C.


## 3.2.1. Path-Pair Level Graphical Representation of〈PAa,PAb,PAc,PAd〉

Given a path-quad〈PAa,PAb,PAc,PAd〉 and Quad_C(PAa,PAb,PAc,PAd)=∅, the path-quad can have 11 scenarios S0–S10 shown in Figure 10 where all four paths are considered symmetrically.Figure 10
A path-pair level graphical representation of〈PAa,PAb,PAc,PAd〉.In Figure11, we introduce three building blocks {B1,B2,B3}. For B1 and B2, the rules presented in Figure 7 are also applicable for Figure 11. For B3, we only consider root overlap, because the crossover individuals can be eliminated by using the splitting operator introduced in Section 3.1.4. Note that for B3, if Tri_C(PAa,PAb,PAc)=∅, then it is equivalent to the scenario S3 in Figure 8 Therefore, we only need to consider B3 when Tri_C(PAa,PAb,PAc)≠∅.Figure 11
Building blocks for all scenarios of〈PAa,PAb,PAc,PAd〉.


## 3.2.2. Building Block-Based Cases Construction for〈PAa,PAb,PAc,PAd〉

For a scenarioSi(0≤i≤10) in Figure 11, we first decompose Si to one or multiple building blocks. For a scenario Si∈{S1,S3}, it has only one building block, and all acceptable cases can be obtained directly. For S2={u1=B1,u2=B1}, there is no need to consider the conflict between the edges in u1 and u2 because u1 and u2 are disconnected. Let Ri denote all acceptable cases of the path-pairs in ui, and let Ti denote all acceptable cases for Si. Therefore, we obtain T2=R1×R2 where × denotes the Cartesian product operator from relational algebra.ForS6={u1=B3}, we obtain T6=R1. For Si∈{Si∣4≤i≤10andi≠6}, we define the largest subgraph of Si based on which we construct Ti.Definition 7 (Largest Subgraph).
Given a scenarioSi(4≤i≤10 and i≠6),the largest subgraph of Si, denoted as Sj, is defined as follows:(1)
Sj is a proper subgraph of Si;(2)
ifSi contains B3, then Sj must also contain B3;(3)
no suchSk exists that Sj is a proper subgraph of Sk while Sk is also a proper subgraph of Si.For each scenarioSi(4≤i≤10 and i≠6), we list the largest subgraph of Si, denoted as Sj, in Table 2.Table 2
Largest subgraph of a scenarioSi (4≤i≤10 and i≠6).
S
i
S
4
S
5
S
7
S
8
S
9
S
10
S
j
S
3
S
3
S
6
S
5
S
7
S
9For a scenarioSi(4≤i≤10 and i≠6), let Diff(Si∖Sj) denote the set of building blocks in Si but not in Sj, where Sj is the largest subgraph of Si. Let |Ei| and |Ej| denote the number of edges in Si and Sj, respectively. According to Table 2, we can conclude that |Ei|-|Ej|=1. In order to leverage the dependency among building blocks, we consider only B2 in Diff(Si∖Sj). For example, Diff(S5∖S3)={B2}. Let T3 denote all acceptable cases for S3. And let R1 denote the set of acceptable cases for Diff(S5∖S3). Then, we can use S3 and Diff(S5∖S3) to construct all acceptable cases for S5. Then, we apply this idea for constructing all acceptable cases for each Si in Table 2.Given a path-quad〈PAa,PAb,PAc,PAd〉, an acceptable case has the following properties:(1)
if there is one root 3-overlap path, there can be at most one root 2-overlap path;(2)
otherwise, there can be at most two root 2-overlap paths.


## 3.2.3. Path-Counting Formula forΦabcd

Now, we present the path-counting formula forΦabcd as follows:
(14)Φabcd=∑A(∑Type1(12)LquadΦAAAAvvvv+∑Type2(12)Lquad+1ΦAAAvvvv+∑Type3(12)Lquad+2ΦAA),
where   ΦAA=(1/2)(1+FA), ΦAAA=(1/4)(1+3FA), ΦAAAA=(1/8)(1+7FA),FA: the inbreeding coefficient of A, A: a quad-common ancestor of a, b, c, and d, Type 1: zero root 2-overlap and zero root 3-overlap path, Type 2: one root 2-overlap path PAs ending at s(15)Type3:{Case  1: tworoot 2-overlap pathsPAs1,PAs2endingats1ands2,respectivelyCase  2: oneroot 3-overlap pathPAtendingattCase  3: oneroot 2-overlap pathPAs,one root 3-overlappathPAtendingatsandt,respectively,Lquad={LPAa+LPAb+LPAc+LPAdforType1LPAa+LPAb+LPAc+LPAd-LPAsforType2LPAa+LPAb+LPAc+LPAd-LPAs1-LPAs2forCase1∈Type3LPAa+LPAb+LPAc+LPAd-2*LPAtforCase2∈Type3LPAa+LPAb+LPAc+LPAd-LPAt-LPAsforCase3∈Type3,
and LPAa: the length of the path PAa (also applicable for PAb,PAc,PAd, etc.).For completeness, the path-counting formulas forΦaabc and Φaaab are presented in Appendix A. The correctness of the path-counting formula for four individuals is proven in Appendix C.


## 3.3. Path-Counting Formulas for Two Pairs of Individuals

### 3.3.1. Terminology and Definitions

(1) 2-Pair-Path-Pair. It consists of two pairs of path-pairs denoted as 〈(PSa,PSb),(PTc,PTd)〉, where PSa∈P(S,a),PSb∈P(S,b),PTc∈P(T,c),PTd∈P(T,d), S is a common ancestor of a and b, and T is a common ancestor of c and d. If A=S=T, then A is aquad-common ancestor of a, b, c, and d.(2) Homo-Overlap and Heter-Overlap Individual. Given two pairs of individuals 〈a,b〉and〈c,d〉, if s∈Bi_C(PAa,PAb) (or s∈Bi_C(PAc,PAd), we call s ahomo-overlap individual when PAa and PAb (or PAc and PAd) pass through thesame parent of s. If r∈Bi_C(PAi,PAj), where i∈{a,b} and j∈{c,d}, we call r aheter-overlap individual when PAi and PAj pass through thesame parent of r.(3) Root Homo-Overlap and Heter-Overlap Path. Given a 2-pair-path-pair 〈(PAa,PAb),(PAc,PAd)〉, if s is a homo-overlap individual and the homo-overlap path extends all the way to the quad-common ancestor A, then we call it aroot homo-overlap path. If r is a heter-overlap individual and the heter-overlap path extends all the way to the quad-common ancestor A, then we call it aroot heter-overlap path.Example 8.
A isquad-common ancestor for a, b, c, and d in Figure 12. For (a), s is ahomo-overlap individual between PAa and PAb.
t is ahomo-overlap individual between PAc and PAd. And, A→s and A→t areroot homo-overlap paths. For (b), x is aheter-overlap individual between PAa and PAd. y is aheter-overlap individual between PAb and PAc. And A→x and A→y areroot heter-overlap paths.Examples of 2-pair-path-quads forΦab,cd.
(a)
(b)


### 3.3.2. Path-Counting Formula forΦab,cd

Now, we present a path-pair level graphical representation for〈(PAa,PAb),(PAc,PAd)〉 shown in Figure 13. The options for an edge can be {T,X,TX}. (Refer to Section 3.1.1 for definitions of T,X, and TX). Based on the different types of 〈PAa,PAb,PAc,PAd〉 presented in (14), all cases for 〈(PAa,PAb),(PAc,PAd)〉 are summarized in Table 3, where h is the last individual of a root homo-overlap path PAh (i.e., the path PAh ending at h) and r1 and r2 are the last individuals of root heter-overlap paths PAr1 and PAr2, respectively.Table 3
A summary of all cases for〈(PAa,PAb),(PAc,PAd)〉.
〈
P
A
a
,
P
A
b
,
P
A
c
,
P
A
d
〉
〈
(
P
A
a
,
P
A
b
)
,
(
P
A
c
,
P
A
d
)
〉
Zero root 2-overlap andzero root 3-overlap
Zero root homo-overlap and zero root heter-overlap
One root 2-overlap path
One root homo-overlap and zero root heter-overlap
Zero root homo-overlap and one root heter-overlap
Two root 2-overlap paths
Two root homo-overlaps and zero root heter-overlap
Zero root homo-overlap and two root heter-overlaps
One root 3-overlap path
One root homo-overlap and two root heter-overlaps, andh=r1=r2
One root 2-overlap and one root 3-overlap
One root homo-overlap and two root heter-overlaps, andr1=r2≠h
One root homo-overlap and two root heter-overlaps, andh=r1≠r2Figure 13
Scenarios of〈(PAa,PAb),(PAc,PAd)〉 at path-pair level.Given a pedigree graph having one or multiple progenitors{pi∣i>0}, we define that the generation of a progenitor pi is 0, denoted as gen(pi)=0. If an individual a has only one parent p, then we define gen(a)=gen(p)+1. If an individual a has two parents f and m, we define gen(a)=MAX{gen(f),gen(m)}+1.The path-counting formula forΦab,cd is as follows:
(16)Φab,cd=∑A(∑Type1(12)L2-pairΦAAA+∑Type2(12)L2-pair+1ΦAAAvvvv+∑Type3(12)L2-pair+2ΦAAvvvv+∑Type4(12)L2-pair+1ΦAA)+∑(S,T)∈Type5(12)L〈PSa,PSb〉+L〈PTc,PTd〉+1ΦBB,
where A: a quad-common ancestor of a, b, c, and d, S: a common ancestor of a and b, and T: a common ancestor of c and d. For 〈(PAa,PAb),(PAc,PAd)〉(S=T=A), there are four types (i.e., Type 1 to Type 4).Type 1: zero root homo-overlap and zero root heter-overlap.Type 2: zero root homo-overlap and one root heter-overlapPAr ending at r,
(17)Type3:{zeroroothomo-overlapandtworootheter-overlapPAr1andPAr2endingatr1andr2,respectively,oneroothomo-overlapPAhendingathandtworootheter-overlapPAr1andPAr2endingatr1andr2,andr1≠r2.Type 4: one root homo-overlapPAh ending at h and two root heter-overlap ending at r1 andr2, andh=r1=r2. For 〈(PSa,PSb),(PTc,PTd)〉(S≠T), there is one type (i.e., Type 5).Type 5:〈PSa,PSb〉 has zero overlap individual, 〈PTc,PTd〉 has zero overlap individual.At most one path-pair(either〈PSa,PSb〉or〈PTc,PTd〉)can have crossover individuals.Between a path from〈PSa,PSb〉 and a path from 〈PTc,PTd〉, there are no overlap individuals, but there can be crossover individuals, x, where x≠S and x≠T:(18)B={Swhengen(S)<gen(T)Swhengen(S)=gen(T)andThastwoparentsTotherwise,L2-pair={LPAa+LPAb+LPAc+LPAdforType1LPAa+LPAb+LPAc+LPAd-LPArforType2LPAa+LPAb+LPAc+LPAd-LPAr1-LPAr2forType3LPAa+LPAb+LPAc+LPAd-2*LPAhforType4,L〈PSa,PSb〉=LPSa+LPSbforType5,L〈PTc,PTd〉=LPTc+LPTdforType5.Note that if〈a,b〉 and 〈c,d〉 have zero quad-common ancestors, we have the following formula for Φab,cd:
(19)Φab,cd=∑(S,T)∈Type6(12)L〈PSa,PSb〉+L〈PTc,PTd〉ΦSS*ΦTT.
Type  6:〈PSa,PSb〉 is a nonoverlapping path-pair and 〈PTc,PTd〉is a nonoverlapping path-pair. Between a path from 〈PSa,PSb〉 and a path from 〈PTc,PTd〉, there are no overlap individuals, but there can be crossover individuals.L
〈
P
S
a
,
P
S
b
〉 and L〈PTc,PTd〉 are defined as in Type 5.The correctness of the path-counting formula forΦab.cd is proven in Appendix C. For completeness, please refer to [18] for the path-counting formulas for Φaa,bc, Φab,ac, Φab,ab, and Φaa,ab.


## 3.3.1. Terminology and Definitions

(1) 2-Pair-Path-Pair. It consists of two pairs of path-pairs denoted as 〈(PSa,PSb),(PTc,PTd)〉, where PSa∈P(S,a),PSb∈P(S,b),PTc∈P(T,c),PTd∈P(T,d), S is a common ancestor of a and b, and T is a common ancestor of c and d. If A=S=T, then A is aquad-common ancestor of a, b, c, and d.(2) Homo-Overlap and Heter-Overlap Individual. Given two pairs of individuals 〈a,b〉and〈c,d〉, if s∈Bi_C(PAa,PAb) (or s∈Bi_C(PAc,PAd), we call s ahomo-overlap individual when PAa and PAb (or PAc and PAd) pass through thesame parent of s. If r∈Bi_C(PAi,PAj), where i∈{a,b} and j∈{c,d}, we call r aheter-overlap individual when PAi and PAj pass through thesame parent of r.(3) Root Homo-Overlap and Heter-Overlap Path. Given a 2-pair-path-pair 〈(PAa,PAb),(PAc,PAd)〉, if s is a homo-overlap individual and the homo-overlap path extends all the way to the quad-common ancestor A, then we call it aroot homo-overlap path. If r is a heter-overlap individual and the heter-overlap path extends all the way to the quad-common ancestor A, then we call it aroot heter-overlap path.Example 8.
A isquad-common ancestor for a, b, c, and d in Figure 12. For (a), s is ahomo-overlap individual between PAa and PAb.
t is ahomo-overlap individual between PAc and PAd. And, A→s and A→t areroot homo-overlap paths. For (b), x is aheter-overlap individual between PAa and PAd. y is aheter-overlap individual between PAb and PAc. And A→x and A→y areroot heter-overlap paths.Examples of 2-pair-path-quads forΦab,cd.
(a)
(b)


## 3.3.2. Path-Counting Formula forΦab,cd

Now, we present a path-pair level graphical representation for〈(PAa,PAb),(PAc,PAd)〉 shown in Figure 13. The options for an edge can be {T,X,TX}. (Refer to Section 3.1.1 for definitions of T,X, and TX). Based on the different types of 〈PAa,PAb,PAc,PAd〉 presented in (14), all cases for 〈(PAa,PAb),(PAc,PAd)〉 are summarized in Table 3, where h is the last individual of a root homo-overlap path PAh (i.e., the path PAh ending at h) and r1 and r2 are the last individuals of root heter-overlap paths PAr1 and PAr2, respectively.Table 3
A summary of all cases for〈(PAa,PAb),(PAc,PAd)〉.
〈
P
A
a
,
P
A
b
,
P
A
c
,
P
A
d
〉
〈
(
P
A
a
,
P
A
b
)
,
(
P
A
c
,
P
A
d
)
〉
Zero root 2-overlap andzero root 3-overlap
Zero root homo-overlap and zero root heter-overlap
One root 2-overlap path
One root homo-overlap and zero root heter-overlap
Zero root homo-overlap and one root heter-overlap
Two root 2-overlap paths
Two root homo-overlaps and zero root heter-overlap
Zero root homo-overlap and two root heter-overlaps
One root 3-overlap path
One root homo-overlap and two root heter-overlaps, andh=r1=r2
One root 2-overlap and one root 3-overlap
One root homo-overlap and two root heter-overlaps, andr1=r2≠h
One root homo-overlap and two root heter-overlaps, andh=r1≠r2Figure 13
Scenarios of〈(PAa,PAb),(PAc,PAd)〉 at path-pair level.Given a pedigree graph having one or multiple progenitors{pi∣i>0}, we define that the generation of a progenitor pi is 0, denoted as gen(pi)=0. If an individual a has only one parent p, then we define gen(a)=gen(p)+1. If an individual a has two parents f and m, we define gen(a)=MAX{gen(f),gen(m)}+1.The path-counting formula forΦab,cd is as follows:
(16)Φab,cd=∑A(∑Type1(12)L2-pairΦAAA+∑Type2(12)L2-pair+1ΦAAAvvvv+∑Type3(12)L2-pair+2ΦAAvvvv+∑Type4(12)L2-pair+1ΦAA)+∑(S,T)∈Type5(12)L〈PSa,PSb〉+L〈PTc,PTd〉+1ΦBB,
where A: a quad-common ancestor of a, b, c, and d, S: a common ancestor of a and b, and T: a common ancestor of c and d. For 〈(PAa,PAb),(PAc,PAd)〉(S=T=A), there are four types (i.e., Type 1 to Type 4).Type 1: zero root homo-overlap and zero root heter-overlap.Type 2: zero root homo-overlap and one root heter-overlapPAr ending at r,
(17)Type3:{zeroroothomo-overlapandtworootheter-overlapPAr1andPAr2endingatr1andr2,respectively,oneroothomo-overlapPAhendingathandtworootheter-overlapPAr1andPAr2endingatr1andr2,andr1≠r2.Type 4: one root homo-overlapPAh ending at h and two root heter-overlap ending at r1 andr2, andh=r1=r2. For 〈(PSa,PSb),(PTc,PTd)〉(S≠T), there is one type (i.e., Type 5).Type 5:〈PSa,PSb〉 has zero overlap individual, 〈PTc,PTd〉 has zero overlap individual.At most one path-pair(either〈PSa,PSb〉or〈PTc,PTd〉)can have crossover individuals.Between a path from〈PSa,PSb〉 and a path from 〈PTc,PTd〉, there are no overlap individuals, but there can be crossover individuals, x, where x≠S and x≠T:(18)B={Swhengen(S)<gen(T)Swhengen(S)=gen(T)andThastwoparentsTotherwise,L2-pair={LPAa+LPAb+LPAc+LPAdforType1LPAa+LPAb+LPAc+LPAd-LPArforType2LPAa+LPAb+LPAc+LPAd-LPAr1-LPAr2forType3LPAa+LPAb+LPAc+LPAd-2*LPAhforType4,L〈PSa,PSb〉=LPSa+LPSbforType5,L〈PTc,PTd〉=LPTc+LPTdforType5.Note that if〈a,b〉 and 〈c,d〉 have zero quad-common ancestors, we have the following formula for Φab,cd:
(19)Φab,cd=∑(S,T)∈Type6(12)L〈PSa,PSb〉+L〈PTc,PTd〉ΦSS*ΦTT.
Type  6:〈PSa,PSb〉 is a nonoverlapping path-pair and 〈PTc,PTd〉is a nonoverlapping path-pair. Between a path from 〈PSa,PSb〉 and a path from 〈PTc,PTd〉, there are no overlap individuals, but there can be crossover individuals.L
〈
P
S
a
,
P
S
b
〉 and L〈PTc,PTd〉 are defined as in Type 5.The correctness of the path-counting formula forΦab.cd is proven in Appendix C. For completeness, please refer to [18] for the path-counting formulas for Φaa,bc, Φab,ac, Φab,ab, and Φaa,ab.


## 3.4. Experimental Results

In this section, we show the efficiency of our path-counting method using NodeCodes for condensed identity coefficients by making comparisons with the performance of a recursive method used in [10]. We implemented two methods: (1) using recursive formulas to compute each required kinship coefficient and generalized kinship coefficient; (2) using path-counting method coupled with NodeCodes to compute each required kinship coefficient and generalized kinship coefficient independently. We refer to the first method asRecursive, the second method asNodeCodes. For completeness, please refer to [18] for the details of the NodeCodes-based method.Nodecodes of a node is a set of labels each representing a path to the node from its ancestors. Given a pedigree graph, letr be the progenitor (i.e., the node with 0 in-degree). (For simplicity, we assume there is one progenitor, r, as the ancestor of all individuals in the pedigree. Otherwise, a virtual node r can be added to the pedigree graph and all progenitors can be made children of r.)   For each node u in the graph, the set of NodeCodes of u, denoted as NC(u), are assigned using a breadth-first-search traversal starting from r as follows.(1)
Ifu is r then NC(r) contains only one element: the empty string.(2)
Otherwise, letu be a node with NC(u), and v0,v1,…,vk be u’s children in sibling order; then for each x in NC(u), a code xi* is added to NC(vi), where 0≤i≤k, and * indicates the gender of the individual represented by node vi.Computations of kinship coefficients for two individuals and generalized kinship coefficients for three individuals presented in [11, 12, 14, 15] are using NodeCodes. The NodeCodes-based computation schemes can also be applied for the generalized kinship coefficients for four individuals and two pairs of individuals. For completeness, please refer to [18] for the details using NodeCodes to compute the generalized kinship coefficients for four individuals and two pairs of individuals based on our proposed path-counting formulas in Sections 3.2 and 3.3.In order to test the scalability of our approach for calculating condensed identity coefficients on large pedigrees, we used a population simulator implemented in [11] to generate arbitrarily large pedigrees. The population simulator is based on the algorithm for generating populations with overlapping generations in Chapter 4 of [19] along with the parameters given in Appendix B of [20] to model the relatively isolated Finnish Kainuu subpopulation and its growth during the years 1500–2000. An overview of the generation algorithm was presented in [11, 12, 14]. The parameters include starting/ending year, initial population size, initial age distribution, marriage probability, maximum age at pregnancy, expected number of children by time period, immigration rate, and probability of death by time period and age group.We examine the performance of condensed identity coefficients using twelve synthetic pedigrees which range from 75 individuals to 195,197 individuals. The smallest pedigree spans 3 generations, and the largest pedigree spans 19 generations. We analyzed the effects of pedigree size and the depth of individuals in the pedigree (the longest path between the individual and a progenitor) on the computation efficiency improvement.In the first experiment, 300 random pairs were selected from each of our 12 synthetic pedigrees. Figure14 shows computation efficiency improvement for each pedigree. As can be seen, the improvement ofNodeCodes overRecursive grew increasingly larger as the pedigree size increased, from a comparable amount of 26.83% on the smallest pedigree to 94.75% on the largest pedigree. It also shows that path-counting method coupled with NodeCodes can scale very well on large pedigrees in terms of computing condensed identity coefficients.Figure 14
The effect of pedigree size on computation efficiency improvement.In our next experiment, we examined the effect of the depth of the individual in the pedigree on the query time. For each depth, we generated 300 random pairs from the largest synthetic pedigree.Figure15 shows the effect of depth on the computation efficiency improvement. We can see the improvement ofNodeCodes overRecursive, ranging from 86.48% to 91.30%.Figure 15
The effect of depth on computation efficiency improvement.


## 4. Conclusion

We have introduced a framework for generalizing Wright’s path-counting formula for more than two individuals. Aiming at efficiently computing condensed identity coefficients, we proposed path-counting formulas (PCF) for all generalized kinship coefficients for which are sufficient for expressing condensed identity coefficients by a linear combination. We also perform experiments to compare the efficiency of our method with the recursive method for computing condensed identity coefficients on large pedigrees. Our future work includes (i) further improvements on condensed identify coefficients computation by collectively calculating the set of generalized kinship coefficients to avoid redundant computations, and (ii) experimental results for using PCF in conjunction with encoding schemes (e.g., compact path-encoding schemes [13]) for computing condensed identity coefficients on very large pedigrees.



---

*Source: 898424-2014-07-21.xml*