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.     

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].     

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).     

Gorenstein injective complexes of modules over Noetherian rings

A complex C is called Gorenstein injective if there exists an exact sequence of complexes $?\to I_{\mathrm{?1}}\to I_0\to I_1\to ?$ such that each $I_i$ is injective, $C=\mathrm{Ker}(I_0\to I_1)$ and the sequence remains exact when $\mathrm{Hom}(E,?)$ is applied to it for any injective complex E. We show that over a left Noetherian ring R, a complex C of left R-modules is Gorenstein injective if and only if $C^m$ is Gorenstein injective in R-Mod for all $m\in \mathbb{Z}$. Also Gorenstein injective dimensions of complexes are considered.     

Gabor systems and almost periodic functions

Inspired by results of Kim and Ron, given a Gabor frame in $L^2(\mathbb{R})$, we determine a non-countable generalized frame for the non-separable space ${\mathit{AP}}_2(\mathbb{R})$ of the Besicovic almost periodic functions. Gabor type frames for suitable separable subspaces of ${\mathit{AP}}_2(\mathbb{R})$ are constructed. We show furthermore that Bessel-type estimates hold for the AP norm with respect to a countable Gabor system using suitable almost periodic norms of sequences.     

Un théorème de Liouville pour l'opérateur de Schrödinger avec dérive

Let $(M,g)$ be a complete Riemannian manifold without boundary of dimension n and V be a $C^2$ vector field on M such that $r(x)|V(x)|$ is bounded. Suppose that ${\mathrm{Ric}}_g(x)??\min \{\lambda (r(x))?{\mu }_{\mathrm{?}V}(x),\beta (r(x))\}$ outside a compact set of M, where ${\mu }_{\mathrm{?}V}$ denotes the upper eigenvalue of ?V and $\lambda ,\beta$ are non-negative decreasing functions such that ${\lim }_{t\to +\infty }{t}^2\lambda (t)=0$. There exists positive numbers $b_n$ and $c_n$ which depend only on n and $6V{6}_{\infty }$ such that if h is a $C^2$ function defined on M with $\mathrm{\Delta }h??c_n{a}^2$ and ${\mathrm{lim?sup}}_{R\to \infty }{R}^{\mathrm{?2}}{\min }_{x\in B_p(3R)?B_p(R)}h(x)??b_n{a}^2$, where $0?a<{\mathrm{lim?inf}}_{j\to \infty }h(z_j)$, where $(z_j)$ is a sequence of M such that $r(z_j)\to \infty$, then the equation $\mathrm{\Delta }u(x)+V(x)?\mathrm{?}u(x)+h(x)u(x)=0$ has no positive $C^2$ solution on M. To cite this article: S. Asserda, C. R. Acad. Sci. Paris, Ser. I 342 (2006).