Nadia Pisanti
email: pisanti@di.unipi.it

Maxime Crochemore
email: maxime.crochemore@univ-mlv.fr

Roberto Grossi
email: grossi@di.unipi.it

Marie-France Sagot

Bases of Motifs for Generating Repeated Patterns with Wild Cards *

Motif inference represents one of the most important areas of research in computational biology, and one of its oldest ones. Despite this, the problem remains very much open in the sense that no existing definition is fully satisfying, either in formal terms, or in relation to the biological questions that involve finding such motifs. Two main types of motifs have been considered in the literature: matrices (of letter frequency per position in the motif) and patterns. There is no conclusive evidence in favour of either, and recent work has attempted to integrate the two types into a single model. In this paper, we address the formal issue in relation to motifs as patterns. This is essential to get at a better understanding of motifs in general. In particular, we consider a promising idea that was recently proposed, which attempted to avoid the combinatorial explosion in the number of motifs by means of a generator set for the motifs. Instead of exhibiting a complete list of motifs satisfying some input constraints, what is produced is a basis of such motifs from which all the other ones can be generated. We study the computational cost of determining such a basis of repeated motifs with wild cards in a sequence. We give new upper and lower bounds on such a cost, introducing a notion of basis that is provably contained in (and thus smaller) than previously defined ones. Our basis can be computed in less time and space, and is still able to generate the same set of motifs. We also prove that the number of motifs in all bases defined so far grows exponentially with the quorum, that is, with the minimal number of times a motif must appear in a sequence, something unnoticed in previous work. We show that there is no hope to efficiently compute such bases unless the quorum is fixed.

Introduction

Identifying motifs in biological sequences is one of the oldest fields in computational biology. Yet it remains also very much an open problem in the sense that no currently existing definition of a "motif" is fully satisfying for the purposes of accurately and sensitively identifying the biological features that such motifs are supposed to represent. Among the most difficult to model are binding sites, as they are often quite degenerate. Indeed, variability may be considered part of their function. Such variability translates itself into changes in the motif, mostly substitutions, that do not affect the biological function. Two main schools of thought on how to define motifs in biology have co-existed for years, each valid in its own way. The first works with a statistical representation of motifs, usually given in the form of what is called in the literature a PSSM ("Position Specific Scoring Matrix" [START_REF] Gribskov | Profile analysis: detection of distantly related proteins[END_REF][START_REF] Hertz | Escherichia coli promoter sequences: Analysis and prediction[END_REF][START_REF] Lawrence | An expectation maximization (EM) algorithm for the identification and characterization of common sites in unaligned biopolymer sequences[END_REF][START_REF] Lawrence | Detecting subtle sequence signals: a Gibbs sampling strategy for multiple alignment[END_REF] or a profile which is one type of PSSM). Interesting PSSMs are those that have a high information value (measured, for instance, by the relative entropy of the corresponding matrix). The second school defines a motif as a consensus [START_REF] Brazma | Approaches to the automatic discovery of patterns in biosequences[END_REF][START_REF] Vanet | Promoter sequences and algorithmical methods for identifying them[END_REF]. A motif is therefore a pattern that appears repeatedly, in general approximately, that is, up to a certain number of differences (most often substitutions only) in a sequence or set of sequences of interest.

It is generally accepted that PSSMs are more appropriate for modelling an already known (in the sense of well-characterized) biological feature for the purpose of then identifying other occurrences of the feature, even though the false positive rate of this further identification remains very high. Identifying the PSSM itself ab initio is still, however, a difficult problem, particularly for large data sets or when the amount of noise may be high. The methods used are also no guarantee heuristics, leaving an uncertainty as to whether motifs that are statistically as meaningful as those reported have not been missed.

On the other hand, formulating the problem of identifying approximate motifs as patterns enables one to address the motif identification problem in an exhaustive fashion, even though the algorithmic complexity of the problem remains relatively high, and the model may appear more limited than PSSMs. Because of the lower algorithmic complexity of identifying repeated patterns, the model may however be made more complex and biologically pertinent in other ways. One could think of introducing motifs composed of various different submotifs separated by variable-length distances that may then also be found in a relatively efficient way [START_REF] Marsan | Algorithms for extracting structured motifs using a suffix tree with an application to promoter and regulatory site consensus identification[END_REF]. Motifs presenting such a high level of combinatorial complexity are indeed frequent, particularly in eukaryotes. Exhaustively seeking for approximately repeated patterns may however have the drawback of producing many "solutions", that is, many motifs. In fact, the number of motifs identified with this model may be so high (e.g., exponential in the size of the input) that it is as impossible to manage as the initial input sequence(s) even though they provide a first way of structuring such input. Yet it appeared clear also to any computational biologist working with motifs as patterns that there was further structure to be extracted from the set of motifs found, even when such a set is huge. Furthermore, such a structure could reflect some additional biological information, thus providing additional motivation for inferring it. Doing this is generally addressed by means of clustering, or even by attempting to bring together the two types of motif models (PSSMs and patterns). Indeed, recently researchers have been using pattern detection as a first filter-flavoured step towards inferring PSSMs from biological sequences [START_REF] Eskin | From profiles to patterns and back again: A branch and bound algorithm for finding near optimal motif profiles[END_REF]. This seems very promising although much work remains to be done to precisely determine the relation between the two types of models, and to fully explore the biological implications this may have.

Again, each of the two above approaches is valid, but the question remained open whether or not the inner structure of a set of motifs could be expressed in a manner that would be more satisfying from both the mathematical and the biological points of view. Then, in 2000, a paper by Parida et al. [START_REF] Parida | Pattern Discovery on Character Sets and Real-valued Data: Linear Bound on Irredundant Motifs and Efficient Polynomial Time Algorithm[END_REF] seemed to present a way of extracting such an inner structure in a very elegant and powerful way for a particular type of motif. The power of their proposal resided in the fact that the above mentioned structure corresponded to a well-known and precisely defined mathematical object and, moreover, guaranteed that no solution would be lost. Exhaustiveness in relation to the chosen type of motif is also preserved, thus enabling a biologist to draw some conclusions even in the face of negative answers (i.e., when no motifs, or no a priori "expected" motifs are found in a given input), something which PSSM-detecting methods do not allow. The structure is that of a basis of motifs. Informally speaking, it is a subset of all the motifs satisfying some input parameters (related, for instance, to which differences between a pattern and its occurrences are allowed) from which it is possible to recover all the other motifs, in the sense that all motifs not in the basis are a combination of some (in general a few only) motifs in the basis. Such a combination is modelled by simple rules to systematically generate the other motifs with an output sensitive cost [START_REF] Parida | An output-sensitive flexible pattern discovery algorithm[END_REF]. A basis would therefore provide also a way of characterizing the input, which then might be used to compare different inputs without resorting to the traditional alignment methods with all the pitfalls they present. The idea of a basis would fulfill such expectations if its size could be proven to be small enough. The argument [START_REF] Parida | Pattern Discovery on Character Sets and Real-valued Data: Linear Bound on Irredundant Motifs and Efficient Polynomial Time Algorithm[END_REF] seemed to be that, for the type of motifs considered, a compact enough basis could always be found.

The motifs considered in [START_REF] Parida | Pattern Discovery on Character Sets and Real-valued Data: Linear Bound on Irredundant Motifs and Efficient Polynomial Time Algorithm[END_REF] were patterns with wild card symbols occurring in a given sequence s of n symbols drawn over an alphabet Σ. A wild card symbol is a special symbol '•' matching any other element1 of Σ. For example, the pattern T•G matches both TTG and TGG inside s = TTGG. Parida et al. focused on patterns which appear at least q times in s for an input parameter q ≥ 2, called the quorum. This may, at first sight, seem an even more restrictive type of motif than patterns in general. It however has the merit of capturing one aspect of biological features that current PSSMs in general ignore, or address only in an indirect way. This aspect often concerns isolated positions inside a motif that are not part of the biological feature being captured. This is the case for instance with some binding sites, particularly at the protein level. Studying patterns with wild cards has a further very important motivation in biology, even when no differences (such as substitutions) are allowed. Indeed, motifs such as these or closely related ones can be used as seeds for finding long repeats and for aligning, pairwise or multiple-wise, a set of sequences or even whole genomes [START_REF] Miller | Comparison of genomic DNA sequences: solved and unsolved problems[END_REF][START_REF] Pollard | Benchmarking tools for the alignment of functional noncoding dna[END_REF].

The basis introduced by Parida et al. had interesting features but presented some unsatisfying properties. In particular, as we show in this paper, there is an infinite family of strings for which the authors' basis contains Ω(n 2 ) motifs for q = 2. This contradicts the upper bound of 3n for any q ≥ 2 given in [START_REF] Parida | Pattern Discovery on Character Sets and Real-valued Data: Linear Bound on Irredundant Motifs and Efficient Polynomial Time Algorithm[END_REF]. As a result, the algorithm taking O(n 3 log n) time, mentioned in [START_REF] Parida | Pattern Discovery on Character Sets and Real-valued Data: Linear Bound on Irredundant Motifs and Efficient Polynomial Time Algorithm[END_REF],, for finding the basis of motifs does not hold since it relies on the upper bound of 3n, thus leaving open the problem of efficiently discovering a basis. A refinement of the definition of basis and an incremental construction in O(n 3 ) time has recently been described by Apostolico and Parida [START_REF] Apostolico | Incremental paradigms of motif discovery[END_REF]. A comparative survey of several notions of bases can be found in [START_REF] Pisanti | NATO volume on String Algorithmics, chapter A Comparative Study of Bases for Motif Inference[END_REF].

Closely following previous work, here we introduce a new definition of basis. The condition for the new basis is stronger than that of [START_REF] Parida | Pattern Discovery on Character Sets and Real-valued Data: Linear Bound on Irredundant Motifs and Efficient Polynomial Time Algorithm[END_REF] and hence our basis is included in that of [START_REF] Parida | Pattern Discovery on Character Sets and Real-valued Data: Linear Bound on Irredundant Motifs and Efficient Polynomial Time Algorithm[END_REF] (and is thus smaller) while both are able to generate the same set of motifs with mechanical rules. Our basis is moreover symmetric: given a string s, the motifs in the basis for the its reverse s are the reversals of the motifs in the basis for s. Moreover, the number of motifs in our basis can provably be upper bounded in the worst case by n -1 for q = 2 and occur in s a total of 2n times at most. However, we reveal an exponential dependency on q for the number of motifs in all bases defined so far (i.e. including our basis, Parida's and Pelfrene et al.'s [START_REF] Pelfrêne | Extracting approximate patterns[END_REF]), something unnoticed in previous work. Consequently, no polynomial-time algorithm can exist for finding one of these bases with arbitrary values of q ≥ 2.

Notation and Terminology

We consider strings that are finite sequences of letters drawn from an alphabet Σ, whose elements are also called solid characters. We introduce an additional symbol (denoted by • and called wild card ) that does not belong to Σ and matches any letter; a wild card clearly matches itself. The length of a string t, denoted by |t|, is the number of letters and wild cards in t, and t[i] indicates the letter or wild card at position i in t for 0

≤ i ≤ |t| -1 (hence, t = t[0]t[1] • • • t[|t| -1] also noted t[0 . . |t| -1]).
Definition 1 (pattern) Given the alphabet Σ, a pattern is a string in Σ ∪ Σ(Σ ∪ {•}) * Σ (that is, it starts and ends with a solid character).

The patterns are related by the following specificity relation .

Definition 2 ( ) For individual characters σ 1 , σ 2 ∈ Σ ∪ {•}, we have σ 1 σ 2 if σ 1 = • or σ 1 = σ 2 .
Relation extends to strings in (Σ ∪ {•}) * under the convention that each string t is implicitly surrounded by wild cards, namely, letter t[j] is • when j ≥ |t|. Hence, v is more specific than u (written u v) if u[j] v[j] for any integer j.

