Peter Vandendriessche
email: peter.vandendriessche@ugent.be

LDPC codes arising from partial and semipartial geometries

Keywords: LDPC codes, bounds, finite geometry codes, minimum distance, partial and semipartial geometries

We study several high-rate LDPC codes derived from partial and semipartial geometries. We study in particular the minimum distance of several known infinite classes of these partial and semipartial and we improve the known bounds on this minimum distance in the binary and non-binary case. In some cases, we can determine the exact minimum distance.

1 Introduction Definition 1. Let F be a finite field and let H be an m × n matrix of rank n -k over F. The linear [n, k]-code C defined by H is the k-dimensional subspace of F n consisting of all vectors which have a zero inproduct (in F) with all rows of H. The matrix H is called the parity check matrix of C. The parameters n and k are respectively called the length and dimension of the code C and are denoted by len(C) and dim(C) respectively. Definition 2. Let C be a linear code. If d is the maximum integer for which every two different vectors in C differ in at least d positions, then d is called the minimum distance of the code C. Definition 3. An LDPC code C is a code defined by a sparse parity check matrix, i.e. a parity check matrix with much more zeros than nonzero elements.

In particular, we will focus on LDPC codes defined by {0, 1}-matrices, i.e. matrices only containing entries 0 and 1. Since 0 and 1 are elements of every field, such matrices yield valid codes over any finite field F. ⋆ The author is supported by a PhD fellowship of the Research Foundation -Flanders (FWO).

Originally introduced by Gallager [START_REF] Gallager | Low density parity check codes[END_REF], LDPC ('low density parity check') codes are used frequently these days due to their excellent empirical performance under belief-propagation/sum-product decoding. In some cases, their performance is even near to the Shannon limit [START_REF] Mackay | Near Shannon limit performance of low density parity check codes[END_REF].

To exploit structural properties, one usually wants an explicit construction rather than random matrices. Lately, many constructions related to finite geometries have been studied because of their low complexity decoding features [START_REF] Kou | Low-density parity-check codes based on finite geometries: a rediscovery and new results[END_REF][START_REF] Ngatched | An improved decoding algorithm for finite-geometry LDPC codes[END_REF], such as generalized quadrangles [START_REF] Kim | Small weight code words in LDPC codes defined by (dual) classical generalized quadrangles[END_REF][START_REF] Liu | LDPC codes from generalized polygons[END_REF], linear representations [START_REF] Pepe | Small weight code words in the LDPC codes arising from linear representations of geometries[END_REF][START_REF] Vandendriessche | Some low-density parity-check codes derived from finite geometries[END_REF][START_REF] Vandendriessche | LDPC codes associated with linear representations of geometries[END_REF] and partial and semipartial geometries [START_REF] Johnson | Codes for Iterative Decoding From Partial Geometries[END_REF][START_REF] Li | Regular LDPC codes from semipartial geometries[END_REF]. Geometrical LDPC codes have been used in several high-end modern data transmission systems [START_REF] Djordjevic | Projective geometry LDPC codes for ultralong-haul WDM high-speed transmission[END_REF][START_REF] Djordjevic | Projective-Plane Iteratively Decodable Block Codes for WDM High-Speed Long-Haul Transmission Systems[END_REF] and in entanglement-assisted quantum decoding [START_REF] Clark | Entanglement-assisted quantum low-density parity-check codes[END_REF].

In [START_REF] Johnson | Codes for Iterative Decoding From Partial Geometries[END_REF], the authors show that LDPC codes derived from partial and semipartial geometries have excellent empirical performance under LDPC decoding methods based on belief propagation, and they derive bounds on the dimension and minimum distance of these codes. In this paper, we will improve the known bounds on the minimum distance and we provide several new theoretical results and computer results about it. Similar techniques can be used for other relevant parameters such as stopping distance, trapping distance or pseudodistance, but this falls beyond the scope of this paper.

Finite Geometry LDPC codes

To obtain the best decoding performance, one usually refrains from working with random {0, 1}-matrices. Instead, one will work with codes associated with finite combinatorial structures, and in particular, finite geometry codes. From now on, we will assume that F is a prime field, as the F p h -code associated to a {0, 1}parity check matrix is equivalent to the direct sum of h copies of the associated F p -code, and hence has the same minimum distance.

In this section, we provide a new lower bound on the minimum distance of finite geometry LDPC codes with girth at least 6 in their associated Tanner graph. For all point-line finite geometries, this condition is fulfilled. In many cases, our bound turns out to be better than the best known bounds. In particular, it also improves the known bounds on the minimum distance of general partial and semipartial geometry codes. Definition 4. An incidence structure (P, B, I) consists of a finite set P, the elements of which are called points, a finite set B, the elements of which are called blocks, and a relation I ⊆ P × B, which is called the incidence relation. Often, B is a collection of subsets of P and the incidence relation is simply ∈. If additionally, any two distinct points are contained in at most one common block (or equivalently, any two distinct blocks contain at most one common point), the blocks are sometimes called lines.

The fact that the Tanner graph has girth at least 6 can be stated equivalently (geometrically) as the fact that two different blocks have at most one common point or, again equivalently, as the fact that two different points are contained in at most one common block. Definition 5. The dual incidence structure to an incidence structure (P, B, I) is the incidence structure (B, P, I ′ ) with pIb ⇔ bI ′ p for all p ∈ P and all b ∈ B. For example, the dual of (P, B, ∈) is (B, P, ∋). Definition 6. The incidence matrix of an incidence structure (P, B, I), with P = {p 1 , . . . , p m } and B = {b 1 , . . . , b n } is the m × n matrix, in which the rows are labeled by the points and the columns are labeled by the blocks, such that H ij = 1 if p i Ib j , and H ij = 0 otherwise. The incidence matrix of the dual incidence structure is then simply the transposed of this matrix. Definition 7. Given an incidence structure (P, B, I), we define C F to be the code over F having its parity check matrix H equal to the incidence matrix of an incidence structure (P, B, I). If the field F is clear from the context, we will simply write C. This gives the code a nice interpretation: a code word c of the code corresponds to a map ϕ : B → F such that, for each point r ∈ P, we have L∋r ϕ(L) = 0 over F. We call ϕ(L) the coefficient of the line L in the code word c, and we denote this by c L . Similarly, when considering the code derived from the dual structure, a code word is a map ϕ : P → F such that, for each block L ∈ B, we have r∈L ϕ(r) = 0 over F.

For arbitrary incidence structures, the dimension of the corresponding code can easily be determined in polynomial time, by simple row reduction. The minimum distance is however not at all easy to determine. In fact, it has been shown [START_REF] Vardy | The intractability of computing the minimum distance of a code[END_REF] that the determination of the minimum distance is an NP-complete problem in general, and even in the special case of LDPC codes, the problem remains unfeasible [START_REF] Hu | On the computation of the minimum distance of low-density parity-check codes[END_REF]. In the general case, we can only expect upper and lower bounds on the minimum distance. The best known bound is the following.

Theorem 1 ([1]

). Let C be an LDPC code defined by a {0, 1}-parity check matrix H over the finite field F p . If v is the minimum number of ones in a column of the parity check matrix H, and r is the maximum number of common ones in any two different columns, then

d ≥ 2 p (p -1) v r + 1 . (1)
3 Partial and Semipartial Geometries

However, for several infinite families of incidence structures, in particular those from finite geometries, we can find strongly improved bounds or even the exact minimum distance, using geometrical techniques. We focus on the case where the largest set (P or B) corresponds to the positions, as this results in the highest code rates, which is important for LDPC transmission. In case anything noteworthy can be said about the other (lowerrate) code, we will add this in a remark. Definition 8. An (s, t, α)-partial geometry is an incidence structure (P, B, ∈) for which:

(a) each block contains exactly s+1 points and each point is contained in exactly t + 1 blocks; (b) any two distinct blocks have at most one point in common; and (c) for any non-incident point-block pair (p, L) there are exactly α blocks which contain p and which intersect L.

A partial geometry is called proper when 1 < α < min(s, t).

Clearly, the dual of an (s, t, α)-partial geometry is a (t, s, α)-partial geometry. In an (s, t, α)-partial geometry (P, B, I), one has |P| = (s+1)(st+α)

α and |B| = (t+1)(st+α) α . Hence, |P| ≥ |B| is equivalent to s ≥ t.
Definition 9. Slightly more general, an (s, t, α, µ)-semipartial geometry is an incidence structure (P, B, ∈) for which:

(a) each block contains exactly s+1 points and each point is contained in exactly t + 1 blocks; (b) any two distinct blocks have at most one point in common; (c) for any non-incident point-block pair (p, L), there are either 0 or exactly α blocks which contain p and which intersect L; and (d) for any two points p, p ′ not contained in a common block, there are exactly µ points which are contained in a common block with p and in a common block with p ′ .

A semipartial geometry is called proper when it is not a partial geometry, and 1 < α < min(s, t).

