Pierre Peterlongo

Nadia Pisanti

Alair Pereira Do Lago

Marie-France Sagot

Lossless Filter for Long Multiple Repetitions with Edit Distance

Identifying local similarity between two or more sequences, or identifying repetitions occurring at least twice in a sequence, is an essential part in the analysis of biological sequences and of their phylogenetic relationship. Finding fragments that are conserved among several given sequences, or inside a unique sequence, while allowing for a certain number of insertions, deletions, and substitutions, is however known to be a computationally expensive task, and consequently exact methods can usually not be applied in practice. The filter we introduce in this paper, called Ed'Nimbus, provides a possible solution to this problem. It can be used as a preprocessing step to any multiple alignment method, eliminating an important fraction of the input that is guaranteed not to contain any approximate repetition. It consists in the verification of a strong necessary condition. This condition concerns the number and order of exactly repeated words shared by the approximate repetitions. The efficiency of the filter is due to this condition, that we show how to check in a fast way. The speed of the method is achieved thanks also to the use of a simple and efficient data structure, that we describe in this paper, as well as its linear time and space construction. Our results show that using Ed'Nimbus allows us to sensibly reduce the time spent in a local multiple alignment.

Introduction

Multiple comparison is an essential part of the analysis of biological sequences and of their phylogenetic relationship. In particular, local multiple alignment is a powerful way to detect functional elements while identifying (multiple) repetitions inside a sequence is fundamental, for instance, in the investigation of transposition or duplication events. Finding fragments that are conserved among several given sequences or inside a unique sequence (i.e. finding repetitions) while allowing for a certain number of insertions, deletions, and substitutions, is however known to be a computationally expensive task, and consequently exact methods can usually not be applied in practice.

When comparing biological sequences in order to find features such as promoter or regulatory regions [START_REF] Ahituv | Mapping Cis-regulatory Domains in the Human Genome Using Multi-species conservation of synteny[END_REF][START_REF] Hardison | Global Predictions and Tests of Erythroid Regulatory Regions[END_REF], transposable elements or other types of long repetitions [START_REF] Juretic | Transposable Element Annotation of the Rice Genome[END_REF][START_REF] Lipatov | Paucity of Chimeric Gene-transposable Element Transcripts in the Drosophila Melanagaster Genome[END_REF], or to precisely identify the different rearrangements that may have happened [START_REF] Bourque | Genome-Scale Evolution: Reconstructing Gene Orders in the Ancestral Species[END_REF][START_REF] Brudno | Glocal Alignment: Finding Rearrangements During Alignment[END_REF][START_REF] Pevzner | Genome Rearrangements in Mammalian Evolution: Lessons From Human and Mouse Genomes[END_REF], it is therefore important to be able to deal in a fast and accurate way with the huge amount of data represented by one or more whole genomes. Filtering, lossless or with possible loss, has appeared as one important way of dealing with part of the problem. The main idea behind it is to eliminate in a first, hopefully quick step, many portions of the input sequences before any further potentially costly investigation. Given a definition of what is the ultimate goal of the sequences comparison (for instance, it may be to identify all long repetitions of a certain type), lossless filters eliminate only those portions of the input data that are guaranteed not to contain the sought elements (in this example, the repetitions). Lossless filters produce therefore no false negatives. Filters that are not lossless cannot provide such guarantee and are thus heuristics.

In the last few years, there has been an increasing number of papers on the topic of filtering sequences prior to aligning them. This trend has been motivated by the fact that the problem of aligning biological sequences has scaled up considerably with the increasing number of genomes, notably of eukaryotes, that are being entirely sequenced and annotated. Filters, lossless or not, have thus been devised for comparing one string with itself [START_REF] Kolpakov | MREPS: Efficient and Flexible Detection of Tandem Repeats in DNA[END_REF], two strings pairwise [START_REF] Aghili | Efficient Filtration of Sequence Similarity Search Through Singular Value Decomposition[END_REF][START_REF] Brudno | LAGAN and Multi-LAGAN: Efficient Tools for Large-Scale Multiple Alignment of Genomic DNA[END_REF][START_REF] Kucherov | Multiseed Lossless Filtration[END_REF][START_REF] Li | PatternHunter II: Highly Sensitive and Fast Homology Search[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] or more than two strings among them at the same time [START_REF] Peterlongo | Lossless Filter for Finding Long Multiple Approximate Repetitions Using a New Data Structure, the Bi-factor Array[END_REF]. Most filters rest on the idea that sequences that are reasonably similar have some parts that match exactly.

The fragments matching exactly that have been considered for building efficient filters have been, like in the Blast strategy [START_REF] Altschul | Basic Local Alignment Search Tool[END_REF], mostly single blocks (also called seeds) or a set of blocks separated by a fixed or flexible distance (also called spaced-seeds) as in [8-10, 24, 27, 29, 31, 32].

The authors of this paper have also contributed to the area in the past, notably in the context of identifying long repetitions allowing for substitutions only [START_REF] Peterlongo | Lossless Filter for Finding Long Multiple Approximate Repetitions Using a New Data Structure, the Bi-factor Array[END_REF]. Results in terms of both specificity (that is, percentage of filtered data) and time were promising, but the tool Nimbus presented in [START_REF] Peterlongo | Lossless Filter for Finding Long Multiple Approximate Repetitions Using a New Data Structure, the Bi-factor Array[END_REF] was meant as a lossless filter preceeding an alignment where no insertions or deletions were allowed, which is in general less relevant in biology.

In this paper, we eliminate this drawback by introducing a new filter, called Ed'Nimbus, that is lossless like Nimbus and has the same good performances while working with edit distance, that is, with insertions and deletions allowed besides substitutions. The other main characteristics of our filter, besides the fact that it is lossless and works within an edit distance framework, are that: 1. it is a filter that may be used, and indeed was conceived, for doing a multiple comparison, 2. it considers multiple seeds, and 3. it considers such multiple seeds taking into account both their number and the relative order among them.

Furthermore, Ed'Nimbus can take as input either m sequences or one unique sequence. In the first case, we want to find long approximate repetitions present in r ≤ m of the input sequences, and in the second case, we are looking for fragments occurring r times in the unique input sequence. The filter we present may however be used in more general contexts (for instance, as a first step in a multiple alignment algorithm) as we show with one application.

