Search

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.

Unlabelled: 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

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]

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]