Chaining algorithms for multiple genome comparison

Given n fragments from k>2 genomes, Myers and Miller showed how to find an optimal global chain of colinear non-overlapping fragments in O(nlog^kn) time and O(nlog^k−1n) space. For gap costs in the L₁-metric, we reduce the time complexity of their algorithm by a factor and the space complexity by a factor logn. For the sum-of-pairs gap cost, our algorithm improves the time complexity of their algorithm by a factor . A variant of our algorithm finds all significant local chains of colinear non-overlapping fragments. These chaining algorithms can be used in a variety of problems in comparative genomics: the computation of global alignments of complete genomes, the identification of regions of similarity (candidate regions of conserved synteny), the detection of genome rearrangements, and exon prediction.     

On minimizing pattern splitting in multi-track string matching

Given a pattern string P=p₁p₂p_m and K parallel text strings over an integer alphabet Σ, our task is to find the smallest integer κ>0 such that P can be split into κ pieces P=P¹…P^κ, where each Pⁱ has an occurrence in some text track T^k_i and these partial occurrences retain the order. We study some variations of this minimum splitting problem, such as splittings with limited gaps and transposition invariance, and show how to use sparse dynamic programming to solve the variations efficiently. In particular, we show that the minimum splitting problem can be interpreted as a shortest path problem on line segments.     

Linear time isotonic and unimodal regression in the and norms

We consider L₁-isotonic regression and L_∞ isotonic and unimodal regression. For L₁-isotonic regression, we present a linear time algorithm when the number of outputs are bounded. We extend the algorithm to construct an approximate isotonic regression in linear time when the output range is bounded. We present linear time algorithms for L_∞ isotonic and unimodal regression.     

An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality

We consider the asymmetric traveling salesperson problem with γ-parameterized triangle inequality for γ[1/2,1). That means, the edge weights fulfill w(u,v)γ(w(u,x)+w(x,v)) for all nodes u,v,x. Chandran and Ram [L.S. Chandran, L.S. Ram, Approximations for ATSP with parametrized triangle inequality, in: Proc. 19th Int. Symp. on Theoret. Aspects of Comput. Sci. (STACS), in: Lecture Notes in Comput. Sci., vol. 2285, Springer, Berlin, 2002, pp. 227–237] gave the first constant factor approximation algorithm with polynomial running time for this problem. They achieve performance ratio γ/(1−γ). We devise an approximation algorithm with performance ratio (1+γ)/(2−γ−γ³), which is better for γ[0.5437,1), that is, for the particularly interesting large values of γ.     

A loop-free two-close Gray-code algorithm for listing k-ary Dyck words

P. Chase and F. Ruskey each published a Gray code for length n binary strings with m occurrences of 1, coding m-combinations of n objects, which is two-close—that is, in passing from one binary string to its successor a single 1 exchanges positions with a 0 which is either adjacent to the 1 or separated from it by a single 0. If we impose the restriction that any suffix of a string contains at least k−1 times as many 0's as 1's, we obtain k-suffixes: suffixes of k-ary Dyck words. Combinations are retrieved as special case by setting k=1 and k-ary Dyck words are retrieved as a special case by imposing the additional condition that the entire string has exactly k−1 times as many 0's as 1's. We generalize Ruskey's Gray code to the first two-close Gray code for k-suffixes and we provide a loop-free implementation for k2. For k=1 we use a simplified version of Chase's loop-free algorithm for generating his two-close Gray code for combinations. These results are optimal in the sense that there does not always exist a Gray code, either for combinations or Dyck words, in which the 1 and the 0 that exchange positions are adjacent.     

Area-preserving approximations of polygonal paths