Clearly, µ ≤ α(t + 1), with µ = α(t + 1) if and only if the semipartial geometry is a partial geometry. The dual of a semipartial geometry is in general not a semipartial geometry, hence we will not consider the dual structure here. It can be proven [START_REF] Hirschfeld | General Galois Geometries[END_REF]Theorem 26.7.5] that if a semipartial geometry is not a partial geometry, then |B| ≥ |P|. Hence, for semipartial geometries, we will let B correspond to the positions of the code words. Definition 10. An (n, k)-arc K in PG(2, q) is a set of n points of PG(2, q), such that each line intersects K in at most k points. Clearly, the size |K| = n of an (n, k)-arc is at most 1 + (q + 1)(k -1) = qk -q + k, since each of the q + 1 lines through any one point of K can contain at most k -1 other points of K. Definition 11. A maximal (n, k)-arc K in PG(2, q) (often incorrectly referred to as a maximal (n, k)-arc or maximal (n, k)-arc) is an (n, k)-arc of size n = qk -q + k, with 1 < k < q. It has been shown [START_REF] Ball | Maximal arcs in Desarguesian planes of odd order do not exist[END_REF] that maximal (n, k)-arcs in PG(2, q) only exist when q is even and k divides q. In that case, each line intersects K in either 0 (and then the line is called skew) or k (and then the line is called secant) points. A maximum 2-arc is called a hyperoval. When it is not necessary to specify k, or when the parameters are clear from the context, we will simply write maximal arc.

Up to dualization, only two infinite classes of proper partial geometries are known, and both of them are related to maximal arcs. We now provide a construction of these geometries below. We also provide a construction for the common proper semipartial geometries, listed in [START_REF] Hirschfeld | General Galois Geometries[END_REF].

(a) Let K be a maximal (n, k)-arc in PG(2, q), with q even. Define S(K) = (P, B, ∈) as follows: P is the set of points outside of K, and B is the set of lines which contain at least one (and hence exactly k) points of K. Then S(K) is an (s, t, α)-partial geometry, where s = q-k, t = q-q k and α = q-q k +1-k. (b) Let again K be a maximal (n, k)-arc in PG(2, q), with q even. Define T * 2 (K) = (P, B, ∈) as follows: embed this PG(2, q) (containing K) as a plane π 0 in PG(3, q), let P be the set of points of PG(3, q) outside of π 0 and let B be the set of lines of PG(3, q) which intersect π 0 in a point of K (and in no points of π 0 \ K). Then T * 2 (K) is an (s, t, α)-partial geometry, where s = q -1, t = |K| -1 = qk -q + k -1 and α = k -1. (c) Similarly, let K be a Baer subplane in PG(2, q), with q = p h , h even, and repeat the construction from (b). Then T * 2 (K) is an (s, t, α, µ)-semipartial geometry, where s = q -1, t = q + √ q, α = √ q and µ = √ q( √ q + 1).

(d) Similarly, let K be a Hermitian arc in PG(2, q), with q = p h , h even, and repeat the construction from (b). Then T * 2 (K) is an (s, t, α, µ)-semipartial geometry, where s = q -1, t = q √ q, α = √ q and µ = q(q -1).

(e) Let Π n-2 be an (n -2)-dimensional subspace of the projective n-space PG(n, q), with n ≥ 3. As the point set P, we take the lines of PG(n, q) which have no point in common with Π n-2 . As the block set B, we take the planes of PG(n, q) which have exactly one point in common with Π n-2 . Then (P, B, ⊂) is an (s, t, α, µ)-semipartial geometry, where now s = q 2 -1, t = q n-2 + q n-3 + • • • + q, α = q and µ = q(q + 1). (f) Consider the projective n-space PG(n, q), with n ≥ 3. As the point set P, we take the lines of PG(n, q). As the block set B, we take the planes of PG(n, q). Then (P, B, ⊂) is an (s, t, α, µ)-semipartial geometry, where s = q(q + 1), t = q n-2 + q n-3 + • • • + q, α = q + 1 and µ = (q + 1) 2 .

Similar to [START_REF] Johnson | Codes for Iterative Decoding From Partial Geometries[END_REF], C is a linear code over a finite field F, having its parity check matrix H equal to the incidence matrix of a partial or semipartial geometry. Important hereby is that we will always set q = p h , with F = F p . Hence, the characteristic of the code's field and of the geometry's field coincide. This is known experimentally to yield the highest code rates. We will now further study each of these codes, and we study the minimum distance of these codes. We improve the existing bounds from [START_REF] Johnson | Codes for Iterative Decoding From Partial Geometries[END_REF] and we try to determine when the bounds are sharp. We finish this section with a definition, which will appear to be useful in the study of several of the listed partial and semipartial geometries. Definition 12. The support of a code word c ∈ C is defined as the set of nonzero (as elements of F p ) positions of the code word, and is denoted by supp(c). The weight or Hamming weight of that code word is then the number of elements in its support.

Geometrically, supp(c) corresponds to the following. When positions correspond to points, supp(c) is a set of points, namely supp(c) = {r ∈ P : ϕ(r) = 0} .

(

) 2
When positions correspond to lines, supp(c) is a set of lines, namely

supp(c) = {ℓ ∈ B : ϕ(ℓ) = 0} . (3)
In the binary case, i.e. when p = 2, the support uniquely determines its code word c: in this case, c is simply the characteristic vector of its support. Often in this case, we will identify the support of a codeword with its corresponding set of points or lines.

The codes arising from S(K)

To begin with, we will study the LDPC codes derived from our first structure: S(K), with K a maximal (n, k)-arc in PG(2, q). Since maximal (n, k)-arcs only exist when q is even, we will only consider binary codes in this section.

For the geometry S(K), it turns out that we do not need to study the two types of codes separately (once for points corresponding to positions, once for lines corresponding to positions), as we will now show. Definition 13. Let K be a maximal (n, k)-arc. Consider the set of lines of PG(2, q) skew to K. Clearly, each point lies on either 0 or q k of these lines, hence it is the dual of a maximum q k -arc. This maximum q k -arc is called the dual maximal arc of K. Theorem 2. Let K be a maximal arc and let K ′ be its dual. Then the block code derived from K is equivalent to the point code derived from K ′ .

Hence, in the remainder of this section, we will only study the point code C. The following conjecture was proven in [3, Theorem 3.10] when K is a regular hyperoval; we conjecture it to be true for arbitrary maximal arcs.

Conjecture 1. Let K be a maximal arc in PG(2, q), q even. Then the incidence vector of each line in PG(2, q) can be written as a linear combination of incidence vectors of secant lines to K.

Computer simulations show that Conjecture 1 is true for all maximal arcs in PG(2, q) with q ≤ 32, and for all known maximal arcs in PG(2, q), q ≤ 64. We conjecture it to be true for arbitrary q; it would be interesting to prove this in general. However, this appears to be a nontrivial problem even for k = 2 (when K is a nonregular hyperoval). An equivalent way of stating this problem is to ask whether the binary rank of the incidence matrix is always equal to 3 h + 1, the binary rank of the incidence matrix of PG(2, q), for q even [START_REF] Smith | On the p-rank of the incidence matrix of points and hyperplanes in a finite projective geometry[END_REF].

A large class of maximal arcs in PG(2, q), q even, was constructed by Denniston [START_REF] Denniston | Some maximal arcs in finite projective planes[END_REF]. In particular, he constructed an example for all possible values of k and q. However, other examples have been constructed as well, notably by Mathon [START_REF] Mathon | New maximal arcs in Desarguesian planes[END_REF] and others. We have been able to prove Conjecture 1 for Denniston arcs. From now on, we assume K to be a maximal (n, k)-arc for which Conjecture 1 holds (for example, a maximal arc of Denniston type). consisting of code words which do not contain any point of K in their support. In particular,

dim(C) = (q 2 + q + 1 -|K|) -(3 h + 1) , (4)
where q = 2 h .

Theorem 5. The minimum distance of C has d(C) ≥ q + 2, and equality is attained if and only if there exists a hyperoval disjoint from K.

For q ≤ 16, brute-force calculations have shown that there always exists a hyperoval skew to K when 1 < k < q, yielding d(C) = q + 2 for every maximal arc in PG(2, q), with q ≤ 16. It would be interesting to find out if this holds in general.

5 The codes arising from T * 2 (K) Definition 14. A (q + t, t)-arc of type (0, 2, t) in PG(2, q), with 2 < t < q, is a set S of q + t points in PG(2, q) for which every projective line ℓ meets S in either 0, 2 or t points.

Definition 14 was introduced in [START_REF] Korchmáros | On (q + t, t)-arcs of type (0, 2, t) in a Desarguesian plane of order q[END_REF] and it was proven that (q + t, t)-arcs of type (0, 2, t) can only exist if q is even. Moreover, they prove that t needs to be a divisor of q, i.e. t = 2 r with r ≤ h. Several infinite families of these arcs are known, see [START_REF] Gács | On (q + t, t)-arcs of type (0, 2, t)[END_REF][START_REF] Korchmáros | On (q + t, t)-arcs of type (0, 2, t) in a Desarguesian plane of order q[END_REF][START_REF] Vandendriessche | Codes of Desarguesian projective planes of even order, projective triads and (q + t, t)-arcs of type (0, 2, t)[END_REF]. A hyperoval in PG(2, q), q = 2 h with h ≥ 1, can be seen as a (q + 2, 2)-arc of type (0, 2, 2). One can see (q + t, t)-arcs of type (0, 2, t) as a generalization of hyperovals. The symmetric difference of two lines of PG(2, q) can be seen as a (2q, q)-arc of type (0, 2, q).

