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

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

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.     

Algorithms for Singleton Attractor Detection in Planar and Nonplanar AND/OR Boolean Networks

Singleton attractor (also called fixed point) detection is known to be NP-hard even for AND/OR Boolean networks (AND/OR BNs in short, i.e., BNs consisting of AND/OR nodes), where BN is a mathematical model of genetic networks and singleton attractors correspond to steady states. In our recent paper, we developed an O(1.787ⁿ) time algorithm for detecting a singleton attractor of a given AND/OR BN where n is the number of nodes. In this paper, we present an O(1.757ⁿ) time algorithm with which we succeeded in improving the above algorithm. We also show that this problem can be solved in time, which is less than O((1 + ∈)ⁿ) for any positive constant ∈, when a BN is planar. A preliminary version of this paper has appeared in Proc. 3rd International Conference on Algebraic Biology (AB2008) [27].     

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

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

Lempel–Ziv Factorization Using Less Time & Space

For 30 years the Lempel–Ziv factorization LZ _x of a string x = x[1..n] has been a fundamental data structure of string processing, especially valuable for string compression and for computing all the repetitions (runs) in x. Traditionally the standard method for computing LZ _x was based on Θ(n)-time (or, depending on the measure used, O(n log n)-time) processing of the suffix tree ST _x of x. Recently Abouelhoda et al. proposed an efficient Lempel–Ziv factorization algorithm based on an “enhanced” suffix array – that is, a suffix array SA _x together with supporting data structures, principally an “interval tree”. In this paper we introduce a collection of fast space-efficient algorithms for LZ factorization, also based on suffix arrays, that in theory as well as in many practical circumstances are superior to those previously proposed; one family out of this collection achieves true Θ(n)-time alphabet-independent processing in the worst case by avoiding tree structures altogether. The work of the first and third authors was supported in part by grants from the Natural Sciences & Engineering Research Council of Canada.     

Non-overlapping Common Substrings Allowing Mutations

This paper studies several combinatorial problems arising from finding the conserved genes of two genomes (i.e., the entire DNA of two species). The input is a collection of n maximal common substrings of the two genomes. The problem is to find, based on different criteria, a subset of such common substrings with maximum total length. The most basic criterion requires that the common substrings selected have the same ordering in the two genomes and they do not overlap among themselves in either genome. To capture mutations (transpositions and reversals) between the genomes, we do not insist the substrings selected to have the same ordering. Conceptually, we allow one ordering to go through some mutations to become the other ordering. If arbitrary mutations are allowed, the problem of finding a maximum-length, non-overlapping subset of substrings is found to be NP-hard. However, arbitrary mutations probably overmodel the problem and are likely to find more noise than conserved genes. We consider two criteria that attempt to model sparse and non-overlapping mutations. We show that both can be solved in polynomial time using dynamic programming.      

Diophantine Integral Geometry

In his works [1], [2] and [3], the author succeeded in establishing several inversion formulas for Radon transform on Euclidean space, Damek-Ricci space and also on a finite set. The present paper deals with Radon transform R on discrete hyperplanes in the lattice defined by linear diophantine equations. More precisely, we study carefully various natural questions in this context: specific properties of the discrete Radon transform R and its dual R*, inversion formula for R (see Theorem 4.1) and also an appropriate support theorem in the discrete case (see Theorem 5.3).      

Boundary Value Problems for the Helmholtz Equation in an Octant

We consider a class of boundary value problems for the three-dimensional Helmholtz equation that appears in diffraction theory. On the three faces of the octant, which are quadrants, we admit first order boundary conditions with constant coefficients, linear combinations of Dirichlet, Neumann, impedance and/or oblique derivative type. A new variety of surface potentials yields 3 × 3 boundary pseudodifferential operators on the quarterplane that are equivalent to the operators associated to the boundary value problems in a Sobolev space setting. These operators are analyzed and inverted in particular cases, which gives us the analytical solution of a number of well-posed problems. Dedicated to Vladimir G. Maz’ya on the occasion of his 70th birthday     

Investigating Algebraic and Logical Algorithms to Solve Hopf Bifurcation Problems in Algebraic Biology

