betaFeedback

WorksMathematics

Global genetic inference at the scale of mass disasters

Abstract

DNA-based disaster victim identification is commonly performed sequentially, with matches accepted before all genetic evidence is considered jointly. However, early matches may be incorrect or inconsistent with the globally most likely assignment, and treating them as final can affect subsequent identifications. Joint analysis avoids this dependence on decision order, but combinatorial growth has historically made it prohibitive in large cases. In this paper, we show that the general joint identification problem is NP-hard and develop a local-to-global framework for joint genetic inference at scale. We reduce the search using genetic compatibility tests, likelihood-based pruning of unlikely assignments, and symmetry reductions. We represent pedigree likelihoods as polynomials and reformulate the Elston-Stewart algorithm for efficient parallel likelihood evaluation on GPUs. Together, these advances yield a manageable set of candidate assignments and their likelihoods, from which we construct an integer linear program that resolves competing identifications and determines the global maximum-likelihood assignment. In small benchmarks, the method recovers the exhaustive-search optimum with up to 99.96% fewer likelihood evaluations. We also apply it to simulated disasters involving up to 10 thousand victims and missing persons. The framework is not limited to a single global optimum but yields a list of probable alternative assignments, thus providing a flexible tool to be used alongside other forensic evidence.

Introduction

DNA-based disaster victim identification (DVI) is a well-established field in forensic science, with notable examples including the 2026 Nepal floods [18], the 2026 New Year’s Eve bar fire in Crans-Montana, Switzerland [20], the Malaysia Airlines Flight MH17 [29] and the 2004 Thailand tsunami [6]. While various sources of evidence can support victim identification, this paper only considers genetic evidence. In a DVI context, this evidence is usually split into two categories: the post-mortem (PM) DNA obtained from victim material and ante-mortem (AM) DNA provided by biological relatives of missing persons, optionally supplemented with auxiliary information such as sex. This paper is concerned with the computational aspects of identification cases involving multiple and possibly related victims, after the data have been collected [21, 26].

A standard approach matches a victim to a missing person when that specific match is strongly supported by the genetic evidence. When the identified individual belongs to a reference family, the victim’s profile can then be incorporated into the reference data to help identify other missing relatives in the same family. This process is repeated until no new identifications can be made. Following [31, 5], we refer to this as a sequential method.

Sequential methods, such as those implemented in Bonaparte [7, 23] and Familias [9, 15] can perform well when individual identifications are strongly supported and hence effectively independent. However, each decision is made using only part of the evidence available for the complete DVI case. Once an assignment has been accepted, it is generally treated as fixed, and later decisions are conditioned on that assignment rather than being obtained by reconsidering all assignments simultaneously. An early incorrect assignment can therefore propagate through the remaining analysis and produce additional incorrect or order-dependent identifications [31]. Sequential methods may also miss assignments that receive strong support jointly but only weak support when evaluated pairwise [5].

Joint identification, as advocated in [31, 5], addresses these limitations. This approach seeks assignments that maximize the joint likelihood over all identifications. To the best of our knowledge, the RR-package dvir [30] is the only freely available software that supports joint DVI computations. Although it contains several elements to speed up the evaluation process, it is limited in the size of the problems it can consider. In this work, we contribute to the literature on joint DVI by combining local inference within reference families with global optimization. We reduce the assignment space through genetic compatibility filtering, likelihood-based pruning, and symmetry reduction, and use a polynomial reformulation of the Elston–Stewart algorithm for efficient parallel likelihood evaluation on GPUs. An integer linear program then combines the resulting assignments and likelihoods to determine the global maximum-likelihood assignment. The source code of our new approach is freely available from https://github.com/[].

In § 2, we describe the core components of our approach for DNA-based DVI problems, after which we present the results and the method’s limitations in § 3 and § 4 respectively. Before presenting the method, we emphasize that DNA evidence is interpreted probabilistically. With sufficient genetic data, conclusions can often be drawn with high confidence; however, the most likely explanation may nevertheless differ from the ground truth. This is a natural limitation of DNA; the probabilistic uncertainty cannot be eliminated entirely, but this uncertainty can be reduced by allowing additional, potentially non-genetic information to be incorporated [28, 4]. For this reason, the method returns a ranked list of the most likely configurations rather than returning only the single best explanation, so that they can be evaluated alongside the other case-specific evidence. For forensic practitioners, such a list generally provides an adequate basis for subsequent forensic decision-making [5].

Methods

Definitions

We begin with a formal outline of the DVI problem. Following [31], the first component is the ante-mortem (AM) data. This is a collection

