We prove that many dynamical properties of group cellular automata (GCA) can be decided by decomposing them into a set of much simpler GCA, provided those properties are decidable for such simpler GCA. Specifically, we provide a novel algorithmic technique that decomposes the GCA under investigation into a finite number of GCA, some defined on abelian groups, while others, if any, on products of simple non-abelian isomorphic groups. Importantly, the groups resulting from the decomposition depend only on the original group and are therefore completely independent of both the automaton and the considered property. Consequently, they do not inherit any aspect of the complexity of the automaton under investigation. We study the inheritance of the dynamical properties in the original GCA versus the same properties in the GCA obtained through decomposition. The latter turn out to be significantly easier to analyze than in the original GCA. Then, we show that injectivity, surjectivity, and equicontinuity/sensitivity to initial conditions can be decided by testing them in the smaller GCA produced by the decomposition. Moreover, we prove that the topological entropy of a GCA can be computed, provided one knows how to compute it for GCA defined on products of simple non-abelian isomorphic groups – for which we explicitly prove how to compute it in the surjective case – and on abelian groups. Finally, we prove that no strongly transitive, and therefore no positively expansive, GCA defined on non-abelian groups exist.

We provide an efficient algorithm deciding chaos for linear cellular automata (LCA) over (Z/mZ)n, a large and important class of cellular automata (CA) which may exhibit many of the complex features typical of general CA and are used in many applications. The efficiency of our algorithm is mainly due to fact that it avoids the computation of the prime factor decomposition of m which is a well-known difficult task. Instead of factoring m we make use of a new and efficient generalized technique for computing the greatest common divisor (gcd) of polynomials with coefficients not belonging to a field, which in itself is an interesting result. We wish also to emphasize that the gcd computations required by our algorithm always involve polynomials of degree at most n. We also illustrate the impact of our algorithm in real-world applications regarding the growing domain of cryptosystems, the latter being often based on LCA over (Z/mZ)n with n>1. As a matter of facts, since cryptosystems have to satisfy the so-called confusion and diffusion properties (which are ensured if the involved LCA is chaotic) our algorithm turns out to be an important tool for building chaotic LCA over (Z/mZ)n and, hence, for improving the existing methods based on them.

Let $\mathbb{K}$ be a finite commutative ring, and let $\mathbb{L}$ be a commutative $\mathbb{K}$-algebra. Let $A$ and $B$ be two $n \times n$-matrices over $\mathbb{L}$ that have the same characteristic polynomial. The main result of this paper states that the set $\left\{ A^0,A^1,A^2,\ldots\right\}$ is finite if and only if the set $\left\{ B^0,B^1,B^2,\ldots\right\}$ is finite. We apply this result to Cellular Automata (CA). Indeed, it gives a complete and easy-to-check characterization of sensitivity to initial conditions and equicontinuity for linear CA over the alphabet $\mathbb{K}^n$ for $\mathbb{K} = \mathbb{Z}/m\mathbb{Z}$ i.e., CA in which the local rule is defined by $n\times n$-matrices with elements in $\mathbb{Z}/m\mathbb{Z}$. To prove our main result, we derive an integrality criterion for matrices that is likely of independent interest. Namely, let $\mathbb{K}$ be any commutative ring (not necessarily finite), and let $\mathbb{L}$ be a commutative $\mathbb{K}$-algebra. Consider any $n \times n$-matrix $A$ over $\mathbb{L}$. Then, $A \in \mathbb{L}^{n \times n}$ is integral over $\mathbb{K}$ (that is, there exists a monic polynomial $f \in \mathbb{K}\left[t\right]$ satisfying $f\left(A\right) = 0$) if and only if all coefficients of the characteristic polynomial of $A$ are integral over $\mathbb{K}$. The proof of this fact relies on a strategic use of exterior powers (a trick pioneered by Gert Almkvist). Furthermore, we extend the decidability result concerning sensitivity and equicontinuity to the wider class of additive CA over a finite abelian group. For such CA, we also prove the decidability of injectivity, surjectivity, topological transitivity and all the properties (as, for instance, ergodicity) that are equivalent to the latter.

