Pablo Barceló
email: pbarcelo@dcc.uchile.cl

Diego Figueira
email: dfigueir@inf.ed.ac.uk

Leonid Libkin
email: libkin@inf.ed.ac.uk

Graph Logics with Rational Relations and the Generalized Intersection Problem

Keywords: rational relations, regular relations, recognizable relations, logics for graphs, expressive power, decidability and complexity, regular path queries, subsequence, subword

We investigate some basic questions about the interaction of regular and rational relations on words. The primary motivation comes from the study of logics for querying graph topology, which have recently found numerous applications. Such logics use conditions on paths expressed by regular languages and relations, but they often need to be extended by rational relations such as subword (factor) or subsequence. Evaluating formulae in such extended graph logics boils down to checking nonemptiness of the intersection of rational relations with regular or recognizable relations (or, more generally, to the generalized intersection problem, asking whether some projections of a regular relation have a nonempty intersection with a given rational relation).

We prove that for several basic and commonly used rational relations, the intersection problem with regular relations is either undecidable (e.g., for subword or suffix, and some generalizations), or decidable with non-multiply-recursive complexity (e.g., for subsequence and its generalizations). These results are used to rule out many classes of graph logics that freely combine regular and rational relations, as well as to provide the simplest problem related to verifying lossy channel systems that has non-multiplyrecursive complexity. We then prove a dichotomy result for logics combining regular conditions on individual paths and rational relations on paths, by showing that the syntactic form of formulae classifies them into either efficiently checkable or undecidable cases. We also give examples of rational relations for which such logics are decidable even without syntactic restrictions.

I. INTRODUCTION

The motivation for the problems investigated in this paper comes from the study of logics for querying graphs. Such logics form the basis of query languages for graph databases, that have recently found numerous applications in areas including biological networks, social networks, Semantic Web, crime detection, etc. (see [START_REF] Angles | Survey of graph database models[END_REF] for a survey) and led to multiple systems and prototypes. In such applications, data is usually represented as a labeled graph. For instance, in social networks, people are nodes, and labeled edges represent different types of relationship between them; in RDF -the underlying data model of the Semantic Web -data is modeled as a graph, with RDF triples naturally representing labeled edges.

The questions that we address are related to the interaction of various classes of relations on words, for instance, rational relations (examples of those include subword and subsequence) or regular relations (such as prefix, or equality of words). An example of a question we are interested in is as follows: is it decidable whether a given a regular relation contains a pair (w, w ) so that w is a subword/subsequence of w ? Problems like this are very basic and deserve a study on their own right, but they are also necessary to answer questions on the power and complexity of querying graph databases. We now explain how they arise in that setting.

Logical languages for querying graph data have been developed since the late 1980s (and some of them became precursors of languages later used for XML). They query the topology of the graph, often leaving querying data that might be stored in the nodes to a standard database engine. Such logics are quite different in their nature and applications from another class of graph logics based on spatial calculi [START_REF] Cardelli | A spatial logic for querying graphs[END_REF], [START_REF] Dawar | Expressiveness and complexity of graph logic[END_REF]. Their formulae combine reachability patterns. The simplest form is known as regular path queries (RPQs) [START_REF] Cruz | A graphical query language supporting recursion[END_REF], [START_REF] Consens | GraphLog: a visual formalism for real life recursion[END_REF]; they check the existence of a path whose label belongs to a regular language. Those are typically used as atoms and then closed under conjunction and existential quantification, resulting in the class of conjunctive regular path queries (CRPQs), which have been the subject of much investigation [START_REF] Calvanese | Containment of conjunctive regular path queries with inverse[END_REF], [START_REF] Deutsch | Optimization properties for classes of conjunctive regular path queries[END_REF], [START_REF] Florescu | Query containment for conjunctive queries with regular expressions[END_REF]. For instance, a CRPQ may ask for nodes v so that there exist nodes v 1 and v 2 and paths from v to v i with the label in a regular language L i .

The expressiveness of these queries, however, became insufficient in applications such as the Semantic Web or biological networks due to their inability to compare paths. For instance, it is a common requirement in RDF languages to compare paths based on specific semantic associations [START_REF] Anyanwu | ρ-Queries: enabling querying for semantic associations on the semantic web[END_REF]; biological sequences often need to be compared for similarity, based, for example, on the edit distance.

To address this, an extension of CRPQs with relations on paths was proposed [START_REF] Barceló | Expressive languages for path queries over graph-structured data[END_REF]. It used regular relations on paths, i.e., relations given by synchronized automata [START_REF] Elgot | On relations defined by generalized finite automata[END_REF], [START_REF] Frougny | Synchronized rational relations of finite and infinite words[END_REF]. Equivalently, these are the relations definable in automatic structures on words [START_REF] Benedikt | Definable relations and first-order query languages over strings[END_REF], [START_REF] Blumensath | Automatic structures[END_REF], [START_REF] Bruyère | Logic and precognizable sets of integers[END_REF]. They include prefix, equality, equal length of words, or fixed edit distance between words. The extension of CRPQs with them, called ECRPQs, was shown to have acceptable complexity (NLOGSPACE with respect to data, PSPACE with respect to query). However, it was still short of the expressiveness needed in many applications. For instance, semantic associations between paths used in RDF applications often deal with subwords or subsequences, but these relations are not regular. They are rational: they are still accepted by automata, but those whose heads move asynchronously. Adding them to a query language must be done with extreme care: simply replacing regular relations with rational in the definition of ECRPQs makes query evaluation undecidable! So we set out to investigate the following problem: given a class of graph queries, e.g., CRPQs or ECRPQs, what happens if one adds the ability to test whether pairs of paths belong to a rational relation S, such as subword or subsequence? We start by observing that this problem is a generalization of the intersection problem: given a regular relation R, and a rational relation S, is R ∩ S = ∅? It is well known that there exist rational relations S for which it is undecidable [START_REF] Berstel | Transductions and Context-Free Languages[END_REF]; however, we are not interested in artificial relations obtained by encoding PCP instances, but rather in very concrete relations used in querying graph data.

The intersection problem captures the essence of graph logics ECRPQs and CRPQs (for the latter, when restricted to the class of recognizable relations [START_REF] Berstel | Transductions and Context-Free Languages[END_REF], [START_REF] Choffrut | Relations over words and logic: a chronology[END_REF]). In fact, query evaluation can be cast as the generalized intersection problem. Its input includes an m-ary regular relation R, a binary rational relation S, and a set I of pairs from {1, . . . , m}. It asks whether there is a tuple (w 1 , . . . , w m ) ∈ R so that (w i , w j ) ∈ S whenever (i, j) ∈ I. For m = 2 and I = {(1, 2)}, this is the usual intersection problem.

Another motivation for looking at these basic problems comes from verification of lossy channel systems (finite-state processes that communicate over unbounded, but lossy, FIFO channels). Their reachability problem is known to be decidable, although the complexity is not bounded by any multiplyrecursive function [START_REF] Chambart | The ordinal recursive complexity of lossy channel systems[END_REF]. In fact, a "canonical" problem used in reductions showing this enormous complexity [START_REF] Chambart | Post embedding problem is not primitive recursive, with applications to channel systems[END_REF], [START_REF] Chambart | The ordinal recursive complexity of lossy channel systems[END_REF] can be restated as follows: given a binary rational relation R, does it have a pair (w, w ) so that w is a subsequence of w ? This naturally leads to the question whether the same bounds hold for the simpler instance of the intersection problem when we use regular relations instead of rational ones. We actually show that this is true.

Summary of results: We start by showing that evaluating CRPQs and ECRPQs extended with a rational relation S can be cast as the generalized intersection problem for S with recognizable and regular relations respectively. Moreover, the complexity of the basic intersection problem is a lower bound for the complexity of query evaluation.

We then study the complexity of the intersection problem for fixed relations S. For recognizable relations, it is well known to be efficiently decidable for every rational S. For regular relations, we show that if S is the subword, or the suffix relation, then the problem is undecidable. That is, it is undecidable to check, given a binary regular relation R, whether it contains a pair (w, w ) so that w is a subword of w , or even a suffix of w . We also present a generalization of this result.

The analogous problem for the subsequence relation is known to be decidable, and, if the input is a rational relation R, then the complexity is non-multiply-recursive [START_REF] Chambart | Post embedding problem is not primitive recursive, with applications to channel systems[END_REF]. We extend this in two ways. First, we show that the lower bound remains true even for regular relations R. Second, we extend decidability to the class of all rational relations for which one projection is closed under subsequence (the subsequence relation itself is trivially such, obtained by closing the first projection of the equality relation).

In addition to establishing some basic facts about classes of relations on words, these results tell us about the infeasibility of adding rational relations to ECRPQs: in fact adding subword makes query evaluation undecidable, and while it remains decidable with subsequence, the complexity is prohibitively high.

So we then turn to the generalized intersection problem with recognizable relations, corresponding to the evaluation of CRPQs with an extra relation S. We show that the shape of the relation I holds the key to decidability. If its underlying undirected graph is acyclic, then the problem is decidable in PSPACE for every rational relation S (and for a fixed formula the complexity drops to NLOGSPACE). In the cyclic case, the problem is undecidable for some rational relation S.

For relations generalizing subsequence, we have decidability when I is a DAG, and for subsequence itself, as well as for suffix, query evaluation is decidable regardless of the shape of CRPQs.

Thus, under the mild syntactic restriction of acyclicity of comparisons with respect to rational relations, such relations can be added to the common class CRPQ of graph queries, without incurring a high complexity cost.

Organization: We give basic definitions in Section II and define the main problems we study in Section III. Section IV introduces graph logics and establishes their connection with the (generalized) intersection problem. Section V studies decidable and undecidable cases of the intersection problem. Section VI looks at the case of recognizable relations and CRPQs and establishes decidability results based on the intersection pattern. Complete proofs of all results are available in the full version of the paper.