For the geometry T * 2 (K), we have to consider three cases: K is a maximal (n, k)-arc, K is a Baer subplane, or K is a Hermitian arc. In each of these cases, one has |K| > q, hence there are more blocks than points and the code will be constructed using blocks (here: lines) as the positions of the code. Definition 15. Let π be any plane different from π 0 such that the line L = π 0 ∩π contains at least two points of K. Let p 1 , p 2 be two distinct points of K∩L. Define ϕ as follows: all the lines in π \ π 0 through p 1 map to 1, all the lines in π \ π 0 through p 2 map to -1 and all other lines map to 0. Then L∋r ϕ(L) = 0 for any point r, since for r ∈ π we get one line with coefficient 1 and one line with coefficient -1 (and all other lines 0), and for r / ∈ π we only sum up lines with coefficient 0; hence this defines a code word of weight 2q. Such a code word is called a plane word.

In [START_REF] Pepe | Small weight code words in the LDPC codes arising from linear representations of geometries[END_REF]Proposition 5], it is shown that d ≥ q + √ q (if K is a Baer subplane or Hermitian arc) or d ≥ q + q k-1 (if K is a maximal (n, k)-arc). In the first case, this bound is sharp when p = 2, since Korchmáros and Mazzocca [START_REF] Korchmáros | On (q + t, t)-arcs of type (0, 2, t) in a Desarguesian plane of order q[END_REF] have shown the existence of a (q + √ q, √ q)-arc of type (0, 2, √ q) with the points on a Baer subline as its dual t-secants. For p = 2 or if K is a maximal (n, k)-arc with k > 2, this bound is no longer sharp, and the exact minimum distance is not known in these cases.

In the second case (when K is a maximal (n, k)-arc and hence p = 2), we can however find partial results. For k = 2, one can easily show that d = 2q, and the code words of minimum weight correspond to dual (2q, q)-arcs of type (0, 2, t), which are exactly the plane words from [START_REF] Vandendriessche | Some low-density parity-check codes derived from finite geometries[END_REF][START_REF] Vandendriessche | LDPC codes associated with linear representations of geometries[END_REF]. For k > 2, we can however find a geometrical upper bound on the minimum distance d, in the following theorem, which holds for any maximal arc K. Theorem 6. One has d ≤ q + r, where r is the smallest integer for which there exists a line ℓ in π 0 and a dual (q + r, r)-arc of type (0, 2, r) having its dual r-secants contained in ℓ ∩ K.

Conjecture 2. The bound in Theorem 6 is always sharp, i.e. d = q + r, where r is the smallest integer for which there exists a line ℓ in π 0 and a dual (q + r, r)-arc of type (0, 2, r) having its dual r-secants contained in ℓ ∩ K.

Computer simulations have shown the bound in Theorem 6 to be sharp for small values of q and for several constructions with larger q. We conjecture it to be sharp for all q. In all cases we tested, this resulted in a maximum weight of

d = q + q 2 ⌊log 2 (k-1)⌋ = q + 2q k . (5)
It would be interesting to prove this in the general case; even for k = 4 we only achieved a partial result (the conjecture being that the case after 'or' in Theorem 7 can never occur).

Theorem 7. When k = 4, either (5) holds (i.e. d = 3q 2 ) or d = 4s with q 3 ≤ s ≤ 3 q 8 and the code words of minimum weight consist of four sets of s lines, each concurrent at a point of a fixed line ℓ, with the additional property that each line contains 3s-q 2 points on 4 of these lines and 3(q-s) 2 points on two of these lines.

The codes arising from projective planes and lines

Now we will study examples (e) and (f) in our list of partial and semipartial geometries. Here, a code word is a mapping B → F, associating an F-coefficient to each plane in B, such that the sum of all coefficients of planes of B containing a line ℓ is zero, for every ℓ ∈ P. Denote these codes by C (e) and C (f ) respectively.

Let C ⊥ PG(2,q) be the similar code with spaces one dimension lower: the positions of C PG (2,q) are the lines of PG(2, q) and a code word c ∈ C PG(2,q) is a map which associates a coefficient in F p to each line of PG(2, q), such that the sum of all coefficients of lines through a given point, equals zero. Theorem 8. The codes C (e) and C (f ) contain code words of weight 2q 2 -q-p p-1 q, hence d ≤ 2q 2 -q-p p-1 q.

Explicit constructions for code words of this weight are known.

Theorem 9. In the binary case, i.e. when p = 2, equality is attained: d(C (e) ) = d(C (f ) ) = q(q + 2).

We cannot fully characterize the code words of minimum weight, however, we can greatly reduce the space in which code words have to be searched for.

Theorem 10. If c is a code word of C (e) or C (f ) , of weight w < 2(q 2 +q +1)+2, then supp(c) is contained in a 3-space.

We summarize the new results on the minimum distances in Table 1. In almost all cases, we obtain improvements to the bound in Theorem 1. N/A T * 2 (K) with K Baer subplane d = q + √ q d > q + √ q T * 2 (K) with K Hermitian arc d = q + √ q d > q + √ q

Lines and planes skew to (n -2)-space d = q(q + 2) d ≤ q " 2q -q-p p-1

"

All lines and planes of PG(n, q) d = q(q + 2) d ≤ q " 2q -q-p p-1 "

Theorem 3 .

 3 If K is an arc of Denniston type, then Conjecture 1 is true.

Theorem 4 .

 4 The code C is the subset of the dual projective plane code C ⊥ PG(2,q)

Table 1 .

 1 Summary of the new bounds obtained for partial and semipartial geometry codes. Here, ≈ stands for conjectured equality.

	Code	p = 2	p = 2
	General (semi)partial geometry
	(blocks correspond to positions)

d ≥ s + 2 d ≥ 2 p ((p -1)s + p) General (semi)partial geometry (points correspond to positions) d ≥ t + 2 d ≥ 2 p ((p -1)t + p) S(K) with K maximal (n, k)-arc d ≈ q + 2 N/A T * 2 (K) with K maximal (n, k)-arc d ≈ q + 2q k


Lam Pham Sy

Valentin Savin
email: valentin.savin@cea.fr

David Declercq
email: declercq@ensea.fr

Nghia Pham
email: hpham@eutelsat.fr

Scheduled-PEG construction of LDPC codes for Upper-Layer FEC

Keywords: LDPC codes, bipartite graph, PEG, UL-FEC, decoding overhead/inefficiency

The Progressive Edge Growth (PEG) algorithm is one of the most widely-used methods for constructing finite length LDPC codes. In this paper we consider the PEG algorithm together with a scheduling distribution, which specifies the order in which edges are established in the graph. The goal is to find a scheduling distribution that yields "the best" performance in terms of decoding overhead, performance metric specific to erasure codes and widely used for upper-layer forward error correction (UL-FEC). We rigorously formulate this optimization problem, and we show that it can be addressed by using genetic optimization algorithms. We also exhibit PEG codes with optimized scheduling distribution, whose decoding overhead is less than half of the decoding overhead of their classical-PEG counterparts.

Context and motivations

Low Density Parity Check (LDPC) codes constitute a very broad class of FEC codes, distinguished by the fact that they are defined by sparse parity-check matrices, and can be iteratively decoded in linear time with respect to their block-length. Invented by Gallager in early 60's [START_REF] Gallager | Low Density Parity Check Codes[END_REF], but considered impractical to implement, these codes have been neglected for more that three decades, and "rediscovered" in the late 90's [START_REF] Mackay | Good error-correcting codes based on very sparse matrices[END_REF]. Nowadays, a large body of knowledge has been acquired (analysis, optimization, construction); LDPC codes are known to be capacity approaching codes for a large class of channels [START_REF] Richardson | Design of capacity approaching irregular low density parity check codes[END_REF], and became synonymous with modern coding.

However, this capacity approaching property holds in the asymptotic limit of the code length, and codes optimized from this asymptotic perspective may suffer significant performance degradation at practical lengths. Actually, the asymptotic optimization, performed by using density-evolution methods [START_REF] Richardson | The capacity of low-density parity-check codes under message-passing decoding[END_REF], yields an irregularity profile, which specifies the distribution of node-degrees in the bipartite (Tanner) graph [START_REF] Tanner | A recursive approach to low complexity codes[END_REF] associated with the code. It is assumed that the girth4 of the bipartite graph goes to infinity with the code-length. Hence, optimized irregularity profiles can be used to construct codes that are "long enough" (at least few thousand bits) to avoid short cycles, although they must be "short enough" to be practical.

