A simple and space-efficient fragment-chaining algorithm for alignment of DNA and protein sequences

In the segment-based approach to sequence alignment, nucleic acid, and protein sequence alignments are constructed from fragments, i.e., from pairs of ungapped segments of the input sequences. Given a set F of candidate fragments and a weighting function w : F → R⁺₀, the score of an alignment is defined as the sum of weights of the fragments it consists of, and the optimization problem is to find a consistent collection of pairwise disjoint fragments with maximum sum of weights. Herein, a sparse dynamic programming algorithm is described that solves the pairwise segment-alignment problem in O(L + N_max) space where L is the maximum length of the input sequences while N_max ≤ #F holds. With a recently introduced weighting function w, small sets F of candidate fragments are sufficient to obtain alignments of high quality. As a result, the proposed algorithm runs in essentially linear space.     

Indecomposable modules over one-dimensional Noetherian rings

In this article we consider finitely generated torsion-free modules over certain one-dimensional commutative Noetherian rings R. We assume there exists a positive integer N_R such that, for every indecomposable R-module M and for every minimal prime ideal P of R, the dimension of M_P, as a vector space over the field R_P, is less than or equal to N_R. If a nonzero indecomposable R-module M is such that all the localizations M_P as vector spaces over the fields R_P have the same dimension r, for every minimal prime P of R, then r=1,2,3,4 or 6. Let n be an integer ≥8. We show that if M is an R-module such that the vector space dimensions of the M_P are between n and 2n−8, then M decomposes non-trivially. For each n≥8, we exhibit a semilocal ring and an indecomposable module for which the relevant dimensions range from n to 2n−7. These results require a mild equicharacteristic assumption; we also discuss bounds in the non-equicharacteristic case.     

Rank-sets of indecomposable modules over one-dimensional rings

Let R be a one-dimensional, reduced Noetherian ring with finite normalization, and suppose there exists a positive integer N_R such that, for every indecomposable finitely generated torsion-free R-module M and every minimal prime ideal P of R, the dimension of M_P, as a vector space over the localization R_P (a field), is less than or equal to N_R. For a finitely generated torsion-free R-module M, we call the set of all such vector-space dimensions the rank-set of M. What subsets of the integers arise as rank-sets of indecomposable finitely generated torsion-free R-modules? In this article, we give more information on rank-sets of indecomposable modules, to supplement previous work concerning this question. In particular we provide examples having as rank-sets those intervals of consecutive integers that are not ruled out by an earlier article of Arnavut, Luckas and Wiegand. We also show that certain non-consecutive rank-sets never arise.     

A new formula for the volume of lattice polyhedra

LetL _n be the lattice consisting of all pointsx inR ^N such thatnx belongs to the fundamental latticeL ₁ of points with integer coordinates. When the vertices of a polyhedronP inR ^N are restricted to lie inL ₁ there is a formula which relates the volume ofP to the numbers of points ofL ₁,...,L _N in the interior and on the boundary ofP. The aim of this note is to show that the volume ofP can be determined only by means of the numbers of points ofL ₁,...,L _N lying in the interior ofP and cannot be expressed by the numbers of points ofL ₁,...,L _N lying on the boundary ofP. The latter numbers in turn can be used to compute to comopute the Euler characteristic of the boundary ofP.     

From U-bounds to isoperimetry with applications to H-type groups

In this paper we study U-bounds in relation to L₁-type coercive inequalities and isoperimetric problems for a class of probability measures on a general metric space (RN,d). We prove the equivalence of an isoperimetric inequality with several other coercive inequalities in this general framework. The usefulness of our approach is illustrated by an application to the setting of H-type groups, and an extension to infinite dimensions.     

On shortest disjoint paths in planar graphs