II. PRELIMINARIES

Alphabets, languages, and morphisms: We shall use letters Σ, Γ to denote finite alphabets. The set of all finite words over an alphabet Σ is denoted by Σ * . We write ε for the empty word, w • w for the concatenation of two words, and |w| for the length of a word w.

If w = w • u • w , then
obtained by removing some letters (perhaps none) from w, i.e., w = a 1 . . . a n , and w = a i1 a i2 . . . a i k , where

1 ≤ i 1 < i 2 < . . . < i k ≤ n.
Recall that a monoid M = U, •, 1 has an associative binary operation • and a neutral element 1 satisfying 1x = x1 = x for all x (we often write xy for x • y). The set Σ * with the operation of concatenation and the neutral element ε forms a monoid Σ * , •, ε , the free monoid generated by Σ. A function f : M → M between two monoids is a morphism if it sends the neutral element of M to the neutral element of M , and if

f (xy) = f (x)f (y) for all x, y ∈ M . Every morphism f : Σ * , •, ε → M is uniquely determined by the values f (a), for a ∈ Σ, as f (a 1 . . . a n ) = f (a 1 ) • • • f (a n ). A morphism f : Σ * , •, ε → Γ * , •, ε is called alphabetic if f (a) ∈ Γ ∪ {ε}, and strictly alphabetic if f (a) ∈ Γ for each a ∈ Σ, see [5]. A language L is a subset of Σ * . It is recognizable if there is a finite monoid M , a morphism f : Σ * , •, ε → M , and a subset M 0 of M such that L = f -1 (M 0 ).
A language L is regular if there exists an NFA (nondeterministic finite automaton) A = Q, Σ, q 0 , δ, F such that L = L(A), the language of words accepted by A. We use the standard notation for NFAs, where Q is the set of states, q 0 is the initial state, F is the set of final states, and

δ ⊆ Q × Σ × Q is the transition relation.
A language is rational if it is denoted by a regular expression; such expressions are built from ∅, ε, and alphabet letters by using operations of concatenation (e•e ), union (e∪e ), and Kleene star (e * ). It is of course the classical result of formal language theory that the classes of recognizable, regular, and rational languages coincide.

Recognizable, regular, and rational relations: While the notions of recognizability, regularity, and rationality coincide over languages L ⊆ Σ * , they differ over relations over Σ, i.e., subsets of Σ * × . . . × Σ * . We now define those (see [START_REF] Berstel | Transductions and Context-Free Languages[END_REF], [START_REF] Carton | Decision problems among the main subfamilies of rational relations[END_REF], [START_REF] Choffrut | Relations over words and logic: a chronology[END_REF], [START_REF] Elgot | On relations defined by generalized finite automata[END_REF], [START_REF] Frougny | Synchronized rational relations of finite and infinite words[END_REF], [START_REF] Thomas | Infinite trees and automaton-definable relations over ωwords[END_REF]).

Since Σ * , •, ε is a monoid, the product (Σ * ) n has the structure of a monoid too. We can thus define recognizable n-ary relations over Σ as subsets R ⊆ (Σ * ) n so that there exists a finite monoid M and a morphism f : (Σ * ) n → M such that R = f -1 (M 0 ) for some M 0 ⊆ M . The class of n-ary recognizable relations will be denoted by REC n ; when n is clear or irrelevant, we write just REC.

It is well-known that a relation R ⊆ (Σ * ) n is in REC n iff it is a finite union of the sets of the form L 1 × . . . × L n , where each L i is a regular language over Σ, see [START_REF] Berstel | Transductions and Context-Free Languages[END_REF], [START_REF] Elgot | On relations defined by generalized finite automata[END_REF].

Next, we define the class of regular relations. Let ⊥ ∈ Σ be a new alphabet letter, and let Σ ⊥ be Σ ∪ {⊥}. Each tuple w = (w 1 , . . . , w n ) of words from Σ * can be viewed as a word over Σ n ⊥ as follows: pad words w i with ⊥ so that they all are of the same length, and use as the kth symbol of the new word the n-tuple of the kth symbols of the padded words. Formally, let

= max i |w i |. Then w 1 ⊗ . . . ⊗ w n is a word of length whose kth symbol is (a 1 , . . . , a n ) ∈ Σ n ⊥ such that a i = the kth letter of w i if |w i | ≥ k ⊥ otherwise.
We shall also write ⊗ w for w 1 ⊗ . . . ⊗ w n . A relation R ⊆ (Σ * ) n is called a regular n-ary relation over Σ if there is a finite automaton A over Σ n ⊥ that accepts {⊗ w | w ∈ R}. The class of n-ary regular relations is denoted by REG n ; as before, we write REG when n is clear or irrelevant.

Finally, we define rational relations. There are two equivalent ways of doing it. One uses regular expressions, which are now built from tuples ā ∈ (Σ ∪ {ε}) n using the same operations of union, concatenation, and Kleene star. Binary relations suff , , and are all rational: the expression

a∈Σ (ε, a) * • a∈Σ (a, a) * defines suff , the expression a∈Σ (ε, a) * • a∈Σ (a, a) * • a∈Σ (ε, a) * defines ,
and the expression a∈Σ (ε, a) ∪ (a, a) * defines .

Alternatively, n-ary rational relations can be defined by means of n-tape automata, that have n heads for the tapes and one additional control; at every step, based on the state and the letters it is reading, the automaton can enter a new state and move some (but not necessarily all) tape heads. The classes of n-ary relations so defined are called rational n-ary relations; we use the notation RAT n or just RAT, as before.

Relationships between classes of relations: While it very well known that

REC 1 = REG 1 = RAT 1 , we have strict inclusions REC k REG k RAT k for every k > 1. For instance, pref ∈ REG 2 -REC 2 and suff ∈ RAT 2 -REG 2 .
The classes of recognizable and regular relations are closed under intersection; however the class of rational relations is not. In fact one can find R ∈ REG 2 and S ∈ RAT 2 so that R ∩ S ∈ RAT 2 . However, if R ∈ REC m and S ∈ RAT m , then R ∩ S ∈ RAT m .

Binary rational relations can be characterized as follows [START_REF] Berstel | Transductions and Context-Free Languages[END_REF], [START_REF] Nivat | Transduction des langages de Chomsky[END_REF]. A relation R ⊆ Σ * × Σ * is rational iff there is a finite alphabet Γ, a regular language L ⊆ Γ * and two alphabetic morphisms f, g : Γ * → Σ * such that R = {(f (w), g(w)) | w ∈ L}. If we require f and g to be strictly alphabetic morphisms, we get the class of length-preserving regular relations, i.e., R ∈ REG 2 so that (w, w ) ∈ R implies |w| = |w |. Regular binary relations are then finite unions of relations of the form

{(w • u, w ) | (w, w ) ∈ R, u ∈ L} and {(w, w • u) | (w, w ) ∈ R, u ∈ L},
where R ranges over length-preserving regular relations, and L over regular languages.

Properties of classes of relations: Since relations in REC and REG are given by NFAs, they inherit all the closure/decidability properties of regular languages. If R ∈ RAT, then each of its projections is a regular language, and can be effectively constructed (e.g., from the description of R as an n-tape automaton). Hence, the nonemptiness problem is decidable for rational relations. However, testing nonemptiness of the intersection of two rational relations is undecidable [START_REF] Berstel | Transductions and Context-Free Languages[END_REF]. Also, for R, R ∈ RAT, the following are undecidable: checking whether R ⊆ R or R = R , universality (R = Σ * × Σ * ), and checking whether R ∈ REG or R ∈ REC [START_REF] Berstel | Transductions and Context-Free Languages[END_REF], [START_REF] Carton | Decision problems among the main subfamilies of rational relations[END_REF], [START_REF] Lisovik | The identity problem for regular events over the direct product of free and cyclic semigroups[END_REF].

Remark: We defined recognizable, regular, and rational relations over the same alphabet, i.e., as subsets of (Σ * ) n . Of course it is possible to define them as subsets of Σ 1 ×. . .×Σ n , with the Σ i 's not necessarily distinct. Technically, there are no differences and all the results will continue to hold. Indeed, one can simply consider a new alphabet Σ as the disjoint union of Σ i 's, and enforce the condition that the ith projection only use the letters from Σ i (this is possible for all the classes of relations we consider). In fact, in the proofs we shall be using both types of relations.

III. GENERALIZED INTERSECTION PROBLEM

We now formalize the main technical problem we study. Let R be a class of relations over Σ, and S a class of binary relations over Σ. We use the notation The problem (REC ∩ S) ? = ∅ is decidable for every rational relation S, simply by constructing R ∩ S, which is a rational relation, and testing its nonemptiness. However, (REG∩S) ? = ∅ could already be undecidable (we shall give one particularly simple example later).

IV. GRAPH LOGICS AND THE GENERALIZED INTERSECTION PROBLEM

In this section we show how the (generalized) intersection problems provide us with upper and lower bounds on the complexity of evaluating a variety of logical queries over graphs. We start by recalling the basic classes of logics used in querying graph data, and show that extending them with rational relations allows us to cast the query evaluation problem as an instance of the generalized intersection problem. The key observations are that:

• the complexity of GENINT S (REC) and (REC ∩ S) ? = ∅ provide an upper and a lower bound for the complexity of evaluating CRPQ(S) queries; and

• for ECRPQ(S), these bounds are provided by the complexity of GENINT S (REG) and of (REG ∩ S) ? = ∅. The standard abstraction of graph databases [START_REF] Angles | Survey of graph database models[END_REF] is finite Σlabeled graphs G = V, E , where V is a finite set of nodes, or vertices, and

