Regular expression constrained sequence alignment

We introduce regular expression constrained sequence alignment as the problem of finding the maximum alignment score between given strings $S_1$ and $S_2$ over all alignments such that in these alignments there exists a segment where some substring $s_1$ of $S_1$ is aligned to some substring $s_2$ of $S_2$, and both $s_1$ and $s_2$ match a given regular expression R, i.e. $s_1,s_2\in L(R)$ where $L(R)$ is the regular language described by R. For complexity results we assume, without loss of generality, that $n=|S_1|⩾|m|=|S_2|$. A motivation for the problem is that protein sequences can be aligned in a way that known motifs guide the alignments. We present an $\mathrm{O}(nmr)$ time algorithm for the regular expression constrained sequence alignment problem where $r=\mathrm{O}(t^4)$, and t is the number of states of a nondeterministic finite automaton N that accepts $L(R)$. We use in our algorithm a nondeterministic weighted finite automaton M that we construct from N. M has $\mathrm{O}(t^2)$ states where the transition-weights are obtained from the given costs of edit operations, and state-weights correspond to optimum alignment scores we compute using the underlying dynamic programming solution for sequence alignment. If we are given a deterministic finite automaton D accepting $L(R)$ with $t_d$ states then our construction creates a deterministic finite automaton $M_d$ with $t_d^2$ states. In this case, our algorithm takes $\mathrm{O}(t_d^{2}nm)$ time. Using $M_d$ results in faster computation than using M when $t_d<t^2$. If we only want to compute the optimum score, the space required by our algorithm is $\mathrm{O}(t^{2}n)$ ($\mathrm{O}(t_d^{2}m)$ if we use a given $M_d$). If we also want to compute an optimal alignment then our algorithm uses $\mathrm{O}(t^{2}m+t^2|s_1||s_2|)$ space ($\mathrm{O}(t_d^{2}m+t_d^2|s_1||s_2|)$ space if we use a given $M_d$) where $s_1$ and $s_2$ are substrings of $S_1$ and $S_2$, respectively, $s_1,s_2\in L(R)$, and $s_1$ and $s_2$ are aligned together in the optimal alignment that we construct. We also show that our method generalizes for the case of the problem with affine gap penalties, and for finding optimal regular expression constrained local sequence alignments.     

Inviscid limit for the derivative Ginzburg–Landau equation with small data in modulation and Sobolev spaces

Applying the frequency-uniform decomposition technique, we study the Cauchy problem for derivative Ginzburg–Landau equation $u_t=(\nu +\mathrm{i})\mathrm{\Delta }u+{\overrightarrow{\lambda }}_1?\mathrm{?}({|u|}^{2}u)+({\overrightarrow{\lambda }}_2?\mathrm{?}u){|u|}^2+\alpha {|u|}^{2\delta }u$, where $\delta \in \mathbb{N}$, ${\overrightarrow{\lambda }}_1,{\overrightarrow{\lambda }}_2$ are complex constant vectors, $\nu \in [0,1]$, $\alpha \in \mathbb{C}$. For $n\ge 3$, we show that it is uniformly global well posed for all $\nu \in [0,1]$ if initial data $u_0$ in modulation space $M_{2,1}^s$ and Sobolev spaces $H^{s+n/2}$ ($s>3$) and $6u_0{6}_{L^2}$ is small enough. Moreover, we show that its solution will converge to that of the derivative Schrödinger equation in $C(0,T;L^2)$ if $\nu \to 0$ and $u_0$ in $M_{2,1}^s$ or $H^{s+n/2}$ with $s>4$. For $n=2$, we obtain the local well-posedness results and inviscid limit with the Cauchy data in $M_{1,1}^s$ ($s>3$) and $6u_0{6}_{L^1}?1$.     

Large-time geometrical properties of solutions of the Barenblatt equation of elasto-plastic filtration