We study the dynamical behavior of D-dimensional (D >= 1) additive cellular automata where the alphabet is any finite abelian group. This class of discrete time dynamical systems is a generalization of the systems extensively studied by many authors among which one may list [Masanobu Ito et al., 1983; Giovanni Manzini and Luciano Margara, 1999; Giovanni Manzini and Luciano Margara, 1999; Jarkko Kari, 2000; Gianpiero Cattaneo et al., 2000; Gianpiero Cattaneo et al., 2004]. Our main contribution is the proof that topologically transitive additive cellular automata are ergodic. This result represents a solid bridge between the world of measure theory and that of topology theory and greatly extends previous results obtained in [Gianpiero Cattaneo et al., 2000; Giovanni Manzini and Luciano Margara, 1999] for linear CA over Z_m i.e. additive CA in which the alphabet is the cyclic group Z_m and the local rules are linear combinations with coefficients in Z_m. In our scenario, the alphabet is any finite abelian group and the global rule is any additive map. This class of CA strictly contains the class of linear CA over Z_m^n, i.e. , with the local rule defined by n x n matrices with elements in Z_m which, in turn, strictly contains the class of linear CA over Z_m. In order to further emphasize that finite abelian groups are more expressive than Z_m we prove that, contrary to what happens in Z_m, there exist additive CA over suitable finite abelian groups which are roots (with arbitrarily large indices) of the shift map. As a consequence of our results, we have that, for additive CA, ergodic mixing, weak ergodic mixing, ergodicity, topological mixing, weak topological mixing, topological total transitivity and topological transitivity are all equivalent properties. As a corollary, we have that invertible transitive additive CA are isomorphic to Bernoulli shifts. Finally, we provide a first characterization of strong transitivity for additive CA which we suspect it might be true also for the general case.

BACKGROUND: Functional annotation of genes and gene products is a major challenge in the post-genomic era. Nowadays, gene function curation is largely based on manual assignment of Gene Ontology (GO) annotations to genes by using published literature. The annotation task is extremely time-consuming, therefore there is an increasing interest in automated tools that can assist human experts. RESULTS: Here we introduce GOTA, a GO term annotator for biomedical literature. The proposed approach makes use only of information that is readily available from public repositories and it is easily expandable to handle novel sources of information. We assess the classification capabilities of GOTA on a large benchmark set of publications. The overall performances are encouraging in comparison to the state of the art in multi-label classification over large taxonomies. Furthermore, the experimental tests provide some interesting insights into the potential improvement of automated annotation tools. CONCLUSIONS: GOTA implements a flexible and expandable model for GO annotation of biomedical literature. The current version of the GOTA tool is freely available at http://gota.apice.unibo.it.

We investigate the relationships between dynamical complexity and the set of periodic configurations of surjective Cellular Automata. We focus on the set of strictly temporally periodic configurations, i.e., the set of those configurations which are

The attractor properties in Cellular Automata dynamical systems have been extensively investigated and well characterized. We consider here two attractor classification for Cellular Automata and we prove the computational undecidability of some quest

Correlated mutations in proteins are believed to occur in order to preserve the protein functional folding through evolution. Their values can be deduced from sequence and/or structural alignments and are indicative of residue contacts in the protein three-dimensional structure. A correlation among pairs of residues is routinely evaluated with the Pearson correlation coefficient and the MCLACHLAN similarity matrix. In literature, there is no justification for the adoption of the MCLACHLAN instead of other substitution matrices. In this paper, we approach the problem of computing the optimal similarity matrix for contact prediction with correlated mutations, i.e., the similarity matrix that maximizes the accuracy of contact prediction with correlated mutations. We describe an optimization procedure, based on the gradient descent method, for computing the optimal similarity matrix and perform an extensive number of experimental tests. Our tests show that there is a large number of optimal matrices that perform similarly to MCLACHLAN. We also obtain that the upper limit to the accuracy achievable in protein contact prediction is independent of the optimized similarity matrix. This suggests that the poor scoring of the correlated mutations approach may be due to the choice of the linear correlation function in evaluating correlated mutations.