E ⊆ V × Σ × V is a set of labeled edges. A path ρ from v 0 to v m in G is a sequence of edges (v 0 , a 0 , v 1 ), (v 1 , a 1 , v 2 ), • • • , (v m-1 , a m-1 , v m ) from E, for some m ≥ 0.
The label of ρ, denoted by λ(ρ), is the word

a 0 • • • a m-1 ∈ Σ * .
The main building blocks for graph queries are regular path queries, or RPQs [START_REF] Cruz | A graphical query language supporting recursion[END_REF]; they are expressions of the form x L → y, where L is a regular language. We normally assume that L is represented by a regular expression or an NFA. Given a Σlabeled graph G = V, E , the answer to an RPQ above is the set of pairs of nodes (v, v ) such that there is a path ρ from v to v with λ(ρ) ∈ L.

Conjunctive RPQs, or CRPQs [START_REF] Calvanese | Containment of conjunctive regular path queries with inverse[END_REF], [START_REF] Calvanese | View-based query processing and constraint satisfaction[END_REF], [START_REF] Consens | GraphLog: a visual formalism for real life recursion[END_REF] are the closure of RPQs under conjunction and existential quantification. Formally, they are expressions of the form

ϕ(x) = ∃ȳ m i=1 (u i Li -→ u i ) (1)
where variables u i , u i s come from x, ȳ. The semantics naturally extends the semantics of RPQs: ϕ(ā) is true in G iff there is a tuple b of nodes such that for every i ≤ m and every v i , v i interpreting u i and u i , respectively, we have a path ρ i between v i and v i whose label λ(ρ i ) is in L i . CRPQs can further be extended to compare paths. For that, we need to name path variables, and choose a class of allowed relations on paths. The simplest such extension is the class of CRPQ(S) queries, where S is a binary relation over Σ * . Its formulae are of the form

ϕ(x) = ∃ȳ m i=1 (u i χi:Li -→ u i ) ∧ (i,j)∈I S(χ i , χ j ) (2)
where I ⊆ [m] 2 . We use variables χ 1 , . . . , χ m to denote paths; these are quantified existentially. That is, the semantics of G |= ϕ(ā) is that there is a tuple b of nodes and paths ρ k , for k ≤ m, between v k and v k (where, as before, v k , v k are elements of ā, b interpreting u k , u k ) such that (λ(ρ i ), λ(ρ j )) ∈ S whenever (i, j) ∈ I. For instance, the query ∃y, y (x

χ:Σ * a -→ y) ∧ (x χ :Σ * b -→ y ) ∧ χ χ
finds nodes v so that there are two paths starting from v, one ending with an a-edge, whose label is a subsequence of the other one, that ends with a b-edge.

The input to the query evaluation problem consists of a graph G, a tuple v of nodes, and a query ϕ(x); the question is whether G |= ϕ(v). This corresponds to the combined complexity of query evaluation. In the context of query evaluation, one is often interested in data complexity, when the typically small formula ϕ is fixed, and the input consists of the typically large graph (G, v). We now relate it to the complexity of GENINT S (REC).

Lemma IV.1. Fix a CRPQ(S) query ϕ as in [START_REF] Anyanwu | ρ-Queries: enabling querying for semantic associations on the semantic web[END_REF]. Then there is a DLOGSPACE algorithm that, given a graph G and a tuple v of nodes, constructs an m-ary relation R ∈ REC so that the answer to the generalized intersection problem (R ∩ I S)

? = ∅ is 'yes' iff G |= ϕ(v).
Proof idea. Given a Σ-labeled graph G = V, E and two nodes v, v , we write A(G, v, v ) for G viewed as an NFA with the initial state v and the final state v . Now consider a CRPQ(S) query ϕ(x) given by ( 2). Let v be a tuple of nodes of G, of the same length as x.

The algorithm first enumerates all tuples b of nodes of G of the same length as ȳ. Let n i and n i be the interpretations of u i and u i , when x is interpreted as v and ȳ as b. Define

Rb = m i=1 (L(A(G, n i , n i )) ∩ L i ); this is a relation in REC m . Hence, R = b Rb in REC m too. It is now easy to see that R ∩ I S = ∅ iff G |= ϕ(v). 2
Conversely, the intersection problem for recognizable relations and S can be encoded as answering CRPQ(S) queries.

Lemma IV.2. For each binary relation S, there is a CRPQ(S) query ϕ(x, x ) and a DLOGSPACE algorithm that, given a relation R ∈ REC 2 , constructs a graph G and two nodes v, v so that

G |= ϕ(v, v ) iff R ∩ S = ∅. Proof idea. Let R ∈ REC 2 be given as n i=1 (L i × K i )
, where the L i , K i ⊆ Σ * are regular languages for every i. Let V i , E i be the underlying graph of the NFA defining L i , such that v i 0 is the initial state, and F i is the set of final states. Likewise we define W i , H i , nodes w i 0 and sets C i ⊆ W i for NFA defining K i .

We now construct the graph G. Its labeling alphabet is the union of Σ and {#, $, !}. Its set of vertices is the disjoint union of all the V i s, W i s, as well as two distinguished nodes start and end. Its edges include all the edges from E i s and H i s, and the following:

• #-labeled edges from start to each initial state, i.e., to each v 0 i and w 0 i for all i ≤ n. • $-labeled edges between the initial states of automata with the same index, i.e., edges (v i 0 , $, w i 0 ) for all i ≤ n. • !-labeled edges from final states to end, i.e., edges (v, !, end), where v ∈ i≤n F i ∪ i≤n C i . The CRPQ(S) query ϕ(x, y) is given below; it omits path variables for paths that are not used in comparisons:

∃x 1 , x 2 , z 1 , z 2       x # → x 1 ∧ x # → x 2 ∧ x 1 χ:Σ * → z 1 ∧ x 2 χ :Σ * → z 2 ∧ z 1 ! → y ∧ z 2 ! → y ∧ x 1 $ → x 2 ∧ S(χ, χ )       It is routine to verify that G |= ϕ(start, end) iff R ∩ S = ∅. 2
Combining the lemmas, we obtain:

Theorem IV.3. Let K be a complexity class closed under DLOGSPACE reductions. Then: 1) If the problem GENINT S (REC) is in K, then data complexity of CRPQ(S) queries is in K; and

2) If the problem (REC ∩ S)

?
= ∅ is hard for K, then so is data complexity of CRPQ(S) queries.

We now consider extended CRPQs, or ECRPQs, which enhance CRPQs with regular relations [START_REF] Barceló | Expressive languages for path queries over graph-structured data[END_REF], and prove a similar result for them, with the role of REC now played by REG. Formally, ECRPQs are expressions of the form

ϕ(x) = ∃ȳ m i=1 (u i χi:Li -→ u i ) ∧ k j=1 R j ( χj ) (3)
where each R j is a relation from REG, and χj a tuple from χ 1 , . . . , χ m of the same arity as R j . The semantics of course extends the semantics of CRPQs: the witnessing paths ρ 1 , . . . , ρ m should also satisfy the condition that for every atom R(ρ i1 , . . . , ρ i l ) in (3), the tuple (λ(ρ i1 ), . . . , λ(ρ i l )) is in R.

Finally, we obtain ECRPQ(S) queries by adding comparisons with respect to a relation S ∈ RAT, getting a class of queries ϕ(x) of the form

∃ȳ m i=1 (u i χi:Li -→ u i ) ∧ k j=1 R j ( χj ) ∧ (i,j)∈I S(χ i , χ j ) (4)
Exact analogs of Lemmas IV.1 and IV.2 hold, with ECRPQs replacing CRPQs and REG replacing REC. Hence, we get: Theorem IV.4. Let K be a complexity class closed under DLOGSPACE reductions. Then:

1) If the problem GENINT S (REG) is in K, then data complexity of ECRPQ(S) queries is in K; and 2) If the problem (REG ∩ S) ? = ∅ is hard for K, then so is data complexity of ECRPQ(S) queries. Thus, our next goal is to understand the behaviors of the generalized intersection problem for various rational relations S which are of interest in graph logics; those include subword, suffix, subsequence. In fact to rule out many undecidable or infeasible cases it is often sufficient to analyze the intersection problem. We do this in the next section, and then analyze the decidable cases to come up with graph logics that can be extended with rational relations.

V. THE INTERSECTION PROBLEM: DECIDABLE AND UNDECIDABLE CASES

We now study the problem (REG ∩ S) ? = ∅ for binary rational relations S such as subword and subsequence, and for classes of relations generalizing them. The input is a binary regular relation R over Σ, given by an NFA over Σ ⊥ ×Σ ⊥ . The question is whether R ∩ S = ∅. We also derive results about the complexity of ECRPQ(S) queries. For all lower-bound results in this section, we assume that the alphabet contains at least two symbols.

As already mentioned, there exist rational relations S such that (REG∩S) ? = ∅ is undecidable. However, we are interested in relations that are useful in graph querying, and that are among the most commonly used rational relations, and for them the status of the problem was unknown.

Note that the problem (REC ∩ S) ? = ∅ is tractable: given R ∈ REC, the relation R ∩ S is rational, can be efficiently constructed, and checked for nonemptiness.

A. Undecidable cases: subword and relatives

We now show that even for such simple relations as subword and suffix, the intersection problem is undecidable. That is, given an NFA over Σ ⊥ ×Σ ⊥ defining a regular relation R, the problem of checking for the existence of a pair (w, w ) ∈ R with w suff w or w w is undecidable. As an immediate consequence of this, we obtain: Corollary V.2. The query evaluation problem for ECRPQ( suff ) and ECRPQ( ) is undecidable.

Thus, some of the most commonly used rational relations cannot be added to ECRPQs without imposing further restrictions.

