Pierre Fernandez

Guillaume Couairon

Teddy Furon

Matthijs Douze

Meta Fair

FUNCTIONAL INVARIANTS TO WATERMARK LARGE TRANSFORMERS

Keywords: DNN watermarking, white-box, transformers

The rapid growth of transformer-based models increases the concerns about their integrity and ownership insurance. Watermarking addresses this issue by embedding a unique identifier into the model, while preserving its performance. However, most existing approaches require to optimize the weights to imprint the watermark signal, which is not suitable at scale due to the computational cost. This paper explores watermarks with virtually no computational cost, applicable to a non-blind white-box setting (assuming access to both the original and watermarked networks). They generate functionally equivalent copies by leveraging the models' invariance, via operations like dimension permutations or scaling/unscaling. This enables to watermark models without any change in their outputs and remains stealthy. Experiments demonstrate the effectiveness of the approach and its robustness against various model transformations (fine-tuning, quantization, pruning), making it a practical solution to protect the integrity of large models.

INTRODUCTION

Large-scale transformer models are a leap forward in the field of machine learning, with large language models like GPT-4 [START_REF] Openai | Gpt-4 technical report[END_REF], LLaMA [START_REF] Touvron | Llama: Open and efficient foundation language models[END_REF] and others [START_REF] Ai | Mistral 7b[END_REF][START_REF] Anthropicai | Introducing claude[END_REF][START_REF] Pichai | An important next step on our AI journey[END_REF], or vision ones like ViT-22b [START_REF] Dehghani | Scaling vision transformers to 22 billion parameters[END_REF] or DI-NOv2 [START_REF] Oquab | Dinov2: Learning robust visual features without supervision[END_REF]. As these models grow in complexity and size, protecting them is important due to investments in their development. Notably, this is raised by the US "Ensuring Safe, Secure, and Trustworthy AI" announcement, European AI Act and Chinese AI governance rules.

Watermarking deep neural networks [START_REF] Uchida | Embedding watermarks into deep neural networks[END_REF][START_REF] Adi | Turning your weakness into a strength: Watermarking deep neural networks by backdooring[END_REF] presents a step towards ensuring their security, integrity and ownership. Embedding a unique identifier into the model enables tracing it to safeguard it from unauthorized usage and distribution. However, watermarking large transformer models poses new challenges. Current watermarking methods involve optimizing the weights to infuse the watermark, either during pre-training or by fine-tuning the weights with additional losses. While these techniques have shown success for smaller models, they become computationally infeasible for large-scale models and for the burgeoning number of potential users and applications.

To address these challenges, we introduce a new approach to watermarking large transformers, when access to both the original and watermarked model is granted, i.e. in a non-blind white-box setting. Our method capitalizes on the inherent invariance of transformers. For a given model, it generates equivalent copies that serve as carriers for arbitrary signatures. By employing operations such as dimension permutation and coupled matrix multiplications, we create model replicas without changing the model's outputs and without training. We conduct experiments on state-of-the-art transformer architectures ‹ Correpondance to pfz@meta.com : Work supported by ANR / AID under Chaire SAIDA ANR-20-CHIA-0011. to evaluate the applicability of our approach and its robustness against model processing (e.g. fine-tuning, pruning, quantization, etc.). We also discuss the main drawbacks of this setting.

Invariant copies

The paper is organized as follows: section 2 provides an overview of related works on DNN watermarking and background on transformers; section 3 details the transformer's invariants and how to exploit them for watermarking; section 4 presents experimental results on large language models. Problem statement. A provider Alice, distributes her model to various users Bob (either individuals or organizations). She aims to trace the model back to a specific user, in case of unauthorized distribution or leaks. As a precautionary measure, Alice embeds a unique signature in the model's weights for each user. In a whitebox setting, Alice has access to the models' weights and extracts the signature from it to identify Bob. Besides, Bob may evade detection intentionally (trying to remove the watermark) or unintentionally (fine-tuning, quantization, etc.). This setting is quite common. Indeed few entities ("Alices") have the necessary computation resources, data and expertise to generate the base model. For example, the training of the 65-B LLaMA model took around 1B GPU-hours. Therefore, there are few variants of such large models in the world. Besides, when Bob gains access to the base model, it is common that he transforms it and that it re-emerges in a public forum or through another channel, so that Alice can analyze it. This can be either because Bob re-distributed it or because Alice sought the model through legal channels, as suggested by Fan et al. [START_REF] Fan | Deepip: Deep neural network intellectual property protection with passports[END_REF]. For example, many variants of the LLaMA models have been fine-tuned on instruction datasets and been made available online.

RELATED WORK & TECHNICAL BACKGROUND

Deep Neural Network (DNN) Watermarking

DNN watermarking robustly embeds a unique identifier into the model without affecting its performance, in order to later verify the model's identity. Watermarking should satisfy three criteria, utility: the new model should have the same performance as the original one; security: it should be stealthy, hard to remove and to forge; robustness: the watermark should be detected even after the model has been modified. Modifications may be unintentional -models are fine-tuned, pruned and quantized -or intentional -adversaries may try to remove the watermark or embed their own [START_REF] Fan | Rethinking deep neural network ownership verification: Embedding passports to defeat ambiguity attacks[END_REF][START_REF] Zhang | Passport-aware normalization for deep model protection[END_REF][START_REF] Kallas | Rose: A robust and secure dnn watermarking[END_REF]. For instance, some adversarial transforms employ invariance operations in neurons and ReLU layers to evade detection [START_REF] Yan | Rethinking white-box watermarks on deep learning models under neural structural obfuscation[END_REF], in a similar fashion as the techniques of this work.

We distinguish between white-box and black-box settings, depending on whether the model weights are accessible at verification time, or only through a remote API. In white-box, the pioneering work [START_REF] Uchida | Embedding watermarks into deep neural networks[END_REF] embeds watermarks into the DNN's weights. A regularization loss term during training constrains the weights to carry a specific signal, while minimizing the impact on the model's performance. The watermark is then retrieved directly by analyzing the model's weights. The Deep•Signs•Marks [START_REF] Darvish Rouhani | Deepsigns: An end-to-end watermarking framework for ownership protection of deep neural networks[END_REF][START_REF] Chen | Deepmarks: A secure fingerprinting framework for digital rights management of deep learning models[END_REF] extends this to target black-box settings and propose building collusion-resistant watermarks, RIGA [START_REF] Wang | Riga: Covert and robust whitebox watermarking of deep neural networks[END_REF] improves its covertness and robustness, and greedy residuals [START_REF] Liu | Watermarking deep neural networks with greedy residuals[END_REF] improves the selection of the weights to modify.

Another line of work, called trigger-set based methods, embeds the watermark in the behavior of the model with regards to certain inputs. A recurrent idea is to use "backdoors", i.e. memorize certain sequences of input-output pairs [START_REF] Adi | Turning your weakness into a strength: Watermarking deep neural networks by backdooring[END_REF][START_REF] Zhang | Protecting intellectual property of deep neural networks with watermarking[END_REF]. Watermarking generative models is also an active field of research, either by employing triggers [START_REF] Lim | Protect, show, attend and tell: Empowering image captioning models with ownership protection[END_REF][START_REF] Ong | Protecting intellectual property of generative adversarial networks from ambiguity attacks[END_REF], or by watermarking their outputs [START_REF] Fernandez | The stable signature: Rooting watermarks in latent diffusion models[END_REF][START_REF] Kim | Wouaf: Weight modulation for user attribution and fingerprinting in textto-image diffusion models[END_REF].

All previous methods require training or optimization. This is expensive computationally and requires extensive expertise in the case of large-scale transformers. The feasibility of existing watermarking methods to these models therefore remains an open question.

Transformers

Transformer [START_REF] Vaswani | Attention is all you need[END_REF] neural networks have become the standard for many applications in the last few years. They can be trained efficiently on GPUs and scale well to large datasets and models, in both natural language processing [START_REF] Raffel | Exploring the limits of transfer learning with a unified text-to-text transformer[END_REF][START_REF] Kaplan | Scaling laws for neural language models[END_REF] and computer vision [START_REF] Dehghani | Scaling vision transformers to 22 billion parameters[END_REF][START_REF] Oquab | Dinov2: Learning robust visual features without supervision[END_REF]. In the following we describe the NLP architecture from [START_REF] Radford | Language models are unsupervised multitask learners[END_REF].

The input string is first tokenized into a sequence of integers px1, . . . , xnq P V n . An embedding layer E P R |V|ˆd maps each token xi to a continuous vector z 0 i " Ex i P R d , where d is the embedding dimension. The transformer is a stack of attention and feed-forward layers, that we describe in the following.

Attention layers. The self-attention mechanism enables long-range dependencies between sequence elements. A self-attention transforms an input sequence z P R nˆd into queries Q, keys K, and values V :

Q " zW Q P R nˆd k ; K " zW K P R nˆd k ; V " zW V P R nˆdv . (1)
It then computes attention weights by taking a scaled dot product between the queries and keys:

AttentionpQ, K, V q " softmax ˆQK J ? d k ˙V. (2)
Where the Softmax operator is applied column-wise.

This attention operator is applied h times in parallel, yielding h output heads. The results are concatenated and projected back to the original dimension:

MultiHeadpQ, K, V q " Concatphead1, ., head h qW O , (3) where headi " AttentionpQW Q i , KW K i , V W V i q. The projections W Q i , W K i P R dˆd k , W V i P R dˆdv and W O P R hdvˆd are learned parameters.
The feed-forward network. The output is fed to a feed-forward network (FFN), e.g. two linear layers with a ReLU activation:

FFNphq " ReLUphW1 `b1qW2 `b2, (4)
where W1 P R dˆd ff , b1 P R d ff , W2 P R d ff ˆd and b2 P R d are learned parameters (SwiGLU [START_REF] Shazeer | Glu variants improve transformer[END_REF] and other variants also frequently replace ReLU).

A stack of residual connections. Instead of directly feeding z and h to the attention and FFN layers, residual connections are applied and the inputs are normalized using layer normalization [START_REF] Ba | Layer normalization[END_REF] (or variants like RMSnorm [START_REF] Zhang | Root mean square layer normalization[END_REF]):

LayerNormpzq " z ´µ σ d g `b, (5)
where µ and σ are the mean and standard deviation of z along its second dimension, and g P R d and b P R d are learned parameters. This is repeated for each layer l P t1, ..., Lu of the transformer:

h l " Att l ´Ln l att `zl ˘¯`z l (6)
z l`1 " Ffn l ´Ln l ffn `hl ˘¯`h l . ( 7
)
The output is fed to a normalization layer Lnout and a linear layer Wout P R dˆ|V| to generate logits, and a softmax outputs the probability distribution of the next token.

Positional embeddings. For many tasks, it is useful to encode the position of tokens in the input sequence. Positional embeddings are what allows to encode this information. They were originally sinusoidal functions of the position [START_REF] Vaswani | Attention is all you need[END_REF] added to the input embeddings.

There are now several variants [START_REF] Raffel | Exploring the limits of transfer learning with a unified text-to-text transformer[END_REF][START_REF] Su | Roformer: Enhanced transformer with rotary position embedding[END_REF][START_REF] Press | Train short, test long: Attention with linear biases enables input length extrapolation[END_REF][START_REF] Kazemnejad | The impact of positional encoding on length generalization in transformers[END_REF], that may change Eq. ( 2). For instance, rotary embeddings [START_REF] Su | Roformer: Enhanced transformer with rotary position embedding[END_REF] multiply queries and keys depending on their relative position in the sequence. If m is the position of the query (Qm " zmW Q ) and n the position of the key, then it rewrites the product of Eq. ( 2) as:

QmK J n " zmW Q RΘ,n´mpznW K q J . ( 8
)
RΘ,n is a block diagonal matrix with 2 ˆ2 rotation matrix entries:

pRΘ,nq i " ˆcos nθi ´sin nθi sin nθi cos nθi ˙,
with rotation frequencies chosen as θi " 10, 000 ´2i{d .

WATERMARKING THROUGH INVARIANCE

Invariants in the weights of transformers

We define an invariant as a series of operation applied on the model's weights θ Ñ θ 1 such that for any input x, the output f θ 1 pxq is the same as before the application of the invariant.

Permutation invariance appears in (at least) four levels of the transformer. We note Π d the set of permutations of t1, ..., du. For a matrix M P R dˆd and π P Π d , we denote by M:,π (resp. Mπ,:) the matrix where columns (resp. rows) are permuted according to π.

Embedding dimension. The embedding matrix E can be permuted along its second dimension without changing the output of the model, as long as the permutation is propagated to other matrices in the model. More formally, for π P Π d , if E 1 " E:,π, then matrices tW Q , W K , W V , W1, Wout, Ln att , Ln ffn , b2u Ă θ need to be permuted along their first dimension by π and all matrices tW O , W2u along their second one: pW Q q 1 " W Q π,: , pW O q 1 " W O :,π , etc. FFN layer dimension. All neurons making up matrices W1 and W2 of feed-forward networks can be permuted: for π P Π d ff , if W 1 1 " pW1q:,π and W 1 2 " pW2qπ,:, then f θ 1 p¨q " f θ p¨q. Attention heads. Because of Eq. 3, heads are interchangeable, provided that W O is permuted in blocks of dv rows, according to its first dimension. In practice, the pW Q i q iPt1,..,hu are stored as a unique matrix, so permuting the heads is equivalent to permuting the columns of this matrix in blocks of d k (same for W K i and W V i ). Inside the head. Depending on the type of positional embeddings, the previous permutations can be extended. For instance if they do not impact Eq. 2 (this is not the case for rotary embeddings) then W Q and W K can be permuted along their second dimension.

Scaling/Unscaling. Whenever layer norms or variants are directly followed (or preceded) by linear layers, e.g. at every attention or FFN block, we can rescale component-wise the parameters g, b of Eq. 5 by a vector α P R d . Invariance is obtained by dividing the rows of the following (or preceding) linear layers by the same vector.

Invertible matrices in QK products. We hereby assume the positional embeddings do not impact Eq. 2. If P P R d k ˆdk is invertible, then choosing pW Q q 1 " W Q P and pW K q 1 " W K pP J q ´1 is invariant in Eq. 2. This also applies to the case of rotary embeddings by restricting P to be block diagonal of 2 ˆ2 matrices that apply a 2D rotations and scaling by a factor λ (thanks to the commutativity of 2D rotations).

Combining invariants. All previous parameter transformations may be seen as invertible right or left matrix multiplications applied to the model parameters. For instance, π is associated to a permutation matrix P such that P i,πpiq " 1 and Pi,j " 0 otherwise, scalings are diagonal matrix, etc. They do not interfere and may be combined in a sequence of arbitrary order, yielding θ Ñ θ 1 Ñ θ 2 Ñ ¨¨¨.

Combining transformations at all levels improves robustness to intentional removal attacks and to collusion (i.e. when several Bobs share their weights to evade detection). Indeed, if Bob tries to remove the watermark by re-applying one invariant, it will still be present in the other invariants. In the same way, if several Bobs compare their models, it will be hard for them to identify which operations were applied to their models, since the order in which they were applied is unknown, and since the weights will differ a lot between them.

From invariants to watermarks

Insertion. Before starting the watermark process, for each invariant and each level of the network, we restrict the set of transformations to 2 k . For example, we randomly sample 2 k possible permutations in Π d for the Embedding dimension (out of the total d!). This is to simplify the detection procedure.

Therefore, we can encode k bits for each combination of an invariant and a level. Thus, we encode a model's identifier as the concatenation of m chunks of k bits (2 mk possibilities). For instance, let k " 4 and the model have 32 layers. We choose to embed two permutations per layer, one for the attention block and one for the FFN block. The total number of bits is 2ˆ32ˆ4 " 256, representing 10 77 possible models (approximately the number of atoms in the universe, an upper bound of the number of Bobs). This embedding process provides robustness and efficiency when extracting the watermarks.

Extraction. The brute-force way to extract the k-bits message from a weight matrix is to re-apply all 2 k possible invariants to the original matrix. We then compute the Frobenius norm of the difference between the observed weight and the possible watermarked ones. We choose the one with lowest among the 2 k and this choice is encoded as a k-bit integer. Doing that on every blocks of the network and every invariant, we end up with a full message made of m chunks of k bits. In the case of intertwined invariants, we do the same in the order in which we inserted the invariants, reverting them as we go.

To speed up extraction, we may select a subset of the matrices' rows before extraction. This speeds up the extraction (in the order of 100ˆ), but makes the detection slightly less robust. For instance, in the case of scaling/unscaling we may select the first 100 components of α from R d to R 100 and W from R dˆd 1 to R 100ˆ100 .

Matching. To match an extracted message (made of m chunks of k bits) with a model's identifier, we compute the number s of chunkwise errors with respect to all possible identifiers. We return a match if s is bellow a fixed threshold τ to ensure resilience to corruption and to provide a confidence score. A theoretical p-value, i.e. the probability of obtaining a number of errors lower than s for a random model, is given by the regularized incomplete beta function I:

p-valuepsq " 1 ´`1 ´I1{2 k pm ´s, s `1q ˘N , (9)
where N is the number of distributed models. N accounts for the fact that when multiple models are distributed, the risk of finding a match by chance is higher.

Robustness and security. Watermarking models through invariance is stealthy, because it does not change their outputs and does not leave artifacts in the weights. However, a distortion-free watermark is also a weakness. On the one hand, Alice can hide the watermark without impacting the model's utility, on the other hand, an adversarial Bob may do the same at no cost. In short, most of these watermarks are very robust against classical model manipulations (fine-tuning, quantization, etc.) but not against a malicious user who knows the method. In this case we would only know that the model is an unauthorized copy, without knowing the leaker.

EXPERIMENTS

The purpose of the experiments is to evaluate the effectiveness and the robustness of the watermarks to transformations on transformers, in the context of large language models.

Setup

Model. We use LLaMA [START_REF] Touvron | Llama: Open and efficient foundation language models[END_REF] models as main benchmark. The architectural differences with regards to the original transformer architecture are pre-normalization [START_REF] Radford | Language models are unsupervised multitask learners[END_REF] with RMSnorm [START_REF] Zhang | Root mean square layer normalization[END_REF], SwiGLU activation [START_REF] Shazeer | Glu variants improve transformer[END_REF] and rotary embeddings [START_REF] Su | Roformer: Enhanced transformer with rotary position embedding[END_REF]. Unless stated otherwise, we use the 7B-parameter model. To evaluate that the utility of the model is not degraded, we show results on a next-token prediction task. This is done on random sequences of text taken from Wikipedia, then tokenized using the default tokenizer of LLaMA.

Table 1: Distortion induced on generation (measured as the proportion of generated tokens that differ between the original and the watermarked model); and robustness of watermark extraction under various processes. Each line stands for a different invariant, "all" is the combination of the three invariants in the following order: perm, QK and scaling. We present results of the sped-up extraction, the ones for no speed-up are given as (acc).

Method Distortion

Byte accuracy (%) on: Attacks. We consider the following attacks. Fine-tuning. We finetune the model in a supervised manner with the same settings as [START_REF] Taori | Stanford Alpaca: An instruction-following LLaMA model[END_REF], on 3 epochs with learning-rate of 2 ˆ10 ´5. Noise. We add zeromean Gaussian noise with standard deviation σ to the model weights.

Quantization. We quantize the model weights into b bits. To allow flexible rates and ease the experiments, this is done by uniformly quantizing the weights between their minimum and maximum values.

Pruning. We prune the model weights by zeroing the ones with smallest L1 norms, with sparsity given in percentage of zero weights.

Watermark settings. We apply the encoding process of Sect. 3.2.

For permutation invariance, we permute attention heads and FFN layers. For scaling, we alter the layers' RMSnorms and following matrices. The scaling vector α is such that log 10 pαq " Up´1, 1q.

For QK products, as mentioned in §3.1, the invertible matrix has to be block diagonal of 2 by 2 rotation matrices, so we randomly sample d{2 rotation angles. We fix the number of possible choices at k=8, i.e. each choice is encoded with a byte. Therefore, we encode 2 bytes at every layer, except in QK products where we encode 1. When combining all invariants together, we proceed the same way for all blocks: we start with permutation, then apply invertible matrices in QK products, then scale/unscale the layer norms and matrices.

Results.

Robustness. We evaluate the robustness of the watermark using the byte accuracy, i.e. the percentage of bytes correctly recovered.

Results are averaged over N =100 watermarked models except for fine-tuning where we only fine-tune one model. The model has L=32 layers so the watermark is 64 bytes long except for the QK products invariant where it is 32. In the case of combined invariants, the total number of bytes is 160. We speed-up the extraction by selecting a subset of 100 rows of the matrices (see Sect. 3.2); time needed for extraction is around 20 minutes when using the full matrix instead. Table 1 reports the byte accuracy for different processing applied before extraction. We observe that the watermark is robust to all attacks with byte accuracy >50%. Errors mainly come from the speed-up of the extraction process. We also consider the p-value of the associated statistical test (see Eq. 9). A byte accuracy of 50% on 64-bytes messages is more than enough to reliably identify a model: the p-values are always bellow 10 ´60 , due to the very low probability of simultaneously observing a match between tens of pairs of random bytes. As an illustration, 8 matching bytes on 64-bytes messages already gives a p-value of 10 ´8. Model's utility. In fact, previous invariants are not perfect because of quantization (weights are stored as 16bits floating point numbers). Thus, we quantitatively compare watermarked and original models. We feed to both of them 1k sequences of 256 tokens. Predicted next tokens are greedily chosen as the argmax of the 256k observed logits. Table 1 reports the proportion of predicted tokens that differ between watermarked and original models. As expected this proportion is very low (<1.8%) and higher for the scaling invariant since it further affects quantization. Besides, the distortion increases when the token is far in the sequence e.g. for sequences of length 1024 tokens, the average distortion at the last token rises to 2.5% for the scaling invariant. This is still very low and does not affect the utility of the model since predicted tokens are still likely.

Computational efficiency. Larger models have more layers and parameters, which increases the watermark capacity but also the computational cost of insertion and extraction. In Table 2, we report results for different model sizes. Insertion and extraction times are averaged over 100 runs and measured on 2 Intel(R) Xeon(R) 6230 @ 2.10GHz cores and a total of 480GB of RAM. The low computational costs and requirements (no GPU needed) makes it possible to scale to very large models.

CONCLUSION

Our work presents a lightweight approach for watermarking large transformers. We leverage invariance properties to generate equivalent copies for watermark embedding. It ensures that the model's outputs are preserved while providing close-to-perfect robustness against processes like fine-tuning or quantization.

Yet, this approach has limitations. Namely, it is limited to whitebox scenarios. Additionally, if a sophisticated attacker identifies all invariants, they may remove the watermark by applying the same transformation techniques. In this case, it would still be possible to identify that the model is an unauthorized copy but without the corresponding binary signature. Overall, this work is a starting point to exploit invariance properties that stem from the extreme redundancy of parameters of large networks, for watermarking applications.

Fig. 1 :

 1 Fig.1: Overview. We identify each model by applying invariance operations to the original weights.

Noise 1 . 0

 10 Quant. 3b Prun. 50% Fine-

Table 2 :

 2 Computational cost of watermark insertion and extraction for different model sizes and the different invariants.

	Model L	d	Insertion (s) Perm. Scaling QK	Extraction (s) Perm. Scaling QK
	7b 32 4096 3.5	2.7	7.4	9.2	31.7	6.0
	13b 40 5120 7.0	4.9	15.8 14.1 30.3	7.7
	30b 60 6656 19.3 8.7	47.3 31.7 54.7	13.5
	70b 80 8192 37.1 17.5	106	56.3 110	21.5


Guillaume Martin
email: guillaume.martin@cirad.fr

Franc-Christophe Baurens

Karine Labadie

Catherine Hervouet

Frédéric Salmon

Franck Mari

Nilda Paulo-De-La-Reberdiere

Ines Van Den Houwe

Jean-Marc Aury

Angélique D'hont

Nabila Yahiaoui
email: nabila.yahiaoui@cirad.fr

Shared pedigree relationships and transmission of unreduced gametes in cultivated banana

Keywords: Musa acuminata, Musa balbisiana, Musa schizocarpa, banana cultivars, Mchare, parentage, unreduced gamete, polyploid, whole genome approach

Background and Aims Cultivated bananas resulted from inter(sub)specific hybridizations involving Musa species and subspecies (M. acuminata subspecies, M. schizocarpa, M. balbisiana) and the subsequent selection, centuries ago, of hybrids with parthenocarpic, seedless fruits. Cultivars have low fertility and are vegetatively propagated, forming groups of somaclones. Relatively few of them, mainly triploids, are grown on a large scale and characterization of their parental relationships may be useful for breeding strategies. Here we investigate parental relationships and gamete-type contributions among diploid and polyploid banana cultivars.

• Methods We used SNP genotyping data from whole-genome sequencing of 178 banana individuals, including 111 cultivars, 55 wild bananas and 12 synthetic F 1 hybrids. We analysed the proportion of SNP sites in accordance with direct parentage with a global statistic and along chromosomes for selected individuals.

• Key Results

We characterized parentage relationships for 7 diploid cultivars, 11 triploid cultivars and 1 tetraploid cultivar. Results showed that both diploid and triploid cultivars could have contributed gametes to other banana cultivars. Diploids may have contributed 1x or 2x gametes and triploids 1x to 3x gametes. The Mchare diploid cultivar group, nowadays only found in East Africa, was found as parent of two diploid and eight triploid cultivars. In five of its identified triploid offspring, corresponding to main export or locally popular dessert bananas, Mchare contributed a 2x gamete with full genome restitution without recombination. Analyses of remaining haplotypes in these Mchare offspring suggested ancestral pedigree relationships between different interspecific banana cultivars.

• Conclusions

The current cultivated banana resulted from different pathways of formation, with implication of recombined or un-recombined unreduced gametes produced by diploid or triploid cultivars. Identification of dessert banana's parents and the types of gametes they contributed should support the design of breeding strategies.

INTRODUCTION

Cultivated bananas (Musa sp.) resulted from a complex process of natural inter(sub)specific hybridization [START_REF] Simmonds | The evolution of the bananas[END_REF][START_REF] Perrier | Multidisciplinary perspectives on banana (Musa spp.) domestication[END_REF]Martin et al., 2020b[START_REF] Martin | Interspecific introgression patterns reveal the origins of worldwide cultivated bananas in New Guinea[END_REF]. They are vegetatively propagated and only a very limited number of these cultivars are grown on a large scale. For example, the commercial dessert Cavendish banana represents >50 % of the world production [START_REF] Lescot | Diversité génétique de la banane[END_REF]. Banana culture faces major biotic stresses, including the fungal disease caused by a Fusarium sp. lineage named TR4, which currently threatens banana cultures [START_REF] Viljoen | Fusarium wilt (Panama disease) and monoculture in banana production: resurgence of a century-old disease[END_REF]. There is thus a crucial need for breeding disease-resistant bananas while maintaining agro-morphological and fruit quality traits. However, breeding strategies are hampered by the sterility or very low fertility of cultivars, which limits crossing abilities and progeny number. In this context, knowledge of cultivar parentage would represent a very useful resource for breeding.

The main domestication traits of bananas relate to fruit edibility, with the selection by humans of plants with parthenocarpic seedless fruits, and therefore with low fertility. Three main species are involved in their formation process: Musa acuminata (A genome, 2n = 2x = 22), M. balbisiana (B genome, 2n = 2x = 22) and M. schizocarpa (S genome, 2n = 2x = 22). So far, the A genome has been present in all analysed banana cultivars, except the small group of Fe'i cultivars that derived only from Musa species of the Australimusa series (T genome, 2n = 2x = 20) [START_REF] Simmonds | The taxonomy and origins of the cultivated bananas[END_REF][START_REF] Jarret | RFLP-based phylogeny of Musa species in Papua New Guinea[END_REF][START_REF] Martin | Interspecific introgression patterns reveal the origins of worldwide cultivated bananas in New Guinea[END_REF].

Hybridizations involving M. schizocarpa and M. acuminata subspecies (ssp. banksii and possibly ssp. zebrina) in New Guinea are proposed as the starting point of banana domestication [START_REF] Martin | Interspecific introgression patterns reveal the origins of worldwide cultivated bananas in New Guinea[END_REF]. Along with diffusion of early cultivars throughout Southeast Asia, additional hybridizations occurred with other Musa species and subspecies, such as M. acuminata ssp. zebrina, malaccensis, burmannica, halabanensis, M. balbisiana and at least one unknown contributor that might be an uncharacterized M. acuminata subspecies (Martin et al., 2020b[START_REF] Martin | Interspecific introgression patterns reveal the origins of worldwide cultivated bananas in New Guinea[END_REF][START_REF] Sardos | Hybridization, missing wild ancestors and the domestication of cultivated diploid bananas[END_REF]. Large chromosomal rearrangements (i.e. translocation, inversion) present in some wild Musa were transmitted to many cultivars (Martin et al., 2020a). This context of inter(sub)specific hybridization may have favoured production of 2x gametes from diploid hybrids, leading to the formation of triploid cultivars [START_REF] Simmonds | The evolution of the bananas[END_REF][START_REF] Perrier | Multidisciplinary perspectives on banana (Musa spp.) domestication[END_REF]. The current diversity of cultivars includes diploids and triploids with different global genomic combinations (e.g. AA, AB, AAA, AAB, ABB, AAT) modulated by interspecific recombination and with an A genome introgressed by M. schizocarpa [START_REF] Simmonds | The taxonomy and origins of the cultivated bananas[END_REF][START_REF] Nemeckova | Molecular and cytogenetic study of East African Highland banana[END_REF][START_REF] Baurens | Recombination and large structural variations shape interspecific edible bananas genomes[END_REF][START_REF] Cenci | Unravelling the complex story of intergenomic recombination in ABB allotriploid bananas[END_REF][START_REF] Martin | Interspecific introgression patterns reveal the origins of worldwide cultivated bananas in New Guinea[END_REF]. Within these genomic groups, cultivars are classified in distinct subgroups, each of which is thought to derive from one seed and centuries or millennia of vegetative propagation, and thus they represent subgroups of phenotypically different somaclonal mutants (Simmonds, 1954;[START_REF] Perrier | Multidisciplinary perspectives on banana (Musa spp.) domestication[END_REF]. The most-grown cultivar subgroups are triploid, including AAA dessert bananas such as Cavendish, AAA cooking East African Highland bananas and AAB plantain bananas.

The complex hybridization processes at the origin of cultivars would be difficult to rapidly reproduce in breeding programmes. The identification and use of direct parents of successful cultivars could thus be useful to facilitate banana breeding [START_REF] Raboin | Diploid ancestors of triploid export banana cultivars: molecular identification of 2n restitution gamete donors and n gamete donors[END_REF]. Several parentages have been proposed based on analyses with low-density markers (RFLP and SSR) involving in particular the diploid Mchare cultivar subgroup (previously named Mlali) [START_REF] Raboin | Diploid ancestors of triploid export banana cultivars: molecular identification of 2n restitution gamete donors and n gamete donors[END_REF][START_REF] Perrier | Combining biological approaches to shed light on the evolution of edible bananas[END_REF][START_REF] Hippolyte | Foundation characteristics of edible Musa triploids revealed from allelic distribution of SSR markers[END_REF]. Higher-density markers should allow confirmation of parentage relationships at whole-genome scale, and should provide additional information on cultivar pedigree and on gamete transmission processes.

The aim of this study was to use high-density singlenucleotide polymorphism (SNP) genotyping information from 178 banana individuals to identify potential parents of cultivars from our sample. Special emphasis was placed on the contribution of the Mchare cultivar subgroup and the parental relationships between Mchare-derived cultivars. This work also addresses questions on gamete transmission type leading to major cultivars and the potential role of triploids as parents to other triploids.

MATERIALS AND METHODS

Materials

A set of 178 banana individuals was first considered for this analysis (Supplementary Data Table S1). These individuals correspond to wild Musa acuminata (A genome, 2n = 2x = 22), M. schizocarpa (S genome, 2n = 2x = 22), M. balbisiana (B genome, 2n = 2x = 22) and Australimusa spp. accessions (T genome, 2n = 2x = 20), to cultivars derived from these species, and to 12 synthetic F 1 hybrids generated at the CIRAD breeding platform by crosses between parents also represented in the dataset (Supplementary Data Table S1). SNP-based genotyping data (not phased) of these individuals were extracted from a larger vcf file obtained from high-coverage Illumina sequencing data used to perform chromosome ancestry painting, described in [START_REF] Martin | Interspecific introgression patterns reveal the origins of worldwide cultivated bananas in New Guinea[END_REF]. SNP positions are located along the DH-Pahang V4 reference genome [START_REF] Belser | Telomere-to-telomere gapless chromosomes of banana using nanopore sequencing[END_REF]. All scripts used are available in the vcfhunter toolbox (https:// github.com/SouthGreenPlatform/VcfHunter). Compared with the original file, a new genotype calling was performed (using TotalRecal.1.0.py), for accession DB_Pisang_Awak, which was tetraploid instead of triploid according to the [START_REF] Martin | Interspecific introgression patterns reveal the origins of worldwide cultivated bananas in New Guinea[END_REF] analysis. Among the 178 individuals, 26 were similar to other accessions (i.e. somaclones or duplicates of other accessions). For these similar accessions (Supplementary Data Table S1), only one was reported in results tables. Representations of genome ancestry mosaic painting were published previously [START_REF] Martin | Interspecific introgression patterns reveal the origins of worldwide cultivated bananas in New Guinea[END_REF] https://banana-genome-hub.southgreen.fr/ node/50/1598445), except for newly generated results of deduced haplotypes (see below).

Methods

Two types of SNP data analysis were performed (Supplementary Data Fig. S1). The first one consisted in the identification of triplets of individuals that match a direct parents-child trio relationship [i.e. the genotype from an individual (2x, 3x or 4x) defined as child is compatible with a combination of two individuals (2x, 3x or 4x) defined as parents when looking at their genotypes]. The second one consisted in the identification of pairs of individuals that match a direct parent-child duo relationship involving one individual from the diploid Mchare clonal subgroup as a parent [i.e. the genotype from an individual (2x, 3x or 4x) defined as child is compatible with Mchare as parent when looking at the genotype]. Both analyses were performed in two steps: (1) calculation of the global proportion of SNP sites in accordance with each tested trio or duo; and (2) validation of identified trios or duos through local analysis along chromosomes of the proportion of SNP sites in accordance with such trios or duos.

Identification of potential parents-child trios through global SNP analysis

This analysis was performed using the ValPar.py tool, added to the vcfhunter toolbox. The tool worked as follows.

(1) For each potential parent, all possible gametes were generated. These gametes were all combinations of k elements, with repetition and without order, sampled among n non-redundant alleles found at the studied position in the potential parent (k being the ploidy of the potential gamete). For example, for a position where a parent is ATT, the different possible diploid gametes are: AA, AT and TT. If the potential child was triploid, two values of n were tested for each parent, i.e. n = 1 and n = 2.

(2) For each potential parent pair, all possible zygote allele combinations were generated by combining possible gametes from both parents (only gamete combinations giving the correct zygote ploidy were generated). (3) The allele combination found in the potential child was searched for among the possible zygote allele combinations from the parents. (4) The proportion of sites in which the potential child allele combination matched one of the possible zygote allele combinations from the parent pair was then calculated for each potential parent pair. Ploidy was considered; for example, if the potential child was triploid, two final values were reported: one with parent 1 being the 1x gamete donor and parent 2 being the 2x gamete donor, and a second one with parent 1 being the 2x gamete donor and parent 2 being the 1x gamete donor.

To save computation time, accessions without Australimusa ancestry were analysed using a filtered vcf including only polymorphic sites in the 167 accessions from M. acuminata, M. schizocarpa and/or M. balbisiana origin. The filtered vcf contained 6 867 490 polymorphic sites. Accessions with an Australimusa ancestry were analysed using a filtered vcf including only polymorphic sites in the 178 individuals (the 167 A, S and/or B accessions plus the 11 Australimusa or Australimusa hybrid accessions) (Supplementary Data Table S2). The filtered vcf contained 8 285 170 polymorphic sites.

The proportion of sites in accordance with tested parentage was calculated for each trio with a cultivated accession as a child (Supplementary Data Table S3). The following criteria were used to consider parental relationships as valid: (1) the proportion of sites in accordance with the tested parentage should be equal to or higher than 0.999, which is the minimal value observed in the 12 synthetic parents-child trios (Supplementary Data Table S4); and (2) among couples of parents that validated this threshold only those with the minimal cumulative ploidy were retained. The reason behind this is that we considered that diploids were more likely to be parents compared with triploids.

Identification of potential Mchare contribution through global SNP analysis

The contribution of Mchare was specifically analysed by looking for a potential 1x and 2x Mchare gamete restitution on all individuals of the dataset.

According to [START_REF] Martin | Interspecific introgression patterns reveal the origins of worldwide cultivated bananas in New Guinea[END_REF], Mchare ancestral contributors were only from M. acuminata ssp. and M. schizocarpa. Thus, only polymorphic sites between and within these genetic groups were kept for the analysis. For this, sites containing private alleles from other species (i.e. M. balbisiana or Australimusa; Supplementary Data Table S2) were identified and removed using IdentPrivateAllele.py, allele_ratio_group. py and vcfSelect.py as previously described [START_REF] Martin | Interspecific introgression patterns reveal the origins of worldwide cultivated bananas in New Guinea[END_REF]. If not removed, such sites would generate an important proportion of sites in accordance with the Mchare contribution only because they are homozygous in all individuals with M. acuminata and/or M. schizocarpa origin. The resulting vcf file contained 5 412 666 polymorphic SNP sites.

The analysis was then performed in several steps (Supplementary Data Fig. S1, purple steps): (1) selecting, for each duo (Mchare, potential child), only sites that are polymorphic within and/or between individuals of the duo using vcfFilter.1.0.py; (2) calculating the proportion of sites validating a potential 1x contribution of Mchare to the potential child using the ACRO.py tool added to the vcfhunter toolbox (Supplementary Data Table S5); (3) in case of a polyploid potential child, calculating the proportion of sites validating a potential 2x (recombined or un-recombined) contribution of Mchare to the potential child using the ACRO.py tool (Supplementary Data Table S5); (4) in case of a polyploid potential child, looking for the proportion of sites validating a complete Mchare genome (i.e. un-recombined 2x gamete, named hereafter 2x c ) in the potential child using vcfRemove.1.0.py (Supplementary Data Table S5).

The summary statistics obtained from steps 2, 3 and 4 were used to identify potential duos with a Mchare contribution. For this, duos that had a proportion of SNP sites in accordance with a 1x or 2x contribution >99 % were selected (Supplementary Data Table S5). This value was selected based on an observed shift in the summary statistic values (Supplementary Data Table S5).

Validation of parents-child trios through local SNP analysis along chromosomes

To validate selected parents-child trios, the distribution of the proportion of shared SNPs was inspected along reference chromosomes. This was performed in several steps (Supplementary Data Fig. S1, green steps), as follows. (1) Selecting, in the vcf file, the SNP sites that were polymorphic within and/or between individuals of the trio. (2) Calculating from the obtained vcf file the proportion of sites in accordance with the trio on windows of 201 SNPs size. Sites in accordance were calculated as described in the trio identification section above. (3) Filtering the vcf in order to keep, for each parentchild duo, polymorphic SNPs within and between individuals of the duo, and calculating from the resulting vcf file the proportion of sites in accordance with the duo on window sizes of 201 SNPs. This calculation considers the gamete ploidy of the tested parent. (4) In parallel, the number of alleles shared between the parent and the child was calculated to test for complete genome restitution. (5) In cases where the complete genome of the parent was found in the child, the alleles from this parent were removed from the child's genotype in the vcf obtained in step (1). This allowed access to the gamete given by the other parent. ( 6) The remaining genotype(s) were compared with the genotype of the second potential parent to analyse the proportion of sites in accordance with such parentage. This analysis was performed using the APAR.py tool that was added to the vcfhunter toolbox.

For ease of representation, the proportions of sites in discordance with tested parentages were displayed along each chromosome and all results were visualized using Circos [START_REF] Krzywinski | Circos: an information aesthetic for comparative genomics[END_REF]. Configuration and files required for Circos visualization were automatically generated by the APAR.py tool.

Validation of parent-child duos through local SNP analysis along chromosomes

Validation of parent child duos (Supplementary Data Fig. S1, blue steps) was performed as follows: (1) for each duo, Downloaded from https://academic.oup.com/aob/article/131/7/1149/7189797 by CEA Saclay user on 22 December 2023 selection in the vcf of sites that were polymorphic within and between individuals of the duos using vcfFilter.1.0.py; (2) looking along chromosomes for the proportion of SNP sites validating a 1x contribution of the potential parent to the potential child using the ACRO.py tool; (3) in case of a polyploid potential child, looking along chromosomes for the proportion of SNP sites validating a potential 2x contribution of the potential parent to the potential child using the ACRO.py tool; (4) in case of a polyploid potential child, looking along chromosomes for the proportion of sites validating a complete parental genome in the potential child using the vcfIdent.1.0.py tool of the vcfhunter toolbox. These proportions were calculated along chromosomes on windows of size 201 SNPs.

The proportions of sites in discordance with tested parentages were represented along each chromosome and results were visualized using Circos [START_REF] Krzywinski | Circos: an information aesthetic for comparative genomics[END_REF] and the DrawCircos.py tool added to the vcfhunter toolbox.

In silico chromosome ancestry painting of remaining haplotype(s) in polyploid progeny where complete genome restitution of a parent was identified

The genotype of the parent was removed from the polyploid child in the vcf using the vcfRemove.1.0.py tool. Remaining alleles were considered as a haplotype, representative of the gamete from the second parent. The in silico chromosome ancestry painting of the remaining haplotype(s) corresponding to the gamete from the second parent was performed using the ancestry specific alleles and the process described in [START_REF] Martin | Interspecific introgression patterns reveal the origins of worldwide cultivated bananas in New Guinea[END_REF]. The process was automated with the SPRH.py tool added to the vcfhunter toolbox (Supplementary Data Fig. S1).

Mosaics obtained for Mchare-derived AAB cultivars were compared with published banana mosaics [START_REF] Martin | Interspecific introgression patterns reveal the origins of worldwide cultivated bananas in New Guinea[END_REF] by looking for similar ancestry mosaic patterns or compatible mosaics that could derive from recombination between parental haplotypes.

Management of aneuploidy

The triploid Lady Finger (Nadan) accession had a supernumerary chromosome 8. To manage this aneuploidy, the genotype calling of Lady Finger along chromosome 8 was recalculated with a ploidy of 4 using the TotalRecal.1.0.py script of the vcfhunter toolbox. For this accession, the analyses described previously (with exception of the global one) were performed separately on triploid chromosomes and on chromosome 8 and results were pooled. For tetraploid Calypso, aneuploid regions were identified by analysing read coverage of SNP sites along chromosomes, using the vcf2cov.py program added to the vcfhunter toolbox.

RESULTS

Global parentage analysis identifies one parent or the two parents for several cultivars

Parentage relationships were searched among 178 banana individuals (Supplementary Data Table S1) using SNP genotyping data obtained by [START_REF] Martin | Interspecific introgression patterns reveal the origins of worldwide cultivated bananas in New Guinea[END_REF] from whole-genome Illumina sequencing. The dataset included 55 wild accessions representing M. acuminata ssp. (A genome), M. schizocarpa (S genome), M. balbisiana (B genome) and Australimusa spp. (T genome), 111 cultivars derived from these species and 12 F 1 diploid hybrids for which both parents were known. Banana cultivars belonging to a subgroup correspond to somaclonal variants that are currently indistinguishable at the genomic level. In order to facilitate the reading of the manuscript, when relevant, we will refer to the name of the subgroup (Supplementary Data Table S1) rather than to the name of the accession.

Ten parents-child trios were identified, as they showed a global proportion of SNP sites in accordance with the trio that was equal to or higher than the proportion (99.9 %) observed for the 12 F 1 synthetic parents-child trios (Table 1, Supplementary Data Table S3). Three additional parents-child trios that involved Australimusa species were identified; however, two of them may correspond to clonal relationship between cultivars and the third to similarity between two wild accessions (Supplementary Data Table S3).

The targeted search for parental contributions of the Mchare cultivar subgroup (Supplementary Data Table S5) yielded a total of 13 Mchare-child duos (Table 1). Three of these 13 duos (involving Gros Michel, Mnalouki, Colatina Ouro) were already identified among the parents-child trios. The duos involved two diploid, ten triploid and one tetraploid accessions. Among them, six accessions (five triploids and one tetraploid) had >99.6 % of sites in accordance with Mchare being the 2x gamete donor and >99.4 % of sites suggested that both haplotypes of Mchare are found in each of these six accessions (Supplementary Data Table S5).

Analysis of SNPs along chromosomes validates most candidate parents from the parents-child trio and parent-child duo analysis

The proposed parentages for cultivars (10 trios and 13 duos) were further investigated by local analysis of shared SNPs along their chromosomes. Two additional trios proposed in the literature [START_REF] Perrier | Combining biological approaches to shed light on the evolution of edible bananas[END_REF][START_REF] Hippolyte | Foundation characteristics of edible Musa triploids revealed from allelic distribution of SSR markers[END_REF] with Cavendish cultivars as a child, Mchare as 2x gamete donor and diploid cultivars Pisang Madu or Pisang Pipit as 1x gamete donor were also tested. The proportion of SNPs in discordance along the chromosomes was calculated and represented together with the in silico chromosomal ancestry painting (Fig. 1). Figure 1A represents the tested trio Gros Michel (child), Mchare (2x parent) and Khai Nai On (1x parent). The proportion of SNPs in discordance was close to zero along all chromosomes, validating this parents-child trio. In contrast, the two trios proposed in the literature with Cavendish as child showed large regions, on nearly all chromosomes, in which the proportion of SNPs in discordance was relatively high (Fig. 1B, Supplementary Data Fig. S2A), indicating that the direct trio parentages were not valid.

All ten trios suggested by the global analysis were validated by this approach (Fig. 1A,C, Supplementary Data Fig. S2B-I). For two of them, a peak of discordance was observed on a small region on chromosome 8 (Fig. 1C, Supplementary Data Fig. S2D), probably due to small differences (gene conversion, aneuploidy) resulting from divergence after vegetative propagation over centuries or problems of read mapping and variant calling. Among the ten validated trios, three distinct trios were proposed with Galeo as child (in italics in Table 1). This impossible situation is further investigated in the next section of results.

The seven remaining validated trios revealed different types of cross involving diploids and triploids as parents of diploid or triploid cultivars (Table 1, Fig. 1, Supplementary Data Fig. S2). Figure 1C illustrates a case where a plantain (AAB triploid genome) is proposed as a 2x gamete donor for another triploid cultivar. All identified parents are cultivars except in one case where a wild M. balbisiana accession [Pisang Klutuk Wulung (PKW)] is a parent of the triploid cultivar Saba (Table 1, Supplementary Data Fig. S2).

Similar analyses were performed with the 13 predicted Mchare duos (including three already present in trios) and validated 11 of them (Table 1). A 2x contribution of the Mchare was validated for five triploid cultivars: Nadan (Fig. 2A), Gros Michel (Supplementary Data Fig. S3A), Cavendish (Supplementary Data Fig. S3B), Nendra Padaththi (Supplementary Data Fig. S3C) and Pome (Supplementary Data Fig. S3D). A 2x contribution of the Mchare was also found in tetraploid cultivar Calypso (Supplementary Data Fig. S3E). A 1x contribution of the Mchare was validated for two diploid cultivars [Paka (Supplementary Data Fig. S3F) and Colatina Ouro (Supplementary Data Fig. S3G)] and three triploid cultivars [Koja (Supplementary Data Fig. S3H), Pisang Ambon (Supplementary Data Fig. S3I) and Mnalouki (Supplementary Data Fig. S3J)]. In Pisang Ambon (Supplementary Data Fig. S3I), a small region at the beginning of chromosome 1 was discordant for a 1x Mchare contribution but corresponded to a region where Pisang Ambon is aneuploid with a ploidy of 2x instead of 3x [START_REF] Martin | Interspecific introgression patterns reveal the origins of worldwide cultivated bananas in New Guinea[END_REF]. The segment of Mchare origin was likely lost from this region during years of vegetative propagation of Pisang Ambon. Finally, for two triploids, Hom Thong Mokho (Fig. 2B) and Wh-O-Gu (Supplementary Data Fig. S3K), regions of discordance, even with a 1x contribution of the Mchare were observed, suggesting that these accessions were not directly derived from Mchare accessions but are related to them.

Complete 2x and 3x gamete transmission among cultivated bananas

The proportions of shared SNPs along chromosomes were analysed in the seven predicted cases of 2x gamete transmission by a diploid accession (Table 1) to specify the nature of the transmitted 2x gametes. One case involved the diploid Tjau Lagada, which transmitted a recombined 2x gamete to Pisang Papan (Fig. 2C). In six cases, a complete diploid Mchare genome restitution was detected (Fig. 2A, Supplementary Data Fig. S3A-E). These cases included the tetraploid accession Calypso, which is an improved cultivar derived from a cross between Highgate, a dwarf clone of the triploid Gros Michel cultivar and a diploid individual [START_REF] Borges | Characterisation of metabolic profile of banana genotypes, aiming at biofortified Musa spp. cultivars[END_REF]. The Mchare contribution to Calypso identified in this duo is due to the presence of the Mchare genome in Gros Michel. The test of the complete genome restitution of Gros Michel along chromosomes of Calypso showed that only one region at one extremity of chromosome 10 was not in accordance with such complete genome restitution (Fig. 2D). Calypso is aneuploid for a few chromosomal regions, including a missing chromosomal region at one extremity of chromosome 10 (Fig. 2D, Supplementary Data Fig. S4). The results were thus in accordance with a complete 3x gamete restitution of Gros Michel to Calypso.

A particular situation was found for the Galeo diploid cultivar, which was proposed as child in three distinct trios involving the Palang triploid accession, as one parent, and any of the diploid accessions Khai Nai On, Sinwobogi or SF265 as the second parent (Table 1). These three diploid potential parents are not somaclones as they do not have the same ancestral mosaic genome [START_REF] Martin | Interspecific introgression patterns reveal the origins of worldwide cultivated bananas in New Guinea[END_REF], which raised questions about the process generating these trios. Further examination of the trios involving Galeo revealed that the complete genome of Galeo was present in triploid Palang (Supplementary Data Fig. S5A). This led us to propose that Galeo may not be the child but rather the parent of these accessions and transmitted a 2x gamete to Palang and a 1x gamete to Khai Nai On, Sinwobogi and SF265 (Table 1). The first proposed trios are a consequence of the presence of the Galeo genome in Palang, which allows for recombinant haplotypes complementing those present in Khai Nai On, Sinwobogi and SF265 to generate Galeo (Supplementary Data Fig. S5B). Access to real haplotypes (phased data from genetic studies or long-read sequencing technologies) of these individuals should allow validation or rejection of this hypothesis.

In silico extraction and analysis of the remaining 1x gamete from Mchare-derived accessions

For accessions derived from a complete gamete restitution (2x or 3x), it is possible to deduce the complementary 1x gamete. In most Mchare-derived polyploid accessions resulting from such gametes, the parental origins of the second parent were not identified (Table 1). To learn more about the second parent, alleles from the complete genome donor (Mchare or Gros Michel) were removed from the child genotypes to deduce the gamete from the second parent. These gametes were predicted to be 1x except for Nadan, where the deduced gamete had two copies of chromosome 8, suggesting a 1x + 1 gamete. These deduced gametes were then processed as described in [START_REF] Martin | Interspecific introgression patterns reveal the origins of worldwide cultivated bananas in New Guinea[END_REF] to obtain their genome ancestry mosaic (Supplementary Data Fig. S6). This revealed a M. balbisiana introgressed status of the second parents of AAB cultivars Nadan, Nendra Padaththi and Pome. The comparison of the genome ancestry mosaic of deduced gametes of these three AAB cultivars with the ancestral mosaics of A/B hybrid cultivars obtained by [START_REF] Martin | Interspecific introgression patterns reveal the origins of worldwide cultivated bananas in New Guinea[END_REF] suggested potential similarity between their 1x gamete donors and two ABB triploid cultivars (Monthan and Ney Mannan; Figs 3 and4, Supplementary Data Fig. S6). Nadan showed potential additional similarity with Saba and Pome showed potential additional similarity with Saba, Pelipita and Pisang Kelat (Supplementary Data Fig. S6). This led us to investigate the potential shared pedigree between these cultivars. As illustrated for chromosome 8 (Fig. 3A-C), for all three AAB cultivars (Pome, Nendra Padaththi and Nadan), large regions of agreement but also large regions of discordance were observed when parentage of their deduced gamete with Ney Mannan and Monthan was tested. Such patterns were visible on several chromosomes (Supplementary Data Fig. S6), suggesting close pedigree relationships. In contrast, comparison with Saba, Pelipita and Pisang Kelat did not show such large regions of agreement (Fig. 3B,C, Supplementary Data Fig. S6), excluding very close pedigree relationships.

Figure 3 also illustrates some similar agreement/discordance patterns when comparing the deduced gametes from the AAB cultivars with Ney Mannan and Monthan. This suggests that all tested AAB cultivars and the ABB Ney Mannan and Monthan are related to each other.

The mosaics of the other deduced gametes also revealed a M. acuminata ssp. malaccensis and ssp. banksii hybrid as second parent of Calypso and a more complex hybrid status of the second parents of Cavendish and Gros Michel (Fig. 4). As expected from validated trios, the remaining haplotype of Gros Michel matched a potential 1x gamete from Khai Nai On (Supplementary Data Fig. S6K). The remaining haplotype of Cavendish showed large accordance/discordance segments with Pisang Pipit or Pisang Madu as 1x gamete donors, suggesting that the 1x gamete donor of Cavendish is a close relative of both accessions (Supplementary Data Fig. S6L,M).

DISCUSSION

We analysed the direct parentage between 178 banana individuals including 111 cultivars and 55 wild accessions and characterized parentage relationships for 7 diploid cultivars, 11 triploid cultivars and 1 tetraploid, some of them representing major subgroups of dessert banana. These results highlighted that diploid but also triploid cultivars could be parents of other diploid, triploid or tetraploid cultivars by contributing 1x, 2x or 3x gametes. A targeted analysis of the Mchare subgroup parentage relationships showed an important contribution of this subgroup to banana cultivars (Fig. 4).

Mchare contributions to banana cultivars

The Mchare bananas form a phenotypically diverse subgroup of AA diploids. They are nowadays only found in some East African regions and islands, where they are particularly appreciated and culturally important [START_REF] Perrier | East African diploid and triploid bananas: a genetic complex transported from South-East Asia[END_REF]. We found that Mchare contributed 1x gametes to two diploid and three triploid cultivars, and also 2x gametes to five triploid cultivars of our sample. It is also present in tetraploid Calypso through the Gros Michel contribution (Fig. 4). The Gros Michel dessert banana was very popular in the first half of the previous century, but being susceptible to the Panama disease (Fusarium oxysporum fsp. cubense Race 1), it was replaced by Cavendish. We confirmed that both cultivars resulted from the transmission of a 2x gamete from Mchare [START_REF] Raboin | Diploid ancestors of triploid export banana cultivars: molecular identification of 2n restitution gamete donors and n gamete donors[END_REF][START_REF] Perrier | Combining biological approaches to shed light on the evolution of edible bananas[END_REF][START_REF] Hippolyte | Foundation characteristics of edible Musa triploids revealed from allelic distribution of SSR markers[END_REF]Martin et al., 2020b) and demonstrated that in both cases the complete Mchare genome was transmitted. In addition, we validated the implication of Mchare as 2x gamete donor in the AAB cultivars Nadan, Pome/ Prata and Nendra Padaththi [START_REF] Perrier | Combining biological approaches to shed light on the evolution of edible bananas[END_REF][START_REF] Hippolyte | Foundation characteristics of edible Musa triploids revealed from allelic distribution of SSR markers[END_REF] with additional information on complete genome transmission, but we excluded the 2x contribution of Mchare to Hom Thong Mokho [START_REF] Perrier | Combining biological approaches to shed light on the evolution of edible bananas[END_REF]. Differences between our results and previous studies are likely due to the higher genotyping density and to the methodology that we used to validate parentage along chromosomes. However, we cannot completely exclude differences between studied individuals from distinct collections or resulting from mis-labelling. In addition, we also showed that Mchare contributed a 1x gamete to the triploid cultivars Mnalouki (AAB from Comoro Islands), Koja (AAA from Comoro Islands) and Pisang Ambon (AAA) and to diploid cultivars Paka (AA from East Africa) and Colatina Ouro (AA) (Fig. 4). Mchare clones have contributed their genomes to cultivars of diverse origins, including cultivars found in Africa but also triploid dessert bananas that are predicted to originate from Southeast Asia. Thus, Mchare most probably originated in Southeast Asia and were transported by humans to Africa [START_REF] Perrier | East African diploid and triploid bananas: a genetic complex transported from South-East Asia[END_REF]. In all cases in which the Mchare was proposed as a 2x gamete donor, a full genome of the Mchare was found. This is the case for the two main dessert AAA banana cultivar subgroups Cavendish and Gros Michel, and also for AAB cultivars from the Pome/Prata, Nadan and Nendra Padaththi subgroups. One can hypothesize that a complete genome of Mchare brings highly favourable agro-morphological trait combinations that could explain the selection of individuals resulting from complete Mchare gamete restitution. An alternative hypothesis is that this genome is prone to perform a full gametic restitution, thereby increasing the probability of finding such a contribution to cultivated bananas. A combination of both these hypotheses could also be considered.

Other pedigree relationships

Second parents in Mchare-derived cultivars were various (Fig. 4). We confirmed that the second gamete present in Gros Michel was a 1x gamete from Khai Nai On [START_REF] Raboin | Diploid ancestors of triploid export banana cultivars: molecular identification of 2n restitution gamete donors and n gamete donors[END_REF][START_REF] Hippolyte | Foundation characteristics of edible Musa triploids revealed from allelic distribution of SSR markers[END_REF]. Moreover, we showed that the Galeo accession may be a grandparent of Gros Michel through Khai Nai On. We excluded Pisang Pipit or Pisang Madu as 1x gamete donors to Cavendish [START_REF] Perrier | Combining biological approaches to shed light on the evolution of edible bananas[END_REF][START_REF] Hippolyte | Foundation characteristics of edible Musa triploids revealed from allelic distribution of SSR markers[END_REF], although the presence of large regions consistent with the proposed relationship suggested some shared pedigree.

Other second parents to Mchare-derived cultivars included cultivars as diverse as diploid Sucrier and triploid plantains, and also unknown A/B hybrids. For AAB Nadan, Nendra Padaththi and Pome, we showed that their unknown A/B hybrid second parents were related to ABB Ney Mannan and Monthan and that they transmitted 1x gametes (or in the case of Nadan an aneuploid 1x + 1 gamete) (Fig. 4). Note that ABB cultivars from the subgroup named Bluggoe were found to be similar at the genome mosaic level to cultivars from subgroup Monthan (Supplementary Data Table S1) [START_REF] Cenci | Unravelling the complex story of intergenomic recombination in ABB allotriploid bananas[END_REF][START_REF] Martin | Interspecific introgression patterns reveal the origins of worldwide cultivated bananas in New Guinea[END_REF]. In this study, we also suggested that Saba cultivars derived from Monthan. Thus, the AAB cultivars Nadan, Nendra Padaththi, Pome and ABB cultivars Monthan, Ney Mannan, Bluggoe and Saba are related. This is coherent with their shared A/B recombination breakpoints on chromosome 9 [START_REF] Martin | Interspecific introgression patterns reveal the origins of worldwide cultivated bananas in New Guinea[END_REF].

In this study, all identified parental relationships only involved cultivars as parents, with one exception. This can be explained by the fact that cultivars have a fixed genotype conserved through vegetative propagation, which allows the identification of natural hybridization events that occurred centuries ago. Conversely, most wild parents involved in hybridizations some centuries ago may not exist any more, due to sexual reproduction. The only exception we found is a wild individual, PKW, which was proposed as a parent of triploid cultivar Saba. The PKW accession, as well as some accessions of M. balbisiana, are popular in Indonesia for various uses and are vegetatively propagated [START_REF] Ahmad | Genetic diversity of Musa balbisiana Colla in Indonesia based on AFLP marker[END_REF]. This may explain why we could still identify parentage involving PKW.

Different types of gametes and triploid individuals are involved in the formation of many banana cultivars

Several cases of transmission of un-recombined or recombined 2x gametes from diploid to triploid cultivars were identified. They involved mainly Mchare cultivars but also Tjau Lagada and likely Galeo. More surprisingly, in a few cases, a triploid was proposed as parent of another triploid or diploid cultivar, either as a 2x or as a 1x gamete donor. Banana cultivars, either diploid or triploid, are poorly fertile and sometimes totally sterile. Crosses have been undertaken since the 1930s in order to exploit a cultivar's residual fertility in breeding programmes. This often required a huge number of pollinations.

Cytogenetic analysis of the progenies obtained showed that diploid bananas generally produce 1x gametes while triploids may produce from 1x up to 6x gametes (Wilson, 1946a-c;[START_REF] De Langhe | Did backcrossing contribute to the origin of hybrid edible bananas?[END_REF][START_REF] Shepherd | Cytogenetics of the genus Musa. Montpellier: INIBAP Simmonds NW. 1954. Varietal identification in the Cavendish group of bananas[END_REF]. These features are exploited in breeding programmes to generate tetraploids by crossing triploid cultivars with diploids. Triploids could thus also potentially be involved through natural hybridization in the formation of other cultivars. However, this should be rare given their poor levels of fertility. Based on nuclear and cytoplasmic genome information, a possible implication of triploid cultivars in the formation of other cultivars has been proposed [START_REF] Carreel | Ascertaining maternal and paternal lineage within Musa by chloroplast and mitochondrial DNA RFLP analyses[END_REF][START_REF] De Langhe | Did backcrossing contribute to the origin of hybrid edible bananas?[END_REF]. Here, we identified such cases. For two triploid cultivars (ABB Saba and AAB Mnalouki), we identified a triploid parent (ABB or AAB, respectively) that could have contributed a 2x gamete. In addition, we observed one trio and one duo in which a 1x and 3x gamete respectively could have been provided by AAA triploids. This illustrates that such a process may occur in different types of triploid banana. However, we cannot exclude that a yet not identified diploid accession could be the parent of both the child and the triploid parent proposed in our parents-child trio analysis.

Previous studies of progeny obtained by crossing triploid Gros Michel with different diploids showed that the main class of offspring obtained was tetraploid (Wilson, 1946c;[START_REF] De Langhe | Did backcrossing contribute to the origin of hybrid edible bananas?[END_REF]. Based on breeding behaviour and cytological observations, it was proposed that triploid gametes were the main class of viable gametes produced by Gros Michel (Wilson, 1946c;[START_REF] De Langhe | Did backcrossing contribute to the origin of hybrid edible bananas?[END_REF]. Our analysis along chromosomes showed that the tetraploid cultivar Calypso resulted from the transmission of an un-recombined 3x gamete from the triploid Gros Michel. One region of discrepancy on chromosome 10 may be explained by aneuploidy in the triploid parent [a Gros Michel clone named Highgate [START_REF] Borges | Characterisation of metabolic profile of banana genotypes, aiming at biofortified Musa spp. cultivars[END_REF]] and/or in Calypso compared with the accession Gros Michel we have used. A triploid plantain was also previously shown to have transmitted a recombined 3x gamete (supplementary material in [START_REF] Baurens | Recombination and large structural variations shape interspecific edible bananas genomes[END_REF].

Unreduced gametes are generally more frequent in interspecific hybrids and in allopolyploids, and result in most cases from disturbed meiotic processes, although premeiotic and postmeiotic doubling have also been mentioned [START_REF] De Storme | Sexual polyploidization in plants -cytological mechanisms and molecular regulation[END_REF][START_REF] Mason | Unreduced gametes: meiotic mishap or evolutionary mechanism?[END_REF]. If the first division step of meiosis does not occur, meiosis is similar to mitosis and produces un-recombined unreduced gametes, retaining full parental heterozygosity [START_REF] De Storme | Sexual polyploidization in plants -cytological mechanisms and molecular regulation[END_REF]. Other disturbances during meiosis, such as cytological alterations during the second division step [e.g. parallel spindles (d'Erfurth et al., 2008)] or absence of the second division, can result in unreduced gametes with recombined chromosomes [START_REF] De Storme | Sexual polyploidization in plants -cytological mechanisms and molecular regulation[END_REF]. The inter(sub)specific origins of cultivated bananas often resulted in the presence of large chromosomal rearrangements at a heterozygous state in their genome (Martin et al., 2020a). This may disturb meiotic processes and/or lead to the production of non-viable, unbalanced 1x gametes that could favour the transmission of unreduced gametes. For example, in the case of Mchare, the presence of two independent heterozygous large reciprocal translocations (Martin et al., 2020a) will statistically generate 75 % of unbalanced gametes during meiosis, which should be non-viable. This phenomenon mathematically increases the proportion of 2x gametes in the pool of viable gametes.

Prospects for banana breeding

This study illustrated that different processes are involved in the formation of banana cultivars involving various types of gamete. They include recombined or un-recombined 2x gametes from diploids and various types of gametes, including 3x un-recombined gametes from triploids. These peculiar gametes must be rare and thus are potentially selected to conserve particularly favourable hybrid genomic combinations that required several generations to be obtained.

In this context, pre-breeding strategies that aim at maintaining such favourable genomic combinations while introgressing desirable traits such as resistance could be favoured. For example, the important contribution of the Mchare subgroup to other cultivars, often through un-recombined 2x gametes, suggested that its genomic combination should be preserved as much as possible. High-throughput genotyping technologies may be used to select individuals with the targeted genomic combination. These strategies, like others, will be complicated by the poor fertility of bananas but conversely may be particularly useful in this context.

  ABB

Fig. 1 .

 1 Fig.1. Validation along chromosomes of predicted parents-child trios. Accession chromosome ancestry mosaics obtained from[START_REF] Martin | Interspecific introgression patterns reveal the origins of worldwide cultivated bananas in New Guinea[END_REF] and the local proportion of sites in discordance with tested trios are represented. Child pseudohaplotypes are represented on outer circles and are separated from tested parents' pseudohaplotypes (on inner circles) by the local proportion of alleles in discordance with the tested parentage (value between 0 and 1). Ploidy of the parental tested gamete is indicated between square brackets and the ploidy of the child is indicated between round brackets. Colour codes 'banksii', 'burmannica', 'zebrina', 'malaccensis', 'truncata', 'sumatrana' and 'halabanensis' stand for an origin from M. acuminata ssp. banksii/microcarpa/errans, burmannica, zebrina, malaccensis, truncata, sumatrana and halabanensis respectively. 'schizocarpa' and 'balbisiana' stand for M. schizocarpa and M. balbisiana respectively. 'M_2' is an uncharacterized contributor to banana and 'unknown' corresponds to regions in which no origin could be attributed. Panels (A, B and C) correspond to three tested trios whose names are indicated in each figure centre.

Fig. 2 .Fig. 3 .Fig. 4 :

 234 Fig. 2. Validation along chromosomes of predicted parent-child duos and transmitted gamete types. Accession chromosome ancestry mosaics obtained from Martin et al. (2023) and the local proportion of sites in discordance with tested duos and gamete types are represented. Child pseudohaplotypes are represented on outer circles and are separated from tested parent pseudohaplotypes (on inner circles) by the local proportion of alleles in discordance with tested parentage (value between 0 and 1). Depending on the duos tested, different type of parentage could be tested: a haploid gamete restitution (1x), a diploid gamete restitution (2x), a diploid gamete with complete genome restitution (2x c ) or a triploid gamete with complete genome restitution (3x c ). Ploidy of the parental tested gamete is indicated between square brackets and the ploidy of the child is indicated between round brackets. Colour codes are identical to those in Fig. 1. Panels (A-D) correspond to four tested duos whose names are indicated in each figure centre.

Table 1 .

 1 Proposed banana parents-child trios and parent-child duos

  Downloaded from https://academic.oup.com/aob/article/131/7/1149/7189797 by CEA Saclay user on 22 December 2023

Downloaded from https://academic.oup.com/aob/article/131/7/1149/7189797 by CEA Saclay user on 22 December 2023

ACKNOWLEDGEMENTS

The authors thank the CRB Plantes Tropicales Antilles CIRAD-INRA Guadeloupe France and the Bioversity International Transit Centre (https://www.bioversityinternational.org/ banana-genebank/) for providing the original plant materials; Xavier Perrier for contributing DNA; Caroline Belser

FUNDING This work was supported by the France Génomique (ANR-10-INBS-09-08) project DYNAMO, the Centre de coopération Internationale en Recherche Agronomique pour le Développement (CIRAD) and the Agropolis Fondation (ID 1504-006) 'GenomeHarvest' project through the French Investissements d'Avenir program (Labex Agro: ANR-10-LABX-0001-01).

SUPPLEMENTARY DATA

Supplementary Data are available online at https://academic. oup.com/aob and consist of the following. Figure S1: flowchart and scripts used to perform parentage analyses. Figure S2: validation along chromosomes of predicted parents-child trios. Figure S3: validation along chromosomes of predicted parentchild duos and transmitted gamete types. Figure S4: Calypso Illumina reads coverage along chromosomes of DH-Pahang V4. Figure S5: analysis of Galeo contribution to cultivars. Figure S6: local proportions of SNP sites in discordance with AAB/ ABB tested parentage relationships. Table S1: accession information. Table S2: list of accessions used for global trio analysis and of accessions used for identification of M. balbisiana and Australimusa private allele sites for the Mchare analysis. Table S3: global parentage trio analysis: proportions of SNP sites in accordance with trios. Table S4: global parentage trio results for synthetic F 1 trios. Table S5: global analysis of Mchare contribution.