One of the most widely-used method for constructing finite length codes is the Progressive Edge Growth (PEG) algorithm [START_REF] Hu | Regular and irregular progressive edge-growth tanner graphs[END_REF]. It constructs bipartite graphs with large girth, by establishing edges progressively: the graph grows in an edgeby-edge manner, optimizing each local girth. There is an underlying edge order within the PEG, corresponding to the order in which edges are established in the graph. In general, edges are progressively established starting with those incident to symbol-nodes of degree-2 and ending with those incident to symbol-nodes of maximum degree. However, any other order with respect to the symbol-node degrees would also be possible. Besides, for a given symbol-node degree, edges can be established in a node-by-node manner (all edges incident to some symbol node are established before moving to the next symbol-node), or in a degree-by-degree manner (a first edge is established for each symbol-node, then a second edge is established for each symbol-node, and so on until all the symbol-nodes reach the given degree). Although this order may significantly impact the performance of the constructed code, it is rather difficult to formalize and has practically not been investigated in the literature. There are however several papers that aim to enhance the PEG construction by optimizing some objective function, as for instance minimizing the number of cycles created [START_REF] Venkiah | Design of Cages with a Randomized Progressive Edge Growth Algorithm[END_REF], or minimizing the approximate cycle extrinsic (ACE) message degree [START_REF] Tian | Construction of irregular LDPC codes with low error floors[END_REF], [START_REF] Xiao | Improved progressive-edge-growth (PEG) construction of irregular LDPC codes[END_REF].

Scheduled-PEG construction

In this paper we consider the PEG algorithm together with a scheduling distribution, which will be referred to as scheduled-PEG, or SPEG for short. Within the SPEG algorithm, symbol-nodes are divided into subsets, each subset containing symbol-nodes of same degree. Edges incident to the symbol-nodes of a subset are established in a degree-by-degree manner, before moving to the next subset. The scheduling distribution specifies the fraction of nodes within each subset. Our purpose is to find a scheduling distribution that yields the best performance in terms of decoding overhead (performance metric widely used for UL-FEC). We rigorously formulate this optimization problem, and we show that it can be addressed by using genetic optimization algorithms.

The proposed Scheduled-PEG algorithm allows the enhancement of the classical PEG algorithm. By varying the scheduling distribution, one can explore the ensemble of LDPC codes with fixed code-length and degree distributions, which allows us to find codes with very small average inefficiency (the performance metric considered in this paper).

We show that the SPEG algorithm can be successfully combined with genetic optimization algorithms [START_REF] Storn | Differential evolution -a simple and efficient heuristic for global optimization over continuous spaces[END_REF], which significantly improves the average inefficiency of the constructed LDPC codes over the classical-PEG construction. In terms of error rate curves, this translates into a significant improvement of the waterfall region.

Finally, we remark that the optimization of the scheduling distribution makes use of the specific channel model (through the use of the decoding inefficiency). Hence, LDPC codes constructed by using the SPEG algorithm together with an optimized scheduling distribution are channel dependent. However, the proposed algorithm could be generalized for more general channel models (e.g. by optimizing with respect to a target FER, or to the area under the FER curve.).

Length of a shortest cycle.

Acknowledgment

This work was supported by the French National Research Agency (ANR), grant No 2009 VERS 019 04 -ARSSO project.

The complete version of the paper can be found on hal.inria.fr and arxiv.org websites.


Swanhild U Meyer
email: meyers@wzw.tum.de

Michael W Pfaffl

Susanne E Ulbrich

Normalization strategies for microRNA profiling experimentsa 'normal' way to a hidden layer of complexity?

Keywords: microarray, microRNA, normalization, profiling, real time quantitative PCR, ultra high throughput sequencing

MicroRNA (miRNA) profiling is a first important step in elucidating miRNA functions. Real time quantitative PCR (RT-qPCR) and microarray hybridization approaches as well as ultra high throughput sequencing of miRNAs (small RNA-seq) are popular and widely used profiling methods. All of these profiling approaches face significant introduction of bias.

Normalization, often an underestimated aspect of data processing, can minimize systematic technical or experimental variation and thus has significant impact on the detection of differentially expressed miRNAs. At present, there is no consensus normalization method for any of the three miRNA profiling approach. Several normalization techniques are currently in use, of which some are similar to mRNA profiling normalization methods, while others are specifically modified or developed for miRNA data. The characteristic nature of miRNA molecules, their composition and the resulting data distribution of profiling experiments challenges the selection of adequate normalization techniques. Based on miRNA profiling studies and comparative studies on normalization methods and their performances, this review provides a critical overview of commonly used and newly developed normalization methods for miRNA RT-qPCR, miRNA hybridization microarray, and small RNA-seq datasets. Emphasis is laid on the complexity, the importance and the potential for further optimization of normalization techniques for miRNA profiling datasets.

Introduction

The importance of microRNAs (miRNAs), a class of small RNAs mediating posttranscriptional gene regulation, has been shown in several cellular processes as well as in different metabolic and pathologic conditions. Predominantly, miRNAs repress gene expression by binding of target mRNAs and formation of the RNA-induced silencing complex (RISC) (reviewed in [START_REF] Carthew | Origins and Mechanisms of miRNAs and siRNAs[END_REF]. Multiple mechanisms by which miRNAs cause translational repression at the translation initiation step or at post-initiation steps as well as mRNA decay through deadenylation have been reported (reviewed in [START_REF] Fabian | Regulation of mRNA translation and stability by microRNAs[END_REF]. Moreover, miRNAs activate rather than repress translation in quiescent cells [START_REF] Vasudevan | Switching from repression to activation: microRNAs can upregulate translation[END_REF]). However, miRNA-mediated activation of translation is probably not a general mechanism in nonproliferating cells [START_REF] Fabian | Regulation of mRNA translation and stability by microRNAs[END_REF].

The expression, regulation and function of miRNA are addressed in an increasing number of studies. To date, more than 10,500 miRNAs from 115 species are registered in the miRSanger Base (Release 14) (http://www.mirbase.org) [START_REF] Griffiths-Jones | miRBase: tools for microRNA genomics[END_REF]) and according to bioinformatic predictions, this number is expected to increase further [START_REF] Sheng | Mammalian microRNA prediction through a support vector machine model of sequence and structure[END_REF]). The specific function of individual miRNAs is only partly known and in most cases not fully understood. High throughput miRNA profiling is a first important step in characterizing specific miRNA signatures and thus, in unravelling the regulatory functions of this species of small RNAs.

Understanding miRNA functions implies great potential for the application in the field of biotechnology as well as diagnostic and therapeutic approaches. For example, miRNAs have been shown to be key regulators for the induction or maintenance of cell fate in plants [START_REF] Carlsbecker | Cell signalling by microRNA165/6 directs gene dose-dependent root cell fate[END_REF], mammalian cells [START_REF] Cardinali | Microrna-221 and microrna-222 modulate differentiation and maturation of skeletal muscle cells[END_REF], cancer [START_REF] Kim | Myc-induced microRNAs integrate Myc-mediated cell proliferation and cell fate[END_REF], and stem cells [START_REF] Gunaratne | Embryonic stem cell microRNAs: defining factors in induced pluripotent (iPS) and cancer (CSC) stem cells?[END_REF][START_REF] Gangaraju | MicroRNAs: key regulators of stem cells[END_REF]. Furthermore, miRNAs can serve as biomarkers [START_REF] Baker | RNA interference: MicroRNAs as biomarkers[END_REF]. Experimental evidence demonstrates that correction of specific miRNA alterations using miRNA mimics or antagomirs can reverse the phenotype in cancerous cells [START_REF] Wang | MicroRNA-based therapeutics for cancer[END_REF]. Thus, miRNA-based therapeutic interventions as well as diagnostics are being developed [START_REF] Pfeifer | Pharmacological potential of RNAi -focus on miRNA[END_REF].

In addition, miRNA expression profiles may be more accurate than mRNA expression profiles in disease classification [START_REF] Lu | MicroRNA expression profiles classify human cancers[END_REF]. Accordingly, numerous methods have been established to identify and globally quantify small RNAs (Li and [START_REF] Ruan | MicroRNA detection by microarray[END_REF][START_REF] Yin | Profiling microRNA expression with microarrays[END_REF][START_REF] Benes | Expression profiling of microRNA using real-time quantitative PCR, how to use it and what is available[END_REF][START_REF] Kong | Strategies for profiling microRNA expression[END_REF]. Real-time quantitative PCR (RT-qPCR) was optimized to not only perform single reverse transcription and PCR amplification experiments but also for a large number of miRNAs in parallel by multi-or megaplexing [START_REF] Chen | Real-time quantification of microRNAs by stem-loop RT-PCR[END_REF][START_REF] Benes | Expression profiling of microRNA using real-time quantitative PCR, how to use it and what is available[END_REF]. Currently, RT-qPCR is the method of choice for validation of miRNA profiling results from other holistic platforms. Hybridization based quantitative miRNA profiling by microarrays [START_REF] Yin | Profiling microRNA expression with microarrays[END_REF][START_REF] Ruan | MicroRNA detection by microarray[END_REF] has become a widely used and popular method as e.g. a valuable tool for biomarker and therapeutic target identification and functional prediction of miRNAs by correlating miRNA expression patterns to corresponding mRNA [START_REF] Jayaswal | Identification of microRNAs with regulatory potential using a matched microRNA-mRNA time-course data[END_REF][START_REF] Manakov | Reciprocal regulation of microRNA and mRNA profiles in neuronal development and synapse formation[END_REF]) and protein profiles [START_REF] Iliopoulos | Integrative microRNA and proteomic approaches identify novel osteoarthritis genes and their collaborative metabolic and inflammatory networks[END_REF]. MiRNA profiling strategies based on deep sequencing (reviewed in Wang et al. 2009;[START_REF] Linsen | Limitations and possibilities of small RNA digital gene expression profiling[END_REF]) allow the de novo identification as well as the relative quantification of miRNAs and are essential for getting a holistic picture of small RNA signatures. Each miRNA profiling strategy faces unique challenges. Specific strengths and entailed consequences are of distinct importance to consider depending on the nature of the research context (Table 1).

The analysis of microRNA expression faces several challenges. Both the short length and the heterogeneous GC content of miRNAs result in large impede intervals of melting temperatures complicating optimized probe or primer design [START_REF] Benes | Expression profiling of microRNA using real-time quantitative PCR, how to use it and what is available[END_REF][START_REF] Yin | Profiling microRNA expression with microarrays[END_REF]. Extended loop probes [START_REF] Wang | Direct and sensitive miRNA profiling from low-input total RNA[END_REF]), stem-loop primer [START_REF] Chen | Real-time quantification of microRNAs by stem-loop RT-PCR[END_REF], or the incorporation of modified nucleotides, e.g. locked nucleic acids [START_REF] Castoldi | miChip: an array-based method for microRNA expression profiling using locked nucleic acid capture probes[END_REF] or 2'-O-(2-methoxyethyl)-derivatives [START_REF] Beuvink | A novel microarray approach reveals new tissue-specific signatures of known and predicted mammalian microRNAs[END_REF]) have been used for normalization of melting temperatures. Furthermore, as the mature form of the miRNA is derived by processing of genome encoded hairpin-shaped precursors, the sequence of interest is not only present in the mature miRNA but also in the primary transcript (pri-miRNA) and the precursor miRNA (pre-miRNA). Finally, miRNAs within the same family may differ by a single nucleotide only (reviewed in [START_REF] Benes | Expression profiling of microRNA using real-time quantitative PCR, how to use it and what is available[END_REF]. Potential cross-hybridization or cross-sequencing specificity issues may complicate the discrimination of the expression of closely related miRNAs [START_REF] Willenbrock | Quantitative miRNA expression analysis: comparing microarrays with next-generation sequencing[END_REF]. In general, similarly to mRNA expression analysis, miRNA quantification depends on high quality RNA [START_REF] Becker | mRNA and microRNA quality control for RT-qPCR analysis[END_REF].

Thus, in addition to adequate experimental design, data analysis of miRNA profiling experiments needs to account for the specific physicochemical nature of miRNAs, their expression pattern, and the properties of the analytical tools used such as technical variation.

One particularly important aspect of preprocessing of miRNA profiling data is to apply an optimal normalization method. The purpose of data normalization is to minimize the effects of systematic experimental bias and technical variations. Therefore, normalization is a prerequisite for getting true biological changes and allowing biologically meaningful comparisons to be made. Several studies pointed out that selection of the data preprocessing method can have great impact on the resulting data outcome [START_REF] Lopez-Romero | Processing of Agilent microRNA array data[END_REF][START_REF] Hua | Comparison of normalization methods with microRNA microarray[END_REF][START_REF] Pradervand | Impact of normalization on miRNA microarray expression profiling[END_REF][START_REF] Risso | A modified LOESS normalization applied to microRNA arrays: a comparative evaluation[END_REF][START_REF] Sarkar | Quality assessment and data analysis for microRNA expression arrays[END_REF] such as identification of differentially expressed miRNAs and data interpretation. Thus, inappropriate normalization of the data can lead to incorrect conclusions. Rigorous normalization of miRNA data may even be more critical than that of other RNA functional classes since relatively small changes in miRNA expression may be biologically and clinically significant [START_REF] Peltier | Normalization of microRNA expression levels in quantitative RT-PCR assays: identification of suitable reference RNA targets in normal and cancerous human solid tissues[END_REF]Latham 2008, Chang et al. 2010).