We can now formally define the occurrences of patterns x in s and their lists. Definition 3 (occurrence, L) We say that u occurs at position ℓ in v if u[j] v[j + ℓ], for 0 ≤ j ≤ |u|-1 (equivalently, we say that u matches v[ℓ . . ℓ+|u|-1]). For the input string s ∈ Σ * with n = |s|, we consider the location list L x ⊆ {0 . . n -1} as the set of all the positions on s at which x occurs.

When a pattern u occurs in another pattern (or into a string) v, we also say that v contains u. For example, the location list of x = T•G in s = TTGG is L x = {0, 1}, hence s contains x. Definition 4 (motif ) Given a parameter q ≥ 2, called quorum, we say that pattern x is a motif in s when |L x | ≥ q.

Given any location list L x and any integer d, we adopt the notation

L x + d = {ℓ + d | ℓ ∈ L x }
for indicating the occurrences in L x "displaced" by the offset d.

Definition 5 (maximality) A motif x is maximal if for any other motif y that contains x, we have no integer d such that L y = L x + d.

In other words, making a maximal motif x more specific (thus obtaining y) reduces the number of its occurrences in s. Definition 5 is equivalent to that meant in [START_REF] Parida | Pattern Discovery on Character Sets and Real-valued Data: Linear Bound on Irredundant Motifs and Efficient Polynomial Time Algorithm[END_REF] stating that x is maximal if there exist no other motif y and no integer d ≥ 0 verifying L x = L y + d, such that x[j] y[j + d] for 0 ≤ j ≤ |x| -1 (that is, x occurs in y at position d in our terminology). 2 Actually, the definition literally reported in [START_REF] Parida | Pattern Discovery on Character Sets and Real-valued Data: Linear Bound on Irredundant Motifs and Efficient Polynomial Time Algorithm[END_REF] is "Definition 4 (Maximal Motif). Let p1, p2, . . . , p k be the motifs in a sequence s. Let pi[j] be '.', if j > |pi|. A motif pi is maximal if and only if there exists no p l , l = i and no integer 0 ≤ δ such that Lp i + δ = Lp l and p l [δ + j] pi[j] hold for 1 ≤ j ≤ |pi|." (the symbols in pi and p l are indexed starting from 1 onwards). The corresponding example in the paper illustrates the definition for s = ABCDABCD, stating that pi = ABCD is maximal while p l = ABC is not. However, pi does not match the definition because of the existence of its prefix p l (setting δ = 0); hence we suspect a minor typo in the definition, for which the definition should read as "... such that Lp i = Lp l + δ and pi[j] p l [δ + j].". Definition 6 (irredundant motif ) A maximal motif x is irredundant if, for any maximal motifs y 1 , y 2 , . . . , y k such that L x = ∪ k i=1 L y i , motif x must be one of the y i 's. Conversely, if all the y i 's are different from x, pattern x is said to be covered by motifs y 1 , y 2 , . . . , y k .

The basis of irredundant motifs for string s is the set of all irredundant motifs in s. The definition is given with respect to the set of maximal motifs of the input string which is unique; indeed, such basis is unique and it can be used as a generator for all maximal motifs in s as proved in [START_REF] Parida | Pattern Discovery on Character Sets and Real-valued Data: Linear Bound on Irredundant Motifs and Efficient Polynomial Time Algorithm[END_REF]. The size of the basis is the number of irredundant motifs contained in it. We illustrate the notions given so far by employing the example string s = FABCXFADCYZEADCEADC. For this string and q = 2 the location list of motif

x 1 = A•C is L x 1 = {1, 6, 12, 16}, and that of motif x 2 = FA•C is L x 2 = {0, 5}.
They are both maximal because they lose at least one of their occurrences when extended with solid characters at one side (possibly with wild cards inbetween), or when their wild cards are replaced by solid characters. However, motif x 3 = DC having list L x 3 = {7, 13, 17} is not maximal. It occurs in x 4 = ADC, where L x 4 = {6, 12, 16}, and its occurrences can be obtained from those of x 4 by a displacement of d = 1 positions. The basis of the irredundant motifs for s is made up of

x 1 = A•C, x 2 = FA•C, x 4 = ADC, and x 5 = EADC.
The location list of each of them cannot be obtained from the union of any of the other location lists.

3 Irredundant Motifs: The Basis and its Size for Quorum q = 2

In this section, we show the existence of an infinite family of strings s k (k ≥ 5) for which there are Ω(n 2 ) irredundant motifs in the basis for quorum q = 2, where n = |s k |. In this way, we disprove the claimed upper bound of 3n [START_REF] Parida | Pattern Discovery on Character Sets and Real-valued Data: Linear Bound on Irredundant Motifs and Efficient Polynomial Time Algorithm[END_REF] mentioned in Section 1. Each string s k will be constructed from a shorter string t k , which we now define. For each k, t k = A k TA k , where A k denotes the letter A repeated k times (our argument works in general for z k wz k , where z and w are strings of equal length not sharing any common character). String t k contains an exponential number of maximal motifs, including those having the form A{A, •} k-2 A with exactly two wild cards. To see why, each such motif x occurs four times in t k : specifically, two occurrences of x match the first and the last k letters in t k while each distinct wild card in x matching the letter T in t k contributes to one of the two remaining occurrences. Extending x or replacing a wild card with a solid character reduces the number of these occurrences, so x is maximal. The idea of our proof is to obtain strings s k by prefixing t k with O(|t k |) symbols so that these motifs x become irredundant in s k . Since there are Ω(k 2 ) of them, and

n = |s k | = Θ(|t k |) = Θ(k), this leads to the claimed result.
In order to define the strings s k on the alphabet Σ = {A, T, u, v, w, x, y, z, a 1 , a 2 , . . . , a k-2 }, we introduce some notation. Let u denote the reversal of u, and let ev k , od k , u k , v k be the strings thus defined if k is even :

ev k = a 2 a 4 • • • a k-2 , od k = a 1 a 3 • • • a k-3 , u k = ev k u ev k vw ev k , v k = od k xy od k z od k , if k is odd : ev k = a 2 a 4 • • • a k-3 , od k = a 1 a 3 • • • a k-2 , u k = ev k uv ev k wx ev k , v k = od k y od k z od k .
The strings s k are then defined by Fact 1 The length of u k v k is 3k, and that of s k is n = 5k + 1.

s k = u k v k t k for k ≥ 5. Figure 1 shows them for k = 7. AA•AAAA AA•AAAA AA•AAAA s 7 = 24uv42wx24135y531z135AAAAAAATAAAAAAA 4•••••••••••••••••••AAAA•AA 4•••••••••••••••••••AAAA•AA 4•••••••••••••••••••AAAA•AA
Proof : Whatever the parity of k, the string u k v k contains the six letters u, v, w, x, y, z, two occurrences each of ev k and od k , and one occurrence each of ev k and od k . Since od k and ev k together contain one occurrence of each letter a 1 , a 2 , . . . , a k-2 , we have

|od k | + |ev k | = k -2. Moreover, | ev k | = |ev k | and | od k | = |od k |, so that |u k v k | = 6 + 3(k -2) = 3k
. This proves the first statement. For the second statement, the total length of s k follows by observing that

|t k | = 2k + 1, and so n = |s k | = 3k + 2k + 1 = 5k + 1. ⊲⊳ Proposition 1 For 1 ≤ p ≤ k -2, no motif of the form A p • A k-p-1 can be maximal in s k . Also motif A k cannot be maximal in s k .
Proof : Let w be an arbitrary motif of the form

A p • A k-p-1 , with 1 ≤ p ≤ k -2. Its location list is L w = {0, k-p, k+1}+|u k v k | = {3k, 4k-p, 4k+1} since |u k v k | = 3k
by Fact 1 and w matches the two substrings A k of s k as well as A p TA k-p-1 . The occurrences are shown in Figure 1 for k = 7 and p = 2. No other occurrences are possible. Let us consider the position, say i, of the leftmost appearance of letter a p in s k (recall that there are three positions on s k at which letter a p occurs; we have i = 0 in our example of Figure 1 with p = 2). We claim that motif y = a p • 3k-i-1 w satisfies L y = L w -(3ki). Since w appears in y, it follows that w cannot be maximal in s k by Definition 5 (setting d = -3k + i). To see why L w = L y + (3ki), it suffices to prove that the distance in s k between the positions of the two leftmost letters a p is kp while that of the leftmost and the rightmost a p is k + 1. The verification is a bit tedious because four cases arise according to the fact that each of k and p can be even or odd. Since the cases are analogous, we detail only two of them, namely, when both k and p are even, and when k is even and p is odd. In the first case, the three occurrences of a p are all in u k . Moreover, the distance between the two leftmost letters a p is the length of the substring

a p a p+2 • • • a k-2 ua k-2 a k-4 • • • a p+2 , that is, 2|a p+2 • • • a k-2 | + 2 = 2(k -2 -p)/2 + 2 = k -p.
The distance between the leftmost and rightmost a p is the length of

a p a p+2 • • • a k-2 u ev k vwa 2 a 4 • • • a p-2 . This is also the length of u ev k vwa 2 a 4 • • • a p-2 a p a p+2 • • • a k-2 = u ev k vwev k , that is, 2(k -2)/2 + 3 = k + 1
as expected. In the second case where k is even and p is odd, the occurrences of a p are all in v k . Analogously to the first case, the distance between the two leftmost letters a p is the length of

a p a p+2 • • • a k-3 xya k-3 • • • a p+2 , that is, 2|a p+2 • • • a k-3 | + 3 = 2(k -3 -p)/2 + 3 = k -p.
The distance between the leftmost and the rightmost a p is the length of the string

a p a p+2 • • • a k-3 xy od k za 1 a 3 • • • a p-2
, which equals k + 1, the length of xy od k zod k . The analogous verification of the other two cases yields the fact that w cannot be maximal.

The second part of the lemma for motif A k proceeds along the same lines, except that we choose y = a p • 3k-i-1 A k with i as before (note that y is not required to be maximal and that the motifs in the statement are maximal in t k ). ⊲⊳ Proposition 2 Each motif of the form A{A, •} k-2 A with exactly two •'s is irredundant in s k .

Proof : Let x be an arbitrary motif of the form A{A,

•} k-2 A with two •'s, namely, x = A p 1 • A p 2 -p 1 -1 • A k-p 2 -1 for 1 ≤ p 1 < p 2 ≤ k-2.
To prove that x is an irredundant motif, we first show that x is maximal.

Its location list is L x = {0, k -p 2 , k -p 1 , k + 1} + 3k since |u k v k | = 3k
L x = ∪ h i=1 L y i .
We claim that at least one y i is of the form A{A, •} k-2 A. Indeed, there must exist a location list L y i containing position 4k + 1 since that position belongs to L x . This implies that y i occurs in the suffix A k of s k . It cannot be that |y i | < k since y i would occur also in some position j > 4k + 1 whereas j ∈ L x , so it is impossible. Consequently, y i is of length k and matches A k , thus being of the form A{A, •} k-2 A. We observe that y i cannot contain zero or one •'s, as it would not be maximal by Proposition 1. Also, y i cannot contain three or more

Terminology and properties

In this section we introduce a natural notion of a basis for generating all maximal motifs occurring in a string s of length n.

Definition 7 (tiling motif ) A maximal motif x is tiling if, for any maximal motifs y 1 , y 2 , . . . , y k and for any integers

d 1 , d 2 , . . . , d k such that L x = ∪ k i=1 (L y i + d i ), motif
x must be one of the y i 's. Conversely, if all the y i 's are different from x, pattern x is said to be tiled by motifs y 1 , y 2 , . . . , y k .