To the best of our knowledge, there is no lossless method that filters data for finding long multiple repetitions using edit distance. Among existing methods for finding repetitions, most use multiple seeds that have been shown in [START_REF] Burkhardt | Better Filtering with Gapped q-Grams[END_REF] to be particularly efficient for this task. Some deal with edit distance [START_REF] Aghili | Efficient Filtration of Sequence Similarity Search Through Singular Value Decomposition[END_REF][START_REF] Brudno | LAGAN and Multi-LAGAN: Efficient Tools for Large-Scale Multiple Alignment of Genomic DNA[END_REF][START_REF] Burkhardt | q-Gram Based Database Searching Using a Suffix Array (QUASAR)[END_REF][START_REF] Burkhardt | One-Gapped q-Gram Filters for Levenshtein Distance[END_REF][START_REF] Navarro | Indexing Text with Approximate q-Grams[END_REF][START_REF] Rasmussen | Efficient q-Gram Filters for Finding All -Matches Over a Given Length[END_REF] but for pairwise comparison only. Other methods [START_REF] Bray | MAVID: Constrained Ancestral Alignment of Multiple Sequences[END_REF][START_REF] Brudno | LAGAN and Multi-LAGAN: Efficient Tools for Large-Scale Multiple Alignment of Genomic DNA[END_REF][START_REF] Edgar | MUSCLE: Multiple Sequence Alignment with High Accuracy and High Throughput[END_REF][START_REF] Katoh | Mafft: a novel method for rapid multiple sequence alignment based on fast fourier transform[END_REF] quickly find multiple repetitions, but are heuristics and use a phylogenetic tree to drive the alignment. Hence, Ed'Nimbus is the first lossless filter for finding multiple repetitions within an edit distance framework.

It is worth stressing that Ed'Nimbus is meant as a preprocessing step to any method that searches for long approximate repetitions, or that performs a multiple alignment based on the detection of such repetitions. The goal of Ed'Nimbus is to reduce the input size for these methods in order to obtain a significant overall speed up.

The paper is organised as follows: we start by presenting the necessary condition we use for our lossless filter in Section 2. In Section 3, after having detailed the data structure used, we present the filtering algorithm and a complexity analysis. We then give in Section 4 the results of some tests: in Section 4.1 we show the specificity and time requirement of Ed'Nimbus, and in Section 4.2, we present some preliminary applications of Ed'Nimbus as a preprocessing of a multiple alignment.

Although Ed'Nimbus can identify repetitions either common to a set of sequences or that appear various times in a unique sequence, for clarity of exposition and because of space limitations, we address only, in Sections 2 and 3, the case of finding repetitions common to a set of sequences. The case of a unique sequence is treated in a very similar way and leads to the same performances.

A sequence is a set of zero or more symbols from an alphabet Σ. A sequence s of length n on Σ is represented also by s[0]s [START_REF] Aghili | Efficient Filtration of Sequence Similarity Search Through Singular Value Decomposition[END_REF] . . . s[n -1], where s[i] ∈ Σ for 0 ≤ i < n. The length of s is denoted by |s|. We denote by s[i, j] the word s[i]s[i + 1] . . . s[j] of s. In this case, we say that the word s[i, j] occurs at position i in s. We define a k-factor as a word of length k. A k-factor is said to be shared by two or more sequences if it occurs in all of them. We define a k-hit as a k-factor that is shared by at least two sequences. If s = uv for u, v ∈ Σ * , we say that u is a prefix of s and that v is a suffix of s. Definition 1. Given r sequences s 1 , . . . , s r , a length L, and a distance d, we call an (L, r, d)repetition a set of integers {δ 1 , . . . , δ r } such that

∀ i ∈ [1, r] : 0 ≤ δ i ≤ |s i | -L and ∀ i, j ∈ [1, r] : d E (s i [δ i , δ i + L -1], s j [δ j , δ j + L -1]) ≤ d.
The symbol d E stands for the edit distance between two sequences, that is, the minimum number of letter insertions, deletions and substitutions that transforms one into the other.

Given m input sequences, let us suppose we want to find words of length L that occur in at least r ≤ m sequences with at most d edit operations1 between each pair of the r repetitions, where L, d and r are given by the user. In other terms, let us suppose we want to identify all the (L, r, d)-repetitions in a set of r ≤ m input sequences. The goal of the Ed'Nimbus filter is to very quickly eliminate from the input sequences as many positions as possible that cannot belong to such repetitions. This operation can be seen as a preprocessing that drastically reduces the search space for any method that looks for approximate repetitions or performs local multiple alignments. Moreover, since (as we shall see in Section 4.1) Ed'Nimbus actually removes almost every sequence position that does not contain an (L, r, d)-repetition, it can also be used alone as a heuristic method with a very low false positive rate, and no false negatives (since it is lossless).

The main idea of our filter is based on checking a necessary condition concerning the amount of k-hits that an (L, r, d)-repetition must contain. Let p be the minimum number of possibly overlapping k-hits that an (L, 2, d)-repetition must have. Pevzner and Waterman showed in [START_REF] Pevzner | Multiple Filtration and Approximate Pattern Matching[END_REF] that:

p = L -(d + 1) × k + 1.
That is, if two words of length L have edit distance at most d, then they share at least

p = L -(d + 1) × k + 1 k-factors.
Moreover, such k-hits obviously have also to occur in the same order in the two words of length L, even if not necessarily at the same distance from one another. In particular, a word of length L of the input can be part of an (L, r, d)-repetition only if it shares at least p k-hits in the same order, with words of length L that belong to at least r -1 other input sequences. Notice that this property is a weaker condition than having r or more words of length L that pairwise share at least p k-hits in the same order.

The idea of Ed'Nimbus is to check this (weaker) property for each possible starting position of a word of length L, and to discard those that do not satisfy this necessary condition.

Ed'Nimbus

The efficiency of Ed'Nimbus in checking the necessary condition we just indicated, is partly due to the use of a data structure, called the k-factor array. We start by presenting it, before giving the idea of the method (Section 3.2) and a detailed description of the algorithm (Section 3.3) with its complexity (Section 3.4).

The k-factor array

The k-factor array is an array providing in constant time all positions in a text of a given k-factor. We show in this section how to construct this data structure. information is stored in the suffix array: the length of the longest common prefix (lcp) between two consecutive suffixes (s[π(i) . . . ] and s[π(i + 1) . . . ]) in the array. The construction of the permutation π of a text of length n is done in linear time and space [START_REF] Kärkkäinen | Simple Linear Work Suffix Array Construction[END_REF][START_REF] Kim | Linear-time Construction of Suffix Arrays[END_REF][START_REF] Ko | Space Efficient Linear Time Construction of Suffix Arrays[END_REF]. A linear time and space lcp row construction is presented in [START_REF] Kasai | Linear-time Longest-Common-Prefix Computation in Suffix Arrays and its Applications[END_REF].

The k-factor array is a modification of the suffix array, to which we add two columns: the label and the index. A label is an integer ∈ [0, |Σ| k ], and there is a label for each distinct k-factor occurring in the input sequences. All suffixes starting with the same k characters have the same label at the corresponding position in the array label, while all suffixes starting with different k characters have distinct labels. In order to give each distinct k-factor a different label, the lcp array is used. The label of the k-factor corresponding to the i th suffix in the suffix array, called label[i], is created as follows for each i ∈ [1, n -1]:

label[i] =    0 i f i = 0 label[i -1] + 1 if lcp[i] ≤ k label[i -1] otherwise
The second novelty of the k-factor is the index array, that allows to quickly retrieve the positions of all k-factors having a certain label. The index array is constructed such that index[i] represents the index of the first occurrence of the suffix starting with a k-factor labelled i. The label and index arrays are created simultaneously in linear time and space. An example of a k-factor array is given in Figure 1.