Various normalization techniques have been developed in the context of mRNA profiling methods. These normalization approaches can in part be directly applied to miRNA data as well. However, some normalization methods have been challenged and adapted to the specific nature of miRNA profiling experiments. At present, there is no consensus normalization for either an RT-qPCR, hybridization microarray, or deep sequencing based miRNA profiling approach.

Data processing of miRNA profiling experiments

Prior to normalization, data preprocessing of miRNA profiling experiments includes platform and vendor specific steps, such as e.g. baseline adjustment and threshold setting for RT-qPCR analyses, background correction for microarray technology, or filtering for small RNAsequence data. Following these very first steps of raw data preprocessing the experimenter needs to choose the optimal normalization strategy to correct for systematic and technical variation enabling a better estimation of the biological variation.

Normalization approaches for miRNA RT-qPCR

The guidelines for quality control and standardization of RT-qPCR experiments imply the use of the optimal normalization method [START_REF] Bustin | Why the need for qPCR publication guidelines?--The case for MIQE[END_REF][START_REF] Bustin | The MIQE guidelines: minimum information for publication of quantitative real-time PCR experiments[END_REF]. This is not only important for mRNA, but as well for miRNA quantification. Normalization of RT-qPCR miRNA profiling data is needed as in addition to reflecting miRNA levels, signal intensities may also depend on reverse transcription and PCR reaction efficiencies. Normalized miRNA RT-qPCR profiling data is widely used for independent evaluation of the goodness of miRNA microarray normalization strategies [START_REF] Sarkar | Quality assessment and data analysis for microRNA expression arrays[END_REF][START_REF] Pradervand | Impact of normalization on miRNA microarray expression profiling[END_REF][START_REF] Sato | Intra-platform repeatability and inter-platform comparability of microRNA microarray technology[END_REF][START_REF] Hua | Comparison of normalization methods with microRNA microarray[END_REF]) and validation of microarray or small RNA-seq results [START_REF] Git | Systematic comparison of microarray profiling, real-time PCR, and next-generation sequencing technologies for measuring differential microRNA expression[END_REF]. RT-qPCR is generally accepted as gold standard for microRNA measurement [START_REF] Sato | Intra-platform repeatability and inter-platform comparability of microRNA microarray technology[END_REF][START_REF] Hua | Comparison of normalization methods with microRNA microarray[END_REF]) though this view has been recently challenged [START_REF] Git | Systematic comparison of microarray profiling, real-time PCR, and next-generation sequencing technologies for measuring differential microRNA expression[END_REF]. Normalization based on predefined invariant endogenous controls, reference miRNAs [START_REF] Peltier | Normalization of microRNA expression levels in quantitative RT-PCR assays: identification of suitable reference RNA targets in normal and cancerous human solid tissues[END_REF] or other small non-coding RNAs such as small nuclear, small nucleolar RNA (summarized in Table 2) or 5s rRNA, is a commonly used approach in miRNA RT-qPCR profiling data analysis [START_REF] Benes | Expression profiling of microRNA using real-time quantitative PCR, how to use it and what is available[END_REF][START_REF] Pradervand | Impact of normalization on miRNA microarray expression profiling[END_REF][START_REF] Mestdagh | A novel and universal method for microRNA RT-qPCR data normalization[END_REF]). However, the use of small non-coding RNAs other than miRNAs does not mirror the physicochemical properties of miRNA molecules and it has been argued that it is best to normalize genes with reference genes belonging to the same RNA class [START_REF] Vandesompele | Accurate normalization of real-time quantitative RT-PCR data by geometric averaging of multiple internal control genes[END_REF]. Using non-miRNA reference genes for qPCR normalization is not advisable when the overall abundance of miRNA varies, e.g., in experiments affecting the miRNA processing machinery, or in comparisons involving multiple tissues or combinations of tissues and cell lines [START_REF] Git | Systematic comparison of microarray profiling, real-time PCR, and next-generation sequencing technologies for measuring differential microRNA expression[END_REF]. Selection of invariant miRNAs identified by algorithms specifically developed for reference gene evaluation and selection e.g. based on reference gene ranking and stepwise elimination of the least stable gene [START_REF] Vandesompele | Accurate normalization of real-time quantitative RT-PCR data by geometric averaging of multiple internal control genes[END_REF], or repeated pairwise correlation and regression analysis [START_REF] Pfaffl | Determination of stable housekeeping genes, differentially regulated target genes and sample integrity: BestKeeper--Excel-based tool using pair-wise correlations[END_REF], or statistical linear mixed-effects modelling [START_REF] Andersen | Normalization of real-time quantitative reverse transcription-PCR data: a model-based variance estimation approach to identify genes suited for normalization, applied to bladder and colon cancer data sets[END_REF]) of the respective experimental data was superior over small non-coding RNA based normalization [START_REF] Mestdagh | A novel and universal method for microRNA RT-qPCR data normalization[END_REF][START_REF] Peltier | Normalization of microRNA expression levels in quantitative RT-PCR assays: identification of suitable reference RNA targets in normal and cancerous human solid tissues[END_REF]. Data driven invariant selection of miRNAs whose expression pattern is similar to the global mean expression [START_REF] Mestdagh | A novel and universal method for microRNA RT-qPCR data normalization[END_REF][START_REF] Chang | MicroRNA expression profiling to identify and validate reference genes for relative quantification in colorectal cancer[END_REF]) has been suggested. Moreover, invariant selection based on a distinguishable low standard deviation and high-mean population as suggested by [START_REF] Pradervand | Impact of normalization on miRNA microarray expression profiling[END_REF] for miRNA microarray preprocessing is generally applicable for RT-qPCR profiling experiments as well. Basically, the use of more than one reference gene increases the accuracy of quantification compared to the use of a single reference gene [START_REF] Vandesompele | Accurate normalization of real-time quantitative RT-PCR data by geometric averaging of multiple internal control genes[END_REF][START_REF] Andersen | Normalization of real-time quantitative reverse transcription-PCR data: a model-based variance estimation approach to identify genes suited for normalization, applied to bladder and colon cancer data sets[END_REF]).

