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

Non-level semi-standard graded Cohen–Macaulay domain with h-vector (h0,h1,h2)

Let $\mathbb{k}$ be an algebraically closed field of characteristic 0, and $A={?}_{i\in \mathbb{N}}{A}_i$ a Cohen–Macaulay graded domain with $A_0=\mathbb{k}$. If A is semi-standard graded (i.e., A is finitely generated as a $\mathbb{k}[A_1]$-module), it has the h-vector$(h_0,h_1,\dots ,h_s)$, which encodes the Hilbert function of A. From now on, assume that $s=2$. It is known that if A is standard graded (i.e., $A=\mathbb{k}[A_1]$), then A is level. We will show that, in the semi-standard case, if A is not level, then $h_1+1$ divides $h_2$. Conversely, for any positive integers h and n, there is a non-level A with the h-vector $(1,h,(h+1)n)$. Moreover, such examples can be constructed as Ehrhart rings (equivalently, normal toric rings).     

On the Hochschild homology of quantum SL(N)

We show that the quantized coordinate ring $A:=k_q[\mathit{SL}(N)]$ satisfies van den Bergh's analogue of Poincaré duality for Hochschild (co)homology with dualizing bimodule being $A_{\sigma }$, the A-bimodule which is A as k-vector space with right multiplication twisted by the modular automorphism σ of the Haar functional. This implies that ${\mathrm{H}}_{N^2?1}(A,A_{\sigma })?k$, generalizing our previous result for $k_q[\mathit{SL}(2)]$. To cite this article: T. Hadfield, U. Krähmer, C. R. Acad. Sci. Paris, Ser. I 343 (2006).     

On Noether's problem for central extensions of symmetric and alternating groups

For a field k and a finite group G acting regularly on a set of indeterminates $\underset{?}{X}={\{X_g\}}_{g\in G}$, let $k(G)$ denote the invariant field $k{(\underset{?}{X})}^G$. We first prove for the alternating group $A_n$ that, if n is odd, then $\mathbb{Q}(A_n)$ is rational over $\mathbb{Q}(A_{n?1})$. We then obtain an analogous result where $A_n$ is replaced by an arbitrary finite central extension of either $A_n$ or $S_n$, valid over $\mathbb{Q}({\zeta }_N)$ for suitable N. Concrete applications of our results yield: (1) a new proof of Maeda's result on the rationality of $\mathbb{Q}{(X_1,\dots ,X_5)}^{A_5}/\mathbb{Q}$; (2) an affirmative answer to Noether's problem over $\mathbb{Q}$ for both $\stackrel{?}{A_5}$ and $\stackrel{?}{S_5}$; (3) an affirmative answer to Noether's problem over $\mathbb{C}$ for every finite central extension group of either $A_n$ or $S_n$ with $n?5$.