Efficient Reconstruction of Stochastic Pedigrees

The decreased costs of sequencing technologies have enabled large-scale, data-driven analyses of genomes [Ins19]. Recent science and news articles feature stories only possible due to this plethora of data, such as the recent identification and capture of a high-profile criminal [KM18] predicated on DNA evidence. In this effort, an individual’s genetic information was compared to a large, curated database called GEDMatch consisting of over one million individual genomes. In comparison, there exist databases which are of several orders of magnitude larger in size such as MyHeritage ($\sim$3.7 million [MyH]), 23andMe ($\sim$10 million [23a]), and Ancestry ($\sim$15 million [Anc]).

This raises the question: how much kinship information can be learned from DNA? Current databases already contain a considerable amount of this information. Indeed, it is estimated that a given US individual of European ancestry, on average, has a third cousin or closer who is already in the MyHeritage database [ESPC18]. However, such databases are still far from complete. This calls into question the ability to detect missing kinships based on individuals already present in the database.

This discussion also highlights the issue of genomic privacy. Indeed, it becomes much easier to identify and locate individuals by combining the genetic and genealogical information with outside information (addresses, e-mails, family photos, etc.). This potential, having already been demonstrated by the resolution of the aforementioned criminal case, was brought to attention by [ESPC18]. From this point of view, the ability to reconstruct genealogies from collected genetic data is of concern for individuals whose information is revealed, even if one has never been sequenced. Since our work establishes a positive result in a pessimistic scenario where we start with no ground truth information, we believe that our work brings to attention this critical issue via a theoretical framework.

Without any prior knowledge about the ground truth, can we learn everyone’s genealogy using their genetic information? In this paper, we study the inference problem of recovering ancestral kinship relationships of a population of extant (present-day) individuals, using only their genetic data. Our goal is to use this extant genetic data to recover the pedigree of the extant population, under an idealized model. A pedigree is a graph whose nodes (individuals) have edges that encode parent-sibling relationships. The topology and reconstruction of pedigrees are well-studied in bioinformatics from both a theoretical and empirical perspective, and in general the study of pedigrees poses formidable computational and statistical challenges.

In this paper, we introduce a novel recursive algorithm Rec-Gen for pedigree reconstruction. To demonstrate the effectiveness of our approach, we give a mathematical proof that for an idealized generative model on pedigrees, our algorithm is able to approximately recover the true, unknown pedigree only using the genetic data of the extant population. In terms of sample complexity, which for our purposes refers to the common gene sequence length of an extant individual, our algorithm greatly outperforms the naive reconstruction method (estimate pairwise distances between the extant individuals, then construct the pedigree that produces these distances). We propose our approach in this work as a prototype for the future study of more general pedigrees, including those involving real-life genetic data, from both a theoretical and empirical perspective. For further discussion on our model of pedigree generation, as well as its features and limitations, see Section 1.4 and Section 1.6.

A common method in theoretical evolutionary biology is to model lineages and inheritance via a family of directed acyclic graphs. One line of work is that of phylogenetics (refer to [SS03] for an overview) which uses trees to model the occurrence of large-scale speciation events in evolutionary biology. Another line of work is coalescent theory, which focuses on variable-height inheritance trees between genes as its main statistic to infer large-scale population sizes, as in e.g. [KKM⁺19]. In contrast, pedigrees capture small-scale individual genealogies that encode familial relationships. Specifically, most pedigree models are for human genealogies, where we designate exactly two parents to each individual. By construction, such graphs are no longer trees and warrant different strategies for inference.

[SH06] posed the formal definition of pedigrees using graph-theoretic language. In that work, the authors gave combinatorial arguments proving that one can reconstruct complete pedigrees, assuming the correct ancestral history is provided as an input for each extant individual. Our definition of pedigrees is essentially the same as the one outlined by these authors, though we make the simplification that we do not identify the vertex set bipartition (corresponding to the biological sex of the individuals).

To tie in more closely with real-world applications, one must consider the challenge of estimating these histories from data. Along these lines, [TS08] studied stochastic processes that one can associate with the pedigree, in such a way that one can prove negative results (information-theoretic impossibility) or positive results (an algorithm) for the reconstruction of the pedigree from extant data. The stochastic process used to show their positive result was based on a very specific family of Markov chains which allows for inference but is quite different from our model.

For the problem of performing pedigree reconstruction on real data, there is a wealth of literature [Tho00, KLKH11, HWH⁺13, Tho13, HWPE14, STH14, Hui17, Wan19]. Such studies apply heuristics that take into account various complications and phenomena observed in human genomes, such as varying levels of correlations between different sites and the presence of mutations that are not inherited from parents.