Calculation of a plate normalizing factor for RT-qPCR based expression profiling platforms, a scaling method suggested by [START_REF] Wang | A PCR-based platform for microRNA expression profiling studies[END_REF], uses the average of eight selected miRNA expression values from a descending sorted list [START_REF] Wang | A PCR-based platform for microRNA expression profiling studies[END_REF]. Plate-normalizing factor normalization corresponds to an enlargement of percentile normalization and needs further validation by independent datasets prior to judge the robustness of this method.

For large scale microRNA expression profiling studies the mean expression value normalization outperformed the current normalization strategy that makes use of stable small RNA controls, such as e.g. snoRNAs proposed by manufacturers, in terms of better reduction of technical variation [START_REF] Mestdagh | A novel and universal method for microRNA RT-qPCR data normalization[END_REF]). However, the selection of a limited number of miRNAs or small RNA controls that resemble the mean expression value can be successfully used for normalization in follow-up studies where only a limited number of miRNA molecules are profiled to allow a more accurate assessment of relevant biological variation from a miRNA RT-qPCR profiling experiment [START_REF] Mestdagh | A novel and universal method for microRNA RT-qPCR data normalization[END_REF][START_REF] Chang | MicroRNA expression profiling to identify and validate reference genes for relative quantification in colorectal cancer[END_REF].

Normalization methods for miRNA microarray experiments

The first miRNA microarray experiments were accompanied by either normalization using scaling to the median or even no normalization of miRNA data by applying background signal subtraction only (summarized in [START_REF] Hua | Comparison of normalization methods with microRNA microarray[END_REF][START_REF] Pradervand | Impact of normalization on miRNA microarray expression profiling[END_REF]). Only recently, comparative studies on the relative performance of different normalization methods within a miRNA microarray platform have emphasized the need for evaluating and identifying appropriate normalization methods [START_REF] Rao | A comparison of normalization techniques for microRNA microarray data[END_REF][START_REF] Pradervand | Impact of normalization on miRNA microarray expression profiling[END_REF][START_REF] Hua | Comparison of normalization methods with microRNA microarray[END_REF]. Signal intensities of miRNA microarray experiments may be biased by differences in sample RNA preparation, dye labelling, hybridization and washing efficiency, peculiarities of print tip, spatial or hybridization specific effects or pre-amplification of extracted RNA. Thus, several different normalization approaches have been applied to decrease the introduced technical variance and to minimize over all variance. However, up to now there is no clear consensus about their relative performances [START_REF] Pradervand | Impact of normalization on miRNA microarray expression profiling[END_REF].

MiRNA microarrays can be single-color or dual-color systems calling for different normalization approaches. Single-colour miRNA microarrays have been predominately used, while dual-colour hybridization systems are less frequently prevalent [START_REF] Rao | A comparison of normalization techniques for microRNA microarray data[END_REF]). Both can be observed with respect to intra-array normalization for the correction of dye effects and inter-array approaches for the balance of the distribution differences among experiments [START_REF] Chiogna | A comparison on effects of normalisations in the detection of differentially expressed genes[END_REF].

Certain transformation or scaling based methodologies currently used for large-scale genome arrays have been adapted to and modified for miRNA arrays. Of these methods e.g. quantile [START_REF] Bolstad | A comparison of normalization methods for high density oligonucleotide array data based on variance and bias[END_REF] and LOESS (reviewed in [START_REF] Steinhoff | Normalization and quantification of differential expression in gene expression microarrays[END_REF] normalization as well as scaling (e.g. [START_REF] Hua | Comparison of normalization methods with microRNA microarray[END_REF][START_REF] Lopez-Romero | Processing of Agilent microRNA array data[END_REF]) are based on two assumptions, i) only a small portion of spots is differentially expressed, and ii) differentially expressed spots are homogeneously distributed with respect to both, over-and under-expressed miRNAs [START_REF] Risso | A modified LOESS normalization applied to microRNA arrays: a comparative evaluation[END_REF]). However, these assumptions could fail for miRNA platforms as they are printed with a relatively small number of selected sequences [START_REF] Risso | A modified LOESS normalization applied to microRNA arrays: a comparative evaluation[END_REF][START_REF] Hua | Comparison of normalization methods with microRNA microarray[END_REF]. Moreover, the number of expressed miRs in a given sample tends to be small [START_REF] Sarkar | Quality assessment and data analysis for microRNA expression arrays[END_REF]). Hence, the proportion of those miRNAs that are differentially expressed (among those expressed at all) is much larger than that observed when profiling global mRNA expression [START_REF] Sarkar | Quality assessment and data analysis for microRNA expression arrays[END_REF]). Thus, one needs to verify whether these assumptions hold true for the respective datasets. If necessary, one should choose e.g. a normalization method for which most algorithms make only the minimal assumption that there exists a set of miRNAs whose expression is constant like invariantbased normalization [START_REF] Pradervand | Impact of normalization on miRNA microarray expression profiling[END_REF]). Alternatively, a normalization method free of assumption ii) e.g. the majority of algorithms for variance stabilization normalization [START_REF] Huber | Variance stabilization applied to microarray data calibration and to the quantification of differential expression[END_REF] or even an assumption free approach [START_REF] Xiong | Using generalized procrustes analysis (GPA) for normalization of cDNA microarray data[END_REF]) can be utilized instead.

Quantile normalization is a transformation method originally proposed by [START_REF] Bolstad | A comparison of normalization methods for high density oligonucleotide array data based on variance and bias[END_REF] for oligonucleotide arrays. It is now widely used for one-color miRNA microarrays as well and was confirmed as one of the most robust methods [START_REF] Hua | Comparison of normalization methods with microRNA microarray[END_REF][START_REF] Pradervand | Impact of normalization on miRNA microarray expression profiling[END_REF][START_REF] Rao | A comparison of normalization techniques for microRNA microarray data[END_REF][START_REF] Bargaje | Consensus miRNA expression profiles derived from interplatform normalization of microarray data[END_REF]). Quantile normalization is an inter-array approach and equalizes the distributions of expression intensities across arrays. Thus, quantile normalization assumes that the overall distribution of signal intensity does not change. While this assumption likely holds true for the comparison of p53 overexpressing versus control cells [START_REF] Pradervand | Impact of normalization on miRNA microarray expression profiling[END_REF] or even for brain-heart comparisons according to Rao et al. [START_REF] Rao | A comparison of normalization techniques for microRNA microarray data[END_REF] where only 5 % of miRNAs were differentially expressed, it may not hold true in case large numbers of miRNAs are differentially expressed in only one direction. Such cases may be e.g. knockouts of essential miRNA biogenesis proteins which lead to a dramatic reduction in steady state miRNA levels by blocking production of mature miRNAs [START_REF] Rao | A comparison of normalization techniques for microRNA microarray data[END_REF].

Quantile normalization might be applicable to dual-labeled array data if red and green channel are treated as independent two single-labeled array data. On the contrary, if two single-labeled array data are considered as a dual-labeled data [START_REF] Do | Normalization of microarray data: single-labeled and dual-labeled arrays[END_REF] a LOESS normalization may be used.

LOESS (Locally Weighted Regression and Smooting Scatterplots) normalizations and its

variants [START_REF] Rao | A comparison of normalization techniques for microRNA microarray data[END_REF][START_REF] Hua | Comparison of normalization methods with microRNA microarray[END_REF][START_REF] Risso | A modified LOESS normalization applied to microRNA arrays: a comparative evaluation[END_REF] However, in a similar study, [START_REF] Sarkar | Quality assessment and data analysis for microRNA expression arrays[END_REF] did not find significant differences between print-tip LOESS and other normalizations. [START_REF] Risso | A modified LOESS normalization applied to microRNA arrays: a comparative evaluation[END_REF] proposed the non-parametric LOESSM normalization which scales the expression data on the global median expression rather than on zero. This modification relaxes the assumption of symmetry among up-and down-regulated genes [START_REF] Risso | A modified LOESS normalization applied to microRNA arrays: a comparative evaluation[END_REF]) and it was shown that LOESSM, in case of absence of channel-effect, outperformed other normalization methods [START_REF] Risso | A modified LOESS normalization applied to microRNA arrays: a comparative evaluation[END_REF].

