A New Approach to Pattern Matching in Degenerate DNA/RNA Sequences and Distributed Pattern Matching

In this paper, we consider the pattern matching problem in DNA and RNA sequences where either the pattern or the text can be degenerate, i.e., contain sets of characters. We present an asymptotically faster algorithm for the above problem that works in O(n log m) time, where n and m is the length of the text and the pattern respectively. We also suggest an efficient implementation of our algorithm, which works in linear time when the pattern size is small. Finally, we also describe how our approach can be used to solve the distributed pattern matching problem. The preliminary version of this paper appeared in [26].     

Parameterized Algorithms in Smooth 4-Regular Hamiltonian Graphs

Smooth 4-regular hamiltonian graphs are generalizations of cycle plus triangles graphs. It has been shown that both the independent set and 3-colorability problems are NP-Complete in this class of graphs. In this paper we show that these problems are fixed parameter tractable if we choose the number of inner cycles as parameter. The reseach has been supported by International Science Programme (ISP) of Sweden, under the project titled “The Eastern African Universities Mathematics Programme (EAUMP)”.     

A Tutorial on Computational Cluster Analysis with Applications to Pattern Discovery in Microarray Data

Microarrays offer unprecedented possibilities for the so-called omic, e.g., genomic and proteomic, research. However, they are also quite challenging data to analyze. The aim of this paper is to provide a short tutorial on the most common approaches used for pattern discovery and cluster analysis as they are currently used for microarrays, in the hope to bring the attention of the Algorithmic Community on novel aspects of classification and data analysis that deserve attention and have potential for high reward. R. Giancarlo is partially supported by Italian MIUR grants PRIN “Metodi Combinatori ed Algoritmici per la Scoperta di Patterns in Biosequenze” and FIRB “Bioinformatica per la Genomica e la Proteomica” and Italy-Israel FIRB Project “Pattern Discovery Algorithms in Discrete Structures, with Applications to Bioinformatics”. D. Scaturro is supported by a MIUR Fellowship in the Italy-Israel FIRB Project “Pattern Discovery Algorithms in Discrete Structures, with Applications to Bioinformatics”.     

Efficient Algorithms for Variants of Weighted Matching and Assignment Problems

Obtaining a matching in a graph satisfying a certain objective is an important class of graph problems. Matching algorithms have received attention for several decades. However, while there are efficient algorithms to obtain a maximum weight matching, not much is known about the maximum weight maximum cardinality, and maximum cardinality maximum weight matching problems for general graphs. Our contribution in this work is to show that for bounded weight input graphs one can obtain an algorithm for both maximum weight maximum cardinality (for real weights), and maximum cardinality maximum weight matching (for integer weights) by modifying the input and running the existing maximum weight matching algorithm. Also, given the current state of the art in maximum weight matching algorithms, we show that, for bounded weight input graphs, both maximum weight maximum cardinality, and maximum cardinality maximum weight matching have algorithms of similar complexities to that of maximum weight matching. Subsequently, we also obtain approximation algorithms for maximum weight maximum cardinality, and maximum cardinality maximum weight matching.      

Deriving Behavior of Boolean Bioregulatory Networks from Subnetwork Dynamics

In the well-known discrete modeling framework developed by R. Thomas, the structure of a biological regulatory network is captured in an interaction graph, which, together with a set of Boolean parameters, gives rise to a state transition graph describing all possible dynamical behaviors. For complex networks the analysis of the dynamics becomes more and more difficult, and efficient methods to carry out the analysis are needed. In this paper, we focus on identifying subnetworks of the system that govern the behavior of the system as a whole. We present methods to derive trajectories and attractors of the network from the dynamics suitable subnetworks display in isolation. In addition, we use these ideas to link the existence of certain structural motifs, namely circuits, in the interaction graph to the character and number of attractors in the state transition graph, generalizing and refining results presented in [10]. Lastly, we show for a specific class of networks that all possible asymptotic behaviors of networks in that class can be derived from the dynamics of easily identifiable subnetworks.      

A General Tractable Density Concept for Graphs