Let P be an x-monotone polygonal path in the plane. For a path Q that approximates P let W_A(Q) be the area above P and below Q, and let W_B(Q) be the area above Q and below P. Given P and an integer k, we show how to compute a path Q with at most k edges that minimizes W_A(Q)+W_B(Q). Given P and a cost C, we show how to find a path Q with the smallest possible number of edges such that W_A(Q)+W_B(Q)C. However, given P, an integer k, and a cost C, it is NP-hard to determine if a path Q with at most k edges exists such that max{W_A(Q),W_B(Q)}C. We describe an approximation algorithm for this setting. Finally, it is also NP-hard to decide whether a path Q exists such that |W_A(Q)−W_B(Q)|=0. Nevertheless, in this error measure we provide an algorithm for computing an optimal approximation up to an additive error.     

An improved algorithm for generalized comparison of minisatellites

One of the most important objects in genetic mapping and forensic studies are minisatellites. They consist of a heterogeneous tandem array of short repeat units called variants. The evolution of minisatellites is realized by tandem duplication and tandem deletion of variants. Jeffrey et al. proposed a method to obtain the sequence of variants, called maps. Bérard and Rivals designed the first algorithm of comparison of two minisatellite maps under an evolutionary model including deletion, insertion, mutation, amplification and contraction. The complexity of this first algorithm was O(n⁴) in time and O(n³) in space where n is the size of the maps. In this paper we propose a more efficient algorithm using the same generic evolutionary model which is O(n³) in time and O(n²) in space. Our algorithm with this better efficiency can even solve generalized and more refined models.     

Constructing suffix arrays in linear time

The time complexity of suffix tree construction has been shown to be equivalent to that of sorting: O(n) for a constant-size alphabet or an integer alphabet and O(nlogn) for a general alphabet. However, previous algorithms for constructing suffix arrays have the time complexity of O(nlogn) even for a constant-size alphabet.

In this paper we present a linear-time algorithm to construct suffix arrays for integer alphabets, which do not use suffix trees as intermediate data structures during its construction. Since the case of a constant-size alphabet can be subsumed in that of an integer alphabet, our result implies that the time complexity of directly constructing suffix arrays matches that of constructing suffix trees.     

Uniform asymptotic expansions of the Pollaczek polynomials

Two uniform asymptotic expansions are obtained for the Pollaczek polynomials P_n(cosθ;a,b). One is for , , in terms of elementary functions and in descending powers of . The other is for , in terms of a special function closely related to the modified parabolic cylinder functions, in descending powers of n. This interval contains a turning point and all possible zeros of P_n(cosθ) in θ(0,π/2].     

Extracting approximate patterns

In this paper, we define a family of patterns with don't cares occurring in a text. We call them primitive patterns. The set of primitive patterns forms a basis for all the maximal patterns occurring in the text. The number of primitive patterns is smaller than other known basis.

We present an incremental algorithm that computes the primitive patterns occurring at least q times in a text of length n, given the N primitive patterns occurring at least q−1 times, in time O(|Σ|Nn²logn), where Σ is the alphabet. In the particular case where q=2, the complexity in time is only O(|Σ|n²logn). We also give an algorithm that decides if a given pattern is primitive in a given text. These algorithms are generalized, taking many sequences in input. Finally, we give a solution for reducing the number of patterns of interest by using scoring techniques, as we show that the number of primitive patterns is exponential.     

Constrained tree inclusion

The tree matching problem is considered of given labeled trees P and T, determining if the pattern tree P can be obtained from the text tree T by deleting degree-one and degree-two nodes and, in the case of unordered trees, by also permuting siblings. The constrained tree inclusion problem is more sensitive to the structure of the pattern tree than the general tree inclusion problem. Further, it can be solved in polynomial time for both unordered and ordered trees. Algorithms based on the restricted subtree homeomorphism algorithm of M.-J. Chung [J. Algorithms 8 (1) (1987) 106–112] are presented that solve the constrained tree inclusion problem in O(m^1.5n) time on unordered trees with m and n nodes, and in O(mn) time on ordered trees, using O(mn) additional space.     

Ore-type degree condition for heavy paths in weighted graphs