Combined with Generalized Procrustes Analysis (GPA)an assumption free inter-array normalization [START_REF] Xiong | Using generalized procrustes analysis (GPA) for normalization of cDNA microarray data[END_REF]) -results were even more improved.

In essence, LOESS normalization and its modified variants demonstrate the adaptability of this approach. In addition, LOESS normalizations emerged as being robust in the reduction of non-biological bias, and it has been shown that the combination of LOESS and GPA is able to outperform other individual techniques.

Variance stabilization normalization (VSN), an inter-array transformation method, has frequently been applied to microRNA data [START_REF] Sarkar | Quality assessment and data analysis for microRNA expression arrays[END_REF][START_REF] Pradervand | Impact of normalization on miRNA microarray expression profiling[END_REF]. VSN was developed for mRNA arrays and is based on a parameterized arsinh transformation instead of a logarithmic transformation that calibrates sample-to-sample variations and renders variance approximately independent of the mean intensity [START_REF] Huber | Variance stabilization applied to microarray data calibration and to the quantification of differential expression[END_REF].

Spike-in VSN normalization as described restricts the model fit to spike-in spots [START_REF] Sarkar | Quality assessment and data analysis for microRNA expression arrays[END_REF]. Normalization intensities for all miRNAs are then obtained by applying the resulting transformation to all spots of interest on the array. Thus, reliable results can only be obtained for intensities within the range covered by the spike-in used. Moreover, the use of internal spike-ins can provide a reasonable metric for assessing the performance of different normalization schemes [START_REF] Sarkar | Quality assessment and data analysis for microRNA expression arrays[END_REF] or allow for absolute quantification of miRNA expression by microarrays [START_REF] Bissels | Absolute quantification of microRNAs by using a universal reference[END_REF]. [START_REF] Pradervand | Impact of normalization on miRNA microarray expression profiling[END_REF] developed a linear regression method to select non-changing miRNAs (invariants) and used these invariants to calculate VSN parameter (VSN-INV). The approach for selecting invariant miRNAs is particularly appropriate, if a significant fraction is expected to be differentially expressed since VSN used with default parameter settings assumes that most genes are not differentially expressed, whereas the invariant-based regression only assumes that a subpopulation of expressed genes does not change [START_REF] Pradervand | Impact of normalization on miRNA microarray expression profiling[END_REF]). [START_REF] Pradervand | Impact of normalization on miRNA microarray expression profiling[END_REF] drew the conclusion that VSN-INV and quantile normalization were the most robust normalization methods compared to VSN with default parameter or scaling. In general, one should note that VSN strongly affects the distribution of the large fraction of miRNAs whose expression is near or at background, resulting in the large increase of variability for those microRNAs [START_REF] Pradervand | Impact of normalization on miRNA microarray expression profiling[END_REF].

Invariant-based methods, or positive control normalization using the signal of predefined and stably expressed housekeeping (reference) genes, such as small non-coding RNA, has been used for one-or two-channel miRNA microarray profiling as one of the first approaches to normalize mRNA gene microarray data (summarized in [START_REF] Hua | Comparison of normalization methods with microRNA microarray[END_REF][START_REF] Pradervand | Impact of normalization on miRNA microarray expression profiling[END_REF]. In these applications, non differentially expressed genes are selected which occur in the same rank order on each chip (rank invariants). These latter, however, could imply truly differentially expressed candidates as invariant if they did not change rank position. Such a case is conceivable for miRNA microarrays as they have features ranging only in the hundreds. Thus, a miRNA may have a large difference in intensity without appreciably altering its rank order [START_REF] Pradervand | Impact of normalization on miRNA microarray expression profiling[END_REF]. Most commercially available miRNA microarrays do not have controls for endogenous RNAs that have been shown to be robustly invariant between various different tissue samples or conditions [START_REF] Rao | A comparison of normalization techniques for microRNA microarray data[END_REF]). To date, there is no consensus on the existence and reliability of reference gene miRNAs. The selection of reference genes to normalize miRNA levels depends on bioinformatic analysis of the respective data (as shown for mRNA [START_REF] Vandesompele | Accurate normalization of real-time quantitative RT-PCR data by geometric averaging of multiple internal control genes[END_REF][START_REF] Andersen | Normalization of real-time quantitative reverse transcription-PCR data: a model-based variance estimation approach to identify genes suited for normalization, applied to bladder and colon cancer data sets[END_REF]) and is otherwise still rather empirical due to the lack of robust reference miRNAs [START_REF] Benes | Expression profiling of microRNA using real-time quantitative PCR, how to use it and what is available[END_REF], although a universal reference miRNA reagent set has been proposed [START_REF] Sarkar | Quality assessment and data analysis for microRNA expression arrays[END_REF].

Moreover, inter-platform and inter-laboratory meta-analyses identified constitutively expressed miRNAs across tissues [START_REF] Bargaje | Consensus miRNA expression profiles derived from interplatform normalization of microarray data[END_REF]. A mean of expression levels of a set of 16 microRNAs showing minimum variability was reasonably successful as a normalization factor for comparing datasets generated by the same platforms. However, normalization using constitutive microRNAs was ineffective when comparing bead-based and microarraybased datasets. In these cases quantile and Z-score normalization were both successful in transforming the data sets generating comparable means and scale [START_REF] Bargaje | Consensus miRNA expression profiles derived from interplatform normalization of microarray data[END_REF].

By applying scaling methods like Z-score [START_REF] Bargaje | Consensus miRNA expression profiles derived from interplatform normalization of microarray data[END_REF], mean, median (reviewed in [START_REF] Hua | Comparison of normalization methods with microRNA microarray[END_REF], or 75 th percentile [START_REF] Lopez-Romero | Processing of Agilent microRNA array data[END_REF], one assumes that different sets of intensities differ by a constant global factor. These are only correct for 'global multiplicative effects' (reviewed in [START_REF] Steinhoff | Normalization and quantification of differential expression in gene expression microarrays[END_REF], since all raw intensity values are multiplied with one common (i.e. global) scaling factor. The Z-score provides a meancentered rank for the expression level in units of standard deviation. Z-scores thus provide an index of the expression level of the miRNA with respect to the cellular pool of miRNA.

Unlike other normalization methods Z-scores are not influenced by the addition of new datasets allowing flexible cross-platform validation of miRNA microarray profiling experiments [START_REF] Bargaje | Consensus miRNA expression profiles derived from interplatform normalization of microarray data[END_REF].

Recently, [START_REF] Wang | A personalized microRNA microarray normalization method using a logistic regression model[END_REF] suggested the pre-evaluation of the overall miRNA expression pattern by a panel of miRNAs using RT-qPCR assays to build a logistic regression model based on these results. The personalized logistic regression model based on 29 miRNAs efficiently calibrated the variance across arrays and improved miRNA microarray discovery accuracy compared with different scaling methods, LOESS or quantile normalization [START_REF] Wang | A personalized microRNA microarray normalization method using a logistic regression model[END_REF]. However, selection of the miRNAs included in pre-evaluations seems rather empirical. This personalized logistic regression model approach n eeds to be evaluated by further independent studies to estimate robustness of this normalization method.

Normalization techniques for small RNA-seq data

An advantage of RNA-seq is that it can capture transcriptome dynamics without sophisticated normalization of data sets (Wang et al. 2009). This might hold true for direct RNA sequencing approaches [START_REF] Ozsolak | Direct RNA sequencing[END_REF]. At present, however, standard normalization methods for non-direct RNA-seq are not sufficient to remove RNA composition bias because relying on library size [START_REF] Robinson | A scaling normalization method for differential expression analysis of RNA-seq data[END_REF]. Systematic technical bias such as RNA ligase preferences, reverse transcription reaction, and PCR based amplification during library preparation are likely to contribute to bias in RNA-seq experiments [START_REF] Linsen | Limitations and possibilities of small RNA digital gene expression profiling[END_REF].

Small RNA-seq approaches relying on cDNA library-construction are strongly biased towards certain small RNAs [START_REF] Linsen | Limitations and possibilities of small RNA digital gene expression profiling[END_REF]) largely independent of the sequencing platform but strongly determined by the method used for small RNA library preparation. However, a satisfactory correction model has not yet been identified [START_REF] Linsen | Limitations and possibilities of small RNA digital gene expression profiling[END_REF]. As these biases are systematic and highly reproducible [START_REF] Marioni | RNA-seq: an assessment of technical reproducibility and comparison with gene expression arrays[END_REF]), RNA-seq may be suited for determining relative expression differences between samples [START_REF] Linsen | Limitations and possibilities of small RNA digital gene expression profiling[END_REF].

However, technical sample to sample variations may be introduced before and in follow-up steps of library preparation. Nevertheless, several small RNA-seq studies do not report on data normalization at all. Following microarray technology, quantile normalization of small RNA-seq data has been utilized to remove systematic bias between samples [START_REF] Pradervand | Concordance among digital gene expression, microarrays, and qPCR when measuring differential expression of microRNAs[END_REF]) and other normalization strategies established for microarrays could theoretically be applied as well.

