Guillaume Blin
email: gblin@univ-mlv.fr

Minghui Jiang
email: mjiang@cc.usu.edu

Stéphane Vialette
email: vialette@univ-mlv.fr

The longest common subsequence problem with crossing-free arc-annotated sequences

An arc-annotated sequence is a sequence, over a given alphabet, with additional structure described by a -possibly empty -set of arcs, each arc joining a pair of positions in the sequence. As a natural extension of the longest common subsequence problem, Evans introduced the LONGEST ARC-PRESERVING COMMON SUBSEQUENCE (LAPCS) problem as a framework for studying the similarity of arc-annotated sequences. This problem has been studied extensively in the literature due to its potential application for RNA structure comparison, but also because it has a compact definition. In this paper, we focus on the nested case where no two arcs are allowed to cross because it is widely considered the most important variant in practice. Our contributions are three folds: (i) we revisit the nice NP-hardness proof of Lin et al. for LAPCS(NESTED, NESTED), (ii) we improve the running time of the FPT algorithm of Alber et al. from O(3.31 k 1 +k 2 n) to O(3 k 1 +k 2 n), where resp. k1 and k2 deletions from resp. the first and second sequence are needed to obtain an arc-preserving common subsequence, and (iii) we show that LAPCS(STEM, STEM) is NP-complete for constant alphabet size.

.

In an arc-annotated sequence (S, P ), two arcs (i 1 , j 1 ) and (i 2 , j 2 ) are crossing, if

, Evans has introduced a five level hierarchy 1 for arc-annotated sequences that is described as follows: UNLIMITED: no restriction at all, CROSSING: each base is incident to at most one arc, NESTED: each base is incident to at most one arc and no two arcs are crossing, STEM: each base is incident to at most one arc, and given any two arcs one is nested into the other, and PLAIN: there is no arc. This hierarchy is clearly organized according to the following chain of inclusions: PLAIN ⊂ STEM ⊂ NESTED ⊂ CROSSING ⊂ UNLIMITED.