i lcp π associated suffix label 0 0 2 AACCAC$ 0 1 1 6 AC$ 1 2 2 0 ACAACCAC$ 1 3 2 3 ACCAC$ 1 4 0 7 C$ 2 5 1 1 CAACCAC$ 3 6 2 5 CAC$ 3 7 1 4 CCAC$ 4 index 0 0 1 1 2 4 3 5 4 7
Fig. 1. The k-factor array, with the label and index array for the text ACAACCAC and k = 2.

In order to avoid problems due to k-factors occurring at one of the k -1 last positions of the text, one can consider that the text is followed by as many special symbols ($ for instance) alphabetically smaller than all others.

In the next section, we present an overview of the method of which we give a detailed description later in Section 3.3.

Overview of the method

Ed'Nimbus takes as input the parameters L, r and d, and m (with m ≥ r) input sequences: s 0 , s 1 , . . . , s m-1 . Given such parameters, first, if the user does not specify it, it fixes the value of k to 62 to obtain the most suitable value of p. Secondly, this value is used to actually filter, that is, to detect portions of the input that satisfy the required condition, and hence that can contain an (L, r, d)-repetition. The goal of this section is to explain how the filtering works.

We remind that the condition that should be checked for each position of each sequence, is whether the word of length L starting at that position shares at least p = L -(d + 1) × k + 1 k-hits, that occur in the same order and within a window of size L, with at least r -1 other input sequences. More formally, for each sequence s j and for each one of its words s j [i, i + L -1] of length L (with i ∈ [0, |s j | -L]), let t(s j , i) be the number of distinct sequences s = s j where ∃ i ∈ [0, |s | -L] such that s j [i, i + L -1] and s [i , i + L -1] have at least p k-hits occurring in the same order. We should compute t(s j , i) for each j ∈ [1, m] and each i ∈ [0, |s j | -L], and keep only the positions that belong to the following set:

{i ∈ [0, |s j | -L] | j ∈ [1, m], t(s j , i) ≥ r -1}.
A first approach to do this would, for each sequence s j in turn, use a single sliding window of size L that refers to a candidate repetition in s j (we call this window the reference window) and, for this reference window, check whether its k-factors are k-hits shared, in the same order, with words of length L belonging to at least r -1 other input sequences. This first approach would therefore count, for each sequence s j and each of its positions i ∈ [0, |s j | -L], and for each other sequence s and each one of its positions i ∈ [0, |s | -L], the number of k-hits of s j [i, i + L -1] and s [i , i + L -1] that occur in the same order.

However, as is done in [START_REF] Burkhardt | q-Gram Based Database Searching Using a Suffix Array (QUASAR)[END_REF], in order to avoid considering all positions in all other sequences except s, we can divide those remaining sequences into blocks of length 2L (instead of L) that overlap in at least L positions3 , and then perform the following two steps:

1. Detect the blocks with which the reference window shares at least p k-factors (without looking at their relative order). We call such blocks the good blocks. This step is done using the k-factor array (as described in Section 3.1) that allows us to access in constant time the list of positions in the input sequences where a given k-factor occurs. 2. Keep, among the good blocks, only those that share at least p k-hits occurring in the same order. If these are in at least r -1 distinct input sequences, then the position of the reference window is considered as a starting point for a possible repetition. Otherwise, it is rejected by the filter.

This second approach is the one adopted in Ed'Nimbus. We call the first approach Naive. Strictly speaking, this is a slight abuse of language since Naive is not a naive version of exactly the same algorithm as Ed'Nimbus because the two check different things.

Indeed, considering O(N/L) blocks of size 2L rather that all O(N ) words of length L, leads to a factor L gain in the time complexity, but also in a loss of specificity. Since the resulting verified necessary condition is slightly weaker, we could keep parts of the sequences that would have been discarded by Naive. However, in Section 4.1, we compare the specificity and the time costs of Ed'Nimbus and of Naive in order to show that the small extra false positive ratio is by far compensated by the speed of Ed'Nimbus.

Before that, Section 3.3 describes the Ed'Nimbus algorithm in more detail.

The algorithm

In this section, we describe how exactly the filter works, showing which operations it performs in the initialisation step and each time the window is moved, and how the necessary condition is checked for each position of the window.

The algorithm begins with the construction of a k-factor array as described in Section 3.1. A unique k-factor array is created for all the sequences as if they were concatenated, thus providing a unique and uniform labelling of the k-factors.

At each moment, the reference window refers to a word of length L in one of the input sequences, and all the other sequences are divided into overlapping blocks of length 2L. We keep an array called hits that stores in hits[b] the number of k-hits shared by the word of length L inside the window and the block b. Furthermore, we use an array called nbGoodBlocks having as length the number of input sequences, and containing in nbGoodBlocks[i], for the reference windows, the number of good blocks in the sequence s i . Both arrays are initially set to zero in all positions.

For each input sequence s j , the window of length L is initially placed at position 0. In all the other sequences, we consider blocks of length 2 × L that overlap by L positions, i.e. every L positions (0, L, 2 × L, . . . ), a block of length 2 × L starts. concerning the initial position of the window in the following way. For each k-factor (say, labelled l) found inside the reference window, for each block b i where l occurs 4 , hits[b i ] is incremented by one. With this increment, if hits[b i ] becomes equal to p, then b i becomes a good block. In this case, if s j is the sequence containing this good block, then nbGoodBlocks[j] is incremented by one.

For each one of the other O(N ) positions of the reference window, we perform the following two steps:

1. Sliding the reference window: When sliding the reference window, a k-factor is removed and another one is introduced. We pick the labels of both and read in the k-factor array the list of blocks they belong to; for the former, we decrease the corresponding entries in the array hits, while for the latter we increase them.

After decrementing its value, if hits[b i ] becomes equal to p -1, then it means that b i is no longer a good block. In this case, if s j denotes the sequence containing b i , then nbGoodBlocks[j] is decremented by one. Symmetrically, we do as described above for all entries hits[b i ] that are incremented.

2. Checking the relative order of the k-hits: Using the nbGoodBlocks array, we check if at least r -1 sequences contain at least one good block. If this is the case, we check whether there are enough good blocks where the k-hits occur in the same order. Thus, for each good block b, we have to check whether at least p (out the hits[b]) k-hits are in the same order. This consists in computing the longest common subsequence (LCS) between the reference window and the considered block, after both have been rewritten using the alphabet of the labels associated with the k-factors 5 . If the LCS is greater or equal to p, then the condition is satisfied. More precisely, we proceed as follows. For each good block on a sequence where no good block has already been found containing at least p k-hits in the same order:

-Compute the LCS between this block and the reference window, both rewritten using the k-factor labels alphabet. -If this is greater or equal to p, then mark the sequence where the block occurs as containing a possible repetition.

If at the end of the step, less than r -1 sequences contain a good block with at least p k-hits in the same order, then it means that the reference window cannot be an approximate repetition, and the corresponding position is discarded. Notice that in this way, we check whether the word inside the current window has at least r -1 possible matches (that is blocks in which there are enough k-hits in the same order), but we do not check any similarity condition between pairs of such r -1 matches. This is a main reason for the speed of the filter.

We now list all possible cases that can lead to false positives, that is, all cases where a word of length L corresponding to a currently examined window is not discarded although it is not part of an (L, r, d)-repetition.