At present, scaling to library size is the standard procedure to normalize small RNA-seq experiments. Using this method reads are divided by the total number of small RNA-seq reads aligning to the genome [START_REF] Marques | Loqs and R2D2 act sequentially in the siRNA pathway in Drosophila[END_REF]. Alternatively, the relative frequency of miRNAs is determined by normalizing miRNA reads against the total count of 18 to 22 nucleotide reads or total number of reads that map to known miRNAs, respectively [START_REF] Zhang | A genome-wide characterization of microRNA genes in maize[END_REF][START_REF] Linsen | Limitations and possibilities of small RNA digital gene expression profiling[END_REF][START_REF] Git | Systematic comparison of microarray profiling, real-time PCR, and next-generation sequencing technologies for measuring differential microRNA expression[END_REF]. Normalized data is then reported as reads (or transcripts) per million for each respective library. However, the problem underlying the analysis of RNA-seq data is that while the total number of reads for a library is known, the composition of the RNA population is unknown. Thus, library size scaling might have its limitations for datasets with markedly different RNA composition [START_REF] Robinson | A scaling normalization method for differential expression analysis of RNA-seq data[END_REF][START_REF] Marques | Loqs and R2D2 act sequentially in the siRNA pathway in Drosophila[END_REF].

Only recently, trimmed mean of M-values (TMM) normalization has been suggested to remove RNA composition bias as the number of reads for a gene is dependent not only on the gene's expression level and length, but also on the population of RNA from which it originates [START_REF] Robinson | A scaling normalization method for differential expression analysis of RNA-seq data[END_REF]. RNA population differences like abundance or diversity of different small RNA species lead to a different distribution of available reads per gene and may skrew data. Therefore, TMM equates the overall expression levels of genes between samples by estimation of relative RNA production levels or scale factors, respectively, that can be incorporated into currently used statistical methods for differential expression analysis without modification of the sampling properties of the data itself. Similar to assumptions made in microarray normalization procedures such as LOESS or quantile normalization, TMM assumes that the majority of genes common to both samples, are not differentially expressed. Moreover, simulation studies indicate that the TMM method is robust against deviations to this assumption up to about 30 % of differential expression in one direction [START_REF] Robinson | A scaling normalization method for differential expression analysis of RNA-seq data[END_REF]. It can be expected that this assumption will not be violated for most small RNA-seq applications. Thus, independent utilization and evaluation of TMM normalization can be awaited in the near future.

Conclusions and perspectives

Introducing normalization strategies to raw expression data is crucial for the reduction of false positives or negative data points. In many ways mRNA and miRNA experiments face similar influencing factors introducing bias. However, the nature of miRNA profiling data which mirrors the distinct biogenesis and physicochemical nature of miRNAs can challenge conventional normalization methods originally developed for mRNA expression data. Thus, several normalization methods have been adapted or proposed for miRNA expression profiling analyses. Biological or experimental setups which are accompanied by significant global changes in miRNA amount or composition may not meet certain assumptions on data distribution, e.g. if miRNA biogenesis pathways are affected or very distinct tissues are compared. Thus, nonparametric or assumption free transformation methods and specific scaling approaches emerge as robust, frequently used methods in addition to parametric and linear normalization techniques. The combination of two normalization methods, that in each case handle different aspects of microarray data has been shown to be able to outperform other individual techniques in some cases [START_REF] Risso | A modified LOESS normalization applied to microRNA arrays: a comparative evaluation[END_REF][START_REF] Pradervand | Impact of normalization on miRNA microarray expression profiling[END_REF]. It is unlikely that a set of truly universal reference miRNAs will be identified, but similar to mRNA a subset of promising candidates will further emerge. The importance of validating suitable reference genes in a sample-specific context remains.

When novel miRNA discovery is not of priority, assumption based technologies can still be the method of choice as RT-qPCR and hybridization based microarrays still surpass RNAseq technology with respect to absolute RNA expression quantification. RNA-seq was shown to be strongly biased towards certain small RNAs. In contrary to microarrays, these shortcomings might not be overcome with the use of synthetic spike-in controls until a suitable correction model for sequence specific biases has been developed. Generally, evaluation of normalization methods is most in its infancy for RNA-seq, but has both a great potential and a challenging demand to be further optimized.

In conclusion, there are many distinct ways to normalize miRNA expression profiling datasets ultimately leading to uncovering a layer of post-transcriptional regulatory complexity.

Individual selection of the optimal normalization method, dependent on the characteristics of the dataset, can be strongly recommended. Standard normalization methods may carefully need to be scrutinized in specific biological contexts. It still remains unclear which method uniformly outperforms the others under different experimental setupif there is any single approach fulfilling these demands at all. Evaluation of the goodness of a normalization method remains a challenge on its own. The reduction in the coefficient of variation as well as the concordance with good positive controls or inter-platform as well as inter-technology validations, respectively, measured as consistency of p-values or fold-changes, may serve as evaluation criteria.

Table 1: Basic summary of miRNA profiling by RT-qPCR, microarray and small RNAseq, including corresponding normalization methods. Each profiling approach has specific advantages and disadvantages which should be weighted depending on the research context. Aspects of consideration range from economic and time capacity issues to sample availability, required sensitivity and dynamic range, absolute or relative quantification, as well as the biological hypothesis to be tested. RT-qPCR has superior sensitivity [START_REF] Chen | Real-time quantification of microRNAs by stem-loop RT-PCR[END_REF] and requires low time expenditure. Microarray-based techniques have the advantage of being relatively cost-effective, relatively quick from RNA labeling to data generation and simple to use [START_REF] Pradervand | Concordance among digital gene expression, microarrays, and qPCR when measuring differential expression of microRNAs[END_REF]. Ultra high throughput DNA sequencing allows for the de novo detection and relative quantification of miRNAs, but requires a considerable amount of time for data generation and data analysis. The dynamic range of sequencing depends on the sequencing depth.

  are widely preferred transformation based methods which use local regression via locally weighted scatter plot smooth. As outlier values can strongly influence the local regression curve it is advisable to introduce weights that penalize outliers. Local regression via LOESS uses a quadratic polynomial weighted regression function with Tukey's biweight function (reviewed in Steinhoff and Vingron 2006) of the log ratios Cy3/Cy5 on overall spot intensity Cy3*Cy5 (the LOESS smoother for the so called MA-plots) (Risso et al. 2009). Hua et al. (2008) demonstrated that for two-channel technology print-tip LOESS performed most consistent of all the 15 normalization methods which they compared illustrating that miRNA microarrays manufactured by print technology have, in addition, systematic spatial bias with respect to each block. Print-tip LOESS normalizes each M value by subtracting the corresponding value on the tip-group LOESS curve from the raw data[START_REF] Hua | Comparison of normalization methods with microRNA microarray[END_REF]).

Table 1 microRNA RT-qP CR microRNA microarray small RNA-seq

 1

	Principle	PCR amplific ation	Hybridization	Sequencing
	Throughput	Medium to high	High	Ultra high
	Costs	economic	economic	comparatively high
	Required amount	10 ng -700 ng	100 ng -10, 000 ng	250 ng -10, 000 ng
	of RNA
	Data generation	1 day	up to more than	up to more than
	Limit of detection Dynamic range	10 -22 mol 10 6	2 days 10 -15 -10 -18 mol 10 3 -10 4	1 week 10 -15 mol 10 4 -10 7
	Data information	Assumption based;	Assumption based;	Assumption free, de
		dependent on the	dependent on the	novo identification of
		number and nature	number and nature	transcripts within the
		of targeted	of targeted	small RNA
		transcripts	transcripts	transcriptome
	Data analysis	Low	Moderate	Considerable
		expenditure of time	expenditure of time	expenditure of time
	Memory capacity	Low	Low	High
	requirements
	Preferential field	Relative and	Relative and	De novo identification
	of application	absolute	absolute	of small RNAs,
		quantification;	quantification of	simultaneous relative
		validation of other	miRNA regulation,	quantification of
		miRNA profiling	miRNA biomarker	different small RNA
		approaches	identification, routine	species, holistic
			application and	picture of the small
			higher throughput	RNA transcriptome
			with respect to
			sample number
			compared to small
			RNA -seq
	Common	Invariant -bas ed (e.g.	Quantile	Scaling to library or
	normalization	stable reference		sub-library (e.g.
	strategies	small non-coding	LOESS	miRNA ) size
		RNAs)
			Variance stabilization	Quantile
		Plate normalizing
		factor	Invariant -bas ed	Trimmed mean of M-
				values
		Global mean expression	Scaling (e.g. Z-score, mean, median, 75 th
			percentile)
			Personalized logistic
			regression model

Table 2 : MicroRNAs, small nuclear and small nucleolar RNAs suggested as stable reference genes for normalization of microRNA expression analyses

 2 . Reference RNAs identified by studies comparing different human or mouse tissues or cell lines, respectively, are listed. However, careful selection and analysis of the suitability of the respective microRNAs, small nuclear or small nucleolar RNAs as stable reference genes can strongly be recommended for each individual experimental setup.

*Applied Biosystems: Endogenous controls for real-time quantification of miRNA using TaqMan microRNA assays. (ed. Application Note).