Proof idea. We sketch the idea of the proof for suff . We encode nonemptiness for linearly bounded automata (LBA). The alphabet Σ is the disjoint union of the tape alphabet of the LBA, its states, and the designated symbol $. Each configuration C with the tape content a 0 . . . a n , where a 0 and a n are the left and right markers, the state is q, and the head points at a i is encoded as a word w C = $a 0 . . . a i-1 qa i . . . a n $. Note that the relation {(w C , w C ) | C is an immediate successor of C} is regular and hence so is the relation R = {(w C0 w C1 . . . w Cm , w C 1 . . . w C m ) | C i+1 is an immediate successor of C i for i < m}, since all configuration encodings are of the same length. In fact, taking product with a regular language, we can also assume that R enforces C 0 to be an initial configuration, and C m to be a final configuration. If R ∩ suff is nonempty, it contains a pair (w C0 w C1 . . . w Cm , w C1 . . . w Cm ) such that C i+1 is an immediate successor of C i for all i < m, i.e., iff there is an accepting computation of the LBA. This proves undecidability. The proof for is very similar.

2

Note that the relation R constructed in the proof is definable in first-order logic, so the intersection problem for suffix and subword is undecidable even if the input relation comes from the class of star-free regular relations.

The essence of the undecidability result is that relations such as suff and can be decomposed in a way that one of the components of the decomposition is a graph of a nontrivial strictly alphabetic morphism. More precisely, let R • R be the binary relation

{(w•w , u•u ) | (w, u) ∈ R and (w , u ) ∈ R }. Let Graph(f ) be the graph of a function f : Σ * → Σ * , i.e., {(w, f (w)) | w ∈ Σ * }.
Proposition V.3. Let R 0 , R 1 be binary relations on Σ such that R 0 is recognizable and its second projection is Σ * . Let f be a strictly alphabetic morphism that is not constant. Then,

for S = R 0 • Graph(f ) • R 1 , the problem (REG ∩ S) ? = ∅ is undecidable.
Note that both suff and are of the required shape: suffix is ({ε} × Σ * ) • Graph(id) • ({ε} × {ε}), and subword is ({ε} × Σ * ) • Graph(id) • ({ε} × Σ * ), where id is the identity alphabetic morphism.

B. Decidable cases: subsequence and relatives

We now show that the intersection problem is decidable for the subsequence relation and, much more generally, for a class of relations that do not, like the relations considered in the previous section, have a "rigid" part. More precisely, for relations one of whose projections is closed under taking subsequences, we also retain decidability. However, the complexity bounds are extremely high. In fact we show that the complexity of checking whether (R ∩ ) = ∅, when R ranges over REG 2 , is not bounded by any multiply-recursive function. This was previously known for R ranging over RAT 2 , and was viewed as the simplest problem with non-multiply-recursive complexity [START_REF] Chambart | Post embedding problem is not primitive recursive, with applications to channel systems[END_REF]. We now push it further and show that this high complexity is already achieved with regular relations. Some of the ideas for showing this come from a decidable relaxation of the Post Correspondence Problem (PCP), namely the regular Post Embedding Problem, or PEP reg , introduced in [START_REF] Chambart | Post embedding problem is not primitive recursive, with applications to channel systems[END_REF], and shown to be in the level F ω ω of the fast-growing hierarchy of recursive functions [START_REF] Löb | Hierarchies of number theoretic functions[END_REF], [START_REF] Rose | Subrecursion: Functions and Hierarchies[END_REF]. The input to the problem consists of two morphisms f, g : Σ * → Γ * and a regular language L ⊆ Σ * ; it asks whether there is some w ∈ L such that f (w) g(w) (recall that in the case of the PCP the question is whether f (w) = g(w) with L = Σ + ). This problem is known to be decidable, and as hard as the reachability problem for lossy channel systems [START_REF] Chambart | Post embedding problem is not primitive recursive, with applications to channel systems[END_REF] which cannot be bounded by any primitive-recursive function -in fact, by any multiple-recursive function [START_REF] Rose | Subrecursion: Functions and Hierarchies[END_REF].

The problem PEP reg is just a reformulation of the problem (RAT ∩ ) ? = ∅. Indeed, relations of the form {(f (w), g(w)) | w ∈ L}, where L ⊆ Σ * ranges over regular languages and f, g over morphisms Σ * → Γ * are precisely the relations in RAT 2 [START_REF] Berstel | Transductions and Context-Free Languages[END_REF], [START_REF] Nivat | Transduction des langages de Chomsky[END_REF]). Hence, (RAT ∩ ) ? = ∅ is decidable, with non-multiply-recursive complexity. We show that the lower bound already applies to regular relations.

Theorem V.4. The problem (REG ∩ ) ? = ∅ is decidable, and its complexity is not bounded by any multiply-recursive function.

Proof idea. As already mentioned, decidability follows from [START_REF] Chambart | Post embedding problem is not primitive recursive, with applications to channel systems[END_REF]. To prove the lower bound, we first show that the existence of a solution to PEP reg is equivalent to the existence of a special solution, which we call a strict codirect solution. 1A word w = a 1 • • • a m ∈ Σ * is a strict codirect solution if f (a

  [m] for {1, . . . , m}. The generalized intersection problem (R ∩ I S) ? = ∅ is defined as: PROBLEM: (R ∩ I S) ? = ∅ INPUT: an m-ary relation R ∈ R, a relation S ∈ S, and I ⊆ [m] 2 QUESTION: is there w = (w 1 , . . . , w m ) ∈ Rso that (w i , w j ) ∈ S for all (i, j) ∈ I?If S = {S}, we write S instead of {S}. We write GENINT S (R) for the class of all problems (R ∩ I S) ? = ∅ where S is fixed, i.e., the input consists of R ∈ R and I. As was explained in the introduction, this problem captures the essence of evaluating queries in various graph logics, e.g., CRPQs or ECRPQs extended with rational relations S. The classes R will typically be REC and REG.If m = 2 and I = {(1, 2)}, the generalized intersection problem becomes simply the intersection problem for the classes R and S of binary relations: and S ∈ S QUESTION: is R ∩ S = ∅?

Theorem V. 1 .

 1 The problems (REG ∩ suff ) ? = ∅ and (REG ∩ ) ? = ∅ are undecidable.

  [START_REF] Angles | Survey of graph database models[END_REF]

  • • • a m ) g(a 1 • • • a m ) and for every i < m, f (a 1 • • • a i ) g(a 1 • • • a i ).We then show how to code decidable, non-multiply-recursive decidable, non-multiply-recursive[START_REF] Chambart | Post embedding problem is not primitive recursive, with applications to channel systems[END_REF] (R ∩ I ) Complexity of the intersection and generalized intersection problems, and combined complexity of graph queries for subword ( ), suffix ( suff ), and subsequence ( ) relations

						R ∈ REC	R ∈ REG	R ∈ RAT
	(R ∩ )	? = ∅	undecidable	undecidable
	(R ∩ suff )	? = ∅	PTIME (cf. [5])	undecidable	undecidable
	(R ∩ )
			? = ∅	?	undecidable
	(R ∩ I suff )	? = ∅	NEXPTIME	undecidable	undecidable
	(R ∩ I )	? = ∅	NEXPTIME	decidable, non-multiply-recursive
						S =	S = suff	S =	S arbitrary in RAT
	ECRPQ(S)	decidable, non-multiply-recursive undecidable undecidable	undecidable
	CRPQ(S)	NEXPTIME	NEXPTIME	?	undecidable
	acyclic CRPQ(S)	PSPACE	PSPACE	PSPACE	PSPACE
	Fig. 1.

?

= ∅

• u is a subword of w (also called factor in the literature, written as u w), • w is a prefix of w (written as w pref w), and • w is a suffix of w (written as w suff w). We say that w is a subsequence of w (also called subword embedding in the literature, written as w w) if w is

This is a slightly more restrictive definition than the codirect solutions used for the decidability of PEP reg in[START_REF] Chambart | Post embedding problem is not primitive recursive, with applications to channel systems[END_REF], which is essential to make possible our reduction from the (REG ∩ ) ? = ∅ problem.

Acknowledgments: We thank Sylvain Schmitz for helpful comments and suggestions. Partial support provided by Fondecyt grant 1110171, EPSRC grant G049165, and FET-Open Project FoX, grant agreement 233599. Part of this work was done when the first author visited Edinburgh, and the third author visited Santiago.

the existence of a strict codirect solution as an instance of (REG ∩ ) ? = ∅. Given a rational relation R ⊆ Σ * × Γ * we convert it into a length-preserving regular relation R ⊆ Σ * ⊥ × Γ * ⊥ so that R is the set of elements of R projected onto Σ * × Γ * , and if (q, (a, b), q ) is a transition of the NFA accepting R so is (q, (⊥, ⊥), q ). If we now let R to be the regular relation R • {( , v) | v ∈ {⊥} * }, we obtain that:

then w ∈ R ∩ , where w is the projection of w onto Σ * × Γ * ; and (ii) for any w ∈ R ∩ there is some strict codirect solution w ∈ R ∩ such that w is the projection of w onto Σ * × Γ * .

Thus the theorem follows.

Whereas (i) is trivial, (ii) follows from the fact that w is a strict codirect solution. If w = (u, v) ∈ R , where f (w) = (u) Γ , g(w) = (v) Γ , the complication is now that, since u ∈ Σ ⊥ , it could be that u v just because there is some ⊥ in u that does not appear in v. But we build (u, v) such that whenever u[i] = ⊥ forces v[j] = ⊥ with j > i then we also have that u[j] = ⊥. This repeats, forcing v[k] = ⊥ for some k > j and so on, until we reach the tail of v that has sufficiently many ⊥'s to satisfy all the accumulated demands for occurrences of ⊥.

2