First, it may happen that the reference window respects the necessary condition with r -1 blocs while the r -1 blocks are pairwise distant by more than d edit operations. Second, it can be that the block of size 2L does contain a real match, but that this has length greater than L. Third, a possible match may not be a real match: having p k-hits in the same order is only a necessary condition for two words of length L to be no more than d edit operations apart.

We can observe that the first case becomes more unlikely as the value of r is higher. The second case, apparently leading to many false positives, creates in fact only few. We show in Section 4 that in practical cases, the false positives due to this reason are rare. However, we show in Section 4 that the specificity of the filter is quite good in practice.

Complexity analysis

Let us assume Ed'Nimbus has to filter m sequences, each of length n, and let us recall that N denotes the total input size n × m.

Space Complexity: The k-factor array construction can be done in linear time and space w.r.t. the data length (see Section 3.1). The hits array has size N L (that is the number of blocks). We use another array to store the results (the positions of the windows where a possible repetition occurs), which is simply an array of N booleans. Thus, the total space complexity is in O(N ), that is, linear in the input size.

Time complexity:

We take into consideration two distinct cases. The first case, called dense, corresponds to sequences that contain a great number of highly similar repetitions. The second case, called sparse, corresponds to sequences containing only a few repetitions that are weakly similar. Furthermore, we assume that every possible k-factor exists in the sequences, considering that each k-factor occurs on average at N |Σ| k positions instead of N positions. This assumption is realistic when filtering long DNA sequences (the goal of the filter) with small k-factors (k 8).

For each of the O(N ) positions of the sliding window, we do the following (we consider separately the two parts described in Section 3.3).

-Sliding the window: removing and adding one k-factor costs as much as the number of blocks of which the entry in the array k-hits has to be updated, that is, O( N L×|Σ| k ) both in the dense and in the sparse case. Notice that on sequences composed only of 'A' for instance, this complexity grows to O( N L ). -Checking the relative order of the k-hits: this means computing the LCS of the windows against all the good blocks. Denoting by G the number of good blocks found for the current window, we thus have to compute G times the LCS between a word of length L against another of length 2L. We compute the LCS using the method of [START_REF] Hunt | A fast algorithm for computing longest common subsequences[END_REF] and described in [START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology[END_REF] that takes time in O(l log l ) to compute LCS(u,v), where l is the number of letters of u times the number of their occurrences in v, and l is the length of LCS(u,v). In our case, l is at most L, while l is at most 2 × L 2 (in the dense case), and can be assumed to be L in the sparse case. Summing up, in the dense case, this step takes

O(L 2 × log L × G) time, whereas it takes O(L × log L × G) time in the sparse case.
Since we have to perform up to N times the two steps above, the overall time complexity is

O N × N L × |Σ| k sliding + L 2 × log L × G LCS = O N 2 L × |Σ| k + N × L 2 × log L × G (dense case) and O N × N L × |Σ| k sliding + L × log L × G LCS = O N 2 L × |Σ| k + N × L × log L × G (sparse case)
In the dense case, G can theoretically be as high as the total number of blocks, that is N L . This leads to an overall complexity in O( N 2 L|Σ| k +N 2 ×L×log L). Notice, however, that it is enough to detect r -1 blocks that conserve the order of the k-factors and, in particular, that when one of them is found in a input sequence, no other good block of that sequence will have to be checked. Moreover, since we are in the dense case, we can expect that this happens soon enough to actually save many LCS computations with respect to the worst case in the complexity indicated above.

Comparatively with the time complexity in O N 2 ×L+Y with Y = N ×L 2 ×log L×G (dense case) or Y = N × L × log L × G (sparse case) of the Naive algorithm mentioned in Section 3.2, the Ed'Nimbus algorithm represents a very good improvement, as confirmed by the tests shown in Section 4.1.

Experimental Results

In the next two sections, we show the time actually required by Ed'Nimbus on real biological sequences. As a first test (Section 4.1), we evaluate the growth of the execution time with respect to the input size, as well as the specificity with respect to time. Then, as a second test (Section 4.2), we show the use of the filter as a preprocessing step to a multiple local alignment algorithm. All tests were done on a 1.2 GHz Pentium 3.

Testing specificity and speed

We performed tests that show how much time Ed'Nimbus requires what is its specificity in practice.

For both evaluations (time and specificity), we compared the performance of Ed'Nimbus with respect to the Naive algorithm (Section 3.2). The specificity of Naive is higher than the one of Ed'Nimbus because the Naive algorithm checks the condition (Section 2) on words both of length L, while Ed'Nimbus does it on the current window (of length L) and blocks of length 2L. Ed'Nimbus may thus detect false positives that Naive does not, leading to a weaker specificity. We show in this section that the difference in specificity is negligible, while the difference in speed is very high in favour of Ed'Nimbus.

We start with an experiment that aims to show how the execution time grows with respect to the input size. We generated for this 4 random DNA sequences of the same length, and we planted in each sequence a repetition of length L = 100 whose copies in the sequence have pairwise edit distance exactly equal to 10. We ran both Ed'Nimbus and Naive with parameters L = 100, d = 10, r = 4, k = 6. We did the same test for a length of the input sequences ranging from n = 100 to n = 6000, that is for a total input size, equal to N = 4 × n, ranging from 400 to 24000. We could not go further because the Naive algorithm took too long, in particular since we repeated the experiment 50 times for each input size in order to report an average value. In Figure 2, we report the time taken by the two algorithms, expressed in seconds, with respect to the size of the input sequences. Observe that the difference is significant (the values are plotted in logarithmic scale).

The goal of this experiment was only to show how the time consumption grows with the input size for the two algorithms. We now show how the two methods behave in terms of specificity, still keeping an eye on the time costs. This is more relevantly done on real biological sequences. We thus considered the DNA sequence of the Neisseria meningitidis strain MC58. Neisseria genomes are known for the abundance and diversity of their repetitive DNA in terms of size and structure [START_REF] Tettelin | Complete Genome sequence of Neisseria Meningitidis Serogroup B Strain MC58[END_REF]. The size of the repeated elements range from 10 bases to more than 2000 bases, and their number, depending on the type of the repeated element, may reach more than 200 copies. This fact explains why the N. meningitidis MC58 genomic sequence has already been used as a test case for programs identifying repetitive elements like in [START_REF] Kolpakov | MREPS: Efficient and Flexible Detection of Tandem Repeats in DNA[END_REF]. On half of the sequence (about 1 Mb: more was not feasible for the Naive algorithm), we ran Ed'Nimbus, looking for repetitions of length L = 100, distant pairwise by at most d = 10 edit operation, occurring at least r = 5 times, using k = 5. It We then performed some tests on randomly generated sequences to check how both Ed'Nimbus and Naive behave when the input sequences contain repetitions with more edit operations than the limit specified by the user. We thus created a set of 5 sequences each containing a repetition of length 100, distant pairwise by 10, 12, 14, . . . , 22, 24 edit operations. On those sequences, we ran Ed'Nimbus and Naive, filtering for repetitions of length L = 100, r = 5, d = 10 with k = 5. Each test was computed 50 times, the average results are given in Figure 3. The results show that, first, even if Naive has better specificity than Ed'Nimbus, the difference is low, and second, the filter is fully efficient even when the edit distance between the repetitions is 14 more than the limit specified by the user. Over this value, no repetition is detected anymore. However, one can notice that with these parameters, having 6 more edit operations leads to filtering ≈ 50 % of the repetitions.

We presented in this paper a novel lossless filtration technique designed to precede any exact tool for finding long multiple approximate repetitions distant by a bounded number of substitutions, insertions and deletions. The repetitions may be common to several sequences or present inside one single sequence. As we have seen, the filter runs very fast and uses linear space to discard parts of the data that can not contain repetitions since they do not satisfy a necessary condition based on the number of exactly repeated words such repetitions must share and the way they are arranged. The speed of the method is achieved also thanks to the use of a simple and efficient data structure that is presented in the paper.

We showed in Section 4.1 that the specificity of the filter is very good. Moreover, we have described in Section 4.2 that using Ed'Nimbus allows us, on some preliminary applications, to apply exact multiple alignment methods in a short time.

Needless to say that Ed'Nimbus can also be used as a preprocessing step for a heuristic multiple alignment method, with the only purpose of speeding up the execution time.

As a next step of future work, we want focus on analisying how many among what we consider as false positives, are actually occurrences of what would be real repetitions is the constraint of all having the same length L would be relaxed. Indeed, flexible values for the length of the repetitions filtered, as done for instance in [START_REF] Rasmussen | Efficient q-Gram Filters for Finding All -Matches Over a Given Length[END_REF], would be interesting in practice, as well as natural for Ed'Nimbus. As a matter of fact, we believe that many of what we considered here false positives are actually occurrences of repetitions that have length, say, between L and L+d, actually realising the desiderable flexibility.

On this current version, Ed'Nimbus, available at http://igm.univ-mlv.fr/∼peterlon/officiel/ednimbus/ is useful either as a preprocessing step for any (multiple) local alignment, or, thanks to its high specificity, as a heuristic for finding long multiple repetitions.

  Given a sequence s of length n, for i ∈ [0, n-1], let s[i . . . ] denote the suffix starting at position i. Thus s[i . . . ] = s[i, n -1]. The suffix array of s is the permutation π of {0, 1, . . . , n -1} corresponding to the lexicographic order of the suffixes s[i . . . ]. If ≤ l denotes the lexicographic order between two words, then s[π(0) . . . ] ≤ l s[π(1) . . . ] ≤ l . . . ≤ l s[π(n -1) . . . ]. In general, another

  logarithmic scale) Input data length (logarithmic scale) Time used by Ed'Nimbus and naive

