Pierre Peterlongo

Julien Allali

Sagot

Indexing gapped-factors using a tree

Keywords: suffix tree, k-factor tree, string index, gapped-factor, gapped-factor tree

We present a data structure to index a specific kind of factors, that is of substrings, called gapped-factors. A gapped-factor is a factor containing a gap that is ignored during the indexation. The data structure presented is based on the suffix tree and indexes all the gapped-factors of a text with a fixed size of gap, and only those. The construction of this data structure is done online in linear time and space. Such a data structure may play an important role in various pattern matching and motif inference problems, for instance in text filtration.

Introduction

The indexation and extraction of repeated short words (called k-factors a for words of length k) has become a widely used technique in many text algorithmic problems. One can mention their use in, for instance, fasta [START_REF] Lipman | Rapid and Sensitive Protein Similarity Searches[END_REF] and blast [START_REF] Altschul | Basic Local Alignment Search Tool[END_REF][START_REF] Altschul | Gapped BLAST and PSI-BLAST: a New Generation of Protein Database Search Programs[END_REF]. Indeed, many algorithms for efficiently computing string matches [START_REF] Gravano | Approximate String Joins in a Database (Almost) for Free[END_REF][START_REF] Navarro | Indexing Text with Approximate q-Grams[END_REF][START_REF] Sutinen | On Using q-Gram Locations in Approximate String Matching[END_REF] or alignments [START_REF] Brudno | LAGAN and Multi-LAGAN: Efficient Tools for Large-Scale Multiple Alignment of Genomic DNA[END_REF][START_REF] Brudno | Fast and Sensitive Multiple Alignment of Large Genomic Sequences[END_REF][START_REF] Edgar | MUSCLE: Multiple Sequence Alignment with High Accuracy and High Throughput[END_REF][START_REF] Höhl | Efficient Multiple Genome Alignment[END_REF][START_REF] Li | PatternHunter II: Highly Sensitive and Fast Homology Search[END_REF][START_REF] Ma | Patternhunter: Faster and More Sensitive Homology Search[END_REF][START_REF] Michael | Siteblast Rapid and Sensitive Local Alignment of Genomic Sequences Employing Motif Anchors[END_REF] use k-factors. In particular, filtration algorithms that have been created for quickly discarding large portions of the input before applying a more expensive algorithm on the remaining data are often based on the identification of such short repeated words [START_REF] Burkhardt | q-Gram Based Database Searching Using a Suffix Array (QUASAR)[END_REF][START_REF] Burkhardt | Better Filtering with Gapped q-Grams[END_REF][START_REF] Burkhardt | One-Gapped q-Gram Filters for Levenshtein Distance[END_REF][START_REF] Kucherov | Multiseed Lossless Filtration[END_REF][START_REF] Peterlongo | Lossless Filter for Finding Long Multiple Approximate Repetitions Using a New Data Structure, the Bi-factor Array[END_REF][START_REF] Pevzner | Multiple Filtration and Approximate Pattern Matching[END_REF][START_REF] Rasmussen | Efficient q-Gram Filters for Finding All -Matches Over a Given Length[END_REF].

Among the exact filtration algorithms (exact in the sense that they discard only portions of the text that can not be part of the final solution sought), some consider motifs composed of non consecutive letters [START_REF] Burkhardt | Better Filtering with Gapped q-Grams[END_REF][START_REF] Burkhardt | One-Gapped q-Gram Filters for Levenshtein Distance[END_REF][START_REF] Kucherov | Multiseed Lossless Filtration[END_REF][START_REF] Pevzner | Multiple Filtration and Approximate Pattern Matching[END_REF], or sets of kfactors [START_REF] Burkhardt | q-Gram Based Database Searching Using a Suffix Array (QUASAR)[END_REF][START_REF] Peterlongo | Lossless Filter for Finding Long Multiple Approximate Repetitions Using a New Data Structure, the Bi-factor Array[END_REF][START_REF] Rasmussen | Efficient q-Gram Filters for Finding All -Matches Over a Given Length[END_REF]. Both present advantages for filtering purposes in comparison with single k-factors with no letters skipped as shown in [START_REF] Burkhardt | Better Filtering with Gapped q-Grams[END_REF][START_REF] Kärkkäinen | Computing the Threshold for q-Gram Filters[END_REF][START_REF] Kucherov | Multiseed Lossless Filtration[END_REF].

In order to efficiently use such motifs, one needs data structures to index them. Depending on the kind of motifs adopted, different types of data structures may be considered. For instance, sets of k-factors may be indexed in a hash table or using a labelling technique as proposed in [START_REF] Iliopoulos | A First Approach to Finding Common Motifs With Gaps[END_REF]. In this paper, we introduce a data structure designed for the indexation of sub-words composed of a k-factor, a gap of length d not taken into account during the indexation and a k -factor. Such a sub-word is called a gapped-factor as it contains a unique gap.

The new data structure is an adaptation of the suffix tree [START_REF] Mccreight | A Space-Economical Suffix Tree Construction Algorithm[END_REF]. More precisely, the construction we describe in this paper is an adaptation of the construction of a k-factor tree [START_REF] Allali | The at Most k-deep Factor Tree[END_REF], which itself is an extension of the Ukkonen construction of a suffix tree [START_REF] Ukkonen | On-line Construction of Suffix-Trees[END_REF]. A k-factor tree [START_REF] Allali | The at Most k-deep Factor Tree[END_REF] (also called truncated suffix tree [START_REF] Na | Truncated Suffix Trees and their Application to Data Compression[END_REF]) is a tree indexing all k-factors of a text.

As indicated in Section 5, the new data structure, called a gapped-factor tree, allows to extract in linear time all the repeated gapped-factors of a text or of a set of texts. Furthermore, it offers the possibility to obtain in time O(k + k ) the list of all the positions of a gapped-factor.

The paper is organised as follows. In Section 2, we provide the context and some definitions about text and trees. In Section 3, we formally introduce gapped-factors and the gapped-factor tree. In Section 4, we present the algorithm to construct a gapped-factor tree for indexing the gapped-factors of a text after recalling the Ukkonen construction of a suffix tree and the Allali construction of a k-factor tree. We end by indicating two basic uses of gapped-factor trees.

Preliminaries

A text, also called a string, is a sequence of zero or more symbols from an alphabet Σ. A text t of length n is denoted by t[0, n -1] = t 0 t 1 . . . t n-1 , where t i ∈ Σ for 0 ≤ i < n. The length of t is denoted by |t|. A string w is a factor of t if t = uwv for u, v ∈ Σ * ; in this case, the string w occurs at position |u| in the string t. A k-factor denotes a factor of length k. If t = uv for u, v ∈ Σ * then v is called a suffix of t. A suffix starting at position i in t is denoted by t i... .

A tree is a data structure composed of nodes connected together by edges. Except for a special node called the root, each node has exactly one father. Nodes with no children are called the leaves while all other nodes are called the internal nodes of the tree. An internal node having at least two children is called a branching node.

Edges may be labelled. For instance, in Figure 1, edges are labelled with letters from a given alphabet ({A, T }). The length of an edge is defined as the length of its label. We call the depth of a node N the sum of the lengths of the edges that need to be traversed from the root of the tree to reach N . By definition, the depth of the root is thus 0.

A A A A T T A A ¡ ¡ ¢ ¢ £ ¡£ £ ¡£ ¤ ¤ Internal nodes Leaves ¥ ¡¥ ¥ ¡¥ ¦ ¡¦ ¦ ¡¦ § ¡ § § ¡ § § ¡ § ¨¨© ¡© © ¡© ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ! ¡! ! ¡! " " root
Let N be a node of a tree, we denote by path(N ) the text corresponding to the concatenation of the letters from a given alphabet labelling the edges from the root to N .

For instance, if N 0 denotes the leftmost leaf of the tree presented in Figure 1, path(N 0 ) = AA.

The suffix trie of a text t is a tree with every edges labelled with exactly one elements of Σ. For each factor of t, there exists a node N such that path(N ) is equal to that factor. If t has an ending symbol (a symbol that does not belong to the alphabet Σ), all nodes N for which the path from the root spells a suffix of t are leaves. Figure 1 is an example of suffix trie for the word AT AA.

The implicit suffix tree of t is a tree with edges labelled by non-empty elements of Σ * . The suffix tree is a compressed version of the suffix trie. Each internal node N of the suffix trie that has only one child is deleted and its two adjacent edges are replaced by an edge that goes from the father of N to its child. The label of the new edge is equal to the concatenation of the label of the edge going from the father of N to N and of the label of the edge from N to its child. This tree is called implicit because not all suffixes of t lead to a leaf. The true suffix tree is obtained when a special ending symbol $ not in Σ is added at the end of t. A suffix tree indexes all the |t| suffixes of a text t.

Gapped-factor tree

A gapped-factor tree indexes gapped-factors that are defined as follows: Definition 1 (Gapped-factor) A gapped-factor is a concatenation of a factor of length k, a gap of length d and another factor of length k . A gapped-factor occurring at position i in a text t is t

[i, i + k -1].t[i + k + d, i + k + d + k -1]. Such a gapped-factor is called a (k-d-k )-gapped-factor.
An example of a (2-1-3)-gapped-factor is given in Figure 2.

We propose a new data structure, called a gapped-factor tree, to index all the (k-d-k )-gapped-factors of a text or of a set of texts. This is a modification of the suffix tree [START_REF] Mccreight | A Space-Economical Suffix Tree Construction Algorithm[END_REF] data structure. The gapped-factor tree takes into account the gap of length d of the gapped-factors it indexes. This means that the tree contains a region up to which the k-factors are indexed as in a classical suffix tree, while below this region the second factors (of length k ) of the (k-d-k )-gapped-factors starting with the same k-factor start from the same node. This region is called the invisible region.

An intuitive idea of such a data structure is given in Figure 3.

¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ £ £ £ £ ¤ ¤ ¤ ¤ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ § § § § § § § § § ¨¨¨¨¨¨¨¨© ¡© ¡© ¡© ¡© ¡© ¡© ¡© ¡© ¡© ¡© ¡© ¡© © ¡© ¡© ¡© ¡© ¡© ¡© ¡© ¡© ¡© ¡© ¡© ¡© ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ A T A C A C A A A C C A A C A d k k' A C A C A A C A C A k k'
Fig. 3. An intuitive view of a gapped-factor tree. Even if this is not the way the gapped-factor tree is constructed, a gapped-factor tree can be seen as a truncated suffix tree where a part has been removed, provoking merges in the lower part of the tree.

Definition 2 (Path in a Gapped

-Factor Tree) Let w be a (k-d-k )-gapped-factor starting at position i < |t| -k -d -k that is indexed in such a tree. Let N be the node at depth z ≤ k + k corresponding to this (k-d-k )-gapped-factor. Then: path(N ) = t[i, i + z -1] if z ≤ k t[i, i + k -1].t[i + k + d, i + d + z -1] otherwise (1)
An example of gapped-factor tree and of a path in such a tree is presented in Figure 4.

In the next section, we present the algorithm which performs the online construction of a gapped-suffix tree.

Construction

The algorithm for constructing a gapped-factor tree is an extension of the algorithm for constructing a k-factor tree [START_REF] Allali | The at Most k-deep Factor Tree[END_REF], which is itself an extension of the suffix tree construction algorithm due to Ukkonen [START_REF] Ukkonen | On-line Construction of Suffix-Trees[END_REF]. Therefore, in the following, we AGGAGAGAC AA 0 1 2 3 4 5 6 7 8 9 10

A 7 0 5 1 4 6 3 2 A A G A C G G A A A G A A A A A C G A A C G C A G G A Fig. 4.
Example of gapped-factor tree.

The input sequence is AGGAGAGACAA. The dashed lines correspond to the invisible region of the tree. In this case, the gapped factors indexed are (2-1-3)-gapped-factors. The information attached to the leaves corresponds to the starting positions of a gapped-factor in the text.

start by presenting the construction of a suffix tree, then the one of a k-factor tree, and finally we describe the construction of a gapped-factor tree.

Ukkonen construction of the suffix tree

