Introduction

In [START_REF] Cook | A taxonomy of problems with fast parallel algorithms[END_REF], Cook has described boolean circuits as a computational model of parallelism. In these views, the depth of a circuit corresponds to the running time, while its size corresponds to the number of processors. The class NC, that is functions computed by circuits of polynomial size and poly-logarithmic depth, plays a major role: it corresponds to the case for which there is an exponential speed-up (up to a polynomial) between the parallel algorithm and the relative sequential algorithm.

One of the issues with boolean circuits is that they intrinsically depend on the number of bits of their inputs. Thus, since problems handle inputs of arbitrary size, they are not computed by a single circuit but by a family of circuits. Without restrictions on the family, circuits may compute problems even not computable by a Turing Machine. In other words, the computational power of the model lies in the complexity of the family (the external computational power), not in the circuit's capabilities (the internal computational power). To tame this awkward external computational power, circuit families are described by a "simple" mechanism depending on the number of inputs as its size measure, they are said to be uniform.

With time, the notion of uniformity considered by the authors has been sharper and sharper. It corresponds to polynomial time in Borodin [START_REF] Borodin | On relating time and space to size and depth[END_REF], then logarithmic space in Cook [START_REF] Cook | A taxonomy of problems with fast parallel algorithms[END_REF], then alternating logarithmic time (ALogTime) in Ruzzo's seminal paper [START_REF] Ruzzo | On uniform circuit complexity[END_REF] and finally deterministic logarithmic time (DLogTime) by Barrington, Immermann and Straubing [START_REF] Mix Barrington | On uniformity within N C 1[END_REF] after Buss's notion of problem reduction [START_REF] Buss | The boolean formula value problem is in alogtime[END_REF].

We propose to go one step further in the restrictions of the construction of circuit families, and to consider a uniformity condition based on the notion of (length preserving) rational relations. Predecessor gates are computed by a multi-tape one-way finite state automaton. Let us make two remarks to motivate this notion of uniformity. First, length preserving rational relations are quite robust: they are closed by union, intersection, complement, composition. Thus, many manipulation of addresses can be done harmlessly which means that the uniformity condition itself-though very sharp-is quite robust. Second consideration, in [START_REF] Bonfante | Recursion Schemata for N C k[END_REF], we have characterized each layers of the hierarchy (NC k ) k 2 by means of some recursive schemas. The core recursion scheme, that is miprecursion (mutual in place recursion), involves computations by rational uniform circuit of constant depth. The layers NC k are obtained by iterations of these constant depth circuits. The present work is a first step toward a characterization of rational uniform circuit families.

Our contribution splits in four parts. In a first step, we define the notion of rational-uniformity of a family of circuit and we justify the definition. In particular, we discuss its robustness. One of the main point of the definition is that the size parameter of the connection language refers to the number of inputs n written in binary, not to a witness word of size n. Such a choice already appears in [START_REF] Barrington | Regular languages in NC 1[END_REF], it is however mandatory for rational uniformity due to the low computability power of finite state automata. Then, we propose some alternative descriptions for circuit based on a finite fan-in basis or constant depth circuits, the latter being used for a separation theorem proof. In a second step, to relate the rational uniform hierarchy to the deterministic logarithmic time hierarchy, we establish the inclusion NC k Rat ⊆ NC k DLT ⊆ NC k+1 Rat for all k 0. It is based on the internalization of the construction of the circuits within the computation, an argument already present in Ruzzo's work [START_REF] Ruzzo | On uniform circuit complexity[END_REF]. In a third step, we compare the internal computational capabilities of rational circuit families with respect to the external ones, we prove NC 0 Rat = Reg. At the same time, we show that at the first level there is a separation theorem: NC 0 Rat NC 0 DLT . Finally, in a last step, we consider rational circuit families based on unbounded fan-in gates, and we prove the standard theorem NC k Rat ⊆ AC k Rat ⊆ NC k+1 Rat for all k 0. To sum up, we establish the hierarchy:

NC 0 Rat NC 0 DLT NC 1 Rat ⊆ • • • ⊆ NC k Rat ⊆ NC k DLT ⊆ NC k+1 Rat ⊆ • • • ⊆ NC with a
separation theorem at the first levels. In the remaining of the paper, we study the hierarchy AC k Rat , k 0, and we prove the expected result NC k Rat ⊆ AC k Rat ⊆ NC k+1 Rat for all k 0. We relate the hierarchy to the standard scale with a proof that AC k DLT ⊆ NC k+1 Rat for all k 0 with a separation theorem at the first level.

As a by product of this work, we provide a new description of the class NC, a class of problems which has been intensively studied in the past. Remarkably, NC is characterized according the three main lines of implicit computational complexity, that is in terms of descriptive complexity e.g. [START_REF] Mix Barrington | On uniformity within N C 1[END_REF], with respect to the Curry-Howard paradigm [START_REF] Terui | Proof nets and boolean circuits[END_REF][START_REF] Mogbil | Uniform circuits, & boolean proof nets[END_REF], or by means of recursion theory, see the work of Leivant [START_REF] Leivant | A characterization of NC by tree recurrence[END_REF], Oitavem [START_REF] Oitavem | Characterizing N C with tier 0 pointers[END_REF] with Bellatoni [START_REF] Bellantoni | Separating NC along the δ axis[END_REF].

Preliminaries

To begin with notations, ū denotes a sequence u 1 , . . . , u n . Usually, n is understood from the context. The complement set

S R {x ∈ S | x ∈ R} is abbreviated to R when S is clear from the context.
Given some alphabet Σ of letters, the set Σ * denotes the set of words over Σ. The boolean alphabet is B = {0, 1}. The empty string is written ε and w • w denotes the concatenation of two words w and w . Given a word w, the k-th concatenation w k is defined by the equations: w 0 = ε, w k+1 = w k • w. The length of a word is written |w|. Finally, the subset of words in Σ * of length smaller than k ∈ N is denoted by Σ k , those of length exactly k by Σ k .

We let n be the usual binary encoding of the natural number n in |n| = log 2 (n) + 1 bits. We also denote it |n| when it is unambiguous. Actually, we do not specify the order of the bits: read left to right, they may be sequenced from less significant-bits to most significant ones (LH), or from most significant-bits to less significant ones (HL). This will not make difference since rational languages are closed by mirror. For k > |n |, n k denotes the padding of n with leading 0's so that |n k | = k. Naturally, for an encoding LH, the zero's appear on the right, for HL on the left.

An n-ary relation R ⊆ (Σ * ) n is said to be length preserving iff (w 1 , . . . ,

w n ) ∈ R implies that |w 1 | = • • • = |w n |. For a function f : X → Y , dom(f ) is its domain, that is the set of x ∈ X such that f (x) is defined. A function f : Σ * → B defines a language L(f ) = {w ∈ Σ * | f (w) = 1}
called the relative language of the function.

Multi-tape finite state automata

We recall the some definitions concerning transducers and more generally multitape one-way finite state automata, and some well known facts used in the sequel. We refer the reader to the handbook [START_REF] Rozenberg | Handbook of formal languages[END_REF] or to the book of Sakarovitch [START_REF] Sakarovitch | Elements of Automata Theory[END_REF] for the proofs of the statements presented in this section. Some constructions are taken from Kaplan and Kay [START_REF] Kaplan | Regular models of phonological rule systems[END_REF].

Definition 1 (Originally introduced by Rabin and Scott [START_REF] Rabin | Finite automata and their decision problems[END_REF]). A multitape one-way non writing finite state automaton (MONA) is a 5-tuple Σ, Q, q 0 , F, δ with Σ an alphabet, Q a (finite) set of states, q 0 ∈ Q is called the initial state, F ⊆ Q is the set of final states and δ ⊆ Q × (Σ * ) k × Q is the transition relation. δ induces a relation δ * ⊆ Q×(Σ * ) k ×Q defined as follows. (q, w 1 , . . . , w k , q ) ∈ δ * iff (q, w 1 , . . . , w k , q ) = (q, ε, . . . , ε, q) or (q, u 1 , . . . , u k , q ) ∈ δ * , (q , v 1 , . . . , v k , q ) ∈ δ and w i = u i • v i for all i k.

A MONA T = Q, Σ, Γ, q 0 , F, δ induces the relation [T ] ⊆ (Σ * ) k to be (w 1 , . . . , w k ) ∈ [T ] iff there exists q f ∈ F such that (q 0 , w 1 , . . . , w k , q f ) ∈ δ * .

A relation S ⊆ (Σ * ) k is said to be rational if there is a MONA T such that S = [T ]. It is a rational function if the relation is a function (the last component being the "output").

When k = 1, the definition corresponds to standard (non-deterministic) finite state automata, when k = 2, it corresponds to transducers which have a common input and output alphabet.

Example 1. 0 1 Σ : Σ Σ : ε 0' 1' Σ : ε Σ : Σ
The left transducer H 0 , removes even letters from a word on some alphabet Σ, while right transducer H 1 removes odd letters.

We recall well known facts about rational relations. They are justified by Nivat's Theorem. In the present setting, it is formulated as follows.

Theorem 1 (Nivat [17]). Let Σ be a finite alphabet. R ⊆ (Σ * ) k is a rational relation iff there is a finite alphabet Γ , a regular language S ⊆ Γ * and k monoid morphisms g 1 : Γ * → Σ * ,. . . , g k : Γ * → Σ * and R = {(g 1 (w), . . . , g k (w)) | w ∈ S}.

First, rational relations are closed under union: given two MONA S and T , we let S ∪ T be the (a choice of a) MONA corresponding to the relation [S] ∪ [T ]. They are closed under composition:

Theorem 2. Given two MONA S and T , let (x, z) ∈ [S] • [T ] iff ∃ȳ | (x, ȳ) ∈ [T ] ∧ (ȳ, z) ∈ [S]. Then, there is a MONA S • T such that [S • T ] = [S] • [T ].
Proposition 1. Any projection of a MONA S is regular: that is for all i k, {x i | x ∈ [S]} is a regular language. For any regular sets R 1 , . . . , R i-1 , R i+1 , . . . , R k , the range set

{x i | x ∈ [S] ∧ ∀j = i : x j ∈ R j } is a regular language.
Rational length-preserving relations are closed under intersection and complementation. Again, given two MONA S and T , let

S ∧ T denote the MONA [S ∧ T ] = [S] ∧ [T ] and [ S ] = [S]
. These two constructions can be actually justified by the following Proposition (see for instance Sakarovitch [START_REF] Sakarovitch | Elements of Automata Theory[END_REF]): Proposition 2. For any rational length-preserving relation, there is a MONA Σ, Q, q 0 , F, δ such that (w 1 , . . . , w k ) ∈ δ only if As a corollary of the closure by intersection and by complement, suppose R, S and T be three MONAs representing length-preserving relations, then, the following relation is rational (and length preserving):

|w 1 | = • • • = |w k | = 1.
U ( w) = { w | w ∈ [R] ∧ [T ] or w ∈ [R] ∧ w ∈ [S]}. The relation U is computed by the MONA (R ∧ T ) ∨ ( R ∧ S) next denoted as follows: if R( w) then T ( w) else S( w).
Example 2. In particular, any singleton language is regular, thus if a MONA Addition (and thus subtraction by permutation) and comparison can be computed by length preserving MONA (as long as the two numbers are encoded by words of equal length and with an upper-bit equal to 0). We give the example of addition, the states contain the carry of the addition.