Fig. 3 .

 3 Fig.3. Specificities of Ed'Nimbus and Naive. In all tests, there are 5 input random sequences (of length 10000), each containing a repetition of length 100 distant pairwise from 10 to 26 edit operations.

  Time spent by Ed'Nimbus and the naive algorithm w.r.t. the input size, in logarithmic scale. In all tests there are 4 input sequences of growing size (x axis), and we filter (100, 4, 10)-repetitions, with k = 6. kept 7.3% of the input, after filtering, in about 8 minutes of computation. On the same sequence with the same parameters, the Naive algorithm kept 7.2% of the input, running for 7529 minutes (more than five days).The results show that the ratio between time and specificity is very good for Ed'Nimbus on real DNA sequences.

	Time Ed'Nimbus
	Time Naive
	Fig. 2.

By edit operations we denote insertions, deletions and substitutions.

The value of k is chosen according to an evaluation based on preliminary tests, that we do not describe in this paper. Notice, however, that the choice of k has possible effects on the efficiency (both in terms of time cost and filtration ratio) of the filter, but not on its correctness.

That is, blocks of length 2L starting every L positions: each block overlaps both the previous and the next in L positions, hence ensuring that each word of length L is entirely included in at least one block.

This information is available in the k-factor array and accessible in constant time.

In other words, at each possible position i of the sequence, we replace the letter at that position, say α, with the label representing the k-factor that begins at i.

Notice that we chose Glam as a representatively good software for multiple alignment, but the filter could be used as a preprocessing step to any other multiple alignment algorithm.

-mlv.fr/∼peterlon/officiel/ednimbus/ Supported by the ACI Nouvelles Interfaces des Mathématiques π-vert project of the French Ministry of Research, the ALGONEXT project of the Italian Ministry of Research, and the GALILEO project of the Italian-French University. Supported by the ACI Nouvelles Interfaces des Mathématiques π-vert project of the French Ministry of Research, the ARC BIN project from the INRIA, the ANR project REGLIS, and the GALILEO project of the Italian-French University.

http://igm.univ

We performed additional tests validating the good specificity of Ed'Nimbus coupled with a low time and memory usage. On one random sequence of length 2.2 Mb containing 3, 5, or 100 known planted repetitions with 10 edit operations pairwise, we ran Ed'Nimbus looking for (L, r, d) repetitions with r =3, 5, and 100, L = 100, d = 10 and k = 6. Furthermore, we performed the same tests on the MC58 sequence described above. Each test was computed 50 times, the average results are given in Figure 4. In this Figure, one can notice that on random DNA sequences of length 2.2 Mb, depending on the parameters, the time consumption is a few minutes and the memory usage is limited to less than 100 Mb.

Applications

We finally used Ed'Nimbus for the one of the main purposes we have designed it for: as a preprocessing step for performing a multiple local alignment. On m sequences of length n, this task can be done with dynamic programming using O(2 m n m ) time and O(n m ) space, where r is the number of sequences where a repetition must occur in order to contribute to the alignment. In practice, this is unfeasible for large and/or numerous sequences. As a consequence, the solutions proposed are mostly heuristics (as for example Mulan [START_REF] Ovcharenko | Mulan: Multiple-Sequence Local Alignment and Visualization for Studying Function and Evolution[END_REF]) that do not guarantee to avoid false negatives. The alternative we suggest is to use any exact local alignment method after a preprocessing filtering of the input sequences done using Ed'Nimbus. The filtered data still contains the repetitions plus possibly a few other positions (as we have seen in Section 4.1), but it should now have become feasible, and much faster, to perform an exhaustive search for repetitions. Indeed, we expect that the preprocessing hugely reduces the overall execution time.

GAT A3 is a gene that is involved in various development processes [START_REF] Ovcharenko | Mulan: Multiple-Sequence Local Alignment and Visualization for Studying Function and Evolution[END_REF]. Since some such processes are identified, and differ among distinct species, it is interesting to perform a comparative analysis of this gene in different species by doing a multiple local alignment. We applied this idea to the GAT A3 gene locus of 8 species (human, mouse, rat, chicken, frog, zebrafish, and tetraodon). The total size of the 8 input sequences is about 65000 bp.

We first ran Glam [START_REF] Frith | Finding Functionnal Sequence Elements by Multiple Local Alignement[END_REF], a multiple local alignment method 6 to find repetitions of length 100, taking 10 minutes and 45 seconds. We then ran Ed'Nimbus on the same sequences with L = 100, d = 8, r = 3 and k = 6. It took only 7.e -10 minutes to output filtered data on which we ran Glam finding the same repetition as in the previous case in 24 seconds, that is, almost 27 times faster with a very fast preprocessing.


