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 -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
of missing persons accompanied by open spots. This number is bounded by the post-mortem (PM) data, written as
which consists of the genetic profiles of victims together with 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 and call a problem fully open if both and .
In addition to the AM data, we have (disjoint) reference families . We denote for the missing persons of family . To accommodate for the open spots, we define , so that .
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 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

Figure 2.1. A small DVI problem with .
where indicates that PM sample is identified as missing person . In this notation, indicates that has not (yet) been identified, and similarly, in turn reflects that victim 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 and , the number of possible assignments can be extremely large [31]. Exhaustive evaluation of all possible 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 for the number of missing persons in family . We let be the tuples of cardinality of representing the space of all possible assignments for the missing persons, in a family . We furthermore assume an ordering on and write for its -th element.
Then, for any assignment , we denote the conditional likelihood with
for each . In this work, the likelihood [11, 17] is calculated assuming Mendelian segregation, unlinked markers, linkage equilibrium and mutation models. We further define the weights
as the corresponding natural log-likelihood of the victims placed in , and define as an indicator function that is 1 if the restriction is equal to .
For the global log-likelihood of the assignment , we can now write
where denotes the number of candidate assignments to . The objective is to identify the assignment that maximizes the likelihood among all feasible mappings, given the PM and AM data. With the above notation, we can reformulate this as
subject to
meaning that every family gets one single assignment for the missing persons and
meaning that every victim is only assigned once. In (2.9), indicates with slight abuse of notation that occurs as an entry in . Note that (2.8) and (2.9) effectively require to be an injection and thus a bijection from to .
The above reduces the problem to finding the values for each . That is, for each family , 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 and 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 through that have been recovered, each with a known DNA profile. The AM data involves two families and . Both contain typed reference relatives and a number of missing individuals whose identities are sought. Family has two missing persons and , with being a child of the typed reference . Family has two missing persons and , whose parents are the typed references and . The problem is fully open, as we have 4 open spots () and 4 dummy victims through .
For the sake of simplicity, we assume data on only one locus, with alleles , and . The frequencies are , , , and for simplicity, we do not include any mutation model. We start with . 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 variable | Likelihood formula | Numerical value | Weight | ||||
| * | * | * | 0.12 | ||||
| * | * | * | 0.2 | ||||
| * | * | * | 0.09 | ||||
| * | * | * | 0.3 | ||||
| 0.000648 | |||||||
| * | * | * | * | 1 | 1 | 0.00 |
Table 1. Some assignments for . 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 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 and separately. Starting with , we note that must inherit from , therefore or on will always result in a likelihood of 0. The weights of the non-zero likelihoods are presented in Table 2.
| Decision variable | Likelihood formula | Numerical value | Weight | ||
| 0.075 | −2.59 | ||||
| 0.045 | −3.10 | ||||
| 0.075 | −2.59 | ||||
| 0.3 | −1.20 | ||||
| 0.075 | −2.59 | ||||
| 0.075 | −2.59 | ||||
| 0.5 | −0.69 | ||||
| 0.21 | −1.56 | ||||
| 0.35 | −1.05 | ||||
| 0.045 | −3.10 | ||||
| 0.15 | −1.90 | ||||
| 1 | 1 | 0.00 |
Table 2. Non-zero configurations for of Figure 2.1. An indicates that a missing person is mapped to a dummy variable.
We repeat this for , again noting that assigning or will immediately result in likelihood 0. This yields
| Decision variable | Likelihood formula | Numerical value | Weight | ||
| 0.25 | −1.39 | ||||
| 0.5 | −0.69 | ||||
| 0.5 | −0.69 | ||||
| 1 | 1 | 0.00 |
Table 3. Non-zero configurations for 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 . In this case, an optimal is such that and . In the linear program, this amounts to the decisions .
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 on will globally yield if includes this identification, since carries no allele and must inherit from reference . This partial assignment can thus be discarded outright, without evaluating any combination of 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 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 .
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, is a direct child of typed reference , meaning Mendelian inheritance strongly constrains which victim genotypes are compatible. , by contrast, is connected to the pedigree only through . Scanning first therefore eliminates far more candidates before any combination with 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 are typed (: , : ), so can only be
or . 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 , with only one typed parent (: ), only victims carrying at least one allele qualify. For , whose only typed relative is grandparent separated by the unresolved slot , no genotype constraint can be propagated without first knowing who fills .
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 .
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 and . This gives possible profiles, namely , and . We further suppose that , so that , .

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 and are non-inbred and thus independent, so that . The mother passes on to , and has a 50% chance of inheriting from , so that . This yields .
In our algorithmic approach, we introduce variables for each individual. In this example, we write for the father. If the father is known to be for example, we set and . If the father is unknown, we set . For the mother we write with the same interpretation. This yields the following vector with the product of the genotype indicators and the probability of the corresponding genotypes:
Moving on to , we precalculate all the probabilities and store these in a matrix (not displayed here). We write the variables to store our knowledge about . Given the information in Figure 2.2, we immediately conclude that , cf. § 2.3.1. Thus in this example, we only need the following vector
where the coefficients are now equal to .
The main point is that the likelihood of the entire pedigree can be obtained from the following inner product:
In case of Figure 2.2 all variables are 0, apart from , and . This yields the correct answer of .
To demonstrate the flexibility of (2.12), suppose for instance that the father is unknown. Then
Indeed, when we take , we see that
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 .
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.