T computes a function (Σ * ) k-1 → Σ * , a ∈ Σ * and two MONAs U, V compute relations in (Σ * ) k , the relation R( w) = if [T ]( w) = a then [U ]( w) else [V ]( w) is rational. Example 3.

Rational-uniform circuits

In this section, we define circuit families and circuit complexity classes. We refer the reader to the book of Vollmer [START_REF] Vollmer | Introduction to Circuit Complexity: A Uniform Approach[END_REF] for a wide presentation of circuit complexity. In a large extent, definitions, notations are taken from the book.

A circuit is a labelled directed acyclic graph whose nodes, called gates, output values in booleans B = {0, 1}. Labels, also called the types, are elements of the basis B 0 = {∧, ∨, ¬, 0, 1, i, o}. Gate with type ∧, ∨ have exactly two predecessors, gates of type ¬ and o (that is output gates) have one predecessor. Gates typed 0 (rejecting gates), gates typed 1 (accepting gates), and input gates (with type i) have no predecessors.

Inputs (resp. outputs) are supposed to be ordered from 0 to n -1 (resp. from 0 to m -1), for some n, m > 0. Plugin the input x =

x 0 • x 1 • • • x n-1 ∈ {0, 1} n into a circuit C outputs an array of boolean of size m, denoted C[x]. Such a circuit C computes the function {0, 1} n → {0, 1} m defined by λx.C[x]. A circuit family is a sequence of circuits (C n ) n>0 such that, for all n ∈ N, the circuit C n has exactly n input gates. Such a family computes the function {0, 1} * → {0, 1} * defined by x → C |x| [x].
A circuit is said to be boolean if it outputs only one bit. A family of circuit is said to be boolean if all circuits of the family are boolean. In that case, the family defines a language, namely the set

{x | C |x| [x] = 1}.
Functions computed by circuit family are length respecting, that is |f (w)| = |f (w )| whenever |w| = |w |. As argued by Vollmer, this is actually not a restriction, since it is possible to pad the output with leading zeros. So, from now on, all functions are supposed to be length respecting.

A path in a circuit is a pair (u, π) of a gate u and a word π ∈ {0, 1} * . Given a path (u, π), u[π] denotes the gate defined as follows if it exists.

u[ε] = u and u[π • b] is the b-th predecessor gate of u[π] if it exists.
For some circuit C, we denote by |C| its size, that is the number of gates in C, and by ||C|| its height -or its depth -, that is length of the longest path from an output gate to an input gate. The depth of a gate w is the maximal length of a path from w to an input gate.

Rational-uniformity

We present a more restrictive notion of uniformity than DLogTime-uniformity which we call Rational-uniformity. Gates are given identifiers, also called addresses, that is words in some given alphabet Σ ⊇ {0, 1}.

All along, we suppose that circuits have polynomial size, there is a polynomial P such that This rather restrictive discipline on the syntax of addresses help us to provide some (more) precise descriptions of circuit families in the sequel. The syntax can be for sure generalized, but we let this issue for further research. Definition 2. A family of circuit (C n ) n>0 is said to be Rational-uniform iff:

1. let τ (-, -) be the function mapping any pair (n , w) such that w denotes an address of the circuit C n to its type, that is in B 0 . Then, the function τ is rational. 2. the predecessor function ϕ mapping any triple (n , w, k) to the address of the k-th predecessor of gate w is a rational function. We take the convention that ϕ(n , w, k) is not defined if there are no such k-th predecessor gate.

The underlying MONA corresponding to Item (1) is called the typing automaton and the one corresponding to Item (2) is the predecessor automaton.

The standard notion of uniformity is an efficient computation of a description of each C n from 1 n (a word of size n). Formally this refers to the direct connection language of the circuit family (C n ) n , that is the set made of the tuples (y, g , p, b ) such that: a) |y| = n, b) g is a gate address in C n , c) p ∈ {ε, 0, 1} and d) if p = ε, then b ∈ B 0 , otherwise b is the address of the p-th predecessor of g.

The major difference between the standard notion of uniformity and the current one is that we use a size witness which has size O(log(n)) (that is the argument n ) and not n (the y's in the tuples). This choice is due to an intrinsic limitation on the relative size of components in rational relations. Indeed, consider a MONA running on the input (y, w). By the pumping Lemma, for |w| > C, y = y 1 •y 2 •y 3 and w = w 1 •w 2 •w 3 and for all k 0, (y Second remark, thinking in terms of the direct connection language, Item (1) of Definition 2 corresponds to p = ε and Item (2) to p ∈ {0, 1}. It is only for convenience that we split the mappings. From Proposition 4, it would be equivalent to take a unique transducer for both typing and predecessor functions.

1 •y k 2 •y 3 , w 1 •w k 2 •w 3 )
Third remark, for our bounded fan-in function basis (B 0 ), the second argument of ϕ is either 0 or 1. Again, by Proposition 4, it is equivalent to define ϕ by a pair ϕ 0 , ϕ 1 of two rational functions. Then, the two functions are length preserving, thus can be described by a letter-to-letter MONA. For types, the function τ can be equivalently replaced by rational relations τ t (-, -) for each type t ∈ B 0 where (x, w) ∈ τ t iff τ (x, w) = t. Again, the MONA corresponding to τ t can be supposed to be letter to letter. Consider the addressing system for a circuit with 6 input bits and 1 output bit presented on the left. If one define gate addressed with a prefix w to have type ∨ and gates addressed with s to be rejecting gates, then, the circuit computes the function OR 6 . Here, as length parameter, we have set A = 1 and B = 1. It is clear that the construction extends to a Rationaluniform circuit family. Such circuits provide access to all the bits of the input word through a binary tree of depth log(n). To justify rationality, let us observe that the typing is immediate from the prefix letter and for the two predecessor functions, we work by case analysis.

ϕ 0 (n , o0 |n | ) = w 0 |n |-1 ϕ i (n , wu 00 m ) = if u • i • 0 m+1 < n then w • u • i • 0 m else s • u • i • 0 m+1 ϕ i (n , wu ) = if u • i < n then i • u • i else s • u • i with u ∈ {0, 1} * , i ∈ {0, 1}, m 0. Otherwise, ϕ i , i ∈ {0, 1} is left undefined.
The presentation entails the rationality of the predecessor functions.

We remind that a circuit family is said DLogTime-uniform (resp. ALogTimeuniform) if its direct connection language is in DLogTime (resp. ALogTime). As was to be expected we have the following property.

Theorem 3. Any Rational-uniform circuit family is DLogTime-uniform.

Proof. Let us suppose given a Rational-uniform circuit family (C n ) n with respective typing and successor functions (τ, ϕ 0 , ϕ 1 ) on some alphabet Σ. As justified above, these relations are respectively computed by the letter to letter MONAs (T t ) t∈B0 , Φ 0 , Φ 1 . The main issue is that data are not presented in the same way for the two notions of uniformity. So, in a first step, we prepare the data to fit the format of the MONAs (T t ) t∈B0 , Φ 0 and Φ 1 .

Let us consider the Turing Machine M defined as follows. Remember that inputs for DLogTime-uniformity have the form I = (y, g , p, b ). First, one computes log(y) on some working tape Y and pad it to length A × log(y) + B, this is n . The computation of log(n) can be done in log-time as justified by Buss [START_REF] Buss | The boolean formula value problem is in alogtime[END_REF], the padding takes A × log(n) + B steps, that is logarithmic time. Copying g , p and b on respectively working tapes G, P and B is also done in log-time since g and b have logarithmic length. Words on the working tapes Y , G and B have the format required by the MONAs (T t ) t∈B0 , Φ 0 and Φ 1 .

If p = ε, one runs the MONAs (T t ) t∈B0 in parallel on Y , G, B and we output the index of the succeeding MONA (the one reaching a final state). If p = 0, one runs Φ 0 on Y , G, B. Otherwise, one runs Φ 1 . In each cases, since we took the precaution to use letter-to-letter MONA, the run time is in the size of the tapes, that is in O(log(n)). To conclude, it is immediate to see that the machine M recognizes the connection language of the family, and that it runs in logarithmic time.

Constant-depth Rational-uniform circuit families

In this section, we present an alternative description of constant-depth Rationaluniform circuit families. It is used in Section 5 to prove the separation Theorem 5.

Let C d be the finite set of circuits C such that ||C|| d and C has a unique root, that is a unique gate which is an ancestor of all other gates. Each circuit C in C d has clearly less than W = 2 d input gates. Let Π(C) = (π 1 (C), . . . , π k (C)) with k W be a sequence of all the paths from the root to the input gates of

C. For each circuit C ∈ C d , for each w ∈ C, let E(C, w) be the finite set of pairs of words (π 1 , π 2 ) such that w[π 1 ] = w[π 2 ].
A family of circuit (C n ) n>0 is said to have constant depth whenever there is some d > 0 such that ||C n || d for all n > 0. For each gate w in (C n ) n , let us consider the sub-circuit made of w and its predecessors. It has depth at most d, and thus it is isomorphic to a circuit in C d , next called the index of w. By isomorphic we mean that the two circuits only differ by a renaming of addresses.

Proposition 5. Given a Rational-uniform circuit family of constant depth d, let θ be the function mapping (n , w) for n > 0 and an output gate address w in C n to the index of w. The function θ is rational.

In other words, up to some extra-copies of the circuit size, one may compute with a MONA the part of the circuit which participate to the computation of some gate w.

Proof. In a first step, we build a family of d + 2-ary rational relations (θ C ) C∈C d whose intention is the following: for some n > 0 and some gate address w, θ C holds on (n , . . . , n d+1 times , w) iff C is the index of w where d is the depth of the circuit C. Actually, the definition of the relations θ C is done by induction on the depth of circuits C ∈ C d .

The circuits C of depth 0 in C d are composed of one gate, either an input gate, an accepting gate or a rejecting gate. We define respectively θ

C τ i , θ C τ 1 , θ C τ 0 .
Consider a circuit C of higher depth. By case analysis on the type t of the root gate r of C. If t corresponds to a unary gate, that is o or ¬, let s be the unique predecessor of r in C. As a matter of fact, s is the root of a circuit C ∈ C d of depth strictly smaller than C. We define accordingly θ C (x 0 , . . . , x d , w) τ t (x 0 , w) ∧ θ C (x 1 , . . . , x d , ϕ 0 (x 0 , w)).