One line of work particularly relevant to this paper is [HWH⁺13, HWPE14] in which the authors also tackle the problem of pedigree reconstruction from real extant genetic data. Assuming answers to queries of the form, “how much DNA did $i$ and $j$ simultaneously inherit from their ancestors?”, they design a statistical test that distinguishes between siblings, half-siblings and cousins. Their method leverages this information with a maximal-clique finding algorithm to iteratively reconstruct the parents, layer-by-layer. There is no proof of correctness provided, but they provide benchmarks on real and simulated data to provide experimental justification. Our contributions have a slightly different flavor: using a similar iterative strategy but with a different statistical test (the novel part of our algorithm) and for a more optimistic set of assumptions, one can actually provably reconstruct the pedigree correctly in a sample-efficient way, in an asymptotic sense.

The authors of [HWPE14] specifically emphasize their method’s ability to reconstruct half-siblings. Technically speaking, this is not allowed in our model and therefore it may appear to the reader that there is something too restrictive or suboptimal about our analysis. One major difference between our model and the aforementioned work is that we model haploid individuals (one copy of DNA), while in reality humans are diploids (two copies of DNA). Furthermore, in our proof, we guarantee reconstruction of monogamous couples of haploid individuals – in other words, up to permutation of the two individuals within each couple. It can be observed that given a monogamous pedigree with a haploid model, one can construct a natural, non-monogamous pedigree with a diploid model such that the total variation of the extant data of the two pedigrees is zero. Therefore, we think that our results should also hold for a diploid model with minor modifications and have correctness guarantees to match the empirical results of the aforementioned work [HWPE14], for example by interpreting Fig. 1(a) as a pair of diploid half-siblings.

Our work is also closely related to the problem of phylogenetic reconstruction [ESSW99, Mos04, MR05, DMR06]. In this setting, symbols are passed from the root of a phylogenetic tree to descendants via a Markov process such as in the Cavender–Farris–Neyman model, a basic model for mutations. Similar to our inference problem in this work, in phylogenetic reconstruction, one is tasked with reconstructing the tree given only the symbols at the leaves. The main result of [ESSW99] characterizes the sample complexity—the minimal string length of the data at the leaves such that reconstruction is possible—as logarithmic in the depth of the tree, a phenomenon that our results suggest also holds for the pedigree reconstruction problem. The work [MR05] provides theoretical guarantees for the problem of learning the phylogenetic generative model (i.e., the topology of the tree as well as the transition matrices), which includes hidden Markov models as a special case, from the extant data under a spectral assumption on the transition matrices (see also later work of [HKZ12]). Most closely related to our approach in this paper is the work [Mos04], which shows how to recursively reconstruct phylogenies using techniques from the theory of broadcast processes on trees (see also [DMR06]). This approach provides inspiration for our main algorithm Rec-Gen, which uses similar techniques to recursively reconstruct pedigrees. We direct the reader to [EKPS00] and [Mos01] for studies of broadcast processes on trees with binary and large alphabet respectively, and [MMP18] for a generalization to directed acyclic graphs.

We now give an informal, detailed description of our framework for pedigree reconstruction, with a more detailed treatment of the generative model in Section 3. Our generative model on pedigrees consists of two parts: a parametric model for generating the network structure on the set of ancestors and extant individuals, and an inheritance procedure for transmitting genetic data from the founders, the oldest individuals in the pedigree, to the extant population.

To generate the pedigree network structure, we begin with a large founding population of size $N_{T}$. The founders randomly mate monogamously, and each couple gives birth to a random number of children, so that the average number of offspring per couple is a constant⁵⁵5More precisely, each couple has a random number of children distributed as a Poisson random variable with expectation $\alpha$. $\alpha$. This procedure of random monogamous mating continues for $T$ subsequent generations, eventually yielding the extant nodes and a pedigree $\mathcal{P}$ formed by the individuals in generations $0,1,\ldots,T$, with $N_{i}$ nodes at each level $i$.

Next we describe how genetic data transmits from the founding population to the extant. Every individual in the pedigree has a gene sequence consisting of $B$ symbols placed in $B$ distinct blocks. Each individual in the founding population is initialized with independent uniformly random draws from a very large alphabet $\Sigma$. Now we state how parents pass down genes to their children. In a given block, a child inherits, with equal probability, either its mother’s or its father’s symbol in the corresponding block. This procedure repeats for all couples in a given generation and then continues over subsequent generations so that genetic data is iteratively transferred through the pedigree, eventually giving rise to the gene sequences of the extant individuals.

Our main result is summarized in the following theorem. See Theorem 6.1 for a formal statement.