In many applications it is an important algorithmic task to find a densest subgraph in an input graph. The complexity of this task depends on how density is defined. If density means the ratio of the number of edges and the number of vertices in the subgraph, then the algorithmic problem has long been known efficiently solvable. On the other hand, the task becomes NP-hard with closely related but somewhat modified concepts of density. To capture many possible tractable density concepts of interest in a common model, we define and analyze a general concept of density, called F-density. Here F is a family of graphs and we are looking for a subgraph of the input graph, such that this subgraph is the densest in terms of containing the highest number of graphs from F relative to the size of the subgraph. We show that for any fixed finite family F, a subgraph of maximum F-density can be found in polynomial time. As our main tool we develop an algorithm, that may be of independent interest, which can find an independent set of maximum independence ratio in a certain class of weighted graphs. The independence ratio is the weight of the independent set divided by the weight of its neighborhood. This work was supported in part by NSF grants ANI-0220001 and CCF-0634848.     

Semi-local String Comparison: Algorithmic Techniques and Applications

Given two strings, the longest common subsequence (LCS) problem consists in computing the length of the longest string that is a subsequence of both input strings. Its generalisation, the all semi-local LCS problem, requires computing the LCS length for each string against all substrings of the other string, and for all prefixes of each string against all suffixes of the other string. We survey a number of algorithmic techniques related to the all semi-local LCS problem. We then present a number of algorithmic applications of these techniques, both existing and new. In particular, we obtain a new all semi-local LCS algorithm, with asymptotic running time matching (in the case of an unbounded alphabet) the fastest known global LCS algorithm by Masek and Paterson. We conclude that semi-local string comparison turns out to be a useful algorithmic plug-in, which unifies, and often improves on, a number of previous approaches to various substring- and subsequence-related problems. The author acknowledges the support of The University of Warwick’s DIMAP (the Centre for Discrete Mathematics and its Applications) during this work.     

Hilbert-Schmidt Hankel Operators on the Bergman Space of Planar Domains

In this paper we study the problem of the membership of H _ϕ in the Hilbert-Schmidt class, when and Ω is a planar domain. We find a necessary and sufficient condition.We apply this result to the problem of joint membership of H _φ and in the Hilbert-Schmidt class. Using the notion of Berezin Transform and a result of K. Zhu we are able to give a necessary and sufficient condition. Finally, we recover a result of Arazy, Fisher and Peetre on the case with φ holomorphic.     

On the Fourier spectrum of symmetric Boolean functions

We study the following questionWhat is the smallest t such that every symmetric boolean function on κ variables (which is not a constant or a parity function), has a non-zero Fourier coefficient of order at least 1 and at most t?We exclude the constant functions for which there is no such t and the parity functions for which t has to be κ. Let τ (κ) be the smallest such t. Our main result is that for large κ, τ (κ)≤4κ/logκ.The motivation for our work is to understand the complexity of learning symmetric juntas. A κ-junta is a boolean function of n variables that depends only on an unknown subset of κ variables. A symmetric κ-junta is a junta that is symmetric in the variables it depends on. Our result implies an algorithm to learn the class of symmetric κ-juntas, in the uniform PAC learning model, in time n ^o(κ) . This improves on a result of Mossel, O’Donnell and Servedio in [16], who show that symmetric κ-juntas can be learned in time n ^2κ/3.     

On SU(1,D)/[U(1,D),U(1,D)] for a quaternion division algebra D

Let D be a quaternion division algebra with an involution of the second kind. We show that the quotient group SU(1,D)/[U(1,D),U(1,D)] is nontrivial in general. For global fields, we completely determine this group. Received: 11 May 2007, Revised: 15 December 2007     

The Leray separating operator in the theory of the Cauchy problem

The paper is devoted to the presentation of Leray’s approach to the Cauchy problem for strictly hyperbolic operators. In the first section we give the main definitions of strictly hyperbolic operators and separating operators corresponding to them. We present the plan of derivation of the a priori estimates necessary for the proof of solvability of the Cauchy problem. In the second section we generalize the Leray approach to some classes of PDO which are not hyperbolic.     