For a graph G and a collection of vertex pairs {(s₁,t₁),…,(s_k,t_k)}, the k disjoint paths problem is to find k vertex-disjoint paths P₁,…,P_k, where P_i is a path from s_i to t_i for each i=1,…,k. In the corresponding optimization problem, the shortest disjoint paths problem, the vertex-disjoint paths P_i have to be chosen such that a given objective function is minimized. We consider two different objectives, namely minimizing the total path length (minimum sum, or short: Min-Sum), and minimizing the length of the longest path (Min-Max), for k=2,3.Min-Sum: We extend recent results by Colin de Verdière and Schrijver to prove that, for a planar graph and for terminals adjacent to at most two faces, the Min-Sum 2 Disjoint Paths Problem can be solved in polynomial time. We also prove that, for six terminals adjacent to one face in any order, the Min-Sum 3 Disjoint Paths Problem can be solved in polynomial time.Min-Max: The Min-Max 2 Disjoint Paths Problem is known to be NP-hard for general graphs. We present an algorithm that solves the problem for graphs with tree-width 2 in polynomial time. We thus close the gap between easy and hard instances, since the problem is weakly NP-hard for graphs with tree-width 3.     

Gluings of surfaces with polygonal boundaries

By pairwise gluing edges of a polygon, one obtains two-dimensional surfaces with handles and holes. We compute the number N _g,L (n ₁, ..., n _L ) of distinct ways to obtain a surface of given genus g whose boundary consists of L polygonal components with given numbers n ₁, ..., n _L of edges. Using combinatorial relations between graphs on real two-dimensional surfaces, we derive recursion relations between the N _g,L . We show that the Harer-Zagier numbers arise as a special case of N _g,L and derive a new closed-form expression for them.     

Co-NP-completeness of some matrix classification problems

The classes of P-, P ₀-, R ₀-, semimonotone, strictly semimonotone, column sufficient, and nondegenerate matrices play important roles in studying solution properties of equations and complementarity problems and convergence/complexity analysis of methods for solving these problems. It is known that the problem of deciding whether a square matrix with integer/rational entries is a P- (or nondegenerate) matrix is co-NP-complete. We show, through a unified analysis, that analogous decision problems for the other matrix classes are also co-NP-complete. Received: April 1999 / Accepted: March 1, 2000?Published online May 12, 2000     

Two versions of the Nikodym maximal function on the Heisenberg group

The classical Nikodym maximal function on the Euclidean plane R² is defined as the supremum over averages over rectangles of eccentricity N; its operator norm in L²(R²) is known to be O(logN). We consider two variants, one on the standard Heisenberg group H¹ and the other on the polarized Heisenberg group . The latter has logarithmic L² operator norm, while the former has the L² operator norm which grows essentially of order O(N1/4). We shall imbed these two maximal operators in the family of operators associated to the hypersurfaces {(x₁,x₂,αx₁x₂)} in the Heisenberg group H¹ where the exceptional blow up in N occurs when α=0.     

Bounds for indecomposable torsion-free modules

Let M be a finitely generated torsion-free module over a one-dimensional reduced Noetherian ring R with finitely generated normalization. The rank of M is the tuple of vector-space dimensions of M_P over each field R_P (R localized at P), where P ranges over the minimal prime ideals of R. We assume that there exists a bound N_R on the ranks of all indecomposable finitely generated torsion-free R-modules. For such rings, what bounds and ranks occur? Partial answers to this question have been given by a plethora of authors over the past forty years. In this article we provide a final answer by giving a concise list of the ranks of indecomposable modules for R a local ring with no condition on the characteristic. We conclude that if the rank of an indecomposable module M is (r,r,…,r), then r∈{1,2,3,4,6}, even when R is not local.     

On a Minimum Linear Classification Problem

