Search

We investigate the computational complexity of deciding whether a given univariate integer polynomial p (x) has a factor q (x) satisfying specific additional constraints. When the only constraint imposed on q (x) is to have a degree smaller than the degree of p (x) and greater than zero, the problem is equivalent to testing the irreducibility of p (x) and then it is solvable in polynomial time. We prove that deciding whether a given monic univariate integer polynomial has factors satisfying additional properties is NP-complete in the strong sense. In particular, given any constant value k ∈ Z , we prove that it is NP-complete in the strong sense to detect the existence of a factor that returns a prescribed value when evaluated at x = k (Theorem 1) or to detect the existence of a pair of factors—whose product is equal to the original polynomial—that return the same value when evaluated at x = k (Theorem 2). The list of all the properties we have investigated in this paper is reported at the end of Section Introduction. [ABSTRACT FROM AUTHOR]

We study the following problem. Given a multiset M of non-negative integers, decide whether there exist and, in the positive case, compute two non-trivial multisets whose Minkowski sum is equal to M. The Minkowski sum of two multisets A and B is a multiset containing all possible sums of any element of A and any element of B. This problem was proved to be NP-complete when multisets are replaced by sets. This version of the problem is strictly related to the factorization of boolean polynomials that turns out to be NP-complete as well. When multisets are considered, the problem is equivalent to the factorization of polynomials with non-negative integer coefficients. The computational complexity of both these problems is still unknown. The main contribution of this paper is a heuristic technique for decomposing multisets of non-negative integers. Experimental results show that our heuristic decomposes multisets of hundreds of elements within seconds, independently of the magnitude of numbers belonging to the multisets. Our heuristic can also be used for factoring polynomials in N[x]. We show that, when the degree of the polynomials gets larger, our technique is much faster than the state-of-the-art algorithms implemented in commercial software like Mathematica and MatLab. [ABSTRACT FROM AUTHOR]

Abstract Background The present knowledge of protein structures at atomic level derives from some 60,000 molecules. Yet the exponential ever growing set of hypothetical protein sequences comprises some 10 million chains and this makes the problem of protein structure prediction one of the challenging goals of bioinformatics. In this context, the protein representation with contact maps is an intermediate step of fold recognition and constitutes the input of contact map predictors. However contact map representations require fast and reliable methods to reconstruct the specific folding of the protein backbone. Methods In this paper, by adopting a GRID technology, our algorithm for 3D reconstruction FT-COMAR is benchmarked on a huge set of non redundant proteins (1716) taking random noise into consideration and this makes our computation the largest ever performed for the task at hand. Results We can observe the effects of introducing random noise on 3D reconstruction and derive some considerations useful for future implementations. The dimension of the protein set allows also statistical considerations after grouping per SCOP structural classes. Conclusions All together our data indicate that the quality of 3D reconstruction is unaffected by deleting up to an average 75% of the real contacts while only few percentage of randomly generated contacts in place of non-contacts are sufficient to hamper 3D reconstruction.

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. [ABSTRACT FROM AUTHOR]

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 temporally but not spatially periodic for a given surjective automaton. The cardinality of this set turns out to be inversely related to the dynamical complexity of the cellular automaton. In particular, we show that for surjective Cellular Automata, the set of strictly temporally periodic configurations has strictly positive measure if and only if the cellular automaton is equicontinuous. Furthermore, we show that the set of strictly temporally periodic configurations is dense for almost equicontinuous surjective cellular automata, while it is empty for the positively expansive ones. In the class of additive cellular automata, the set of strictly temporally periodic points can be either dense or empty. The latter happens if and only if the cellular automaton is topologically transitive. This is not true for general transitive Cellular Automata, where the set of of strictly temporally periodic points can be non-empty and non-dense. [ABSTRACT FROM AUTHOR]

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 questions related to such classifications. [ABSTRACT FROM AUTHOR]

We attach to dynamics of cellular automata a sequence of shift spaces we call row subshifts sequence and we use row subshifts properties to investigate the topological entropy of cellular automata. [ABSTRACT FROM AUTHOR]

Presents a study which examined subshift behaviors of one-dimensional bi-infinite cellular automata. Background on one-dimensional cellular automaton; Conditions under which subshifts generated by cellular automaton systems exhibit some components of the chaotic behavior; Classification of all elementary cellular automata with respect to subshifts.

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. [ABSTRACT FROM AUTHOR]

Presents a study that introduced a technique for developing efficient iterated local search procedures and applied it to solve instances of the Euclidean Traveling Salesman Problem (TSP). Description of the Euclidean TSP; Iterating local search and the method of perturbation; Discussion of some implementation issues.

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. [ABSTRACT FROM PUBLISHER]

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.