Note that one cannot solve the problem (REG ∩ ) ? = ∅ by reducing to nonemptiness of rational relations due to the following. Proposition V.5. There is a binary regular relation R such that (R ∩ ) is not rational.

The next question is how far we can extend the decidability of (RAT ∩ ) ? = ∅. It turns out that if we allow one projection of a rational relation to be closed under taking subsequences, then we retain decidability.

Let R ⊆ Σ * ×Σ * be a binary relation. Define another binary relation

Then the class of subsequence-closed relations, or SCR, is the class {R | R ∈ RAT}. Note that the subsequence relation itself is in SCR, since it is obtained by closing the (regular) equality relation under subsequence. That is, = {(w, w) | w ∈ Σ * } . Not all rational relations are subsequence-closed (for instance, subword is not).

The following summarizes properties of subsequence-closed relations.

Proposition V.6.

When an SCR relation is given as an input to a problem, we assume that it is represented as an NFA in item 3 in the above proposition.

Note also that (SCR ∩ SCR)

for some w, and hence the problem reduces to simple NFA nonemptiness checking.

The main result about SCR relations generalizes decidability of (RAT ∩ )

Theorem V.7. The problem (RAT ∩ SCR)

Of course the complexity is non-multiply-recursive, since this subsumes (REG ∩ )

Proof idea. Decidability is shown by reduction to a problem where solutions have a specific shape. Given a rational binary relation R 0 and a subsequence-closed relation R 1 defined by two automata A 0 and A 1 over Σ ⊥ ×Σ ⊥ , we say that (w 0 , w 1 )

where w Σ denotes projection of w onto Σ. We say that (w 0 , w 1 ) is a synchronized solution if it further satisfies v 0 = v 1 .

The problem of finding a solution reduces to that of finding a synchronized solution. Indeed, consider the automata A 0 , A 1 as the result of adding all transitions (q, (⊥, ⊥), q) for every possible state q to both automata. It is clear that the relations recognized by these automata remain unchanged, and that A 0 is still a SCR automaton. It is easy to verify that there is a synchronized solution for (A 0 , A 1 ) if, and only if, there is a solution for (A 0 , A 1 ).

The problem of finding a synchronized solution for A 0 , A 1 can be then formulated as the problem of finding words v, u 0 , u

It corresponds to the rational automaton of the projection onto the first and second components of the ternary relation of A, and it can be computed from A in polynomial time. We then deduce that there exists

, and (u 0 ) Σ = (u 1 ) Σ ).

We have thus reduced the problem to (RAT ∩ ) ? = ∅, which is decidable [START_REF] Chambart | Post embedding problem is not primitive recursive, with applications to channel systems[END_REF], as already mentioned.

2

Coming back to graph logics, we obtain:

Corollary V.8. The complexity of evaluation of ECRPQ( ) queries is not bounded by a multiply-recursive function.

Another corollary can be stated in purely language-theoretic terms.

Corollary V.9. Let C be a class of binary relations on Σ * that is closed under intersection and contains REG. Then the nonemptiness problem for C is:

Discussion: In addition to answering some basic language-theoretic questions about the interaction of regular and rational relations, and to providing the simplest yet problem with non-multiply-recursive complexity, our results also ruled out logical languages for graph databases that freely combine regular relations and some of the most commonly used rational relations, such as subword and subsequence. With them, query evaluation becomes either undecidable or non-multiply-recursive (which means that no realistic algorithm will be able to solve the hard instances of this problem).

This does not yet fully answer our questions about the evaluation of queries in graph logics. First, in the case of subsequence (or, more generally, SCR relations) we still do not know if query evaluation of ECRPQs with such relations is decidable (i.e., what happens with GENINT S (REG) for such relations S).