Figure 2.3. Two symmetric pedigrees.
The dependencies between , and 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- 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 independent families, each containing one typed grandfather and two missing grandsons, so victims and missing persons both number . See Figure 3.1.

Figure 3.1. Schematic DVI instance with independent reference families, each containing two missing grandsons. The additional group contains the open spots, while dummy victims allow missing persons to remain unidentified.
We carried this out up to of such reference families; since at , full enumeration becomes infeasible. The results are displayed in Table 4.
| Method | Likelihood evaluations | Saved evaluations |
| : 2 victims, 2 missing (7 assignments) | ||
| Exhaustive | 483 | 337 |
| Our method | 146 | 69.77% |
| : 4 victims, 4 missing (209 assignments) | ||
| Exhaustive | 28 842 | 28 395 |
| Our method | 447 | 98.45% |
| : 6 victims, 6 missing (13 327 assignments) | ||
| Exhaustive | 2 758 689 | 2 757 648 |
| Our method | 1 041 | 99.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 , 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.

Figure 3.2. The twelve pedigree designs, grouped by the number of missing persons .
| Design | Strongest relationship | No mutation mean | No mutation worst | Equal mean | Equal worst | Stepwise mean | Stepwise worst | |
| 1 | 1 | Parent-Child | 3.5 s | 6.1 s | 1.2 s | 3.5 s | 1.0 s | 2.8 s |
| 2 | 1 | Sibling | 4.6 s | 7.4 s | 2.3 s | 9.0 s | 2.9 s | 4.0 s |
| 3 | 1 | Grandparent-Grandchild | 4.0 s | 5.3 s | 1.3 s | 1.8 s | 4.5 s | 5.1 s |
| 4 | 2 | Parent-Child | 4.6 s | 6.3 s | 1.7 s | 2.5 s | 5.9 s | 7.6 s |
| 5 | 2 | Sibling/Parent-Child | 6.5 s | 7.9 s | 6.1 s | 8.2 s | 26.4 s | 32.0 s |
| 6 | 2 | Sibling | 5.2 s | 6.5 s | 5.1 s | 6.9 s | 51.5 s | 86.8 s |
| 7 | 3 | Parent-Child | 6.1 s | 7.9 s | 3.2 s | 4.2 s | 15.0 s | 17.0 s |
| 8 | 3 | (Grand)parent-(Grand)child | 12.5 s | 14.5 s | 18.1 s | 31.9 s | 112.6 s | 175.7 s |
| 9 | 3 | Sibling | 8.2 s | 10.4 s | 49.6 s | 60.1 s | 161.0 s | 217.6 s |
| 10 | 4 | Parent-Child | 8.3 s | 10.3 s | 6.0 s | 7.8 s | 32.1 s | 35.6 s |
| 11 | 4 | Parent-Child | 18.1 s | 32.1 s | 63.4 s | 79.1 s | 339.6 s | 481.2 s |
| 12 | 4 | Grandparent-Grandchild/Siblings | 44.5 s | 66.2 s | 292.2 s | 423.2 s | 999.5 s | 1512.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: , .
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 .
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.
| Design | full | No Lumping | No PC Filter | No Precompute | No P1 filter | No Obj Filter | No Symmetry | CPU | No parallelism | ||
| 1 | 1 | 240 | 14 (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×) |
| 2 | 1 | 240 | 16 (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×) |
| 3 | 1 | 240 | 27 (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×) |
| 4 | 2 | 240 | 66 (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×) |
| 5 | 2 | 240 | 105 (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×) |
| 6 | 2 | 240 | 72 (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×) |
| 7 | 3 | 240 | 75 (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×) |
| 8 | 3 | 240 | 127 (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×) |
| 9 | 3 | 240 | 208 (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×) |
| 10 | 4 | 240 | 466 (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×) |
| 11 | 4 | 240 | 361 (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×) |
| 12 | 4 | 240 | 5312 (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. denotes the number of victims per design and 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 , . 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 , a set of missing individuals with an associated pedigree and AM genetic data.
Question: Does there exist an assignment such that ?
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 , consider a certificate consisting of an assignment . Given , the likelihood 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 , the overall log-likelihood can be evaluated in time polynomial in the input size. Checking if is trivial. Hence a proposed assignment can be verified in polynomial time, and therefore .
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 with .
Question: Does there exist a permutation such that for all ?
Given a graph with , we construct in polynomial time a DVI instance as follows.
Pedigree structure
We construct a linear pedigree consisting of missing individuals , where for each , the individual is the child of and a typed reference spouse . The spouses are unrelated founders. This is a single reference family with and .
PM samples and missing persons
We create typed PM samples , establishing a one-to-one correspondence between vertices 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 with we introduce a locus with two alleles , with .
At locus :
Victim is assigned genotype .
Victim is assigned genotype .
All other victims and all reference spouses are assigned genotype .
We show that contains a Hamiltonian path if and only if the constructed DVI instance admits an assignment with strictly positive likelihood.
. Suppose contains a Hamiltonian path . Assign the corresponding PM samples to the missing individuals in this order, i.e. .
All members are typed once is fixed, so the likelihood at a locus is the product of the founder probabilities of , and the transmission probabilities . The founder probabilities are positive. For every adjacent pair , an edge exists in , so no locus corresponding to a non-edge forces opposite homozygotes on a parent–child pair. Consequently, the overall likelihood is strictly positive.
. Conversely, suppose there exists an assignment with . This implies that no Mendelian incompatibility occurs at any locus. Because has genotype and can transmit either allele, a trio is inconsistent exactly when parent and child are opposite homozygotes. At locus this happens if and only if and 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 , implying that the assignment defines a Hamiltonian path in .
The construction introduces at most loci and individuals. Every single locus specification requires constant time, yielding an overall construction time of . 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

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

Figure A.2. A valid assignment corresponds to the Hamiltonian path . An invalid assignment places immediately before , violating Mendelian inheritance at locus .
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 , slots , configurations , and weights .
Preliminaries
We assume alleles with subsequent allele frequencies . We write for the number of possible genotypes, which we denote by . The ordering does not matter, but we fix , , , and so on.
Let be a collection of genotypes. For a genotype , we define the indicator function to be 1 if . Write for the power set of . We construct the following maps , accompanied by the vectors :
We further write and , where denotes the element-wise Hadamard product. Assuming no inbreeding, the genotypes and of a father and a mother are independent. Now observe that the joint likelihood that and can be expressed as
In practice, or since individuals are usually typed or unknown. The same holds for .
The genotypes of the children of and are of course dependent on and . For them we need a different notation. We start by writing
The genotypes of children are independent conditionally on their parents’ genotypes. Therefore, let be any child of and . For each , we define
These vectors are stored in a matrix as follows:
As with and , we write .
Now, let denote the pedigree where is a child of and . Again assuming no inbreeding, and writing for the genotype of , we have
with the slightly abusive notation .
If contains multiple children with respective genotypes , the resulting expression is surprisingly simple due to conditional independence:
The Hadamard product is associative with respect to the inner product, so that we also have
which will be useful later on for transmitting messages. In the nuclear family example of § 2.4, and 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 be the pedigree a parent is sending from. Then we write
Fix some profile . We write for the likelihood of the given profiles in the pedigree, but without individual . Now observe that
This motivates the following definition for the paternal resp. maternal sideways message:
Suppose that is a father in pedigrees and . Let be calculated on . Then by conditional independence,
This is exactly what the inner product does:
The right side contains the entries , whereas the inner product with the left side induces multiplication with .
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
The idea is exactly the same as for sideways messages. The probability of the two pedigrees is again conditionally independent:
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 that is sending. We first write
Now we define the paternal resp. maternal downward message as follows:
Observe that
This message is different in the sense that it is already multiplied with , 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 . (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 . For an upward message into a child role, it is composed with . For a downward message, is replaced by , as it does not need the Hadamard product with .
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
for the final peel. Here, the mother received a message as a child, the father had other children, and the denote the messages of the children they transmit as parents. If this is not the final peel, a subsequent can be constructed by selecting the appropriate factors.
Parents can receive multiple messages if they have children with several partners. In such cases, one takes the Hadamard product of these messages, and sends off a complete message .
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 . Since there is only one Hadamard factor , it is no problem that this already contains .
Example of a sideways message
A typical example is a half-sibling pedigree:

Figure B.1. Pedigree with two missing mothers, an untyped father, and two typed children with genotypes and .
If we assume the message via goes from left to right, we have
Now we calculate
so that
This is the message the father receives through the left. Now we calculate
References
- [1]E. Balas and M. W. Padberg. Set partitioning: A survey. SIAM Review, 18(4):710–760, 1976.DOI
- [2]D. J. Balding and C. D. Steele. Weight-of-Evidence for Forensic DNA Profiles. Statistics in Practice. John Wiley & Sons, 2015.
- [3]N. Bell and M. Garland. Efficient sparse matrix-vector multiplication on CUDA. NVIDIA Technical Report NVR-2008-004, NVIDIA Corporation, December 2008.
- [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]A. Boonstra and K. Slooten. An extended joint approach for disaster victim identifications. Submitted to Forensic Science International: Genetics, 2026.
- [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]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]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]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]T. Egeland, D. Kling, and P. Mostad. Relationship Inference with Familias and R: Statistical Methods in Forensic Genetics. Academic Press, 2016.
- [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]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]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]D. B. Kirk and W. W. Hwu. Programming Massively Parallel Processors: A Hands-on Approach. Morgan Kaufmann, Cambridge, MA, 4th edition, 2022.
- [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
- [17]K. Lange. Mathematical and Statistical Methods for Genetic Analysis. Statistics for Biology and Health. Springer-Verlag, New York, 2nd edition, 2002.
- [18]Ministry of Foreign Affairs, Nepal. Sixth press briefing on Bhote Koshi floods. Singhadurbar, Kathmandu. Accessed 3 September 2026.
- [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.
- [20]Police cantonale valaisanne. Crans-Montana: toutes les personnes décédées ont été identifiées. Communiqué de presse, January 2026.
- [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
- [22]I. Simonsson and P. Mostad. Stationary mutation models. Forensic Science International: Genetics, 23:217–225, 2016.DOI
- [23]K. Slooten. Validation of DNA-based identification software by computation of pedigree likelihood ratios. Forensic Science International: Genetics, 2010.DOI
- [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.
- [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
- [26]D. Sweet. INTERPOL DVI best-practice standards—an overview. Forensic Science International, 201(1):18–21, 2010.DOI
- [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.
- [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
- [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
- [30]M. D. Vigeland. Pedigree Analysis in R. Academic Press, 2021.DOI
- [31]M. D. Vigeland and T. Egeland. Joint DNA-based disaster victim identification. Scientific Reports, 2021.DOI
- [32]H. P. Williams. Model Building in Mathematical Programming. John Wiley & Sons, Hoboken, NJ, 5th edition, 2013.