The notion of tiling is in general more selective than that of irredundancy. Continuing our example string s = FABCXFADCYZEADCEADC, we have seen in Section 2 that motif x 1 = A•C is irredundant for s. Now, x 1 is tiled by x 2 = FA•C and x 4 = ADC according to Definition 7 since its location list, L x 1 = {1, 6, 12, 16}, can be obtained from the union of L x 2 = {0, 5} and L x 4 = {6, 12, 16} with respective displacements d 2 = 1 and d 4 = 0.

Remark 1 A fairly direct consequence of Definition 7 is that if x is tiled by y 1 , y 2 , . . . , y k with associated displacements d 1 , d 2 , . . . , d k , then x occurs at position d i in y i for 1 ≤ i ≤ k. As a consequence, we have that d i ≥ 0 in Definition 7. Note also that the y i 's in Definition 7 are not necessarily distinct and that k > 1 for tiled motifs. (It follows from the fact that L x = L y 1 + d 1 with x = y 1 would contradict the maximality of both x and y 1 .) As a result, a maximal motif x occurring exactly q times in s is tiling as it cannot be tiled by any other motifs because such motifs would occur less than q times. The basis of tiling motifs is the complete set of all tiling motifs for s, and the size of the basis is the number of these motifs. For example, the basis, let us denote it by B, for FABCXFADCYZEADCEADC contains FA•C, EADC, and ADC as tiling motifs. Although Definition 7 is derived from that of irredundant motifs given in Definition 6, the difference is much more substantial than it may appear. The basis of tiling motifs relies on the fact that tiling motifs are considered as invariant by displacement as for maximality. Consequently, our definition of basis is symmetric, that is, each tiling motif in the basis for the reverse string s is the reverse of a tiling motif in the basis of s. This follows from the symmetry in Definition 7 and from the fact that maximality is also symmetric in Definition 5. It is a sine qua non condition for having a notion of basis invariant by the left-to-right or right-to-left order of the symbols in s (like the entropy of s), while this property does not hold for the irredundant motifs.

The basis of tiling motifs has further interesting properties for quorum q = 2, illustrated in Sections 4.2-4.4. In Section 4.2, we show that our basis is linear (that is, its size is at most n -1). In Section 4.3, we show that the total size of the location lists for the tiling motifs is less than 2n, describing how to find them in O(n 2 log n log |Σ|) time. In Section 4.4, we discuss some applications such as generating all maximal motifs with the basis and finding motifs with a constraint on the number of undefined symbols.

4.2 A linear upper bound for the tiling motifs with quorum q = 2 Given a string s of length n, let B denote its basis of tiling motifs for quorum q = 2. Although the number of maximal motifs may be exponential and the basis of irredundant motifs may be at least quadratic (see Section 3), we show that the size of B is always less than n. For this, introduce an operator ⊕ between the symbols of Σ to define the merges, which are at the heart of the properties of B. Given two letters σ 1 , σ 2 ∈ Σ with σ 1 = σ 2 , the operator satisfies σ 1 ⊕ σ 2 = • and σ 1 ⊕ σ 1 = σ 1 . The operator applies to any pair of strings x, y ∈ Σ * , so that u = x ⊕ y satisfies u[j] = x[j] ⊕ y[j] for all integers j. Definition 8 (Merge) For 1 ≤ k ≤ n -1, let s k be the (infinite) string whose character at position i is s k

[i] = s[i] ⊕ s[i + k].
If s k contains at least one solid character, Merge k denotes the motif obtained by removing all the leading and trailing •s in s k (that is, those appearing before the leftmost solid character and after the rightmost solid character). Proof : Motif x = Merge k occurs at positions, say, i and i + k in s. Character s k [i] is solid by Definitions 4 and 8. We use the fact that x at occurs at least twice in s for showing that it is maximal. Suppose it is not maximal. By Definition 5, there exists y = x such that x occurs in y and L y = L x + d for some integer d (in this case d ≤ 0). Since y is more specific than x displaced by d, there must exist at least one position j with 0

≤ j < |y| such that x[j + d] = • and y[j] = σ ∈ Σ. Hence x[j + d] = s[i + (j + d)] ⊕ s[i + k + (j + d)] = •, and so s[(i + d) + j] = s[(i + k + d) + j].
Since y[j] cannot match both of the latter symbols in s, at least one of i + d or i + k + d is not a position of y in s. This contradicts the hypothesis that L y = L x + d whereas both i, i + k ∈ L . ⊲⊳ Lemma 2 For each tiling motif x in the basis B, there is at least one k for which Merge k = x.

Proof : As mentioned in Remark 1, a maximal motif occurring exactly twice in s is tiling. Hence, if |L x | = 2, say L x = {i, j} with j > i, then x = Merge k with k = ji by the maximality of x and that of the merges by Lemma 1. Let us now consider the case where |L x | > 2. For any pair i, j ∈ L x , we denote by u ij the string s[i . . i + |x| -1] ⊕ s[j . . j + |x| -1] obtained by applying the operator ⊕ to the two substrings of s matching x at positions i and j, respectively. We have x u ij since x occurs at positions i and j, and L x = i,j∈Lx L u ij since we are taking all pairs of occurrences of x. Letting k = |j -i| for i, j ∈ L x , we observe that u ij is a substring of Merge k occurring at position, say, δ k in it. Thus, i,j∈Lx

L u ij = k=|j-i| : i,j∈Lx L Merge k + δ k = L x .
By Definition 7, the fact that x is tiling implies that x must be one Merge k , proving the lemma.

⊲⊳

We now state the main property of tiling bases that follows directly from Lemma 2.

Theorem 3 (linearity of the basis) Given a string s of length n and the quorum q = 2, let M be the set of Merge k , for 1 ≤ k ≤ n -1 such that Merge k exists. The basis B of tiling motifs for s satisfies B ⊆ M, and therefore the size of B is at most n -1.

A simple consequence of Theorem 3 implies a tight bound on the number of tiling motifs for periodic strings. If s = w e for a string w repeated e > 1 times, then s has at most |w| tiling motifs.

Corollary 1 The number of tiling motifs for s is at most p, the smallest period of s.

The bound in Corollary 1 is not valid for irredundant motifs. String s = ATATATATA has period p = 2 and only one tiling motif ATATATA, while its irredundant motifs are A, ATA, ATATA and ATATATA.

A simple algorithm for computing tiling motifs with quorum q = 2

We describe how to compute the basis B for string s when q = 2. A brute-force algorithm generating first all maximal motifs of s takes exponential time in the worst case. Theorem 3 plays a crucial role in that we first compute the motifs in M and then discard those being tiled. Since B ⊆ M, what remains is exactly B. To appreciate this approach, it is worth noting that we are left with the problem of selecting B from n -1 maximal motifs in M at most, rather than selecting B among all the maximal motifs in s, which may be exponential in number. Our simple algorithm takes O(n 2 log n log |Σ|) time and is faster than previous (and more complicated) methods discussed in Section 1.

Step 1. Compute the multiset M ′ of merges. Letting s k [i] be the leftmost solid character of string s k in Definition 8, we define occ x = {i, i + k} to be the positions of the two occurrences of x whose superposition generates x = Merge k . For k = 1, 2, . . . , n -1, we compute string s k in O(nk) time. If s k contains some solid characters, we compute x = Merge k and occ x in the same time complexity. As a result, we compute the multiset M ′ of merges in O(n 2 ) time. Each merge x in M ′ is identified by a triplet i, i + k, |x| , from which we can recover the jth symbol of x in constant time by simple arithmetic operations and comparisons.

Step 2. Transform the multiset M ′ into the set M of merges. there can be two or more merges in M ′ that are identical and correspond to the same merge in M, we put together all identical merges in M ′ by radix sorting them. The total cost of this step is dominated by radix sorting, giving O(n 2 ) time. As a byproduct, we produce the temporary location list

T x = x ′ =x : x ′ ∈M ′ occ x ′ for each distinct x ∈ M thus obtained. Lemma 3 Each motif x ∈ B satisfies T x = L x .
Proof : For a fixed x ∈ B, the fact that x is equal to at least one merge by Lemma 2 implies that T x is well defined, with |T x | ≥ 2. Since T x ⊆ L x , let us assume by contradiction that L x -T x = ∅. For each pair i ∈ L x -T x and j ∈ T x , let m ij = Merge |j-i| , which is maximal by Lemma 1. Note that each m ij = x by our assumption as otherwise i would belong to T x ; however, x must occur in m ij , say, at position δ ij in m ij . Consequently, i∈Lx-Tx,j∈Tx (L m ij + δ ij ) = L x since any occurrence of x is either i ∈ L x -T x or j ∈ T x . At this point, we apply Definition 7 to the tiling motif x, obtaining the contradiction that x must be equal to one m ij . ⊲⊳

Notice that the conclusion of Lemma 3 does not necessarily hold for the motifs in M -B. For the previous example string FADABCXFADCYZEADCEADCFADC, one such motif is x = ADC with L x = {8, 14, 18, 22} while T x = {8, 18}.

Step 3. Select M * ⊆ M, where M * = {x ∈ M : T x = L x }. In order to build M * , we employ the Fischer-Paterson algorithm based on convolution [START_REF] Fischer | String matching and other products[END_REF] for string matching with don't cares to compute the whole list of occurrences L x for each merge x ∈ M. Its cost is O((|x| + n) log n log |Σ|) time for each merge x. Since |x| < n and there are at most n -1 motifs x ∈ M, we obtain O(n 2 log n log |Σ|) time to construct all lists L x . We can compute M * by discarding the merges x ∈ M such that T x = L x in additional O(n 2 ) time. The property of M * in Lemma 4 is crucial in that x∈M |L x | = Θ(n 2 ) when many lists contain Θ(n) entries. For example, s = A n has n -1 distinct merges, each of the form x = A i for 1 ≤ i ≤ n -1, and so |L x | = ni + 1. This would be a sharp drawback in Step 4 when removing tiled motifs as it may turn into a Θ(n 3 ) algorithm. Using M * instead, we are guaranteed that

x∈M * |L x | = O(n)
; hence, we may still have some tiled motifs in M * , but their total number of occurrences is O(n).

approach can be followed in Step 2 for finding the distinct merges. In this case, the merges are first partially sorted using hashing and exploiting the fact that the input is almost sorted. Insertion sort is then the best choice and works very efficiently in our experiments (at least 50% faster than Quicksort). We do not compute yet the full merges at this stage, but we delay this expensive part to a later stage on a small set of buckets that require explicit representation of the merges. As a result, the average case is almost linear. For example, executing Steps 1 and 2 on chromosome V of C.elegans containing over 21 million bases took around 15 minutes on a machine with 512Mb of RAM running Linux on a 1Ghz AMD Athlon processor. Step 3 is expensive also in practice and the worst case predicted by theory shows up in the experiments. Running this step on sequences much shorter than chromosome V of C.elegans took many hours.

Step 4 is not much of a problem. As a result, an alternative way of selecting M * from M in Step 3 working fast in practice, would improve considerably the overall performance.

Some applications

Checking whether a pattern is a motif. The main property underlying the notion of basis is that it is a generator of all motifs. The generation can be done as follows: first select segments of motifs in the basis that start and end with solid characters, then replace any number of internal solid characters by wild cards. However, since the number of motifs, and even maximal motifs, can be exponential, this is not really meaningful unless this number is small and the time complexity of the algorithm is proportional to the total size of the output. An attempt in this direction is done in [START_REF] Parida | An output-sensitive flexible pattern discovery algorithm[END_REF]. The dual problem concerns testing only one pattern. We show how, given a pattern x, it can be tested whether x is a motif for string s, that is, if pattern x occurs at least q times in s. There are two possible ways of performing such a test, depending on whether we test directly on the string or on the basis. The answer relies on iterative applications of the observation made in Remark 1, according to which any tiled motif must occur in at least one tiling motif. The next two statements deal with the alternative. In both cases we assume that integer k comes from the decomposition of pattern x in the form u 0