Let $\mathcal{P}$ denote the true, unknown pedigree. Our formal version of Theorem 1.1 (see Theorem 6.1) implies that with high probability Rec-Gen outputs a reconstructed pedigree $\hat{\mathcal{P}}$ whose size is at least $0.9N_{i}$ in each generation $i\in\{0,\ldots,T\}$, such that every node $\hat{u}\in\hat{\mathcal{P}}$ can be identified with exactly one node $u\in\mathcal{P}$, and this identification preserves relationships in the sense that $\hat{u}$ is a child of $\hat{v}$ in $\hat{\mathcal{P}}$ if and only if $u$ is a child of $v$ in $\mathcal{P}$. In graph-theoretic terminology, our reconstruction $\hat{\mathcal{P}}$ is a (very large) induced subgraph of the truth $\mathcal{P}$.

We note that the stipulation that we recover 90% of the nodes at each level is actually a simplification; in fact, we can make the fraction of reconstructed nodes in each generation arbitrarily large by taking $\alpha$ to be large enough. We refer the reader to Theorem 6.1 for details.

The algorithm Rec-Gen consists of a recursive procedure that uses only the genetic information from the extant population to construct a good approximation for the true pedigree $\mathcal{P}$ of depth $T$ that generated the observations. In the first phase of recursion, the algorithm reconstructs the parents of the extant nodes, which we label as the $1^{\mathrm{st}}$ generation. In the $t^{\mathrm{th}}$ phase, the algorithm adds a $t^{\mathrm{th}}$ generation to the partially reconstructed version of the true pedigree given by the output of the previous phase. The algorithm terminates after $T$ phases of recursion, producing a pedigree $\hat{\mathcal{P}}$ with $T$ generations that well-approximates the true, unknown pedigree $\mathcal{P}$.

We next give a simplified version of our recursive procedure that serves to illustrate the main ideas. See Section 6 for a detailed description of Rec-Gen. Suppose that we have constructed a pedigree $\hat{\mathcal{P}}_{t}$ of depth $t$, and recall that $B$ refers to the length of the gene sequence of an individual. Also recall that a couple refers to a pair of mated individuals.

Note that the first step of our recursive procedure equips each couple with an empirical gene sequence of length B where each block can contain two distinct symbols. This empirical gene sequence is constructed based on extant data and should be thought of as determining which symbols belong to at least one of the individuals from the couple in a given block. Also, we say that three gene sequences $\sigma,\sigma^{\prime},\sigma^{\prime\prime}$ overlap in a block if all three sequences have some symbol in common in that block.

Perform the following steps to output a pedigree $\hat{\mathcal{P}}_{t+1}$ of depth $t+1$.

• (1)

  Collect-Symbols For each couple $c$ in generation $t$ of $\hat{\mathcal{P}}_{t}$, use the extant genetic data to recover symbols that belong to $c$ as follows.

  • –

    Recover a symbol $\sigma$ in block $b\in[B]$ of $c$ if $c$ has three extant descendants descended from distinct children of $c$ that all share symbol $\sigma$ in block $b$.

  • –

    Repeat this procedure to recover at most one other symbol $\sigma^{\prime}\neq\sigma$ for $c$ in block $b$.

• (2)

  Test-Siblinghood For every triple of couples $c,c^{\prime},c^{\prime\prime}\in\hat{\mathcal{P}}_{t}$ in generation $t$, determine $c,c^{\prime},c^{\prime\prime}$ to be (mutually) ‘siblings’ if and only if at least $0.21B$ of their recovered symbols mutually overlap.

• (3)

  Assign-Parents For every maximal collection $\mathcal{C}=\{c_{1},c_{2},\ldots,c_{k}\}$ of couples in generation $t$ such that every triple in $\mathcal{C}$ consists of mutual siblings, construct a pair of parents in generation $t+1$ that have as children precisely one individual from each couple in $\mathcal{C}$.⁶⁶6We perform this step in such a way that every child is assigned at most $2$ parents.

After $T$ iterations of the above recursive procedure, we output a pedigree $\hat{\mathcal{P}}_{T}$ that gives a good approximation to the underlying pedigree that generated the extant genetic data as described in Theorem 1.1. We remark that working with triples as above greatly simplifies our analysis, as discussed in Section 2.3.

Our generative model imposes various constraints on the typical pedigrees that we consider. We discuss these modeling assumptions here and also consider the problem of investigating more general models that could more accurately capture properties of real-world data.

First, we consider the assumption that the size of the alphabet $\Sigma$ is very large with respect to the size $N_{T}$ of the founding population. Since a “block” represents the unit of inheritance from a parent⁷⁷7Using biology terminology, each block can be considered as an idealized abstraction of a collection of single-nucleotide polymorphisms (sites of variation) with high linkage disequilibrium (empirical measure of correlation) that are passed from parent to child., this implies that with very high probability all of the founders have distinct symbols in their gene sequences, and no two founders share a common symbol.⁸⁸8Mathematically, this can be thought of as an improper prior on a countably infinite alphabet $\Sigma$. Our large alphabet assumption is equivalent to the assertion that the founders are unrelated.