ValueImpl

  Figure 1. Algorithm user-specified apart from provided interfaces and classes

FigureFigure 6 .

 6 Figure 2. Classes, interfaces and primitive types hierarchies


Rémi Forax

Étienne Duris

Gilles Roussel

A Simple Dispatch Technique for Pure Java Multi-Methods

published or not. The documents may come

CharacterData

T

  The fact that T could be the type of the 2nd argument of m3


Yongxin Liao
email: yongxin.liao@cran.uhp-nancy.fr

Mario Lezoche
email: mario.lezoche@cran.uhp-nancy.fr

Hervé Panetto
email: herve.panetto@cran.uhp-nancy.fr

Nacer Boudjlida
email: nacer.boudjlida@loria.fr

Semantic Annotation Model Definition for Systems Interoperability

Keywords: Semantic Annotation, Models, Ontology, Systems Interoperability

Semantic annotation is one of the useful solutions to enrich target's (systems, models, meta-models, etc.) information. There are some papers which use semantic enrichment for different purposes (integration, composition, sharing and reuse, etc.) in several domains, but none of them provides a complete process of how to use semantic annotations. This paper identifies three main components of semantic annotation, proposes for it a formal definition and presents a survey of current semantic annotation methods. At the end, we present a simple case study to explain how our semantic annotation proposition can be applied.The survey presented in this paper will be the basis of our future research on models, semantics and architecture for enterprises systems interoperability during the product lifecycle.

Introduction

Nowadays, the need of systems collaboration across enterprises and through different domains has become more and more ubiquitous. But because the lack of standardized models or schemas, as well as semantic differences and inconsistencies problems, a series of research for data/model exchange, transformation, discovery and reuse are carried out in recent years. One of the main challenges in these researches is to overcome the gap among different data/model structures. Semantic annotation is not only just used for enriching the data/model's information, but also it can be one of the useful solutions for helping semi-automatic or even automatic systems interoperability.

Semantically annotating data/models can help to bridge the different knowledge representations. It can be used to discover matching between models elements, which helps information systems integration [START_REF] Agt | Semantic Annotation and Conflict Analysis for Information System Integration[END_REF]. It can semantically enhance XML-Schemas' information, which supports XML documents transformation [START_REF] Köpke | Semantic Annotation of XML-Schema for Document Transformations[END_REF]. It can describe web services in a semantic network, which is used for further discovery and composition [START_REF] Talantikite | Semantic annotations for web services discovery and composition[END_REF]. It can support system modellers in reusing process models, detecting cross-process relations, facilitating change management and knowledge transfer [START_REF] Born | User-Friendly Semantic Annotation in Business Process Modeling[END_REF]. Semantic annotation can be widely used in many fields. It can link specific resources according to its domain ontologies.

The main contribution of this paper is identifying three main components of semantic annotation, giving a formal definition of semantic annotation and presenting a survey, based on the literature, of current semantic annotation methods that are applied for different purposes and domains. These annotation methods vary in their ontology (languages, tools and design), models and corresponding applications.

The remaining of this paper is organized as follows: Section 2 describes the definition of annotation and gives a formal definition of semantic annotations. Section 3 first provides the answers to why and where to use semantic annotation, then introduces the languages and tools that can be used to develop ontology, the design of semantic annotation structure models and the corresponding applications. Section 4 describes a simple case study example. Section 5 concludes this paper, together with some related work and potential extensions.

2

What is Semantic Annotation?

In Oxford Dictionary Online, the word "annotation" is defined as "a note by way of explanation or comment added to a text or diagram". It is used to enrich target object's information, which can be in the forms of text descriptions, underlines, highlights, images, links, etc. Annotation has special meanings and usages in different fields. In java programming, annotation can be added on classes, methods, variables, parameters, etc., for example, JUnit1 is a test framework that is based on java annotation. In mechanical drawing, an annotation is a snippet of text or symbols with specific meanings. In Library Management, an annotation is written in a set form (numbers, letters, etc.), which helps the classification of books. Further, different annotation types are identified by [START_REF] Bechhofer | The Semantics of Semantic Annotation[END_REF] and [START_REF] Boudjlida | A practical experiment on semantic enrichment of enterprise models in a homogeneous environment[END_REF]. They distinguished annotation as (i) Textual annotation: adding notes and comments to objects; (ii) Link annotation: linking objects to a readable content; (iii) Semantic annotation: that consists of semantic information (machine-readable). Similarly, three types of annotation are described in [START_REF] Oren | What are Semantic Annotations?[END_REF]: (i) Informal annotation: notes that are not machinereadable; (ii) Formal annotation: formally defined notes that are machine-readable (but it does not use ontology terms); (iii) Ontological annotation: notes that use only formally defined ontological terms (commonly accepted and understood).

According to the above classification, semantic annotation can be considered as a kind of formal metadata, which is machine and human readable.

Semantic Annotation

The term "Semantic Annotation" is described as "An annotation assigns to an entity, which is in the text, a link to its semantic description. A semantic annotation is referent to an ontology" in [START_REF] Talantikite | Semantic annotations for web services discovery and composition[END_REF]. Semantic annotation is concerned as "an approach to link ontologies to the original information sources" in [START_REF] Lin | Semantic Annotation for Process Models: Facilitating Process Knowledge Management via Semantic Interoperability[END_REF]. These definitions from different papers show one thing in common: a semantic annotation is the process of linking electronic resource to a specific ontology. Electronic resource can be text contents, images, video, services, etc. Ontology here is only one of the possible means to provide a formal semantic.

As it can be seen on Figure 1, the left side represents an Electronic Resource (ER) and on the right side, there are the three main components of semantic annotation: (1) Ontology, which defines the terms used to describe and represent a body of knowledge [START_REF] Boyce | Developing Domain Ontologies for Course Content[END_REF]. (2) Semantic Annotation Structure Model (SASM), which organizes the structure/schema of an annotation and describes the mappings between electronic resources and one, or more, ontologies. (3) Application, which is designed to achieve the user's purposes (composition, sharing and reuse, integration, etc.) by using SASM. This figure also shows the three main steps on how to use semantic annotation, which is introduced in section 3.

Formal Definition of Semantic Annotation

The following definition formally defines a semantic annotation: a Semantic Annotation is a tuple , consisting of the SASM and an application . ∶ , , Where:

, , … , , is the set of ontology that bring some meaning to any annotated element.

An Ontology is a 4-tuple ( , is_a, , ), where is a set of concepts, is_a is a partial order relation on , is a set of relation names, and : → is a function which defines each relation name with its arity [START_REF] Stumme | Ontology Merging for Federated Ontologies on the Semantic Web[END_REF].

Formally, : 〈 , 〉| represents the set of relationships between an element of the set of electronic resources and an element of the powerset of the ontology set . , is a binary relationship that maps to in the context of an application . It may represent four different kinds of semantic relations: (1) ∼ , : stating that is semantically equivalent to .

(2) ⊃ ,