• ℓ 0 u 1 • ℓ 1 • • • u k-1 • ℓ k-1 u k ,
where the subwords u i contain no wild cards (u i ∈ Σ * , 0 ≤ i ≤ k) and ℓ j are positive integers, 0 ≤ j ≤ k -1. The next proposition states a well-known fact on matching such a pattern in a text without any wild card that we report here because it is used in the sequel.

Proposition 3

The positions of the occurrences of a pattern x in a string of length n can be computed in time O(kn).

Proof : This is a mere application of matching a pattern with don't cares inside a text without don't cares. Using for instance the Fischer and Paterson's algorithm [START_REF] Fischer | String matching and other products[END_REF] is not necessary. Instead, the positions of the subwords u i are computed by a multiple string-matching algorithm, such as the Aho-Corasick algorithm [START_REF] Aho | Efficient string matching: an aid to bibliographic search[END_REF]. For each position p, a counter associated with position pℓ on s is incremented, where ℓ is the position of u i in x (ℓ is the offset of u i in x). Counters whose value is k + 1 correspond then to occurrences of x in s. It remains to check if x occurs at least q times in s. The running time is governed by the string-matching algorithm, which is O(kn) (equivalent to running k times a linear-time string matching algorithm). ⊲⊳ Proposition 4 Given the basis B of string s, testing if pattern x is a motif or a maximal motif can be done in O(kb) time, where b = y∈B |y|.

Proof : From Remark 1, testing if x is a maximal motif requires only finding if x occurs in an element y of the basis. To do this, we can apply the procedure of the previous proof because wild cards in y should be viewed as extra characters that do not match any letter of Σ. The time complexity of the procedure is thus O(kb). Since a non maximal motif occurs in a maximal motif, the same procedure applies to test if x is a general motif. ⊲⊳

As a consequence of Propositions 3 and 4, we get an upper bound on the time complexity for testing motifs.

Corollary 2 Testing whether or not pattern u 0

• ℓ 0 u 1 • ℓ 1 • • • u k-1 • ℓ k-1 u k is a motif in a string of length n having a basis of total size b can be done in time O(k • min{b, n}).
Remark 2 Inside the procedure described in the proofs of Propositions 3 and 4, it is also possible to use bit-vector pattern matching methods [START_REF] Baeza-Yates | A new approach to text searching[END_REF][START_REF] Myers | A fast bit-vector algorithm for approximate string matching based on dynamic programming[END_REF][START_REF] Wu | Path-matching problems[END_REF] to compute the occurrences of x. This leads to practically efficient solutions running in time proportional to the length of the string n or the total size of the basis b, in the bit-vector model of machine. This is certainly a method of choice for short patterns.

Finding the longest motif with bounded number of wild cards. We address an interesting question concerning the computation of a longest motif occurring repeated in a string. Given an integer g ≥ 0, let LM g (s) be the maximal length of motifs occurring in a string s of length n with quorum q = 2, and containing no more than g wild cards. If g = 0, the value can be computed in O(n log |Σ|) time with the help of the suffix tree of s (see [START_REF] Crochemore | Jewels of Stringology[END_REF] or [START_REF] Gusfield | Algorithms on strings, trees and sequences: computer science and computational biology[END_REF]). For g > 0, we can show that LM g (s) can be computed in O(gn 2 ) time using the suffix tree augmented (in linear time) to accept longest common ancestor (LCA) queries as follows. For each possible pair (i, j) of positions on s for which s[i] = s[j], we compute the longest common prefix of s[i . . n -1] and s[j . . n -1] in constant time through an LCA query on the suffix tree. If ℓ is the length of the prefix, we get the first part s[i . . i + ℓ -1]• of a possible longest motif. The second part is found similarly by considering the pair of positions (i + ℓ + 1, j + ℓ + 1). The process is iterated g times (or less) and provides a longest motif containing at most g wild cards and occurring at positions i and j. Length LM g (s) is obtained by taking the maximum length of motifs for all pairs of positions (i, j). This yields the next result.

Proposition 5 Using the suffix tree, LM g (s) can be computed in O(gn 2 ) time.

What makes interesting the use of the basis of tiling motifs is that computing LM g (s) becomes a mere pattern matching exercise because of the strong properties of the basis. This contrasts with the previous result grounded on the deep algorithmic technique for LCA queries. Proof : Let x be a motif yielding LM g (s) (i.e., x is of length LM g (s)); hence, x occurs at least twice in s. Let y be a maximal motif in which x occurs (we have y = x if x is itself maximal). Let z be a tiling motif in which y occurs (again we may have z = y if y is a tiling motif). The word x then occurs in z that belongs to the basis. Let us say that it matches z[i . . j]. Assume that x is not a tiling motif, that is x = z. Certainly i = 0 or z[i -1] = •, otherwise x would not be the longest with its property. For the same reason, j = |z| -1 or z[j + 1] = •. But indeed, x occurs exactly in z, which means that the wild card symbols do not match any solid symbol. Because otherwise, z[i . . j] would contain less than g don't cares and could be extended by at least one symbol to the left or to the right because x = z, yielding a contradiction with the definition of x. Therefore, either x is a tiling motif or it matches exactly a segment of one of the tiling motifs. Searching for x thus reduces to finding a longest segment of a tiling motif in B that contains no more than g wild cards. The computation can be done in linear time with only two pointers on s, which proves the result. ⊲⊳ By Proposition 6, it is clear that a small basis B leads to an efficient computation once B is given. If we have to build B from scratch, we can observe that no (maximal) motif can give a larger value of LM g (s) if it does not belong to B. With this observation, we have O(n 2 ) running time, which always beats the O(g ×n 2 ) cost of using the suffix tree. In particular, it is interesting to notice that the running time of the algorithm using the basis is independent of the parameter g.

Pseudo-Polynomial Bases for Higher Quorum

We now discuss the general case of quorum q ≥ 2 for finding the basis of a string of length n. Differently from previous work, we show in Section 5.1 that no polynomial-time algorithm can exist for any arbitrary value of q in the worst case, both for the basis of irredundant motifs and for the basis of tiling motifs. The size of these bases provably depends exponentially on suitable values of q ≥ 2, that is, we give a lower bound of n-1 2 -1 q-1 = Ω( 1 2 q n-1 q-1 ). In practice, this size has an exponential growth for increasing values of q up to O(log n), but larger values of q are theoretically possible in the worst case. Fixing q = (n -1)/4 + 1 in our lower bound, we get a size of Ω(2 (n-1)/4 ) motifs in the bases. On the average q = O(log |Σ| n) by extending the argument after Theorem 4, namely, using the fact that on the average the number of simultaneous comparisons to find the first solid character of a merge is O(|Σ| q-1 ), which must be less than n.

We show a further property for the basis of tiling motifs in Section 5.2, giving an upper bound of n-1 q-1 on its size with a simple proof. Since we can find an algorithm taking time proportional to the square of that size, we can conclude that a worst case polynomial-time algorithm for finding the basis of tiling motifs exists if and only if the quorum q satisfies either q = O(1) or q = n -O(1) (the latter condition is hardly meaningful in practice).

A lower bound of

n-1 2 -1 q-1

on the bases

We show the existence of a family of strings for which there are at least n-1 2 -1 q-1 tiling motifs for a quorum q. Since a tiling motif is also irredundant, this gives a lower bound for the irredundant motifs to be combined with that in Section 3 (note that the lower bound in Section 3 still gives Ω(n 2 ) for q ≥ 2). For q > 2, this gives a lower bound of Ω n-1 2 -1 q-1 = Ω( 1 2 q n-1 q-1 ) for the number of both tiling and irredundant motifs.

The strings are this time of the form t k = A k TA k (k ≥ 5), without the left extension used in the bound of Section 3. The proof proceeds by exhibiting k-1 q-1 motifs that are maximal and have each exactly q occurrences, from whence it follows immediately that they are tiling. Indeed Remark 1 for tiling motifs holds for any q ≥ 2. Namely, all maximal motifs that occur exactly q times in a string are tiling. Proposition 7 For 2 ≤ q ≤ k and 1 ≤ p ≤ kq + 1, any motif A p • {A, •} k-p-1 • A p with exactly q wild cards is tiling (and so irredundant) in t k .

Proof : Let x be an arbitrary motif A p • {A, •} k-p-1 • A p with 1 ≤ p ≤ kq + 1 and q wild cards; namely,

x = A p 1 •A p 2 -p 1 -1 • • • • •A p q-1 -p q-2 -1 •A k-p q-1 -1 •A p 1 for 1 ≤ p 1 < p 2 < • • • < p q-1 ≤ k -1 and p = p 1 .
We first have to prove that x is a maximal motif according to Definition 5. Its length is k + 1 + p 1 and its location list is L x = {0, kp q-1 , . . . , kp 2 , kp 1 }. Observe that the number of its occurrences is exactly the number of times the wild card appears in x, which is equal to q. A motif y different from x such that x occurs in y can be obtained by replacing the wild card at position p i with a solid symbol, for 1 ≤ i ≤ q -1, but this eliminates kp i from the location list of y. Also, y can be obtained by extending x to the right by a solid symbol (at any position ≥ |x|), but then position kp 1 is not in L y because the last symbol in that occurrence of y occupies position (k

-p 1 ) + |y| -1 ≥ (k -p 1 ) + |x| = (k -p 1 ) + (k + 1 + p 1 ) > |t k | -1 in t k ,
which is impossible. Analogously, y can be obtained by extending x to the left by a solid symbol (at any position d < 0) but position 0 is no longer in L y . Consequently, for any motif y more specific than x we have L y = L x + d, implying that x is maximal. As previously mentioned, x is tiling because it has exactly q occurrences. ⊲⊳

Theorem 5 String t k has n-1 2 -1 q-1 = Ω( 1 2 q
n-1 q-1 ) tiling (and irredundant) motifs, where n = |t k | and k ≥ 2.

Proof : By Proposition 7, the tiling or irredundant motifs in t k are at least k-1 q-1 , the number of choices of q -1 positions on A k-1 . Since n = 2k + 1, we obtain the statement. ⊲⊳ 5.2 An upper bound of n-1 q-1 tiling motifs

We now prove that n-1 q-1 is an upper bound for the size of a basis of tiling motifs for a string s and quorum q ≥ 2. Let us denote as before such a basis by B. To prove the upper bound we use again the notion of a merge, except that it now involves q strings. The operator ⊕ between the elements of Σ extends to more than two arguments, so that the result is a • if at least two arguments differ. Let k denote now an array of q -1 positive values k 1 , . . . , k q-1 with 1 ≤ k i < k j ≤ n -1 for all 1 ≤ i < j ≤ q -1. Definition 9 Let s k denote the string such that its jth character is s k

[j] = s[j] ⊕ s[j + k 1 ] ⊕ • • • ⊕ s[j + k q-1
] for all integers j. Merge k is the pattern obtained by removing all the leading and trailing •s in s k (that is, appearing before the leftmost solid character and after the rightmost solid character).

Lemmas 5 and 6 reported below extend Lemmas 1 and 2 for q > 2.

Lemma 5 If Merge k exists for quorum q, then it must be a maximal motif.