If t corresponds to a logical gate, ∧ or ∨. Let s 0 , s 1 be the two successors (possibly equal) of the unique root r ∈ C. The gate s 0 and s 1 are respectively the root of the circuits C 0 , C 1 of depth strictly smaller than the depth of C. Let π ∈ {0, 1} * , we define by induction on π the rational function ϕ π (x 1 , . . . , x n , w) by ϕ ε (x 1 , . . . , x n , w) = w and ϕ a•π (x 1 , . . . , x n , w) = ϕ π (x 1 , ϕ a (x 2 , . . . , x n , w)). Then, ϕ π (n , . . . , n , w) outputs w[π] whenever the sequence n , . . . , n has length at least |π|. Now, given a circuit C , we claim that C is isomorphic to C whenever (i) C has a root r labeled t, (ii) r has two predecessor states s 0 and s 1 respectively roots of circuits isomorphic to C 0 and C 1 , (iii) E(C, r) = E(C , r ). When defining θ C (x 0 , . . . , x d , w), (i) is verified by: (x 1 , . . . , x d , w) → τ t (x 1 , w), (ii) is verified by: (x 1 , . . . , x d , w) → θ C0 (x 1 , . . . , x d , ϕ 0 (x 0 , w)) ∧ θ C1 (x 1 , . . . , x d , ϕ 1 (x 0 , w)), (iii) is verified as follows. For all words π, π of length smaller than d, if (π, π ) ∈ E(C, r), then: (x 1 , . . . , x d , w) → ϕ π (x 1 , . . . , x d , w) = dom ϕ π (x 1 , . . . , x d , w), otherwise:

(x 1 , . . . , x d , w) → ϕ π (x 1 , . . . , x d , w) = dom ϕ π (x 1 , . . . , x d , w), where ϕ π ( t) = dom ϕ π ( t) iff either t ∈ dom(ϕ π )∧ t ∈ dom(ϕ π ) or ϕ π ( t) = ϕ π ( t).
The three points (i), (ii), (iii) can be put all together by closure under intersection of length preserving rational relations.

To end the proof, observe that θ C can be restricted to θ C (x 0 , . . . , x d , w) ⇔ θ(x 0 , . . . , x d , w) ∧ x 0 = x 1 = • • • = x d which is a length preserving. Let T C = (Σ, Q, q 0 , F, δ) be the corresponding letter-to-letter MONA. Then, θ is recognized by (Σ, Q, q 0 , F, δ ) with (q, a, b, q ) ∈ δ iff (q, a, . . . , a, b, q ) ∈ δ. The trick can be used for paths, and we let the MONA Ψ π for all path π such that [Ψ π ](n, w) = ϕ π (n, . . . , n, w).

Actually, one may think of C d as a (finite) function basis. Then, circuits of depth d on B 0 can be seen as circuits of depth 1 on basis C d . Proposition 6. For any Rational-uniform circuit family (C n ) n>0 of constant depth d, there are MONA (T C ) C∈C d and MONA Φ 1 , . . . , Φ W such that for all n > 0, for all output gate w in C n , [T C ](n , w) holds iff C is the index of w in C n and [Φ j ](n , w) outputs the address of the input gate in C n corresponding to the j-th input gate in C, the index of w.

Proof. The MONA (T C ) C have been constructed in the previous Lemma. The W = 2 d MONA Φ 1 , . . . , Φ W are built as follows. Let the circuits C d = (C 1 , . . . , C r ) and let ar(C) be the number of inputs of the circuit C. The MONA Φ j is:

(n , w) →        if T C1 (n , w) ∧ (j ar(C 1 )) then Ψ πj (C1) (n , w) else if T C2 (n , w) ∧ (j ar(C 2 )) then Ψ πj (C2) (n , w) . . . else ⊥
with Ψ π be defined as in the previous Lemma. 1) in the size of the input. We denote NC = ∪ k∈N NC k DLT . Following Cook [START_REF] Cook | A taxonomy of problems with fast parallel algorithms[END_REF], NC is considered to be the class of problems that can be efficiently solved on a parallel computer. Proposition 8 proves that NC k DLT ⊆ NC k+1

Rat for all k 0. Together with Theorem 3, we have the following hierarchy:

NC 0 Rat ⊆ NC 0 DLT ⊆ NC 1 Rat ⊆ NC 1 DLT ⊆ • • • ⊆ NC k Rat ⊆ NC k DLT ⊆ • • • ⊆ NC which implies that NC Rat = ∪ k∈N NC k Rat = NC. Lemma 1.
Given a ALogTime-uniform circuit family (C n ) n , without loss of generality, one may suppose that the address of any gate is actually labeled by t • u where t denotes the type of the gate. We call such circuits explicitly typed circuits.

Proof. Suppose that the circuit is not explicitly typed. Let M be the machine recognizing the connection language of (C n ) n . Let (C n ) n be exactly the same circuit family but with address (t • w) for any gate w of type t. It is also ALogTimeuniform. Indeed, verifying the type t of a gate w (y, w, ε, t) merely amounts to verify that t (whose size is bounded by some constant K) is the prefix of w so that the procedure takes constant time. Computing the i-th successor of a gate (t • u) is done as follows: verify(y,w,i,u){ //copies of types and address on some working tapes let (a,w') and (b,u') such that a.w' = w and b.u' = u return (run M on (y,w',i,u')) and (run M on (y,u',epsilon,b)) }

Copying addresses of logarithmic size is done in logarithmic time. The copies of the types take constant time. Finally, the two last runs take logarithmic time.

Simulation of alternating random access Turing Machine

We recall some main facts about alternating random access Turing Machine (ARM) as described by Leivant and Marion [START_REF] Leivant | A characterization of alternating log time by ramified recurrence[END_REF], see also [START_REF] Chandra | [END_REF][START_REF] Ruzzo | On uniform circuit complexity[END_REF]. A machine M is a tuple Q, q 0 , δ made of a set of states, an initial state and a transition function δ. States are classified as disjunctive or conjunctive (the action states), as accepting, rejecting or reading states. We recall that the operational semantics of the machine is a two step process: first generating the computation tree, second, evaluating the computation tree. A configuration is a tuple (q, w 1 , . . . , w k ) ∈ Q × B k of a state and k work stacks, the initial tuple being (q 0 , ε, . . . , ε). A computation tree is a tree whose nodes are configurations and whose root is the initial configuration. For action states, depending on the state and on the bits at the top of the work stacks, one spawns a pair of successor configurations by pushing/popping letters on the work stacks. For a machine working in time t(n), the tree is expanded up to depth t(n). For the evaluation, the computations begin at the leaves of the tree. The output of accepting/rejecting states is respectively 1 and 0. The output of action state is given by the associated logical operator. Finally, since we will apply ARM on connection language, that is 4-tuples (n , w, b, u), to simplify reading, we suppose that the input is actually written as four independent words t 0 , . . . , t 3 . To read the inputs, each word t i , i 3, is associated to a working tape indexed ρ(i) k and to a reading state q read(i) ∈ Q. The output of a configuration (q read(i) , w 1 , . . . , w k ) is the w ρ(i) -th bit of t i .

To simulate ARM by means of Rational-uniform circuit family, we need the (rational) function read defined as follows. read takes inputs (w, u) with w, u ∈ {0, 1} * . On inputs of the shape w = w • i with i ∈ {0, 1}, read outputs (w , H i (u)), that is it removes the last bit i of w, and then apply transducer H i on u, cf Example 1. Otherwise, that is if w = ε, read(w, u) = (w, u). By composition, read is clearly a rational function.

Given a circuit family (C n ) n>0 whose direct connection language L is recognized by an ARM M = Q, q 0 , δ working in logarithmic time, given some 4-tuple (y, w, b, u), let us consider the circuits C[M, n , w, b, u] with |y| = n as defined now. Gate addresses are tuples (q, w 1 , • • • w k , n , w, b, u) made of a configuration of M and the content of the inputs of M . We call these addresses extended configurations. According to the state, we define the typing and the predecessor functions of C[M, n , w, b, u]. a) for any action state (of M ), (q, w 1 , • • • w k , n , w, b, u) has the corresponding logical type. Its two predecessors are the extended configuration (q i , w i 1 , . . . , w i k , n , w, b, u) for i ∈ {0, 1}, as given by the transition function. b) Accepting/Rejecting states are typed 0 or 1. c) for a reading state q read(i) , we build a chain of identity gates3 with a last gate being a rejecting gate or an accepting one (actually depending on the bit read in t i ). The first identity gate has the address (w ρ(i) , t i ). Its predecessor is read(w ρ(i) , t i ). After |w ρ(i) | application of the function read, we get a pair of words (ε, u) such that the last bit of u denotes the bit read at address w ρ(i) within t i . The last gate of the gate is accepting or rejecting depending on this last bit.

Given the preceding description, Proof. 1. The simulation of action states, accepting states and rejecting states directly follows from the operational semantics. The simulation of reading state, though done in O(log(n)) steps output the desired result. 2. Since w j is a working tape, it has size O(log(n)). The chain of identity gate having the same length, the depth is O(log(n)). For the size, one observes that all words have length O(log(n)). The result follows by enumeration. 3. Typing is immediate from the classification of states. For predecessor functions, for action states, since the next configuration depend only on the finite control of the top bits, computing the predecessor configurations is clearly rational. For reading states, computing (w j , t i ) from (q read(i) , w 0 , . . . , w k , t 0 , . . . , t 3 ) is also rational and we have seen above that read is rational. 4.2 From DLogTime-uniformity to Rational-uniformity Proposition 8. For all k 0, NC k DLT ⊆ NC k+1 Rat .

Proof. Actually, we prove the even more stronger result, that is NC k ALT ⊆ NC k+1

Rat . Indeed, since DLogTime ⊆ ALogTime, DLogTime-uniformity is a priori sharper than ALogTime-uniformity. Actually, the two notions coincide for k 1 as shown by Barrington, Immerman and Straubing in [START_REF] Mix Barrington | On uniformity within N C 1[END_REF]. So, consider a function computed by an ALogTime-uniform, explicitly typed family of circuits, (C n ) n>0 of polynomial size and depth bounded by c × log k (n). Let M be the machine running in ALogTime which decides the direct connection language of (C n ) n>0 . We begin by some preliminary observations. First, there is a constant K such that the machine M runs in time K ×log(n) and space K × log(n) where n denotes the size of the input. Then accordingly, the size of any gate addresses in the circuit C n is bounded by K × log(n). So by a padding argument, one may suppose without loss of generality that every gate address (in C n ) has actually exactly the size C × log(n) for any n > 0.

Second, circuits (C[M, n , w, b, u]) n , w,b,u described for Proposition 7 have logarithmic depth whenever w, b, u have logarithmic size (in n).

We define now a Rational-uniform circuit family (C n ) n such that C i simulates C i for all i > 0. The principle of our simulation is the following. To any gate w in C n , we associate a corresponding gate w in C n with same logical operator. In a first step, we guess the addresses u 0 and u 1 of both successor gates of w. Given u i , we verify in parallel that u i is actually the i-th successor of w (i ∈ {0, 1}) by means of C[M, n , w, i, u i ] and we build recursively the circuit corresponding to the gate u i . The process ends on input gates.

Let us describe the construction in more details. First, we suppose that the circuit family is typed (as justified by Lemma 1). Any address (t • w) corresponding to a logical gate of type t in C n is mapped to a gate (n , (t • w)) in C n . From that gate, we build a small circuit as follows. Let A be the number of successors of w (one for the negation and two for the binary operators). (n , (t • w)) has A ∨-gate successors (t1) addressed (n , (t • w), i, ε) with 0 i < A . Any such gate (n , t • w, i, ε) is the root of the full binary tree of gates (t2) of depth |w| = C ×log(n) with leaves addressed (n , t•w, i, u). Internal nodes of the binary tree are ∨-gates, the leaves having type ∧.