Symbolic methods to investigate Hopf bifurcation problems of vector fields arising in the context of algebraic biology have recently obtained renewed attention. However, the symbolic investigations have not been fully algorithmic but required a sequence of symbolic computations intervened with ad hoc insights and decisions made by a human. In this paper we discuss the use of algebraic and logical methods to reduce questions on the existence of Hopf bifurcations in parameterized polynomial vector fields to quantifier elimination problems over the reals combined with the use of the quantifier elimination over the reals and simplification techniques available in REDLOG. We can reconstruct most of the results given in the literature within a few seconds of computation time and extend the investigations on these systems to previously not analyzed related systems. Especially we discuss cases in which one suspects that no Hopf bifurcation fixed point exists for biologically relevant values of parameters and system variables. Here we focus on logical and algebraic techniques of finding subconditions being inconsistent with the hypothesis of the existence of Hopf bifurcation fixed points.      

Automatic Proof of Graph Nonisomorphism

We describe automated methods for constructing nonisomorphism proofs for pairs of graphs. The proofs can be human-readable or machine-readable. We have developed an experimental implementation of an interactive webpage producing a proof of (non)isomorphism when given two graphs.      

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

Skew representations of twisted Yangians

Analogs of the classical Sylvester theorem have been known for matrices with entries in noncommutative algebras including the quantized algebra of functions on GL _N and the Yangian for $$ \mathfrak{g}\mathfrak{l}_{{N}} $$ . We prove a version of this theorem for the twisted Yangians $$ {\text{Y(}}\mathfrak{g}_{N} {\text{)}} $$associated with the orthogonal and symplectic Lie algebras $$ \mathfrak{g}_{N} = \mathfrak{o}_{N} {\text{ or }}\mathfrak{s}\mathfrak{p}_{N} $$. This gives rise to representations of the twisted Yangian $$ {\text{Y}}{\left( {\mathfrak{g}_{{N - M}} } \right)} $$ on the space of homomorphisms $$ {\text{Hom}}_{{\mathfrak{g}_{M} }} {\left( {W,V} \right)} $$, where W and V are finite-dimensional irreducible modules over $$ \mathfrak{g}_{{M}} {\text{ and }}\mathfrak{g}_{{N}} $$, respectively. In the symplectic case these representations turn out to be irreducible and we identify them by calculating the corresponding Drinfeld polynomials.We also apply the quantum Sylvester theorem to realize the twisted Yangian as a projective limit of certain centralizers in universal enveloping algebras.     

Lyapunov-type Inequalities for Differential Equations

Let us consider the linear boundary value problem

Small amplitude waves and stability for a pre-stressed viscoelastic solid

We study the propagation of small amplitude waves superimposed on a large static deformation in a nonlinear viscoelastic material of differential type. We use bulk waves and surface waves to address the questions of dissipation and of material and geometric stability. In particular, the analysis provides bounds on the constitutive parameters and on the predeformation that ensure linearized stability in the neighbourhood of a large pre-stretch. This type of result is relevant to the imaging of biological soft tissues using acoustical techniques, where pre-deformation is known to increase contrast and reduce de-correlation noise. This work was supported by GNFM (Italy) and by an International Joint Project grant awarded jointly by the Royal Society of London (UK) and the CNRS (France).     

Harmonic 1-Forms on Compact f-Manifolds

We consider a Riemannian manifold with a compatible f-structure which admits a parallelizable kernel. With some additional integrability conditions it is called -manifold. This class of manifolds is a natural generalization of the Sasakian manifolds. We study properties of harmonic 1-forms on such a manifold and deduce some topological properties. Research supported by the Italian MIUR 60% and GNSAGA. Professor J.J. Konderak died just during the preparation of this paper. His contribution has been substantial. Note of the Editor-in-Chief. Professor Jerzy J. Konderak passed away on September 14, 2005, at the age of 49. Born on February 12, 1956, in Krakow, Poland, he received his Ph.D. in 1986 from the Jagiellonian University of Krakow. Since 2003 he was associated professor of Mathematics at the Faculty of Sciences of the University of Bari. The main area of his scientific interests was Differential Geometry. Professor Konderak was a very gifted researcher and was appreciated by students and colleagues for his passion and devotion to Mathematics and its teaching. All the colleagues of the Department of Mathematics of the University of Bari will remember him not only as a clever mathematician but also as a men of rare quality.