Proof : Let x = Merge k denote the (nonempty) pattern, and let s k [i] be its first character, which is solid by Definition 9. Since x occurs at least q times in s, at positions i, i + k 1 , . . . , i + k q-1 , then x is a motif for quorum q. We show that x is maximal. Suppose it is not maximal. By Definition 5, there exists y = x s.t. x occurs in y and L y = L x +d for some integer d. This implies there exists at least one position j with 0 ≤ j < |y| such that y[j] = σ ∈ Σ and x[j

+ d] = •. Since x[j + d] = s[i + j + d] ⊕ s[i + j + k 1 + d] ⊕ • • • ⊕ s[i + j + k q-1 + d]
, then at least one among i + d, i + k 1 + d, . . . , i + k q-1 + d is not an occurrence of y, contradicting the hypothesis that L y = L x + d (since i, i + k 1 , . . . , i + k q-1 ∈ L x ). ⊲⊳ Lemma 6 For each tiling motif x in the basis B with quorum q, there is at least one k for which Merge k = x.

Proof : If |L x | = q and L x = {i 1 , . . . , i q } with i 1 < • • • < i q , then x = Merge k where k is the array of values i 2 -i 1 , i 3 -i 1 , . . . , i q -i 1 . Let us now consider the case where |L x | > q. Given any q-tuple i 1 , . . . , i q ∈ L x , let u k denote s[i 1 . . i 1 + |x| -1] ⊕ • • • ⊕ s[i q . . i q + |x| -1], which is a substring of Merge k introduced in Definition 9. We have that x u k and L x = i 1 ,i 2 ,...,iq∈Lx L u k . Since each u k for i 1 , i 2 , . . . , i q ∈ L x is a substring of Merge k , we infer that L x = i 1 ,i 2 ,...,iq∈Lx (L Merge k + δ k ) where the δ k 's are non-negative integers. By Definition 7, if Merge k were different from x, then x would not be tiling, which is a contradiction. Therefore, at least one Merge k is x. ⊲⊳

The following property of tiling bases follows from Lemma 5 and 6.

Theorem 6 Given a string s of length n and a quorum q ≥ 2, let M be the set of Merge k , for any of the n-1 q-1 possible choices of k for which Merge k exists. The basis B of tiling motifs for s satisfies B ⊆ M, and therefore the size of B is at most n-1 q-1 .

The tiling motifs in our basis appear in s for a total of q n-1 q-1 times at most. A variation of the algorithm given in Section 4.3 gives a pseudo-polynomial-time complexity of O q 2 n-1 q-1 2 .

When this upper bound is combined with the lower bound of Section 5.1, we obtain that there exists a polynomial-time algorithm for finding the basis if and only if either q = O(1) or q = n -O(1).

Conclusions

The work presented in this paper is theoretical in nature but it should be clear by now that its practical consequences, particularly-but not exclusively-for computational biology, are relevant. Whether motifs as patterns are used for inferring binding sites or repeats of any length, for characterizing sequences or as a filtering step in a whole genome comparison algorithm or before inferring PSSMs: we show that wild cards alone are not enough for a biologically satisfying definition of the patterns of interest. Simply throwing away the pattern-type of motif detection is not a good way to address the problem. This is confirmed by various biological publications [START_REF] Vanet | Promoter sequences and algorithmical methods for identifying them[END_REF][START_REF] Eskin | Genome-wide analysis of bacterial promoter regions[END_REF] as well as by the not yet published-but already publicly available-results of a first motif detection competition Even if patterns are not the best way of modelling biological features, they deserve an important function in any future improved algorithm for inferring motifs ab initio from biological sequences. As such, the purpose of this paper is to shed some further light on the inner structure of one important type of motif.

2

 2

Figure 1 :

 1 Figure 1: Example string s 7 , (a i of the definition is simply denoted by i). Above it, there are the occurrences of w of the Proof of Proposition 1, while the three lines below show the occurrences of motif x = 4 • 19 AAAA • AA in s 7 . The letter 4 corresponds to position 4 of the wild card in AAAA • AA.

Theorem 2 2 =

 22 •'s, as each distinct • symbol would match the letter T in s k giving |L y i | > |L x |, which is impossible. The only possibility is that y i contains exactly two •'s as x does at the same positions because L y ⊆ L x and they are maximal. It follows that y i = x proving the proposition. ⊲⊳ The basis for string s k contains Ω(n 2 ) irredundant motifs, where n = |s k | and k ≥ 5. Proof : By Proposition 2, the number of irredundant motifs in s k is at least k-2 Ω(k 2 ), the number of choices of two positions in {A, •} k-2 . Since |s k | = 5k + 1 by Fact 1, we get the conclusion. ⊲⊳ 4 Tiling Motifs: The Basis and its Properties 4.

Lemma 1

 1 For example, FABCXFADCYZEADCEADC has Merge 4 = EADC, Merge 5 = FA•C, Merge 6 = Merge 10 = ADC and Merge 11 = Merge 15 = A•C. The latter is the only merge that is not a tiling motif. If Merge k exists, it must be a maximal motif.

Lemma 4

 4 The set M * satisfies the conditions B ⊆ M * and x∈M * |L x | < 2n. Proof : The first condition follows from the fact that the motifs in M -M * are surely tiled by Lemma 3. The second condition follows from the definition of M * and from the observation that x∈M * |L x | = x∈M * |T x | ≤ x∈M |occ x | < 2n, since |occ x | = 2 (see Step 1) and there are less than n of them. ⊲⊳

Proposition 6

 6 Using the basis B of tiling motifs, LM g (s) can be computed in time O(b), where b = y∈B |y|.

  by Fact 1 and x matches the two substrings A k of s k as well as A p 1 TA k-p 1 -1 and A p 2 TA k-p 2 -1 . Any other motif y such that x occurs in y can be obtained by replacing at least one wild card (at position p 1 or p 2 ) in x with a solid character, but this would cause the removal of position 4kp 1 or 4kp 2 from L

x . Analogously, extending x to the right by putting a solid character at position |x| or larger would eliminate position 4k + 1 from L x . Finally, extending x to the left by a solid character would eliminate at least one position from L x because no symbol occurs four times in u k v k . In conclusion, for any motif y such that x occurs in y, we have L y = L x + d for any integer d, and thus x is a maximal motif by Definition 5. We now prove that x is irredundant according to Definition 6. Let us consider an arbitrary set of maximal motifs y 1 , y 2 , . . . , y h such that

In the literature on sequence analysis and pattern matching, the wild card is often referred to as don't care (as it is in the literature on bases of motifs). Therefore, we will use this latter term when referring to the sequence analysis and string matching literature.

Acknowledgements

Many suggestions of the anonymous referees greatly improved the original form of this paper. We are in debt with them for this and with M.H.ter Beek for improving the english.

Work partially supported by the French program bioinformatique EPST 2002 "Partially supported by the Italian PRIN project "ALINWEB: Algorithmics for Internet and the Web". Partially supported by CNRS action AlBio, NATO Science Programme grant PST.CLG.977017, and Wellcome Trust Foundation. ). Partially supported by the Italian PRIN project "ALINWEB: Algorithmics for Internet and the Web". Partially supported by CNRS-INRIA-INRA-INSERM action BioInformatique and Wellcome Trust Foundation.

Step 4. Discard the tiled motifs in M * . We can now check for tiling motifs in O(n 2 ) time. Given two distinct motifs x, y ∈ M * , we want to test whether L x +d ⊆ L y for some integer d and, in that case, we want to mark the entries in L y that are in L x + d. At the end of this task, the lists having all entries marked are tiled (see Definition 7). By removing their corresponding motifs from M * , we eventually obtain the basis B by Lemma 4. Since the meaningful values of d are as many as the entries of L y , we have only We therefore detail how to perform the above check with L x and L y in O(|L x | × |L y |) time. We use two bit-vectors V 1 and V 2 of length n initially set to all zeros. Given y ∈ M * , we set

For each x ∈ M * -{y} and for each d ∈ (L ym) (where m is the smallest entry of L x ), we then perform the following test. If all j ∈ L x + d satisfy V 1 [j] = 1, we set V 2 [j] = 1 for all such j. Otherwise, we take the next value of d, or the next motif if there are no more values of d, and we repeat the test. After examining all x ∈ M * -{y}, we check whether

for all i ∈ L y . If so, y is tiled as its list is covered by possibly shifted location lists of other motifs. We then reset the ones in both vectors in O(|L y |) time.

Summing up Steps 1-4, we have that the dominant cost is that of Step 3 and that we have proved the following result.

Theorem 4 Given an input string s of length n over the alphabet Σ, the basis of tiling motifs with quorum q = 2 can be computed in O(n 2 log n log |Σ|) time. The total number of motifs in the basis is less than n, and the total number of their occurrences in s is less than 2n.

We have implemented the algorithm underlying Theorem 4, and we report here the lessons learned from our experiments. Step 1 requires in practice less than the predicted O(n 2 ) running time. If p = 1/|Σ| denotes the probability that two randomly chosen symbols of Σ match in the uniform distribution, the probability of finding the first solid character in a merge follows the binomial distribution, and so the expected number of examined characters in s is O(1/p) = O(|Σ|), yielding O(n|Σ|) time on the average to locate the first (scanning s from the beginning) and the last (scanning s from the end backward) solid character in each merge. A similar


Charlotte C Kruijt
email: c.c.kruijt@lumc.nl.

Libe Gradstein

Arthur A Bergen

Ralph J Florijn

Benoit Arveiler

Eulalie Lasseaux

Xavier Zanlonghi

Laura Bagdonaite-Bejarano

Anne B Fulton

Claudia Yahalom

Anat Blumenfeld

Yonatan Perez

Ohad S Birk

Gerard C De Wit

Nicoline E Schalij-Delfos

Maria M Van Genderen

The Phenotypic and Mutational Spectrum of the FHONDA Syndrome and Oculocutaneous Albinism: Similarities and Differences

Keywords: SLC38A8, FHONDA, foveal hypoplasia, misrouting, melanin

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

U ntil 2006, misrouting of the visual pathways was only described in albinism and believed to be secondary to the lack of ocular pigmentation. [START_REF] Kinnear | Albinism[END_REF][START_REF] Summers | Vision in albinism[END_REF][START_REF] Charles | Clinical features of affected males with X linked ocular albinism[END_REF][START_REF] Jeffery | Correction of retinal abnormalities found in albinism by introduction of a functional tyrosinase gene in transgenic mice and rabbits[END_REF] In 2006, van Genderen et al. first reported the combination of misrouting and foveal hypoplasia in patients without albinism. [START_REF] Van Genderen | Chiasmal misrouting and foveal hypoplasia without albinism[END_REF] The patients described in this paper showed similarities to a family described by Pal et al. with foveal hypoplasia and anterior segment dysgenesis. [START_REF] Pal | A new phenotype of recessively inherited foveal hypoplasia and anterior segment dysgenesis maps to a locus on chromosome 16q23.2-24.2[END_REF] In 2013, the term FHONDA was introduced for the disorder, which is short for Foveal Hypoplasia, Optic Nerve Decussation defects and Anterior segment dysgenesis. [START_REF] Al-Araimi | A new recessively inherited disorder composed of foveal hypoplasia, optic nerve decussation defects and anterior segment dysgenesis maps to chromosome 16q23.3-24[END_REF] Poulter et al. discovered that mutations in the SLC38A8 gene were responsible for the FHONDA syndrome and demonstrated that in embryonic Medaka fish, knockdown of both orthologs of SLC38A8 did not result in any pigmentation defect of the eye or tegumen. [START_REF] Poulter | Recessive mutations in SLC38a8 cause foveal hypoplasia and optic nerve misrouting without albinism[END_REF] Perez et al. described 9 patients with homozygous SLC38A8 mutations who had a combination of foveal hypoplasia and nystagmus also without any signs of hypopigmentation. [START_REF] Perez | Isolated foveal hypoplasia with secondary nystagmus and low vision is associated with a homozygous SLC38A8 mutation[END_REF] FHONDA and albinism share the clinical features of nystagmus, foveal hypoplasia, and misrouting, but because of the lack of pigmentation defect in Medaka fish, and in earlier reported patients with FHONDA it seems that albinism and FHONDA are distinct disorders.