Second, the stochastic process describing inheritance in our model has the following biological interpretation. A standard concept in population genetics refers to long-running sequence matches as being identical by descent (IBD) if they arose due to inheritance from a common ancestor [Tho13]. In contrast, the term identity by state refers to the event that two identical tracts in the genome arose by coincidence – via mutations – in two unrelated individuals. Our inheritance model contains the assertion that each block corresponds to true IBD sequences: if two individuals have the same symbol, we can always identify a common ancestor that gave rise to these symbols.

Third, we recall the hypothesis that every couple has on average $\alpha$ children, where $\alpha$ is a sufficiently large absolute constant independent of the size $N_{T}$ of the founding population. This ensures that, roughly speaking, every new generation is a factor $\alpha/2$ larger than the previous one. Assuming roughly uniform growth of generations, it is necessary that $\alpha>0\,\,$— otherwise the population would die out and there would be no extant nodes after $T$ generations. More subtly, it is necessary that $\alpha\geq 2$   — otherwise, via standard results from the theory of branching processes (see, e.g. [KA15]) a founding node has a very low probability of passing on its symbols to the extant. In this situation, even detection of such an ancestor from extant genetic data alone is information-theoretically impossible. On the other hand, our assumption that $\alpha$ is a large constant essentially amplifies the signal sent from a founder to the extant, and this simplifies our mathematical analysis.

Our first open question considers relaxing the previously discussed assumptions.

A more subtle consequence of our generative model is inbreeding, a term we use to refer to the following phenomena: (1) the presence of multiple lowest common ancestors for a pair of extant nodes, and (2) the presence of mated couples such that the two individuals in the couple have a lowest common ancestor (LCA) (see Definition 3.5 for the formal definition of an LCA). The degree of inbreeding qualitatively refers to the frequency of such structures in the pedigree. Moreover, inbreeding as in (2) is mathematically equivalent to having cycles in the pedigree. In general, a higher degree of inbreeding makes the pedigree reconstruction problem more difficult and in some cases information-theoretically impossible (see Section 2.1 for detailed examples). Our choice of model allows for some degree of inbreeding, and our algorithm and analysis are carefully tailored to circumvent this obstacle.

Other assumptions inherent in our model include that the pedigree is graded, i.e., couples are formed from individuals in the same generation, and monogamous: a given individual only mates with one other individual. Furthermore, mutations — errors in the transmission of genetic data from parents to offspring — are a central component in biological applications that our current model does not incorporate.

Recall that two individuals $u,v$ that share the same set of parents are siblings. If two individuals share a common subset of grandparents (but not parents), we refer to them as cousins.

First consider the pedigrees displayed in Fig. 1(a). An important statistic for determining relationships is the correlation between symbols of nodes at the same level. Consider the event $E$ that the left extant shares the same symbol as the right extant. Note that these two extant nodes are cousins sharing a single set of grandparents. The grandparents are the founders in this example, so we assign to each of them a unique symbol ($a\neq b\neq c\neq d\neq e\neq f$). The occurrence of $E$ implies that $k=c$ or $k=d$ via the left extant receiving a symbol from its right parent; this occurs with probability $\tfrac{1}{2}$. Conditioned on this occurring, the right extant block $\ell$ is the same as $k$ with probability $\frac{1}{4}$, so the overall probability that both receive the same symbol is $\frac{1}{8}$.

Compare this to the example shown in Fig. 1(b), where the two extant are cousins in two ways (siblings marrying siblings). Note that whichever symbol (out of $a,b,c,d$) that $k$ is, the right grandchild receives the same independently with probability $\tfrac{1}{4}$. This is an example of a type of inbreeding where two extant nodes have more than one LCA.

The examples in Fig. 2 demonstrate how the correlation between extant nodes is boosted due to the presence of inbreeding. Note that in the generic case where extant siblings have an ancestral pedigree that is a tree, these individuals have a $\tfrac{1}{2}$ fraction overlap in their blocks. For comparison, let us compute the probability of coincidence for the two extant nodes in Fig. 2(a). The probability that $k=a$, for example, is

$$\mathbb{P}(k=a)=\mathbb{P}(e=f=a)+\frac{1}{2}\mathbb{P}\left(\{e,f\}=\{a,b\}\right)=\frac{1}{4}+\left(\frac{1}{2}\right)^{2}=\frac{1}{2}.$$

Since $k$ and $\ell$ inherit symbols independently from their grandparents, the overall probability is

$$\mathbb{P}(k=\ell)=\mathbb{P}(k=\ell=a)+\mathbb{P}(k=\ell=b)=\left(\frac{1}{2}\right)^{2}+\left(\frac{1}{2}\right)^{2}=\frac{1}{2},$$

