# GRUPS-rs, a high-performance ancient DNA genetic relatedness estimation software relying on pedigree simulations

Maël Lefeuvre, Michael D. Martin, Flora Jay, Marie-Claude Marsolier, Alexis Corrochano, Anaïs Lebrun, Céline Bon

<figure><img src="image_1.png" /></figure>

## ► To cite this version:

Maël Lefeuvre, Michael D. Martin, Flora Jay, Marie-Claude Marsolier, Alexis Corrochano, et al. GRUPS-rs, a high-performance ancient DNA genetic relatedness estimation software relying on pedigree simulations. JOBIM 2023 - Journées Ouvertes en Biologie, Informatique et Mathématiques, Jun 2023, Multisite, France. hal-05242467

HAL Id: hal-05242467

https://hal.science/hal-05242467v1

Submitted on 5 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# GRUPS-rs: a high-performance ancient DNA genetic relatedness estimation software based on pedigree simulations.

Maël Lefeuvre¹, Michaël D. Martin², Flora Jay³, Alexis Corrochano⁴, ⁵, Anaïs Lebrun¹,⁵, Céline Bon¹,† & Marie-Claude Marsolier Kergoat¹,⁶,†

1. UMR 7206 - Éco-Anthropologie (EA), Muséum National d'Histoire Naturelle, CNRS, Université Paris-Cité.
2. Department of Natural History, NTNU University Museum, Norwegian University of Science and Technology (NTNU).
3. UMR9015-- Laboratoire Interdisciplinaire des Sciences du Numérique (LISN), CNRS, INRIA, Université Paris-Saclay
4. UMR5608 - Travaux et Recherches en Archéologie sur les Cultures, les Espaces et les Sociétés (TRACES), CNRS, Université Toulouse II
5. Éveha - Bureau d'Études et Valorisations Archéologiques.
6. UMR9198 - Institut de Biologie Intégrative de la Cellule (I2BC), CNRS, CEA.

e-mail : mael.lefeuvre@mnhn.fr

<figure><img src="image_3.png" /></figure>

Éco-anthropologie (EA)
UMR7206

<figure><img src="image_4.png" /></figure>

cnrs

<figure><img src="image_5.png" /></figure>

MUSÈE
DE L'HOMME

<figure><img src="image_6.png" /></figure>

Éveha
Études et valorisations archéologiques

<figure><img src="image_7.png" /></figure>

Région
Ile-de-France

## Introduction:
The study of fine-grain genetic kinship ties (parents, siblings, cousins, etc.) is of great interest within the field of paleogenetics as a means of deciphering the social organization of past societies. However, kinship analyses are in practice often quite difficult to apply in paleogenetic studies – especially when studying poorly characterized populations and/or archaeological sites – given the significant degradation of the genetic material typically yielded from ancient remains. As of now, several ancient DNA genetic relatedness estimation tools attempt to overcome these challenges by applying their method on a cohort of individuals to obtain a satisfactory statistical significance¹,²,³. Although generally quite robust, these methods consequently share an intrinsic limitation when the number of studied individuals is limited. Here, we present an update and complete reimplementation of "GRUPS", a genetic relatedness estimation software dedicated to ancient DNA, based on the methods originally developed in Martin D., et al. (2017)⁴.

## Methods: GRUPS-rs leverages high-fidelity pedigree simulations to estimate kinship on a pair of individuals.

**Step I:** GRUPS-rs directly estimates the *observed* average mismatch rate (PWD) between two individuals by randomly sampling alleles.

<figure><img src="image_8.png" /></figure>

**Step II:** Using the exact same genomic positions covered in (I), GRUPS-rs then performs pedigree simulations in thousands of replicates, using samples from the 1000G project as founder individuals.

<figure><img src="image_9.png" /></figure>

**Step III:** From these simulations, GRUPS-rs computes the *expected* average mismatch rate between two individuals, according to a set of user-defined hypotheses.

(e.g.: Parent-offspring, Half-siblings, Cousins, etc.)

**Step IV:** Finally, GRUPS-rs estimates a most likely relationship, given the theoretical distributions of each relationship, by fitting a series of ordinally partitioned linear SVM classifiers.

<figure><img src="image_10.png" /></figure>

## Benchmark: GRUPS-rs can perform pedigree simulations on a cohort of individuals in a matter of minutes.

<figure><img src="image_11.png" /></figure>

We tested the runtime performance of GRUPS-rs against an increasing number of comparisons and sequencing coverage on the Allen Ancient DNA Resource (AADR) "1240K" target SNP dataset. We found that GRUPS-rs took an average of **3.32 minutes** to estimate kinship on a single pair of fully covered individuals. This runtime scaled linearly with the number of comparisons, reaching an average of ~3:10 hours, when applied on 11 individuals.