The first successor (t3) of a gate (n

, t • w, i, u) is C[M, n , t • w, i, u].
The second successor (t4) is the gate corresponding to u itself (here the construction will recursively continue). Finally, any input gate within C n is an input gate within C n .

It is clear that the family is Rational-uniform: constructions (t1) and (t2) are obtained by concatenation of finitely many letters to the current address, (t3) refers to Proposition 7, and (t4) consists in erasing the arguments t • w and i.

The length of the path between gate w and gate u is C × log(n) + 1 (the depth of the binary tree (t2)). Thus, the depth ||w|| of the circuit from gate w is

||w|| = max(C × log(n) + ||u||, C × log(n) + K × log(n)) (1)
||u||

+ (C + K) × log(n). (2)
where in Equation 1, the max function comes from the parallel choice (done at each leaf of (t2)) for the verifier (t3) as given by Proposition 7 and the depth of the circuit from that gate. Since the depth of the circuit C n is bounded by c × log k (n), using recursively Equation 2, it follows that the depth of the circuit

C n is bounded by c × log k (n) × (C + K) × log(n) = O(log k+1 (n)).
Remark that since all the addresses in circuit C n have size bounded by O(log(n)), the size of the circuit C n is bounded by n O (1) .

Separation theorems

We present classical separation proofs for the DLogTime-uniform hierarchy. We stress that these proofs are not restricted to the case of uniform circuit family! Definition 4. We define the standard following decision problems. Instance: A binary word w ∈ {0, 1} * . PARITY: Is the number of 1's in w odd? MAJORITY: Are the majority of input bits 1? PALINDROME: Are bits at positions i and |w| -i equals, for all 1 i |w|? OR: Is the disjunction over bits of w equals to 1? HALF: Is the middle bit of w equals to 1? The restriction of the previous problems to an instance of binary word with fixed length n are denoted respectively PARITY n , MAJORITY n , PALINDROME n and HALF n .

Lemma 2. PARITY, MAJORITY, OR and PALINDROME are not in NC 0 Rat but in NC 1 Rat .

Proof. Given an input of size n, all of these problems require circuit depth at least Ω(log(n)), just so all the input bits could effect the output gate. Thus no one belongs to NC 0 Rat (as well as NC 0 DLT ). For NC 1 Rat membership, we have seen how to compute OR n for a given n in Example 4. PARITY uses the same schema but with w-gates typed XOR (those gates being simulated by x xor y = (x ∨ ¬y) ∧ (¬x ∨ y) on basis B 0 ) and s-gates typed 0. To compute PALINDROME, we take again the same schema, but with w-gates being typed ∧, s-gates being typed 1 and input gates addressed i • u are replaced by a XOR-gate addressed c • u with two predecessors being i • u and i • (n -u -1). Since subtraction is rational, this latter address being obtained by equation ϕ 1 (n , c • u) = i • n -u -1 , the predecessor function ϕ 1 remains rational. A standard proof of membership for MAJORITY n given n, is to repeatedly reduce the addition of three numbers to the addition of two numbers, computing carries without propagate them by using bitwise XOR gates. After O(log(n)) depth, the resulting two O(log(n))-bit numbers have to be compared with n/2. All of these computations may be done within Rational-uniformity. Lemma 3. HALF ∈ NC 0 Rat .

Proof. Given n the middle bit address can be computed by a MONA: consider the circuit made of a unique output gate, with a predecessor function ϕ 0 defined only on the input: ϕ(n , o • 0 |n| ) = (n -1)/2 . Subtraction is rational, division by 2 (a shift of the bits of n -1 ) is rational, thus ϕ 0 is rational. ϕ 1 is the empty function, and typing is immediate.

We denote Reg the class of decision problems solvable by deterministic finite automata. It is well known that Reg = DSpace(O(1)), the decision problems that can be solved in constant space [START_REF] Shepherdson | The reduction of two-way automata to one-way automata[END_REF]. Proof. As it is uncommon, we present that the language relative to the function HALF is not regular. Ad absurdum, by Pumping Lemma, suppose it is so. Let N be the bound above which w ∈ L(HALF) implies w = w 1 • u • w 2 with |u| > 0 and w 1 • u k • w 2 ∈ L(HALF) for all k 0. Let us apply it on w = 0 N • 1 • 0 N . Let the decomposition w = w 1 • u • w 2 as above. Either u contains the 1, but then w 1 • w 2 contains no 1 and thus w 1 • w 2 ∈ L(HALF) in contradiction with the Lemma. Or, w 1 = 0 m , u = 0 j and w 2 = 0 N -m-j 10 N is the remaining word with j > 0 since |u| > 0. But, in that case, w 1 • u 2 • w 2 = 0 N +2j • 1 • 0 N has no 1 in the middle, contradicting the Lemma. The last case, w 1 = 0 N • 1 • N k , u = 0 j , w 2 = 0 N -j-k is symmetric to the preceding one. From Buss [START_REF] Buss | The boolean formula value problem is in alogtime[END_REF], for any word y of length n, for any boolean b ∈ {0, 1}, computing log(|y|) from (y, 0, b, u) is done in logarithmic time. Since log(|y|) has logarithmic size with respect to (y, 0, b, u), the equality of log(|y|) with u is performed in logarithmic time.

We establish now ad absurdum that the predicate τ cannot be computed by a Rational-uniform circuit family of constant depth. We propose a proof with an encoding based on size parameters A = 1 and B = 0. The proof can be extended to other cases. Suppose the existence of such a family (C n ) n computing τ . Let D be its depth.

Fact 1. There is a path from the output gate addressed o • 0 n of the circuit C n to the input gate addressed i • log(n) . Otherwise, the output of the circuit C n [w] on some word w would not depend on its log(n)-th bit, that is w log(n) , which contradicts the definition of τ .

Fact 2. Without loss of generality, one may suppose that w log(n) is actually the only input bit read on the input by the circuit C n . Indeed, it is clear that τ does not depend on other bits, so that other input gates can be replaced by a (for instance) rejecting gate. |n| | n > 0} is a regular language. We actually prove that A is not regular. If it were the case, let L be the bound as given by the Pumping Lemma. Consider the smallest k such that n = 2 2 k verifies |n | = 2 k + 1 > L. The word log(n) |n| has the shape 0 2 k -k • 1 • 0 k , thus has length 2 k + 1 Then, since, log(n) |n| ∈ A , there is a decomposition log(n) |n| = u • v • w such that for all t 0, u • v t • w ∈ A . There are three cases, v is at the left or right of the 1, or it contains the 1. The reader can easily check the contradiction, that is, in the first cases |w t | is opposed to membership in A , and the last case is a simple computation.

Proposition 3 .Proposition 4 .

 34 Such a MONA is called a letter-to-letter MONA. Given a rational relation R ⊆ (Σ * ) k and a permutation σ : {1, . . . , k} → {1, . . . , k}, the relation Rσ { w | (w σ(1) , . . . , w σ(k) ) ∈ R} is a rational relation. Consider a rational relation computed by a MONA [T ] ⊆ (Σ * ) k . If R ⊆ Σ * is a regular language then there is a transducer denoted by T |R,i such that w ∈ [T |R,i ] iff w ∈ [T ] and w i ∈ R.

  |C n | P (n) for all n > 0. Consequently there are constants A, B 0 such that all the gates can be encoded in less than |P (n)| A × |n | + B bits. Accordingly, input addresses are encoded i0 A×|n |+B , . . . , in -1 A×|n |+B where i is a letter different from 0,1. In the same way, output addresses are given addresses o0 A×|n |+B , . . . , om -1 A×|n |+B with o a fresh letter. The addresses of the other gates are also supposed to have length A × |n | + B. The size witness is n A|n |+B . Actually, since A and B are fixed by the encoding, we will shorten n A|n |+B in the following to n .

  belongs to the relation. However, in the standard representation, since |w| = O(log(|y|)), for all constant A > 0, there is a sufficiently large y such that |y| > A × |w|. This contradicts |w 2 | > 0. |w 2 | = 0 means that |y 2 | > 0 and (y 1 • y 3 , w) is in the relation. Iterating this process, one finally gets a word y of smaller than C, in contradiction with the fact that |y| O(log(|w|)).

4 Complexity hierarchy robustness Definition 3 (

 3 Complexity classes). For k ∈ N, NC k Rat (resp. NC k DLT and NC k ALT ) is the class of problems solvable by a Rational-uniform (resp. DLogTimeuniform and ALogTime-uniform) family of circuit (C n ) n>0 over basis B 0 , of respective depth ||C n || = O(log k (n)) and size |C n | = n O(

Proposition 7 . 1 .

 71 the circuit C[M, n , w, b, u] outputs 1 iff (y, w, b, u) ∈ L, 2. the circuit has depth O(max(|n|, |w|, |b|, |u|)) and polynomial size, 3. the typing function, the two predecessor functions are rational.

Lemma 4 .

 4 PARITY, OR ∈ Reg and HALF, PALINDROME / ∈ Reg.

Theorem 4 . 1 1 1 Rat

 4111 Reg = NC 0 Rat and NC 0 DLT NC Rat . Proof. Inequality arises from previous lemmas: we have OR / ∈ NC 0 Rat HALF and OR ∈ Reg HALF. Finally NC 0 DLT NC Rat as OR / ∈ NC 0 DLT and OR ∈ NC Let τ : {0, 1} * → {0, 1} such that τ (w) is the log(|w|)-th bit of w. Such a function is computable within NC 0 DLT . Given n ∈ N, consider the circuit made of one output ∨ gate addressed 0 whose two successor gates are the input gate log(n). Typing is trivially DLogTime-uniform. To verify that the successors of the output gate can be computed in DLogTime, we have to verify that the relation {(y, 0, b, u) | b ∈ {0, 1} ∧ u = log(|y|)} is computable in DLogTime.

Fact 3 .

 3 According to Proposition 6, there is a MONA Φ1 such that Φ 1 outputs i • log(n) |n| on input (n , o • 0 |n | ).As we will see, the set of binary wordsA = {i•log(n) |n| | n > 0} is not regular. But the projection of a rational relation is a regular language (see Proposition 1). Since {u | (B * , o • 0 * , u) ∈ [Φ 1 ]} = A, there is a contradiction.Let us suppose that A is regular. Consider a transducer [D] that removes the first letter of a word, then, according to Proposition 1, its range A = [D](A) = {log(n)

On the basis B0, it is obtained as the composition of two gates: x → x∨0 for instance.

Work partially supported by the french project Complice (ANR-08-BLANC-0211-01,3)

Unbounded fan-in circuits

We provide same kind of results for Rational-uniform circuit families, called with unbounded fan-in, over the basis B 1 = {(∧ n ) n 2 , (∨ n ) n 2 , ¬, 0, 1, i, o}.

Again we suppose that circuits have polynomial size, so there is a polynomial P such that |C n | P (n) for all n > 0. Then each gate of C n has at most P (n) predecessors and we consider its k-th predecessor where we encode k also in less than |P (n)| bits. We choose to describe gates over the basis B 1 by giving its type in {∨, ∧, i, o, ¬} and by describing all of its predecessors: this is exactly our Rational-uniform definition 2. Since all the inputs have a common length, again, the MONAs can be considered to be letter-to-letter.

We define AC k Rat for k ∈ N exactly as NC k Rat but over basis 1) in the size of the input. Then by theorem 3, we have for all k 0, AC k Rat ⊆ AC k DLT but also the following.

Proposition 9. For all k 0, we have NC k Rat ⊆ AC k Rat ⊆ NC k+1 Rat .

Proof. First inclusion trivially comes from Rational-uniform definition by describing AC k Rat with the same MONA as NC k Rat . Second inclusion is described as follows. Consider a circuit family (C n ) n in AC k Rat . There are letter-to-letter MONAs T and Φ computing τ and ϕ. Any gate w of C n which is in B 0 is left unchanged, any other gate w, say a ∧ n , is replaced by a binary tree of gates ∧ defined as follows. The root of the tree is (q 0 , ∧, w, ε, ε) with q 0 being the initial state of Φ. Any state (q, ∧, a • w , k , u ) has type ∧ and successors (q , ∧, w , b • k , c • u ) for all (q, a, b, c, q ) ∈ δ Φ with δ Φ the transition relation of Φ. Since δ Φ is finite, this is easily encoded in basis B 0 . Any state (q, ∧, ε, k, u) has type 1 if q ∈ F Φ , the set of final states of Φ. Otherwise, the state has the type of u in C n . From the construction, observe that u is the address of the k-th predecessor of w in C n . Then, removing q, ε, k from the address by a MONA is easy and the definition continues from u. Since, the MONA Φ is letter-to-letter, the length of the path between gate w and gate u is |w|, that is O(log(n)). Thus, the depth of the simulating circuit is

). Since the addressing system simulates a running MONA, the construction is rational. Proposition 10. For all k 0, we have AC k DLT ⊆ NC k+1 Rat .