Even more importantly, we do not yet know what happens with the complexity of CRPQs (i.e., GENINT S (REC) for various relations S. These questions are answered in the next section.

VI. RESTRICTED LOGICS AND GENERALIZED INTERSECTION PROBLEM

The previous section already ruled out some graph logics with rational relations as either undecidable or decidable with extremely high complexity. This was done merely by analyzing the intersection problem for binary rational and regular relations. We now move to the study of the generalized intersection problem, and use it to analyze the complexity of graph logics in full generality. We first deal with the generalization of the decidable case (SCR relations), and then consider the problem GENINT S (REC), corresponding to CRPQs extended with relations S on paths.

A. Generalized intersection problem and subsequence

We know that (REG ∩ ) ? = ∅ is decidable, although not multiply-recursive. What about its generalized version? It turns out it remains decidable.

Theorem VI.1. The problem GENINT (REG) is decidable. That is, there is an algorithm that decides, for a given m-ary regular relation R and

For checking decidability we explore the solution space tree as in the proof of Theorem V.7. However, this time the notion of saturation is different, since we need to consider a different condition for each component of the m-ary relation. The finiteness of the computed tree follows from Higman's Lemma this time in combination with Dickson's Lemma [START_REF] Dickson | Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors[END_REF].

Corollary VI.2. The query evaluation problem for ECRPQ( ) queries is decidable.

Of course the complexity is extremely high as we already know from Corollary V.8.

Note that while the intersection problem of with rational relations is decidable, as is GENINT (REG), we lose the decidability of GENINT (RAT) even in the simplest cases that go beyond the intersection problem (that is, for ternary relations in RAT and any I that does not force two words to be the same).

Proposition VI.3. The problem (RAT ∩ I ) ? = ∅ is undecidable even over ternary relations when I is one of the following:

B. Generalized intersection problem for recognizable relations

We now consider the problem of answering CRPQs with rational relations S, or, equivalently, the problem GENINT S (REC). Recall that an instance of such a problem consists of an m-ary recognizable relation R and a set I ⊆ [m] 2 . The question is whether R ∩ I S = ∅, i.e., whether there exists a tuple (w 1 , . . . , w m ) ∈ R so that (w i , w j ) ∈ S whenever (i, j) ∈ I. It turns out that the decidability of this problem hinges on the graph-theoretic properties of I. In fact we shall present a dichotomy result, classifying problems GENINT S (REC) into PSPACE-complete and undecidable depending on the structure of I.

Before stating the result, we need to decide how to represent a recognizable relation R. Recall that an m-ary R ∈ REC is a union of relations of the form L 1 × . . . × L m , where each L i is a regular language. Hence, as the representation of R we take the set of all such L i s involved, and as the measure of its complexity, the total size of NFAs defining the L i s.

With a set I ⊆ [m] 2 we associate an undirected graph G I whose nodes are 1, . . . , m and whose edges are {i, j} such that either (i, j) ∈ I or (j, i) ∈ I. We call an instance of (REC ∩ I S) ? = ∅ acyclic if G I is an acyclic graph. Now we can state the dichotomy result.

Theorem VI.4.

• Let S be a binary rational relation. Then acyclic instances of GENINT S (REC) are decidable in PSPACE. Moreover, there is a fixed binary relation S 0 such that the problem (REC ∩ I S 0 ) ? = ∅ is PSPACE-complete. • For every I such that G I is not acyclic, there exists a binary rational relation S such that the problem (REC ∩ I S)

Proof idea. For PSPACE-hardness we can do an easy reduction from nonemptiness of NFA intersection. Given m NFAs A 1 , . . . , A m , define the (acyclic) relation

For the upper bound, we show how to construct, in exponential time, for each m-ary recognizable relation R, a binary rational relation S and an acyclic I ⊆ [m] 2 , an mary transducer A(R, S, I) that accepts precisely those w = (w 1 , . . . , w m ) ∈ (Σ * ) m such that w ∈ R and (w i , w j ) ∈ S, for each (i, j) ∈ I. Intuitively, A(R, S, I) represents the "synchronization" of the transducer that accepts R with a copy of the transducer that recognizes S over each projection defined by the pairs in I. Such synchronization is possible since I is acyclic. Hence, in order to solve GENINT S (REC) we only need to check A(R, S, I) for nonemptiness. The latter can be done in PSPACE by the standard "on-the-fly" reachability analysis.

2

C. CRPQs with rational relations

The acyclicity condition gives us a robust class of queries, with an easy syntactic definition, that can be extended with arbitrary rational relations. Recall that CRPQ(S) queries are those of the form

in Sec.IV. We call such a query acyclic if G I , the underlying undirected graph of I, is acyclic.

Theorem VI.5. The query evaluation problem for acyclic CRPQ(S) queries is decidable for every binary rational relation S. Its combined complexity is PSPACE-complete, and data complexity is NLOGSPACE-complete. Thus, we get not only the possibility of extending CRPQs with rational relations but also a good complexity of query evaluation. The NLOGSPACE-data complexity matches that of RPQs, CRPQs, and ECRPQs [START_REF] Consens | GraphLog: a visual formalism for real life recursion[END_REF], [START_REF] Cruz | A graphical query language supporting recursion[END_REF], [START_REF] Barceló | Expressive languages for path queries over graph-structured data[END_REF], and the combined complexity matches that of first-order logic, or ECRPQs without extra relations.

The next natural question is whether we can recover decidability for weaker syntactic conditions by putting restrictions on a class of relations S. The answer to this is positive if we consider directed acyclicity of I, rather than acyclicity of the underlying undirected graph of I. Then we get decidability for the class of SCR relations. In fact, we have a dichotomy similar to that of Theorem VI.4.

Theorem VI.6.

• Let S be a relation from SCR. Then (REC ∩ I S)

• There is a relation I with a directed cycle and S ∈ SCR such that (REC ∩ I S)

In particular, if we have a CRPQ(S) query [START_REF] Anyanwu | ρ-Queries: enabling querying for semantic associations on the semantic web[END_REF] where I is acyclic (as a directed graph) and S ∈ SCR, then query evaluation has NEXPTIME combined complexity.

The proof of this result is quite different from the upper bound proof of Theorem VI.4, since the set of witnesses for the generalized intersection problem is no longer guaranteed to be rational without the undirected acyclicity condition. Instead, here we establish the finite-model property, which implies the result.

Also, as a corollary to the proof of Theorem VI.6, we get the following result: Proposition VI.7. Let S ∈ SCR be a partial order. Then GENINT S (REC) is decidable in NEXPTIME.

Corollary VI.8. If S ∈ SCR is a partial order, then CRPQ(S) queries can be evaluated with NEXPTIME combined complexity. In particular, CRPQ( ) queries have NEXPTIME combined complexity.

The last question is whether these results can be extended to other relations considered here, such as subword and suffix. We do not know the result for subword (which appears to be hard), but we do have a matching complexity bound for the suffix relation.

Proposition VI.9. The problem GENINT suff (REC) is decidable in NEXPTIME. In particular, CRPQ( suff ) queries can be evaluated with NEXPTIME combined complexity.

VII. CONCLUSIONS

Motivated by problems arising in studying logics on graphs (as well as some verification problems), we studied the intersection problem for rational relations with recognizable and regular relations over words. We have looked at rational relations such as subword , suffix suff , and subsequence , which are often needed in graph querying tasks. The main results on the complexity of the intersection and generalized intersection problems, as well as the combined complexity of evaluating different classes of logical queries over graphs are summarized in Fig. 1. Several results generalizing those (e.g., to the class of SCR relations) were also shown. Two problems related to the interaction of the subword relation with recognizable relations remain open and appear to be hard.

From the practical point of view, as rational-relation comparisons are demanded by many applications of graph data, our results essentially say that such comparisons should not be used together with regular-relation comparisons, and that they need to form acyclic patterns (easily enforced syntactically) for efficient evaluation.

So far we dealt with the classical setting of graph data [START_REF] Angles | Survey of graph database models[END_REF], [START_REF] Calvanese | Containment of conjunctive regular path queries with inverse[END_REF], [START_REF] Calvanese | View-based query processing and constraint satisfaction[END_REF], [START_REF] Consens | GraphLog: a visual formalism for real life recursion[END_REF], [START_REF] Cruz | A graphical query language supporting recursion[END_REF] in which the model of data is that of a graph with labels from a finite alphabet. In both graph data and verification problems it is often necessary to deal with the extended case of infinite alphabets (say, with graphs holding data values describing its nodes), and languages that query both topology and data have been proposed recently [START_REF] Grumberg | Variable automata over infinite alphabets[END_REF], [START_REF] Libkin | Regular path queries on graphs with data[END_REF]. A natural question is to extend the positive results shown here to such a setting.


Dominique Lavenier
email: dominique.lavenier@irisa.fr

Liu Xinchun

Gilles Georges
email: gilles.georges@irisa.fr

Seed-based Genomic Sequence Comparison using a FPGA/FLASH Accelerator

This paper presents a parallel architecture for computing genomic sequence alignments using seed-based algorithms. Originality comes from the simultaneous use of FPGA components and FLASH memories. The FPGA technology brings the computer power while the FLASH memory provides high memory bandwidth able to feed a large array of specific operators. A 64 GBytes FLASH memory connected to a Xilinx Virtex-2 Pro PCI board has been developed and an array of 160 distancecomputation operators have been implemented to perform the first step of seed-based alignment algorithms. Compared to the BLAST reference software family, we measured a speed-up of 75 on a real intensive genomic sequence comparison application.

I. INTRODUCTION

For the last ten years, biotechnology improvements in the sequencing area led to generate an increasing amount of genomic data. More precisely, the size of the genomic databases are doubling every 16 months [START_REF] Benson | [END_REF]. This exponential growth provides a priceless source of knowledge which can be advantageously exploited by in-silico studies. Today, wet lab experimentations are systematically preceded by a deep analysis of recent data available in the public databases. Results obtained from these analyses limit the number of invivo experimentations, saving both time and money.

On the other hand, processing large volume of genomic data may require huge computational resources. Genomic sequence comparison programs are traditionally used for that purpose, particularly programs from the BLAST package [START_REF] Altschul | Basic Local Alignment Search Tool[END_REF]. Typically, a set of genomic sequences is compared to a specific database or an entire genome. The result is a list of alignments giving a measure of similarity between genomic sequences. Detecting similarities through alignments at the text level often gives clues for determining relationship about gene functionalities.

An alignment is expressed as follows:

ATTAGGACCAGGGGATATGA...GACCCAGGAATTTA.GGGA ||| |||| |||| ||||| ||||| || ||||| |||| ATTCGGAC.AGGGATTATGAGGAGACCCGGGGATTTAGGGGA
It is composed of two substrings. Their size may differ since gap errors (dot characters) can be inserted. A score is calculated according to the number of errors found (substitution or gap). It is linked to an expected value reflecting the biological significance of the alignment.

Many algorithms have been developed to compute alignments. The historical one is due to Wagner and Fisher [START_REF] Wagner | The String-to-String Correction Problem[END_REF] for simply calculating a distance between two strings of characters. It has been extended by Smith and Waterman [START_REF] Smith | Identification of common molecular subsequences[END_REF] to find the best local alignment between two biological sequences and, later on, improved by Gotoh [START_REF] Gotoh | An Improved Algorithm for Matching Biological Sequence[END_REF] to better reflect biological reality. All these algorithms use dynamic programming algorithms. Because of their high complexity, they are not suited for intensive comparisons. Since the end of the 80's, to face the genomic data explosion, seed-based heuristics have been proposed [START_REF] Pearson | Improved tools for biological sequence comparison[END_REF] [START_REF] Altschul | Basic Local Alignment Search Tool[END_REF]. They do not guarantee to find the best alignments but, in practice, they produce very satisfying results. The great advantage is that the computation time is drastically reduced.

The BLAST [START_REF] Altschul | Gapped BLAST and PSI-BLAST: a new generation of protein database search programs[END_REF] family programs belongs to this class of algorithms. This is today the most popular software both for scanning large databases and for comparing large genomic data sets. Even if this program is fast, handling genomic sequences of billions of nucleotides may take a very long time. Accelerating this kind of algorithm is still worthwhile.

Whereas many efforts have been done to implement dynamic programming algorithms on dedicated parallel architectures [START_REF] Grate | Sequence Analysis With the Kestrel SIMD Parallel Processor Pacific Symposium on Biocomputing[END_REF] [10] [11] [12], seed-based implementation mainly remains a software approach. Today, as far as we know, the only available commercial board accelerating the BLAST program family has been developed by TimeLogic Inc. through the DeCypher FPGA Engine [START_REF]TimeLogic Web Site[END_REF]. And it is not clear how BLAST is implemented. Academic research includes work on the Mercury system [START_REF] Krishnanurthy | Biosequence Similarity search on the Mercury system[END_REF] [3] and on the RDISK system [7] [8]. Both projects consider the database as a data stream and perform fast hardware filtering to select regions of interest for further processing. Another interesting idea (RC-BLAST) is based on an open source hardware implementation to only speed-up some critical parts of the BLAST software [START_REF] Muriki | RC-BLAST: Towards a Portable, Cost-Effective Open Source Hardware Implementation[END_REF]. Unfortunately, this direct approach doesn't provide significant speed-up, but gives good clues towards advanced hardware implementations.

The approach we propose here is new in the sense that we don't scan the database. Instead, the database is formatted as an index structure from which regions of interest can be directly accessed. The index is built using-BLAST similar seedbased heuristics. This mechanism provides a very efficient way to speed-up the first steps of the genomic sequence comparison algorithms as long as the index memory is able to sustain a fast data access and a high bandwidth. Unfortunately, the size of the database index can be very large (100 GBytes), which makes the use of a simple DRAM memory impossible. In this paper, we show how a large capacity FLASH memory tightly connected to FPGA resources can best implement the first steps of seed-based algorithms.

For the problem introduced above, a PCI-based system has been designed. It includes a 64 GBytes FLASH memory and a Virtex-2 Pro FPGA component. It has been successfully tested on a real and time-consuming application: the comparison of 400,000 proteins against the Human genome. We measured a speed-up of 75 compared to a stand alone 3 GHz PC running the TBLASTN program.

The rest of the paper is organized as follows. The next section presents one of the BLAST program family, TBLASTN, which is used as a reference for the process of comparing proteins versus DNA databases. Section 3 details the database index structure used in our hardware implementation. Section 4 describes the parallel architecture implemented on the reconfigurable resources. Section 5 deals with implementation and result issues. Section 6 concludes this paper.

II. TBLASTN ALGORITHM

The TBLASTN program belongs to the BLAST program family [START_REF] Altschul | Gapped BLAST and PSI-BLAST: a new generation of protein database search programs[END_REF]. It aims to find alignments between a query protein sequence and a nucleic database. The result is displayed as protein-based alignments, requiring first the database to be translated into protein sequences before the comparison process. The (simplified) TBLASTN algorithm can be described as follows: The first step consists in indexing the query protein sequence: for each 3-amino acid word (3-AA word), a list of positions is attached. The list gives the position (the index) of the words where they appear in the sequence. This data structure is called the query index. For example, suppose the following (small) protein sequence:

T P A T Y K L P E W G G E S 1 2 3 4 5 6 7 8 9 10 11 12 13 14 The index associated to this protein is:

A T Y 3 P A T 2 E W G 9 P E W 8 G E S 12 T P A 1 G G E 11 T Y K 4 K L P 6 W G G 10 L P E 7 Y K L 5
Once the query sequence is indexed, the next step is to translate all the DNA sequences of the database into the 6 possible potential proteins. Indeed, a DNA sequence can be translated starting from any nucleotides following either the direct or reverse DNA strand. As the genetic code translates an amino acid from a 3-uplet nucleotide (codons), there are 3 encoding possibilities by frame, leading to 6 possibilities if the direct and reverse strand are considered. Suppose the following DNA sequence is given:

ACGCAAGCTACCTATAAATTACCTGACTGGGGAGAGTCAACA

The reverse strand is given by: TGTTGACTCTCCCCAGTCAGGTAATTTATAGGTAGCTTGCGT The sequence is first inverted and the nucleotides are replaced following the (A ↔ T) and (C ↔ G) rules. The first ACG... characters become the last ...CGT characters. From these 2 strands, using the genetic code, we get the 6 following potential proteins:

ACGCAAGCTACCTATAAATTACCTGACTGGGGAGAGTCAACA 1 T Q A T Y K L P D W G E S T 2 R K L P I N Y L T G E S Q 3 A S Y L X I T X L G R V N TGTTGACTCTCCCCAGTCAGGTAATTTATAGGTAGCTTGCGT 4 C X L S P V R X F I G S L R 5 V D S P Q C G N L X V A C 6 L T L P S Q V I Y R X L A
At this point, protein-protein comparison can now be considered. Alignments are thus searched using seed-based protein heuristics. The hypothesis is that the two subsequences which compose an alignment share, at least, one identical 3-AA word. Thus, instead of considering all the possible alignments, we only focus on the alignments having this property. Practically, this technic finds most of the significant alignments while decreasing the computation time from 2 or 3 orders of magnitude as compared to exact methods such as dynamic programming methods.

The next step is to detect the 3-AA common words between the query sequence and the six translated sequences. This is rapidly performed using the query index computed at step 1. When a hit is found (that is two identical 3-AA words), an ungapped alignment is calculated by extending the comparison on its left and right hand side. This treatment doesn't consider gap error. A score is simply calculated by adding substitution Fig. 1. Structure of the index. All the 3-AA words of the sequences are grouped together. Then, each 3-AA word is associated with its position in the sequence and its neighboring environment. For example, the 3-AA word AAC is present at position 24, 38 and 49. This entry is thus linked to 3 amino acid substrings (TPAAACFGKL, YNPFAACTTRQ, YYYTAACGFPL) which will be used to start the computation of ungapped alignment.

costs between pairwise amino acids. Suppose that the KLP word is processed: it is present both in the query (at position 6) and in the frame #1 and #2 of the database. The 2 following hits can be set:

Query T P A T Y K L P E W G G E S | | | | | | | | | Frame #1 T Q A T Y K L P D W G E S T Query T P A T Y K L P E W G G E S | | | Frame #2 R K L P I N Y L T G E S Q
Clearly, the first hit position is better and lead to a higher score when an extension is made. The second one will be discarded. This ungapped alignment step can be seen as a filter step to select promising hits, that is, hits with a favorable environment likely to produce significant alignments. The selection is based on the score value: only extended hits with scores higher than a threshold value are transmitted to the final step.

The last step computes alignments with gap errors. The hit acts as an anchor from which the final alignment is found.

In our example we can still increase the length of the first ungapped alignment by adding one gap as follows:

Query T P A T Y K L P E W G G E S | | | | | | | | | | | Frame #1 T Q A T Y K L P D W G . E S T
The principle of the algorithm can be summarized as a 3 step procedure:

• step 1: find hits • step 2: extend hit (compute ungapped alignments) • step 3: process alignment (compute gap alignments) Previous studies have shown that most of the computation time is spent in steps 1 and 2. The following table, extracted from [START_REF] Krishnanurthy | Biosequence Similarity search on the Mercury system[END_REF], precisely indicates, for various query length, the percentage of time spent in stage 1, 2 and 3. Obviously, to get a significant speed up, both step 1 and 2 need to be accelerated. Before presenting how an hardware accelerator can handle these 2 steps, we first introduce a suitable data structure allowing fast data accesses and able to rapidly feed hardwire operators.

III. DATABASE INDEXING

In the context of intensive genomics computation, a large set of query proteins (let say N proteins) are compared to a DNA database. In this case, the database is processed N times. From a computational point of view, this approach is quite inefficient since the database need to be systematically retranslated into the 6 frames. Actually, the TBLASTN software has an optimizing parameter allowing the user to concatenate a few query protein sequences into a single one. Setting this optional parameter greatly improves the efficiency, but doesn't remove the need to periodically recomputing the 6 frames.

To avoid this drawback, the database can be permanently encoded as a 6 protein sequence set resulting from the 6-frame DNA translation. Consequently, compared to the BLAST approach, the whole process can be inverted: instead of indexing the N queries and reading N times the database, the database is fully indexed and the N queries are sequentially processed, word by word.

Furthermore, to optimize the database access, the index structure is enhanced with extra information: a 3-AA word is not only linked with a list of positions but also with neighboring knowledge. The goal is to be able to rapidly decide if a 3-AA hit has a favorable environment to start an alignment. Thus, each 3-AA word in the index is tied with a neighboring amino acid substring representing its environment (see figure 1). This information allow short ungapped alignments to be immediately computed, avoiding millions of random accesses to the database.

To illustrate the database index structure, consider again the DNA sequence of the previous example and its 6 frame translations. The KLP word of the database will be indexed as follows:

KLP --> ATY DWG #1 16 ** R INY #2 5
It is present in frame #1 at position 16 with a left neighboring environment ATY and a right neighboring environment DWG. It is also present in frame #2 at position 5 with a (**R,

INY) environment.
When a KLP word is found in the query sequence, all the KLP words of the database are immediately accessed together with their neighboring environment. The great advantage is that we only focus on the useful parts of the database. A systematic scan is no longer required.