Let (S 1 , P 1 ) and (S 2 , P 2 ) be two arc-annotated sequences. If S 1 [i] = S 2 [j] for some pair of integers i and j (1

with (i, k) ∈ P 1 and (j, l) ∈ P 2 , we refer to the pair ( i, k , j, l ) as an arc-match. A common subsequence T of S 1 and S 2 can be viewed as a set of pairwise disjoint base-matches

.

 presented two FPT algorithm for the LAPCS(NESTED,NESTED) problem. Given two arc-annotated sequences of maximum length n, their first algorithm decides in O((3|Σ|) n) time whether the two sequences have an arc-preserving common subsequence of length , and their second algorithm decides in O(3.31 k1+k2 n) time whether an arc-preserving common subsequence can be obtained by deleting k 1 letters from the first sequence and k 2 letters from the second sequence. Improving the exponential running times of the two algorithms was left as an immediate open question.

Introduction

Structure comparison for RNA has become a central computational problem bearing many computer science challenging questions. Indeed, RNA secondary structure comparison is essential for (i) identification of highly conserved structures during evolution (which cannot always be detected in the primary sequence, since it is often unpreserved) which suggest a significant common function for the studied RNA molecules, (ii) RNA classification of various species (phylogeny), (iii) RNA folding prediction by considering a set of already known secondary structures, and (iv) identification of a consensus structure and consequently of a common role for molecules. From an algorithmic point of view, RNA structure comparison was first considered in the framework of ordered trees [START_REF] Shasha | Simple fast algorithms for the editing distance between trees and related problems[END_REF] and, later on, in the one of arc-annotated sequences [START_REF] Evans | Finding common subsequences with arcs and pseudoknots[END_REF]. An arc-annotated sequence over some fixed alphabet Σ is a pair (S, P ), where S (the sequence) is a string of Σ * and P (the annotation) is a set of arcs {(i, j) : 1 ≤ i < j ≤ |S|}. In the context of RNA structures, S is a sequence of RNA bases and P represents hydrogen bonds between pairs of elements of S. From a purely combinatorial point of view, arc-annotated sequences are a natural extension of simple sequences. However, using arcs for modeling non-sequential information together with restrictions on the relative positioning of arcs allow for varying restrictions on the structure of arc-annotated sequences. Observe that a (plain) sequence without any arc can be viewed as an arc-annotated sequence with an empty arc set. Moreover, Alber et al. [START_REF] Alber | Computing the similarity of two sequences with nested arc annotations[END_REF] noted that their second algorithm relies on a breadth-first search that is very space-consuming, and asked whether it can be replaced by a simple depth-first search. Our paper makes the following contributions. First, w e revisit the nice NP-hardness proof of Lin et al. [START_REF] Lin | The longest common subsequence problem for sequences with nested arc annotations[END_REF] for the LAPCS(NESTED, NESTED) problem. We point out a problem an provide a simple solution. Second, we improve the running time of the (second) FPT algorithm of Alber et al. [START_REF] Alber | Computing the similarity of two sequences with nested arc annotations[END_REF] from O(3.31 k1+k2 n) to O(3 k1+k2 n). Our algorithm uses the bounded search tree technique, and can be implemented using a simple depth-first search. Third, we show that the LAPCS(STEM, STEM) problem is NP-complete for constant alphabet size. The proof is by a tricky modification of [START_REF] Hamel | Comparing RNA structures with biologically relevant operations cannot be done without strong combinatorial restrictions[END_REF].

LAPCS(NESTED, NESTED) is NP-complete

In this section we prove that the LAPCS(NESTED, NESTED) problem is NP-complete even if both arc-annotated sequences are unary. We actually point out a problem in a previous proof by Lin et al. [START_REF] Lin | The longest common subsequence problem for sequences with nested arc annotations[END_REF] for the same result, and give a simple solution for the correctness of the proof. Our proof is for a large part the same as the proof of Lin et al. [START_REF] Lin | The longest common subsequence problem for sequences with nested arc annotations[END_REF]. The only difference is that we use larger "barriers" of length Ω(n) each. Our counter-example graph for the proof of Lin et al. [START_REF] Lin | The longest common subsequence problem for sequences with nested arc annotations[END_REF] is presented Figure 1. The graph A has 4 vertices v 1 , v 2 , v 3 and v 4 . The graph G has n = 4t vertices, and consists of t copies A 1 , A 2 , . . . , A t of the graph A linked into a circular "list" (for convenience let A 0 = A t and A t+1 = A 1 ) by one additional edge from the vertex v 1 of each A i to the vertex v 4 of A i-1 . One can easily verified that G is cubic, planar, bridgeless, and connected. Moreover, G has a natural two-page book embedding such that each vertex is incident to at least 1 and at most 2 edges on each page, as illustrated in Figure 1. We have the following lemma about the graph G.

Lemma 1. The maximum cardinality k * of an independent set in the graph G is 3 8 n .

We now turn to pointing out the problem in the proof of Lin et al. [START_REF] Lin | The longest common subsequence problem for sequences with nested arc annotations[END_REF]. Refer to Figure 2 for the construction of the two arc-annotated sequences P 1 and P 2 based on the graph G according to the reduction of Lin et al. [START_REF] Lin | The longest common subsequence problem for sequences with nested arc annotations[END_REF]. As illustrated by the dotted lines between the two sequences, the two arc-annotated sequences (S 1 , P 1 ) and (S 2 , P 2 ) has an arc-preserving common subsequence of length = 8n + 3+2 2 n -6 = 10n + 1 2 n -6. Lin et al. [START_REF] Lin | The longest common subsequence problem for sequences with nested arc annotations[END_REF] claimed that every LAPCS can be transformed into a good LAPCS (of the same length). We show that this claim is wrong. Following their proof, the graph G has an independent set of cardinality k if and only if (S 1 , P 1 ) and (S 2 , P 2 ) have a good LAPCS of length 8(n + 1) + 2n + k = 10n + k + 8. Then, by Lemma 1, the maximum length of a good LAPCS of (S 1 , P 1 ) and (S 2 , P 2 ) is at most good = 10n + 3 8 n + 8. Note that for t > 28 and correspondingly n = 4t > 112, we have > good . This disproves their claim. For a correct proof, we increase the length of each separating block in the reduction from 8 to s = 4n. Then, following their proof, the length of an LAPCS is at least s(n + 1) + 2n + k * . If a common subsequence has a far match i, j such that |j -i| ≥ n, then in each sequence there must be at least n unmatched bases on each side of the match. It follows that the length of the common subsequence is at most s(n + 1) + 4n -2n, which is less than s(n + 1) + 2n + k * . Therefore every match i, j of an LAPCS must be near, i.e., |j -i| < n. By the same argument, an LAPCS must include at least one arc from each separating block in each sequence, because otherwise a separating block with no arcs in the LAPCS would have at least 4n/2 = 2n unmatched bases. Since all matches must be near, any arc (i 1 , i 2 ) in the LAPCS that comes from a separating block in P 1 must match an arc (j 1 , j 2 ) from the corresponding separating block in P 2 such that either

i 1 ≤ j 1 ≤ j 2 ≤ i 2 or j 1 ≤ i 1 ≤ i 2 ≤ j 2 .
Then a simple replacement argument shows that all separating blocks are matched completely, and consequently any LAPCS can be transformed into a good LAPCS of the same length.

A faster algorithm for the LAPCS(NESTED, NESTED) problem

Theorem 1. There is an O(3 k1+k2 n)-time algorithm for LAPCS(NESTED,NESTED) that decides whether an arc-preserving common subsequence of two arc-annotated sequences of maximum length n can be obtained by deleting k 1 letters from the first sequence and k 2 letters from the second sequence.

We first observe that the two parameters k 1 and k 2 are not independent. Let n 1 and n 2 be the lengths of the two sequences. Then the problem admits a valid solution only if

n 1 -k 1 = n 2 -k 2 .
Without loss of generality, we use a single parameter k = k 1 + k 2 for the total number of letters deleted from the two arc-annotated sequences. The running time of our algorithm is thus O(3 k n). For an arc-annotated sequence S and an index i, define buddy(S, i) = j if S[i] is connected to S[j] by an arc, and buddy(S, i) = 0 otherwise. For an arc-annotated sequence S of length n and two indices i ≤ j, denote by S[i, j] the subsequence obtained from S by deleting letters S [START_REF] Alber | Computing the similarity of two sequences with nested arc annotations[END_REF], S [START_REF] Blin | Algorithms in Computational Molecular Biology: Techniques, Approaches and Applications, chapter Algorithmic Aspects of Arc-Annotated Sequences[END_REF], . . . , S[i -1] and S[j + 1], S[j + 2], . . . , S[n] together with the incident arcs. For an arc-annotated sequence S and three indices i ≤ j ≤ k, denote by S[i, j, k] the subsequence obtained from S[i, k] by deleting S[j] and its incident arc (if any).

Algorithm lapcs(S, T, k) Input: Two arc-annotated sequences S and T , an integer k. Output: returns k * -the minimum number of letters that must be deleted from S and T to obtain an arc-preserving common subsequence -if

k * ≤ k; ∞ otherwise.
The algorithm is recursive. For the base case, the algorithm returns 0 if S = T and k ≥ 0, and returns ∞ if S = T and k ≤ 0. For the inductive case, the algorithm tries all applicable following cases and returns the minimum value. Let s and t be the lengths of the two sequences S and T , respectively. Put i = buddy(S, 1) and j = buddy(T, 1).

Case 1 S[1] = T [1]. -Delete S[1], then return lapcs(S[2, s], T, k -1) + 1. -Delete T [1], then return lapcs(S, T [2, t], k -1) + 1. Case 2.1 S[1] = T [1], i = j = 0. -Match S[1] ∼ T [1], then return lapcs(S[2, s], T [2, t], k). Case 2.2 S[1] = T [1], i > 0 and j = 0. -Delete S[1], then return lapcs(S[2, s], T, k -1) + 1. -Delete T [1], then return lapcs(S, T [2, t], k -1) + 1. -Delete S[i], match S[1] ∼ T [1], then return lapcs(S[2, i, s], T [2, t], k -1) + 1. Case 2.3 S[1] = T [1], i = 0 and j > 0. -Delete S[1], then return lapcs(S[2, s], T, k -1) + 1. -Delete T [1], then return lapcs(S, T [2, t], k -1) + 1. -Delete T [j], match S[1] ∼ T [1], then return lapcs(S[2, s], T [2, j, t], k -1) + 1. Case 2.4 S[1] = T [1], i > 0 and j > 0, S[i] = T [j]. -Delete S[1], then return lapcs(S[2, s], T, k -1) + 1. -Delete T [1], then return lapcs(S, T [2, t], k -1) + 1. -Delete S[i] and T [j], match S[1] ∼ T [1], then return lapcs(S[2, i, s], T [2, j, t], k - 2) + 2. Case 2.5.1 S[1] = T [1], i > 0 and j > 0, S[i] = T [j], S[2, i -1] = T [2, j -1]. -Match S[1, i] ∼ T [1, j], then return lapcs(S[i + 1, s], T [j + 1, t], k). Case 2.5.2 S[1] = T [1], i > 0 and j > 0, S[i] = T [j], S[i + 1, s] = T [j + 1, t]. -Match S[1] ∼ T [1] and S[i, s] ∼ T [j, t], then return lapcs(S[2, i-1], T [2, j -1], k). Case 2.5.3 S[1] = T [1], i > 0 and j > 0, S[i] = T [j], ∃a : S[2, a, i -1] = T [2, j -1]. -Delete S[1], then return lapcs(S[2, s], T, k -1) + 1. -Delete T [1], then return lapcs(S, T [2, t], k -1) + 1. -Delete S[a], match S[1, a, i] ∼ T [1, j], then return lapcs(S[i + 1, s], T [j + 1, t], k - 1) + 1. Case 2.5.4 S[1] = T [1], i > 0 and j > 0, S[i] = T [j], ∃b : S[2, i -1] = T [2, b, j -1]. -Delete S[1], then return lapcs(S[2, s], T, k -1) + 1. -Delete T [1], then return lapcs(S, T [2, t], k -1) + 1. -Delete T [b], match S[1, i] ∼ T [1, b, j], then return lapcs(S[i + 1, s], T [j + 1, t], k - 1) + 1. Case 2.5.5 S[1] = T [1], i > 0 and j > 0, S[i] = T [j], ∃a : S[i + 1, a, s] = T [j + 1, t].
-Delete S [START_REF] Alber | Computing the similarity of two sequences with nested arc annotations[END_REF], then return lapcs(S[2, s], T, k -1) + 1.

-Delete T [1], then return lapcs(S, T [2, t], k -1) + 1. -Delete S[a], match S[1] ∼ T [1] and S[i, a, s] ∼ T [j, t], then return lapcs(S[2, i - 1], T [2, j -1], k -1) + 1. Case 2.5.6 S[1] = T [1], i > 0 and j > 0, S[i] = T [j], ∃b : S[i + 1, s] = T [j + 1, b, t].
-Delete S [START_REF] Alber | Computing the similarity of two sequences with nested arc annotations[END_REF], then return lapcs(S[2, s], T, k -1) + 1.

-Delete T [1], then return lapcs(S, T [2, t], k -1) + 1. -Delete T [b], match S[1] ∼ T [1] and S[i, s] ∼ T [j, b, t], then return lapcs(S[2, i - 1], T [2, j -1], k -1) + 1. Case 2.5.7 S[1] = T [1], i > 0 and j > 0, S[i] = T [j], S[2, i -1] = T [2, j -1], S[i+1, s] = T [j +1, t], ∀a : S[2, a, i-1] = T [2, j -1], ∀a : S[i+1, a, s] = T [j +1, t], ∀b : S[2, i -1] = T [2, b, j -1], ∀b : S[i + 1, s] = T [j + 1, b, t]. -Delete S[1], then return lapcs(S[2, s], T, k -1) + 1. -Delete T [1], then return lapcs(S, T [2, t], k -1) + 1. -Delete S[i] and T [j], match S[1] ∼ T [1], then return lapcs(S[2, i, s], T [2, j, t], k - 2) + 2. -Match S[1] ∼ T [1] and S[i] ∼ T [j], compute k = lapcs(S[2, i -1], T [2, j - 1], k -2) + lapcs(S[i + 1, s], T [j + 1, t], k -2),, then return k if k ≤ k, or ∞ if k > k.
The correctness of the algorithm is self-evident for the cases from 1 to 2.5.2. To justify the four cases from 2.5.3 and 2.5.6, we have the following easy lemma. Lemma 2. For each case from 2.5.3 to 2.5.6, if the condition of the case is met, then there is an optimal solution that corresponds to one of the three branches for that case.

Finally, the condition for case 2.5.7 ensures that at least two deletions are necessary in each of the two subproblems for (S[2, i -1], T [2, j -1]) and (S[i + 1, s], T [j + 1, t]). Thus in the last branch of this case, it is sufficient to set the third parameter to k -2 in the two recursions. In terms of time complexity, the seven cases 2.2, 2.3, and 2.5.3-2.5.7 are the worst cases. The six cases 2.2, 2.3, and 2.5.3-2.5.4 correspond to the characteristic polynomial equation 1 = x -1 + x -1 + x -1 ; the last case 2.5.7 corresponds to the characteristic polynomial equation 1 = x -1 +x -1 +x -2 +(x -2 +x -2 ). Both equations have a unique positive real root x 0 = 3.

LAPCS(STEM, STEM) for constant alphabet size

The LAPCS(STEM, STEM) problem turns out to be of particular interest for RNA practical issues [START_REF] Guignon | An edit distance between rna stem-loops[END_REF]. This problem has been shown to be NP-complete for arbitrarily large alphabets [START_REF] Hamel | Comparing RNA structures with biologically relevant operations cannot be done without strong combinatorial restrictions[END_REF]. This section is devoted to investigating the LAPCS(STEM, STEM) problem for constant alphabet size. We first make the easy observation that the LAPCS(STEM, STEM) problem for an alphabet of size 1 admits a polynomial-time exact algorithm by dynamic programming. Unfortunately, this approach cannot be pushed too far. Indeed, we now show that the constant alphabet size assumption is not enough to gain tractability for the LAPCS(STEM,STEM) problem.

Theorem 2. The LAPCS(STEM,STEM) problem is NP-complete for constant alphabet size.

To prove hardness, we propose a reduction from the NP-complete 3-SAT problem [START_REF] Garey | Computers and Intractability: A guide to the theory of NP-completeness[END_REF] which is defined as follows: Given a collection C q = {c 1 , c 2 , . . . , c q } of q clauses, where each clause is the disjunction of 3 literals on a finite set of n boolean variables V n = {x 1 , x 2 , . . . , x n }, determine whether there exists a truth assignment to the variables so that each clause has at least one true literal. Let (C q , V n ) be an arbitrary instance of the 3-SAT problem. For convenience, let L j i denote the jth literal of the ith clause (i.e. c i ) of C q . In the following, given a sequence S over an alphabet Σ, let occ(i, c, S) denote the ith occurrence of the letter c in S. We build two arc-annotated sequences (S 1 , P 1 ) and (S 2 , P 2 ) as follows. An illustration of a full example is given in figures 3 and4, where n = 4 and q = 3. For readability reasons, the arc-annotated sequences resulting from the construction have been split into several parts and a schematic overview of the overall placement of each part is provided.

Let S 1 and S 2 be the two sequences defined as follows:

S 1 = C 1 q S C 1 q-1 . . . C 1 2 S C 1 1 S S 1 M S P 1 1 S P 1 2 . . . P 1 q-1 S P 1 q S 2 = C 2 q S C 2 q-1 . . . C 2 2 S C 2 1 S S 2 M S P 2 1 S P 2 2 . . . P 2 q-1 S P 2 q
where, for all 1 ≤ i ≤ q and 1 ≤ k ≤ n,

-S = 2 β -C 1 i = 9 δ 6 γ 8 δ 6 γ X 1 1 X 1 2 . . . X 1 n 6 γ 8 δ 6 γ 7 δ with X 1 k = 0 s j 1 2 α if x k = L j i or x k = L j i , with s 1 = 3, s 2 = 4 and s 3 = 5; X 1 k = 0 1 2 α otherwise; -P 1 i = 6 γ 6 γ 9 δ X 1 n . . . X 1 n 2 +1 8 δ X 1 n 2 . . . X 1 1 7 δ 6 γ 6 γ s.t. X 1 k = 1 0 2 α ; -C 2 i = X 2 1 . . . X 2 n 9 δ 6 γ X 2 1 . . . X 2 n 2 8 δ X 2 n 2 +1 . . . X 2 n 6 γ 7 δ X 2 1 . . . X 2 n s.t. ∀1 ≤ j ≤ 3, occ(j, X 2 k , C 2 i ) = 1 0 s j 2 α (resp. s j 1 0 2 α ) if x k = L j i (resp. x k = L j i ), with s 1 = 3, s 2 = 4 and s 3 = 5; occ(j, X 2 k , C 2 i ) = 1 0 2 α otherwise; -P 2 i = (0 1 2 α ) n 7 δ 6 γ (0 1 2 α ) n 2 8 δ (0 1 2 α ) n 2 6 γ 9 δ (0 1 2 α ) n .
Moreover, let S 1 M = (0 1 2 α ) n and S 2 M = (1 0 2 α ) n . Notice that, by construction, there is only one occurrence of each {3, 4, 5} in

C 2 i . Moreover, let α = 2n + 1, β = |S 1 M |+ 1≤i≤q (|C 1 i |+|P 1 i |), δ = α(n+1
) and γ = 5δ+4 . Let us now define P 1 and P 2 . For all 1 ≤ i ≤ q -1, (1) add an arc in P 1 between occ(k, 0, 2) add an arc in P 2 between occ(j * k, 0, 3) add an arc in P 2 between occ(k, j, C 2 i ) and occ(d + 1 -k, j, P 2 i ), ∀j ∈ {7, 8, 9} and 1 ≤ k ≤ δ (see Fig. 3.c, 4.a and 4.c). Clearly, this construction can be achieved in polynomial-time, and yields to sequences (S 1 , P 1 ) and (S 2 , P 2 ) that are both of type STEM. We now give an intuitive description of the different elements of this construction. Each clause c i ∈ C q is represented by a pair (C 1 i , C 2 i ) of sequences. The sequence C 2 i is composed of three subsequences representing a selection mechanism of one of the three literals of c i . The pair (S 1 M , S 2 M ) of sequences is a control mechanism that will guarantee that a variable x k cannot be true and false simultaneously. Finally, for each clause c i ∈ C q , the pair (P 1 i , P 2 i ) of sequences is a propagation mechanism which aim is to propagate the selection of the assignment (i.e. true or false) of any literal x k all over C q . Notice that all the previous intuitive notions will be detailed and clarified afterwards. In the sequel, we will refer to any such construction as a snail-construction. In order to complete the instance of the LAPCS(STEM, STEM) problem, we set k = |S 1 | -ε with ε = q(2(n + 2δ + 2γ + 1)) + n. (the desired length of the solution). Let (S 1 , P 1 ) and (S 2 , P 2 ) denote the arc-annotated sequences obtained by a snail-construction. We will denote S d the set of symbols deleted in a solution of the LAPCS problem on (S 1 , P 1 ) and (S 2 , P 2 ) (i.e. the symbols that do not belong to the common subsequence). We need some technical lemmas (proofs deferred to Appendix) Lemma 3. Any optimal solution of the LAPCS(STEM, STEM) problem on (S 1 , P 1 ) and

C 1 i ) (resp. occ(k, 1, C 1 i )) and occ(n -k + 1, 0, P 1 i+1 ) (resp. occ(n -k + 1, 1, P 1 i+1 )), ∀1 ≤ k ≤ n (see
C 2 i ) (resp. occ(j * k, 1, C 2 i )) and occ(3n -jk + 1, 0, P 2 i ) (resp. occ(3n -jk + 1, 1, P 2 i )), ∀1 ≤ j ≤ 3, 1 ≤ k ≤ n (see
(S 2 , P 2 ) is of length |S 1 | -ε. Lemma 4.
In any optimal solution of the LAPCS(STEM, STEM) problem on (S 1 , P 1 ) and

(S 2 , P 2 ), if occ(k, 1, S 1 M ) (resp. occ(k, 0, S 1 M )) for a given 1 ≤ k ≤ n is deleted then, ∀1 ≤ j ≤ q, occ(k, 1, C 1 j ) (resp. occ(k, 0, C 1 j )) is deleted.
The following lemma proves Theorem 2.

Theorem 3. Given an instance of the problem 3SAT with n variables and q clauses, there exists a satisfying truth assignment if and only if the LAPCS(STEM, STEM) problem for (S 1 , P 1 ) and (S 2 , P 2 ) is of length k = |S 1 | -ε. Proof. (⇒) An optimal solution for C q = (x 1 ∨x 2 ∨x 3 )∧(x 1 ∨x 2 ∨x 4 )∧(x 2 ∨x 3 ∨x 4 ) -i.e. x 1 = x 3 = true and x 2 = x 4 = f alse -is illustrated in figures 3 and 4 where any symbol over a grey background have to be deleted. Suppose we have a solution for our 3-SAT instance, that is an assignment of each variable of V n satisfying each clause of C q . Let us first list all the symbols to delete in S 1 . For all 1 ≤ k ≤ n, if x k = f alse then delete, ∀1 ≤ j ≤ q, {occ(k, 0, C 1 j ), occ(k, 1, P 1 j )} and occ(k, 0, S 1 M ); otherwise delete, ∀1 ≤ j ≤ q, {occ(k, 1, C 1 j ), occ(k, 0, P 1 j )} and occ(k, 1, S 1 M ). For each L j i satisfying c i with the biggest index j with 1 ≤ i ≤ q, if (1) j = 1 then from C 1 i , delete all the symbols 9, the two first substrings of γ symbols 6, the first substring of δ symbols 8, symbols 4 and 5. Moreover, from P 1 i delete all the symbols 7 and 8, the two last substrings of γ symbols 6 (cf Fig. 3.c); if (2) j = 2 then from C 1 i , delete all the symbols 8, the first and the last substrings of γ symbols 6, symbols 3 and 5. Moreover, from P 1 i delete all the symbols 7 and 9, the first and the last substrings of γ symbols 6 (cf Fig. 4.a); if (3) j = 3 then from C 1 i , delete all the symbols 7, the two last substrings of γ symbols 6, the last substring of δ symbols 8, symbols 3 and 4. Moreover, from P 1 i delete all the symbols 8 and 9, the two first substrings of γ symbols 6 (cf Fig. 4.c);

Let us now list all the symbols in S 2 to be deleted. For all

1 ≤ k ≤ n, if x k = f alse then delete occ(k, 0, S 2 M ); otherwise delete occ(k, 1, S 2 M ). For each L j i satisfying c i with the biggest index j with 1 ≤ i ≤ q, if (1)
j = 1 then, in C 2 i , delete all the symbols not in {6, 7, 8} appearing after occ(1, 9,

C 2 i ) (included). Moreover, if x k = f alse with 1 ≤ k ≤ n then delete, occ(k, 0, C 2 i ), otherwise delete occ(k, 1, C 2 i ) (cf Fig. 3.c).
2 i ) (included). Moreover, if x k = f alse with 1 ≤ k ≤ n then delete, occ(2n + k, 0, C 2 i ), otherwise delete occ(2n + k, 1, C 2 i ) (cf Fig. 4.c). Moreover, in P 2
i , delete all the symbols not in {6, 7} appearing after occ(1, 7, P

i ). Moreover, if x k = f alse with 1 ≤ k ≤ n then delete, occ(n -k + 1, 0, P 2
i ), otherwise delete occ(n -k + 1, 1, P 2 i ) (cf Fig. 4.c); By construction, the natural order of the symbols of S 1 and S 2 allows the corresponding set of undeleted symbols to be conserved in a common arc-preserving common subsequence between (S 1 , P 1 ) and (S 2 , P 2 ). Let us now prove that the length of this last is k . One can easily check that in this solution, in S 1 , n symbols have been deleted from S 1 M and ∀1 ≤ i ≤ q, 2δ +2γ +n+2 symbols from C 1 i and 2δ +2γ +n symbols from P 1 i have been deleted. Thus, the length of the solution is |S 1 | -[q(2(n + 2δ + 2γ + 1)) + n].