The phenotypic spectrum of albinism has been extensively investigated and appears to be very broad. [START_REF] Kruijt | The Phenotypic Spectrum of Albinism[END_REF][START_REF] Grønskov | Birth Prevalence and Mutation Spectrum in Danish Patients with Autosomal Recessive Albinism[END_REF][START_REF] Mauri | Clinical evaluation and molecular screening of a large consecutive series of albino patients[END_REF][START_REF] Marti | Lessons of a day hospital: Comprehensive assessment of patients with albinism in a European setting[END_REF][START_REF] Lasseaux | Molecular characterization of a series of 990 index patients with albinism[END_REF][START_REF] Dem Hagen | Pigmentation predicts the shift in the line of decussation in humans with albinism[END_REF] Albinism is a heterogeneous condition, and even patients who have mutations in the same gene also show variable clinical features. Visual acuity in albinism ranges from very poor to normal and foveal hypoplasia of all grades has been described, from absent (grade 0) to severe (grade 4). None of the clinical features is universal for all patients with albinism, with nystagmus being absent in at least 7% and misrouting in 16%. [START_REF] Kruijt | The Phenotypic Spectrum of Albinism[END_REF] FHONDA appears to be rare, and seems more homogeneous than albinism. Since the identification of the first patient, only a few cases have been reported. [START_REF] Van Genderen | Chiasmal misrouting and foveal hypoplasia without albinism[END_REF][START_REF] Pal | A new phenotype of recessively inherited foveal hypoplasia and anterior segment dysgenesis maps to a locus on chromosome 16q23.2-24.2[END_REF][START_REF] Al-Araimi | A new recessively inherited disorder composed of foveal hypoplasia, optic nerve decussation defects and anterior segment dysgenesis maps to chromosome 16q23.3-24[END_REF][START_REF] Poulter | Recessive mutations in SLC38a8 cause foveal hypoplasia and optic nerve misrouting without albinism[END_REF][START_REF] Perez | Isolated foveal hypoplasia with secondary nystagmus and low vision is associated with a homozygous SLC38A8 mutation[END_REF][START_REF] Lasseaux | Molecular characterization of a series of 990 index patients with albinism[END_REF][START_REF] Kuht | SLC38A8 mutations result in arrested retinal development with loss of cone photoreceptor specialization[END_REF][START_REF] Toral | Structural modeling of a novel SLC38A8 mutation that causes foveal hypoplasia[END_REF][START_REF] Vincent | Variable expressivity of ocular associations of foveal hypoplasia in a family[END_REF][START_REF] Campbell | Clinical and genetic variability in children with partial albinism[END_REF][START_REF] Weiner | The pathogenicity of SLC38A8 in five families with foveal hypoplasia and congenital nystagmus[END_REF] The disorder is unknown to most clinicians and therefore is not adequately recognized. The purpose of this study is to further define the phenotypic and genetic spectrum of FHONDA, and to compare its presentation to albinism.

METHODS

The study was approved by the Medical Ethics Committee of Leiden University Medical Center and adhered to the tenets of the Declaration of Helsinki.

Patients With FHONDA

We included 28 patients with FHONDA from 4 countries, 12 male patients and 17 female patients, aged 1 to 71 years (median age 24 years). All patients, or their affected siblings, had two likely disease-causing variants in SLC38A8, and had records on their pigmentation status and ophthalmic findings.

Patients with FHONDA from the Netherlands (9 patients and 5 families) were diagnosed at the Bartiméus Institute. Additional patients came from tertiary referral centers in Israel (13 patients, 7 families), France, (2 patients, 1 family), and the United States of America (4 patients, 3 families). Five patients from the Netherlands, nine from Israel, and one patient from France were previously reported, however, several clinical features were not described, for instance, grading of foveal hypoplasia. [START_REF] Van Genderen | Chiasmal misrouting and foveal hypoplasia without albinism[END_REF][START_REF] Al-Araimi | A new recessively inherited disorder composed of foveal hypoplasia, optic nerve decussation defects and anterior segment dysgenesis maps to chromosome 16q23.3-24[END_REF][START_REF] Poulter | Recessive mutations in SLC38a8 cause foveal hypoplasia and optic nerve misrouting without albinism[END_REF][START_REF] Lasseaux | Molecular characterization of a series of 990 index patients with albinism[END_REF] Data were obtained through medical record review for best-corrected visual acuity (VA), refractive error, pigmentation of eyes, skin, and hair, slit lamp examination, ophthalmoscopy, fundus photography, optical coherence tomography (OCT) scans, and multichannel Visual Evoked Potentials (VEPs) tests. We used a grading scheme for foveal hypoplasia previously described by Thomas et al., with grade 0 indicating normal foveal structure, grades 1 and 2 not having incursion of the inner retinal layers, and grades 3 and 4 also affecting the photoreceptor differentiation (Supplementary Table S1). [START_REF] Thomas | Structural grading of foveal hypoplasia using spectral-domain optical coherence tomography a predictor of visual acuity?[END_REF] Multichannel VEPs were obtained with Espion E2 or E3 (Diagnosys LLC, Cambridge, UK), according to ISCEV standards. [START_REF] Robson | ISCEV guide to visual electrodiagnostic procedures[END_REF] A chiasm coefficient was calculated and the cutoff values were used from the study of Kruijt et al. [START_REF] Kruijt | The detection of misrouting in albinism: Evaluation of different VEP procedures in a heterogeneous cohort[END_REF]

FHONDA Versus Albinism

We compared the phenotypic spectrum of FHONDA to that of 133 patients with genetically confirmed albinism, 99 male patients and 34 female patients, aged 0 to 77 years (median age 10 years). These patients had either two mutations in TYR (49 patients) or OCA2 (41 patients), or a mutation in GPR143 (43 patients). Mutations in TYR and OCA2 cause oculocutaneous albinism (OCA) type 1 and 2, respectively, and those in GPR143 cause ocular albinism (OA1), the 3 most common types of albinism in the Netherlands.We used IBM SPSS Statistics software version 22 to perform statistical analysis. Data were not normally distributed, and therefore we used nonparametric tests.

RESULTS

All but two of the 28 patients with FHONDA were able to cooperate with VA measurement, OCT scans for grading were available in 17 of 28 cases. VEP testing was performed in 9 of 28 patients. VA could be tested in 57 of 90 patients with albinism, in 43 of 90 patients, OCT-scans were obtained, and in 58 of 90 patients VEP tests were done.

FHONDA (N = 28)

Molecular analyses and demographic characteristics of the 28 patients with FHONDA are presented in Table 1. Patients had a total of 15 different mutations in SLC38A8, consisting of missense, (inframe) deletions, frameshift, and truncating mutations located over the entire gene (Table 1, Fig. 1). We report six novel mutations: c.260C > T; p. About two thirds of the patients (i.e. 18/28 patients from 8 families, were of south-western Asian origin, Afghani, and Indian, and Ashkenazi Jewish descent). All had homozygous mutations, except the patient from family XIII. The 11 patients from the 4 Indian Jewish families were all homozygous for c.95T > G; p.(Ile32Ser). The c.848A > C variant was found in all Ashkenazi-Jewish patients. The patient from family XIII was of a mixed origin, includingAshkenazi, Lebanon-Syria, and Yemenite-Afghanisti descent, and had a compound heterozygous mutation c.848A > C; p.(Asp283Ala), and a whole gene deletion. In contrast, 9 of 10 (partially) western European patients were compound heterozygotes. Phenotypic data of patients with FHONDA are presented in Table 2. Patients (25/28) had a median VA of 0.7 logMAR (interquartile range [IQR] = 0.6-0.8). None of the patients was emmetropic, with moderate (1 to 2 diopters) to severe (>2 diopters) astigmatism as the most characteristic refractive error. Only 4 of 28 patients had anterior segment abnormalities (i.e. posterior embryotoxon). All patients had nystagmus (28/28), grade four foveal hypoplasia (17/17), and misrouting of the optic nerve fibers at the chiasm (9/9). All (28/28) patients had normal pigmentation of skin, and/or hair compared to family members and no iris translucency. Fundus imaging showed a lightly pigmented midperiphery in an infant of 6 months of age (VII-811), but some pigmentation was already seen in the macular region. Figures 2A and2B show examples of foveal hypoplasia and fundus images in patients with FHONDA and patients with albinism. Figure 3 shows misrouting in a patient with FHONDA.

FHONDA (N = 28) Versus Albinism (N = 133)

VA was poorer and less variable in FHONDA (median = 0.7 logMAR, IQR = 0.6-0.8) compared to the 133 patients with albinism (median = 0.5 logMAR, IQR = 0.3-0.7, Mann-Whitney U test, P = 0.006). Analysis of VA of FHONDA compared to the different subtypes of albinism showed a significantly better VA in OCA1 and OCA2 (median = 0.5 logMAR, IQR = 0.3-0.7, P = 0.004, and median = 0.5 logMAR, IQR = 0.2-0.7, P = 0.006), respectively). Median VA in OA1 was 0.6 logMAR, IQR = 0.5 to 0.8 and was not [START_REF] Thomas | Structural grading of foveal hypoplasia using spectral-domain optical coherence tomography a predictor of visual acuity?[END_REF] The patient had two mutations in the TYR gene (c.164G > A and c.896G > A), visual acuity was 1.0 logMAR, and patient had nystagmus, and complete iris translucency. (D) Example of an albinism patient without obvious hypopigmentation of the fundus, comparable to patient FIII-804 with FHONDA. Note the minimal foveal hypoplasia grade 1. [START_REF] Thomas | Structural grading of foveal hypoplasia using spectral-domain optical coherence tomography a predictor of visual acuity?[END_REF] Other manifestations were also mild, with a suboptimal visual acuity of 0.3 logMAR, nystagmus, and absence of iris translucency. The patient was homozygote for mutation c.1037-7T > A in the TYR gene. All optical coherence tomography scans of the left eye and right eye had the same grade of foveal hypoplasia. significantly better than in FHONDA (P = 0.11). Besides VA, all phenotypic characteristics in OCA1, OCA2, and OA1 were more variable than in FHONDA in this study: 11% (14/132) of patients with albinism did not have nystagmus (0% in FHONDA), foveal hypoplasia varied from grades 1 to 4 (only grade 4 in FHONDA), and misrouting was absent in 22% (16/74, 0% in FHONDA; see also Fig. 4) Misrouting was more evident in FHONDA, and was detected with all stimulus types (i.e. pattern onset and flash VEP), regardless of age. In albinism, VEP recordings were much more variable, and when misrouting was confirmed by the method recommended for that age, it was not always present in recordings with other stimuli (Fig. 5).

Patients with OA1 resemble patients with FHONDA the most, because they have no hypopigmentation of the skin or hair. In addition, they have on average poorer VA and more severe foveal hypoplasia than patients with OCA in our cohort. However, almost all patients with OA1 have ocular hypopigmentation, in contrast to none of the patients with FHONDA. In our cohort, only 3 of 43 patients with OA1 were described with normal ocular pigmentation (no iris translucency AND normal fundus pigmentation). The first patient had grade one hypopigmentation of the posterior pole, according to the scheme of Kruijt et al., [START_REF] Kruijt | The Phenotypic Spectrum of Albinism[END_REF] which was considered normal in this fair skinned Caucasian patient. However, he had obvious hypopigmentation of the (mid)periphery with choroidal vessels clearly visible through the translucent retinal pigment epithelium. He had VA of 0.5 logMAR, nystagmus, foveal hypoplasia grade 3, and misrouting. The second patient with OA1, from Somalian descent, had high myopia, VA of 1.0 logMAR, nystagmus, and no misrouting. An OCT scan was not obtained. There was possible hypopigmentation of the fundus, but this could also be secondary to the high myopia (S-16/ S-14). The last patient, of mixed S1). [START_REF] Thomas | Structural grading of foveal hypoplasia using spectral-domain optical coherence tomography a predictor of visual acuity?[END_REF] Misrouting was determined by using cutoff values from the study of Kruijt et al. for the calculated chiasm coefficients from the multichannel visually evoked potential recordings. Dutch-Indonesian descent, had VA of 0.25 logMAR, nystagmus, foveal hypoplasia grade 2, and misrouting. Ocular pigmentation for FHONDA and the albinism subtypes is shown in Figure 4.