On the other hand, the size of the index becomes very large: for all words of the six frames, in addition to their positions, two short substrings reflecting the neighboring amino acid environment need to be memorized. As an example, storing a 40 amino acid substring environment leads to a 150 GBytes index for the Human genome. This is 50 times more than the raw data. The database index structure is represented figure 1. Using this structure, and supposing that the database index already exists, the algorithm becomes: Compared to the TBLASTN algorithm, the finding-hit step is suppressed since statistically, when indexing a large database (such as a complete genome), all the possible 3 amino acid words exist and are associated to a list of positions. Thus, we can directly process the ungapped alignments from the list associated to every 3-AA words. Accelerating this algorithm means to focus on lines 3 to 6. The next section describes the hardware architecture to perform this calculation.

IV. ARCHITECTURE

The critical part of the algorithm is to compute a large number of ungapped alignments from two short amino acid subsequences. Let L be the length of the protein subsequences, Qry a subsequence from the query and Db a subsequence from the database. Computing the best score based on an ungapped alignment is done as follows: Hardwiring this operator is straightforward as depicted figure 2 (left). This is a serial operator which need L cycles (the length of the substrings) to compute a maximum score value. The substrings Qry and Db are supposed to be sent character by character, one every cycle. The substitution cost is memorized into a ROM memory directly addressed by the amino acids code. As there are 20 different amino acids, they are 5-bit encoded.

One query substring need to be compared with a large number of database substrings. These comparisons are independant and can be performed in parallel. If we suppose that K database substrings can be accessed together, a parallel architecture made of K ungapped operators can be simply implemented. Figure 2 (right) shows the interconnection of K operators.

The Qry substring is broadcasted to all the ungapped operators while K database substrings are connected to K different operators. The system is synchronous: all computation start at the same time, and after L cycles K new results are available. Extra hardware has been added for collecting the results: at the end of the L cycles, they are stored in a register and during the K next cycles they are sequentially shifted to the output. This shift mechanism works only when L (number of cycles to compute a score) is higher than K (the number of operators).

In that scheme, to reach a maximal efficiency, the number of operators depends on:

• the available bandwidth (B) between the database storage support and the reconfigurable resources;

• the clock frequency (F );

• the input data width (dw). Here amino acids are 5-bit encoded (dw=5). Consequently, the number of operators can be determined as the following ratio:

#operators = B dw × F (1)
Remember that the size of the index databases is important. It can range from 30 to 300 GBytes, or even more. This is an easy fit to today's disk capacity. However, limitations come from both the time for accessing the data (a few milliseconds) and the limited bandwidth. As an example, with a 50 Mo/sec bandwidth and a 40 MHz clock frequency, it is impossible to implement more than 2 operators.

Using Random Access Memory appears as an attractive alternative to sustain a higher bandwidth, but the complexity of managing hundreds of GBytes of DRAM, the power consumption and the volatility of the data, seriously compromise the use of this technology.

A better solution is FLASH memory technology. It is faster than magnetic storages in terms of data access and bandwidth, it has a low power consumption compared to DRAM and it permanently stores the data. Drawback are a much higher price (compared to disk), a slower data access (compared to DRAM) and a limited write cycles.

To investigate this approach, we have designed a 64 GBytes FLASH memory allowing both to store large database index and to support a bandwidth of 640 MB/sec. Using this memory, 25 ungapped operators can be fed simultaneously. Actually, this represents a small amount of reconfigurable resources available in the Xilinx XC2VP30 FPGA component. There are still resources available to fit many more operators.

In the context of comparing a large set of proteins against large DNA sequences (chromosomes), identical 3-AA words coming from the proteins can be gathered and processed simultaneously. Thus, a few parallel ungapped operators working on different data from the query proteins, but on the same data from the database can be advantageously implemented in order to fill the FPGA and to reach a higher efficiency. The resulting architecture is shown figure 3. This is an array of P × K ungapped operators. This array is steered by a controller whose task is to feed the array with query data and to collect the results from the ungapped operators. To reduce the output data flow, results from the ungapped operator are filtered: only the values higher than a threshold value are transmitted.