Scoring Unusual Words with Varying Mismatch Errors

Patterns consisting of strings with a bounded number of mismatches are central to coding theory and find multiple applications in text processing and computational biology. In this latter field, the presence of over-represented patterns of this kind has been linked, for instance, to modeling regulatory regions in biosequences. The study and computation of expected number of occurrences and related scores for these patterns is made difficult by the sheer explosion of the roster of candidates that need to be evaluated. In recent work, properties of pattern saturation and score monotonicity have proved capable to mitigate this problem. In such a context, expectation and score monotonicity has been established within the i.i.d. model for all cases of interest except that of a fixed word length with a varying number of mismatches. The present paper completes this investigation by showing that the expected number of occurrences in a textstring for such a word is bi-tonic, that is, behaves as a unimodal function of the number of errors. This extends to this case the time and space savings brought about by discovery algorithms based on pattern saturation. Work Supported in part by the Italian Ministry of University and Research under the Bi-National Project FIRB RBIN04BYZ7, and by the Research Program of Georgia Tech. An extended abstract related to this work was presented at the Dagstuhl Seminar Dagstuhl on “Combinatorial and Algorithmic Foundations of Pattern and Association Discovery”, May 14-19, 2006 [3].     

Conditions for the spectrum associated with an asymptotically straight leaky wire to contain an interval [− α2/4, ∞)

The method of singular sequences is used to provide a simple and, in some respects, a more general proof of a known spectral result for leaky wires. The method introduces a new concept of asymptotic straightness. Received: 4 October 2007     

Schatten-von Neumann Hankel Operators on the Bergman Space of Planar Domains

In this paper we study the problem of the joint membership of Hφ and in the Schatten-von Neumann p-class when φ ∈ L∞(Ω) and Ω is a planar domain. We use a result of K. Zhu and the localization near the boundary to solve the problem. Finally, we recover a result of Arazy, Fisher and Peetre on the case with φ holomorphic.      

From Individuals to Populations: A Symbolic Process Algebra Approach to Epidemiology

Is it possible to symbolically express and analyse an individual-based model of disease spread, including realistic population dynamics? This problem is addressed through the use of process algebra and a novel method for transforming process algebra into Mean Field Equations. A number of stochastic models of population growth are presented, exploring different representations based on alternative views of individual behaviour. The overall population dynamics in terms of mean field equations are derived using a formal and rigorous rewriting based method. These equations are easily compared with the traditionally used deterministic Ordinary Differential Equation models and allow evaluation of those ODE models, challenging their assumptions about system dynamics. The utility of our approach for epidemiology is confirmed by constructing a model combining population growth with disease spread and fitting it to data on HIV in the UK population. This work was supported by EPSRC through a Doctoral Training Grant (CM, from 2004–2007), and through System Dynamics from Individual Interactions: A process algebra approach to epidemiology (EP/E006280/1, all authors, 2007–2010).     

Dynamic Multi-level Overlay Graphs for Shortest Paths

Multi-level overlay graphs represent a speed-up technique for shortest paths computation which is based on a hierarchical decomposition of a weighted directed graph G. They have been shown to be experimentally efficient, especially when applied to timetable information. However, no theoretical result on the cost of constructing, maintaining and querying multi-level overlay graphs in a dynamic environment is known. In this paper, we show theoretical properties of multi-level overlay graphs that lead us to the definition of a new data structure for the computation and the maintenance of an overlay graph of G while weight decrease or weight increase operations are performed on G. Our solution is theoretically faster than the recomputation from scratch and allows queries that can be performed more efficiently than running Dijkstra’s shortest paths algorithm on G. This work was partially supported by the Future and Emerging Technologies Unit of EC (IST priority – 6th FP), under contract no. FP6-021235-2 (project ARRIVAL).     

Group gradings on diagonal algebras

We describe all group gradings on the diagonal algebra k ⁿ , where k is an arbitrary field. Received: 21 January 2008     

Lyapunov-type Inequalities for Differential Equations

Let us consider the linear boundary value problem