Proof (Sketch). We revisit the proof of proposition 8 only for the three following points. 1) We consider a function computed by an ALogTime-uniform explicitly typed family of circuits (C n ) n of polynomial size and depth bounded by c × log k (n), but over B 1 . Then given n, each gate has at most log(n O(1) ) = O(log(n)) predecessors. 2) We will use the circuits (C[M, n , w, b, u]) n , w,b,u described in Proposition 7 which have logarithmic depth whenever w, b, u have logarithmic size (in n). In Proposition 8, b was a constant, here, it has logarithmic size. But the proof of Proposition 7 remains valid in the present case.

3) When simulating a gate w, instead of spanning a full binary tree to find the predecessor u corresponding to w, we span a full binary tree whose leaves are pairs (k, u) ∈ Σ A×log(n)+B ×Σ A×log(n)+B . Such addresses having size O(log(n)), the depth of the tree remains O(log(n)) as in Proposition 8. At each leaf, instead of verifying that (n

The depth and the size bound are computed as in Proposition 8.

Lemma 5. PARITY / ∈ AC 0 Rat .

Proof. Standard and very nice proofs for PARITY / ∈ AC 0 DLT are valid for even non-uniform circuit family. E.g. they are based on the fact that every constant depth circuit computing PARITY n must have sub-exponential size (i.e. exp(Ω(n

)) for depth d circuit) [START_REF] Furst | Parity, circuits, and the polynomial-time hierarchy[END_REF]1,[START_REF] Håstad | Almost optimal lower bounds for small depth circuits[END_REF]. This applies also with Rationaluniformity! Theorem 6. Reg = AC 0 Rat NC 1

Rat

Proof. By proposition 9 for k = 0, we have NC 0

Rat ⊆ AC 0 Rat ⊆ NC 1 Rat . By lemmas 4 and 3 , we have HALF is not in Reg but in NC 0 Rat , thus in AC 0 Rat . Then AC 0 Rat ⊆ Reg. By lemmas 2, 4 and 5, PARITY is not in AC 0 Rat but in Reg ∩ NC 1 Rat . Then we have both Reg ⊆ AC 0 Rat and NC 1 Rat ⊆ AC 0 Rat , and the result holds.

Conclusion

Common questions remain to study w.r.t P and NP . Indeed our uniformity notion is a weak external computational power keeping the internal computational power for separation approaches. E.g. as MAJORITY∈ NC 1 Rat we have for Constant-Depth Threshold Circuits T C 0 Rat ⊆ NC 1 Rat , and one could ask whether T C 0 Rat = NC 1 REG , or whether T C 0 = NP . Finally, the relationship between Reg and AC 0 is a long standing issue. We refer to the work of [START_REF] Buss | An optimal parallel algorithm for formula evaluation[END_REF] for a presentation of regular languages in NC 1 . It is almost clear that Reg ⊆ NC 1 Rat , but the question is renewed due to the fact that AC 0 Rat = AC 0 DLT using again the argument of the HALF function. Observe that AC 0 DLT HALF ∈ AC 0 Rat and HALF ∈ Rat which could mean that AC 0 Rat could be the "correct" set to deal with Reg. In this branch of research, the relation between Reg and ACC 0 Rat should be also reconsidered since HALF ∈ AC 0 Rat .


PharmD Mirjam B Zeisel
email: mirjam.zeisel@unistra.fr

Isabel Fofana

Samira Fafi-Kremer

PhD Thomas F Baumert
email: thomas.baumert@unistra.fr.

S J Polyak

Shuhart Mc

Wang

Hepatitis C virus entry into hepatocytes: 3 molecular mechanisms and targets for antiviral therapies 4 5

Keywords: claudin-1, HCV: hepatitis C virus, HCVcc: cell culture-derived HCV, HCVpp: HCV 24 pseudoparticle, HCV-LP: HCV-like particle, JFH1: Japanese fulminant hepatitis 1, OCLN: 25 occludin, SR-BI: scavenger receptor class B type

Hepatitis C virus (HCV) is a major cause of liver cirrhosis and hepatocellular carcinoma.

2

Preventive modalities are absent and the current antiviral treatment is limited by resistance, 3 toxicity and high costs. Viral entry is required for initiation, spread, and maintenance of 4 infection, and thus is a promising target for antiviral therapy. HCV entry is a highly 5 orchestrated process involving viral and host cell factors. These include the viral envelope 6 glycoproteins E1 and E2, CD81, scavenger receptor BI and tight junction proteins claudin-1 7 and occludin. Recent studies in preclinical models and HCV-infected patients have 8 demonstrated that the virus has developed multiple strategies to escape host immune 9 responses during viral entry. These include evasion from neutralizing antibodies and viral 10 spread by cell-cell transmission. These challenges have to be taken into account for the 11 design of efficient antiviral strategies. Thus, a detailed understanding of the mechanisms of 12 viral entry and escape is a prerequisite to define viral and cellular targets and develop novel 13 preventive and therapeutic antivirals. This review summarizes the current knowledge about 14 the molecular mechanisms of HCV entry into hepatocytes, highlights novel targets and 15 reviews the current preclinical and clinical development of compounds targeting entry. Proof-16 of-concept studies suggest that HCV entry inhibitors are a novel and promising class of 17 antivirals widening the preventive and therapeutic arsenal against HCV infection. 18 19 Hepatitis C virus (HCV) is a major cause of chronic hepatitis worldwide. The current therapy 1 against HCV infection, consisting of an association of pegylated interferon alpha (PEG-IFN) 2 and ribavirin, is limited by resistance, adverse effects and high costs. Although the clinical 3 development of novel antivirals targeting HCV protein processing has been shown to 4 improve sustained virological response, toxicity of the individual compounds and 5 development of viral resistance remain major challenges [1-3]. To date, a vaccine is not 6 available. The absence of preventive strategies is a major limitation for patients undergoing 7 liver transplantation (LT) for HCV-related end-stage liver disease. Re-infection of the graft is 8 universal and characterized by accelerated progression of liver disease [4]. Moreover, 9 treatment of recurrent HCV infection after LT is challenging due to enhanced adverse effects 10 and limited efficacy of IFN-based therapies in LT recipients [4, 5]. Recurrent HCV liver 11 disease in the graft with poor outcome has become an increasing problem facing 12 hepatologists and transplant surgeons. Thus, novel antiviral preventive and therapeutic 13 strategies are urgently needed. 14 Viral entry is the first step of virus-host cell interactions leading to productive infection 15 and thus represents an interesting target for antiviral therapy. HCV entry is believed to be a 16 highly orchestrated process involving several viral and host cell factors, thereby offering 17 multiple novel targets for antiviral therapy. However, multiple strategies evolved by the virus 18 in order to escape the host immune system, such as escape from neutralizing antibodies and 19 direct cell-cell transmission, have to be taken into account for the design of efficient novel 20 antiviral strategies. Understanding the mechanisms of viral entry and escape are thus a 21 prerequisite to define viral and cellular targets that will give broad protection against HCV 22 infection.

23

HCV is an enveloped single-strand RNA virus that mainly targets hepatocytes. Due to 24 the difficulty to grow HCV in vitro and the species specificity of this virus, surrogate model 25 systems have been developed to study HCV entry into hepatocytes: recombinant envelope 26 glycoproteins [6], HCV-like particles (HCV-LP) [7], HCV pseudoparticles (HCVpp) [8, 9] and 27 recombinant infectious HCV (HCVcc) [10-12] have been used to study interactions of the 109.

4

viral envelope with human hepatoma cells or primary human hepatocytes. Moreover, the use 1 of transgenic immunodeficient mice with hepatocyte-lethal phenotype (Alb-uPA/SCID [13] 2 and Fah/Rag2/IL2r mice [14]) that can be successfully transplanted with primary human 3 hepatocytes allowed to establish a small animal model to study certain aspects of HCV 4 infection in vivo [15,16].

5

Using the above described model systems, tremendous progress has been made

28

Both E1 and E2 contain putative fusion domains [25,26]. While the role of E1 in HCV 1 entry is not completely understood, several E2 domains play pivotal roles in viral entry, i.e.

7

[28] as well as HCV membrane fusion process [28]. HVR1 is a target for neutralizing 8 antibodies. However, due to its high variability, antibodies targeting HVR1 exhibit poor cross-9 neutralization potency across different HCV isolates [29]. Broadly neutralizing antibodies are 10 directed against conserved conformational epitopes within E2 [30,31] and mostly inhibit E2-

11

CD81 interaction [32]. The region located immediately downstream of HVR1 contains a 12 potent and highly conserved epitope. This epitope defined by the mouse monoclonal 13 antibody (mAb) AP33 and a rat mAb 3/11, is involved in E2-CD81 [33] and E2-heparan 14 sulfate interaction [34]. Importantly, mutated variants that escape from AP33 neutralization 15 show very low infectivity [35]. Recently, new conformational and conserved epitopes were 16 identified in the N-terminal part of E2. Antibodies targeting these epitopes neutralize 17 genetically diverse HCV isolates and protect against heterologous HCV quasispecies 18 challenge in the human liver-chimeric Alb-uPA/SCID mouse model [31]. Since these epitopes 19 are thought to be involved in HCV entry, viral mutation could induce escape from broadly 20 neutralizing antibodies but at a substantial cost in viral fitness [35]. The conserved nature of 21 these epitopes makes them of interest for vaccine and immunotherapeutic development.

22

In vivo, humoral responses are thought to play an important role in controlling HCV 23 infection. Indeed, spontaneous resolvers tend to have early induction of neutralizing antibody 24 responses, whereas chronically evolving subjects have delayed initiation of neutralizing 25 antibody responses [36][37][38]. Furthermore, the generation of cross-reactive humoral 26 responses is associated with protection against HCV reinfection [39]. These data suggest 27 that protective immunity following HCV infection is possible and highlights the plausibility of 28 preventive antiviral strategies including a vaccine [39]. However, the accelerate evolution [40] 1 and diversity of HCV as well as the variety of strategies the virus evolved to escape antibody-2 mediated neutralization (reviewed in [41]) are a major challenge. Indeed, due to its very high 3 replication rate and the highly error prone viral polymerase, HCV circulates as a pool of

27

terminal cytoplasmic tail of SR-BI modulates the basal HCV entry process, but seems not to influence HDL-mediated infection-enhancement whereas the extracellular domain is required 1 for E2 binding and lipid transfer function [72]. Taken together, these results suggest the 2 existence of a complex interplay between lipoproteins, SR-BI and HCV envelope 3 glycoproteins for HCV entry that needs to be taken into account for the development of 4 antivirals targeting SR-BI.

5

CLDN1, a 23 kDa four transmembrane protein, has been identified as a critical HCV 6 hepatocyte entry factor by expression cloning [49]. Interestingly, CLDN6 and CLDN9 are also 7 able to mediate HCV entry in hepatoma cells [START_REF] Sarrazin | Resistance to direct antiviral agents in patients with hepatitis 8 C virus infection[END_REF]74]