(⇐) Suppose we have an optimal solution -i.e. a set of symbols S d to delete -for LAPCS of (S 1 , P 1 ) and (S 2 , P 2 ). Let us define the truth assignment of V n s.t., ∀1 ≤ i ≤ q, if in C 1 i symbol 3 is not deleted, then the first literal of clause c i (i.e. L 1 i ) is true; if in C 1 i symbol 4 is not deleted, then the second literal of clause c i (i.e. L 2 i ) is true; if in C 1 i symbol 5 is not deleted, then the third literal of clause c i (i.e. L 3 i ) is true;. Let us prove that it is a solution for our 3-SAT instance. By construction, if L j i = x k (resp. x k ) then in C 1 i , symbol 2 + j (i.e. 3, 4 or 5) appears between occ(k, 0, C 1 i ) and occ(k, 1, C 1 i ) whereas in C 2 i it appears after occ(k, 1, C 2 i ) (resp. before occ(k, 0, C 2 i )). Thus, if symbol 2 + j (i.e. 3, 4 or 5) in C 1 i is not deleted then occ(k, 1, C 1 i ) (resp. occ(k, 0,

C 1 i )) in C 1 i is deleted if L j i = x k (resp.
x k ). Consequently, according to the proof of Lemma 4, if symbol 2+j (i.e. 3, 4 or 5) in C 1 i is not deleted then occ(k, 1, C 1 i ) (resp. occ(k, 0, C 1 i )) in all C 1 i , with 1 ≤ i ≤ q is deleted if L j i = x k (resp. x k ). Therefore, we can ensure that one cannot obtain L j i and L j i being true whereas L j i = L j i (that is a variable cannot be simultaneously true and false). By Lemma 3, we can ensure that for any 1 ≤ i ≤ q exactly one of {3, 4, 5} is conserved in C 1 i .