which is precisely the probability that two generic siblings inherit the same symbol.

The situation in Fig. 2(b) is even more pronounced. The two parents share the same symbol (either $a$ or $b$) with probability $\tfrac{1}{2}$ and have different symbols with probability $\tfrac{1}{2}$. This means that the coincidence probability is now $\tfrac{1}{2}+\tfrac{1}{2}\times\tfrac{1}{2}=\tfrac{3}{4}$: their correlation between overlaps is much stronger than that of siblings in the generic case.

From the example in Fig. 2(a), we conclude that the statistical model of extant data parametrized by pedigrees is unidentifiable. Stated another way, it is information-theoretically impossible to distinguish between siblings and inbred cousins using only extant data. Thus, in order for any algorithm to succeed in reconstructing a large fraction of the pedigree using only extant data, it is necessary to bound the amount of inbreeding in the ensemble of pedigrees of interest. We accomplish this using a careful analysis of our generative model.

In this section, we present a high-level analysis of the Rec-Gen algorithm. Theorem 1.1 states that Rec-Gen yields an accurate reconstruction on $90\%$ of nodes for typical pedigrees from our generative model⁹⁹9We note again that the $90\%$ is for simplicity of exposition, and in reality we can recover an arbitrarily large fraction of nodes. This is made precise in Theorem 6.1.. Note that a formal statement of this theorem, our main result, is given by Theorem 6.1, and a complete proof is contained in the upcoming sections.

Suppose we construct a pedigree $\hat{\mathcal{P}}_{t}$ on $t$ generations that, for simplicity of the discussion, exactly matches the true, unknown pedigree $\mathcal{P}$ up to generation $t$. We show that Collect-Symbols, Test-Siblings, and Assign-Parents applied to $\hat{\mathcal{P}}_{t}$ provide an accurate reconstruction of $90\%$ of the nodes at generation $t+1$. In the remainder of this section we give a high-level argument that the output $\hat{\mathcal{P}}_{t+1}$ satisfies the following conditions:

• (i)

  every individual $\hat{u}$ in $\hat{\mathcal{P}}_{t+1}$ can be identified with a unique individual $u$ in $\mathcal{P}$ at generation $t+1$,

• (ii)

  at most $10\%$ of the nodes in generation $t+1$ of $\mathcal{P}$ are not identified with an individual in $\hat{\mathcal{P}}_{t+1}$, and

• (iii)

  if $v$ is a child of $\hat{u}$ in $\hat{\mathcal{P}}_{t+1},$ then $v$ is a child of $u$ in $\mathcal{P}$.

Recall that for the purposes of reconstruction, we only have access to the genetic data of the extant.

In this discussion, we refer to three couples $c,c^{\prime},c^{\prime\prime}\in\mathcal{P}$ as (mutual) siblings if there exist individuals $u\in c,u^{\prime}\in c^{\prime},$ and $u^{\prime\prime}\in c^{\prime\prime}$ such that $u,u^{\prime},$ and $u^{\prime\prime}$ are mutually siblings. A clique refers to a collection of couples $\mathcal{C}=\{c_{1},\ldots,c_{k}\}$ such that every triple from $\mathcal{C}$ consists of mutual siblings.

The next two facts are essential to the argument.

1. (A)

   If Collect-Symbols recovers symbol $\sigma$ in block $b$ for a couple $c$ in generation $t$, then $c$ also has the symbol $\sigma$ in block $b$ in $\mathcal{P}$ (5).

2. (B)

   Collect-Symbols recovers at least $99\%$ of the symbols for at least $99\%$ of the couples in generation $t$ (Lemma 5.9).

Together, (A) and (B) imply that for $99\%$ of the couples in generation $t$, our algorithm gets all of the siblings relationships between these couples correct. To see why, we can use a similar calculation as in the first example of Section 2.1 to conclude that the average overlap between the symbols of three individuals that are mutually siblings is $25\%$. By concentration of binomial random variables about their means, it follows that with high probability, all triples of individuals that are mutually siblings in $\mathcal{P}$ have at least $24.9\%$ mutual overlap between their symbols. A simple union bound combined with (A) and (B) implies that for most triples of individuals in generation $t$ that are mutually siblings, the recovered symbols from Collect-Symbols in those individuals’ corresponding couples have overlap at least $21\%$. Hence, Test-Siblinghood infers correct siblinghood relationships for a majority of triples.

Moreover, our siblings test on the recovered symbols does not have any false-positives:

• (C)

  Test-Siblinghood never misclassifies non-siblings as siblings (Lemma 6.5).

The next and last key fact argues that our naive assignment of parents to individuals in cliques as in Assign Parents is in fact the correct assignment in a typical pedigree. This property holds with very high probability over our generative model.