We study the geometric behavior for large times of the solutions of the following equation$u_t+\gamma |u_t|=\mathrm{\Delta }u,0<|\gamma |<1,$ posed in the whole space ${\mathbb{R}}^N$, for $N?1$ when the initial data are nonnegative, continuous and compactly supported. We prove that, after a finite time, $\log (u)$ becomes a concave function in the space variable and converges to all orders of differentiability to a certain parabolic shape, so-called Barenblatt-type profile, which was described in Kamin et al. (1991) [20]. Extensions to more general fully nonlinear equations are considered.     

On sub-harmonic bifurcations

Under fairly general hypotheses, we investigate by elementary methods the structure of the p-periodic orbits of a family $h_u$ of transformations near $(u_0,x_0)$ when $h_{u_0}(x_0)=x_0$ and $\mathrm{d}{h}_{u_0}(x_0)$ has a simple eigenvalue which is a primitive p-th root of unity. To cite this article: M. Chaperon et al., C. R. Acad. Sci. Paris, Ser. I 340 (2005).     

Dynamics of epidemics in homogeneous/heterogeneous populations and the spreading of multiple inter-related infectious diseases: Constant-sign periodic solutions for the discrete model

We consider the following model that describes the dynamics of epidemics in homogeneous/heterogeneous populations as well as the spreading of multiple inter-related infectious diseases:$u_i(k)=\sum _{\ell =k-{\tau }_i}^{k-1}{g}_i(k,\ell )f_i(\ell ,u_1(\ell ),u_2(\ell ),\dots ,u_n(\ell )),k\in \mathbf{Z},1⩽i⩽n\text{.}$Our aim is to establish criteria such that the above system has one or multiple constant-sign periodic solutions $(u_1,u_2,\dots ,u_n)$, i.e., for each $1⩽i⩽n$, $u_i$ is periodic and ${\theta }_i{u}_i⩾0$ where ${\theta }_i\in \{1,-1\}$ is fixed. Examples are also included to illustrate the results obtained.     

On low-dimensional cancellation problems

A well-known cancellation problem of Zariski asks when, for two given domains (fields) $K_1$ and $K_2$ over a field k, a k-isomorphism of $K_1[t]$ ($K_1(t)$) and $K_2[t]$ ($K_2(t)$) implies a k-isomorphism of $K_1$ and $K_2$. The main results of this article give affirmative answer to the two low-dimensional cases of this problem:1. Let K be an affine field over an algebraically closed field k of any characteristic. Suppose $K(t)?k(t_1,t_2,t_3)$, then $K?k(t_1,t_2)$.2. Let M be a 3-dimensional affine algebraic variety over an algebraically closed field k of any characteristic. Let $A=K[x,y,z,w]/M$ be the coordinate ring of M. Suppose $A[t]?k[x_1,x_2,x_3,x_4]$, then $\mathrm{frac}(A)?k(x_1,x_2,x_3)$, where $\mathrm{frac}(A)$ is the field of fractions of A.In the case of zero characteristic these results were obtained by Kang in [Ming-chang Kang, A note on the birational cancellation problem, J. Pure Appl. Algebra 77 (1992) 141–154; Ming-chang Kang, The cancellation problem, J. Pure Appl. Algebra 47 (1987) 165–171]. However, the case of finite characteristic is first settled in this article, that answered the questions proposed by Kang in [Ming-chang Kang, A note on the birational cancellation problem, J. Pure Appl. Algebra 77 (1992) 141–154; Ming-chang Kang, The cancellation problem, J. Pure Appl. Algebra 47 (1987) 165–171].     

Diffusion versus absorption in semilinear parabolic problems