13

Mapping studies suggest that the first extracellular loop (ECL1), and more particularly

2

To date, the sequence of events leading from HCV-interaction with host factors on the 3 plasma membrane to internalization, viral fusion and replication still remains elusive. Studies

20

HCV entry into target cells is a promising target for preventive and therapeutic 21 antiviral strategies since it is essential for initiation, spread and maintenance of infection.

22

Interfering with HCV entry holds promise for drug design and offers several targets: (i)

23

blocking virus-target cell interaction during attachment and binding, (ii) interfering with post-24 binding events, and (iii) interfering with viral fusion (Figure 1). Various modalities may be HCV antiviral activity by blocking HCV entry into target cell [112]. As most of the HCV 13 glycosylation sites are highly conserved, drugs that target glycans on HCV glycoproteins may 14 not lead so rapidly to viral escape/resistance as it is the case for HIV [START_REF] Wei | Antibody neutralization 15 and escape by HIV-1[END_REF]. Other

11

These studies suggest that neutralizing antibodies represent an interesting approach for the 12 development of novel preventive and therapeutic antiviral strategies (Table 1). In line with 13 this concept, it has been shown that immunoglobulins prepared from unscreened donors or

28

Targeting the host entry factors, which are indispensable for the propagation of the 1 virus, represents an additional approach for the development of antivirals because they may 2 impose a higher genetic barrier for resistance. HCV interaction with host entry factors offers 3 multiple targets for the development of specific entry inhibitors (Table 1).

4

CD81 is one of these potential targets. Imidazole based compounds mimicking an 5 alpha helix in the LEL of CD81 compete for HCV E2-CD81 binding. These drugs bind E2 in a 6 reversible manner and block E2-CD81 interaction while having no effect on CD81 expression 7 nor on CD81 interaction with physiological partner molecules [START_REF] Rosa | A quantitative 13 test to estimate neutralizing antibodies to the hepatitis C virus: cytofluorimetric assessment of 14 envelope glycoprotein 2 binding to target cells[END_REF]. Interestingly, anti-CD81

24

CLDN1 is a promising antiviral target since it is essential for HCV entry and to date 25 there is no evidence for CLDN1-independent HCV entry. Furthermore, CLDN1 has been

7

Finally, OCLN may also be considered as a potential target for interfering with HCV 8 entry. To date, no anti-OCLN antibodies inhibiting HCV infection have been described.

9

Further characterization of the role of this host cell factor in the HCV entry process may lead 10 to designing compounds interfering with OCLN and inhibiting HCV entry.

11

In addition to cell surface expressed host factors, HCV internalization and fusion are 12 complex processes that also offer several targets for antivirals. Long phosphorothioate 13 oligonucleotides (PS-ON), are a promising new class of antiviral compounds. These

23

(Table 1). Arbidol is a broad-spectrum antiviral that has already been evaluated in humans

11

 HCV entry into hepatocytes depends on clathrin-mediated endocytosis.

12

 HCV appears to be delivered to early but not late endosomes where the acidic pH 13 provides an essential cue that triggers penetration and uncoating.

3

 HCV entry into target cells is a promising target for preventive and therapeutic antiviral 4 strategies since it is essential for initiation, spread and maintenance of infection.

5

 The clinical impact of HCV entry for pathogenesis of HCV infection has been confirmed in 6 clinical cohorts of acute and chronic HCV infection.

6

  over the past years in deciphering the mechanisms of HCV-host interactions leading to viral 7 entry. The understanding of these mechanisms has allowed researchers to identify novel 8 targets for antivirals and several compounds are reaching early clinical development. The 9 aim of this review is to summarize the current knowledge about the complex mechanisms of 10 HCV entry into host cells, highlight antiviral targets and review the current development of 11 HCV entry inhibitors that represent a novel important class of antivirals. Developing efficient 12 HCV entry inhibitors may hold promise to improve sustained virological response in chronic 13 HCV-infected patients and prevent HCV re-infection during LT. 14 15 Hepatitis C virus evades host immune responses to enter the hepatocyte 16 Viral entry is the first step of HCV infection that requires interaction of the HCV envelope 17 glycoproteins E1 and E2 and the host cell membrane. E1 and E2 are type I transmembrane 18 proteins with a N-terminal ectodomain and a short C-terminal transmembrane domain (TMD). 19 Functional virion-associated E1E2 envelope glycoproteins mediating viral entry form large 20 covalent complexes are stabilized by disulfide bridges [17]. The TMD plays a major role in 21 the biogenesis of the E1E2 complexes and membrane fusion process [18]. The N-terminal 22 ectodomains of E1 and E2 are heavily glycosylated. The glycans play a major role in E1E2 23 folding as well as HCV entry [19] and are of crucial importance for the evasion from the host 24 immune responses by masking immunogenic envelope epitopes [20]. Moreover, HCV exists 25 in heterogenous forms in human serum and may be associated with VLDL, LDL and HDL 26 [21-24] also shielding the virus from neutralizing antibodies targeting the HCV envelope 27 glycoproteins.

2

  putative domain binding to two HCV entry factors, CD81 and scavenger receptor class B 3 type I (SR-BI), and escape from host immune responses. Hypervariable regions (HVR) have 4 been identified in E2. The first 27 amino acids of E2 called hypervariable region 1 (HVR1), 5 are most divergent among HCV isolates. HVR1 plays an important role in viral fitness, likely 6 due to an involvement in SR-BI-mediated entry [27], assembly and release of virus particles

4

  genetically distinct but closely related variants known as viral quasispecies. The capacity of 5 HCV to mutate continuously allows a high plasticity, an ability of the virus to adapt to variable 6 environmental conditions and escape the host's immune responses leading to HCV 7 persistence [42, 43]. Noteworthy, a recent longitudinal analysis of six HCV-infected patients 8 undergoing LT suggests that efficient entry and escape from host neutralizing antibodies 9 represent important mechanisms for selection of HCV during LT [43]. As strains selected 10 during LT could be neutralized by broadly neutralizing antibodies, the major challenge for 11 developing efficient antiviral strategies targeting the HCV envelope glycoproteins will be to 12 identify epitopes largely conserved among genotypes and selected isolates.

  uses multiple host factors to enter its target cell 15 HCV attachment and entry into host cells is a complex and multistep process. Using various 16 model systems, several cell surface molecules have been identified interacting with HCV.17These include CD81 [44], the low-density lipoprotein (LDL) receptor [21], highly sulfated 18 heparan sulfate (HS) [45], SR-BI [46], DC-SIGN (dendritic cell-specific intercellular adhesion 19 molecule 3 grabbing non integrin)/L-SIGN (DC-SIGNr, liver and lymph node specific) [47, 20 48], claudin-1 (CLDN1) [49] and occludin (OCLN) [50-52]. 21 In vivo, HCV enters the liver through the sinusoidal blood. Capture of circulating HCV 22 particles by liver sinusoidal cells may thus facilitate viral infection of neighbouring 23 hepatocytes which are not in direct contact with circulating blood. This process may be 24 mediated by DC-SIGN, expressed in Kupffer cells that localize close to liver sinusoidal 25 endothelial cells (LSEC) and hepatocytes [53], and L-SIGN that is highly expressed in LSEC.26 DC-SIGN and L-SIGN have been shown to bind envelope glycoprotein E2 with high affinity 7 55] that may help to concentrate the virus on the target cell surface and allow further 1 interactions with other host factors triggering viral entry. 2 CD81 is a ubiquitously expressed 25 kDa tetraspanin, containing a small extracellular 3 and a large extracellular loop (LEL). CD81 has been the first molecule described to interact 4 with a soluble truncated form of HCV E2 and to be a critical host cell factor for viral entry [11, 5 56, 57]. The LEL seems to play an important role in this process as soluble recombinants 6 forms of CD81 LEL have been shown to inhibit HCVpp and HCVcc infection [58]. Several 7 amino acid residues critical for E2-CD81 binding have been identified throughout the CD81 8 LEL and HCV E2 [33, 44, 59-61]. In recent years, studies using HCVpp and HCVcc have 9 provided additional valuable information about E2-CD81 interactions and highlighted the 10 importance of E2 residues at positions 415, 420, 527, 529, 530, 535 [62, 63] for virus 11 particle-CD81 interaction. 12 Human SR-BI or CLA-1 (CD36 and LIMPII Analogous-1) is a 82 kDa glycoprotein with 13 a large extracellular loop highly expressed in the liver and steroidogenic tissues [64]. SR-BI 14 binds a variety of lipoproteins (HDL, LDL, oxLDL) and is involved in bidirectional cholesterol 15 transport at the cell membrane. The SR-BI extracellular loop has been demonstrated to 16 interact with E2 HVR1 [46]. Recent evidence suggests that amino acids 70 to 87 and the 17 single residue E210 of SR-BI are required for E2 recognition [65]. SR-BI may play a dual role 18 during the HCV entry process, during both binding and postbinding steps [65, 66]. 19 Physiological SR-BI ligands have been shown to modulate HCV infection: HDL is able to 20 enhance HCVpp and HCVcc infection [67, 68] whereas oxidized LDL inhibits HCVpp and 21 HCVcc infection [69]. Interestingly, high concentrations of HDL and LDL inhibited HCV 22 replication in human hepatocytes infected with serum-derived HCV [70]. Moreover, using 23 serum-derived HCV, it has been suggested that the virus-associated lipoproteins rather than 24 the E2 protein interact with SR-BI on transfected CHO cells [71]. A recent mapping study 25 reported that HCV and HDL binding to SR-BI as well as the lipid transfer properties of SR-BI 26 are required for SR-BI function as HCV entry factor [72]. This study also suggests that the C-