We study the following linear classification problem in signal processing: Given a set B of n black point and a set W of m white points in the plane (m=O(n)), compute a minimum number of lines L such that in the arrangement of L each face contain points with the same color (i.e., either all black points or all white points). We call this the Minimum Linear Classification (MLC) problem. We prove that MLC is NP-complete by a reduction from the Minimum Line Fitting (MLF) problem; moreover, a C-approximation to Minimum Linear Classification implies a C-approximation to the Minimum Line Fitting problem. Nevertheless, we obtain an O(log _n )-factor algorithm for MLC and we also obtain an O(log _Z)-factor algorithm for MLC where Z is the minimum number of disjoint axis-parallel black/white rectangles covering B and W.     

POLARITIES FOR NEARRINGS

Abstract

We show that the left and right polar sets of a nearring N form complete bounded lattices P_R(N) and P_L(N). We consider properties of P_L(N) and its elements, which are ideals, when N is 3-semiprime. If in addition N is zero-symmetric we strengthen these results and use them to describe a class in which 3-semiprime nearrings are strongly 3-semiprime.     

Some isoperimetric norm bounds for solutions of the helmholtz equation

Summary Previous results of the authors [2] relating theL ₁ andL ₂ integrals of the first eigenfunction in the two dimensional fixed membrane problem are here extended to the analogous problem in higher dimensions.

---

Zusammenfassung Frühere Resultate der Verfasser [2], welche eine Beziehung zwischen demL ₁- und demL ₂-Integral der ersten Eigenfunktion einer zweidimensionalen eingespannten Membran ergaben, werden hier auf das analoge Problem in höheren Dimensionen erweitert.

     

On the conjugacy problem in the group F/N 1 ∩ N 2

Let N ₁ (N ₂) be the normal closure of a finite symmetrized set R ₁ (R ₂, respectively) in a finitely generated free group F = F(A). As is known, if R _i satisfies condition C(6), then the conjugacy problem is decidable in F/N _i . In the paper, it is proved that, if one adds to condition C(6) on the set R ₁ ∪ R ₂ the atoricity condition for the presentation 〈A | R ₁, R ₂〉, then the conjugacy problem is decidable in the group F/N ₁ ∩ N ₂ as well. In particular, for the decidability of the conjugacy problem in F/N ₁ ∩ N ₂, it is sufficient to assume that the set R ₁ ∪ R ₂ satisfies condition C(7).     

THE P-COTORSION DIMENSIONS OF MODULES AND RINGS

Let R be a ring. We define a dimension, called P-cotorsion dimension, for modules and rings. The aim of this article is to investigate P-cotorsion dimensions of modules and rings and the relations between P-cotorsion dimension and other homological dimensions. This dimension has nice properties when the ring in consideration is generalized morphic.     

Locating an axis-parallel rectangle on a Manhattan plane

In this paper we consider the problem of locating an axis-parallel rectangle in the plane such that the sum of distances between the rectangle and a finite point set is minimized, where the distance is measured by the Manhattan norm ? ₁. In this way we solve an extension of the Weber problem to extensive facility location. As a model, our problem is appropriate for position sensing of rectangular objects.     

A remark concerning the theory of scattering for a perturbed polyharmonic operator

Let R₀ and R be resolvents of the operators (?δ) ^l and (?δ) ^l +q acting in L₂(E^m). We study the problem of the belonging of the operator R^P?R ₀ ^p to various symmetrically-normed ideals of the ring of bounded operators. We give applications to the theory of scattering.     

A duality principle for groups

The duality principle for Gabor frames states that a Gabor sequence obtained by a time-frequency lattice is a frame for L²(Rd) if and only if the associated adjoint Gabor sequence is a Riesz sequence. We prove that this duality principle extends to any dual pairs of projective unitary representations of countable groups. We examine the existence problem of dual pairs and establish some connection with classification problems for II₁ factors. While in general such a pair may not exist for some groups, we show that such a dual pair always exists for every subrepresentation of the left regular unitary representation when G is an abelian infinite countable group or an amenable ICC group. For free groups with finitely many generators, the existence problem of such a dual pair is equivalent to the well-known problem about the classification of free group von Neumann algebras.