A weighted graph is one in which every edge e is assigned a nonnegative number w(e), called the weight of e. For a vertex v of a weighted graph, d^w(v) is the sum of the weights of the edges incident to v. And the weight of a path is the sum of the weights of the edges belonging to it. In this paper, we give a sufficient condition for a weighted graph to have a heavy path which joins two specified vertices. Let G be a 2-connected weighted graph and let x and y be distinct vertices of G. Suppose that d^w(u)+d^w(v)2d for every pair of non-adjacent vertices u and vV(G) x,y . Then x and y are joined by a path of weight at least d, or they are joined by a Hamilton path. Also, we consider the case when G has some vertices whose weighted degree are not assumed.     

Limit shape of convex lattice polygons with minimal perimeter

Let n be a positive integer and · any norm in . Denote by B the unit ball of · and the class of convex lattice polygons with n vertices and least ·-perimeter. We prove that after suitable normalization, all members of tend to a fixed convex body, as n→∞.     

On partitioning two matroids into common independent subsets

Let M₁ and M₂ be two matroids on the same ground set S. We conjecture that if there do not exist disjoint subsets A₁,A₂,…,A_k+1 of S, such that _isp_M1(A_i)≠Ø, and similarly for M₂, then S is partitioned into k sets, each independent in both M₁ and M₂. This is a possible generalization of König's edge-coloring theorem. We prove the conjecture for the case k=2 and for a regular case, in which both matroids have the same rank d, and S consists of k·d elements. Finally, we prove another special case related to a conjecture of Rota.     

Fractal sets determined by dilation-stable processes

Let be a dilation-stable process on . We determine a Hausdorff measure function (a) such that the fractal set X[0,1]={X(t):0t1} has positive finite -measure. We also investigate the packing measure of X[0,1].     

On relations between 1-lines of Adams–Novikov spectral sequences modulo invariant prime ideals

We have a ring homomorphism Θ from the cohomology of the extended Morava stabilizer group G_n with coefficients in F[w^±1] to the cohomology of G_n+1 with coefficients in the graded field F((u_n))[u^±1]. In this note we study the behavior of Θ on H¹. Then it is shown that Θ is injective on H¹ for n1 and for all primes p.     

Proximity problems on line segments spanned by points

Finding the closest or farthest line segment (line) from a point are fundamental proximity problems. Given a set S of n points in the plane and another point q, we present optimal O(nlogn) time, O(n) space algorithms for finding the closest and farthest line segments (lines) from q among those spanned by the points in S. We further show how to apply our techniques to find the minimum (maximum) area triangle with a vertex at q and the other two vertices in S{q} in optimal O(nlogn) time and O(n) space. Finally, we give an O(nlogn) time, O(n) space algorithm to find the kth closest line from q and show how to find the k closest lines from q in O(nlogn+k) time and O(n+k) space.     

On periodic radical groups in which permutability is a transitive relation

A group G is said to be a -group if permutability is a transitive relation in the set of all subgroups of G. Our purpose in this paper is to study -groups in the class of periodic radical groups satisfying min-p for all primes p.     

Countable choice and compactness

We work in set-theory without choice ZF. Denoting by the countable axiom of choice, we show in that the closed unit ball of a uniformly convex Banach space is compact in the convex topology (an alternative to the weak topology in ZF). We prove that this ball is (closely) convex-compact in the convex topology. Given a set I, a real number p1 (respectively p=0), and some closed subset F of [0,1]^I which is a bounded subset of ℓ^p(I), we show that (respectively DC, the axiom of Dependent Choices) implies the compactness of F.     

General preservers of invariant subspace lattices

Let be the space of all bounded linear operators on a Banach space X and let LatA be the lattice of invariant subspaces of the operator . We characterize some maps with one of the following preserving properties: Lat(Φ(A)+Φ(B))=Lat(A+B), or Lat(Φ(A)Φ(B))=Lat(AB), or Lat(Φ(A)Φ(B)+Φ(B)Φ(A))=Lat(AB+BA), or Lat(Φ(A)Φ(B)Φ(A))=Lat(ABA), or Lat([Φ(A),Φ(B)])=Lat([A,B]).