We study the limit, when $k\to \infty$, of the solutions $u=u_k$ of (E) ${?}_{t}u?\mathrm{\Delta }u+h(t)u^q=0$ in ${\mathbb{R}}^N\times (0,\infty )$, $u_k(?,0)=k{\delta }_0$, with $q>1$, $h(t)>0$. If $h(t)={\mathrm{e}}^{?\omega (t)/t}$ where $\omega >0$ satisfies to ${\int }_0^1\sqrt{\omega (t)}{t}^{\mathrm{?1}}\mathrm{d}t<\infty$, the limit function $u_{\infty }$ is a solution of (E) with a single singularity at $(0,0)$, while if $\omega (t)\equiv 1$, $u_{\infty }$ is the maximal solution of (E). We examine similar questions for equations such as ${?}_{t}u?\mathrm{\Delta }{u}^m+h(t)u^q=0$ with $m>1$ and ${?}_{t}u?\mathrm{\Delta }u+h(t){\mathrm{e}}^u=0$. To cite this article: A. Shishkov, L. Véron, C. R. Acad. Sci. Paris, Ser. I 342 (2006).     

Régularité conditionnelle des équations de Navier–Stokes

In this Note, we give sufficient conditions for the regularity of Leray–Hopf weak solutions to the Navier–Stokes equation. We prove that, if one of three conditions (i) $?u/?x_3\in L_t^{s_0}{L}_x^{r_0}$ where $2/s_0+3/r_0?2$ and $9/4?r_0?3$, (ii) $\mathrm{?}{u}_3\in L_t^{s_1}{L}_x^{r_1}$ where $2/s_1+3/r_1?11/6$ and $54/23?r_0?18/5$, or (iii) $u_3\in L_t^{s_0}{L}_x^{r_0}$ where $2/s_0+3/r_0?5/8$ and $24/5?r_0?\infty$, is satisfied, then the solution is regular. These conditions improve earlier results on the conditional regularity of the Navier–Stokes equations. To cite this article: I. Kukavica, M. Ziane, C. R. Acad. Sci. Paris, Ser. I 343 (2006).     

The coloring complex and cyclic coloring complex of a complete k-uniform hypergraph

In this paper, we study the homology of the coloring complex and the cyclic coloring complex of a complete k-uniform hypergraph. We show that the coloring complex of a complete k-uniform hypergraph is shellable, and we determine the rank of its unique nontrivial homology group in terms of its chromatic polynomial. We also show that the dimension of the $(n?k?1)\text{st}$ homology group of the cyclic coloring complex of a complete k-uniform hypergraph is given by a binomial coefficient. Further, we discuss a complex whose r-faces consist of all ordered set partitions $[B_1,\dots ,B_{r+2}]$ where none of the $B_i$ contain a hyperedge of the complete k-uniform hypergraph H and where $1\in B_1$. It is shown that the dimensions of the homology groups of this complex are given by binomial coefficients. As a consequence, this result gives the dimensions of the multilinear parts of the cyclic homology groups of $\mathbb{C}[x_1,\dots ,x_n]/\{x_{i_1}\dots x_{i_k}|i_1\dots i_k\text{is a hyperedge of}H\}$.     

Some asymptotic properties for solutions of one-dimensional advection–diffusion equations with Cauchy data in Lp(R)

We state and discuss a number of fundamental asymptotic properties of solutions $u(?,t)$ to one-dimensional advection–diffusion equations of the form $u_t+f{(u)}_x=(a{(u)u_x)}_x$, $x\in \mathbb{R}$, $t>0$, assuming initial values $u(?,0)=u_0\in L^p(\mathbb{R})$ for some $1?p<\infty$. To cite this article: P. Braz e Silva, P.R. Zingano, C. R. Acad. Sci. Paris, Ser. I 342 (2006).     

Distance-preserving approximations of polygonal paths

Given a polygonal path P with vertices $p_1,p_2,\dots ,p_n\in {\mathbb{R}}^d$ and a real number $t⩾1$, a path $Q=(p_{i_1},p_{i_2},\dots ,p_{i_k})$ is a t-distance-preserving approximation of P if $1=i_1<i_2<\cdots <i_k=n$ and each straight-line edge $(p_{i_j},p_{i_{j+1}})$ of Q approximates the distance between $p_{i_j}$ and $p_{i_{j+1}}$ along the path P within a factor of t. We present exact and approximation algorithms that compute such a path Q that minimizes k (when given t) or t (when given k). We also present some experimental results.