: stating that subsumes the semantic of . (3) ⊂ , : stating that is subsumed by the semantic of . (4) ⋂ ,

: stating that intersects with the semantic of . can be further extended, including also some additional parameters or constraints c k , generally expressed using, in the worst case, natural language, or, better, a formal logical expression.

is then defined as ≔ , . The main issue, related to mappings such as in [START_REF] Köpke | Semantic Annotation of XML-Schema for Document Transformations[END_REF] and in [START_REF] Talantikite | Semantic annotations for web services discovery and composition[END_REF], is being able to measure the semantic gap [START_REF] Köpke | Semantic Annotation of XML-Schema for Document Transformations[END_REF] or the over semantic [START_REF] Talantikite | Semantic annotations for web services discovery and composition[END_REF], brought by the semantic annotation. Such measures have been studied by researchers in the domain of information retrieval [START_REF] Ellis | The Dilemma of Measurement in Information Retrieval Research[END_REF] or in the domain of ontology merging [START_REF] Stumme | Ontology Merging for Federated Ontologies on the Semantic Web[END_REF], matching [START_REF] Maedche | Measuring Similarity between Ontologies[END_REF], mapping [START_REF] Doan | Learning to map between ontologies on the semantic web[END_REF] and alignment [START_REF] Noy | PROMPT: Algorithm and Tool for Automated Ontology Merging and Alignment[END_REF].

In addition, [START_REF] Peng | A Novel Approach to Semantic Annotation Based on Multi-ontologies[END_REF] also gave a very simple definition of semantic annotation which is SA ∶ R, O , where R is set of resources and O is an ontology. Furthermore, [START_REF] Luong | A Rule-based Approach for Semantic Annotation Evolution[END_REF] defined it as SA ∶ R , C , P , L, T . In this definition, R is a set of resources; C is a set of concept names; P is a set of property names; L is a set of literal values; and T is a set of triple s, p, v , where s ∈ R , p ∈ P , v ∈ R ⋃L . To the best of our knowledge, T in this definition is duplicated.

3

Why, Where and How to use Semantic Annotation?

Semantic annotation uses ontology objects to enrich resource's information that tells a computer the meanings and relations of the data terms. It can be used to bridge the gap between modelsas additional information that helps description, discovery and composition.

Semantic Annotations are generally used in heterogeneous domains.We found several papers presenting different employments. [START_REF] Agt | Semantic Annotation and Conflict Analysis for Information System Integration[END_REF] used semantic annotations to annotate the model/object at CIM, PIM and PSM levels of the MDA approach [START_REF] Mellor | Model-Driven Architecture[END_REF], which helps information system integration. In the research of [START_REF] Köpke | Semantic Annotation of XML-Schema for Document Transformations[END_REF], a path expression method is developed for adding annotations to XML-Schemas. Then they transform paths to ontology concepts and use them to create XML-Schema mappings that help XML document transformation. [START_REF] Talantikite | Semantic annotations for web services discovery and composition[END_REF] used it to help matching and composition algorithm, which represents web services as a semantic network and produces the best composition plan. [START_REF] Born | User-Friendly Semantic Annotation in Business Process Modeling[END_REF] used semantic description of process artefacts to help graphical modelling of business processes. In the research of [START_REF] Lin | Semantic Annotation for Process Models: Facilitating Process Knowledge Management via Semantic Interoperability[END_REF], a semantic annotation framework is designed to manage the semantic heterogeneity of process model, to solve the discovery and sharing of process models problems in/between enterprise(s). In [START_REF] Patil | Meteor-S Web Service annotation framework[END_REF], an annotation framework is proposed for semi-automatically marking up web service descriptions (WSDL files) with domain ontologies to help web services discovery and composition. In the next three subsections we will present our proposed three semantic annotation components.

3.1

Step 1: Design or Select Ontology Design or select an appropriate ontology for semantic annotations is the first step of the annotation process. Ontology has been actively studied for a long period of time, and there are many research works proposing ontology-engineering techniques, such as Ontolingua2 , F-logic 3 , OWL 4 , etc. We are not going to give, here, a complete overview of every ontology languages, but we provide a brief introduction toseveral examples.

[1] designed a SMM (Semantic Meta-model) to describe domain ontologies. Artefacts in ontology are castigated as DomainFunction and DomainObject. The relations (predicates) among Objects and Functions are defined as: IsA, IsInputOf, IsOutputOf, Has, etc. A RDF-like triple (e.g., Tax Has TaxNumber) is used as the statement in SMM.

[4] used two kinds of ontologies: sBPMN5 ontology and a domain ontology. The first ontology is used to represent BPMN process models. The second ontology defines domain objects, states and actions according to objects lifecycle, which is used to provide the user advices during the modelling process.

[8] used Protégé OWL editor to design the ontology. In order to separately annotate meta-models (modelling language) and their process models, the author designs two ontologies: General Process Ontology (GPO) and Domain Ontology. The design of GPO is based on Bunge-Wand-Weber (BWW) Ontology [START_REF] Wand | On the ontological expressiveness of information systems analysis and design grammars[END_REF]. The Domain ontology is formalized according to SCOR6 specifications (Supply Chain Operations Reference-model).

3.2

Step 2: Design the Semantic Annotation Structure Model

The second component of a semantic annotation is SASM. It is the connection between electronic resources, applications and ontology concepts. A study in this direction is pursued by SAWSDL Working Group7 that developed SAWSDL [START_REF] Kopecký | SAWSDL: Semantic Annotations for WSDL and XML Schema[END_REF] (Semantic Annotation for Web Services Definition Language) which provides two kinds of extension attributes as follow: (i) modelReference, to describe the association between a WSDL or XML Schema component and a semantic model concept; (ii) liftingSchemaMapping and loweringSchemaMapping, to specify the mappings between semantic data and XML [START_REF] Martin | Towards Semantic Annotations of Web Services: OWL-S from the SAWSDL Perspective[END_REF].

To be more specific, we abstract four structure models that are designed for different requirements. Figure 2 below gives an overview of these three SASMs: Model A is proposed to conceptually represent a web service from [START_REF] Talantikite | Semantic annotations for web services discovery and composition[END_REF]; Model B is designed to annotate the business process model from [START_REF] Born | User-Friendly Semantic Annotation in Business Process Modeling[END_REF]; and Model C is the annotation model for an activity element which is part of the Process Semantic Annotation Model (PSAM) from [START_REF] Lin | Semantic Annotation for Process Models: Facilitating Process Knowledge Management via Semantic Interoperability[END_REF].

In order to compare above semantic annotation structure models, we identify five types for classifying the contents in SASM:

(1) identity of annotation;

(2) reference to ontology concept;

(3) reference to element (represent the relationship between element themselves); (4) text description, the natural language definitions of annotation contents;

(5) others (extinction contents, such as: execution time, restriction, etc.).