DISCUSSION

In this study, we described the genotypic and phenotypic characteristics of the rare FHONDA syndrome and compared it to the phenotype of the most common types of albinism, OCA1, OCA2, and OA1. To date, only 33 patients with the FHONDA syndrome were reported in the literature. [START_REF] Pal | A new phenotype of recessively inherited foveal hypoplasia and anterior segment dysgenesis maps to a locus on chromosome 16q23.2-24.2[END_REF][START_REF] Al-Araimi | A new recessively inherited disorder composed of foveal hypoplasia, optic nerve decussation defects and anterior segment dysgenesis maps to chromosome 16q23.3-24[END_REF][START_REF] Poulter | Recessive mutations in SLC38a8 cause foveal hypoplasia and optic nerve misrouting without albinism[END_REF][START_REF] Lasseaux | Molecular characterization of a series of 990 index patients with albinism[END_REF][START_REF] Kuht | SLC38A8 mutations result in arrested retinal development with loss of cone photoreceptor specialization[END_REF][START_REF] Toral | Structural modeling of a novel SLC38A8 mutation that causes foveal hypoplasia[END_REF][START_REF] Vincent | Variable expressivity of ocular associations of foveal hypoplasia in a family[END_REF][START_REF] Campbell | Clinical and genetic variability in children with partial albinism[END_REF][START_REF] Weiner | The pathogenicity of SLC38A8 in five families with foveal hypoplasia and congenital nystagmus[END_REF]

Genotype

The SLC38A8 gene consists of 10 exons (all coding), spanning almost 32.4 kb of genomic DNA in the region of 16q23.3. This gene encodes the Solute carrier family 38 member 8 protein, a 46.9 kDa putative sodium-coupled neutral amino acid transporter (SNAT) with 11 transmembrane domains, which consists of 435 amino acids. The protein is expressed in the central nervous system and neuronal retina, predominantly in the inner and outer plexiform layers and photoreceptor layers. SLC38A8 has a possible broad substrate profile with high preference for transporting glutamate. [START_REF] Poulter | Recessive mutations in SLC38a8 cause foveal hypoplasia and optic nerve misrouting without albinism[END_REF][START_REF] Hägglund | Transport of l-glutamine, l-alanine, l-arginine and l-histidine by the neuron-specific slc38a8 (SNAT8) in CNS[END_REF] Including all patients from the literature, 15 of the 18 identified missense mutations are localized in, or very near, transmembrane regions (see Fig. 1, Supplementary Table S2). Mutations probably affect the transport function of the protein. The p.(Thr87Ile) and p.(Asp283Ala) are both localized on the extracellular side of the channel and cause a change to a hydrophobic amino acid. Toral et al. postulated that p.(Asp283Ala) missense mutation results in a more positive electrostatic potential at the extracellular side of the channel, potentially disrupting the local concentration of sodium and affecting glutamine transport. [START_REF] Toral | Structural modeling of a novel SLC38A8 mutation that causes foveal hypoplasia[END_REF] However, the exact mechanisms of the pathogenicity of the identified missense mutations are still unknown.

The identified nonsense, splice, deletion, and frameshift mutations are spread over the entire gene. They result in translation of a truncated protein or reduced amount of protein due to nonsense mediated decay, thus, affecting localization and/or transport function of the protein. A SLC38A8 functional analysis test is needed to determine the pathological effects of the identified mutations.

It is noteworthy that the c.848A > C; p.(Asp283Ala) mutation was detected in all Ashkenazi Jewish patients reported in this study, and 2 Ashkenazi Jewish patients from the study of Toral et al. [START_REF] Toral | Structural modeling of a novel SLC38A8 mutation that causes foveal hypoplasia[END_REF] In total, five patients from three families were homozygous, and one patient of mixed Ashkenazi descent was compound heterozygous. In all Indian Jewish patients from this study, and Indian and Karaite Jewish patients reported in the literature, the mutation c.95T > G; p.(Ile32Ser) was discovered, 17 patients from 8 families were homozygous and one patient was compound heterozygous (see Table 1, Supplementary Table S2). This mutation was not seen in other patients. The six novel SLC38A8 mutations identified in our study significantly extend the genotypic heterogeneity among patients with FHONDA.

Phenotype

All 38 different mutations that are discovered until now in the SLC38A8 gene resulted in similar phenotypes, comprising poor VA, nystagmus, severe foveal hypoplasia (grade 4 in our study, and grade 3 or 4 in previously reported patients), definite chiasmal misrouting, and no signs of any pigmentation defect (skin, hair, iris, or fundus). All newly diagnosed and all but two of the previously reported patients fit this profile. [START_REF] Van Genderen | Chiasmal misrouting and foveal hypoplasia without albinism[END_REF][START_REF] Pal | A new phenotype of recessively inherited foveal hypoplasia and anterior segment dysgenesis maps to a locus on chromosome 16q23.2-24.2[END_REF][START_REF] Al-Araimi | A new recessively inherited disorder composed of foveal hypoplasia, optic nerve decussation defects and anterior segment dysgenesis maps to chromosome 16q23.3-24[END_REF][START_REF] Poulter | Recessive mutations in SLC38a8 cause foveal hypoplasia and optic nerve misrouting without albinism[END_REF][START_REF] Perez | Isolated foveal hypoplasia with secondary nystagmus and low vision is associated with a homozygous SLC38A8 mutation[END_REF][START_REF] Toral | Structural modeling of a novel SLC38A8 mutation that causes foveal hypoplasia[END_REF][START_REF] Vincent | Variable expressivity of ocular associations of foveal hypoplasia in a family[END_REF][START_REF] Campbell | Clinical and genetic variability in children with partial albinism[END_REF][START_REF] Weiner | The pathogenicity of SLC38A8 in five families with foveal hypoplasia and congenital nystagmus[END_REF] These two patients seem to express some amount of hypopigmentation. First, patient P4, one of 990 patients from an albinism study by Lasseaux et al. had iris translucency. [START_REF] Lasseaux | Molecular characterization of a series of 990 index patients with albinism[END_REF] Further details of this patient were unavailable, so we were unable to determine if this translucency could have other causes. The other patient from this study that had iris translucency was excluded from the series (personal communication). In addition, one patient described by Kuht et al. had mild iris transillumination, but this patient also had a TYR variant which could explain the pigmentation defect of the iris. In three patients, some hypopigmentation of the fundus was described. In all patients, the pigmentation could be considered normal for age, because two patients were only a few months old. The only adult was of white British background and she had no hypopigmentation compared to her family. [START_REF] Kuht | SLC38A8 mutations result in arrested retinal development with loss of cone photoreceptor specialization[END_REF][START_REF] Campbell | Clinical and genetic variability in children with partial albinism[END_REF] It is noteworthy that, even though we detected 6 various novel SLC38A8 mutations among our patients, this did not change the phenotypic homogeneity. The only variable phenotypic characteristic of FHONDA appears to be anterior segment dysgenesis (ASD), mostly consisting of posterior embryotoxon/Axenfeld's anomaly. This was found in only four patients from three families in this study, and seven patients from three families of previously reported patients (see Table 2, Supplementary Table S3). The genetic changes in four families with posterior embryotoxon were solely detected in these patients, and not in any patients without ASD. However, differences in genotype cannot fully explain the presence or absence of ASD, because mutations in the remaining three families with ASD were also observed in patients without any ASD. This means that posterior embryotoxon/Axenfeld's anomaly is not a frequent abnormality in this disorder, occurring in less than 19% of the patients, which is within the range of prevalence in the normal population (7-32%). [START_REF] Forsius | Embryotoxon corneae posterius in an isolated population[END_REF][START_REF] Ozeki | Clinical evaluation of posterior embryotoxon in one institution[END_REF][START_REF] Rennie | The prevalence and associated features of posterior embryotoxon in the general ophthalmic clinic[END_REF][START_REF] Hashemi | The frequency of occurrence of certain corneal conditions by age and sex in Iranian adults[END_REF]

FHONDA Versus Albinism

It is interesting that FHONDA appears to have a more narrow phenotypic spectrum compared to albinism, especially with regard to nystagmus, grade of foveal hypoplasia, and chiasmal misrouting. Mutations in several genes can cause different subtypes of albinism, but within one genetic subtype, the phenotypic spectrum is still broad. [START_REF] Kruijt | The Phenotypic Spectrum of Albinism[END_REF][START_REF] Grønskov | Birth Prevalence and Mutation Spectrum in Danish Patients with Autosomal Recessive Albinism[END_REF][START_REF] Marti | Lessons of a day hospital: Comprehensive assessment of patients with albinism in a European setting[END_REF][START_REF] Lasseaux | Molecular characterization of a series of 990 index patients with albinism[END_REF] A previous study on albinism concluded that absence of photoreceptor specialization (grades 3 and 4 foveal hypoplasia) was associated with worse VA in albinism, with grade 4 associated with the poorest VA. [START_REF] Kruijt | The Phenotypic Spectrum of Albinism[END_REF] Photoreceptor differentiation was affected in all patients with FHONDA, which may explain the significantly poorer VA than in albinism. Besides poorer VA and more severe foveal hypoplasia, misrouting was detected with all VEP test stimuli with chiasm coefficients not higher than -0.45. This could be explained by, on average, more crossing of the optic nerve fibers at the chiasm than in albinism, so that noise is not affecting the signal as much (noise causes a shift of the chiasm coefficient towards zero). [START_REF] Kruijt | The detection of misrouting in albinism: Evaluation of different VEP procedures in a heterogeneous cohort[END_REF] This theory is also supported by the findings of Ahmadi et al., who demonstrated that in a patient with FHONDA, all temporal retinal fibers project to the contralateral hemisphere, instead of excessive crossing only in most patients with albinism. [START_REF] Ahmadi | Altered organization of the visual cortex in FHONDA syndrome[END_REF] Despite the recently described diagnostic criteria for albinism, the clinical distinction between patients with FHONDA of Caucasian descent and patients with OA1 without evident ocular hypopigmentation might still be difficult. For instance, mild hypopigmentation of the (mid)peripheral fundus can be normal in a lightly pigmented Caucasian family, as is seen in the patient with FHONDA VII-811 and in proband 2 described by Campbell et al. In our OA1 cohort, we identified only three patients without ocular hypopigmentation. One patient was mildly affected, in contrast to FHONDA, with better VA, and grade 1 or 2 foveal hypoplasia. In the other two patients, fundus hypopigmentation could be related to an overall light skinned Caucasian phenotype and high myopia, respectively. Of these two patients, one resembled FHONDA closely (VA 0.5 logMAR, nystagmus, foveal hypoplasia grade 3, and misrouting), whereas the other patient did not have misrouting, which has not yet been reported in patients with FHONDA. Therefore, only in 1 of 43 patients with OA1 the differentiation with FHONDA could not be clearly made. To further differentiate the two disorders, in a recent study describing the phenotypic spectrum of albinism, poor visual acuity, grade 4 foveal hypoplasia, and misrouting were always accompanied by iris translucency or other obvious signs of hypopigmentation. [START_REF] Kruijt | The Phenotypic Spectrum of Albinism[END_REF] This means that in a severely affected patient but without evident hypopigmentation the possibility of FHONDA is most likely (see Fig. 2). It should be noted, however, that this conclusion is based on a small number of patients with FHONDA. The identification of only 3e patients with mutations in SLC38A8 in a series of 990 presumed patients with albinism, and only 61 patients with FHONDA reported to date confirm that this is a rare entity. [START_REF] Lasseaux | Molecular characterization of a series of 990 index patients with albinism[END_REF] We hope that this study will raise physicians' awareness to this uncommon disease and that SLC38A8 will be added to gene panels for nystagmus.