14

  residues in the highly conserved claudin motif W(30)-GLW(51)-C(54)-C(64), are critical for 15 HCV entry [49, 77]. CLDN1 associates to CD81 in a variety of cell types and the formation of 16 CLDN1-CD81 complexes is essential for HCV infection [79, 80]. Mutations at residues 32 17 and 48 in CLDN1 ECL1 ablate the association with CD81 and the viral receptor activity [80]. 18 OCLN has been identified as another host cell factor critical for HCV entry, probably 19 at a late post-binding event [50, 51, 81]. OCLN is a 65 kDa four transmembrane protein 20 expressed in TJ of polarized cells. To date, there is no evidence of a direct interaction with 21 HCV. It is worth noting that OCLN has been reported to be one of the two HCV host entry 22 factors responsible for the species specificity of HCV: expression of human OCLN and 23 human CD81 may confer HCV permissivity to mouse cell lines [50]. The species-specific 24 determinants of this protein have been mapped to the second extracellular loop [50]. 25 Interestingly, OCLN expression on hepatocytes as well as HCV entry are increased upon 26 glucocorticoid treatment [82] while OCLN expression is downregulated upon HCV infection to prevent superinfection [51]. Further studies are needed to decipher the interplay between 1 HCV, OCLN and the other known host factors. 2 As HCV circulates in the blood in association with LDL and very low-density 3 lipoproteins (VLDL), the LDL receptor has also been proposed as an attachment and/or entry 4 factor for HCV [21, 83]. As HCVpp are not associated with lipoproteins, studies investigating 5 the role of LDLR in HCVpp entry did not show a major role for LDLR [8]. Moreover, no direct 6 interaction between envelope glycoprotein E2 and LDL or LDLR was demonstrated [83]. 7 However, the LDLR has been shown to mediate internalization of serum-derived HCV into 8 CD81-deficient HepG2 cells by binding virus-LDL particles [21]. This will have to be taken 9 into account for the development of antiviral therapies targeting HCV host factors. 10 11 HCV entry is a multistep process 12 In vivo, HCV most likely first interacts with the basolateral surfaces of hepatocytes. HS 13 glycosaminoglycans represent first attachment sites [34, 45, 55] before the virus interacts 14 with several entry factors, SR-BI [27, 46, 66, 68, 84], CD81 [44, 55], CLDN1 [49, 78] and 15 OCLN [50-52] (Figure 1). It is worth noting that all these entry factors are required for 16 productive HCV infection. This suggests that HCV entry may be mediated through the 17 formation of a tightly orchestrated HCV-entry factor complex at the plasma membrane [66, 18 78]. First evidence for such co-entry factor complexes has been provided by fluorescence 19 resonance energy transfer (FRET) studies demonstrating the role of CLDN1-CD81 20 complexes in HCV infection [79, 80]. The fact that only members of the CLDN family 21 supporting HCV entry, i. e. CLDN1, CLDN6 and CLDN9, were able to form complexes with 22 CD81 suggests that CLDN-CD81 complex formation is essential for HCV entry [78, 80]. To 23 date, our knowledge about the molecular mechanisms of potential other co-factor 24 association(s) is still rudimental. First studies showed that the majority of CLDN1 proteins at 25 the plasma membrane interact with OCLN but did not show any relationship between 26 CLDN1-OCLN association and HCV infection [80]. In addition, it has been demonstrated that 27 cell contacts modulate SR-BI and CLDN1 expression levels and favours HCV internalization 28 through facilitation of entry factor complexes [85]. Further studies are thus necessary to 1 assess which set of host factors are present with HCV in these complexes.

4

  using HCVpp and HCVcc have demonstrated that HCV entry into both hepatoma cells and 5 primary human hepatocytes depends on clathrin-mediated endocytosis [86-90], the most 6 commonly route of endocytosis for viruses that require internalization. Moreover, actin and 7 clathrin-actin associations have also been shown to be involved in efficient HCV endocytosis 8 [90]. The question whether all or part of the plasma membrane expressed HCV host factors 9 internalize together with HCV still remains unanswered. A recent study suggests that during 10 internalization, HCV associates with CD81 and CLDN1 [90]. Moreover, PKA has been 11 suggested to play a role during this process as inhibition of PKA lead to reorganization of 12 CLDN1 from the plasma membrane to intracellular vesicular location(s) and disrupted CD81-13 CLDN1 co-receptor association [91]. Interestingly, in line with the fact that polarization 14 restricts HCV entry [92] and that HCV co-entry factors are co-expressed on basolateral sites 15 of hepatocytes but not at TJ [76], imaging studies suggest that HCV internalization does not 16 preferentially take place at sites of cell-cell contacts [90].

  17

  Clathrin-mediated endocytosis transports incoming viruses together with their 18 receptors into early and late endosomes [93]. HCVpp have been suggested to be delivered 19 to early but not late endosomes [87]. This is in line with recent imaging data showing 20 colocalization between HCV and Rab5a, an early endosome marker [90]. The acidic pH in 21 endosomes provides an essential cue that triggers penetration and uncoating. Penetration of 22 enveloped virus occurs by membrane fusion catalyzed by fusion peptides embedded in the 23 viral envelope glycoproteins [94]. To date, the mechanisms of HCV fusion have not been 24 completely elucidated but it has been suggested that similar fusion mechanisms as 25 described for other flaviviridae may apply to HCV [95-98]. This hypothesis is supported by 26 the observation that HCVpp entry [8, 9, 99] and HCVcc infection [86, 100] are pH-dependent, 27 suggesting that a pH-dependent membrane fusion process may be required for delivery of 28 the HCV genome into the host cell cytosol. It is worth noting that although HCV entry 1 requires an acidification step, extracellular HCV is resistant to low pH treatment [87, 100]. As 2 HCV fusion kinetics are delayed as compared to other viruses, it has been suggested that 3 after internalization, HCVpp entry necessitates additional, low-pH-dependent interactions, 4 modifications, or trafficking [87]. However, neither HCVpp nor HCVcc require cleavage by 5 endosomal proteases for fusion [87, 100]. Several in vitro fusion assays have been set up in 6 the last years [25, 26, 49, 99]. Liposome/HCVpp fusion assays suggest that HCVpp-induced 7 fusion was low pH and temperature dependent and facilitated by cholesterol [99]. 8 Interestingly, patient-derived anti-HCV antibodies were able to inhibit liposome/HCVpp fusion 9 [101] highlighting the importance of HCV envelope glycoproteins in this process. These data 10 have been recently confirmed in a novel liposome/HCVcc fusion assay showing that HCVcc 11 fusion was dependent on pH, lipid composition of both viral and target membranes and HCV 12 E2 [102]. However, in this kind of assay no host cell factor is necessary to allow fusion to 13 occur. To study the role of both viral and host factors in HCV fusion, cell-cell fusion assays 14 have been used where HCV envelope glycoproteins are expressed on one cell type and host 15 entry factors on another cell type [25]. Cell-cell fusion assays are also pH-dependent and 16 most interestingly, these assays highlighted the importance of CD81 and CLDN1 in this 17 process [25, 49]. To date, it still remains unclear whether these host factors directly 18 participate in the HCV fusion process or whether they play a role in an earlier entry steps 19 required to enable efficient subsequent fusion. Taken together, these data suggest that HCV 20 internalization and fusion offer multiple targets for the development of HCV entry inhibitors. 21 22 An alternative route of entry and spread by cell-cell transmission 23 The above described entry mechanisms have been unravelled using cell-free HCV, i. e. the 24 virus infects surrounding cells after the formation of viral particles that are released from 25 infected cells and enter naïve cells by a host factor-dependent mechanism. In addition, 26 viruses may also use direct cell-cell transfer to infect neighbouring cells [93] thereby 27 escaping potential interaction with neutralizing antibodies in the extracellular milieu.28 1 described for HCV [103]. CLDN1, CD81 and probably SR-BI are involved in this process [85, 2 103]. Interestingly, CD81-independent routes of cell-cell transport have also been described 3 [103, 104]. Direct cell-cell transfer has an important impact for the development of antivirals 4 as this process allows viral spreading by escaping extracellular neutralizing antibodies as 5 well as defined antibodies interfering with host cell entry factors. It will be challenging to 6 develop novel anti-HCV therapeutics interfering with this process.

7 8

 7 Viral entry offers promising targets for antiviral therapy 9In contrast to the current standard of care therapy for HCV infection, new therapeutic 10 approaches aim at the development of more specific compounds targeting the virus and/or 11 host cell factors. This represents the concept of specifically targeted antiviral therapy for HCV 12 (STAT-C). This concept consists in developing more efficient and better tolerated 13 combination therapies that need shorter treatment periods. To date, several small molecule 14 compounds targeting the HCV non-structural proteins including protease, polymerase and 15 NS5A have been developed and are at various stages of clinical development [1-3, 105].16First clinical trial data are promising but toxicity of the individual compounds and emergence 17 of resistance against these drugs limit their use in monotherapy. This suggests that 18 additional drugs, ideally targeting different steps of the viral life cycle, are needed for efficient 19 anti-HCV therapy.

  25 developed as HCV entry inhibitors: these include neutralizing antibodies targeting the viral 26 envelope and inhibitory/blocking antibodies targeting host cell surface factors as well as 27 small molecule compounds or siRNAs against host cell factors or viral proteins [106, 107]. 28 Several non-HCV specific molecules interfering with HCV envelope glycoproteins and 1 abrogating viral attachment have been described. As HCV envelope proteins are highly 2 glycosylated, molecules interfering with glycoproteins may possess antiviral activity against 3 HCV. As shown for HIV, targeting the glycans may represent a new therapeutic concept for 4 controlling HCV infection [108]. Carbohydrate-binding agents that interact with the viral-5 envelope glycans may compromise the efficient entry of the virus into its susceptible target 6 cells and induce a progressive creation of deletions in the envelope glycan shield, thereby 7 triggering the immune system to act against previously hidden immunogenic epitopes of the 8 viral envelope [108]. The lectin cyanovirin-N (CV-N) interacts with high-mannose 9 oligosaccharides on viral envelope glycoproteins and has been demonstrated to have 10 antiviral activity against several enveloped viruses [109-111]. It has been shown that 11 oligomannose glycans within the HCV envelope glycoproteins interact with CV-N resulting in

  12

  15 carbohydrate-binding agents that have been shown to prevent HIV infectivity [108] might also 16 be efficient against other viruses that require a glycosylated envelope for entry into target 17 cells. Interfering with interaction of viral envelope proteins and glycosaminoglycans on the 18 cell surface is another way to abrogate viral attachment. HS glycosaminoglycans mediate 19 HCV and dengue virus binding to host cells and heparin, a structural analogue of HS, has 20 been demonstrated to inhibit dengue virus infection as wells as HCV E2, HCVpp, HCV-LP 21 and HCVcc binding to hepatoma cells [34, 45, 55, 114]. HS-like molecules and semisynthetic 22 derivatives are already explored as an antiviral approach against dengue virus infection 23 [115]. Such molecules may also have antiviral activity against HCV. 24 Neutralization of the viral particle may be achieved by targeting the HCV envelope or 25 host derived factors associated with the mature viral particle. The molecular mechanisms of 26 viral assembly and the exact composition of released HCV particles still remain elusive but 27 recent studies suggest that HCV and VLDL assembly are closely linked [116, 117].14 Noteworthy, apolipoprotein E (apoE) is required for HCV assembly[118, 119] and is also part 1 of infectious HCV particles[118]. Interestingly, anti-apoE antibodies are able to inhibit HCV 2 entry[21, 118] suggesting that HCV may be neutralized using compounds directed against 3 the lipoprotein moiety of the viral particle (Table1).