Thus, GRUPS-rs offers a substantial runtime performance overhaul compared to its previous version, most notably through the use of *Finite State Acceptors* (FSA) to index the 1000G dataset used during the simulations. Here the use of an FSA data-structure allows GRUPS-rs to retrieve the alleles of founder individuals with a time complexity of O(k), where k is the length of the output query string.

<figure><img src="image_12.png" /><figcaption>**Figure 1:** Surface plot representing the average runtime of GRUPS-rs against SNP coverage and the number of pairwise comparisons. Benchmark replicates (n=10) were performed on a constant simulated input dataset with a sequencing depth of ~1X. SNP coverage was achieved through successive downsampling of this dataset. **Constants:** 500 pedigree simulations replicates – 1 CPU thread (Intel Xeon Gold 5218R @ 2.10GHz)</figcaption></figure>

## Results: GRUPS-rs can compute robust estimates of kinship beyond the second degree.

To assess its ability to detect fine-grain levels of kinship, we tested GRUPS-rs on the Hazelton North panel of individuals, initially described in Fowler 2022¹. These ancient samples are known to form an intricate family tree, spanning five generations (Fig. 2A). Using GRUPS-rs, we investigated kinship ties up to the fifth degree on this dataset (Fig. 2B). These results were then compared to the method originally applied in the original publication³ (Fig. 2C). GRUPS-rs provided estimates that are highly concordant with the results showcased in the initial publication, with only 14 discordant results out of a total of 595 comparisons (Fig.2B). These results should, moreover, be considered in light of the fact that GRUPS assesses genetic relatedness *without* the need for a cohort of individuals.

<caption>**Figure 2:** Comparing the kinship matrices obtained from the Hazelton North long cairn individuals, using either (B) GRUPS-rs, or (C) the "Kennett" method used in (Fowler C. et al. 2022)¹,³. Colored numbers within cells indicate the true degree of relatedness when a misclassification occured ; white, indicating both methods misclassified the given pair, and red, highlighting method-specific misclassifications. (A) Retranscribed pedigree of the 35 individuals found within the Hazelton long cairn¹</caption>

<caption>**Figure 2:** Comparing the kinship matrices obtained from the Hazelton North long cairn individuals, using either (B) GRUPS-rs, or (C) the "Kennett" method used in (Fowler C. et al. 2022)¹,³. Colored numbers within cells indicate the true degree of relatedness when a misclassification occured ; white, indicating both methods misclassified the given pair, and red, highlighting method-specific misclassifications. (A) Retranscribed pedigree of the 35 individuals found within the Hazelton long cairn¹</caption>

## Discussion: GRUPS-rs is able to compute kinship on a single pair of low-coverage samples

<figure><img src="image_13.png" /></figure>

<figure><img src="image_14.png" /></figure>

Finally, we tested GRUPS-rs on two newly published individuals – MT23 and MT26 – from the archeological site of Mentesh Tepe, Azerbaijan: an early representant of the Shomu-Shulaveri culture, dated from 5700-5600 cal. B.C.⁵

Here, the low coverage of MT23 and MT26 (0.1X – 0,2X), coupled with the lack of a well-defined characterization of the genetic landscape found in the South-Caucasus during this period are challenges which were skillfully addressed by our method. Thus we could determine with confidence that MT23–MT26 are related to the first order, and were in fact siblings.

<caption>**Figure 3:** Applying GRUPS-rs on a set of newly sequenced individuals from the Mentesh Tepe archaeological site. (A) Photography of juveniles MT23 and MT26 within structure 342 of Mentesh Tepe. © Laure Pecqueur.</caption>

(B) : Genetic relatedness estimation of MT23-MT26, using GRUPS-rs.

## References:

1. Fowler, C., Olalde, I., Cummings, V. et al. (2022) A high-resolution picture of kinship practices in an Early Neolithic tomb. Nature 601, 584–587. https://doi.org/10.1038/s41586-021-04241-4
2. Monroy Kuhn JM, Jakobsson M, Günther T (2018) Estimating genetic kin relationships in prehistoric populations. PLoS ONE 13(4): e0195491. https://doi.org/10.1371/journal.pone.0195491
3. Kennett, D., Plog, S., George, R. et al. Archaeogenomic evidence reveals prehistoric matrilineal dynasty. Nat Commun 8, 14115 (2017). https://doi.org/10.1038/ncomms14115
4. Martin, MD, Jay, F, Castellano, S, Slatkin, M. (2017) Determination of genetic relatedness from low- coverage human genome sequences using pedigree simulations. Mol Ecol. 2017; 26: 4145–4157. https://doi.org/10.1111/mec.14188
5. Guarino-Vignon, P., Lefeuvre, M., Chimènes, A. et al. Genome-wide analysis of a collective grave from Mentesh Tepe provides insight into the population structure of early neolithic population in the South Caucasus. Commun Biol 6, 319 (2023). https://doi.org/10.1038/s42003-023-04681-w