This study confirms that, in consent with the findings of Poulter et al., FHONDA and albinism appear to be different entities, and the combination of foveal hypoplasia and misrouting of the optic nerve fibers can occur independently of abnormal melanin synthesis. It is therefore plausible that a common pathway exists that causes both foveal hypoplasia and misrouting. The uniformly severe pheno- type of FHONDA suggests that SLC38A8 might be located at the end of this pathway, without the possibility of a partial rescue.

Downloaded
Although Ehprin-B1 was previously identified as playing a key role in ipsilateral guidance in species with a small part of the ventral retina projecting ipsilaterally, Hoffmann et al. did not detect an association with visual pathway abnormalities in humans with Ephrin-B1 deficiency. [START_REF] Nakagawa | Ephrin-B Regulates the Ipsilateral Routing of Retinal Axons at the Optic Chiasm[END_REF][START_REF] Williams | Ephrin-B2 and EphB1 Mediate Retinal Axon Divergence at the Optic Chiasm[END_REF][START_REF] Lambot | Mapping Labels in the Human Developing Visual System and the Evolution of Binocular Vision[END_REF][START_REF] Hoffmann | Visual Pathways in Humans With Ephrin-B1 Deficiency Associated With the Cranio-Fronto-Nasal Syndrome[END_REF] We hypothesize that other components of the Eph system may play an important role in this pathway. Ephrins are a family of membrane-tethered proteins that serve as ligands of the Eph receptor. Eph/ephrin signaling regulates many developmental processes, including the guidance of axonal growth of cones, and formation of tissue boundaries. [START_REF] Egea | Bidirectional Eph-ephrin signaling during axon guidance[END_REF][START_REF] Rohani | EphrinB/EphB signaling controls embryonic germ layer separation by contact-induced cell detachment[END_REF][START_REF] Fagotto | A Molecular Base for Cell Sorting at Embryonic Boundaries: Contact Inhibition of Cadherin Adhesion by Ephrin/Eph-Dependent Contractility[END_REF] The formation of a foveal avascular zone (FAZ) is necessary for normal foveal development. [START_REF] Provis | Adaptation of the central retina for high acuity vision: Cones, the fovea and the a vascular zone[END_REF] Kozulin et al. showed involvement of pigment epithelium derived factor (PEDF) and EphA6 in the definition of the FAZ. [START_REF] Kozulin | Gradients of Eph-A6 expression in primate retina suggest roles in both vascular and axon guidance[END_REF][START_REF] Kozulin | Differential expression of anti-angiogenic factors and guidance genes in the developing macula[END_REF] During formation of the FAZ, EphA6 levels start to rise in the macular region and continue to rise after birth while cone differentiation and elongation of the most central cones occurs, a process that appears not to take place in patients with grade four foveal hypoplasia. [START_REF] Provis | Adaptation of the central retina for high acuity vision: Cones, the fovea and the a vascular zone[END_REF][START_REF] Kozulin | Gradients of Eph-A6 expression in primate retina suggest roles in both vascular and axon guidance[END_REF][START_REF] Kozulin | Differential expression of anti-angiogenic factors and guidance genes in the developing macula[END_REF] During axon guidance, EphA6 expression is highest in the temporal retina and gradually drops around the central retina, implying an important role of EphA6 in retinal ipsilateral axon guidance. [START_REF] Lambot | Mapping Labels in the Human Developing Visual System and the Evolution of Binocular Vision[END_REF][START_REF] Provis | Adaptation of the central retina for high acuity vision: Cones, the fovea and the a vascular zone[END_REF] Therefore, EphA6 might be a promising candidate for a common pathway causing foveal hypoplasia and excessive crossing of the optic nerve fibers at the chiasm.

In conclusion, we describe the mutational spectrum, including six novel mutations, and narrow phenotypic spectrum of FHONDA, consisting of poor VA, nystagmus, severe foveal hypoplasia (grade 3 or 4), and chiasmal misrouting. Our study confirms that lack of pigmentation is not essential to cause the combined occurrence of foveal hypoplasia and misrouting. This, in turn, may have important implications for current research on the pathogenesis of these abnormalities and future therapeutic options for alleviation of ocular anomalies leading to vision loss in albinism. [START_REF] Onojafe | Nitisinone improves eye and skin pigmentation defects in a mouse model of oculocutaneous albinism Nitisinone improves eye and skin pigmentation defects in a mouse model of oculocutaneous albinism[END_REF][START_REF] Dolinska | Albinism-causing mutations in recombinant human tyrosinase alter intrinsic enzymatic activity[END_REF]

  (Thr87Ile) and c.800T > G; p.(Leu267Arg) in the Dutch family III, c.160G > T; p.(Gly54*) and c.388 + 5G > A; p.(?) in family VII from the United States, c.(805 + 1_806-1)_(1162 + 1_1163-1)del; p.(?) (deletion exon 7 and 8) in the French family VI and family VIII from the United States, respectively, and c.1256G > T; p.(Gly419Val) in family VIII.

>FIGURE 1 .

 1 FIGURE 1. Schematic representation of the SLC38A8 gene. The location of the variants found in this study patients is represented on the right and of those retrieved from literature on the left, in grey. Exons are illustrated in orange and blue, transmembrane domains in green. Deletions are depicted at the location of the first deletion coordinate.

  six months of age ND VIII-812 +7.75D/-4.75Dx2 +7.75D/-4.50Dx2 partially described previously. 5,7-9,14 † Refraction right eye (RE) and left eye (LE). ‡ Visual acuity in logMAR. VII-811 was not determined because patient was one year of age. § According to the grading of Thomas et al. 21 Downloaded from iovs.arvojournals.org on 11/03/2023

FIGURE 2 .

 2 FIGURE 2. Clinical results. (A) Fundus images and optical coherence tomography scans of the clinical study patient VIII-812. (B) Fundus image and optical coherence tomography scan of clinical study patient III-804. (C) Example of a severely affected albinism patient. Note the completely translucent fundus accompanied by grade four foveal hypoplasia.[START_REF] Thomas | Structural grading of foveal hypoplasia using spectral-domain optical coherence tomography a predictor of visual acuity?[END_REF] The patient had two mutations in the TYR gene (c.164G > A and c.896G > A), visual acuity was 1.0 logMAR, and patient had nystagmus, and complete iris translucency. (D) Example of an albinism patient without obvious hypopigmentation of the fundus, comparable to patient FIII-804 with FHONDA. Note the minimal foveal hypoplasia grade 1.[START_REF] Thomas | Structural grading of foveal hypoplasia using spectral-domain optical coherence tomography a predictor of visual acuity?[END_REF] Other manifestations were also mild, with a suboptimal visual acuity of 0.3 logMAR, nystagmus, and absence of iris translucency. The patient was homozygote for mutation c.1037-7T > A in the TYR gene. All optical coherence tomography scans of the left eye and right eye had the same grade of foveal hypoplasia.

FIGURE 3 .

 3 FIGURE 3. Chiasmal misrouting in FHONDA. (A) Visually evoked pattern onset potentials recordings of a normal subject. Note correlation of responses recorded from right and left eye in the differential signal. (B) Visually evoked pattern onset potentials from clinical study patient V-808. Note the asymmetry in the differential signal recorded from right eye and left eye.The chiasm coefficient was -0.9, indicating chiasmal misrouting.[START_REF] Kruijt | The detection of misrouting in albinism: Evaluation of different VEP procedures in a heterogeneous cohort[END_REF][START_REF] Jansonius | A girl without a chiasm: electrophysiologic and MRI evidence for the absence of crossing optic nerve fibers in a girl with a congenital nystagmus[END_REF][START_REF] Pott | Chiasmal coefficient of flash and pattern visual evoked potentials for detection of chiasmal misrouting in albinism[END_REF]

FIGURE 4 .

 4 FIGURE 4. Phenotypic spectrum of FHONDA versus oculocutaneous albinism type 1, type 2, and ocular albinism. For the grading of foveal hypoplasia we used a grading scheme according to Thomas et al., with grades 1 and 2 not having incursion of the inner retinal layers, and grades 3 and 4 also affecting the photoreceptor differentiation (see Supplementary TableS1).[START_REF] Thomas | Structural grading of foveal hypoplasia using spectral-domain optical coherence tomography a predictor of visual acuity?[END_REF] Misrouting was determined by using cutoff values from the study of Kruijt et al. for the calculated chiasm coefficients from the multichannel visually evoked potential recordings.[START_REF] Kruijt | The detection of misrouting in albinism: Evaluation of different VEP procedures in a heterogeneous cohort[END_REF]

23

 23 FIGURE 4. Phenotypic spectrum of FHONDA versus oculocutaneous albinism type 1, type 2, and ocular albinism. For the grading of foveal hypoplasia we used a grading scheme according to Thomas et al., with grades 1 and 2 not having incursion of the inner retinal layers, and grades 3 and 4 also affecting the photoreceptor differentiation (see Supplementary TableS1).[START_REF] Thomas | Structural grading of foveal hypoplasia using spectral-domain optical coherence tomography a predictor of visual acuity?[END_REF] Misrouting was determined by using cutoff values from the study of Kruijt et al. for the calculated chiasm coefficients from the multichannel visually evoked potential recordings.[START_REF] Kruijt | The detection of misrouting in albinism: Evaluation of different VEP procedures in a heterogeneous cohort[END_REF]

FIGURE 5 .

 5 FIGURE 5. Visually evoked potentials in FHONDA and albinism. The chiasm coefficients were calculated according to Kruijt et al.[START_REF] Kruijt | The detection of misrouting in albinism: Evaluation of different VEP procedures in a heterogeneous cohort[END_REF] A negative chiasm coefficient indicates misrouting. This figure shows all test results, independently of age. Not all patients were tested with all stimuli, sometimes only the stimulus recommended for the age was used. Note the variability in albinism and the obvious misrouting in patients with FHONDA for all stimuli.

  from iovs.arvojournals.org on 11/03/2023 The Phenotypic Spectrum of the FHONDA Syndrome IOVS | January 2022 | Vol. 63 | No. 1 | Article 19 | 10

TABLE 1 .

 1 Molecular Analyses Patients With FHONDA Family

TABLE 2 .

 2 Phenotype Patients With FHONDA

Acknowledgments

The authors thank Herman Talsma for his insightful help with the creation of the illustrations. The authors would also like to thank Herman Talsma, Frans Riemslag, and Frank Hoeben for performing many of the visually evoked potentials recordings.

Supported by the following foundations in the form of unrestricted funds: ODAS, Vereniging Bartiméus Sonneheerdt and Landelijke Stichting Blinden en Slechtzienden (via contributions through UitZicht). The funding organizations had no role in the design or conduct of this research. Disclosure: C.C. Kruijt, None; L. Gradstein, None; A.A. Bergen, None; R.J. Florijn, None; B. Arveiler, None; E. Lasseaux, None; X. Zanlonghi, None; L. Bagdonaite-Bejarano, None; A.B. Fulton, None; C. Yahalom, None; A. Blumenfeld, None; Y. Perez, None; O.S. Birk, None; G.C. de Wit, None; N.E. Schalij-Delfos, None; M.M. van Genderen, None