MOTIVATION: Searching for structural similarity is a key issue of protein functional annotation. The maximum contact map overlap (CMO) is one of the possible measures of protein structure similarity. Exact and approximate methods known to optimize the CMO are computationally expensive and this hampers their applicability to large-scale comparison of protein structures. RESULTS: In this article, we describe a heuristic algorithm (Al-Eigen) for finding a solution to the CMO problem. Our approach relies on the approximation of contact maps by eigendecomposition. We obtain good overlaps of two contact maps by computing the optimal global alignment of few principal eigenvectors. Our algorithm is simple, fast and its running time is independent of the amount of contacts in the map. Experimental testing indicates that the algorithm is comparable to exact CMO methods in terms of the overlap quality, to structural alignment methods in terms of structure similarity detection and it is fast enough to be suited for large-scale comparison of protein structures. Furthermore, our preliminary tests indicates that it is quite robust to noise, which makes it suitable for structural similarity detection also for noisy and incomplete contact maps. AVAILABILITY: Available at http://bioinformatics.cs.unibo.it/Al-Eigen.

Cellular Automata (CA) are discrete dynamical systems and an abstract model of parallel computation. The limit set of a cellular automaton is its maximal topological attractor. A well know result, due to Kari, says that all nontrivial properties of limit sets are undecidable. In this paper we consider properties of limit set dynamics, i.e. properties of the dynamics of Cellular Automata restricted to their limit sets. There can be no equivalent of Kari's Theorem for limit set dynamics. Anyway we show that there is a large class of undecidable properties of limit set dynamics, namely all properties of limit set dynamics which imply stability or the existence of a unique subshift attractor. As a consequence we have that it is undecidable whether the cellular automaton map restricted to the limit set is the identity, closing, injective, expansive, positively expansive, transitive.

Abstract Summary: Fault Tolerant Contact Map Reconstruction (FT-COMAR) is a heuristic algorithm for the reconstruction of the protein three-dimensional structure from (possibly) incomplete (i.e. containing unknown entries) and noisy contact maps. FT-COMAR runs within minutes, allowing its application to a large-scale number of predictions. Availability: http://bioinformatics.cs.unibo.it/FT-COMAR Contact: [email protected] Supplementary information: Supplementary data are available on Bioinformatics online.

The prediction of the protein tertiary structure from solely its residue sequence (the so called Protein Folding Problem) is one of the most challenging problems in Structural Bioinformatics. We focus on the protein residue contact map. When this map is assigned it is possible to reconstruct the 3D structure of the protein backbone. The general problem of recovering a set of 3D coordinates consistent with some given contact map is known as a unit-disk-graph realization problem and it has been recently proven to be NP-Hard. In this paper we describe a heuristic method (COMAR) that is able to reconstruct with an unprecedented rate (3-15 seconds) a 3D model that exactly matches the target contact map of a protein. Working with a non-redundant set of 1760 proteins, we find that the scoring efficiency of finding a 3D model very close to the protein native structure depends on the threshold value adopted to compute the protein residue contact map. Contact maps whose threshold values range from 10 to 18 Angstroms allow reconstructing 3D models that are very similar to the proteins native structure.