Fig. 1 .

 1 Fig. 1. The counter-example graph G.

Fig. 2 .

 2 Fig. 2. The two arc-annotated sequences P1 and P2 for the graph G. The separating blocks, each of length 8, are illustrated by large dots.

  Fig. 3.d and 4.b); (

  Fig. 3.c, 4.a and 4.c); (

Fig. 3 .

 3 Fig. 3. Considering Cq = (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x4) ∧ (x2 ∨ x3 ∨ x4). For readability, all the arcs have not been drawn, consecutive arcs are representing by a unique arc with lines for endpoints. Symbols over a grey background may be deleted to obtain an optimal LAPCS. a) A schematic view of the overall arrangement of the components of the two a.a. sequences. b) Description of S 1 M , S 2 M , P 1 1 , P 2 1 and the corresponding arcs in P1. c) Description of C 1 1 , C 2 1 , P 1 1 , P 2 1 and the corresponding arcs in P2. d) Description of C 1 1 , C 2 1 , P 1 2 , P 2 2 and the corresponding arcs in P1.

Fig. 4 .

 4 Fig. 4. Considering Cq = (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x4) ∧ (x2 ∨ x3 ∨ x4). For readability all the arcs have not been drawn, consecutive arcs are representing by a unique arc with lines for endpoints. Symbols over a grey background may be deleted to obtain an optimal LAPCS. a) Description of C 1 2 , C 2 2 , P 1 2 , P 2 2 and the corresponding arcs in P2. c) Description of C 1 2 , C 2 2 , P 1 3 , P 2 3 and the corresponding arcs in P1. d) Description of C 1 3 , C 2 3 , P 1 3 , P 2 3 and the corresponding arcs in P2.

  Moreover, in P 2 i , delete all the symbols not in {6, 9} appearing before occ(1, 9, P 2 i ). Moreover, if x k = f alse with 1 ≤ k ≤ n then delete, occ(3n-k +1, 0, P 2

	i ), otherwise delete occ(3n-k +1, 1, P 2 i )
	(cf Fig. 3.c);
	if (2) j = 2 then, in C 2 i , delete all the symbols 8 and all the symbols appearing before occ(1, 9, C 2
	i ) i , delete all the symbols appearing before occ(1, 6, P 2 (cf Fig. 4.a). Moreover, in P 2 i ) (excluded) or after occ(2γ, 6, P 2
	2 i ) (cf Fig.
	4.a);
	if (3) j = 3 then, in C 2 i , delete all the symbols not in {6, 8, 9} appearing before
	occ(δ, 7, C

i ) (excluded) or after occ(δ, 7,

C 2 i ) (excluded). Moreover, if x k = f alse with 1 ≤ k ≤ n then delete, occ(n + k, 0, C 2 i ), otherwise delete occ(n + k, 1, C 2 i ) (excluded). Moreover, if x k = f alse with 1 ≤ k ≤ n then delete, occ(2n -k + 1, 0, P

2

i ), otherwise delete occ(2n -k + 1, 1, P

Our presentation actually replaces the original CHAIN level with the STEM level due to its importance for practical issues[START_REF] Guignon | An edit distance between rna stem-loops[END_REF].

Appendix

Proof (Of Lemma 1). Consider any independent set S in the graph G. Clearly, S includes at most two vertices from each copy A i of the graph A. Moreover, if S includes exactly two vertices from A i , then the two vertices must be v 1 and v 4 , and consequently S includes at most one vertex from A i-1 and at most one vertex from A i+1 . Recall that n = 4t. Thus the maximum cardinality k * of an independent set in the graph G is 2+1 2 t = 3 8 n .

Proof (Of Lemma 2). We first consider case 2.5.3, where S[1] = T [START_REF] Alber | Computing the similarity of two sequences with nested arc annotations[END_REF], i > 0 and j > 0, S[i] = T [j], and ∃a : S[2, a, i

Consider any optimal solution in which S [START_REF] Alber | Computing the similarity of two sequences with nested arc annotations[END_REF] and T [START_REF] Alber | Computing the similarity of two sequences with nested arc annotations[END_REF] are not deleted, that is, S[1] ∼ T [START_REF] Alber | Computing the similarity of two sequences with nested arc annotations[END_REF] is a match. Then the jth letter of this optimal solution matches S[i ] ∼ T [j ] for some i ≥ j and j ≥ j. If S[i] is not deleted, then the arc

and consequently at least one letter in S[2, i -1] must be deleted because S[2, i -1] has one more letter than T [2, j -1]. In any case, at least one letter in S[1, i] must be deleted, thus i > j. Since j = i -1, it follows that i ≥ i. Since we also have j ≥ j, it is safe to replace the first j letters of this optimal solution by the j letters in S[1, a, i] = T [1, j], which results in an optimal solution that matches S[1, a, i] ∼ T [1, j] and deletes S[a]. This proves the lemma for case 2.5.3. A similar replacement argument proves the lemma for the other three cases.

Technical lemma needed to prove Lemma 4.

Lemma 5. In any optimal solution of the LAPCS(STEM, STEM) problem on (S 1 , P 1 ) and (S 2 , P 2 ), at least one symbol incident to any arc has to be deleted. Moreover, all the substrings of β symbols 2 -denoted as S in the construction -will not be deleted.

Proof. By contradiction, let us suppose that there exist an optimal solution where one complete substring S has been deleted. Therefore, since S 1 is, by construction, smaller than S 2 the length of this optimal solution is at most |S 1 | -β. Then, in order for this solution to be optimal, one should have ε ≥ β; a contradiction since

. Thus, in an optimal solution, all the substrings of β symbols 2 should be preservedcontributing (2q -1)β to the length of the optimal. This also induces that, ∀1 ≤ i ≤ q, symbols of C 1 i will be matched to symbols of C 2 i , symbols of P 1 i will be matched to symbols of P 2 i and symbols of S 1 M will be matched to symbols of S 2 M .

Technical lemma needed to prove Lemma 3 and Lemma 4.

Lemma 6. In any optimal solution of the LAPCS(STEM, STEM) problem on (S 1 , P 1 ) and (S 2 , P 2 ), the alignment of S 1 M and S 2 M contributes (α + 1)n to the length of the solution.

Proof. Indeed, in any optimal solution, all the symbols 2 of S 1 M should be kept. By contradiction, suppose a full substring of α symbols 2 is not kept. Then the contribution of S 1 M to this optimal solution is at most

M and S 2 M where all the symbols 2 are kept. This last is of size

Therefore, in any optimal solution, by construction, for all 1 ≤ i ≤ n, either occ(i, 0, S 1 M ) or occ(i, 1, S 1 M ) will be kept in addition to all the symbols 2; leading to a common subsequence of size (α + 1)n.

Technical lemma needed to prove Lemma 3 and Lemma 4.

Lemma 7. In any optimal solution of the LAPCS(STEM, STEM) problem on (S 1 , P 1 ) and (S 2 , P 2 ), the alignment of P 1 i and P 2 i contributes (2γ + δ + (α + 1)n) to the length of the solution.

Proof. In any optimal solution, in P 1 i , half of the symbols 6 should be kept. First, note that there are 4γ symbols 6 in P 1 i and only 2γ such symbols in P 2 i . Thus, in any optimal solution, in P 1 i , at most half of the symbols 6 can be kept. By contradiction to the first assumption, suppose there are, in an optimal solution, less than half of the symbols 6 kept in P 1 i . Then the length of this optimal solution is at most |P i | -3γ; a contradiction. Therefore, in any optimal solution, since in P 1 i half of the symbols 6 are kept, by construction, at most one of the substrings 7 δ , 8 δ or 9 δ can be kept. Moreover, in P 1 i , by construction, for all 1 ≤ j ≤ n, either occ(j, 0, P 1 i ) or occ(j, 1, P 1 i ) will be kept in addition to all the symbols 2; leading to a common subsequence of size (2γ + δ + (α + 1)n).

Technical lemma needed to Prove Lemma 3 and Lemma 4.

Lemma 8. In any optimal solution of the LAPCS(STEM, STEM) problem on (S 1 , P 1 ) and (S 2 , P 2 ), the alignment of C 1 i and C 2 i contributes (2γ + 2δ + (α + 1)n + 1) to the length of the solution.

Proof. By a similar proof as in Lemma 7, in any optimal solution, in C 1 i half of the symbols 6 should be kept. Moreover, among all the 4δ symbols 7, 8 and 9, only 2δ may be kept in an optimal solution. Indeed, first, note that there are 2δ symbols 8 in C 2 i and only δ such symbols in C 1 i . Thus, in any optimal solution, in C 1 i , at most δ of the symbols 8 can be kept. Then, note that by Lemma 7, at most one of the substrings 7 δ , 8 δ or 9 δ can be kept in an optimal solution and in P 2 , for all 1 ≤ j ≤ δ and k ∈ {7, 8, 9}, there is an arc between occ(j, k, C 2 i ) and occ(δ -j + 1, k, P 2 i ). Moreover, considering all the combinations of alignment of the symbols 6, at most one of {3, 4, 5} may be kept. Finally, by construction, for all 1 ≤ j ≤ n, either occ(j, 0, C 1 i ) or occ(j, 1, C 1 i ) will be kept in addition to all the symbols 2; leading to a common subsequence of size (2γ + 2δ + (α + 1)n + 1).

Proof (Of Lemma 3). By construction, S 1 is of length (2q -1)β + q(4γ

According to Lemmas 6, 7, 8, any optimal solution is of size (2q-1)β +q(2γ +2δ+1+(1+α)n)+(1+α)n+q(2γ +δ+(1+α)n). One can easily verify that any optimal solution is, thus, of size |S 1 | -ε.

Proof (Of Lemma 4). By Lemma 6, for every 1 ≤ k ≤ n only one of {occ(k, 0, S 1 M ), occ(k, 1, S 1 M )} may be conserved between S 1 M and S 2 M . By Lemma 5, at least one symbol incident to any arc is deleted. Therefore, ∀1 ≤ k ≤ n only one of {occ(n -k + 1, 0,

) is deleted whereas occ(n-k +1, 1, P 1 1 ) and occ(k, 0, S 1 M ) are conserved. By construction, since according to the proof of Lemma 7, in P 1 1 half of the symbols 6 and one of the substrings 7 δ , 8 δ or 9 δ are kept, either (1) the two first substrings of γ symbols 6 and the substring of symbols 9, or (2) one of the two first and one of the two last substrings of γ symbols 6 and the substring of symbols 8, or (3) the two last substrings of γ symbols 6 and the substring of symbols 7 are conserved.

Let us first consider that the two first substrings of γ symbols 6 and the substring of symbols 9 are conserved (cf. Fig. 3.c). Since, in P 2 , ∀1 ≤ k ≤ δ there is an arc between occ(k, 9, C 2 1 ) and occ(δ -k + 1, 9, P 2 1 ), according to Lemma 8, a substring of δ symbols 7 and a substring of δ symbols 8 in C 1 1 have to be conserved. Then one can check that the only solution is to conserve the second substring of δ symbols 8 and the two last substrings of γ symbols 6 of C 1 1 since otherwise one would not be able to conserve all the symbols 2 of C 1 1 (which is required according to Lemma 8). Consequently, the only solution is to conserve, the symbols 2 appearing before occ(1, 6, C 2 1 ) (resp. after occ(γ + 1, 6, P 2 1 )) in C 2 1 (resp. P 2 1 ). Since by construction, ∀1 ≤ k ≤ n, there is an arc between occ(k, 1, C 2 1 ) (resp. occ(k, 0, C 2 1 )) and occ(3n -k + 1, 1, P 2 1 ) (resp. occ(3n -k + 1, 0, P 2 1 )), in order for occ(k, 1, P 1 1 ) to be conserved, one has to conserved occ(3n -k + 1, 1, P 2 1 ). Thus, by Lemma 5, occ(k, 1, C 2 1 ) has to be deleted and, according to the proof of Lemma 8, occ(k, 0, C 1 1 ) has to be conserved. Let us now consider that one of the two first and one of the two last substrings of γ symbols 6 and the substring of symbols 8 are conserved (cf Fig. 4.a). By a similar reasoning, one can check that the only solution is to conserve, the symbols 2 appearing between occ(1, 6, C 2 1 ) and occ(γ + 1, 6, C 2 1 ) (resp. between occ(1, 6, P 2 1 ) and occ(γ + 1, 6, P 2 1 )) in C 2 1 (resp. P 2 1 ). Since by construction, ∀1 ≤ k ≤ n, there is an arc between occ(n + k, 1, C 2 1 ) (resp. occ(n + k, 0, C 2 1 )) and occ(2n -k + 1, 1, P 2 1 ) (resp. occ(2n -k + 1, 0, P 2 1 )), in order for occ(k, 1, P 1 1 ) to be conserved, one has to conserved occ(2n -k + 1, 1, P 2 1 ). Thus, by Lemma 5, occ(n + k, 1, C 2 1 ) has to be deleted and, according to the proof of Lemma 8, occ(k, 0, C 1 1 ) has to be conserved. Finally, let us consider that the two last substrings of γ symbols 6 and the substring of symbols 7 are conserved (cf Fig. 4.c). Once again, by a similar reasoning, one can check that the only solution is to conserve, the symbols 2 appearing after occ(γ + 1, 6, C 2 1 ) (resp. before occ(1, 6, P 2 1 )) in C 2 1 (resp. P 2 1 ). Since by construction, ∀1 ≤ k ≤ n, there is an arc between occ(2n + k, 1, C 2 1 ) (resp. occ(2n + k, 0, C 2 1 )) and occ(n -k + 1, 1, P 2 1 ) (resp. occ(n -k + 1, 0, P 2 1 )), in order for occ(k, 1, P 1 1 ) to be conserved, one has to conserved occ(n -k + 1, 1, P 2 1 ). Thus, by Lemma 5, occ(2n + k, 1, C 2 1 ) has to be deleted and, according to the proof of Lemma 8, occ(k, 0, C 1 1 ) has to be conserved. With a similar reasoning, by recurrence, since, ∀1 ≤ i ≤ q, 1 ≤ k ≤ n, there is an arc in P 1 between occ(k, 0, C 1 i ) (resp. occ(k, 1, C 1 i )) and occ(k, 0, P 1 i+1 ) (resp. occ(k, 1, P 1 i+1 )), if occ(k, 0, C 1 i ) is conserved then occ(k, 0, P 1 i+1 ) is deleted. And therefore, with similar arguments, occ(k, 0, C 1 i+1 ) is conserved. Once more, it is easy to see that this result still holds if occ(k, 0, C 1 i ) is conserved.


John Douglas
email: j.douglas@brgm.fr

Hideo Aochi
email: h.aochi@brgm.fr

Peter Suhadolc
email: suhadolc@dst.units.it4ditto

Giovanni Costa
email: costa@dst.units.it

THE IMPORTANCE OF CRUSTAL STRUCTURE IN EXPLAINING THE OBSERVED UNCERTAINTIES IN GROUND MOTION ESTIMATION

Keywords: Ground motion estimation, attenuation relations, crustal structure, uncertainties, ground motion simulation

) to model the effect of crustal structure in empirical equations the scatter associated with ground motion estimation equations derived using these simulated data could be reduced to zero if real-to-equivalent hypocentral distance mapping functions were derived for every combination of mechanism, depth and crustal structure present in the simulated dataset. This is, obviously, unrealistic for a practical use of the method. The relative importance of each parameter in affecting the decay of ground motions is assessed here. It is found that variation in focal depth is generally more important than the effect of crustal structure when deriving the real-to-equivalent hypocentral distance mapping functions.

INTRODUCTION

 [START_REF] Douglas | On the incorporation of the effect of crustal structure into empirical strong ground motion estimation[END_REF]introduce a new distance metric, which seeks to capture in empirical ground motion estimation equations (GMEEs) the effect on the decay rate of the layered structure of the crust. The layered structure of the crust leads to a much more complex decay of ground motions with distance than is currently captured in any GMEE. Also the differences in crustal structures between regions cause correspondingly different decay rates, which could be responsible for some of the variability in observed ground motions. This variability is shown by the large aleatory uncertainties (measured by the standard deviations of the equations) associated with GMEEs, which are not significantly decreasing with time despite increasing data and complexity of analysis (e.g. [START_REF] Douglas | Earthquake ground motion estimation using strong-motion records: A review of equations for the estimation of peak ground acceleration and response spectral ordinates[END_REF]. In order to test their proposed distance metric, [START_REF] Douglas | On the incorporation of the effect of crustal structure into empirical strong ground motion estimation[END_REF] conducted a small test based on observed data from Umbria-Marche and south Iceland, which are areas with considerable different crustal structures and hence theoretically different decay rates. The data was combined together with and without correction for the effect of the crust and simple ground motion estimation equations were derived. Disappointingly, and surprisingly, the standard deviations of the equations derived having corrected for the different effects of the crust in the two regions were higher than those of the equations derived having neglected the different effects of the crust.

Possible reasons for this disappointing result are the following. Firstly, the crustal structure models used for the wave velocities, densities and Q values used for the two regions were not completely appropriate. It is likely that this is an important factor because there is still uncertainty in the true structure of the crust for the two examined regions, which is demonstrated by the wide dispersion in the three crustal structures for south Iceland displayed in Figure 4 of [START_REF] Douglas | On the incorporation of the effect of crustal structure into empirical strong ground motion estimation[END_REF]. In addition, the values of Q used for the computation of the synthetics for the two regions were taken from global relations connecting velocity and anelastic attenuation and therefore probably are not completely appropriate. The second possible reason for no reduction in the scatter of ground motions after having tried to remove the effect of the crust is that the real-to-equivalent hypocentral distance mapping functions used for the two regions by [START_REF] Douglas | On the incorporation of the effect of crustal structure into empirical strong ground motion estimation[END_REF] were for a specific magnitude (M w 5), focal depth (5 km), azimuth (22.5°) and focal mechanism (pure strike-slip) whereas the observational data they used for testing the method were from earthquakes with differing magnitudes, focal depths and focal mechanisms and from stations at different azimuths. All of these additional factors have an effect on the decay rate of ground motions, particularly the focal depth [see Figure 9 of [START_REF] Douglas | On the incorporation of the effect of crustal structure into empirical strong ground motion estimation[END_REF]]. Therefore the distance mapping functions used by [START_REF] Douglas | On the incorporation of the effect of crustal structure into empirical strong ground motion estimation[END_REF] were not wholly correct for all the used data. Possibly the effect of one or more of the ignored factors (magnitude, focal depth, focal mechanism or azimuth) on the decay is more important than the difference in the decay rate caused by the differing crusts in the two regions.

If real-to-equivalent hypocentral distance mapping functions were derived for all combinations of magnitude, focal depth, focal mechanism and azimuth present in the observed data sets using a highly accurate model of the crustal structure in the two regions then the scatter caused by the effect of the crust could be reduced to practically zero. Obviously computing real-to-equivalent hypocentral distance mapping functions for every combination of magnitude, focal depth, focal mechanism and azimuth is unrealistic when using the concept of equivalent hypocentral distance in practice. Hence the purpose of this paper is to assess how close one can get to this theoretical value of zero by neglecting different factors that affect the decay of ground motions (magnitude, focal mechanism, focal depth, azimuth and crustal structure).

SELECTED REGIONS AND CRUSTAL STRUCTURE MODELS

Three regions of metropolitan France (the Pyrenees, the upper Rhine Graben and the western Alps) were selected for study. These three regions were chosen because they are the most seismically active parts of metropolitan France and because the crusts in these three areas are considerably different from one another.

Crustal velocity structures for these three regions could be obtained from the global model CRUST5.1 [START_REF] Mooney | CRUST 5.1: A global crustal model at 5° × 5°[END_REF] or its update CRUST2.0 [START_REF] Laske | The Reference Earth Model website[END_REF] or from the European model EurID [START_REF] Du | EurID: a regionalized 3-D seismological model of Europe[END_REF]. However, it was shown in [START_REF] Douglas | On the incorporation of the effect of crustal structure into empirical strong ground motion estimation[END_REF] that a better fit between synthetic and observed accelerograms is obtained by using a local crustal velocity structure. Therefore in this study we only use crustal structure models that have been derived for the specific regions studied and not compiled from large scale models.

For the Alps, the crustal velocity structure model of Costa et al. (2003) is used. For the Pyrenees, the structure derived by [START_REF] Souriau | A tomographic study of the lithosphere beneath the Pyrenees from local and teleseismic data[END_REF] is chosen. For the upper Rhine graben the recent crustal structure derived by Lopes Cardozo ( 2003) is used. Unfortunately, the profiles chosen for the Pyrenees and the upper Rhine Graben do not provide information on the velocities in the top few kilometres because of the type of data used for their derivations. Therefore, in order to have realistic near-surface velocities in the used structures the generic rock profiles provided by Boore and [START_REF] Joyner | Site amplifications for generic rock sites[END_REF] were appended to the top of adopted structures. By comparing the structure for the upper Rhine graben to the two generic profiles provided by Boore and [START_REF] Joyner | Site amplifications for generic rock sites[END_REF] at depths greater than 2km it was decided to append their 'generic rock site' profile (their Table 1) since this closely matches the adopted profile at common depths. Similarly by comparing the crustal structure models for the Pyrenees to the two profiles of Boore and Joyner (1997) the velocities for a 'generic very hard rock site' was found to provide a close match at common depths, therefore it was appended. These findings are consistent with the statement of Boore and Joyner (1997) that sites with their 'very hard rock site profile' are found in areas where glaciers have scoured the weathered and cracked near-surface materials; such areas are common in the Pyrenees whereas they are less common in the Rhine graben region. Comparison of the V p and V s crustal structures used for the simulations for the three regions.

The geographical distribution of the travel-paths of strong-motion recordings from the Réseau Accélérométrique Permanent (RAP) of France was examined to choose a 1D velocity that is representative of the travel paths of recordings in the three regions. Figure 2.1 compares the crustal structures used for the three regions.

Published density estimates for the chosen regions are not common. Therefore, and also because it is commonly adopted, the relation of [START_REF] Gardner | Formation velocity and density -The diagnostic basics for stratigraphic traps[END_REF], i.e. ρ = 1.741V p 0.25 , where V p is P-wave velocity in km/s and ρ is density in g/cm 3 , has been used here. Minor changes in the density values will not significantly affect the results.

GROUND MOTION SIMULATIONS

Wave propagation for the different scenarios was calculated using a finite difference scheme within an elastic volume of 34×34×25 km 3 at equally spaced points every 100m using a time step of 0.005 s. Simulations have been conducted for a point source of magnitude M w 5.0, three focal depths (5, 10 and 15km) and two mechanisms: pure normal (λ=-90°, δ = 60°) and pure strike-slip (λ=0°, δ = 90°). Ground motions are extracted at ideally located surface stations whose azimuths from the strike of the earthquake are between 250° and 340° in steps of 15° at 11 different epicentral distances (0 km to 45 km).The mechanism-independent equations of [START_REF] Wells | New empirical relationships among magnitude, rupture length, rupture width, rupture area, and surface displacement[END_REF] estimate a subsurface fault length of 3.3km therefore, assuming a rupture velocity of 2.5 km/s, this gives a rupture duration of 1.3s, which was used as a local support of B-spline function of order 4 (degree 3) assumed as the moment source time function in all the simulations.

Because the assumed source model (point source with a simple smooth time function) does not well model the high frequency content of the motions it was decided to study the decay of peak ground velocity (PGV).

RESULTS

In [START_REF] Douglas | On the incorporation of the effect of crustal structure into empirical strong ground motion estimation[END_REF] a new distance metric called the equivalent hypocentral distance is introduced. The true hypocentral distance is converted to the equivalent hypocentral distance that would experience the same amplitude decay as a station on a homogenous crust. For each strong-motion record in the set of records selected for analysis, a theoretical decay curve is defined through ground motion simulations for the region where the earthquake occurred. The true hypocentral distance is then mapped to the equivalent hypocentral distance and this equivalent distance is used for the regression analysis, in which the geometrical decay is constrained to 1/r. Data from regions with different crustal structures can then be combined because equivalent hypocentral distance is used, which incorporates the effect of crustal structure, rather than true hypocentral distance, which neglects these effects. The advantage of this method is that a complex form of the equation is not needed; the effect of crustal structure being handled by using a better distance metric. It removes the need to use simple functional forms to handle Moho bounce or a change to surface-wave decay because they are implicitly handled by the distance metric.

As an example of the variability in PGVs present in the simulations due to different crustal structures, focal depths, azimuths and mechanisms Figure 4.1 displays the simulated PGVs for all scenarios against distance. As can be seen the scatter in PGVs is considerable. To measure of this scatter an equation with functional form: log PGV=a+blog d h +cd h , where d h is hypocentral distance, was fitted to the simulated points and the standard deviation of this equation was computed. The standard deviation computed was 0.27 corresponding to a factor of 1.86 between the median and 84 percentile ground motions, which compares well to the uncertainty associated with empirical ground motion estimation equations for PGV, e.g. the standard deviation of 0.28 associated with the PGV equation of [START_REF] Tromans | The attenuation of strong-motion peaks in Europe[END_REF]. The simulations in this study, however, do not include the scatter due to variation in the earthquake source propagation or variation due to local site conditions, both of which contribute to the scatter in empirical GMEEs. In this study, equivalent hypocentral distances are calculated using a reference point of 15km that they could be computed consistently for all three studied focal depths (5, 10 and 15km). Therefore the mapping function is: r equivalent =15 y(15km)/y(r real ) where y(x) is the simulated acceleration at a real hypocentral distance of x. These mapping functions were derived independently for each scenario, which makes the implicit assumption that the average ground motions at 15km for each scenario is the same and only the decay function varies with scenario. Figure 4.2 shows the computed real-to-equivalent distance mappings for the three regions for each of the three depths for normal faulting for an azimuth of 295°. The large variations in these mappings is noticeable. In particular, the three mapping functions for the same region but for different depths show large differences.

In order to assess the ability of the equivalent hypocentral distance technique to lead to a reduction in ground motion scatter due to regional crustal differences, the standard deviation of the mean real-to-equivalent hypocentral distance mapping functions for a region (i.e. neglecting focal depth) and for a focal depth (i.e. neglecting region) were computed. These standard deviations measure the importance of assuming either a single mapping function for a region (regardless of focal depth) or a single mapping function for a focal depth (regardless of region). Figure 4.3 shows these computed standard deviations with respect to real hypocentral distance. It shows that the standard deviations of the equivalent hypocentral distance mapping functions computed with respect to the three regions are, in general, higher than the standard deviations computed with respect to the three focal depths showing that focal depth within a given region is more important than regional differences in crustal structure for a given focal depth. This is thought to be due to similarities in the crustal structural models of the three regions at depths between 10 and 15km (see Figure 2.1). For 6 shallow earthquakes (h=5km) the effect of region is more important because the three crustal models are significantly different at shallow depths.

DISCUSSION AND CONCLUSIONS

In this brief article, a number of ground motion simulations have been conducted in order to assess the utility of the equivalent hypocentral distance technique introduced by [START_REF] Douglas | On the incorporation of the effect of crustal structure into empirical strong ground motion estimation[END_REF] to capture the possible regional dependence of ground motions caused by differences in crustal structure. For the three regions studied (the western Alps, the Pyrenees and the upper Rhine Graben) it has been found that focal depth is more important in explaining the variation in decay of the simulated ground motions than differing crustal structures. This finding needs to be verified for other regions.

If in two regions the earthquakes occur within a narrow depth range, with similar mechanisms and are recorded at similar azimuths then the differences in crust between the two regions would dominate over these confounding effects and the real-to-equivalent hypocentral distance technique should lead to a significant reduction in the scatter observed when the two sets of data are combined.

It is planned to extend this study by computing simulations for different magnitudes and focal mechanisms to assess the need to derive real-to-equivalent distance mapping functions to account for differences in decay due to these factors. It is planned to publish these further results in a journal article.

Figure

  Figure 2.1:Comparison of the V p and V s crustal structures used for the simulations for the three regions.

Figure 4 . 1 :

 41 Figure 4.1: Decay of simulated PGVs for all scenarios against hypocentral distance.

Figure

  Figure 4.2:Real-to-equivalent hypocentral distance mappings for the three regions for each of the three depths for normal faulting for an azimuth of 295°.

Figure 4

 4 Figure 4.3: Standard deviations of the mean real-to-equivalent hypocentral distance mapping functions overall, for a region and for a focal depth with respect to distance for normal faulting.

ACKNOWLEDGEMENTS

This study was funded by RISQSIS (an internal seismic hazard project funded by BRGM). We thank Reneta Raykova for her list of crustal structure models and for discussions. We are very grateful to: Gideon Lopes Cardozo, Edi Kissling and Annie Souriau for sending us their velocity models in electronic form.


Deep Kamal

Yassine Singh

Gerardo Hadjadj-Aoul
email: yassine.hadjadj-aoul@inria.fr

Rubino

QUALITY OF EXPERIENCE ESTIMATION FOR ADAPTIVE HTTP/TCP VIDEO STREAMING USING H.264/AVC

Keywords: QoE, Video Quality, adaptive HTTP streaming, TCP video streaming, H.264, IPTV

Video services are being adopted widely in both mobile and fixed networks. For their successful deployment, the content providers are increasingly becoming interested in evaluating the performance of such traffic from the final users' perspective, that is, their Quality of Experience (QoE). For this purpose, subjective quality assessment methods are costly and can not be used in real time. Therefore, automatic estimation of QoE is highly desired. In this paper, we propose a noreference QoE monitoring module for adaptive HTTP streaming using TCP and the H.264 video codec. HTTP streaming using TCP is the popular choice of many web based and IPTV applications due to the intrinsic advantages of the protocol. Moreover, these applications do not suffer from video data loss due to the reliable nature of the transport layer. However, there can be playout interruptions and if adaptive bitrate video streaming is used then the quality of video can vary due to lossy compression. Our QoE estimation module, based on Random Neural Networks, models the impact of both factors. The results presented in this paper show that our model accurately captures the relation between them and QoE.

INTRODUCTION

Distribution of digital video is undergoing dramatic transformation at present. Many developments in this area are changing the way contents are generated, distributed and consumed. In fact, reductions in the cost of digital video cameras coupled with the development of easy-to-use content sharing platforms (e.g. the YouTube phenomenon) have clearly stimulated media delivery over HTTP. The current success of streaming over HTTP is also due to the intrinsic advantages of the protocol, which has the ability, notably, to bypass firewalls while exploiting the standard HTTP entities in the media delivery.

With these considerations, HTTP-based streaming is experiencing a widespread adoption by Services providers and

The work described in this paper is partially supported by the national French project ANR VERSO ViPeer.

CDN operators for both mobile and fixed networks. In this context, content providers are increasingly becoming interested in evaluating the performance of such applications from the final users' perspective. Indeed, more importance is being attached to the quality as perceived by the final users, or Quality of Experience (QoE), as compared to Quality of Service. In fact, with HTTP streaming, it is possible to have a bad QoS, but a good QoE, since HTTP provides a reliable mean of transportation. This can happen for example when the QoS parameters are packet loss rate and packet delay. In that case, even if there will be some packet loss and delay reflecting bad QoS, the HTTP streaming, with TCP retransmissions, will still be able to provide good QoE, at least for up to some values of these parameters.

QoE is defined in [1] as "the overall acceptability of an application or service, as perceived subjectively by the enduser". Moreover, it is noted that QoE includes everything such as network, client, terminal, etc., and overall acceptability may be influenced by the context and the expectations of the user. As will be stated in next section, several methods to measure the QoE are available. However, none of the proposed methods address the problem of measuring QoE in the case of adaptive bitrate video using a reliable transport protocol, the situation in adaptive streaming over HTTP.

In light of the above observations, the main concern of the present work is to design a no-reference QoE monitoring module for HTTP/TCP video streaming using H.264/AVC video codec in the context of IPTV. The proposed approach uses a methodology called Pseudo-Subjective Quality Assessment (PSQA) [START_REF] Mohamed | A Study of Real-time Packet Video Quality Using Random Neural Networks[END_REF][START_REF] Rubino | Quantifying the Quality of Audio and Video Transmissions over the Internet: The PSQA Approach[END_REF], which is based on Random Neural Network (RNN) [START_REF] Gelenbe | Random neural networks with negative and positive signals and product form solution[END_REF], to estimate the QoE in the above context. In this work, instead of packet loss patterns and latencies, we consider the Quantization Parameter (QP) used in video compression and the playout interruptions as metrics that directly impact QoE. Indeed, when using adaptive HTTP streaming the perceived quality depends directly on QP, which reflects changes in quality, and on the playout interruptions.

The remainder of this paper is organized as follows. Section 2 gives an overview of the background and discusses the state of the art. Section 3 focuses on monitoring QoE. Section 4 presents and discusses performance evaluation results. Finally, the paper concludes in Section 5 with a summary re-capping the main achievements of the proposed scheme.

RELATED WORK AND BACKGROUND

Background

Several factors can influence QoE for video applications depending on their type and the underlying network. For example, packet losses in the case of applications using an unreliable transport protocol and packet delay, in the case of real time applications, can significantly impact QoE. Moreover, the video content itself may have some impact

In the context of HTTP streaming, considered in this paper, a reliable transport protocol such as TCP is assumed and thus video data will not be lost. However, there may be playout interruptions caused by either bandwidth fluctuations or long delays due to retransmissions after some packet losses. Such playout interruptions are annoying for the users and should be taken into account for QoE estimation.

Quantization is another important factor that is relevant especially in the case of adaptive HTTP streaming. In fact, to adapt to a diminution in the available bandwidth, the adaptive HTTP streaming client will ask for low bitrate video chunks with more compression that may degrade QoE.

Related Work

Objective quality measurement tools, such as PSNR, may not correlate well with human perceived video quality and may not be able to assess the impact of video playout interruptions. On the other hand the subjective quality assessment methods [2] are costly and time consuming. Thus, automatic QoE monitoring is highly desired. Some existing approaches [START_REF] Wolf | Video Quality Measurement Techniques[END_REF][START_REF] Van Den | Perceptual Models and Architectures for Video Coding Applications[END_REF][START_REF] Wang | Video quality assessment using structural distortion measurement[END_REF][START_REF] Wang | Survey of objective video quality measurements[END_REF] take the full original video as a reference (can be very costly), or at least as a partial reference for QoE estimation.

About no-reference models: an "opinion model" is described in ITU G.1070 [START_REF]Opinion model for video-telephony applications[END_REF], mainly for planning purposes and is not very accurate [START_REF] Singh | No-Reference Quality of Experience Monitoring in DVB-H Networks[END_REF]. The work in [START_REF] Singh | No-Reference Quality of Experience Monitoring in DVB-H Networks[END_REF] uses a methodology called Pseudo-Subjective Quality Assessment (PSQA) [START_REF] Mohamed | A Study of Real-time Packet Video Quality Using Random Neural Networks[END_REF], which is based on Random Neural Network (RNN), a family of Artificial Neural Networks based on queueing models [START_REF] Gelenbe | Random neural networks with negative and positive signals and product form solution[END_REF], to estimate the QoE of H.264 video streaming over DVB-H networks experiencing packet losses. However, the above module is not valid for HTTP streaming where lost packets are retransmitted and playout interruptions may occur.

A QoE model considering video playout interruptions is proposed in [START_REF] Watanabe | Objective video quality assessment method for evaluating effects of freeze distortion in arbitrary video scenes[END_REF]. However, that approach does not take into account the impact of video bitrate change on the perceived quality, which is the case in adaptive video streaming.

In this paper, we use new subjective tests and studies to propose a model considering video playout interruptions as well as an encoding parameter called Quantization Parameter (QP) that impacts the bitrate as well as the video quality. We consider the number of playout interruptions, the average interruptions delay as well as the maximal interruptions delay, which are direct consequences of network conditions. The above choices are explained in the following section.

QOE ESTIMATION

Pseudo-Subjective Quality Assessment (PSQA)

A general technology called Pseudo-Subjective Quality Assessment (PSQA) has been proposed in [START_REF] Mohamed | A Study of Real-time Packet Video Quality Using Random Neural Networks[END_REF]. PSQA is based on a specific type of queuing network used as a learning tool called Random Neural Network [START_REF] Gelenbe | Random neural networks with negative and positive signals and product form solution[END_REF]. For every different context, such as when the video codec or the parameters affecting the QoE change, a new PSQA based module is to be designed after analysing the associated parameters and after conducting new subjective tests. The idea is to have several distorted samples evaluated subjectively by a panel of human observers. Then the results of this evaluation are used to train a RNN in order to capture the relation between the parameters causing distortion and the perceived quality.

Adaptive HTTP Streaming

The keen interest towards multimedia streaming over the Internet, which was clearly encouraged by the development of easy-to-use content sharing platforms (e.g. YouTube), is making HTTP/TCP streaming the leading technology in the media delivery sectors [START_REF] Zong | Survey and Gap Analysis for HTTP Streaming Standards and Implementations[END_REF] for both mobile and fixed networks. As opposed to the former protocols, HTTP enables a reliable and an adaptive streaming process. These properties are directly inherited from those of the TCP protocol. It also allows to seamlessly bypass firewalls and adapt the streaming quality to the bandwidth, which makes the technology particularly interesting for a wide deployment. For adaptive bitrate streaming, the media file is fragmented into small segments or chunks of same duration (e.g. a few seconds) [START_REF] Wu | Problem statement for HTTP streaming[END_REF].

In order to allow adaptive streaming, each chunk is decoded independently enabling seamless switching from one quality to another when network conditions change. Thus, once the playout of a chunk is finished, the video player can start playing the next chunk with a different quality.

QoE estimation for Adaptive HTTP Streaming

In order to use PSQA for Adaptive HTTP Streaming, first the relevant parameters need to be identified and their effect on the perceived quality needs to be studied. Then the selected parameters have to be simulated, which will result in distorted video sequences. These distorted video sequences will be used to train the PSQA tool with the help of a panel of human observers. The trained PSQA will, then, be used in real time to estimate the video quality. In the following text, we describe the parameters that are considered for QoE estimation in the context of HTTP streaming over TCP/IP networks.

It should be noted that other parameters, not described below, like resolution and frame rate, are either constant in our study or, like losses, delay and jitter that cause packets to miss their deadline, are converted into playout interruptions.

Playout Interruptions

TCP/IP networks are characterised by frequent packet losses and fluctuating bandwidth over time. In contrast to the streaming over UDP, HTTP streaming implies an automatic recovery of lost packets by TCP, that may eliminate video distortions. However, the retransmissions and bandwidth fluctuations may cause playout interruptions which should be considered for QoE estimation. In this paper, by playout interruptions we mean pauses in the playout without any skip of video data. This case is more relevant for Video On Demand applications where video can be paused when some immediate chunks are not yet downloaded.

We model the playout interruptions using three parameters measured over an interval containing a fixed duration of video data (16 seconds in this paper, but interval can be longer due to interruptions): the total number of playout interruptions N , the average D avg and the maximal D max values of interruption delays. Note that, for longer videos, a different QoE score will be provided after every 16 seconds of video.

It should be noted that in order to train our QoE module, different values of N , D avg and D max must be generated uniformly to avoid missing regions in the input parameter space of the training database. However, the existing relation between D avg and D max makes it difficult to uniformly generate such values. Thus, we decided to model the playout interruptions as a function of N , D avg and D max and to use the following cumulative distribution function F (x) of the delay:

F (x) =          αx D avg if x ≤ D avg , (1 -α) x -D avg D max -D avg + α if x ∈ [D avg , D max ],
1 otherwise.

(1) As the desired average value of the distribution function is D avg , we must have D avg = +∞ 0 1 -F (x) dx and combining it with (1), we get α = 1 -D avg D max . In order to generate the D avg values, we need to invert function F . This gives

F -1 (u) =        D avg D max D max -D avg if 0 ≤ u ≤ α, (u -1)D 2 max -(u -2)D max D avg D avg if α ≤ u ≤ 1.
(2) To sample different independent values of the delay, we simply generate i.i.d. pseudo-random numbers uniformly distributed on [0, 1], say U 1 , U 2 , . . . and return the values F -1 (U 1 ), F -1 (U 2 ), . . .. They are then used to simulate playout interruptions in the videos by inserting pauses with durations equal to these values.

Quantization Parameter (QP)

In the HTTP streaming context, another parameter significantly impacting QoE is the quantization parameter that controlles the amount of video compression. H.264 codec uses QP (from 0 to 51) to quantize the transform coefficients obtained while encoding the video. The trade-off is that a higher value means more loss of information and lower quality, but a lower bitrate; and vice versa. In H.264, QP can vary in different frames as well as in different macro blocks (MB) in each frame. QP is adapted over time to attain the target video bitrate for the encoded chunks. For QoE estimation, we consider the average of QP values, QP avg , over all MBs in all video frames present over the measurement time window. Also note that from now onwards we use QP and QP avg interchangeably in the paper, unless otherwise specified.

In the case of adaptive HTTP streaming, we want to cover the context of several chunks having different bitrates. Thus, we encoded video chunks with different bitrates that in turn resulted in different values of QP.

RESULTS

In order to generate the QoE Estimation module, 4 different video sequences of 16 seconds each were considered: Aspen, ControlledBurn, RushFieldsCuts and RedKayak from VQEG. The resolution was 720p, fps = 30, GOP size = 60 frames. The high profile of H.264 was used. The encoder used was x264 [12]. The value of QP was varied from 22 to 48.

Some videos having similar quality were discarded using random sampling for limiting the final size of the video database to avoid too long subjective testing sessions. 15 users evaluated the videos using a MOS scale of 1, very bad, to 5, excellent, using Single Stimulus Impairment Scale (SS) testing methodology [2]. Similar to the screening procedure in [START_REF] Mohamed | A Study of Real-time Packet Video Quality Using Random Neural Networks[END_REF], the subjective test scores of the users, who did not give consistent scores, were removed (1 in our case). The MOS scores were used to train the RNN. Out of total 118 videos, 100 videos were used for training and 18 videos for validation. The trained RNN is validated only if the root mean square error (RMSE) for both training and validation data is less than the target. The target is equal to the average RMSE of users in the subjective panel that in turn is 0.61.

The trained RNN had 3 layers. The first layer has 4 neurons, for the input parameters, the hidden layer has 5 neurons (this number was varied and 5 provided the best RMSE) and the last layer has 1 neuron for output. To understand RNN, some very compressed details (please see [START_REF] Mohamed | A Study of Real-time Packet Video Quality Using Random Neural Networks[END_REF] for more info.): the output of the network is a fraction where the numerator is the sum in h of the "state" ̺ h of hidden neuron h, weighted by W + (h, o), the positive weight from h to the single output neuron o; the denominator is the sum of the rate of neuron o and the sum of the ̺ h weighted by the W -(h, o). State ̺ h is in turn equal to a similar fraction using layers 0 and 1. Table 1 provides the weights of the trained RNN. The 3 layers are indexed using l and the neurons in each layer using k. The weights connecting the neurons in different layers are denoted W + and W -. The 4 input parameters explained in section 3.3 were normalised as follows: 1 -(QP -20)/(54 -20), 1 -α, D max /16 and N/16.

The results are shown in Figure 1 which shows the estimated QoE with respect to different pairs of parameters, the remaining ones being fixed. Figure 1(a) shows that users are more sensitive to video playout interruptions as compared to an increase in QP for lower values of QP. When QP increases or the quality degrades due to increased quantization, initially the QoE scores fall very slowly. Only after reaching a high value of QP, the QoE scores start to decrease faster. Whereas, QoE drops faster with increasing D max , initially, but after a higher value of D max the decrement of QoE becomes slow. This is because after a high value of D max , around 6 to 8 seconds, the dropped QoE becomes saturated and the users are less sensitive to further increments in D max .

Increasing QP decreases the video bitrate. Thus, when the bandwidth decreases in the network, the QP can be increased significantly to adapt the streaming bitrate to the available bandwidth, rather than risking even a single playout interruption. This depends on the obtained QoE function, whose weights are given in Table 1, as well as the trade-off between increasing QP or risking a playout interruption. With respect to previous observations, our QoE model can be integrated with the controller of adaptive HTTP streaming. It will help the controller to make decisions that optimize QoE for the given values of QP and network parameters. It can be seen that for lower values of D max or N the QoE is very sensitive to both. However, for higher values, QoE decreases very slowly because after a certain value of D max or N the quality is already bad enough and users are not sensitive to further increments. Also note that the worst value of predicted MOS in this figure is 1.5, but for such high values of D max and N the MOS should be 1.0, that is the minimum MOS possible. This prediction error of 0.5 is because RNN shows saturation near bad quality and because while training we wanted to be accurate when quality is good instead of being accurate when quality is already bad. Figure 1(c) shows QoE behaviour with respect to 1 -α = D avg /D max . The real significance of 1 -α is that it characterizes the spread of pause durations. When the value of 1 -α is low then the interruptions are spread out between 0 and D max , but for high values of 1 -α the durations of all the interruptions are closer to D max . Thus the QoE scores would be low for higher values of 1 -α. Figure 1(c) shows that the behaviour is as expected.

Figure 2 shows the good accuracy of the estimation using a scatter plot with estimated MOS vs. real MOS obtained from the subjective tests. The points corresponding to the training as well as the validation data are shown. The overall Root Mean Square Error (RMSE) of 0.37 for all data (with slightly higher and lower RMSE for training and validation sets, respectively) on the MOS scale going from 1.0 to 5.0. The RMSE is less than that of the human test panel (0.61) and thus is satisfactory.

We also compared our QoE estimation model with a model proposed in [START_REF] Watanabe | Objective video quality assessment method for evaluating effects of freeze distortion in arbitrary video scenes[END_REF], that estimates video quality based on freeze distortions. In Figure 3, we plot the values of mean square error (MSE) for the estimated MOS vs. different QPs. Similar MSE values are observed for low QPs. However, our model performs significantly better in QoE estimation by maintaining low values of MSE even when QP increases, whereas with the existing model the MOS estimation error, increases significantly. This is because, unlike our model, the freeze distortion based model does not take QP into account.

CONCLUSIONS

In this study, we have addressed the problem of estimating the QoE of video streaming in TCP/IP networks. As a solution, we designed an automatic no-reference QoE estimation module for HTTP video streaming using TCP and H.264 video codec and the trained RNN function is provided in this paper. The proposed approach is different from the existing ones as it addresses the problem of measuring QoE in the combined case of adaptive bitrate video and the use of a reliable transport protocol. This is the case of the adaptive streaming over HTTP. Extensive simulations showed that our model accurately measures the QoE and performs better than an existing QoE model when the value of QP is varied. Finally, for future work, it should be stressed out that the QoE feedback can be used to take some corrective measures, in case the quality drops, to bring back QoE to satisfactory level.

[1] ITU-T SG12, "Definition of Quality of Experience", COM12 -LS 62 -E, TD 109rev2 (PLEN/12), Geneva, Jan. 2007.

[2] ITU-R Recommendation BT.500-11, "Methodology for the subjective assessment of the quality of television pictures", June 2002.

4 Fig. 1 .

 41 Fig. 1. MOS scores with respect to different parameters.

Figure 1

 1 Figure 1(b) shows the QoE with respect to D max and N .It can be seen that for lower values of D max or N the QoE is very sensitive to both. However, for higher values, QoE decreases very slowly because after a certain value of D max or N the quality is already bad enough and users are not sensitive to further increments. Also note that the worst value of predicted MOS in this figure is 1.5, but for such high values

Fig. 2 .

 2 Fig. 2. Real vs Estimated QoE scores with our QoE module.

Fig. 3 .

 3 Fig. 3. Comparison of proposed QoE model in this paper with the freeze distortion based model that does not consider QP.

Table 1 .

 1 Weights for RNN function.

	From	To	W +	W -	From	To	W +	W -
	l, k	l, k			l, k	l, k
	0:0	1:0	0.13656	0.00946	0:2	1:3	0.04169	0.06672
	0:0	1:1	0.04683	0.02828	0:2	1:4	0.13656	0.01814
	0:0	1:2	0.05276	12.3531	0:3	1:0	0.05961	0.20870
	0:0	1:3	0.25218	0.02317	0:3	1:1	1.90036	0.05845
	0:0	1:4	1.13732	1.70886	0:3	1:2	0.07383	1.83576
	0:1	1:0	0.00599	0.32773	0:3	1:3	0.29561	12.2138
	0:1	1:1	0.02582	67.1723	0:3	1:4	0.00972	1.15571
	0:1	1:2	8.03364	1.12285	1:0	2:0	0.11194	2.47160
	0:1	1:3	0.01362	1.39952	1:1	2:0	0.01686	0.00329
	0:1	1:4	0.00821	0.03468	1:2	2:0	0.00024	0.04832
	0:2	1:0	0.30222	0.18335	1:3	2:0	0.01047	12.4031
	0:2	1:1	0.02602	0.54512	1:4	2:0	0.11556	0.00370
	0:2	1:2	1.92420	1.25226