• (D)

  Let $\mathcal{C}\subset\mathcal{P}$ denote a clique at generation $t$ in the true pedigree. Then there exists a couple $\tilde{c}$, which we refer to as the parents of $\mathcal{C}$, in generation $t+1$ of $\mathcal{P}$ that has exactly one child in every couple of $\mathcal{C}$, and no other couple has more than $1$ child in $\mathcal{C}$ (Lemma 4.8).

Together, (A), (B), (C), and (D) imply that our reconstruction criteria (i), (ii), and (iii) from the beginning of this section hold, as we now justify. Recall that we already showed (A) and (B) imply that we classify a large fraction of the couples at generation $t$ correctly as siblings. Moreover, part (C) and the transitivity of siblinghood in $\mathcal{P}$ imply that cliques in our reconstruction really correspond to cliques in the truth. By part (D) such cliques have unique parents. Thus, for (i), we identify newly constructed couples $\hat{u}\in\mathcal{P}_{t+1}$ with the unique parents $u\in\mathcal{P}$ of the clique formed by the children of $\hat{u}$, further pairing the two individuals in $u$ with those in $\hat{u}$ arbitrarily. With this identification, (iii) follows immediately. To show part (ii), later in the paper we give a sufficient condition for a couple at generation $t$ to have $99\%$ of its symbols collected by Collect-Symbols as in (B) (see Lemma 5.9). Then we show that $90\%$ of individuals in generation $t+1$ have children in such couples (see Proposition 5.8), which proves part (ii). Essentially, this sufficient condition amounts to saying that a couple $c$ at generation $t$ has no inbreeding (cycles) above or below it (i.e. among its ancestors or descendants, respectively) and that the pedigree of descendants of $c$ contains a $\alpha/4$-ary tree (see Definition 5.4).

It is tempting to employ a seemingly simpler recursive scheme than the one described in Section 1.5 that operates on pairs instead of triples. As an example, consider an alternative recursive procedure such that:

1. 1.

   Collect-Symbols only uses pairs of extant descendants to recover symbols of a couple $c,$

2. 2.

   Test-Siblinghood considers only pairs of couples at generation $t$ and detects them to be siblings if their strings overlap by at least $49\%$, and

3. 3.

   Assign-Parents assigns parents to individuals in maximal collections $\mathcal{C}$ such that every pair of couples is (tested as) siblings.

Unfortunately, this simpler approach encounters two major technical complications.

First, working with a pairwise siblings test introduces a problem for the step of assigning parents. Define a pairwise clique to be a collection of couples so that every pair of couples passes the pairwise siblings test. With high probability, it turns out in every generation there exist a constant number of pairwise cliques that are not explained in the naive way of assigning to this clique parents that have precisely one child per couple. In particular, in the true pedigree $\mathcal{P}$ it is possible to have three couples that mutually pass the pairwise siblings test, yet there are three distinct parent couples each having precisely two children among these three couples. See Fig. 3 for an illustration. This type of structure, though rare, occurs a constant number of times in each generation, and thus introduces inherent errors in our reconstruction that accumulate at every step of iteration.

A second problem caused by working with pairs arises in the step of collecting symbols. The pairwise version of our algorithm assigns a symbol to a couple if that symbol occurs in two extant descendants that are descended from distinct children of that couple. In our generative model, it turns out that with high probability there are a logarithmic number of pairs of extant nodes that have at least two LCA’s. For such pairs, the pairwise algorithm does not accurately assign symbols to their reconstructed ancestors. Similar to the previous issue, these errors snowball and make the analysis for proving Theorem 1.1 very difficult.

On the other hand, working with an algorithm using triples as described in Section 1.5 makes for a much cleaner analysis and nicer reconstruction guarantee. This innovation circumvents the technical complications of the pairwise version because every clique (recall that this is a collection of couples where every triple consists of mutual siblings) can be explained in a naive way (Lemma 4.8), and in our generative model every triple of extant individuals descended from distinct children of a given ancestor have that ancestor as their unique LCA with very high probability (Lemma 4.10).

The remainder of the paper, which provides a formal proof of Theorem 1.1, is divided into four parts.

• •

  Section 3 provides preliminary definitions and a formal definition of our generative model.

• •

  Section 4 proves important properties about the typical network structure of pedigrees from our generative model.

• •

  Definition 5.2 proves important properties about the block statistics of the extant nodes in a typical pedigree from our generative model.

• •

  Section 6 gives a precise description of Rec-Gen and provides a formal statement and proof of Theorem 1.1.

Specifically, in Section 4 we rigorously quantify the degree of inbreeding in typical pedigrees from our model by counting the number of collisions (see Definition 4.1 and Lemma 4.4). This has several useful consequences, including that every clique has a unique parent (fact (D) from Section 2.2, also see Lemma 4.8) and that the extant individuals used in Collect-Symbols have a unique LCA (see Lemma 4.10). In particular, the latter is key to showing fact (A) from Section 2.2.