A basic treatment consists in comparing P query substrings having in common the same 3-AA hit word. The PowerPC processor available in the Virtex-II Pro component controls the treatment. It receives the P substrings from the PCI interface together with information to locate, in the FLASH memory, the 3-AA database word list. Then it runs the whole computation and transfers back the results to the PCI interface. The results which are returned correspond to the locations where significant ungapped hits have been found together with the ID of the matching query.

V. IMPLEMENTATION AND RESULTS

A. Platform

An array of 8 × 20 ungapped operators have been implemented and successfully tested. The platform is a commercial board from Avnet (ADS-XLX-V2PRO-DEVP30). It includes a Xilinx Virtex-2 Pro (XC2VP30), 128 MBytes of DDR SDRAM, a PCI bridge and 4 connectors to plug daughter boards.

In addition, we have developed a FLASH memory board of 64 GBytes which can be connected to the Avnet board. 64 1-GB NAND-FLASH chips are interconnected into 4 independent 16 GB banks. Each bank has its own controller implemented into specific Xilinx Spartan-3 FPGA (see figure 4). The maximal bandwidth is 640 MB/sec: each bank is able to deliver a 32-bit data every 25 ns.

NAND-FLASH memory cannot be used efficiently as pure random access memory. To be efficient, data need to be read by pages. In our case, this is not a major problem since we have to read a list of 3-AA word environments which may represent a few consecutive pages. However, access times need to be considered. Typically, it takes about 20 µsec to get a block of data before being able to process it. This latency may highly penalize performance by including idle period each time a new block of data is accessed. The FLASH controllers we designed have integrated advanced mechanisms for anticipating the read of new blocks: while data from a page are output, a new page can be concurrently accessed. This overlap mechanism allows high bandwidth to be sustained if the data access can be predicted. Once again, in our case, the algorithm fits to these requirements: all the data accesses (i.e. all the lists of all 3-AA words of the query) can be progressively forecasted as the query input is processed. Sending periodically a list of reading commands to the FLASH controller reduces significantly the access time overhead. In the best case, we only pay the first page access, the other ones are free.

B. Application

The FPGA/FLASH architecture have been tested on a real, intensive comparison genomic application. The scope of this paper is not to precisely describe the biological context, but to give an idea of the volume of data to process at an initial stage of a large scale genomic project. The study aims to detect new mitochondrial proteins in the Human genome. As mitochondria may originate from ancestral bacteria, a systematic comparison with the proteome of all available bacteria is done. From a computational point of view, about 400 000 proteins have to be compared with all the chromosomes of the Human genome.

Usually, the TBLASTN program is used. Experiments have shown that performing this computation on a 3 GHz processor will require about 20 000 hours (or 27 months) of computation. With a 64-node cluster, supposing no communication overhead, it will approximately take 13 days.

A program similar to TBLASTN has been developed for integrating the hardware version of step 1 and 2 in our FPGA/FLASH architecture. As the FLASH memory cannot hold the full index of the Human genome, we process each chromosome sequentially. The size of the largest Human chromosome is 246 × 10 6 nt, leading to an index of nearly 12 GBytes. This easily fit into the FLASH memory. Hence, the whole process is done as follows:

for each chromosome:

-download chromosome index into FLASH -process 400,000 proteins

C. Performances

The complete computation has been performed in approximately 260 hours (11 days). It includes the time for downloading new data into the FLASH memory, but not the time for calculating the index of each chromosomes. We consider that this operation need to be done once and that the resulting data index structure can be re-used for many other applications, as it is done for the BLAST family programs.

This experiment shows that connecting a PCI reconfigurable board enhanced with large FLASH memory into a standard PC can highly reduce the computation time of seed-based algorithms for intensive genomic comparison applications. We get, here, a speed-up of 75. Another way to compare performances is to say that the computer power of this architecture is nearly equivalent to a 64-node cluster.

However, these performances need to be relativized considering the cost of the accelerator. Today (mid 2006), the price of a 2-GB NAND-FLASH component is around $40. A Virtex-2 Pro FPGA equipped with 64 GB of FLASH memory can easily fit into a single PCI board. The price of such a board would not exceed the price of the host station. In other word, with the same amount of money, the FPGA/FLASH alternative provide a substantial speed-up for this class of algorithms.

In order to compare the computational power of this FPGA architecture with other FPGA solutions we introduce a measurement unit: the number of Kilo Amino Acids (Kaa) compared to the number of Mega nucleotids (Mnt) performed every second. On the above application, we get: Performance comparison of the DeCypher Engine and the FPGA/FLASH architecture. A database, composed of 192 bacterial genomes, is compared against set of proteins. For small sets, the DeCypher Engine is better as it is not penalized by the FLASH memory initialization. For large set, the FLASH/FPGA architecture is approximatively 2.5 times faster.

A comparison can be done with the Tera-T-BLASTN implementation on the FPGA Timelogic DeCypher Engine. The accelerator has been benchmarked for searching 4289 proteins from the E. Coli bacteria against 192 bacterial genomes (775× 10 6 symbols) 1 . It took 1 hours and 36 minutes to perform the computation. From this benchmark, we can calculate the architecture performance:

1358Kaa × 775M nt 5760sec = 182KaaM nt/sec
It appears that the FPGA/FLASH architecture has a higher raw performance ratio. Actually, this unit doesn't exactly reflect the features of both architectures. The FPGA/FLASH architecture is handicaped by the initialization of the FLASH memory. Figure 5 show the comparison of an increasing set of proteins against the 192 bacterial genomes. It can be seen that for small set of query proteins, the DeCyper Engine is better, even if this performance ratio is lower than the FPGA/FLASH one. This is mainly due to the time for downloading, at the begining of the computation, the index of the 192 bacterial genomes. But, as the set of the query proteins becomes larger, this penalty tends to disappear.

VI. CONCLUSION

In this paper, we have presented a new way of accelrating seed-based search algorithms in the context of intensive genomic sequence comparison. Our approach relies on:

• an index database structure built from seed-based heuristics;

• a large FLASH memory tightly connected to FPGA resources;

• a parallel architecture implementing an array of 160 simple ungapped operators. We have designed a PCI based system including 64 GBytes of FLASH memory connected to a Xilinx Virtex-2 Pro component. A speed-up of 75 has been measured on a real intensive genomic sequence comparison application.

Compared to other research works, which mainly process the database as a nucleic data stream, data are structured in such a way that they can be highly re-used when accessed. Performances essentially come from that point: today FPGA components house a huge potential computational power which can really be exploited if they can be fed at a consequent data rate. Magnetic storage cannot sustain such features, and hundred of GBytes of RAM or DRAM memories are no so easy to implement. FLASH memory appears as a good compromise.

The limited write cycles of the FLASH memory might be seen as a strong constraint, leading to restrictive use of the accelerator. Actually, in the context of large computation, data remains long enougth in the FLASH memory to avoid a fast wear. The FLASH memories we used (Samsung K9W8G08U1M [START_REF] K9w | 8G08U1M Samsung, 1G x 8 Bit NAND Flash Memory Datasheet[END_REF]) can support 100,000 writes before any degradation in a typical application. If we reload the complete memory every hour, then we have a potential use of more than 10 years ! Furthermore, the life of the memory can be augmented by using wear-leveling mechanisms [START_REF] Gal | Algorithms and data structures for flash memories[END_REF] which avoids writing to always the same memory blocks.

Further researche will focus on investigating implementation of other programs from the BLAST family, especially the BLASTN program in the context of detecting all the repeat sequences inside full genomes. These applications require comparing entire genomes against themselves. They take days of computation, even on large clusters. The same index technique, based on DNA seeds, can be used to structure the database, and feed a specific DNA ungapped processor array.

More sophisticated data structures are also envisioned, such as suffix trees which are intensively used in the bioinformatics area to locate identical motifs along genomes. Today, even for medium size genomes, such structures cannot fit into the main memory of computers. Having these structures stored in FLASH memories together with their appropriate query hardware mechanisms will surely contribute to eliminating the current bottleneck in the use of suffix trees for processing large genomes.

Fig. 2 .

 2 Fig. 2. Ungapped Operator. Left side: architecture principle of an ungapped operator. The substitution cost of the amino acids coming from the query and databse substrings are added. The return score is the maximum value achieved during the calculation. Righ side: K ungapped operators can be connected in such a way that one query substring is compared with K database substrings. Extra hardware are added for collecting the results by shifting the maximum values calculated during the previous cycles.

  ; i<L; i++) { score = score + SubMat(Qry[i]][Db[i]); if (score>max) max = score; } The SubMat function returns a positive or negative value according to the substitution cost of amino acid Qry[i] by amino acid Dd[i].

Fig. 3 .

 3 Fig. 3. Architecture of the accelerator. An array of P × K ungapped operators is both feed from the FLASH memory and from a small local memory implemented with the FPGA RAM resources. The local memory contains K substrings which are re-initialized by the PowerPC processor each time a new computation is done.

Fig. 4 .

 4 Fig. 4. FLASH memory organization. It is composed of 4 independant 16 GBytes banks. Each bank has its own controller implemented into Xilinx Spartan-3 FPGA. These controllers permit page reading and page access overlaping, leading to sustain a 640 Mbytes/sec bandwidth.

  Fig. 5.Performance comparison of the DeCypher Engine and the FPGA/FLASH architecture. A database, composed of 192 bacterial genomes, is compared against set of proteins. For small sets, the DeCypher Engine is better as it is not penalized by the FLASH memory initialization. For large set, the FLASH/FPGA architecture is approximatively 2.5 times faster.

TimeLogic benchmark: http://www.timelogic.com/benchmark blast.html

1 This work is supported by the French Research Ministry under the ACI Masses de Données ReMIX 2 This work is supported by the National Natural Science Foundation of China (Grant No.60573163) 3 This work is supported by the French-Chinese Research Program PRA SI04-04