To present the Ukkonen algorithm, we follow the description given in [START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology[END_REF]. This algorithm constructs a full suffix tree of a text t in O(|t|) time and space. An example of a suffix tree is given in the Figure 5. The algorithm is divided into |t| phases. The i th phase (for 0 ≤ i < |t|) consists in the insertion of all the i + 1 suffixes of t[0, i] into the tree. The naive approach divides each phase i into i+1 steps, one step j (0 ≤ j < i) consisting in the insertion of the suffix t[j, i] into the tree. This naive version of the construction algorithm is presented in Algorithm 1. Clearly this algorithm is in O(|t| 3 ).

A $ G G A $ G $ A G $ $ G A G $ G A G G A G
The Ukkonen algorithm uses three tricks in order to reduce the time complexity to O(|t|).

Algorithm 1 Naive suffix tree construction algorithm Require: A text t Ensure: The suffix tree ST (t) of t 1: for i from 0 to |t| -1 do 2:

for j from 0 to i do 3:

Add(ST (t),t[j, i])

4:
end for 5: end for Before we present those tricks, we describe the encoding of a suffix tree. The suffix tree created by this algorithm does not store the text: each node N contains a couple of integers (s, e) corresponding to the starting and ending positions of the factor in the text that led to the creation of the node itself. In the following, we denote by N s,e such a node. Thus, by definition, in the suffix tree of a text t, path(N s,e ) is equal to t[s, e].

The Ukkonen algorithm uses suffix links. If the path from the root to a node spells the word aw, with a ∈ Σ and w ∈ Σ * then the path from the root to the suffix link of this node spells the word w. More precisely, a suffix link is an oriented link between two branching nodes of a suffix tree. Given a node N s,e , its suffix link is denoted by S l (N s,e ) and the node pointed by S l (N s,e ) is denoted by S n (N s,e ). In this case, path (S n (N s,e )) = path(N s,e ) 1, |path(N s,e )| . For instance, if path(N s,e ) = AGGT , then, path(S n (N s,e )) = GGT .

In Figure 5, the suffix links are represented by dashed lines. We present the three ideas leading to a linear time complexity for constructing a suffix tree for the text t.

1. Let us assume that the suffix tree is constructed for t[0, i -1]. During the i th phase, all the leaves labels have to be lengthened by one in order to take the character t i into account. In other terms, the ending integer e of each leaf has to be incremented by one. Since by definition, all leaves have the same ending integer, the latter can be coded by a global variable that is incremented by one at each phase of the Ukkonen algorithm. This global variable is equal to i during phase i. Thus, the extension of the leaves is implicit and done in constant time.

2. (a) Fast Insertion: during the i th phase, let N s,e be the last branching node reached during the insertion of t[j, i]. By construction this node contains a suffix link. In this case, t[j, i] = path(N s,e ).w.σ where w ∈ Σ * and σ ∈ Σ. In order to insert t[j + 1, i], w (which is necessarily already in the tree) is read from S n (N s,e ) and σ is added if needed.

To avoid having to read all the letters of w from S n (N s,e ), the following trick is used. At each branching node met during the reading of w, an edge is chosen depending on the current letter in w. Once the edge is identified, the node pointed by this edge is reached and we advance in the reading of w by the number of letters in the edge. The process is repeated while w is not totally read. Thus the complexity of the reading of w is related to the number of nodes traversed and not to |w|.

If σ is added, a branching node is created. The suffix link of such a node points to the last branching node met during the next insertion (it can be a created one).

The pseudo-code of this algorithm is given in appendix in Algorithm 2.

(b) During phase i, all the suffixes of t[0, i] have to be inserted. Yet if during the insertion of t[j, i], this word is already in the tree, then, by definition, all the words {t[k, i], k ∈ [j, i]} are already in the tree as well. In this case, the i th phase stops here. Similarly, the (i + 1) th phase can start inserting t[j, i + 1]: with the implicit extension of the leaves, the factors {t[k, i + 1], k ∈ [1, j -1]} are already in the tree.

A pseudo-code of this construction algorithm is given in appendix in Algorithm 3.

Each phase of the algorithm is not done in constant time. However the amortised construction time is linear with respect to the input text length. The demonstration of this complexity is given in [START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology[END_REF]. It consists in bounding the overall number of nodes traversed during all insertions.

Construction algorithm of a k-factor tree

The k-factor tree, also called truncated suffix tree, has been presented in [START_REF] Na | Truncated Suffix Trees and their Application to Data Compression[END_REF] and [START_REF] Allali | The at Most k-deep Factor Tree[END_REF]. A k-factor tree is a suffix tree cut such that each word spelt from the root to a leaf has a length bounded by k. An example of k-factor tree is given in Figure 6. This structure finds applications in various areas such as data compression [START_REF] Na | Truncated Suffix Trees and their Application to Data Compression[END_REF][START_REF] Na | Data Compression with Truncated Suffix Trees[END_REF] where the indexation is made over a sliding window, or string matching and computational biology [START_REF] Marsan | Extracting Structured Motifs Using a Suffix Tree -Algorithms and Application to Promoter Consensus Identification[END_REF][START_REF] Pisanti | RISOTTO: Fast Extraction of Motifs with Mismatches[END_REF][START_REF] Thbault | Combining Constraint Processing and Pattern Matching to Describe and Locate Structured Motifs in Genomic Sequences[END_REF] where the length of the motifs searched for in the text is bounded.

The linear time construction algorithm we describe here is based on the Ukkonen suffix tree construction algorithm. For further details on implementation and proof of validity, the reader is referred to [START_REF] Allali | The at Most k-deep Factor Tree[END_REF].

This algorithm is divided in two parts:

1. Build the suffix tree for t[0, k -2].

Add in |t| -

k + 1 phases the suffixes of t[i -k + 1, i] for i from k -1 to |t| -1.
The first part is achieved using the Ukkonen algorithm. During this part, the leaves created are added to a queue called queue eaf .

In the second part, we have to modify the Ukkonen algorithm so that:

• for each phase i, we start by inserting t[j, i] with j not smaller than ik + 1;

• implicit leaf extensions are stopped when the length k is reached for the path of a leaf.

To do this last point, we use the queue queue eaf .

During the whole construction, each leaf created is added at the end of queue eaf . Let L s,e denote a leaf corresponding to a string starting position s and ending position e. Suppose queue eaf = L 1 s 1 ,e , L 2 s 2 ,e , . . . , L p s p ,e is not empty. The variable e is a global variable applied to all the leaves present in queue eaf . During each phase, if the queue eaf is not empty, we remove its first element say L 1 s 1 ,e and transform it to L 1 s 1 ,i . if we are in phase i. After this, L 1 s 1 ,i is not modified. Indeed, we know that path(L 1 s 1 ,i ) has a length of k. Suppose we are in phase i = k -1. Then queue eaf contains at least one leaf which corresponds to the one created during the insertion of t[0] in the tree (first insertion of the first phase). This leaf is L 1 0,e . In phase i = k, the leaf is now L 1 0,k-1 , so the length of the path leading to it is equal to k. If there is another leaf in the queue, it corresponds to L 1 1,e and it is clear that the length of its path will be equal to k at the next phase. And so on, as the leaves L s,e are created with s incremented by one between two leaves.

Once the leaf at the beginning of queue eaf is fixed, we apply again the Ukkonen algorithm from the last leaf in queue eaf (the last created which can be the one we have just fixed). At the end of phase (i.e. no leaf created during the last insertion), we remove the leaf at the head of queue eaf .

We describe now the case when there is no leaf in the queue. Suppose there were a leaf in the queue at the previous phase i -1. By fixing the end value of this leaf, we have fixed the leaf corresponding to t[ik, i -1]. Then we started by inserting t[ik + 1, i -1] in the tree. This insertion did not create a leaf (queue eaf is empty in phase i) and lead to a position p in the tree that corresponds to the spelling of t[ik + 1, i -1]. In the current phase i, since queue eaf is empty, we have to start by inserting t[ik + 1, i] in the tree. This can be done in constant time by trying to insert t[i] from the position p. If this insertion creates a leaf, its end value is directly set to i (not added in queue eaf ) and it is used to try to insert

t[i -k + 1, i].
If no leaf is created, then we continue by trying to insert t[ik + 1, i] from the leaf reached (we know that the insertion of t[ik, i] leads to a leaf since the path length of the leaves is bounded by k). If the insertion of t[ik + 1, i] does not create a leaf, we use the position reached in the tree to start the next phase.

A pseudo-code of this algorithm is given in appendix in Algorithm 3.

The time and space complexities of the algorithm are linear in the size of the input text (see [START_REF] Allali | The at Most k-deep Factor Tree[END_REF] for details).

A G G A G A $ G G A $ G A $ G G k=3 Fig. 6.
Example of a k-factor tree for the text AGGAG$ with k = 3.

Gapped-factor tree construction

We now present the construction algorithm of a gapped-factor tree (gft for short). Once again, the construction algorithm is done online. As shown in Figure 4, a gft is composed of three different regions: the upper part of depth k, the invisible region corresponding to the gap of length d, and the lower part of depth k :

1. During the construction of the gft, the first region is treated exactly as for a k-factor tree. The queue containing the leaves in extension is denoted by queue leaf up .

2. When a leaf reaches the depth k, it enters in the invisible region for d phases.

To simulate this behaviour, a queue is created that contains the leaves in extension in the invisible region. This queue is denoted by queue invisible . Leaves entering queue invisible stay inside for d phases. During those phases, leaves inside the queue are ignored. After d phases, a leaf in the queue is virtually reaching the depth k + d. It is then removed from the queue.

3. The construction algorithm of the lower part of the tree is again very similar to the one of a k-factor tree. All the tricks applied for the suffix tree construction are still available. Once more a queue is used to store the leaves in extension in the lower part of the tree. This queue is denoted by queue leaf low . The ending integer of the leaves in extension in the queue is the global variable i.

The leaves stay in the queue during k phases before they become leaves that stay fixed, and contain the positions of the gapped-factors corresponding to the path leading to them from the root.

However, for the construction of the lower part, the use made of suffix links is slightly different than in the upper part of the tree. This is due to the following particularity of the gapped-factor tree: a node in the lower part of the tree may have up to |Σ| suffix links. Indeed, one node in this tree may correspond to several paths. According to the first letter in the invisible region leading to a node, the suffix link to follow will not be the same. Figure 7 illustrates this observation.

The algorithm 7 given in appendix gives an overview of the whole gapped-factor tree construction algorithm.

Complexity of the Gft construction

The algorithm for constructing a gft uses all the tricks employed by Ukkonen and Allali to lead to a linear time and memory complexity. One could at first glance consider that the multiple suffix links add a multiplicative term in |Σ| to both complexities. However one may observe that if more than one suffix link leaves a node N in the lower part of the tree, it means that in a classical suffix tree, N would have existed instead of one node. Thus,multiple suffix links do not involve extra memory and extra time consumption with respect to an usual suffix tree. Thereby the gapped-factor tree construction is done in linear time and memory complexity. The node pointed by an arrow has two suffix links (in dotted line). One is labelled with an A and the other is labelled with a B. The correct suffix link to follow depends on the path that leads to the node. If the node is reached reading ABA.w (w ∈ Σ * ), the correct suffix link to follow is the one labelled with an A; it goes to a node reachable reading the text BA.w. Any other suffix link leaving the node would be labelled differently and would reach a node corresponding to the text B.σ.w, with σ ∈ Σ and σ = A.

¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¢ ¡¢

Generalisation to more than one text

As for the suffix tree or the k-factor tree, the gft can be extended to a generalised gapped-factor tree and accept a set of m > 1 texts t 0 , t 1 , . . . , t m-1 .

In this case, each text i ∈ [0, m -1] ends with a special character $ i and the leaves are labelled not only with the positions of a gapped-factor but also with the sequence number in [0, m -1] where the factors occur. The complexity for constructing a generalised gapped-factor tree is in O m-1 i=0 |t i | .

Basic uses of a gapped-factor tree

To find all the positions where a (k-d-k )-gapped-factor occurs in a text given a (k-d-k )-gapped-factor tree for the text one needs to find the leaf corresponding to the given gapped-factor. This is done straightforwardly by traversing the gappedfactor tree from the root to the node as in a suffix tree. The list attached to the leaf corresponds to the positions of the occurrences of the gapped-factors.

This algorithm takes a time proportional to the number of nodes traversed, which is in the worst case k + k . Thus retrieving the positions of a given (k-d-k )gapped-factor is done in O(k + k ).

The gft data structure allows also to easily find all the repeated gapped-factors of a text or of a set of texts. If we are interested in finding all gapped-factors occurring at least r times in a text, for r a positive integer, we just have to visit the leaves. For each leaf, if the number of elements of the list attached to it is greater or equal to r, the corresponding gapped-factor is considered as repeated.

As the number of elements of each list may be stored in the leaves, this extraction is done in time proportional to the number of leaves. If n denotes the length of the indexed text, the number of leaves is no greater than n. The extraction is therefore done in time O(n).

In the generalised case, one may want to extract all gapped-factors occurring in at least r different texts. In this case, to each leaf is attached the number of different texts in which the corresponding gapped-factor occurs. Thus extracting all gapped-factors occurring in at least r different texts is done by checking each leaf in constant time leading to a complexity in O( m i=1 |t i |).

Conclusion

We presented a new data structure useful for indexing factors containing a gap (called the gapped-factors). This data structure is based on the suffix tree structure. Furthermore, we indicated an online construction algorithm of this data structure for a text in linear time and space. This algorithm is based on the Ukkonen algorithm for constructing a suffix tree.

Algorithm 3 Function Phase (Suffix tree and k-factor tree construction) Require: R, t, i, queue leaf , lastLeaf Ensure: One phase of the construction of the suffix tree and of the k-factor tree.

The underlined parts stand only for the k-factor tree construction. AddString(R,t,if orward + 1,i) Phase (R, t , k, i, queue leaf , lastLeaf ) 15:

remove the leaf at the head of queue leaf and set its end value to i 16: end for 17: return R Algorithm 5 Suffix Tree Require: t Ensure: The suffix tree of t 1: Add to R a leaf L with edge label t 0 2: lastLeaf ← L 3: for i from 1 to |t| -1 do

4:

Phase (R, t , k, i, lastLeaf ) 5: end for 6: return R

Fig. 1 .

 1 Fig. 1. Example of a suffix trie for the word AT AA.

Fig. 2 .

 2 Fig.2. Example of a (2-1-3)-gapped-factor The first factor length is k = 2, the gap is of length d = 1 and the second factor has a length k = 3. It occurs at position 1 in the text. With these parameters, the content of the gapped-factor occurring at position 1 is GGGAG composed by GG and GAG.

Fig. 5 .

 5 Fig. 5. Example of a suffix tree for the text AGGAG$. The dashed lines represent the suffix links.

Fig. 7 .

 7 Fig.7. Example of multiple suffix links. The node pointed by an arrow has two suffix links (in dotted line). One is labelled with an A and the other is labelled with a B. The correct suffix link to follow depends on the path that leads to the node. If the node is reached reading ABA.w (w ∈ Σ * ), the correct suffix link to follow is the one labelled with an A; it goes to a node reachable reading the text BA.w. Any other suffix link leaving the node would be labelled differently and would reach a node corresponding to the text B.σ.w, with σ ∈ Σ and σ = A.

1 : 4 :

 14 endP hase ← f alse 2: repeat 3: f orward ← length(F ather(lastLeaf ), lastLeaf ) -1 if S l (F ather(lastLeaf )) is undefined and F ather(lastLeaf )! = R then 5: f orward ← 6: f orward + length(F ather(F ather(lastLeaf )), F ather(lastLeaf )) 7:if F ather(F ather(lastLeaf )) is R then 8:

4 :

 4 set lastLeaf to the leaf at the end of queue leaf 5:

else 6 :

 6 add t i from last position reached during the last insertion 7: if a leaf is created then 8: add this leaf at the end of queue leaf 9:set lastLeaf to this leaf 10:

  ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢

  Algorithm 4 Factor Tree Require: R, t , k , queue leaf Ensure: The k-factor tree of t 1: do the first k -1 phases using Suffix Tree algorithm, filling queue leaf with each new leaf created 2: for i from k to |t| do 3:if queue leaf is not empty then

	9:	else
	10:

* Supported by the ACI Nouvelles Interfaces des Mathématiques π-vert project of the French Ministry of Research, the ARC BIN project from the INRIA, and the ANR project REGLIS.

a Another currently used term for designing k-factors is q-grams

Appendix A: Pseudo-codes

In the following codes, the function length(N , M) stands for the length of the word spelled by going from node N to the node M.

Algorithm 2 Fast Insertion

Require: N ,t,start,end Ensure: Insert a string t start...end from a node N assuming that the tree is already constructed for t start...end-1 from N 1: endJump ← f alse 2: while (not endJump) and ((endstart) = 0) do AddString(S l (F ather(lastLeaf )),t,if orward,i) f orward+length(F ather(F ather(lastLeaf Low)), F ather(lastLeaf Low))

10:

if F ather(F ather(lastLeaf Low)) is R then

AddString(R,t,if orward + 1,i)

12:

else 13:

AddString(S l (t α , F (F (lastLeaf Low)))t,if orward,i) AddString(R,t,if orward + 1,i) add the new leaf at the end of queue leaf low 6:

remove the node at head of queue invisible 7:

if queue leaf up is not empty then Phase(R, t, k, i, queue leaf up , lastLeaf U p) 20:

remove the pseudo leaf at the head of queue leaf up

21:

if the pseudo leaf is new then if i > k + d //the lower part of the tree is on construction then 26:

if queue leaf low is not empty then end if 43: end for 44: return R


Ludovic Cauvin

Balaji Raghavan

Salima Bouvier

Xiaodong Wang

Fodil Meraghni

Multi-scale investigation of highly anisotropic zinc alloys using crystal plasticity and inverse analysis

A C T Zinc and its alloys are important industrial materials due to their high corrosion resistance, low cost and good ductility. However, the characterization of these materials remains a difficult task due to their highly anisotropic behavior, the latter being due to the influence of microstructural effects, i.e. loading orientation-dependent activation of different families of slip systems and subsequent texture evolution, rendering the development of a reliable material model considerably difficult. A micro-mechanical approach based on polycrystal plasticity would better describe the physical mechanisms underlying the macroscopic behavior. This improved model should ostensibly improve the comprehension of the mechanical behavior, compared to the macroscopic approach using solely phenomenological anisotropy models along with a prohibitively large number of experiments required to identify the material parameters. In this paper, a multi-scale Visco-Plastic Self-Consistent (VPSC) approach is used. It is based on a micro-scale model calibrated by microstructural and deformation mechanism information based on Electron Back-Scattered Diffraction (EBSD) to describe the macroscopic anisotropic mechanical response during sheet metal deformation. The critical resolved shear stress (CRSS) as well as the micro-scale crystal parameters are obtained by an inverse analysis comparing the simulated and experimental results in terms of obtained tensile curves along three different directions. In order to obtain a global solution for the identification, we then use the Covariance Matrix Adaptation-Evolution Strategy (CMA-ES) genetic algorithm to the inverse problem. We validate our approach by comparing the simulated and experimental textures and activated slip systems. Finally, the identified mechanical parameters are used to investigate the anisotropy of the alloy and predict its formability by determining the corresponding R-values and Hill yield coefficients.

Introduction

Zinc and zinc-based alloys are valuable engineering materials whose industrial consumption ranks a close third behind those of Al and Cu among non-ferrous metals. Rolled sheets made from zinc alloys present a plethora of advantages including good aesthetic quality i.e. excellent visual appearance, long life with minimal maintenance needed, reduced cost, high adaptability and high creep resistance (for Zn-Cu-Ti alloys in particular), all of which enable their widespread use in construction for the fabrication of roofing products, cladding, flashings, rainwater down-pipes disposal applications, as well as in more innovative architectural designs [START_REF] Parisot | Modeling the mechanical behavior of a multicrystalline zinc coating on a hot-dip galvanized steel sheet[END_REF].

The main defects of deformed parts during sheet metal forming processes on zinc alloys include: crack, wrinkle, springback and surface deflections. Appropriate mechanical models and simulation tools capable of predicting the formability of rolled Zn sheets are needed to realize their full potential as engineering materials. Mechanical characterization typically involves the use of a variety of mechanical tests such as uniaxial and biaxial tensile tests (for ductile materials such as metals and alloys), different compression tests (for brittle and quasibrittle materials such as concrete) and relatively recent quasi-nondestructive tests such as instrumented indentation [START_REF] Meng | Identification of material properties using indentation test and shape manifold learning approach[END_REF][START_REF] Meng | An objective meta-modeling approach for indentation-based material characterization[END_REF], with the ultimate aim of determining its macroscopic mechanical plastic behavior: (e.g. yield surface, strain hardening, Lankford coefficients). Numerical simulation is widely adopted to complement, and in some cases replace, experimental tests and error methods in order to reduce the time and cost of development.

For several decades, material behavior has been described using phenomenological constitutive relations in the general framework of the theory of elasto-visco-plasticity. This approach, albeit useful for T simulating boundary value problems in a realistic manner with the help of finite element methods, has potential limitations for very anisotropic materials. These could be improved upon by taking into account the fundamental mechanisms involved during mechanical deformation.

Much of the literature on characterizing rolled sheets of Zn-based alloys is related to studying their corrosion resistance [START_REF] Slunder | Zinc: its corrosion resistance[END_REF][START_REF] Van Den Bos | Influence of alloying elements on the corrosion resistance of rolled zinc sheet[END_REF] since these materials are frequently used in chemically aggressive environments. However, in most of these studies, the evolution of mechanical behavior has rarely been examined, with the exception of analyzing the hardness evolution [START_REF] Senna | Hardness analysis and morphological characterization of copper-zinc alloys produced in pyrophosphate-based electrolytes[END_REF].

Zinc is in fact a highly anisotropic material that is very difficult to properly characterize due to the effect of its microstructure and initial crystallographic texture. At the micro-scale level, metal plasticity involves the nucleation and migration of dislocations in the crystals and polycrystals as the underlying basis for microstructure evolution during plastic flow. As the individual crystals have different sizes and orientations, i.e., the crystallographic texture, the anisotropy of the mechanical properties of a polycrystal is a direct consequence of the anisotropy of the properties of each grain and of this crystallographic texture. Moreover, the reorientation of the grains during mechanical deformation of the polycrystal results in texture changes.

Another factor that makes zinc difficult to characterize is its hexagonal structure. Indeed, in general Hexagonal Close Packed (HCP) materials can be deformed by two different mechanisms: slip and twinning. Slip in the crystallographic planes is the principal mechanism, which is activated when the resolved shear stress reaches a critical value. This critical value is lower along close-packed planes due to the higher atomic density, and therefore slip along these planes is the preferential way to accommodate plastic deformation. The second mechanism, twinning, is also activated particularly at higher loads, along several directions of the crystal, and with a separate critical stress value. Twinning leads to a discrete rotation of the c-axis within the twinned volume, by an angle depending on the type of the activated twin system. Several twin families have been identified in HCP materials: (1 0-1 2), (1 0-1 -3), (1 0-1 1), (1 1-2 -4), (1 1-2 2), (1 1-2 1), with the activated twin mode(s) depending on the c a / of the material. Surprisingly few studies, if any, are devoted to the mechanical characterization and to the study of the anisotropic behavior of this class of materials as a function of the initial microstructure, despite the continuing widespread use of these materials. In his paper on ductility in polycrystalline metals [START_REF] Mises | Mechanik der plastischen formanderung von kristallen[END_REF], von Mises was the first to note that five independent slip systems were required to accommodate the strain requirements associated with an arbitrary homogenous plastic deformation. Metal plasticity would require a (nearly) traceless deformation rate tensor with only 5 independent components (i.e. unknowns), needing a system of 5 independent deformation mechanisms (equations). While this criterion is directly applicable to Face-Centered Cubic (FCC) and Body-Centered Cubic (BCC) materials, the fundamentals of the yielding and work hardening response for hexagonal metals are significantly more complex, mainly because the hexagonal lattice does not provide a sufficient number of geometrically equivalent slip systems to satisfy the Von Mises criterion for polycrystal deformation, which is very different from what is seen in the case of FCC and BCC lattices. Meanwhile, to accomplish the deformation, more than one crystallographic slip mode and/or twin mode must be activated. The exact deformation mechanisms in Hexagonal Close Packed (HCP) metals, dislocation motion on specific slip systems and activation of twinning, are not yet completely understood. The discussion in the previous paragraph basically implies that Zinc, as an HCP material, shows markedly anisotropic mechanical properties that depend on its initial textures, deformation mechanisms and critical shear stresses which, in turn, are different for different slip systems as well as the direction of the applied stress (e.g. asymmetry of twin activation) during mechanical loading. There are four possible slip systems, basal, prismatic and pyramidal < > a and pyramidal < + > c a . In general, zinc exhibits de- formation on several crystallographic slip and twin systems, with very different activation stresses for each system. The relative contributions of individual slip and twin modes strongly depend on temperature, loading conditions, alloying elements, crystallographic texture, and microstructure evolution. This is the main reason for zinc's anisotropic behavior. The differing volume fractions of twins during tensile and compressive loading leads to the alloy's tension-compression asymmetry. Nevertheless it can be noticed that basal and pyramidal < + > c a are more likely to be activated in tensile test [START_REF] Bell | The dynamics of twinning and the interrelation of slip and twinning in zinc crystals[END_REF].

Furthermore, zinc and its alloys are typical metals with HCP lattice structure with a c a / of 1.856, i.e. higher than that of an ideal structure ( = c a / 1.632) and this leads to a higher than usual property dependence on the slip and twinning systems [START_REF] Christian | Deformation twinning[END_REF].

Currently, there is a dearth of systematic studies where crystallographic texture and grain anisotropy have been examined over a wide range of conditions. Knowledge of the active deformation mechanisms and the variation in their relative contribution as a function of these variables is required for accurately predicting the plastic response and texture evolution of zinc and its alloys. This is particularly important for the development of reliable material models for use in simulating forming processes with these materials, especially given the increase in applications of this class of materials.

The existing literature on mechanical modeling of the anisotropy of zinc alloys is, as expected, based on micro-mechanical approaches [START_REF] Philippe | Modelling of texture evolution for materials of hexagonal symmetry-i. application to zinc alloys[END_REF][START_REF] Zhang | Experimental and simulation textures in an asymmetrically rolled zinc alloy sheet[END_REF]. Micro-mechanical modeling provides a link between the microstructure of a material and its mechanical behavior, allowing us to quantify plastic deformation at the microstructural level. This approach is thus well-suited for simulations involving material texture and related anisotropy. A considerable amount of simulation has been performed using "physically based" models rather than simply fitting phenomenological behavior laws in the literature [START_REF] Philippe | Modelling of texture evolution for materials of hexagonal symmetry-i. application to zinc alloys[END_REF][START_REF] Zhang | Experimental and simulation textures in an asymmetrically rolled zinc alloy sheet[END_REF][START_REF] Bouvier | Effect of the number and orientation of active slip systems on plane strain single crystal indentation[END_REF][START_REF] Yoshida | Effect of regularization of schmid law on self-consistent estimates for rate-independent plasticity of polycrystals[END_REF][START_REF] Nixon | Anisotropic response of high-purity α-titanium: experimental characterization and constitutive modeling[END_REF][START_REF] Panicaud | Theoretical modelling of ductile damage in duplex stainless steelscomparison between two micro-mechanical elasto-plastic approaches[END_REF][START_REF] Yoshida | Micromechanical modeling of the work-hardening behavior of single-and dual-phase steels under two-stage loading paths[END_REF][START_REF] Bouvier | Hardening in relation with microstructure evolution of high purity α-titanium deformed under monotonic and cyclic simple shear loadings at room temperature[END_REF][START_REF] Benmhenni | Micromechanical modelling of monotonic loading of {CP} α-ti: Correlation between macroscopic and microscopic behaviour[END_REF][START_REF] Gelineau | Elastic properties prediction of nano-clay reinforced polymer using multi-scale modeling based on a multi-scale characterization[END_REF][START_REF] Chatziathanasiou | Phase transformation of anisotropic shape memory alloys: theory and validation in superelasticity[END_REF].

Zinc based alloys typically involve several deformation modes, including slip and twinning systems. These systems have different and unknown activation stresses that depend, usually in a non-unique manner, on the experimental approach used to study the texture as well as on the type of micro-mechanical model. We therefore need an accurate model to simulate its deformation under loading, including the large deformations typically encountered during forming processes. This model needs to be capable of not just describing the mechanical response of the material for a given texture, but also predicting how this texture would evolve with deformation.

Wang et al [START_REF] Wang | Evaluation of self-consistent polycrystal plasticity models for magnesium alloy az31b sheet[END_REF] compared the predictive capability of different polycrystal plasticity models using the predicted and experimental stress responses, observing that: 1. Self-consistent models with grain interaction stiffness halfway between the limiting Secant (stiff) and Tangent (compliant) approximations gave the best results. 2. The affine auto-coherent models using a self-consistent scheme yielded the best overall performance [START_REF] Herve | n-layered inclusion-based micromechanical modelling[END_REF][START_REF] Masson | An affine formulation for the prediction of the effective properties of nonlinear composites and polycrystals[END_REF].

As a result, they concluded that Secant and Tangent approximations were inappropriate for highly anisotropic materials like HCP polycrystals. Given that Zinc alloys are hexagonal polycrystals, and in light of the available evidence, we adopt the Visco-Plastic Self-Consistent (VPSC) approach developed by Lebensohn and others [START_REF] Lebensohn | A self-consistent anisotropic approach for the simulation of plastic deformation and texture development of polycrystals: application to zirconium alloys[END_REF][START_REF] Lebensohn | A self-consistent viscoplastic model: prediction of rolling textures of anisotropic polycrystals[END_REF][START_REF] Lebensohn | Measurement and prediction of texture development during a rolling sequence of zircaloy-4 tubes[END_REF][START_REF] Lebensohn | Computational Methods for Microstructure-Property Relationships[END_REF] which does not enforce either stress or strain equilibrium on the individual grains (unlike the Sachs and Taylor models) and is more appropriate for hexagonal materials [START_REF] Lebensohn | Computational Methods for Microstructure-Property Relationships[END_REF]. The present paper is a contribution towards the development of a complete protocol for the characterization of Zn alloys by clarifying the physical mechanisms involved in the plastic deformation of rolled Zn-Cu-Ti sheets. The experimental portion of this work involves tensile testing of a Zn-Cu-Ti sheet along three directions to study its macroscopic mechanical behavior, and Electron Beam Scatter Diffraction (EBSD) to examine the microstructure i.e. texture evolution. The texture evolution is studied so as to shed some light on the fundamental mechanisms responsible for the plastic deformation, crystallographic slip or mechanical twinning, which is a pre-requisite for the micro-scale model.

The Visco-Plastic Self-Consistent (VPSC) model is considered to estimate the multiscale behavior of the rolled Zn-Cu-Ti sheet, with the required material parameters such as the critical resolved shear stresses for the different slip and twin systems identified using an inverse analysis by comparing the stress-strain curves from uniaxial tensile testing along three different orientations (0°/RD, 45°/RD and 90°/RD) along with the simulated macroscopic stress-strain curves along the same three directions.

The inverse problem is solved by optimization with the well-known Covariance Matrix Adaptation Evolution Strategy (CMA-ES) [START_REF] Hansen | Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (cma-es)[END_REF] evolutionary algorithm. Using the identified micro-scale parameters, we calculate the Lankford R-values followed by the Hill coefficients for the alloy by simulation. The simulated and experimental yield surfaces are compared. The identified microscale parameters are shown to correctly predict the texture evolution during tensile testing along the three directions. Finally, the simulated R-values are compared with those reported in the literature [START_REF] Bramley | Plastic anisotropy of titanium and zinc sheets[END_REF][START_REF] Fundenberger | Modelling and prediction of mechanical properties for materials with hexagonal symmetry (zinc, titanium and zirconium alloys)[END_REF].

In the following sections, we first present the material preparation, EBSD and other experimental techniques used followed by a description of the results obtained. Next we introduce the multi-scale modeling approach based on the VPSC paradigm. We then describe the solution procedure for the final inverse problem using the CMA-ES algorithm, followed by results obtained and a detailed discussion. The paper ends with concluding comments and recommendations for future work.

Materials and experimental techniques

In this section we describe the materials being characterized along with the main experimental tests used in this work.

Materials

We focus on commercial rolled sheets of Zn-Cu-Ti, purchased from Umicore. The desired mechanical properties of these rolled sheet materials are generally attained by alloying Zn with 0.1-0.2% copper and titanium [START_REF] Morgan | Zinc and Its Alloys and Compounds[END_REF], giving a Zn-Cu-Ti alloy. Up to approximately 1% of this copper addition is in the form of a solid solution in the Zn matrix and results in an increase in strength, hardness, and creep resistance.

On the other hand, due to the lower solubility of titanium (no more than 0.11% of Titanium in the alloy), titanium reacts with zinc and hard inter-metallic particles (stringers) of TiZn 15 are formed [START_REF] Mathewson | Zinc: the science and technology of the metal, its alloys and compounds[END_REF] (within the Cu-Zn solid solution) that are distributed parallel to the rolling direction. This inter-metallic phase decreases the grain size of the cast zinc, restrains the grain growth of the rolled zinc sheet at elevated temperatures. The reduction in grain size is because TiZn15 precipitates at grain boundaries, and so acts as a barrier to grain growth. Since the grain size is refined, the intermetallic phase volume fraction increases with Al increasing. The finer grain would create more grain boundaries, thus causing the alloy passivate more easily resulted in a reduced degradation rate. The smaller grain size enables a greater percentage of the surface to be covered with a protective Titania-Zn oxide film [START_REF] Fundenberger | Modelling and prediction of mechanical properties for materials with hexagonal symmetry (zinc, titanium and zirconium alloys)[END_REF][START_REF] Shuai | Biodegradation mechanisms of selective laser-melted mg-xal-zn alloy: grain size and intermetallic phase[END_REF][START_REF] Muster | The influence of microstructure on surface phenomena: rolled zinc[END_REF]. Such an inter-metallic phase expectedly affects the mechanical properties of the material (e.g. tensile strength, hardness). For example, the size and distribution of TiZn15 stringers (within the Cu-Zn solid solution) leads to substantial increase in creep resistance of the alloy [START_REF] Pantazopoulos | Analysis of a weld failure of a rolled zn-alloy strip -a case study[END_REF].

We use a natural Zinc-based alloy in this work, i.e. without any coating. This alloy is fully Hexagonal Close-Packed (HCP) at room temperature and has the chemical composition given in Table 1. The initial thickness of the rolled sheets is 0.65 mm.

Experimental techniques 2.2.1. Uniaxial tensile testing

A series of uniaxial tensile tests have been carried out for the zinc sheets, using testing specimens with a gage length of 30 mm and width of 10 mm each. These specimens were machined using a hyperbar water jet. The tests were performed on different specimens cut out from the materials at various orientations with respect to the rolling direction: 0°, 45°and 90°. The deformation was controlled by a high-resolution extensometer on a rather short measuring base. Each test was repeated 3 times and performed under quasi-static condition at strain rate of --10 s 3 1 .

Texture measurements by EBSD and SEM

Electron Back Scatter Diffraction (EBSD) is used to locally characterize the microstructures, such as the average grain size, the crystallographic grain orientation, the local misorientation, etc. The microstructure has been observed using a Field Emission Electron Gun, Scanning Electron Microscope (FEG-SEM) ZEISS ™ Sigma at 10 keV, with an integrated AMETEK-EDAX detector.

With an electron beam acceleration voltage of 25 kV and a working distance of 20 mm, the TSL OIM Data Collection ™ Software records the Kikuchi patterns generated by the inelastic scatter of electrons in the specimen tilted at 70°. For fine analysis, we assume an initial step size of 1/5th of the average grain diameter, and progressively reduce this for more detail.

Sample preparation has been performed by mechanical polishing in this work, using a VibroMet 2 Vibratory Polisher.

In the OIM scan, the number of points required to determine a "grain group" (the Minimum Grain Size) has been set according to the characteristics of the microstructure, while the value chosen for the Grain Tolerance Angle (between grains) is equal to 5°. Only coherent twins are considered satisfying the following two criteria:

1. The orientation of the twin related to the parent through specific misorientations, 2. The twinning plane must be aligned with the boundary plane separating the twin from the parent.

The parent grain is defined as the entity with the most points measured in a direction. The EBSD data was "cleaned up" to remove erroneous grains (e.g. with diameter less than 2 pixels) using statistical methods such as calculation of average grain size and grain boundaries rotation angle. Serial sectioning and other stereo-logical approaches were then applied to extract the complete boundary normal informations, in order to calculate both orientations as well as misorientations. To determine the activated slip systems, the Schmid factor (described in the Section 4) is calculated using OIM. We carry out a series of SEM observations on the material in "as-received" state as well as on samples deformed by uniaxial tension along different directions (0°, 45°, 90°) with respect to the rolling direction (RD).

In parallel, we use Digital Image Correlation techniques to confirm the rapid evolution of the strain field from uniform to very heterogenous.

Experimental results

The macroscopic strain-stress curves

Fig. 1 shows the strain-stress curves obtained using uni-axial tensile tests along the three directions. The material shows anisotropic behavior, as expected. The ductility decreases as the loading direction approaches the transverse direction (true stress over 200 MPa for barely over 20% plastic strain) with maximum ductility observed along the rolling direction (a true stress of barely 150 MPa for 50% strain). On the other hand, the strength is observed to increase as the loading direction approaches the transverse direction (TD). Therefore, three different loading orientations (0°/RD, 45°/RD and 90°/RD) are considered to examine the macroscale behavior. By comparing these three groups of stress-strain curves, as seen in the Fig. 1, we clearly observe the anisotropic behavior of the considered material.

The crystallographic texture evolution

The regions of observation are shown in Fig. 2. We also note here, from the aforementioned DIC, that the strain field in the specimen is indeed non-uniform.

By comparing the Schmid factor maps for loading along different directions, it is possible to understand the relative contributions of different slip systems to deformation under different loading conditions. Based on the loading conditions and the Euler angles of the grains (obtained by EBSD) the Schmid factors of the 4 theoretically possible slip planes in one grain of the hexagonal material have been calculated. The plane with the largest value of Schmid factor is considered to be the primary slip plane. As already mentioned, in general, basal and pyramidal < + > c a are more likely to be activated in a tensile test [START_REF] Bell | The dynamics of twinning and the interrelation of slip and twinning in zinc crystals[END_REF]. From the Figs. 3 to 5, we see that along the rolling direction, basal slip is the most important while along 45°/RD and 90°/RD, prismatic and pyramidal slips has respectively the higher possibility to be activated during the loading process rather than that of 0°/RD. And therefore, as already observed by [START_REF] Bell | The dynamics of twinning and the interrelation of slip and twinning in zinc crystals[END_REF] basal and pyramidal < + > c a slip systems will be considered in the material model.

As has been frequently mentioned in this paper, HCP materials exhibit deformation twinning to accommodate strains along the c axis. Also the measurement of the twinning fraction is troublesome, due to the difficulty of identifying totally reoriented grains as twins. The EBSD analysis shows a substantial contribution to deformation by twinning, therefore it is logical to fit twinning parameters.

In case of Zinc based materials, the system that is more likely to activate is the (1 0-1 2) system which causes contraction along the c axis. However, in our SEM, we consider two other possible twin systems (1 1-2 1) and (1 1-2 2) in order to additionally estimate the twin volume fraction of both in the "as received" (and later the deformed) material.

Fig. 6 shows the identification of the twin region for the selected twin families. As expected, the dominant twin system belongs to the (1 0-1 2) family with a surface fraction of about 16%, which is in good agreement with the result observed in the figure.

Keeping all these observations in mind, we decide to retain the deformation modes summarized in Table 2 for the micro-scale material model in the next section. This choice is in relative agreement with most of the published experimental works for similar materials (see Table 3)

Multi-scale constitutive modeling

During sheet metal forming involving very anisotropic metals, we are frequently unable to adequately describe the material's macroscopic behavior using a simple phenomenological model, and are forced to take the underlying physical mechanisms into account via a micromechanical model [START_REF] Herve | n-layered inclusion-based micromechanical modelling[END_REF]. This model accounts for the effect of the crystallographic texture and its evolution on the macroscopic response during mechanical loading and deformation.

Simple polycrystal models of the last century include the Sachs [49] and Taylor models [START_REF] Taylor | Plastic strain in metals[END_REF]. In our work, since elastic deformation as well as creep effects are negligible during metal forming, and so we adopt a visco-plastic model instead of elasto-plastic or viscoelastic models.

Lebensohn and Tome's Visco-Plastic Self-Consistent (VPSC) model [START_REF] Lebensohn | A self-consistent anisotropic approach for the simulation of plastic deformation and texture development of polycrystals: application to zirconium alloys[END_REF] is based on [START_REF] Molinari | A self consistent approach of the large deformation polycrystal viscoplasticity[END_REF], where the anisotropic behavior of the matrix was taken into account in a self-consistent scheme [START_REF] Kröner | Berechnung der elastischen konstanten des vielkristalls aus den konstanten des einkristalls[END_REF][START_REF] Hutchinson | Bounds and self-consistent estimates for creep of polycrystalline materials[END_REF], i.e. a grain (inclusion) is assumed to be embedded in a Homogenous Effective Medium (HEM) whose behavior is given by the mean mechanical properties of the surrounding polycrystalline aggregate. This model provides a more accurate description of reorientation by twinning using a Volume Fraction Transfer scheme [START_REF] Lebensohn | A self-consistent viscoplastic model: prediction of rolling textures of anisotropic polycrystals[END_REF][START_REF] Lebensohn | Measurement and prediction of texture development during a rolling sequence of zircaloy-4 tubes[END_REF], and is better adapted to texture prediction in hexagonal materials [START_REF] Lebensohn | Computational Methods for Microstructure-Property Relationships[END_REF].

In the present work, we adopt the affine formulation proposed by Masson et al. [START_REF] Masson | An affine formulation for the prediction of the effective properties of nonlinear composites and polycrystals[END_REF] (similar to the recommendation of Wang et al. [START_REF] Wang | Evaluation of self-consistent polycrystal plasticity models for magnesium alloy az31b sheet[END_REF]). The latter leads to predictions that are in-between the secant and the tangent approaches for high nonlinearity, and been successfully used to describe the behavior of hexagonal polycrystals [START_REF] Brenner | A quasi-elastic affine formulation for the homogenised behaviour of nonlinear viscoelastic polycrystals and composites[END_REF].

Microscale model

The α superscript in the following subsection represents a quantity measured or calculated for slip/twinning system α for a grain (crystal). From Schmid's law, the resolved shear stress τ α is related to the grain's deviatoric Cauchy stress ′ σ g :

= ⊗ + ⊗ ′ = ′ s m m s σ P σ τ 1 2 ( ) : : α α α α α g α g ( 1
)
where P α is the second order Schmid tensor derived from EBSD mea- surements, s α and m α the slip direction and slip plane normal.

For cold deformation, the rate sensitivity of the flow stress is low, so the shear stress and slip rate may be approximated by:

⎜ ⎟ = ⎛ ⎝ ⎞ ⎠ γ γ τ τ sgn τ ˙˙| | ( ) α α c α n α 0 (2)
where γ˙α is the shear strain rate, n is the strain rate sensitivity exponent, γ˙0 is a reference shear strain rate, and τ c α is the critical resolved shear stress (CRSS). The plastic strain rate ε˙p is given by considering that the velocity gradient tensor L p is the result of the accumulation of shear in all of the N s active slip and twinning systems of the crystal:

∑ = + = = ⊗ - = L D F F s m γ Ω ˙( ) ˙( ) p p p p p α N α α α 1 1 s (3)
As explained previously, we have chosen 2 active slip and 1 active twinning mode for the alloy studied. The strain rate used is - 10 3 s -1 , and the strain rate sensitivity exponent is 20.

Mesoscale and macroscale model

Here, we simulate the macro-scale behavior for comparison with the experimental results to identify the micro-scale parameters using inverse analysis. The strain hardening of the macroscopic material is controlled by the Voce hardening parameters giving the critical shear stress as a function of the accumulated deformation for each of the slip/ twinning systems, for each grain (crystal). To obtain the macroscopic behavior, the VPSC approach solves the equivalent inclusion Eshelby problem (single crystal) for an elliptical inclusion in an infinite matrix, and iteratively forcing the polycrystal i.e. composite stress and strain to coincide with the volumetric averages of the same over the grains, i.e., self-consistent homogenization, giving the macroscopic behavior of the material.

This gives concentration equations for the Cauchy stress tensor. Since the averaged stress tensor equals the macroscopic stress tensor, we obtain self-consistent equations for the aggregate moduli. The scheme reproduces the macroscopic deviatoric stress S ͠ and strain rate ∼ D p in the polycrystal from the grain equivalents ′ σ g and ε˙g vp for the current texture at each step using the interaction laws:

- = ′ - = - ∼ - D ε M σ S M I E E M n ˙. ( ) where ( ) ͠ vp g vp g eff 1 (8)
iteratively starting with the initial textures for the "as received" material. Morphology, texture and hardening are updated using an incremental implicit scheme at each step until convergence of the algorithm, at which point we obtain the uniaxial true stress-strain curves in the three different directions °°0 , 45 and °90 . The final stage, determining the optimal micro-scale parameter set that will lead the best agreement with the experimental data for the specimen, will be described in the next section.

Inverse analysis and parameter identification

The parameters required for calibrating the micro-scale model are the 4 parameters of the Voce hardening law (τ α 0 , τ α 1 , θ α 0 and θ α 1 ), for each of the deformation modes considered (i.e., = α 1 .. 3). These parameters need to be extracted using the experimental data obtained from the uniaxial tensile tests in the 3 different directions. This is accomplished by finding the set of micro-scale material parameters that produces the macro-scale tensile curves that are closest to the experimental tensile curves, using inverse analysis [START_REF] Meraghni | Parameters identification of fatigue damage model for short glass fiber reinforced polyamide (pa6-gf30) using digital image correlation[END_REF][START_REF] Meraghni | Parameter identification of a thermodynamic model for superelastic shape memory alloys using analytical calculation of the sensitivity matrix[END_REF][START_REF] Chemisky | Analysis of the deformation paths and thermomechanical parameter identification of a shape memory alloy using digital image correlation over heterogeneous tests[END_REF].

As has been explained in the previous sections, the 3 modes correspond to 2 slip deformation modes (Basal and Pyramidal < + > c a (also called π 2 )) and a single tensile twinning system, as given in Table 2. This gives a total of × = 3 4 12 total micro-scale parameters need to be identified in the inverse problem, τ τ θ θ τ τ θ θ τ τ θ , , , , , , , , , , and θ 1 3 , collected in a vector V , exponent 1, 2 and 3 corresponding respectively to basal, Pyramidal π 2 slip systems and tensile twinning system.

Tensile test simulation

Uniaxial tensile loading on a 0.65 mm natural zinc sheet along three different orientations has been simulated using the approach given in the previous section, with a combination of strain and stress boundary conditions.

Inverse problem

Let V opt represent the set of identified material parameters. The optimization problem is formally presented as follows:

S R S S = = - ⊂ ∈ ∈ + V Argmin J V Argmin σ V σ ( ) ( ) where opt V V int exp 12 (9)
where the objective function S R → J:

is based on the pointwise difference between the theoretical and the experimentally obtained curves of true stress versus true strain (

R ∈ σ ε , calc calc nc and R ∈ σ ε , exp exp
ne ) for uniaxial tensile loading along the 3 directions °°0 , 45 and °90 , and

= σ V σ ε V ( ) ( , ) ͠ int i exp i
is simply the vector of theoretical stress values

(0 0 0 1) (2 -1 -1 2) (1 0 -1 2) Slip direction < 2-1-1 0 > <-2 1 1 3 > <-1 0 1 1 > Table 3
Relative activity of different modes reported in the literature [START_REF] Edwards | Mstrain hardening of latent slip systems in zinc crystals[END_REF][START_REF] Adams | Impurity effects on basal dislocation in zinc single crystals[END_REF][START_REF] Bell | The dynamics of twinning and the interrelation of slip and twinning in zinc crystals[END_REF][START_REF] Adams | Second-order pyramidal slip in zinc single crystals[END_REF][START_REF] Bosin | Experimental and simulation textures in an asymmetrically skin-passed zinc galvanized sheet[END_REF][START_REF] Price | Nucleation and growth of twins in dislocation-free zinc crystals[END_REF][START_REF] Stofel | Fracture of zinc single crystals[END_REF][START_REF] Sztwiertnia | Interpretation of flow stress of textured zinc sheet[END_REF][START_REF] Wierzbanowski | Generalized computer program for texture simulation[END_REF][START_REF] Fundenberger | Modelling and prediction of mechanical properties for materials with hexagonal symmetry (zinc, titanium and zirconium alloys)[END_REF][START_REF] Diot | Texture gradient in rolled zinc sheets[END_REF][START_REF] Parisot | Modeling the mechanical behavior of a multicrystalline zinc coating on a hot-dip galvanized steel sheet[END_REF][START_REF] Delannay | Prediction of the planar anisotropy of springback after bending of a textured zinc sheet[END_REF][START_REF] Boczkal | Precipitation hardening of zn0.1 at.crystals deformed on the[END_REF][START_REF] Zhang | Experimental and simulation textures in an asymmetrically rolled zinc alloy sheet[END_REF][START_REF] Vincent | Experimental and simulation textures in an asymmetrically skin-passed zinc galvanized sheet[END_REF][START_REF] Philippe | Modelling of texture evolution for materials of hexagonal symmetry i. application to zinc alloys[END_REF]. interpolated at the experimentally obtained strain points ε exp obtained by Diffuse Approximation [START_REF] Nayroles | Generalizing the finite element method: Diffuse approximation and diffuse elements[END_REF] (since ≠ nc ne).

= σ ε V p ε a ε V ( , ) ( ) ( , ) ͠ exp i exp i T exp i ( 10
) where = - - … p ε ε ε ε ε ( ) [1, , ( ) ] exp i exp i T 2
is a vector of monomials and the vector a is determined using:

… = - σ ε ε ε ε σ P W P P W [ ( ), ] [ ( ) ( )] [ ( ) ]{ } ͠ exp i calc T calc calc T calc 1 (11)
and W is a diagonal matrix obtained with an appropriate weighting function w ε ( ) giving:

= - - … - diag w ε ε w ε ε w ε ε c W ( ( ), ( ) . ( )) exp exp n exp 1 2 (12)
The parameters are fitted in several stages, using different sets of data to fit different parameters, independently or simultaneously. The whole procedure can be seen in Fig. 7(a). As shown, at the very beginning we try to fit the strain-stress curves of three loading directions (0°/RD, 45°/ RD and 90°/RD) independently using the simplex algorithm to identify the parameters [START_REF] Lagarias | Convergence properties of the nelder-mead simplex method in low dimensions[END_REF], which means three groups of parameters are found. Afterward, the average of these three groups of parameters is adopted as the initial input parameters, and a stochastic algorithm for the treatment of non-linear non-convex optimization problems in continuous domain CMA-ES (Covariance Matrix Adaptation Evolution Strategy) is used to obtain the best fitted parameters simultaneously. The evolutionary optimization approach is illustrated in Fig. 7(b).

In this evolutionary algorithm, new individuals (candidate solutions V V .. g 1 ) i.e., the new generation are generated by the operations of crossover and mutation of the parents in the current generation. Next, some of these individuals are selected as parents in this next generation based on their fitness = f J V ( ) i i . In this way, the fitness levels of the population as a whole continuously improve with each additional generation. The process is iteratively repeated until convergence.

Results and discussion

By solving the inverse problem for the Zn sheet as described in the previous section, we obtain the set of parameters, shown in Table 4, and we observe a relatively good fit between the experimental results and multi-scale simulation (using the approach presented earlier), as will be seen in this section.

To better examine these parameters, we investigate the activation of deformation modes and textures after loading. The simulated textures will be compared to the experimental ones to draw a clear conclusion.

Tensile curves

The comparison of the macroscopic tensile curves obtained by simulation using the "best fit" identified micro-scale slip/twinning parameters and the experimental tensile curves is shown in Fig. 8. We observe good agreement between the experimental data and simulations, the agreement for loading along 0°/RD and 90°/RD being the best and worst respectively. For the 90°/RD loading, a good agreement between the curves is found until we reach a plastic strain of ≈ 3%, after which the simulated strain-stress curves show a lower trend compared to the experimental curves. Overall, the model appears to adequately capture the hardening behavior of the alloy.

It is instructive to note the effect of different deformation modes on mechanical behavior during mechanical loading. Basal slip (0 0 0 1) < 1 1 2 0 > is the principal mode seen in zinc when the applied stress is along a random direction. First order Pyramidal slip {1 0 1-0} < 1-1 2 0 > is typically seen when basal slip is either impossible, or when the applied load is in OR perpendicular to the basal plane. For zinc alloys, prismatic and pyramidal slips generally show greater activity at higher temperatures. The first 3 slip modes have the same slip direction (type < 1 1 2 0 >) and only second order pyramidal slip {1 1 2 2} < 1-1 2 3 > has an out-of-basal plane direction allowing the alloy to accommodate perpendicular strains. Twinning (tension twinning and compression twinning) may be assumed to be similar to a shear along a plane of type (1 0 1 2) along the [1 0 1 1] direction. It does not induce any significant strains [START_REF] Partridge | The crystallography and deformation modes of hexagonal closepacked metals[END_REF], rather it simply modifies the crystal orientation to facilitate additional slip before rupture.

We need to add here that it is risky to attempt to reverse identify the hardening coefficients for a pre-determined set of deformation modes directly from the macroscopic tensile curves, with NO information whatsoever of the fundamental physics of the microscale deformation. This is because the inverse problem in question is inherently ill-posed. Simply put, various combinations of deformation modes could mathematically yield the same cumulative strain ergo the same macroscopic tensile behavior. This means that we either constrain the identification problem in hardening coefficient space to purely physically-reasonable values OR a priori determine the deformation modes active in the specimen under loading (using texture evolution prediction) and use that to "guide" the identification process, so as to obtain solutions that respect the fundamental physics of deformation for the specimen.

Activation of deformation modes

The activity of each of the three active deformation modes is shown in Figs. 9(a) to 9(c).

We see that for the loading direction along 0°/RD, the model predicts that most of the deformation is accommodated by basal slip, followed by 2nd order pyramidal slip (at the beginning). The percentage of basal slip system activity percentage decreases with strain, eventually dropping below that of 2nd order pyramidal slip.

Meanwhile, during loading along 45°/RD and 90°/RD, the activation shows a similar trend as that seen during loading along 0°/RD, the only difference being the 2nd order pyramidal slip system activity that becomes more important (although lower than basal slip system activity). Twinning has approximately the same activity in all three loading conditions.

These observations are in good agreement with the results obtained by Philippe et al. [START_REF] Philippe | Modelling of texture evolution for materials of hexagonal symmetry i. application to zinc alloys[END_REF] who reported the activation of basal slip, followed by pyramidal π 2 slip and finally twinning.

The percentage of twinning activity is seen to decrease with strain. This would appear to contradict the relatively recent (and very relevant) observation by Hou et al. [START_REF] Hou | Study of twinning behaviors of rolled az31 magnesium alloy by interrupted in situ compressive tests[END_REF]. However, Hou's result was on a Mg alloy with a c/a (≈ 1.6) very different from our Zinc alloy (much higher ≈ 1.9) in this work. More importantly, for the alloy chosen by Hou, the initial basal texture (c-axis oriented along ND) favors deformation by twinning rather than the other modes (basal and pyramidal), as seen by the rotation of c-axis from ND to TD. In our case, due to the initial texture and the loading conditions, basal activates first, then twinning activity rises very sharply initially and quickly "saturates" and then drops off, while pyramidal activity steadily increases as deformation increases. This scenario is in agreement with most of the published experimental works for similar texture (see Table 3).

It is important to note that the drop off in twinning activity in our Zn alloy is NOT due to "detwinning" in any way, but rather a reorientation of grains to a new configuration (i.e. texture) that does not favor twinning.

That being said, we have made (in our numerical model) the assumption that the Voce hardening coefficients remain constant throughout the deformation, which could potentially affect the results (for the evolution of system activity).

Finally, we feel there is not enough literature on twinning activity in Zinc alloys to reach any general conclusions. That is why we examine the texture evolution prediction here to further augment the quality of the identified micro mechanical hardening parameters, otherwise one could very easily lead to scenarios that would "fit" the macroscopic tensile curves without correctly describing the underlying physical reality [START_REF] Benmhenni | Micromechanical modelling of monotonic loading of {CP} α-ti: Correlation between macroscopic and microscopic behaviour[END_REF].

Texture comparisons

Figs. 10 to 12 compare the textures obtained using EBSD characterization with those predicted by the multi-scale modeling approach. The MTEX toolbox in MATLAB has been used to plot all the pole figures in this subsection.

We compare the deformed textures from experiment and VPSCbased simulation using the identified parameter set, under nearly the same amount of strain (0°/RD ≈ 60%,45°/RD ≈ 35%,90°/RD ≈ 30%) in Figs. 10 to 12.

The pole figures show a relatively good agreement on loading along 0 °/RD and 90 °/RD condition, as expected, since the texture evolution is governed by the activated deformation modes in the loading process.

This basically means that the model successfully describes the activation of slip and twinning modes during uniaxial tension testing, at least for loading along 0 °/RD and 90 °/RD. The quality of the solution for loading along 45 °/RD is not nearly as good as the other two, since for the experimental textures, the positions of the poles shift along the rolling direction (compared to the initial texture) while, in the simulated textures, the poles remain split from the center of the figure along the rolling direction. That said, in both cases 2 poles (i.e., highest intensity) are observed.

Lankford R-values and Hill coefficients

In order to determine if the identified micro-scale parameters may be applied to more general processes than those used for the fitting procedure, we next simulate the Lankford R-values and compare them with the reported experimental values in the literature. The Lankford value (also called R-values), i.e., the plastic strain ratio (ε ε / p p 22 33 ), is a measure of the plastic anisotropy of a rolled sheet metal for loading along a given direction.

It is known that the degree of planar anisotropy in the zinc is very different from that seen in other HCP materials (e.g., pure titanium or magnesium based materials). In typical HCP materials, deformation is mostly by < 1 1-2 0 > slip thus allowing for higher R-values. R-values >1 indicate a higher resistance to thinning when the material is sub- jected to biaxial tensile stresses in the plane of the sheet. This translates to better formability when different parts of the blank are subjected to stretch-forming and radial drawing.

On the other hand, the R-values (i.e., the Lankford coefficient) for Zn-Cu-Ti rolled sheets are very low (<1), which implies a low resistance to thinning (at least during monotonic loading). The high uniform elongations observed during tensile testing indicate that the deformation is mainly compensated by a significant thickness reduction along the entire gauge area.

Using the modeling approach described previously, we can calculate the R-values from the given texture, by simulating a series of tensile tests in the texture plane, along a series of directions "probed" at angular increments of 5°from RD to TD.

The result obtained is compared with experimental results reported [START_REF] Bramley | Plastic anisotropy of titanium and zinc sheets[END_REF][START_REF] Fundenberger | Modelling and prediction of mechanical properties for materials with hexagonal symmetry (zinc, titanium and zirconium alloys)[END_REF] on a similar material in Fig. 13(a). From the curves, it is clear that the simulated results accurately describe the trend in the R value's evolution when loading along different directions ranging from RD to TD. While there is still a slight difference between the simulated and experimental results, it is insignificant in comparison with the experimental scatter expected in these experiments.

Finally we select the three R-values for tensile loading along 0°/RD, 45°/RD and 90°/RD respectively (i.e., R 0 , R 45 and R 90 ) and use them to calculate the 4 Hill coefficients F, G, H and N for the Zn alloy using the following expressions: These coefficients may be used to draw the Hill yield surface for the alloy in Fig. 13(b). The experimental points have also been shown in the same figure and the results appear to be coherent.

= = + - = + = R H G R N F G R H F G H , 1 2

Comments

We are able to get good agreement between simulation using the identified micro-scale parameters and experimental tensile testing along three different directions (namely, 0°/RD, 45°/RD and 90°/RD). It goes without saying that the model is limited by the experiments used to fit its parameters. Several modes of deformation have a low influence in the type of experiment used, other than first order pyramidal and prismatic slip and possible twinning, and therefore an accurate fitting of the entire model is difficult.

Secondly, it is true that we have calculated a single R-value for a given direction throughout the loading process, and thus ended up with constant Hill coefficients for the alloy considered, while in practice, Rvalues (and therefore Hill coefficients) change slightly with increasing plastic strain. In addition, while we limited ourselves to the simulation of uniaxial tensile tests alone, the goal was to confirm the validity of the approach for predicting the mechanical response of the material. It goes without saying that this study could provide useful information for future work on equibiaxial tension tests or other more complicated loading cases and forming operations.

For accurate macroscopic simulation of the forming operations on zinc sheets, the required materials parameters must be identified using an experimental forming set up that permits the realization of the complex desired shapes and loading conditions. That said, there are several practical difficulties in achieving these experimental setups. Firstly, it is very time consuming to realize all the loading paths adopted in industry, and furthermore, it is often very difficult to realize certain loading paths such as thin sheet compression in the rolling direction.

For all such cases, the multi-scale modeling strategy provides a solution by allowing us to run corresponding virtual tests and also plot the yield surface of studied material. The model's capacity to handle different stress conditions is not beyond question. For example, shear experiments would not give satisfactory results if modeled using parameters identified by uniaxial tension alone, since the model would seemingly be inadequate to describe the mechanical response. This is likely due to two important reasons: firstly, the relatively low activity of twinning under uniaxial tension would provoke an inaccuracy in the parameter identification. Since only three deformation modes have been selected for investigation, this would seem prima facie insufficient for shear tests.

Nevertheless, the strength of the approach lies in its simplicity (needing little more than uniaxial tensile testing) ergo one can justify studying its validity over a wider range of applications to identify the material parameters (e.g. Lankford R-vaues and Hill coefficients). Furthermore, we observe that the simulated Lankford coefficients are in good agreement with the values reported in the literature.

Conclusions

Characterization of zinc alloys, while very important from an industrial standpoint, is rendered difficult by its highly anisotropic behavior that strongly depends on microstructural effects, i.e. loading orientation-dependent activation of different families of slip systems and subsequent texture evolution. In this work, the authors made a contribution to the development of a physics-based multi-scale model using crystal plasticity, to simplify the characterization and take these microstructural effects into account, instead of the traditional approach using a phenomenological anisotropy model in conjunction with a large number of experiments. The approach, based on the VPSC paradigm, involves a viscoplastic micromechanical model based on microstructure and deformation mechanism information obtained by Electron Back-Scattered Diffraction (EBSD), that is combined with a self-consistent homogenization scheme to develop the macroscale deformation under uniaxial tensile loading, that is then compared to the experimental results to identify the crystal parameters in an inverse analysis using the CMA-ES genetic algorithm. By considering 2 slip modes and 1 twinning mode, we are able to satisfactorily reproduce the macroscopic stressstrain curves under uniaxial tension. An obvious way to improve the method is by comparing the experimental and simulated pole figures for the final textures in addition to the macroscopic stress-strain curves.

Fig. 1 .D

 1 Fig. 1. Macro-scale tensile stress-strain curves for 0.65 mm Zn sheet.

Fig. 2 .

 2 Fig. 2. Region for EBSD measurement showing the strain distribution for deformed natural zinc (0.65 mm thickness).

Fig. 3 .

 3 Fig. 3. Schmid Factor map in cold rolled zinc loaded by uniaxial tension along 0°/RD for (a) Basal slip system, (b) Prismatic slip system and (c) Pyramidal slip system.

Fig. 4 .Fig. 5 .

 45 Fig. 4. Schmid Factor map in cold rolled zinc loaded by uniaxial tension along 45°/RD for (a) Basal slip system, (b) Prismatic slip system and (c) Pyramidal slip system.

Fig. 6 .

 6 Fig. 6. Grains with twin boundaries marked (colored region): (a) grains with (1 1-2 2) twin boundaries, (b) grains with (1 1-2 1) twin boundaries, (c) grains with (1 0-1 2) twin boundaries.

Fig. 7 .

 7 Fig. 7. (a) Full procedure for the identification (b) Evolutionary algorithm for the inverse problem.

Fig. 8 .

 8 Fig. 8. Comparison of simulations with the identified micro-scale parameters and experiment.

Fig. 9 .

 9 Fig. 9. Activation of deformation modes during simulated tensile loading along (a) 0°/RD, (b) 45°/RD and (c) 90°/RD.

  following values for the Hill coefficients for rolled Zn-Cu-Ti sheets of 0.65 mm thickness: = F 0.2805, G= 0.885, H= 0.115 and N = 0.7692.

Fig. 10 .Fig. 11 .

 1011 Fig. 10. Comparison of texture obtained by experiments (left) and simulations (right) for tensile loading along 0°/RD up to strain of 60%.

Fig. 12 .

 12 Fig. 12. Comparison of texture obtained by experiments (left) and simulations (right) for tensile loading along 90°/RD up to strain of 30%.

Fig. 13 .

 13 Fig. 13. (a) Comparison of Lankford coefficients (b) Yield surface -simulated and experimental.

Table 1

 1 Chemical composition (%) of the rolled Zn-Cu-Ti commercial zinc alloy.

	Materials	Cu	Ti	Al	Zn
	Natural Zinc	≥ 0.08	≤ 0.06	-	rest

Table 2

 2 Deformation modes to be considered in the microscale model.

	System	Basal	Pyramidal π 2	Tensile twinning
	Number of planes	1	6	6
	Number of directions	3	6	6
	Double planes	3	6	6
	Slip plane &

Table 4

 4 Identified micro-scale Voce parameters for all 3 deformation modes.

	α	Mode	τ α 0	τ α 1	θ α 0	θ α 1
	1	Basal	1	1.6	250	3.31
	2	Pyramidal π 2	47.94	51.54	4500	3.17
	3	Twinning	106.25	4.408	525.61	4.46

Acknowledgements

The authors acknowledge Dr. Ricardo Lebensohn from Los Alamos National Laboratory for providing the VPSC code. We would also like to thank Hugues Marie, former student of Mechanical engineering at INSA Rennes and research intern at Laboratoire Roberval for his contribution to the work.