In Definition 5.2, we provide a definition (see Definition 5.4) that essentially characterizes the individuals in $\mathcal{P}$ that are reconstructible via Rec-Gen. We show that couples involving such individuals, referred to as awesome couples, transmit many of their symbols to the extant, with high probability (see Lemma 5.9). In particular, awesome couples have at least $99\%$ of their symbols recovered by Collect-Symbols (fact (B) from Section 2.2). We also prove an important result for our siblings test: triples of individuals that are not mutually siblings have mutually overlap at most $19\%$ (see Lemma 5.2). This combined with fact (A) from Section 2.2 essentially shows that Test-Siblinghood never classifies non-siblings as siblings (fact (C) from Section 2.2, see also Lemma 6.5).

Our final section, Section 6 ties everything together, following fairly closely the high-level argument presented in Section 2.2 to prove the formal version of Theorem 1.1.

In this work, we focus on a special family of complete pedigrees that are both graded and monogamous.

We assume that every non-extant individual in the pedigree is in a couple, and so the number of vertices at each non-extant level is even. This assumption is effectively without loss of generality—if an individual is not in a couple, then it has no descendants, and so we cannot recover information about this individual or even its existence.

An example of a complete, graded, monogamous pedigree is shown in Fig. 1(a). In our model, symbols are passed down from parents to children in a completely symmetric way. Thus, given the data of the children, it is impossible to distinguish the owner of each symbol from amongst the two parents. The goal of this paper is to show how one can provably infer the structure of a complete pedigree from extant genetic data via the reconstruction of the ancestral symbols, modulo block phasing (determining which symbol belongs to which parent for each block). Therefore, we introduce the following version of a pedigree which condenses this information.

In particular, a coupled pedigree is also a pedigree. Examples are drawn in Fig. 4 in relation to Fig. 1, where the complete pedigree 1(a) induces a coupled pedigree 4(a) and 1(b) induces 4(b).

The only information that is lost after transforming a complete, monogamous pedigree into a coupled pedigree is the block phasing. Indeed, observe that given the coupled structure $\mathcal{Q}=(V_{\mathcal{Q}},E_{\mathcal{Q}})$, one can easily obtain the individual structure $\mathcal{P}=(V_{\mathcal{P}},E_{\mathcal{P}})$ up to block phasing as follows: (1) add the extant individuals in $V_{0}\subset V_{\mathcal{Q}}$ to $V_{\mathcal{P}}$, (2) for every non-extant node $c\in V_{\mathcal{Q}}$ add individuals $u_{c},u_{c}^{\prime}$ to $V_{\mathcal{P}}$, and (3) given parents $c_{1}$ and $c_{2}$ of $c$ in $\mathcal{Q}$, add the four edges $u_{c_{1}}\to u_{c},u_{c_{1}}^{\prime}\to u_{c},u_{c_{2}}\to u_{c}^{\prime},u_{c_{2}}^{\prime}\to u_{c}^{\prime}$ to $E_{\mathcal{P}}$. In addition, if $\mathcal{P}$ is graded, $\mathcal{Q}$ retains a graded structure $V_{\mathcal{Q}}=V_{0}(\mathcal{Q})\cup\cdots\cup V_{T}(\mathcal{Q})$ so that $V_{0}(\mathcal{Q})$ are the extant nodes and $V_{1}(\mathcal{Q}),\ldots,V_{T}(\mathcal{Q})$ are depth-graded couple nodes. In particular, the graph structure of an individuals pedigree $\mathcal{P}$ uniquely determines the graph structure of its associated coupled pedigree $\mathcal{Q}$ and vice versa.

Given the previous discussion, since our goal is to recover the graph structure of an underlying true pedigree $\mathcal{P}$ given gene sequences of a large number of extant individuals, it suffices to reconstruct the associated coupled pedigree $\mathcal{Q}$.

Furthermore, since the graph underlying a pedigree is a DAG, given a subset $S$ of the pedigree, it is natural to consider the notion of “ancestors” (nodes $\mathsf{anc}(S)$ from which there is a directed path to $S$) and “descendants” (nodes $\mathsf{desc}(S)$ to which there is a directed path from $S$). Also for simplicity, we stipulate that every node $v$ is both a descendant and an ancestor of itself, i.e., $v\in\mathsf{anc}(v)$ and $v\in\mathsf{desc}(v)$. Since the indegree of each node can be more than one, it is possible for two nodes to have more than one “lowest common ancestor”. We define this now.

During our analysis, we often restrict our attention to the information that the pedigree contains about the ancestors or descendants of a particular collection of nodes. In particular, we want to exploit (sub)structures that are not too intertwined. The following definitions make these ideas precise:

Note that coupled pedigrees can have edges of multiplicity two, though only in the case where two siblings form a coupled node, which a rare structure in our generative model. In coupled pedigrees, we consider a double edge to be an undirected cycle of length two. Hence, a tree pedigree consists entirely of simple or multiplicity 1 edges.

As we demonstrate (e.g. Lemma 5.2), coupled tree pedigrees exhibit a type of correlation decay between blocks that enable us to perform inference on the structure. In contrast, non-tree coupled pedigrees correspond to pedigrees with inbreeding, which can arise in nature and appear in our probabilistic model as well. Section 2.1 illustrates examples of such structures. These types of structures introduce challenges for performing inference under our generative model.

Note that siblinghood is a transitive relationship: if $u,v$ are siblings and $v,w$ are siblings, then so are $u,w$. As alluded to in Section 2.3, it is important to look at these relationships in triplets. We now detail how one can encode this information as a 3-uniform hypergraph.

Recall that a clique in a 3-uniform hypergraph is a collection of vertices such that all possible triplets form an edge. The next statement is an observation that follows from the definition of $G_{k}$ and the transitivity of siblinghood.

We denote a Poisson distribution with mean $\lambda$ as $\mathsf{Pois}(\lambda)$. We use some basic tools from probability theory in our proof. The first is referred to in literature as Poisson thinning, see e.g. [Lal16].

Second, we recall that sums of Poisson random variables are themselves Poissons:

Third, we will invoke the following standard variants of the Chernoff–Hoeffding bounds for sums of Bernoulli random variables:

Lastly and in the same spirit as the Chernoff–Hoeffding bound, we will use the fact that Poisson distributions also have sub-exponential tails.

For a proof, refer to Chapter 2 of [Pol15].

We now describe our simple model for generating a population and its genetic data. The model is best viewed in two stages. In the first stage, we generate the population as well as the pedigree topology $\mathcal{P}_{\mathsf{indiv}}$ on these individuals, and in the second stage, we generate the genetic data given this pedigree structure. Note that the random individual pedigree $\mathcal{P}_{\mathsf{indiv}}$ constructed below is graded, monogamous, and complete.

Once we have the population and pedigree structure as above, we generate the genetic data in the following manner.

To given an example of our terminology, there are two individuals in a non-extant coupled node. Each individual is a vertex of $\mathcal{P}_{\mathsf{indiv}}$, and together they form a coupled node, which is a vertex of $\mathcal{P}$. Note that as an artifact of our definitions, extant individuals are both coupled nodes and individuals in $\mathcal{P}$. Moreover extant nodes have exactly one parent in $\mathcal{P}$ given by the coupled node containing the individuals comprising that extant individuals biological parents, as determined by our generative model.

To further emphasize the previous remark, recall that by the discussion in Section 3.1, there is a unique correspondence between coupled pedigrees and individual pedigrees. Hence, it suffices to give a (partial) reconstruction $\hat{\mathcal{P}}$ of $\mathcal{P}$ to (partially) reconstruct the original individual pedigree $\mathcal{P}_{\mathsf{indiv}}$. Thus the content of our main result Theorem 6.1 and the remainder of this paper primarily work with the coupled pedigree $\mathcal{P}$.

In this section we quantify the degree of inbreeding in $\mathcal{P}$. To do so, we first describe an alternative description of our generative model. An equivalent procedure for constructing the coupled pedigree structure $\mathcal{P}$ is to (1) sample the generation sizes according to Poisson random variables with appropriate parameters, (2) pair up individuals in each generation at random into coupled nodes, and (3) have coupled nodes choose two parent coupled nodes at random from the previous generation. This is described formally below.

Next we use tail bounds on Poisson random variables to show that the sizes of each level are well-concentrated with high probability, assuming a sufficiently large size of the initial population. Recall that $N_{i}$ denotes the number of individuals in generation $i$.

As mentioned in Section 2.1, two nodes may have significantly higher amounts of symbol overlap caused by inbreeding in their ancestral pedigree than would be expected given their distance in the pedigree. This can cause us to reconstruct an incorrect pedigree if we attempt to explain the symbol overlap without accounting for inbreeding; for instance, we may see two nodes and think they are siblings, when in reality they are cousins with inbreeding in their family tree (see Section 2.1 for a detailed example). To formally connect different patterns of inbreeding with the amount of spurious symbol overlap they cause, we introduce the notion of collisions in an ancestral pedigree. Roughly speaking, triples of coupled nodes with relatively few collisions in their ancestral pedigree do not have many spurious overlaps, which we prove in Definition 5.2. We first define collisions and then bound the number that occur under our probabilistic assumptions in Lemma 4.4. We also give an alternative characterization of collisions in Lemma 4.3 that is useful later.