We can easily find that the basic components of SASMs are: identity of annotation and reference to ontology concepts; reference to element, text description and others are added for different usages. As examples, [START_REF] Talantikite | Semantic annotations for web services discovery and composition[END_REF] added "exec-time" into SASM to record the execution time of a web service request and used "inputs" and "outputs" to represent the relationships between processes; [START_REF] Born | User-Friendly Semantic Annotation in Business Process Modeling[END_REF] described the references with meaning of states of objects (current, before and after); [START_REF] Lin | Semantic Annotation for Process Models: Facilitating Process Knowledge Management via Semantic Interoperability[END_REF] adds "has_Actor-role" to denote the relationship between activity element and actor-role element. Furthermore, one to one mapping is not the only mapping type in SASM. For example, in Model A, there can be more than one input, which means the mapping between model content and ontology concept is one to many. Here, we analyses the mappings of "reference to ontology concepts".

Mappings are separated into two levels in the research of [START_REF] Lin | Semantic Annotation for Process Models: Facilitating Process Knowledge Management via Semantic Interoperability[END_REF]: meta-model level and model level. In the meta-model level the mappings are defined as: Atomic Construct, Enumerated Construct and Composed Construct. In model level, semantic relationships are: Synonym, Polysemy, Instance, Hyponym, Meronym, Holonymand Hypernym. Five mapping types are described in [START_REF] Agt | Semantic Annotation and Conflict Analysis for Information System Integration[END_REF]: single representation, containment, compositions, multiple and alternative representation.

In our opinions, there are three high level mapping types: 1 to 1 mapping, 1 to n mapping and n to 1 mapping (n to n is a combination of 1 to n and n to 1). For each of the mapping, we can design different semantic relationships for further usages. In 1 to 1 mapping semantic relationships can be like: "equal_to", "similar_to", etc. In 1 to n they can be as: "contains", "has", etc. In n to 1 they can be as: "part_of", "member_of", etc. One element can have several semantic relationships, but for each relationship, they belong to one mapping type.

Since the structure and semantic relationships are designed, we should consider how to implement the annotation process. It can be performed manually, semiautomatically or automatically. In the research of [START_REF] Lin | Semantic Annotation for Process Models: Facilitating Process Knowledge Management via Semantic Interoperability[END_REF], mapping is manually linking the process models to ontology. [START_REF] Patil | Meteor-S Web Service annotation framework[END_REF] developed algorithms to semi-automatically match and annotate WSDL files with relevant ontologies. Automatic mapping is, for the moment, restricted to some simple cases because of the impossibility to completely explicit knowledge from the different models.

3.3

Step 3: Develop the Application Once SASM step is accomplished, designers can begin to design the application to achieve their purpose (composition, sharing and reuse, integration, etc.). In several different domains semantic annotation methods are used to resolve particular problems.

In the domain of web services, [START_REF] Talantikite | Semantic annotations for web services discovery and composition[END_REF] presented a matching algorithm to process the "input" and "output" (SASM model C, Figure 3) of elements, and builds a semantic network. This network is explored by a composition algorithm, which automatically finds a composite service to satisfy the request;

In business process modelling domain, [START_REF] Born | User-Friendly Semantic Annotation in Business Process Modeling[END_REF] designed name-base and process context-base matchmaking functionalities to help user annotating process models. Name-base matching uses string distance metrics method for the matching between business process models and domain ontology. Process context-base matching uses the lifecycle (state before, state after, etc.) in domain ontology for suggesting the next activity during modelling.

[8] developed a prototype Process Semantic Annotation tool (Pro-SEAT), which is used to describe the relationship between process models and ontologies. They use Metis8 as a modelling environment integrating Protégé OWL API to provide an ontology browser. Ontologies are stored on an ontology server, which can be loaded by annotators. The output of the annotation is an OWL instance file that is used to support the process knowledge query, discovery and navigation from users.

Indeed, there are many tools and technologies that enable designing applications in semantic annotation. The selections are always depending on the design of SASM and ontology. In any case, all three components of semantic annotation are closely related.

A Simple Case Study

To explain how our semantic annotation proposition can be applied, we give a simple example to illustrate the annotation process between Sage X3 As can be seen in Figure 3, the ONTO-PDM product ontology, based on Tursi work [START_REF] Tursi | Ontological approach for Products-Centric Information System Interoperability in Networked Manufacturing Enterprises[END_REF], is used by both systems as the annotation source. In general cases two systems use different ontologies and the solution can be: mapping between each other; mapping with a reference ontology. Our solution provides SASM and its two main contents are "①identity of annotation", "②reference to ontology concept". The annotate process is performedmanually by a domain expert. Element "BillOfMaterialsID" in Sage X3 model is annotated as semantic annotation SA 1 , which is referenced to the ontology concept "MaterialEntity"; Element "BomNumber" in Flexnet model is annotated as semantic annotation SA 2 , which is referenced to the same ontology concept "MaterialEntity". (id 1 is the identity parameter that refers to"id-sageX3-01"). Similarly, SA 2 can be formally described as

SA ∼ _ . , , ,
.Through the comparisonof SA 1 and SA 2 , application A can match the two different models concepts. However, the design of our semantic annotation model definition still needs to be further developed. We will discuss the possible problems and future work in the last section.

CONCLUSIONS

In this paper, a brief survey of semantic annotation in different domains is presented. We identify three main components of semantic annotations that are Ontology, SASM and Application. In addition, a formal definition of semantic annotation is proposed. It contributes to better understand what a semantic annotation is and proposes a common reference model. But, how using semantic annotation? There are still many problems can be further discussed during the annotation process. For example, how to optimize ontology and an annotated model? How to solve the inconsistency or conflicts during the mapping? How to add consistent semantic on models in different levels of a system? How to achieve semi-automatic or automatic annotation?

We are currently investigating how semantic annotations can help collaborative actors (organizations, design teams, system developers, etc.) in co-designing, sharing, exchanging, aligning and transforming models. In particular, this research work will be based on general systems with several kinds of interactions. We can have interoperation between systems that with different versions (during many years, systems may have been modified or updated). We can also have systems with same functions but used by different enterprises. Semantic annotations can bridge this knowledge gap and identify differences in models, in schemas, etc. In some case, interoperation is a process between a set of related systems throughout a product lifecycle (Marketing, Design, Manufacture, Service, etc.), and semantic annotations can influence the existing foundations and techniques which supports models reuse, semantic alignment and transformation, etc. Above all, our research work will focus on designing, and reusing appropriate ontologies in relationship with a formal semantic annotation structure model.

Fig. 1 .

 1 Fig.1. Semantic Annotation components.

Fig. 2 .

 2 Fig.2. Semantic Annotation Structure Model Examples.

Fig. 3 .

 3 Fig. 3. Semantic Annotation between Sage X3 and FlexnetSemanticAnnotation SA 1 can be formally described as SA

1 ①id

 1 10 http://www.apriso.com/products/flexnet_production/ SA

  9 , an Enterprise Resource Planning (ERP) model and Flexnet 10 , a Manufacturing Execution System (MES) model focused on Bill of Materials concept.

http://www.junit.org/

http://www.ksl.stanford.edu/software/ontolingua/

http://flora.sourceforge.net/

http://www.w3.org/TR/owl-features/

http://www.ip-super.org

http://supply-chain.org/

http://www.w3.org/2002/ws/sawsdl/#Introduction

http://www.troux.com/

http://www.sage.com