We prove a number of negative results about practical (i.e., work efficient and numerically accurate) algorithms for computing the main matrix factorizations. In particular, we prove that the popular Householder and Givens methods for computing the QR decomposition are P-complete, and hence presumably inherently sequential, under both real and floating point number models. We also prove that Gaussian elimination (GE) with a weak form of pivoting, which aims only at making the resulting algorithm nondegenerate, is likely to be inherently sequential as well. Finally, we prove that GE with partial pivoting is P-complete over GF(2) or when restricted to symmetric positive definite matrices, for which it is known that even standard GE (no pivoting) does not fail. Altogether, the results of this paper give further formal support to the widespread belief that there is a tradeoff between parallelism and accuracy in numerical algorithms.

ll;eprove allulllberof negaLive resultsahout practicaf (i.e., numerically accurate) algorithms for certain matrix factorization.In particular.we prow that the popular (;iwns' method for computing the QR decomposition is inherentl} sequential over the realistic model of floating point arithmetic.We also prove a number of additional results concerning Gaussian Elimination for computing the LIT decon]positiou..iltogether, the results of this paper sllpport the widespread belief that there is a tradeotlbetween palallclism and accuracy in numerical algorithms. 1 Introduction Matrix factorization algorithms form the hackhone of stateof-the-ar[ numerical libraries and packages, such as L.\-PACK and hfATL.%f3[9.1~].indeed, factoring ii matrix is almost always the first.step of mall: scient,ifir collll~ut.ations,ancl usually the one which places the heaviest demand in terms of computing resolwces.Among the rompl]t.ationsthat involve matrix factoriza( ions of sonle sort ~ve I.ccall linear system solution, eigenva]ue and least scll]ares alJproximirtion, and rank revealing 11.ansforlllikti{jlls. in Iicfv of this, some authors have invest j~.+t.e[]the parallel conlldcxity of the most popular matrix f&torizat.ion>.]M]IIVI) tlw (} ')L[" and QR(II) clecompositions (see .Appell~lix .1 for {ldinit,ions and simple properties)..4list of positive known resIIlt.sfol- Io\vs.q LL" clecolnposit,ion is in arithmetic ,1"('.}vlw]lef.erit exists, i.e., pro}"ided that tlw leaditl~Iwil]ripal minors "This Ivork haS lb y Esprit P!',)J@ WIT? (;l~Pl'-(""Oht,and by illurst 4077 and G1l'Zf{[ncls tn,,>art,l,,e,, ra<-ll [Ilsortllatlccl.IJl],,!rrs]t{i di Ptsn, ('~,rsu ltal[a 10, JGI05 pl~a, Italy, ~l)d I?,lc.cNFL \;ia S Nlaria .tli,.ZG12G }>lsO, ]ttl)y 13ma11lemlcin]&l UIIII>I II 'D,pamm,c.nrod, SCIK113: c lcC1lOb~l?,%\,a!1Z;3 ??, (l!>),,,.I'sI(;3 <{1 'IcmnO.\"Ia(.'avoIIr&,1511) 11.iiessailclr]a, [i+' an,{ lNt('-('Nrt \'la s Llal'la.l(i,5612(; Plsa, Italy 1~,111 all IIlal)z llllfl'lllllnl 1! , 'D1part.imento ,:11 Sclrllz.(lell'I 11ror111a7,1c,11,.(Jilivsl.11:1,11 Bologna, Alum A1ltKI 'Zallll)Olll i. .11)1?7 ttolcJ~lla It;ily 1<111311 )Ijargara

In this paper we introduce a technique for developing efficient iterated local search procedures and we apply it to solve very large instances of the Euclidean Traveling Salesman Problem (TSP). This technique, which we call perturbation, uses global information on TSP instances to speed-up the computation and to improve the quality of the tours found by heuristic methods. The main idea is to escape from local optima by introducing perturbations in the problem instance rather than in the solution. The performance of our algorithms has been tested and compared with known methods. To this end, we have executed a number of experiments both on available benchmarks, for which the optimal tour length is known, and on randomly generated instances, for which the comparison is done with the Held-Karp lower bound. The experimental results, performed on up to 100,000 cities, show that our algorithms outperform the known methods for iterating local search for very large instances.