4

  Viral attachment and entry is a major target of adaptive host cell defenses and anti-5HCV antibodies represent unique tools to interfere with the HCV entry process. Virus-specific 6 neutralizing antibodies are defined by their antiviral activity enabling them to block viral entry 7 and control viral spread. Neutralizing antibodies may interfere with different steps of the viral 8 entry process such as attachment, post-binding steps and fusion [120]. Two studies of large-9 scale accidental HCV infections demonstrated that rapid induction of neutralizing antibodies 10 in the early phase of infection correlates with viral clearance or control of infection [36, 38].

14

  from selected patients with chronic HCV infection have prevented HCV infection in recipients 15 when administered before exposure to the virus [6, 121]. Moreover, administration of 16 polyclonal immunoglobulins from a chronically infected patient conveyed sterilizing immunity 17 toward a homologous strain in human liver-chimeric Alb-uPA/SCID mouse model [122]. 18 Human mAbs provide an attractive alternative to polyclonal immune globulin for 19 immunotherapy, since mAbs can be more readily standardized. The recent production of 20 human mAbs efficiently cross-neutralizing HCV may represent an important step for the 21 development of immunopreventive strategies against HCV infection [31, 123-125] as such 22 antibodies have been demonstrated to protect against HCV quasispecies challenges in vivo 23 in the human liver-chimeric Alb-uPA/SCID mouse model [31] (Table1). However, due to the 24 high variability of HCV, it will be a major challenge to develop efficient cross-neutralizing 25 antibodies able to target conserved epitopes across all genotypes to avoid escape.

8

  antibodies inhibiting HCV infection in vitro have also been demonstrated to prevent HCV 9 infection in the human liver-chimeric Alb-uPA/SCID mouse model[127]. This study suggests 10 that targeting CD81 may be an efficient strategy to prevent HCV infection in vivo and 11 demonstrates the proof-of-concept that anti-receptor antibodies prevent HCV infection in a 12 clinically relevant animal model,.

13SR-

  BI binds a wide variety of molecules and is thus another interesting target for anti-14 HCV drugs. SR-BI binds and internalizes serum amyloid A (SAA), an acute phase protein 15 produced in the liver [128, 129]. SAA inhibits HCV entry by interacting with the virus thereby 16 reducing its infectivity [130]. Anti-SR-BI antibodies blocking interaction with HCV are another 17 interesting strategy to prevent HCV entry. Anti-SR-BI antibodies have been demonstrated to 18 inhibit HCVcc infection in vitro [66, 67, 131]. Finally, small molecule inhibitors of SR-BI have 19 recently been developed. ITX5061 is a compound that inhibits entry of HCVpp from all major 20 genotypes and HCVcc infection without affecting viral replication [132]. Kinetic studies 21 suggest that this small molecule inhibitor targets HCV entry during an early post-binding 22 stage [132]. The safety of this compound has been evaluated in patients for another clinical 23 indication [132] allowing future clinical trials in HCV infected patients.

  26 suggested to play an important role in cell-cell transmission. In contrast to other HCV entry 27 factors such as CD81 or SR-BI, CLDN1 is predominantly expressed in the liver. Recently, 28 anti-CLDN1 antibodies inhibiting HCV infection in vitro have been developed [78, 133]. Anti-1 CLDN1 antibodies inhibit HCV infectivity by reducing HCV E2 association with the cell 2 surface and disrupting CLDN1-CD81 interactions [78]. Interestingly, monoclonal anti-CLDN1 3 antibodies efficiently block cell entry of highly infectious escape variants of HCV that are 4 resistant to host neutralizing antibodies [133]. These data suggest that anti-CLDN1 5 antibodies might be used to prevent HCV infection, such as after liver transplantation, and 6 might also restrain virus spread in chronically infected patients. [133].

  14 amphipathic DNA polymers display a sequence-independent antiviral activity against HIV by 15 blocking virus-cell fusion [134]. A recent study demonstrated that PS-ON inhibited HCV 16 internalization without affecting viral binding and replication [135]. Noteworthy, PS-ON block 17 de novo HCV infection in the human liver-chimeric Alb-uPA/SCID mouse model [135] 18 highlighting the promise of PS-ON as future clinical HCV entry inhibitors (Table 1). A peptide-19 based HIV fusion inhibitor (Enfuvirtide) has already been approved for treatment of HIV 20 infected patients [136]. As HCV fusion requires acidification of the endosome, molecules able 21 to prevent acidification of endosomes, such as chloroquine, prevent HCV fusion in vitro [86, 22 100]. In the last years, other compounds interfering with HCV fusion have been described

24

  indicating good safety and tolerability (for review see[137]). Arbidol inhibits HCV fusion in the 25 HCVpp-liposome assay and prevents HCVpp and HCVcc infection in vitro [137]. In addition, 26 this molecule also targets other steps of the viral life cycle such as replication [138]. 27 Silymarin is another compound inhibiting HCVpp-liposome fusion as well as other steps of 28 the HCV life cycle, such as replication, protein expression and infectious virus production 1 without affecting viral assembly [139, 140]. Interestingly, silymarin inhibited HCV infection in 2 vitro irrespective of the entry route, i. e. cell-free and cell-cell transmission [140], highlighting 3 the potential of such drugs for in vivo use.

6

  In recent years, substantial progress unravelling the molecular mechanisms of HCV entry 7 has been made and revealed a multitude of novel targets for antivirals. Several compounds 8 interfering with HCV entry have been demonstrated to efficiently inhibit HCV infection using 9 in vitro assays or state of the art animal models and may thus be valuable for future anti-HCV 10 therapy or prevention of HCV infection during LT. As for other chronic viral infections such as 11 HIV, the future therapeutic and preventive approach for HCV infection will probably be based 12 on the combination of several drugs [2, 3]. HCV entry inhibitors represent a promising class 13 of novel antivirals since they are complementary to current approaches and target an 14 essential step of the viral life cycle. Indeed, the first compounds have reached the early stage 15 of clinical development. Moreover, recent data suggest that combination of antivirals 16 targeting the virus and host factors such as CLDN1 act in an additive manner in suppressing 17 HCV infection [133]. Thus, combining compounds targeting viral and host cell factors and 18 complementary steps of the viral life cycle such as entry and replication is a promising 19 approach for prevention of infection in LT and cure of chronic HCV infection.

4

  , Lindenbach BD, Boullier A, Quehenberger O, Paulson M, Rice CM, et al. Oxidized low-density lipoprotein inhibits hepatitis C virus cell entry in human hepatoma cells. Castet V, Fournier-Wirth C, Pichard-Garcia L, Avner R, Harats D, et al. The 7 low-density lipoprotein receptor plays a role in the infection of primary human hepatocytes by 8 hepatitis C virus. J Hepatol 2007;46:411-419.9 71. Maillard P, Huby T, Andreo U, Moreau M, Chapman J, Budkowska A. The interaction 10 of natural hepatitis C virus with human scavenger receptor SR-BI/Cla1 is mediated by ApoB-11 containing lipoproteins. Faseb J 2006;20:735-737.

  Dao Thi VL, Fresquet J, Guerin M, Julia Z, Verney G, et al. Receptor 13 complementation and mutagenesis reveal SR-BI as an essential HCV entry factor and 14 functionally imply its intra-and extra-cellular domains. PLoS Pathog 2009;5:e1000310.

  Yuan F, Li Y, Zhu F, Hou P, Li J, et al. Claudin-6 and claudin-9 function as 16 additional coreceptors for hepatitis C virus. J Virol 2007;81:12465-12471.

  17

  Bertaux C, Cukierman L, Cormier E, Lavillette D, Cosset FL, et al. The 18 tight junction proteins claudin-1, -6, and -9 are entry cofactors for hepatitis C virus. J Virol 19 2008;82:3555-3560.20 75. Furuse M, Fujita K, Hiiragi T, Fujimoto K, Tsukita S. Claudin-1 and -2: novel integral 21 membrane proteins localizing at tight junctions with no sequence similarity to occludin. J Cell 22 Biol 1998;141:1539-1550. 23 76. Reynolds GM, Harris HJ, Jennings A, Hu K, Grove J, Lalor PF, et al. Hepatitis C virus 24 receptor expression in normal and diseased liver tissue. Hepatology 2008;47:418-427.

  Meertens L, Bertaux C, Kajumo F, Dragic T. Residues in a highly 26 conserved claudin-1 motif are required for hepatitis C virus entry and mediate the formation

7 149 .8Figure 1 .

 1491 Figure legend

3and host cell factors. 3 

 3 process are depicted, followed by examples of compounds targeting the respective entry 4 step. Stage of development and references are indicated. CLDN: claudin; mAb: monoclonal 5 antibody; pAb: polyclonal antibodies; SR-BI: scavenger receptor class B type I; PS-ON: HCV entry into hepatocytes is a highly coordinated and multistep process requiring viral 2 The viral envelope glycoproteins E1 and E2 are essential for HCV entry.

4 6 

 6 Lipoproteins have been shown to associate with the viral particle and interfere with viral 5 entry. Host factors mediating viral attachment and binding to hepatocytes include highly 7 sulfated heparan sulfate and the low-density lipoprotein receptor. 8 CD81, scavenger receptor BI and the tight junction proteins caudin-1 and occludin act on 9 a postbinding step and are essential for HCV entry.10 Host factors such as CD81 and CLDN1 form co-receptor complexes.

14

  An alternative route of viral entry is direct cell-cell transmission which is resistant to 15 New therapeutic approaches for HCV infection aim at the development of more specific 2 compounds targeting the virus and/or host cell factors.

7

  Interfering with HCV entry offers several targets including attachment/binding, post-8 binding events and viral fusion.

9 15 

 15 Entry inhibitors comprise neutralizing antibodies targeting the viral envelope, 10 inhibitory/blocking antibodies targeting host cell surface factors as well as small 11 molecules, peptides and siRNAs. 12 HCV entry inhibitors are a promising class of novel antivirals since they are 13 complementary to current approaches focussing on viral protein processing and 14 replication. Combining compounds targeting viral and host cell factors and complementary steps of 16 the viral life cycle will increase the genetic barrier to resistance.

26

  Examples for neutralizing antibodies in preclinical or clinical development are provided in 27

Table 1 .

 1

Table Legend 1 2 Table 1 .

 Legend21 Examples of compounds targeting viral entry. Targets within the HCV entry

[47, 54]. On hepatocytes, HS glycosaminoglycans represent first attachment sites[34, 45,

Complete replication of hepatitis C virus in cell culture. Science 2005;309:623-626.

control of primary hepatitis C virus infection and immunity against persistent reinfection.

Gastroenterology 2010;138:315-324.

and production of hepatitis C virus in cell culture. J Virol 2007;81:13783-13793.

Acknowledgements