M={M1,…,Mt,O1,…,Os′},(1)\mathcal{M} = \{M_1,\ldots,M_t,O_1,\ldots,O_{s'}\}, \tag*{(1)}

of tt missing persons accompanied by s′≤ss' \le s open spots. This number s′s' is bounded by the post-mortem (PM) data, written as

V={V1,…,Vs,⋆1,…,⋆t′},(2)\mathcal{V} = \{V_1,\ldots,V_s,\star_1,\ldots,\star_{t'}\}, \tag*{(2)}

which consists of the genetic profiles of ss victims together with t′≤tt^{\prime} \le t untyped ‘dummy’ victims. The open spots and untyped victims are created to formally allow the option for victims and missing persons to remain unidentified. We require that s+t′=t+s′s+t^{\prime}=t+s^{\prime} and call a problem fully open if both s=s′s=s^{\prime} and t=t′t=t^{\prime}.

In addition to the AM data, we have (disjoint) reference families F1,…,FJF_1,\ldots,F_J. We denote Ij⊆MI_j \subseteq\mathcal{M} for the missing persons of family FjF_j. To accommodate for the open spots, we define I0:=⋃i=1s′{Oi}I_0 := \bigcup_{i=1}^{s^{\prime}}\{O_i\}, so that M=⋃j=0JIj\mathcal{M}=\bigcup_{j=0}^{J} I_j.

The individuals in a reference family are of the following three types:

  • Known members: relatives for whom DNA profiles are available. These supply AM genetic information used to evaluate the plausibility of each PM–missing match.

  • Untyped members: individuals required for the pedigree structure but without observed genotypes. Their genetic states are unknown and must be summed or marginalized over when computing likelihoods.

  • Missing members: individuals whose identities are sought. They correspond to the elements of M\mathcal{M} and must be matched to PM samples if genetically supported.

For a graphical representation of these concepts, see e.g. Figure 2.1 below. Next, we represent a joint identification by an assignment. This is a map

A small DVI problem with post-mortem samples, open spots, families, typed references, missing persons, and untyped relatives

Figure 2.1. A small DVI problem with s=t=4s = t = 4.

x:M→V,(3)x:\mathcal{M}\to\mathcal{V}, \tag*{(3)}

where x(Mj)=Vix(M_j)=V_i indicates that PM sample ViV_i is identified as missing person MjM_j. In this notation, x(Mj)=∗ix(M_j)=*_{i} indicates that MjM_j has not (yet) been identified, and similarly, x(Oi)=Vjx(O_i)=V_j in turn reflects that victim VjV_j is not matched to any reference family. Assignments must of course be bijective as a victim should not be identified with more than one missing person.

Even for moderate values of ss and tt, the number of possible assignments can be extremely large [31]. Exhaustive evaluation of all possible xx to find the most likely assignment is therefore computationally prohibitive. The following theorem makes this precise.

Theorem 2.1. The DVI problem is NP-hard.

We refer to Section A for a formal statement and proof.

A key observation towards an optimal assignment is that the dependencies that drive the complexity occur locally, i.e. only within reference families. The likelihood of a global assignment therefore decomposes into a product of conditional likelihoods per family. As we will see, calculating all configurations per family is still not an easy task, but already much better than counting all possible global assignments.

Once this is done, we rephrase the DVI problem into the language of integer linear programs (ILPs) [32]. The resulting ILP is very similar to an exact weighted set cover problem [1], which can usually be solved with the help of standard ILP solvers [25]. This process returns the globally optimal assignment and, if desired, a ranked list of near-optimal alternatives.

In the remainder of this section, we will cover the core principles of the implementation.

ILP formulation

In order to rewrite a DVI problem into an ILP, we introduce some notation. We start by writing djd_j for the number of missing persons in family FjF_j. We let Vdj\mathcal{V}^{d_j} be the tuples of cardinality djd_j of V\mathcal{V} representing the space of all possible assignments for the missing persons, in a family FjF_j. We furthermore assume an ordering on Vdj\mathcal{V}^{d_j} and write si,j∈Vdjs_{i,j} \in\mathcal{V}^{d_j} for its ii-th element.

Then, for any assignment si,j∈Vdjs_{i,j} \in\mathcal{V}^{d_j}, we denote the conditional likelihood with

P(si,j∣Fj)(4)P(s_{i,j} \mid F_j) \tag*{(4)}

for each si,js_{i,j}. In this work, the likelihood [11, 17] is calculated assuming Mendelian segregation, unlinked markers, linkage equilibrium and mutation models. We further define the weights

wi,j:=log⁡(P(si,j∣Fj))(5)w_{i,j} := \log(P(s_{i,j} \mid F_j)) \tag*{(5)}

as the corresponding natural log-likelihood of the victims placed in FjF_j, and define xi,jx_{i,j} as an indicator function that is 1 if the restriction x∣Ijx|_{I_j} is equal to si,js_{i,j}.

For the global log-likelihood L(x)L(x) of the assignment xx, we can now write

L(x):=∑j=0J∑i=1njwi,jxi,j,(6)L(x) := \sum_{j=0}^{J} \sum_{i=1}^{n_j} w_{i,j}x_{i,j}, \tag*{(6)}

where njn_j denotes the number of candidate assignments to FjF_j. The objective is to identify the assignment xx that maximizes the likelihood L(x)L(x) among all feasible mappings, given the PM and AM data. With the above notation, we can reformulate this as

max⁡∑j=0J∑i=1njwi,jxi,j(7)\max\sum_{j=0}^{J} \sum_{i=1}^{n_j} w_{i,j}x_{i,j} \tag*{(7)}

subject to

∑i=1njxi,j=1 for all 0≤j≤J,(8)\sum_{i=1}^{n_j} x_{i,j} = 1 \text{ for all } 0 \leq j \leq J, \tag*{(8)}

meaning that every family gets one single assignment for the missing persons and

∑j=0J∑i:v∈si,jxi,j=1 for all v∈V,(9)\sum_{j=0}^{J} \sum_{i:v\in s_{i,j}} x_{i,j} = 1 \text{ for all } v \in\mathcal{V}, \tag*{(9)}

meaning that every victim is only assigned once. In (2.9), v∈si,jv \in s_{i,j} indicates with slight abuse of notation that vv occurs as an entry in si,js_{i,j}. Note that (2.8) and (2.9) effectively require xx to be an injection and thus a bijection from M\mathcal{M} to V\mathcal{V}.

The above reduces the problem to finding the values wi,jw_{i,j} for each jj. That is, for each family FjF_j, we need to find the likelihood of all possible assignments. Generally, this still poses computational problems because the number of all possible assignments quickly explodes as ss and tt become larger, see [31] for an exact count. Before we discuss the main strategies to overcome this hurdle, we present the following toy DVI example of manageable size.

Example 1. Consider Figure 2.1. In this example, the PM data consists of four victims V1V_1 through V4V_4 that have been recovered, each with a known DNA profile. The AM data involves two families F1F_1 and F2F_2. Both contain typed reference relatives and a number of missing individuals whose identities are sought. Family F1F_1 has two missing persons M1M_1 and M2M_2, with M1M_1 being a child of the typed reference R1R_1. Family F2F_2 has two missing persons M3M_3 and M4M_4, whose parents are the typed references R2R_2 and R3R_3. The problem is fully open, as we have 4 open spots (F0F_0) and 4 dummy victims ∗1*_{1} through ∗4*_{4}.

For the sake of simplicity, we assume data on only one locus, with alleles aa, bb and cc. The frequencies are pa=0.2p_a = 0.2, pb=0.3p_b = 0.3, pc=0.5p_c = 0.5, and for simplicity, we do not include any mutation model. We start with F0F_0. Mapping all open spots to victims results in the probability of finding the victim profiles in random unrelated individuals, as summarized in the following table.

Decision variableO1O_1O2O_2O3O_3O4O_4Likelihood formulaNumerical valueWeight wi,0w_{i,0}
x1,0x_{1,0}V1V_1***2papb2p_a p_b0.12−2.12-2.12
x2,0x_{2,0}*V2V_2**2papc2p_a p_c0.2−1.61-1.61
x3,0x_{3,0}**V3V_3*pb2p_b^20.09−2.41-2.41
x4,0x_{4,0}***V4V_42pbpc2p_b p_c0.3−1.20-1.20
x5,0x_{5,0}V1V_1V2V_2V3V_3V4V_48pa2pb4pc28p_a^2p_b^4p_c^20.000648−7.34-7.34
x6,0x_{6,0}****110.00

Table 1. Some assignments for F0F_0. The weights of configurations not on this list can be computed as a combination of the first four entries.

Note that the assignment that corresponds to the decision x5,0=1x_{5,0} = 1 connects all open spots with victims, thus also mapping all missing persons to untyped individuals. We call this trivial assignment the null baseline.

Next, we calculate all feasible partial assignments for F1F_1 and F2F_2 separately. Starting with F1F_1, we note that M1M_1 must inherit aa from R1R_1, therefore V3V_3 or V4V_4 on M1M_1 will always result in a likelihood of 0. The weights wi,1w_{i,1} of the non-zero likelihoods are presented in Table 2.

Decision variableM1M_1M2M_2Likelihood formulaNumerical valueWeight wi,1w_{i,1}
x1,1x_{1,1}V1V_1V2V_212pbpc\frac{1}{2}p_b p_c0.075−2.59
x2,1x_{2,1}V1V_1V3V_312pb2\frac{1}{2}p_b^20.045−3.10
x3,1x_{3,1}V1V_1V4V_412pbpc\frac{1}{2}p_b p_c0.075−2.59
x4,1x_{4,1}V1V_1∗*pbp_b0.3−1.20
x5,1x_{5,1}V2V_2V1V_112pbpc\frac{1}{2}p_b p_c0.075−2.59
x6,1x_{6,1}V2V_2V4V_412pbpc\frac{1}{2}p_b p_c0.075−2.59
x7,1x_{7,1}V2V_2∗*pcp_c0.5−0.69
x8,1x_{8,1}∗*V1V_112pb+papb\frac{1}{2}p_b+p_a p_b0.21−1.56
x9,1x_{9,1}∗*V2V_212pc+papc\frac{1}{2}p_c+p_a p_c0.35−1.05
x10,1x_{10,1}∗*V3V_312pb2\frac{1}{2}p_b^20.045−3.10
x11,1x_{11,1}∗*V4V_4pbpcp_b p_c0.15−1.90
x12,1x_{12,1}∗*∗*110.00

Table 2. Non-zero configurations for F1F_1 of Figure 2.1. An ∗* indicates that a missing person is mapped to a dummy variable.

We repeat this for F2F_2, again noting that assigning V1V_1 or V2V_2 will immediately result in likelihood 0. This yields

Decision variableM3M_3M4M_4Likelihood formulaNumerical valueWeight
x1,2x_{1,2}V3V_3V4V_412\frac{1}{2}0.25−1.39
x2,2x_{2,2}V3V_3∗*12\frac{1}{2}0.5−0.69
x3,2x_{3,2}V4V_4∗*12\frac{1}{2}0.5−0.69
x4,2x_{4,2}∗*∗*110.00

Table 3. Non-zero configurations for F2F_2 of Figure 2.1. An ∗* indicates that a missing person is mapped to a dummy variable. Symmetries are not included.

With the above tables, we can find a global optimum by combining the best partial assignments into a feasible global assignment xx. In this case, an optimal xx is such that x(Mi)=Vix(M_i)=V_i and x(Oi)=∗ix(O_i)=*_{i}. In the linear program, this amounts to the decisions x6,0=x1,1=x1,2=1x_{6,0}=x_{1,1}=x_{1,2}=1.

Reducing the number of local calculations

In the above example, it is possible to calculate all weights by hand. As explained above, this becomes impractical with larger families and more victims to consider. We discuss the main strategies to address this problem below.

Eliminating local assignments

As demonstrated in the example, any assignment that contains a partial assignment with zero likelihood can never be better than the null baseline of assigning all missing persons to the dummy variables. For instance, placing V3V_3 on M1M_1 will globally yield L(x)=−∞L(x) = -\infty if xx includes this identification, since V3V_3 carries no aa allele and M1M_1 must inherit aa from reference R1R_1. This partial assignment can thus be discarded outright, without evaluating any combination of V3V_3 with other missing persons.

In order to exploit this idea more efficiently, we can make use of the assumed genetic independence between loci. Instead of immediately considering the product over all loci, we calculate the likelihoods locus by locus. As soon as a single locus already yields a zero for a partial assignment, evaluation on other loci is redundant.

When a mutation model is incorporated, which is generally the case, practically impossible partial assignments will generally not be zero but very close to zero, typically still below the null baseline. This idea still works in this case, but we have to be a bit more careful with such eliminations, since we are interested in the top kk best assignments. The justification lies in the observation that the null baseline is usually a very poor explanation of the data. For that reason, discarding even worse configurations does generally not affect the ultimate goal of providing a list of the most likely solutions. In the highly unlikely case that this happens, it will automatically be noted because the null baseline will then be included in the top kk.

This principle becomes more powerful when one uses a feasible “good guess” instead of the null baseline. When a problem is not fully open, this is automatically required, because assigning only dummy variables is then not allowed. Feasible baselines can be easily found using current sequential algorithms [30].

An efficient order of evaluation

The effectiveness of finding highly unlikely partial assignments often depends on the order in which missing individuals are assigned. Preferably, this is done at an early stage, thus eliminating all downstream possibilities simultaneously. As such, the greatest gains come from assigning the most forcing individuals first. In the running example, M1M_1 is a direct child of typed reference R1R_1, meaning Mendelian inheritance strongly constrains which victim genotypes are compatible. M2M_2, by contrast, is connected to the pedigree only through M1M_1. Scanning M1M_1 first therefore eliminates far more candidates before any combination with M2M_2 is considered.

Pre-filtering via inverse search

So far, the improvements have been on the AM side, taking advantage of the structure of the reference families. Here, we also present an improvement for the processing of the PM data. Rather than evaluating all candidate victims against a missing person and discarding incompatible ones after the fact, we can derive the eligible pool directly from the available constraints without carrying out a full likelihood evaluation. Three sources of constraint are exploited.

  • Typed references constrain the genotypes a missing individual can carry via Mendelian inheritance. In the running example, both parents of M3M_3 are typed (R2R_2: b/bb/b, R3R_3: b/cb/c), so M3M_3 can only be (b,b)(b,b)

or (b,c)(b,c). Victims with any other genotype are excluded immediately. Intersecting this constraint simultaneously across multiple loci typically reduces the candidate pool from hundreds of victims to a handful. For M1M_1, with only one typed parent (R1R_1: a/aa/a), only victims carrying at least one aa allele qualify. For M2M_2, whose only typed relative is grandparent R1R_1 separated by the unresolved slot M1M_1, no genotype constraint can be propagated without first knowing who fills M1M_1.

  • When available, the sex recorded for each missing individual in the pedigree provides an immediate filter: victims of the wrong sex are excluded at no computational cost.

  • When two missing slots stand in a parent–child relationship with each other, placing a victim in the parent slot constrains the child slot: a compatible victim must share at least one allele with the assigned parent at every typed locus. This constraint is applied dynamically as the recursion proceeds.

Together, these three filters can eliminate the vast majority of candidate victims before the likelihood evaluations even begin, leaving only a small pool of genetically plausible assignments to evaluate. As before, this idea also works when mutation is incorporated, where one discards the very unlikely local configurations with the aid of a suitable global baseline.

Naturally, these strategies do not reveal their power in the small example above, but we will demonstrate their effectiveness in the next section. To conclude this section, we describe another, separate component of our method. It provides a way to evaluate the remaining assignments very efficiently, while also breaking symmetry along the way. In large cases this is a hugely useful tool, because it automatically removes many redundancies in the top kk.

Faster evaluations

In the human case of little inbreeding and frequent application of mutation models, the standard approach for likelihood evaluations is the Elston–Stewart (ES) algorithm [11]. Although the current ES implementations are quite fast, we do benefit from a bespoke implementation. This involves an algorithm that returns a polynomial for any given (non-inbred) pedigree. With this polynomial, the likelihood of an assignment to a pedigree then reduces to simply plugging in zeroes and ones depending on the genetic information that we have.

This approach has two main advantages. Firstly, evaluation can be done utilizing a graphics processing unit (GPU) [14], offering significant advantages in case of evaluating high numbers of assignments on the same pedigree. Secondly, polynomials effectively expose symmetries such as multiple missing siblings.

Due to the high notational burden, we refer to the appendix for a complete description of the algorithm. In the remainder of this section, we only demonstrate the method on a small example.

Consider the following pedigree in Figure 2.2. We work with only two alleles aa and bb. This gives K=3K=3 possible profiles, namely aaaa, abab and bbbb. We further suppose that pa=pb=12p_a=p_b=\frac{1}{2}, so that P(aa)=P(bb)=14P(aa)=P(bb)=\frac{1}{4}, P(ab)=12P(ab)=\frac{1}{2}.

A nuclear family with one child, with one marker shown

Figure 2.2. A nuclear family with one child, with one marker shown.

A direct calculation of the likelihood of the above assignment could run as follows. The parents FF and MM are non-inbred and thus independent, so that P(F=ab,M=aa)=P(ab)P(aa)=18P(F=ab,M=aa)=P(ab)P(aa)=\frac{1}{8}. The mother MM passes on aa to CC, and CC has a 50% chance of inheriting bb from FF, so that P(C=ab∣F=ab,M=aa)=12P(C = ab \mid F = ab, M = aa) = \frac{1}{2}. This yields P(F=ab,M=aa,C=ab)=116P(F = ab, M = aa, C = ab) = \frac{1}{16}.

In our algorithmic approach, we introduce KK variables for each individual. In this example, we write xaa,xab,xbbx_{aa}, x_{ab}, x_{bb} for the father. If the father is known to be aaaa for example, we set xaa=1x_{aa}=1 and xab=xbb=0x_{ab}=x_{bb}=0. If the father is unknown, we set xaa=xab=xbb=1x_{aa}=x_{ab}=x_{bb}=1. For the mother we write yaa,yab,ybby_{aa}, y_{ab}, y_{bb} with the same interpretation. This yields the following vector with the product of the genotype indicators and the probability of the corresponding genotypes:

v=(116xaayaa,18xaayab,116xaaybb,18xabyaa,14xabyab,18xabybb,116xbbyaa,18xbbyab,116xbbybb).(10)v=\left(\frac{1}{16}x_{aa}y_{aa},\frac{1}{8}x_{aa}y_{ab},\frac{1}{16}x_{aa}y_{bb},\frac{1}{8}x_{ab}y_{aa},\frac{1}{4}x_{ab}y_{ab},\frac{1}{8}x_{ab}y_{bb},\frac{1}{16}x_{bb}y_{aa},\frac{1}{8}x_{bb}y_{ab},\frac{1}{16}x_{bb}y_{bb}\right). \tag*{(10)}

Moving on to CC, we precalculate all the probabilities P(C∣F,M)P(C\mid F,M) and store these in a matrix (not displayed here). We write the variables zaa,zab,zbbz_{aa},z_{ab},z_{bb} to store our knowledge about CC. Given the information in Figure 2.2, we immediately conclude that zaa=zbb=0z_{aa}=z_{bb}=0, zab=1z_{ab}=1 cf. § 2.3.1. Thus in this example, we only need the following vector

w=(0,12zab,zab,12zab,12zab,12zab,12zab,12zab,0),(11)w=\left(0,\frac{1}{2}z_{ab},z_{ab},\frac{1}{2}z_{ab},\frac{1}{2}z_{ab},\frac{1}{2}z_{ab},\frac{1}{2}z_{ab},\frac{1}{2}z_{ab},0\right), \tag*{(11)}

where the coefficients are now equal to P(C=ab∣F,M)P(C=ab\mid F,M).

The main point is that the likelihood of the entire pedigree can be obtained from the following inner product:

⟨v,w⟩=zab16(xaayab+xaaybb+xabyaa+2xabyab+xabybb+xbbyaa+xbbyab).(12)\langle v,w\rangle=\frac{z_{ab}}{16}\left(x_{aa}y_{ab}+x_{aa}y_{bb}+x_{ab}y_{aa}+2x_{ab}y_{ab}+x_{ab}y_{bb}+x_{bb}y_{aa}+x_{bb}y_{ab}\right). \tag*{(12)}

In case of Figure 2.2 all variables are 0, apart from zabz_{ab}, xabx_{ab} and yaay_{aa}. This yields the correct answer of 116\frac{1}{16}.

To demonstrate the flexibility of (2.12), suppose for instance that the father is unknown. Then

P(M=aa,C=ab)=P(C=ab,F=aa,M=aa)+P(C=ab,F=ab,M=aa)+P(C=ab,F=bb,M=aa)=0+116+116=18.(13)\begin{aligned} P(M=aa,C=ab) &= P(C=ab,F=aa,M=aa)\\ &\quad+P(C=ab,F=ab,M=aa)\\ &\quad+P(C=ab,F=bb,M=aa)\\ &=0+\frac{1}{16}+\frac{1}{16}=\frac{1}{8}. \tag*{(13)} \end{aligned}

Indeed, when we take xaa=xab=xbb=1x_{aa}=x_{ab}=x_{bb}=1, we see that

⟨v,w⟩=116(1+1)=18.(14)\langle v,w\rangle=\frac{1}{16}(1+1)=\frac{1}{8}. \tag*{(14)}

This procedure translates the recursive ES-algorithm into a fixed set of (sparse) matrix operations, which are known to be very efficiently calculated on GPUs [3].

Symmetries

In simple pedigrees, symmetries are usually easy to spot with the human eye. For example, it is immediately clear that in case of two missing brothers, permuting the two will not change the likelihood.

For a computer, this is much more difficult as graphs are complex objects to process. The above algebraic representations automatically yield all symmetries by identifying the symmetric variables.

As an example, if we ignore sex, it is intuitively clear that swapping the parents in a nuclear family does not change the likelihood if we only consider autosomal DNA. With our method, the algorithm can easily deduce this from (12), because the polynomial is invariant under the swapping (xaa,xab,xbb)↔(yaa,yab,ybb)(x_{aa}, x_{ab}, x_{bb}) \leftrightarrow(y_{aa}, y_{ab}, y_{bb}).

A similar mechanism works when we compare different pedigrees. Suppose that in one pedigree, we are looking for a man, his father and his grandfather. In the other pedigree, we are also looking for a man and his father, but instead of the grandfather we are missing a half-brother.

Two symmetric pedigrees

Figure 2.3. Two symmetric pedigrees.

The dependencies between XX, YY and ZZ are identical in both cases. As before, this is straightforward to see from a genetic perspective, but non-obvious for a computer. However, after reducing the pedigrees to their respective inner product, the resulting polynomials will be identical.

Finally, we note that the polynomials can also be used to detect independencies within pedigrees. If the polynomial can be factorized such that all individuals are all contained in one factor, the factors represent the independent branches of the pedigree. For DVI cases however, this is generally not relevant. Large pedigrees are uncommon and recognizing and redefining separate branches of a pedigree is not difficult.

Results

In this section, we evaluate our method using simulated data motivated by DVI cases mentioned in the introduction. § 3.1 compares our method with an exhaustive-search baseline, illustrating the combinatorial growth of the assignment space. § 3.2 examines computational performance across twelve pedigree designs of increasing assignment space. In § 3.3 we consider three case studies: a simulated passenger-flight incident involving 300 victims, a simulated mass grave involving 10,000 victims, and a quasi-empirical case concerning Argentinian children. The latter case also illustrates the interpretation of the top-kk highest-likelihood assignments. Finally, § 3.4 presents an ablation study to assess the contribution of the algorithmic components across these designs.

For the simulations, we use 23 loci of the Norwegian STR frequency database distributed with the forrel package in R [8] and we use an equal (also called uniform) mutation model [10, 22]. All runs were performed on the Snellius supercomputer using a single NVIDIA A100 GPU (40 GB) and 12 cores of an Intel Xeon Platinum 8360Y processor.

Naive exhaustive validation on small instances

Consider kk independent families, each containing one typed grandfather and two missing grandsons, so victims and missing persons both number 2k2k. See Figure 3.1.

Schematic DVI instance with k independent reference families

Figure 3.1. Schematic DVI instance with kk independent reference families, each containing two missing grandsons. The additional group F0F_0 contains the open spots, while dummy victims allow missing persons to remain unidentified.

We carried this out up to k=3k = 3 of such reference families; since at k≥4k \ge4, full enumeration becomes infeasible. The results are displayed in Table 4.

MethodLikelihood evaluationsSaved evaluations
k=1k = 1: 2 victims, 2 missing (7 assignments)
Exhaustive483337
Our method14669.77%
k=2k = 2: 4 victims, 4 missing (209 assignments)
Exhaustive28 84228 395
Our method44798.45%
k=3k = 3: 6 victims, 6 missing (13 327 assignments)
Exhaustive2 758 6892 757 648
Our method1 04199.96%

Table 4. Exhaustive enumeration of distinct assignments compared with our method. Assignments that differ only in dummy labels or open-spot order are counted once. Savings are reported as absolute counts and percentage reductions in likelihood evaluations relative to exhaustive enumeration.

Across all enumerated instances, our method recovered the same maximum-likelihood solution as exhaustive search, while requiring far fewer likelihood evaluations. The relative savings increased with problem size. For k=3k = 3, the exhaustive baseline requires 2,758,689 likelihood evaluations across 13,327 distinct assignments, compared with 1,041 evaluations for our method, corresponding to a reduction of approximately 99.96%.

Twelve designs

The number of assignments that need to be evaluated depends on both the number of missing persons and the pedigree structure. Assignments involving parent-child relationships are genetically easier to exclude than distant relatives or full siblings. Although full siblings and parent–child pairs have the same coefficient of relationship, siblings need not share an allele at every locus, making early exclusion of incompatible candidates more difficult.

In this experiment, we define twelve pedigree structures of increasing complexity. The pedigrees are displayed in Figure 3.2. For each of these designs, we construct an open DVI case consisting of 10 pedigrees of that type. We apply our method and compute the average runtime after 10 repetitions. Finally, we repeat the experiment under three mutation settings: no mutation, equal mutation, and a bounded, symmetric stepwise mutation model [19, 10, 22]. The average and maximum runtimes are reported in Table 5.

The twelve pedigree designs, grouped by the number of missing persons $v$, showing twelve pedigree designs labeled Parent–child, Two siblings, Grandparent–grandchild, Father and child, Brother and nephew, Three siblings, Father and two children, Mother and two children, Four siblings, Father and three children, Parents and two children, and Four grandchildren; legend: Typed reference, Missing person, Untyped relative

Figure 3.2. The twelve pedigree designs, grouped by the number of missing persons vv.

DesignvvStrongest relationshipNo mutation meanNo mutation worstEqual meanEqual worstStepwise meanStepwise worst
11Parent-Child3.5 s6.1 s1.2 s3.5 s1.0 s2.8 s
21Sibling4.6 s7.4 s2.3 s9.0 s2.9 s4.0 s
31Grandparent-Grandchild4.0 s5.3 s1.3 s1.8 s4.5 s5.1 s
42Parent-Child4.6 s6.3 s1.7 s2.5 s5.9 s7.6 s
52Sibling/Parent-Child6.5 s7.9 s6.1 s8.2 s26.4 s32.0 s
62Sibling5.2 s6.5 s5.1 s6.9 s51.5 s86.8 s
73Parent-Child6.1 s7.9 s3.2 s4.2 s15.0 s17.0 s
83(Grand)parent-(Grand)child12.5 s14.5 s18.1 s31.9 s112.6 s175.7 s
93Sibling8.2 s10.4 s49.6 s60.1 s161.0 s217.6 s
104Parent-Child8.3 s10.3 s6.0 s7.8 s32.1 s35.6 s
114Parent-Child18.1 s32.1 s63.4 s79.1 s339.6 s481.2 s
124Grandparent-Grandchild/Siblings44.5 s66.2 s292.2 s423.2 s999.5 s1512.0 s

Table 5. Solve time for the twelve designs. Mean and worst-case total solve time in seconds over ten replicates. Equal: mutation rate 0.001; Stepwise: p1=0.0012p_1 = 0.0012, p2=0.0001p_2 = 0.0001.

Not surprisingly, the runtime increases when the family relationships become weaker. Notably, the more flexible equal mutation model is often faster than the stepwise mutation model. This is due to the fact that allele lumping is often more effective in the case of an equal mutation model. Without a mutation model, certain additional optimizations are possible which are more effective for computationally more demanding cases, however, they do come at a slight cost for computationally easier cases.

Case studies

In this section we discuss three case studies.

A passenger flight

We demonstrate our method on simulated data that represents a plane crash involving 300 individuals (the Malaysia Airlines Flight 17 involved 298 passengers and crew). To the best of our knowledge, no methods exist to jointly solve a DVI problem of this scale.

We simulate a DVI case with 100 pedigrees. Each pedigree has at most 4 missing members. Victim relationships are generally close: after a randomly chosen first victim, each further victim is drawn with probability 0.5 from the immediate relatives (parents, children or full siblings) of those already chosen, and otherwise uniformly over the remainder of the pedigree. Sampling victims in this manner resembles the characteristics of a passenger flight: distant family relationships of fellow travelers are uncommon. Our method solved this instance in 4.5 minutes.

Mass grave

In this example, we consider an instance resembling a mass grave. We simulate this similarly to the plane crash. However, we consider a maximum of 3 victims per pedigree. The instance comprises 3500 pedigrees with 5132 missing persons, plus 3000 victims without a reference family and 3000 missing persons in reference pedigrees without a victim. The problem is open on both sides.

Our method solves this instance in 29 hours. The computational cost is highly skewed: the median pedigree takes 7.7 seconds, whereas the five most expensive pedigrees account for 46% of the compute needed and the four heaviest take over 26 hours each. These are pedigrees in which three members are missing and no typed parent or child constrains the search, so that the number of candidate assignments explodes. In practice, these pedigrees could be handled separately or using different methods to significantly shorten the computation time.

Note that the parameters of this instance are very similar to large disasters such as earthquakes and tsunamis.

Argentinian children

We constructed a DVI case based on the 25 pedigrees in Supplementary Table S1 of [15], with one missing person per family. Using 23 STR loci and Norwegian allele frequencies, we simulated AM reference genotypes and 25 PM profiles. The families were analysed jointly while assuming genetic independence between pedigrees. The highest-ranked assignment had a substantially larger log-likelihood −9509 than the second-ranked assignment −9549, indicating strong relative support for the first assignment with a likelihood ratio of 2.61×10172.61 \times10^{17}.

Ablation study

To assess which components drive the framework’s computational gains, we performed a leave-one-component-out ablation on the twelve pedigree designs in Figure 3.2. For each instance, we changed one component or execution setting at a time, keeping the simulated data and all remaining settings fixed. Table 6 reports runtimes relative to the complete method for variants targeting search reductions, precomputation, GPU acceleration, and worker parallelism. These comparisons quantify each component’s incremental contribution within the complete pipeline and how that contribution varies across pedigree structures.

DesignvvVVfullNo LumpingNo PC FilterNo PrecomputeNo P1 filterNo Obj FilterNo SymmetryCPUNo parallelism
1124014 (1.00×)43 (3.10×)10 (0.74×)10 (0.69×)8 (0.60×)11 (0.80×)20 (1.45×)9 (0.67×)14 (0.99×)
2124016 (1.00×)51 (3.15×)12 (0.71×)13 (0.83×)11 (0.70×)21 (1.27×)31 (1.89×)12 (0.72×)48 (2.95×)
3124027 (1.00×)149 (5.43×)27 (1.00×)28 (1.01×)27 (0.97×)25 (0.92×)50 (1.84×)27 (0.97×)204 (7.45×)
4224066 (1.00×)146 (2.21×)68 (1.03×)56 (0.84×)54 (0.81×)87 (1.32×)87 (1.32×)175 (2.66×)181 (2.75×)
52240105 (1.00×)319 (3.05×)115 (1.10×)107 (1.02×)108 (1.03×)146 (1.40×)174 (1.66×)339 (3.24×)371 (3.54×)
6224072 (1.00×)154 (2.13×)74 (1.02×)73 (1.02×)80 (1.11×)137 (1.90×)156 (2.16×)328 (4.55×)302 (4.20×)
7324075 (1.00×)245 (3.27×)162 (2.17×)67 (0.89×)66 (0.88×)366 (4.89×)748 (10.01×)320 (4.28×)270 (3.61×)
83240127 (1.00×)245 (1.94×)143 (1.13×)109 (0.86×)119 (0.94×)362 (2.86×)1265 (10.00×)552 (4.36×)413 (3.26×)
93240208 (1.00×)1394 (6.70×)207 (0.99×)395 (1.90×)217 (1.04×)1053 (5.06×)2078 (10.00×)1268 (6.10×)455 (2.19×)
104240466 (1.00×)1789 (3.84×)4658 (10.00×)346 (0.74×)447 (0.96×)4658 (10.00×)4658 (10.00×)2139 (4.59×)2094 (4.50×)
114240361 (1.00×)1169 (3.24×)2136 (5.91×)241 (0.67×)345 (0.96×)2513 (6.96×)3613 (10.00×)2082 (5.76×)1733 (4.80×)
1242405312 (1.00×)34194 (6.44×)5504 (1.04×)9153 (1.72×)5406 (1.02×)53116 (10.00×)53116 (10.00×)44800 (8.43×)12651 (2.38×)

Table 6. Runtimes in seconds (rounded to integers), with ratios to the full run in parentheses. vv denotes the number of victims per design and VV the total number of victims in the DVI case. The uniform mutation model is used. Ratios and shading use unrounded data. full and faster runs are white; grayscale increases linearly to black at 10× baseline, which was set as a time-out condition.

Table 6 shows that the effectiveness of the different strategies depends on pedigree structure. For example in design 11, assigning the one missing parent immediately constrains their children and hence the other parent, whereas in design 12 the missing siblings’ parents are untyped, leaving no direct parent–child pairs to check. Removing parent–child filtering therefore slows design 11 by 5.91 but barely affects design 12 (1.04). Symmetry reduction, cache sharing, and objective filtering matter more as the search space grows. Allele lumping affects the time needed for the likelihood evaluations and thus impacts all designs.

The compute ablations show how the bottleneck shifts with problem size. On the smallest workloads (designs 1–3), CPU-only runs are competitive because GPU launch and transfer overhead offsets the speedup. On designs 9 and 12, however, dropping to CPU slows execution by 6.10 and 8.43 respectively, whereas dropping to a single worker costs only 2.19 and 2.38 respectively. Because early pruning is weaker in these designs, more likelihood evaluations reach the GPU. Once the shared device is fully used, adding workers helps very little. Similarly, precomputation pays off in designs 9 and 12 where the setup cost is amortized due to the large number of evaluations and the relatively expensive likelihood evaluations. The effectiveness of the P1 filter is strongly dependent on the mutation model used. For equal mutation, it does not provide any speedup as no branch can be cut early.

Discussion

Although this paper is completely built on the presumption that DVI cases should be analysed and reported jointly, this is not always possible in practice. In large cases such as the Malaysia Airlines Flight 17, the circumstances often naturally lead to a sequential approach. Some victims are immediately found and readily identified, while other samples are found much later. Another factor is the quality of the samples: sometimes new techniques have to be developed in order to retrieve suitable DNA profiles.

In the meantime, the (usually strong) evidence at hand is used to identify as many victims as possible. This process is sequential in nature. However, because our method runs so fast, it can be used multiple times during the identification process. One can add as many dummy variables as needed to jointly run the analysis for the recovered victim samples and rerun the algorithm as more victims come in. In this way, new identifications can be made while simultaneously updating or validating earlier conclusions.

Even when the reporting process is carried out sequentially, it is possible to use our method as an ultimate and global check once all victims are found.

Several methodological caveats apply more broadly to kinship-based identification and fall outside the scope of this paper. Assumptions underlying standard kinship calculations, including Hardy–Weinberg equilibrium and marker independence, have been extensively studied elsewhere [2], as have the complications introduced by degraded or low-quality DNA samples [27].

A related concern specific to large-scale DVI operations is the choice of allele frequency database. Because victims and missing persons may originate from different populations, which naturally occur on large commercial planes, no single database may be clearly appropriate, and results can be sensitive to this choice [12]. When this is a concern, we recommend running the analysis under several candidate databases: agreement across these sensitivity checks provides added confidence that the conclusions do not meaningfully depend on a particular choice of reference population.

Although the method is aimed at DVI cases, there may be more applications for which the computational framework can be useful. For example, instances of familial searching [24] can be reformulated as DVI problems.

Conclusion

We have developed a framework that makes joint DNA-based DVI feasible in large cases by providing methods to reduce the computational burden that was pointed out by [31]. This is achieved by combining local pedigree likelihood calculations with global integer linear optimization. Genetic filtering, likelihood-based pruning, symmetry reduction, and GPU evaluation have shown to substantially reduce the runtime. We have demonstrated that typical instances with up to 10.000 victims can be readily solved. Its practical performance depends strongly on pedigree structure and the availability of informative reference relatives.

References

Appendix A. Proof of complexity

In this proof, we do not incorporate mutations and assume that s=ts=t, s′=t′=0s'=t'=0. This is a special case of the general problem and it suffices to prove hardness for such cases. We consider the following decision variant.

  • Instance: A set of typed PM samples V={V1,…,Vn}\mathcal{V}=\{V_1,\ldots,V_n\}, a set of missing individuals M={M1,…,Mn}\mathcal{M}=\{M_1,\ldots,M_n\} with an associated pedigree and AM genetic data.

  • Question: Does there exist an assignment x:M→Vx:\mathcal{M}\to\mathcal{V} such that L(x)>−∞L(x)>-\infty?

We show that this problem is NP-complete by proving (i) membership in NP and (ii) NP-hardness via a polynomial-time reduction from the Hamiltonian Path problem [13].

Membership in NP

To establish DVI∈NP\mathrm{DVI}\in\mathrm{NP}, consider a certificate consisting of an assignment xx. Given xx, the likelihood L(x)L(x) factorizes over the pedigrees induced by the assignment. For each pedigree, the likelihood is computed using Elston–Stewart. This computation is polynomial in the number of loci and linear in the number of pedigree members ([30]).

Since the total number of pedigrees is at most of order ∣V∣|\mathcal{V}|, the overall log-likelihood L(x)L(x) can be evaluated in time polynomial in the input size. Checking if L(x)>−∞L(x)>-\infty is trivial. Hence a proposed assignment can be verified in polynomial time, and therefore DVI∈NP\mathrm{DVI}\in\mathrm{NP}.

NP-hardness

To prove NP-hardness, we provide a Karp reduction [13] from the Hamiltonian Path (HP) problem, which reads as follows:

  • Instance: An undirected graph G=(W,E)G=(W,E) with ∣W∣=n|W|=n.

  • Question: Does there exist a permutation (vπ(1),…,vπ(n))(v_{\pi(1)},\ldots,v_{\pi(n)}) such that (vπ(i),vπ(i+1))∈E(v_{\pi(i)},v_{\pi(i+1)})\in E for all 1≤i<n1\le i<n?

Given a graph G=(W,E)G=(W,E) with ∣W∣=n|W|=n, we construct in polynomial time a DVI instance f(G)f(G) as follows.

Pedigree structure

We construct a linear pedigree consisting of nn missing individuals M1,…,MnM_1,\ldots,M_n, where for each i=1,…,n−1i=1,\ldots,n-1, the individual Mi+1M_{i+1} is the child of MiM_i and a typed reference spouse RiR_i. The spouses RiR_i are unrelated founders. This is a single reference family F1F_1 with I1={M1,…,Mn}I_1=\{M_1,\ldots,M_n\} and d1=nd_1=n.

PM samples and missing persons

We create nn typed PM samples V1,…,VnV_1,\ldots,V_n, establishing a one-to-one correspondence between vertices W={v1,…,vn}W=\{v_1,\ldots,v_n\} and the missing individuals. An assignment therefore induces an ordering of the vertices along the linear pedigree.

Genetic construction

For every unordered pair of distinct vertices {vj,vk}\{v_j,v_k\} with {vj,vk}∉E\{v_j,v_k\}\notin E we introduce a locus ℓjk\ell_{jk} with two alleles {a,b}\{a,b\}, with pa=pb=0.5p_a=p_b=0.5.

At locus ℓjk\ell_{jk}:

  • Victim VjV_j is assigned genotype aaaa.

  • Victim VkV_k is assigned genotype bbbb.

  • All other victims and all reference spouses RiR_i are assigned genotype abab.

We show that GG contains a Hamiltonian path if and only if the constructed DVI instance admits an assignment with strictly positive likelihood.

(⇒)(\Rightarrow). Suppose GG contains a Hamiltonian path vπ(1)→⋯→vπ(n)v_{\pi(1)} \rightarrow\cdots\rightarrow v_{\pi(n)}. Assign the corresponding PM samples to the missing individuals M1,…,MnM_1,\ldots,M_n in this order, i.e. x(Mi)=Vπ(i)x(M_i)=V_{\pi(i)}.

All members are typed once xx is fixed, so the likelihood at a locus is the product of the founder probabilities of M1M_1, R1,…,Rn−1R_1,\ldots,R_{n-1} and the transmission probabilities P(gMi+1∣gMi,gRi)P(g_{M_{i+1}} \mid g_{M_i},g_{R_i}). The founder probabilities are positive. For every adjacent pair (vπ(i),vπ(i+1))(v_{\pi(i)},v_{\pi(i+1)}), an edge exists in EE, so no locus ℓjk\ell_{jk} corresponding to a non-edge forces opposite homozygotes on a parent–child pair. Consequently, the overall likelihood is strictly positive.

(⇐)(\Leftarrow). Conversely, suppose there exists an assignment xx with L(x)>−∞L(x)>-\infty. This implies that no Mendelian incompatibility occurs at any locus. Because RiR_i has genotype abab and can transmit either allele, a trio (Mi,Ri,Mi+1)(M_i,R_i,M_{i+1}) is inconsistent exactly when parent MiM_i and child Mi+1M_{i+1} are opposite homozygotes. At locus ℓjk\ell_{jk} this happens if and only if VjV_j and VkV_k are placed on consecutive members of the chain, in either order. Therefore every consecutive pair in the induced ordering must correspond to an edge in EE, implying that the assignment defines a Hamiltonian path in GG.

The construction introduces at most O(n2)O(n^2) loci and O(n)O(n) individuals. Every single locus specification requires constant time, yielding an overall construction time of O(n3)O(n^3). Therefore the reduction is computable in polynomial time.

The DVI decision problem belongs to NP and is NP-hard via polynomial-time reduction from Hamiltonian Path. Since Hamiltonian Path is NP-complete, it follows that the DVI decision problem is NP-complete. Consequently, the associated likelihood maximization problem is NP-hard.

Example construction

Below, we provide an example of the construction defined above.

Proof of complexity

A four-vertex Hamiltonian-path instance and its corresponding closed DVI instance. The Hamiltonian-path graph shows vertices $v_1$, $v_2$, $v_3$, and $v_4$, with Hamiltonian path $v_1 \to v_2 \to v_3 \to v_4$ and nonedges $\{v_1,v_4\}$ and $\{v_2,v_4\}$. The corresponding DVI pedigree shows $U_1$, $U_2$, $U_3$, and $U_4$ with reference individuals $R_1$, $R_2$, and $R_3$. The PM and reference genotypes table has columns Profile, $\ell_{14}$, $\ell_{24}$, $\ell_{41}$, and $\ell_{42}$, and rows $V_1$: aa, ab, bb, ab; $V_2$: ab, aa, ab, bb; $V_3$: ab, ab, ab, ab; $V_4$: bb, bb, aa, aa; $R_1,R_2,R_3$: ab, ab, ab, ab.

Figure A.1. A four-vertex Hamiltonian-path instance and its corresponding closed DVI instance.

A valid assignment and an invalid assignment. The compatible assignment is $V_1,V_2,V_3,V_4$, with $L(x)>-\infty$ and Hamiltonian path $1\to2\to3\to4$. The incompatible assignment is $V_1,V_2,V_4,V_3$, with $L(x)=-\infty$ and $\ell_{24}:P(bb\mid aa,ab)=0$.

Figure A.2. A valid assignment corresponds to the Hamiltonian path (v1,v2,v3,v4)(v_1,v_2,v_3,v_4). An invalid assignment places V2V_2 immediately before V4V_4, violating Mendelian inheritance at locus ℓ24\ell_{24}.

Linear algebraic representation

In this section, we demonstrate how to calculate all likelihoods necessary for Elston–Stewart, following the reformulation announced in § 2.4. We assume linkage equilibrium, so that it suffices to work on one locus. Throughout we use the notation of § 2: families FjF_j, slots IjI_j, configurations si,j∈Vdjs_{i,j} \in\mathcal{V}^{d_j}, and weights wi,j=log⁡P(si,j∣Fj)w_{i,j} = \log P(s_{i,j} \mid F_j).

Preliminaries

We assume qq alleles a1,…,aqa_1,\ldots,a_q with subsequent allele frequencies p1,…,pqp_1,\ldots,p_q. We write K=12q(q+1)K = \frac{1}{2}q(q+1) for the number of possible genotypes, which we denote by A={A1,…,AK}\mathcal{A} = \{A_1,\ldots,A_K\}. The ordering does not matter, but we fix A1=a1a1A_1 = a_1a_1, A2=a1a2A_2 = a_1a_2, Aq=a1aqA_q = a_1a_q, Aq+1=a2a2A_{q+1} = a_2a_2 and so on.

Let G⊆AG \subseteq\mathcal{A} be a collection of genotypes. For a genotype g∈Ag \in\mathcal{A}, we define the indicator function 1G(g)∈{0,1}\mathbf{1}_G(g) \in\{0,1\} to be 1 if g∈Gg \in G. Write 2A2^{\mathcal{A}} for the power set of A\mathcal{A}. We construct the following maps IF,IM:2A↦{0,1}K2I_F,I_M : 2^{\mathcal{A}} \mapsto\{0,1\}^{K^2}, accompanied by the vectors pF,pM∈RK2p_F,p_M \in\mathbb{R}^{K^2}:

IF(G)=(1G(A1)1G(A1)⋮1G(A1)1G(A2)⋮1G(A2)1G(A3)⋮⋮1G(AK)),pF=(p12p12⋮p122p1p2⋮2p1p22p1p3⋮⋮pq2),IM(G)=(1G(A1)1G(A2)⋮1G(AK)1G(A1)⋮1G(AK)⋮1G(A1)⋮1G(AK)),pM=(p122p1p2⋮pq2p12⋮pq2⋮p12⋮pq2).(15)\begin{aligned} I_F(G) &= \begin{pmatrix} \mathbf{1}_G(A_1)\\ \mathbf{1}_G(A_1)\\ \vdots\\ \mathbf{1}_G(A_1)\\ \mathbf{1}_G(A_2)\\ \vdots\\ \mathbf{1}_G(A_2)\\ \mathbf{1}_G(A_3)\\ \vdots\\ \vdots\\ \mathbf{1}_G(A_K) \end{pmatrix}, \quad p_F = \begin{pmatrix} p_1^2\\ p_1^2\\ \vdots\\ p_1^2\\ 2p_1p_2\\ \vdots\\ 2p_1p_2\\ 2p_1p_3\\ \vdots\\ \vdots\\ p_q^2 \end{pmatrix}, \quad I_M(G) = \begin{pmatrix} \mathbf{1}_G(A_1)\\ \mathbf{1}_G(A_2)\\ \vdots\\ \mathbf{1}_G(A_K)\\ \mathbf{1}_G(A_1)\\ \vdots\\ \mathbf{1}_G(A_K)\\ \vdots\\ \mathbf{1}_G(A_1)\\ \vdots\\ \mathbf{1}_G(A_K) \end{pmatrix}, \quad p_M = \begin{pmatrix} p_1^2\\ 2p_1p_2\\ \vdots\\ p_q^2\\ p_1^2\\ \vdots\\ p_q^2\\ \vdots\\ p_1^2\\ \vdots\\ p_q^2 \end{pmatrix}. \tag*{(15)} \end{aligned}

We further write F(G):=IF(G)⊙pFF(G) := I_F(G) \odot p_F and M(H):=IM(H)⊙pMM(H) := I_M(H) \odot p_M, where ⊙\odot denotes the element-wise Hadamard product. Assuming no inbreeding, the genotypes gFg_F and gMg_M of a father FF and a mother MM are independent. Now observe that the joint likelihood that gF∈Gg_F \in G and gM∈Hg_M \in H can be expressed as

⟨F(G),M(H)⟩.(16)\langle F(G), M(H) \rangle. \tag*{(16)}

In practice, G={g}G = \{g\} or G=AG = \mathcal{A} since individuals are usually typed or unknown. The same holds for HH.

The genotypes of the children C1,…,CNC_1,\ldots,C_N of FF and MM are of course dependent on FF and MM. For them we need a different notation. We start by writing

IC(G)=(1G(A1)⋮1G(AK)).(17)I_C(G) = \begin{pmatrix} \mathbf{1}_G(A_1)\\ \vdots\\ \mathbf{1}_G(A_K) \end{pmatrix}. \tag*{(17)}

The genotypes of children are independent conditionally on their parents’ genotypes. Therefore, let CC be any child of FF and MM. For each Ai∈AA_i \in\mathcal{A}, we define

Ai=(P(C=Ai∣F=A1,M=A1)P(C=Ai∣F=A1,M=A2)⋮P(C=Ai∣F=A2,M=AK)P(C=Ai∣F=A2,M=A1)⋮P(C=Ai∣F=AK,M=AK)).(18)A_i = \begin{pmatrix} P(C=A_i \mid F=A_1, M=A_1)\\ P(C=A_i \mid F=A_1, M=A_2)\\ \vdots\\ P(C=A_i \mid F=A_2, M=A_K)\\ P(C=A_i \mid F=A_2, M=A_1)\\ \vdots\\ P(C=A_i \mid F=A_K, M=A_K) \end{pmatrix}. \tag*{(18)}

These vectors are stored in a K2×KK^2 \times K matrix as follows:

PC:=(∣∣⋯∣A1A2⋯AK∣∣⋯∣).(19)P_C := \begin{pmatrix} \vert& \vert& \cdots& \vert\\ A_1 & A_2 & \cdots& A_K\\ \vert& \vert& \cdots& \vert \end{pmatrix}. \tag*{(19)}

As with FF and MM, we write C(G):=PCIC(G)C(G) := P_C I_C(G).

Now, let P\mathcal{P} denote the pedigree where CC is a child of FF and MM. Again assuming no inbreeding, and writing gCg_C for the genotype of CC, we have

P(gF,gM,gC∣P)=⟨C(gC),F(gF)⊙M(gM)⟩,(20)P(g_F,g_M,g_C \mid\mathcal{P}) = \langle C(g_C), F(g_F) \mathbin{\odot} M(g_M)\rangle, \tag*{(20)}

with the slightly abusive notation gF={gF}g_F = \{g_F\}.

If P\mathcal{P} contains multiple children C1,…,CNC_1,\ldots,C_N with respective genotypes gC1,…,gCNg_{C_1},\ldots,g_{C_N}, the resulting expression is surprisingly simple due to conditional independence:

P(gF,gM,gC1,…,gCN∣P)=⟨⨀j=1NC(gCj),F(gF)⊙M(gM)⟩.(21)P(g_F,g_M,g_{C_1},\ldots,g_{C_N} \mid\mathcal{P}) = \left\langle\bigodot_{j=1}^{N} C(g_{C_j}), F(g_F) \mathbin{\odot} M(g_M)\right\rangle. \tag*{(21)}

The Hadamard product is associative with respect to the inner product, so that we also have

P(gF,gM,gC1,…,gCN∣P)=⟨⨀j=1NC(gCj)⊙M(gM),F(gF)⟩=⟨⨀j=1NC(gCj)⊙F(gF),M(gM)⟩,(22)\begin{aligned} P(g_F,g_M,g_{C_1},\ldots,g_{C_N} \mid\mathcal{P}) &= \left\langle\bigodot_{j=1}^{N} C(g_{C_j}) \mathbin{\odot} M(g_M), F(g_F)\right\rangle\\ &= \left\langle\bigodot_{j=1}^{N} C(g_{C_j}) \mathbin{\odot} F(g_F), M(g_M)\right\rangle, \tag*{(22)} \end{aligned}

which will be useful later on for transmitting messages. In the nuclear family example of § 2.4, v=F⊙Mv = F \mathbin{\odot} M and w=Cw = C with symbolic indicators, and the inner product (2.12) is exactly this identity.

Sending a message

When messages are sent, we again make use of conditional independence. Since there are no loops, dependencies between peels always go through exactly one individual. If we fix the profile of this individual, the separate parts this individual connects are independent.

Parent to parent

If a parent sends a message, this is one side of the inner product without the parent that is sending. Let P\mathcal{P} be the pedigree a parent is sending from. Then we write

TF:=⨀j=1NC(gCj)⊙M(gM),(23)\mathbf{T}_{F} := \bigodot_{j=1}^{N} C(g_{C_j}) \odot M(g_{M}), \tag*{(23)}
TM:=⨀j=1NC(gCj)⊙F(gF).(24)\mathbf{T}_{M} := \bigodot_{j=1}^{N} C(g_{C_j}) \odot F(g_{F}). \tag*{(24)}

Fix some profile AiA_i. We write P(P\X)P(\mathcal{P}\backslash X) for the likelihood of the given profiles in the pedigree, but without individual XX. Now observe that

P(P\F∣F=Ai)=⟨TF,IF(Ai)⟩,(25)P(\mathcal{P}\backslash F \mid F=A_i)=\langle\mathbf{T}_{F},\mathbf{I}_{F}(A_i)\rangle, \tag*{(25)}
P(P\M∣M=Ai)=⟨TM,IM(Ai)⟩.P(\mathcal{P}\backslash M \mid M=A_i)=\langle\mathbf{T}_{M},\mathbf{I}_{M}(A_i)\rangle.

This motivates the following definition for the paternal resp. maternal sideways message:

SF=(⟨TF,IF(A1)⟩⟨TF,IF(A1)⟩⋮⟨TF,IF(A1)⟩⟨TF,IF(A2)⟩⋮⟨TF,IF(A2)⟩⟨TF,IF(A3)⟩⋮⋮⟨TF,IF(AK)⟩),SM=(⟨TM,IM(A1)⟩⟨TM,IM(A2)⟩⋮⟨TM,IM(AK)⟩⟨TM,IM(A1)⟩⋮⟨TM,IM(AK)⟩⋮⟨TM,IM(A1)⟩⋮⟨TM,IM(AK)⟩).(26)\mathbf{S}_{F}= \begin{pmatrix} \langle\mathbf{T}_{F},\mathbf{I}_{F}(A_1)\rangle\\ \langle\mathbf{T}_{F},\mathbf{I}_{F}(A_1)\rangle\\ \vdots\\ \langle\mathbf{T}_{F},\mathbf{I}_{F}(A_1)\rangle\\ \langle\mathbf{T}_{F},\mathbf{I}_{F}(A_2)\rangle\\ \vdots\\ \langle\mathbf{T}_{F},\mathbf{I}_{F}(A_2)\rangle\\ \langle\mathbf{T}_{F},\mathbf{I}_{F}(A_3)\rangle\\ \vdots\\ \vdots\\ \langle\mathbf{T}_{F},\mathbf{I}_{F}(A_K)\rangle \end{pmatrix}, \qquad \mathbf{S}_{M}= \begin{pmatrix} \langle\mathbf{T}_{M},\mathbf{I}_{M}(A_1)\rangle\\ \langle\mathbf{T}_{M},\mathbf{I}_{M}(A_2)\rangle\\ \vdots\\ \langle\mathbf{T}_{M},\mathbf{I}_{M}(A_K)\rangle\\ \langle\mathbf{T}_{M},\mathbf{I}_{M}(A_1)\rangle\\ \vdots\\ \langle\mathbf{T}_{M},\mathbf{I}_{M}(A_K)\rangle\\ \vdots\\ \langle\mathbf{T}_{M},\mathbf{I}_{M}(A_1)\rangle\\ \vdots\\ \langle\mathbf{T}_{M},\mathbf{I}_{M}(A_K)\rangle \end{pmatrix}. \tag*{(26)}

Suppose that FF is a father in pedigrees P1\mathcal{P}_1 and P2\mathcal{P}_2. Let SF\mathbf{S}_{F} be calculated on P1\mathcal{P}_1. Then by conditional independence,

P(P1,P2)=∑FP(P1\F∣F)⋅P(P2\F∣F)⋅P(F).(27)P(\mathcal{P}_1,\mathcal{P}_2)=\sum_{F}P(\mathcal{P}_1\backslash F\mid F)\cdot P(\mathcal{P}_2\backslash F\mid F)\cdot P(F). \tag*{(27)}

This is exactly what the inner product does:

⟨⨀j=1NC(gCj),F(gF)⊙SF⊙M(gM)⟩=⟨⨀j=1NC(gCj)⊙M(gM),F(gF)⊙SF⟩=⟨⨀j=1NC(gCj)⊙M(gM),pF⊙SF⟩.(28)\begin{aligned} \left\langle \bigodot_{j=1}^{N} C(g_{C_j}),F(g_{F})\odot\mathbf{S}_{F}\odot M(g_{M}) \right\rangle = \left\langle \bigodot_{j=1}^{N} C(g_{C_j})\odot M(g_{M}),F(g_{F})\odot\mathbf{S}_{F} \right\rangle\\ &= \left\langle \bigodot_{j=1}^{N} C(g_{C_j})\odot M(g_{M}),p_{F}\odot\mathbf{S}_{F} \right\rangle. \tag*{(28)} \end{aligned}

The right side contains the entries P(F=Ai)⋅P(P1\F∣F=Ai)=P(F=Ai,P1\F)P(F=A_i)\cdot P(\mathcal{P}_1\backslash F\mid F=A_i)=P(F=A_i,\mathcal{P}_1\backslash F), whereas the inner product with the left side induces multiplication with P(P2\F∣F=Ai)P(\mathcal{P}_2\backslash F\mid F=A_i).

Parent to child

An untyped parent can also be a child in the pedigree it sends the message to. In that case, we need to “wrap” the message in a matrix since that is the way we represent children. The paternal resp. maternal upward message is defined as

UF:=(⟨TF,IF(A1)⟩⟨TF,IF(A2)⟩⋯⟨TF,IF(AK)⟩⋮⋮⋮⟨TF,IF(A1)⟩⟨TF,IF(A2)⟩⋯⟨TF,IF(AK)⟩),UM:=(⟨TM,IM(A1)⟩⟨TM,IM(A2)⟩⋯⟨TM,IM(AK)⟩⋮⋮⋮⟨TM,IM(A1)⟩⟨TM,IM(A2)⟩⋯⟨TM,IM(AK)⟩).(29)U_F := \begin{pmatrix} \langle T_F,I_F(A_1)\rangle& \langle T_F,I_F(A_2)\rangle& \cdots& \langle T_F,I_F(A_K)\rangle\\ \vdots& \vdots& & \vdots\\ \langle T_F,I_F(A_1)\rangle& \langle T_F,I_F(A_2)\rangle& \cdots& \langle T_F,I_F(A_K)\rangle \end{pmatrix}, \qquad U_M := \begin{pmatrix} \langle T_M,I_M(A_1)\rangle& \langle T_M,I_M(A_2)\rangle& \cdots& \langle T_M,I_M(A_K)\rangle\\ \vdots& \vdots& & \vdots\\ \langle T_M,I_M(A_1)\rangle& \langle T_M,I_M(A_2)\rangle& \cdots& \langle T_M,I_M(A_K)\rangle \end{pmatrix}. \tag*{(29)}

The idea is exactly the same as for sideways messages. The probability of the two pedigrees is again conditionally independent:

⟨TM,IM(Ai)⟩⋅P(C=Ai∣F,M)=P(P∖C∣C=Ai)⋅P(C=Ai∣F,M)=P(P∖C∣C=Ai,F,M)⋅P(C=Ai∣F,M)=P(C,P∖C∣F,M).(30)\begin{aligned} \langle T_M,I_M(A_i)\rangle\cdot P(C=A_i\mid F,M) &= P(\mathcal{P}\setminus C\mid C=A_i)\cdot P(C=A_i\mid F,M) \\ &= P(\mathcal{P}\setminus C\mid C=A_i,F,M)\cdot P(C=A_i\mid F,M) \\ &= P(C,\mathcal{P}\setminus C\mid F,M). \tag*{(30)} \end{aligned}

Child to parent

Every peel is sending at most one message. Without loss of generality, we assume that if a child sends the message, it is C1C_1 that is sending. We first write

TC:=⨀j=2NC(gCj)⊙M(gM)⊙F(gF).(31)T_C := \bigodot_{j=2}^{N} C(g_{C_j}) \odot M(g_M) \odot F(g_F). \tag*{(31)}

Now we define the paternal resp. maternal downward message as follows:

DF:=(⟨TC,C(A1)⟩⟨TC,C(A1)⟩⋮⟨TC,C(A1)⟩⟨TC,C(A2)⟩⋮⟨TC,C(A2)⟩⟨TC,C(A3)⟩⋮⋮⟨TC,C(AK)⟩),DM:=(⟨TC,C(A1)⟩⟨TC,C(A2)⟩⋮⟨TC,C(AK)⟩⟨TC,C(A1)⟩⋮⟨TC,C(AK)⟩⋮⟨TC,C(A1)⟩⋮⟨TC,C(AK)⟩).(32)D_F := \begin{pmatrix} \langle T_C,C(A_1)\rangle\\ \langle T_C,C(A_1)\rangle\\ \vdots\\ \langle T_C,C(A_1)\rangle\\ \langle T_C,C(A_2)\rangle\\ \vdots\\ \langle T_C,C(A_2)\rangle\\ \langle T_C,C(A_3)\rangle\\ \vdots\\ \vdots\\ \langle T_C,C(A_K)\rangle \end{pmatrix}, \qquad D_M := \begin{pmatrix} \langle T_C,C(A_1)\rangle\\ \langle T_C,C(A_2)\rangle\\ \vdots\\ \langle T_C,C(A_K)\rangle\\ \langle T_C,C(A_1)\rangle\\ \vdots\\ \langle T_C,C(A_K)\rangle\\ \vdots\\ \langle T_C,C(A_1)\rangle\\ \vdots\\ \langle T_C,C(A_K)\rangle \end{pmatrix}. \tag*{(32)}

Observe that

P(P∣C1=Ai)=⟨TC,PCIC(Ai)⟩=⟨TC,C(Ai)⟩.(33)P(P\mid C_1=A_i)=\langle T_C,P_C I_C(A_i)\rangle=\langle T_C,C(A_i)\rangle. \tag*{(33)}

This message is different in the sense that it is already multiplied with P(C=Ai)P(C = A_i), because this is conditional even within its peel. Thus, when this message is sent, the parent receiving this message should not also multiply this with p\mathbf{p}. (The good news is that a child can only be a child once.)

Receiving a message

When an individual receives a message, we assume it is always unknown. If it is an upward or sideways message, we simply take the Hadamard product SF⊙pFS_F \odot\mathbf{p}_F. For an upward message into a child role, it is UFU_F composed with CC. For a downward message, FF is replaced by DFD_F, as it does not need the Hadamard product with pF\mathbf{p}_F.

A peel can receive multiple messages, but sends only one. In the “final” peel, messages can only be received. Assuming all members receive, we can have for instance

⟨⨀j=1NC(gCj)⊙Uj, SF⊙pF⊙DM⟩(34)\left\langle\bigodot_{j=1}^{N} C(g_{C_j}) \odot U_j,\ S_F \odot\mathbf{p}_F \odot D_M \right\rangle \tag*{(34)}

for the final peel. Here, the mother received a message as a child, the father had other children, and the UjU_j denote the messages of the children they transmit as parents. If this is not the final peel, a subsequent TT can be constructed by selecting the appropriate factors.

Parents can receive multiple messages TFiT_F^i if they have children with several partners. In such cases, one takes the Hadamard product of these messages, and sends off a complete message TF=⨀iTFiT_F = \bigodot_i T_F^i.

As mentioned before, kids only have one pair of parents. However, if they need to send a downward message, while also having children with multiple partners, the complete message is TC⊙⨀iTFiT_C \odot\bigodot_i T_F^i. Since there is only one Hadamard factor TCT_C, it is no problem that this already contains p\mathbf{p}.

Example of a sideways message

A typical example is a half-sibling pedigree:

Pedigree with two missing mothers, an untyped father, and two typed children with genotypes A/A and A/a

Figure B.1. Pedigree with two missing mothers, an untyped father, and two typed children with genotypes A/AA/A and A/aA/a.

If we assume the message via FF goes from left to right, we have

TF=C(AA)⊙pM=(000014120121)⊙(141214141214141214)=(0000181801414).(35)T_F = C(AA) \odot p_M = \begin{pmatrix} 0\\ 0\\ 0\\ 0\\ \frac{1}{4}\\ \frac{1}{2}\\ 0\\ \frac{1}{2}\\ 1 \end{pmatrix} \odot \begin{pmatrix} \frac{1}{4}\\ \frac{1}{2}\\ \frac{1}{4}\\ \frac{1}{4}\\ \frac{1}{2}\\ \frac{1}{4}\\ \frac{1}{4}\\ \frac{1}{2}\\ \frac{1}{4} \end{pmatrix} = \begin{pmatrix} 0\\ 0\\ 0\\ 0\\ \frac{1}{8}\\ \frac{1}{8}\\ 0\\ \frac{1}{4}\\ \frac{1}{4} \end{pmatrix}. \tag*{(35)}

Now we calculate

⟨TF,IF(A1)⟩=0,⟨TF,IF(A2)⟩=14,⟨TF,IF(A3)⟩=12,(36)\langle T_F,I_F(A_1)\rangle= 0,\qquad \langle T_F,I_F(A_2)\rangle= \frac{1}{4},\qquad \langle T_F,I_F(A_3)\rangle= \frac{1}{2}, \tag*{(36)}

so that

SF=(000141414121212).(37)S_F = \begin{pmatrix} 0\\ 0\\ 0\\ \frac{1}{4}\\ \frac{1}{4}\\ \frac{1}{4}\\ \frac{1}{2}\\ \frac{1}{2}\\ \frac{1}{2} \end{pmatrix}. \tag*{(37)}

This is the message the father receives through the left. Now we calculate

LL=⟨⨀j=1NC(gCj)⊙U,SF⊙pF⊙DM⟩=⟨C(Aa),SF⊙pF⊙M⟩=⟨C(Aa),SF⊙pF⊙pM⟩=⟨(01211212121120),(00132116132132132116132)⟩=18.(38)\begin{aligned} LL &= \left\langle\bigodot_{j=1}^{N} C(g_{C_j}) \odot U, S_F \odot p_F \odot D_M \right\rangle\\ &= \left\langle C(Aa), S_F \odot p_F \odot M \right\rangle\\ &= \left\langle C(Aa), S_F \odot p_F \odot p_M \right\rangle\\ &= \left\langle \begin{pmatrix} 0\\ \frac{1}{2}\\ 1\\ \frac{1}{2}\\ \frac{1}{2}\\ \frac{1}{2}\\ 1\\ \frac{1}{2}\\ 0 \end{pmatrix}, \begin{pmatrix} 0\\ 0\\ \frac{1}{32}\\ \frac{1}{16}\\ \frac{1}{32}\\ \frac{1}{32}\\ \frac{1}{32}\\ \frac{1}{16}\\ \frac{1}{32} \end{pmatrix} \right\rangle= \frac{1}{8}. \tag*{(38)} \end{aligned}

References

  1. [1]E. Balas and M. W. Padberg. Set partitioning: A survey. SIAM Review, 18(4):710–760, 1976.DOI
  2. [2]D. J. Balding and C. D. Steele. Weight-of-Evidence for Forensic DNA Profiles. Statistics in Practice. John Wiley & Sons, 2015.
  3. [3]N. Bell and M. Garland. Efficient sparse matrix-vector multiplication on CUDA. NVIDIA Technical Report NVR-2008-004, NVIDIA Corporation, December 2008.
  4. [4]A. Boonstra, R. Meester, and K. Slooten. Reconciling common-source, specific-source, feature-based, and score-based likelihood ratios. Law, Probability and Risk, 24(1):mgaf008, 2025.
  5. [5]A. Boonstra and K. Slooten. An extended joint approach for disaster victim identifications. Submitted to Forensic Science International: Genetics, 2026.
  6. [6]C. H. Brenner. Some mathematical problems in the DNA identification of victims in the 2004 tsunami and similar mass fatalities. Forensic Science International, 157(2):172–180, 2006.pubmed.ncbi.nlm.nih.gov/16361074
  7. [7]C. Van Dongen, K. Slooten, M. Slagter, W. Burgers, and W. Wiegerinck. Bonaparte: Application of new software for missing person’s programme. Forensic Science International: Genetics Supplement Series, 3:119–120, 2011.
  8. [8]B. M. Dupuy, M. Stenersen, and D. Kling. Frequency data for 35 autosomal STR markers in a Norwegian, an East African, an East Asian and Middle Asian population and simulation of adequate database size. Forensic Science International: Genetics Supplement Series, 4(1):e378–e379, 2013.DOI
  9. [9]T. Egeland, P. Mostad, B. Mevåg, and M. Stenersen. Beyond traditional paternity and identification cases. Selecting the most probable pedigree. Forensic Science International, 110(1):47–59, 2000.pubmed.ncbi.nlm.nih.gov/10802200
  10. [10]T. Egeland, D. Kling, and P. Mostad. Relationship Inference with Familias and R: Statistical Methods in Forensic Genetics. Academic Press, 2016.
  11. [11]R. C. Elston and J. Stewart. A general model for the genetic analysis of pedigree data. Human Heredity, 21(6):523–542, 1971.pubmed.ncbi.nlm.nih.gov/5149961
  12. [12]A. L. Fortier, J. Kim, and N. A. Rosenberg. Human-genetic ancestry inference and false positives in forensic familial searching. G3: Genes, Genomes, Genetics, 10(8):2893–2902, 2020.DOI
  13. [13]R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85–103. Plenum Press, New York, 1972.
  14. [14]D. B. Kirk and W. W. Hwu. Programming Massively Parallel Processors: A Hands-on Approach. Morgan Kaufmann, Cambridge, MA, 4th edition, 2022.
  15. [15]D. Kling, T. Egeland, M. Herrera Piñero, and M. D. Vigeland. Evaluating the statistical power of DNA-based identification, exemplified by ‘The missing grandchild of Argentina’. Forensic Science International: Genetics, 31:57–66, 2017.DOI
  16. [17]K. Lange. Mathematical and Statistical Methods for Genetic Analysis. Statistics for Biology and Health. Springer-Verlag, New York, 2nd edition, 2002.
  17. [18]Ministry of Foreign Affairs, Nepal. Sixth press briefing on Bhote Koshi floods. Singhadurbar, Kathmandu. Accessed 3 September 2026.
  18. [19]T. Ohta and M. Kimura. A model of mutation appropriate to estimate the number of electrophoretically detectable alleles in a finite population. Genetical Research, 22(2):201–204, 1973.
  19. [20]Police cantonale valaisanne. Crans-Montana: toutes les personnes décédées ont été identifiées. Communiqué de presse, January 2026.
  20. [21]M. Prinz, A. Carracedo, W. R. Mayr, N. Morling, T. J. Parsons, A. Sajantila, R. Scheithauer, H. Schmitter, and P. M. Schneider. DNA Commission of the International Society for Forensic Genetics (ISFG): Recommendations regarding the role of forensic genetics for disaster victim identification (DVI). Forensic Science International: Genetics, 1(1):3–12, 2007.DOI
  21. [22]I. Simonsson and P. Mostad. Stationary mutation models. Forensic Science International: Genetics, 23:217–225, 2016.DOI
  22. [23]K. Slooten. Validation of DNA-based identification software by computation of pedigree likelihood ratios. Forensic Science International: Genetics, 2010.DOI
  23. [24]K. Slooten and R. Meester. Probabilistic strategies for familial DNA searching. Journal of the Royal Statistical Society: Series C (Applied Statistics), 63(3):361–384, 2014.
  24. [25]M. S. Song, P. Cadiz, Y. Lu, E. Swan, and F. J. Vasko. A simple hybrid approach for solving set covering problems with conflict constraints. Mathematics, 14(2), 2026.DOI
  25. [26]D. Sweet. INTERPOL DVI best-practice standards—an overview. Forensic Science International, 201(1):18–21, 2010.DOI
  26. [27]T. Tvedebrink, P. S. Eriksen, H. S. Mogensen, and N. Morling. Statistical model for degraded DNA samples and adjusted probabilities for allelic drop-out. Forensic Science International: Genetics, 6:97–101, 2012.
  27. [28]P. Vergeer. From specific-source features to common-source score-based likelihood ratio systems: ranking the stars. Law, Probability and Risk, 22:1–43, 2023.DOI
  28. [29]E. Vermeij, P. Zoon, R. Gerretsen, and V. Otieno-Alego. The outcome of the forensic triage preceding disaster victim identification in the downing of Malaysia Airlines Flight MH17. Forensic Sciences Research, 7(3):566–575, 2022.DOI
  29. [30]M. D. Vigeland. Pedigree Analysis in R. Academic Press, 2021.DOI
  30. [31]M. D. Vigeland and T. Egeland. Joint DNA-based disaster victim identification. Scientific Reports, 2021.DOI
  31. [32]H. P. Williams. Model Building in Mathematical Programming. John Wiley & Sons, Hoboken, NJ, 5th edition, 2013.

Paper details

vlnc:W_jmbphaj7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents